How do you compute the square of a Matrix in only 5 multiplications?

The Strassen Algorithm for computing $AB$ where $A$ and $B$ are two even matrices involves splitting the matrices into submatrices and then reducing the number of multiplications by $1$ from $8$ to $7$ through some magic. I'd like to reduce the number of multiplications from $7$ to $5$ in the case of squaring a matrix: $AA$. I understand that after the first step of the algorithm, when I do the recursive call, this doesn't actually work because I will no longer be squaring matrices, however, I'd like to prove that it is possible to do so.

Starting from the Strassen Algorithm, you have:

$M_1 = (A+C)(A+B)$

$M_2 = (B+D)(C+D)$

$M_3 = (A-D)(A+D)$

$M_4 = D(C-A)$

$M_5 = (A+B)D$

$M_6 = (C+D)A$

$M_7 = A(B-D)$

Where $A,B,C,D$ are the sub-matrices. In an attempt to look to combine some of these equations, it seems like $1$ and $5$ could be combined, and $2$ and $6$ as well. However, the order of the multiplications doesn't work, and even if it did, I wouldn't be able to get some of the other products.

Is there anything obvious that I'm missing? (Perhaps "obvious" isn't the right word)

• If you could I think it would be part of the algorithm
– qwr
Feb 5 '14 at 4:33
• The idea is that even if you could, it doesn't affect the algorithm run-time because your recurrence relation only satisfies T(n) = 5T(N/2) + O(N) for the first recurrence. However, once you go to the second recurrence, because you are computing the matrix multiplications M_1, M_2, etc, and you are no longer squaring matrices, the number of multiplications would go back up to the general case giving you T(N) = 7T(N/2)+O(N). I simply want to show that for the first step, you can use only 5 multiplications. Feb 5 '14 at 5:00