Multiplying two matrices using Strassen vs squaring identical matrices

Question

I have an assignment question such as follows: when using the Strassen algorithm we have 7 subproblems usually, and I suppose this applies to any two $n*n$ matrices and the run time is $O(n^{log_27})$. However when I have an example of two identical $2*2$ matrices and I have to multiply them, I can just square them and it will give me 5 subproblems. i.e.:

| A11 A12 | multiplied by | A11 A12 | will give: | A11A11 + A12A21   A11A12 + A12A22 |
| A21 A22 |               | A21 A22 |            | A21A11 + A22A21   A21A12 + A22A22 |

                which is simply          | A11^2 + A12A21   A12(A11+A22)   |
                                         | A21(A11+A22)     A12A21 + A22^2 |

where the multiplications are in A11^2, A22^2, A21*(term), A12*(term), and A12*A21

Why can't I assume that the runtime will be $O(n^{log_25})$? Is it because it only applies to $2*2$ matrices and not n*n in general? Or would I have additional subproblems asides from the 5 subproblems for multiplication?

Answer 1

Using the Strassen algorithm for matrix multiplication, we define seven new matrices, $M_1, \dots, M_7$, where each $M_k$ does one multiplication. This is why the run-time will be $O(n^{\log_2 7})$ all the time using Strassen's algorithm.

However, if we know our matrices are identical, then we can instead define the matrices $N_1,\dots, N_5$, where $$N_1 = A_{11}^2 \\ N_2 = A_{22}^2 \\ N_3 = A_{21}(A_{11}+A_{22})\\ N_4 = A_{12}(A_{11}+A_{22})\\ N_5 = A_{12}A_{21}.\\$$ Then for $AA = C$, we can set $C_{ij}$ to be additions/subtractions of the above $N_k$ matrices. Now our running time will be $O(n^{\log_2 5})$.

---

So, we cannot assume that our running time will be $O(n^{\log_2 5})$ using Strassen's original algorithm, because it won't be. We'd still have to do seven multiplications, even though they are not necessary, as be seen by your reasoning. With our modified and simplified Strassen algorithm for identical matrices though, we do obtain $O(n^{\log_2 5})$ time.

Also, the algorithm does not only apply to $2\times 2$ matrices. The algorithm is a divide-and-conquer algorithm. What we do is divide an $n\times n$ matrix into $4$ blocks, and recurse $n$ times until the "submatrices" are either $1\times 1$, or $2\times 2$.