Companion matrix complexity

Question

Hi, 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.

Answer 1

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

Aⁿ = P^-1 Dⁿ P

where Dⁿ 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.

Answer 2

You can compute the nth power of a matrix M using O(log n) matrix products:

• if n=0, return I
• if n is even, compute N=Mn/2 and return N*N
• if n is odd, compute N=Mn-1 and return M*N