计算矩阵的迹的k次幂

Question

5

我需要计算一个矩阵的3次方和4次方的迹，并且需要尽可能快地完成。

这里的矩阵是一个简单图的邻接矩阵，因此它是方阵，对称的，其条目始终为1或0，对角线元素始终为0。

对于矩阵的平方迹，优化很简单：

- 我们只需要对角线条目（i，i）来计算迹，跳过所有其他条目 - 由于矩阵是对称的，这些条目只是第i行的条目平方和 - 由于条目只是1或0，可以跳过平方运算

我在维基百科上发现另一个想法是将所有哈达玛积（即逐个相乘）的元素相加，但我不知道如何将此方法扩展到3次方和4次方。

请参见http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Properties 也许我只是太盲目了，无法想出简单的解决方案。

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

提前感谢您的任何帮助。

- Gigo

矩阵的大小是多少？ - user85109

3

仔细阅读后，我感到困惑。你说矩阵是对角线矩阵，对角线元素为零。这是什么意思？一个对角线元素为零的对角线矩阵的痕迹很简单：零。任何零矩阵的幂也都有零痕迹。你是不是指矩阵是对称的，而不是对角线矩阵？ - user85109

由于这是一个邻接矩阵，其大小取决于图的大小。我使用过的最大尺寸为1600x1600。 - Gigo

3

我认为这应该属于http://scicomp.stackexchange.com。 - John Alexiou

2个回答

1

好的，我刚刚自己解决了这个问题。

我不知道的重要事情是：

如果A是有向或无向图G的邻接矩阵，则矩阵An（即A的n个副本的矩阵乘积）具有有趣的解释：行i和列j中的条目给出了从顶点i到顶点j的长度为n的（有向或无向）路径数。例如，这意味着无向图G中三角形的数量正好是A^3的迹除以6。

当处理稀疏图并使用邻接列表而不是矩阵时，检索从节点i到i的给定长度的所有n个节点的路径数可以在O（n）内完成。

尽管如此，感谢您的回答！

- Gigo

你有一个稀疏图，因此你有一个稀疏邻接矩阵。在这种情况下，矩阵乘法非常快。你确定这个路径枚举的想法比仅计算A^3更快吗？ - dranxo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dranxo · Accepted Answer

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

也就是说，如果 l_1，...，l_n 是您的矩阵的特征值，则 trace(M^p) = 1_1^p + l_2^p +...+l_n^p。

根据您的矩阵，您可能需要计算特征值然后求和。如果您的矩阵秩低（或可以用低秩矩阵很好地近似），则可以非常便宜地计算特征值（部分特征分解的复杂度为O(n*k^2)，其中k是秩）。

编辑：您在评论中提到它是1600x1600，那么找到所有特征值应该没有问题。这是您可以使用的许多C++代码之一，用于此http://code.google.com/p/redsvd/