我需要计算矩阵的 3 和 4 次方的轨迹，并且它需要尽可能快。
这里的矩阵是一个简单图的邻接矩阵，因此它是正方形的，对称的，它的元素总是 1 或 0，对角元素总是 0。
对于矩阵的 2 次幂的轨迹，优化是微不足道的：
我在维基百科上找到的另一个想法是总结 Hadamard 产品的所有元素，即逐项乘法，但我不知道如何将此方法扩展到 3 和 4 的幂。
请参阅http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Properties
也许我只是盲人，但我想不出一个简单的解决方案。
最后我需要一个 C++ 实现，但我认为这对这个问题并不重要。
提前感谢您的帮助。
迹是特征值的总和，矩阵幂的特征值就是该幂的特征值。
也就是说，如果 l_1,...,l_n 是矩阵的特征值，则 trace(M^p) = 1_1^p + l_2^p +...+l_n^p。
根据您的矩阵，您可能需要计算特征值然后求和。如果您的矩阵具有低秩（或者可以用低秩矩阵很好地近似），您可以非常便宜地计算特征值（部分特征分解的复杂度为 O(n*k^2)，其中 k 是秩）。
编辑：您在评论中提到它是 1600x1600 在这种情况下找到所有特征值应该没有问题。这是可用于此http://code.google.com/p/redsvd/的众多 C++ 代码之一
好的，我只是自己想出了这个。我不知道的重要一点是：
如果 A 是有向或无向图 G 的邻接矩阵，那么矩阵 An（即 A 的 n 个副本的矩阵乘积）有一个有趣的解释：第 i 行和第 j 列中的条目给出了（有向或无向）从顶点 i 到顶点 j 的长度为 n 的游走。例如，这意味着无向图 G 中三角形的数量正好是 A^3 除以 6 的迹。
（从http://en.wikipedia.org/wiki/Adjacency_matrix#Properties复制）
在处理稀疏图和使用邻接表而不是矩阵时，从节点 i 到 i 为所有 n 个节点检索给定长度的路径数基本上可以在 O(n) 中完成。
不过，感谢您的回答！