Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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) ?

share|improve this question
    
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
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
@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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.