# What's the fastest way to take powers of a square matrix?

So I know that you can use the Strassen Algorithm to multiply two matrices in seven operations, but what about multiplying two matrices that are exactly the same. Is there a faster way to go about doing that (ie. by reducing the number of multiplications per iteration to something less than 7) ?

-
Or maybe there is a faster way to at least square such a matrix, if the method does not extend to higher powers? –  I Love Cake Feb 7 '11 at 20:33
Are your matrices allowed to have complex entries, or only real? –  Jonas Meyer Feb 7 '11 at 20:37
The matrix has only real entries. –  I Love Cake Feb 7 '11 at 20:43

Consider $$M = \begin{pmatrix} 0 & A & 0 \\ 0 & 0 & B \\ 0 & 0 & 0 \end{pmatrix}.$$ We have $$M^2 = \begin{pmatrix} 0 & 0 & AB \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}.$$ So matrix squaring is not asymptotically better than regular product. Of course, in practice the constant factor difference is very significant.

Taking a power is best achieved by repeated squaring. The other method is diagonalizing, but I think usually eigenvalues are found via the power method rather than vice versa.

-
@Qiaochu Matrix multiplication is not always commutative... –  Yuval Filmus Feb 7 '11 at 20:48
ha. Right. Just kidding. –  Qiaochu Yuan Feb 7 '11 at 20:49
I don't follow how this shows that matrix squaring is not asymptotically better than the regular product? Can you explain that part a bit more. If say I were to have an algorithm that could square a matrix in some O() time, then would it necessarily be true that this bound is the same for the multiplication of two different matrices? –  I Love Cake Feb 7 '11 at 23:30
This argument show that if you can square $n\times n$ matrices in time $S(n)$, then you can multiply $n\times n$ matrices in time $M(n) = S(3n) + \Theta(n^3) = S(3n)$. If, for example, $S(n) = \Theta(n^\omega)$, then we also get $M(n) = \Theta(n^\omega)$; just a different constant. –  Yuval Filmus Feb 8 '11 at 1:50
You can also find this argument in CLRS (I think). –  Yuval Filmus Feb 8 '11 at 1:50

It really depends on the matrix. For instance if you have a diagonalizable matrix then you can decrease the amount of multiplications by diagonalizing so that

$$A^k=P^{-1}B^k P,$$

and since $B$ is a diagonal matrix it only takes $2$ multiplications to multiply the matrices. Somewhat similar things can be done with jordan normal form matrices. A general method consists of using binary exponentiation to reduce the number of matrix multiplications that need to be done from N to $\log(N)$. Technically speaking matrix multiplication can be done "faster" than Strassen as well, but this will only be the case for very large matrices, due to the large constant coefficient hidden in the Coppersmith–Winograd algorithm.

-