求矩阵到幂k的迹

Question

我需要计算矩阵的轨迹到3和4的幂，它需要尽可能快。

这里的矩阵是一个简单图的邻接矩阵，因此它是正方形的，对称的，它的条目总是1或0，对角元素总是0。

对于矩阵的跟踪到2的幂，优化是很简单的：

• 我们只需要跟踪的对角线条目(i，i)，跳过所有其他的
• ，因为矩阵是对称的，这些条目只是第一行平方和求和
• 的条目，并且由于条目仅为1或0，所以平方操作可以跳过

。

我在维基百科上发现的另一个想法是总结Hadamard产品的所有元素，即入口乘法，但我不知道如何将这个方法扩展到3和4的幂。

请参阅http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Properties

也许我只是瞎了，但我想不出一个简单的解决办法。

最后，我需要一个C++实现，但我认为这对这个问题并不重要。

提前感谢您的帮助。

Answer 1

好吧，我自己想出来的。我不知道的重要一点是：

如果A是有向或无向图G的邻接矩阵，那么矩阵An (即A的n个拷贝的矩阵乘积)有一个有趣的解释:第I行和列j中的条目给出长度为n的(有向或无向)从顶点I到顶点j的步数。例如，这意味着一个无向图G中的三角形数正好是A^3除以6的迹。

(复制自http://en.wikipedia.org/wiki/Adjacency_matrix#Properties)

当处理稀疏图和使用邻接列表代替矩阵时，可以在O(n)中从节点I到i检索给定长度的路径数。

不过，谢谢你的回答！

Answer 2

迹是特征值的和，矩阵幂的特征值就是该幂的特征值。

也就是说，如果l_1，.，l_n是矩阵的特征值，那么跟踪(M^p)= 1_1^p + l_2^p +...+l_n^p。

根据矩阵的不同，您可能需要计算特征值，然后进行求和。如果你的矩阵有低秩(或者可以用低秩矩阵很好地逼近)，你可以非常便宜地计算特征值(局部特征元具有复杂度O(n*k^2)，其中k是秩)。

编辑:您在注释中提到的是1600x1600，在这种情况下，找到所有的特征值应该是没有问题的。下面是许多C++代码中的一个，您可以使用它来实现这个http://code.google.com/p/redsvd/