matrix - 伴随矩阵复杂度

Question

我知道这更像是一个复杂性理论问题而不是一个编程问题，希望我在这里写的东西没有做错，如果它是错误的地方，请向我道歉，但我希望你们中的某个人有答案。它甚至在某种程度上与作为复杂性理论问题的程序相关。

我正在研究线性重复序列，我读到它是为了获得它弹出的序列的第 n 个值，你需要获得伴随矩阵的一些幂，我想知道是否有一个已知的算法来获得幂这种矩阵的快速方式..

我无法给出编码示例，但我会尽力为您提供更多解释:

第 k 阶齐次线性循环序列:
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 个值，而 a(i) 是代数域中的系数。

A 是上述序列的伴随矩阵，如果它是:
( 0 0 0 0 ... 0 a(0) )
( 1 0 0 0 ... 0 a(1) )
( 0 1 0 0 ... 0 a(2) )
(………………………………)
( 0 0 0 0 ... 1 a(k-1) )
此外，理论指出，对于序列的状态向量，我们有:
s(n) = s(0)A^n 对于 n=0,1,..
就是这样，谢谢你的帮助。

Answer 1

快速找到矩阵的幂的常用策略是对其进行对角化(执行特征向量分解):

A = P-1 D P

其中 D 是对角矩阵。然后，您可以通过计算将 A 提高到 n 次方

An = P-1 Dn P

其中 Dn 计算速度很快，因为它是一个对角矩阵，因此您只需分别计算每个元素的幂。

然而，并非所有矩阵都是可对角化的——我不知道你的伴侣矩阵是否可以。您可能会发现 this Wikipedia article在任何情况下都有帮助。