伴随矩阵的复杂性

我知道这是一个比编程问题更复杂的理论问题，希望我没有写错在这里写作，如果是错误的地方，我会道歉，但我希望你们中的某个人有答案。作为一个复杂性理论问题，它甚至与程序设计相关。伴随矩阵的复杂性

我正在研究线性循环序列，并且我读到为了获得它弹出的序列的第n个值，您需要获得伴随矩阵的某些功能，我想知道是否有已知的算法来获得这种矩阵的权力的快捷方式..

我不能给编码的例子，但我会尽力给你一些更多的解释：

齐次线性周期性第k个序列order：
s（n + k）= a（k-1）s（n + k-1）+ a（k-2）s（n + k-2）+ ... + a（0）
对于n = 0,1，...，其中s（i）是序列的第i个值e和a（i）是代数场中的系数。

A为上述序列的友矩阵，如果它是：
（0 0 0 0 ... 0（0））
（1 0 0 0 ... 0（1））
（0 1 0 0 ... 0 a（2））
（.. .. ..）
（0 0 0 0 ... 1 a（k -1））
此外理论认为对于该序列的状态矢量，我们有：
S（N）= S（0）甲^ N对于n = 0,1，..
就是这样，感谢帮助。

来源

2009-04-07 luiss

快速查找矩阵幂的通常策略是diagonalise它（执行特征向量分解）：

甲= P ^-1 d。P个

其中d是对角矩阵。然后，您可以通过计算

一个 ^ň = P ^-1 d ^ň P

其中d ^ñ 是快速计算，因为它是一个对角矩阵，所以养的n次幂你只需分别掌握每个元素的权力。

然而，并非所有的矩阵都是可对角化的 - 我不知道你的伴随矩阵是否会成立。无论如何，你可能会发现 this Wikipedia article 有帮助。

来源

2009-04-07 14:48:38

它并不总是对角化，只有当特征polynoials的根源是不同的，反正没关系，这是很好的，但我想知道是否有某种方式利用矩阵的结构，TY – luiss 2009-04-07 15:07:34

可以使用 O(log n) 矩阵产品计算矩阵 M 的 n 次方：

如果 n=0 ，返回 I
如果 n 是偶数，计算 N=M ^n/2 并返回 N*N
如果 n 是奇数，则计算 N=M ^n-1 并返回 M*N

来源

2009-04-26 12:27:02

对不起，但我无法弄清楚如何使它在O（log n）中，我认为每个矩阵乘法仍然是O（n^2），其中n是行数（supposin一个方阵），不是吗？ – luiss 2009-04-26 15:24:53

伴随矩阵的复杂性

回答

相关问题