Can someone demonstrate the multiplication of two $4\times 4$ matrices using Strassen's algorithm? I don't understand when to stop partitioning the matrices.
We first partition the two $4\times 4$ matrices into four $2\times 2$ submatrices. Is that where we stop? Or do we have to apply the same procedure recursively to the submatrices as well?
Thanks!
In the general case we would recursively divide each $n\times n$ matrix into four $\lceil n/2 \rceil \times \lceil n/2 \rceil$ matrices, adjoining a extra row and column of zeros if $n$ is odd to make the sizes of submatrices whole numbers.
The point here is that Strassen's formulas for multiplying a pair of $2\times 2$ matrices does not assume commutativity of the multiplication on the underlying entries (though it does assume multiplication distributes over addition and the usual properties of addition). It is therefore valid even when the "entries" of the $2\times 2$ matrices are themselves block submatrices.
The simplest case to illustrate this is multiplication of two $4\times 4$ matrices:
$$ \begin{pmatrix} A & B \\ C & D \end{pmatrix} \begin{pmatrix} E & F \\ G & H \end{pmatrix} $$
where $A,B,C,D,E,F,G,H$ are each $2\times 2$ submatrices.
Strassen's algorithm can then be applied recursively. At the top level we want to form these seven products of $2\times 2$ matrices:
$$ \begin{align*} M_1 &= (A+D)(E+H) \\ M_2 &= (C+D)E \\ M_3 &= A(F-H) \\ M_4 &= D(G-E) \\ M_5 &= (A+B)H \\ M_6 &= (C-A)(E+F) \\ M_7 &= (B-D)(G+H) \end{align*} $$
From these the top-level product can be expressed:
$$ \begin{pmatrix} M_1 + M_4 - M_5 + M_7 & M_3 + M_5 \\ M_2 + M_4 & M_1 - M_2 + M_3 + M_6 \end{pmatrix} $$
The interested Reader should verify for themselves that when $A$ through $H$ are scalars, the result agrees with the usual row and column operations. The only thing one needs for the general proof is careful checking that no multiplication of the individual entries is assumed to commute when verifying that agreement.
For simplicity let's check just that the upper right corner gives $AF+BH$:
$$ \begin{align*} M_3 + M_5 &= A(F-H) + (A+B)H \\ &= (AF - AH) + (AH + BH) \\ &= AF + BH \end{align*} $$
It follows that the formulas are valid in particular when $A$ through $H$ are the $2\times 2$ matrices defined above.