伴随矩阵复杂度
我知道这更像是一个复杂性理论问题，而不是一个编程问题，希望我在这里写的时候没有做错事，如果写错了，请向我道歉，但我希望你们中有人能找到答案。 它甚至在某种程度上通过复杂性理论问题与编程相关。
我正在研究线性循环序列，并且我读到为了获得序列的第 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,..
就是这样，谢谢你的帮助。
I know this is more a complexity theory question than a programming question, hope I'm not doing the wrong thing writing here, apologize me if it's the wrong place but I hope someone of you have the answer. And it's even someway programmin related by being a complexity theory qestion.
I'm studying Linear Recurring Sequences, and I read that in order to obtain the n-th value of the sequence it popped out that you need to get some power of a companion matrix, I was wondering if there's a known algorithm to get powers of this kind of matrix in a fast way..
I can't give coding example, but I shall try to get you some more explanation:
Homogeneous Linear Recurring Sequence of k-th order:
s(n+k)=a(k-1)s(n+k-1)+a(k-2)s(n+k-2)+...+a(0)
for n=0,1,.. where s(i) is the i-th value of the sequence, and the a(i) are coefficients in an Algebraic Field.
A is the companion matrix of the above sequence if it's:
( 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) )
Moreover Theory states that for the state vectors of the sequence we have:
s(n) = s(0)A^n for n=0,1,..
That's it, thanks for the help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
快速求矩阵幂的常用策略是将其对角化（执行特征向量分解）：
A = P-1 DP
，其中 D 是对角矩阵。 计算 A 的 n 次方，
然后，您可以通过计算An = P-1 Dn P
其中 Dn 计算速度很快，因为它是一个对角矩阵，因此您只需分别获取每个元素的幂即可。
然而，并非所有矩阵都是可对角化的——我不知道你的伴生矩阵是否可以。 无论如何，您可能会发现这篇维基百科文章很有帮助。
The usual strategy for finding powers of a matrix quickly is to diagonalise it (perform eigenvector decomposition):
A = P-1 D P
where D is a diagonal matrix. You can then raise A to the power n by calculating
An = P-1 Dn P
where Dn is fast to compute because it's a diagonal matrix, so you just take the powers of each element separately.
However not all matrices are diagonalisable -- I don't know if your companion matrix will be or not. You might find this Wikipedia article helpful in any case.
您可以使用
O(log n)矩阵乘积计算矩阵M的n次方：n=0code>，n为偶数，则返回I，计算N=Mn/2并返回N*Nn为奇数，则计算N=Mn-1并返回M*NYou can compute the
nth power of a matrixMusingO(log n)matrix products:n=0, returnInis even, computeN=Mn/2and returnN*Nnis odd, computeN=Mn-1and returnM*N