The above image, describing Strassen's matrix multiplication algorithm, is from the book Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. The algorithm multiplies two square matrices of order $n$, where $n$ is a power of $2$, i.e., $n=2,4,8,16,32,\dots$ and so on.
Can this algorithm be modified so that we can multiply two square matrices of order $n$, for all $n$?
The solution is to pad the matrices with zeroes, using the block matrix identity $$ \begin{bmatrix} A & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} B & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} AB & 0 \\ 0 & 0 \end{bmatrix} . $$
Here $A,B$ are $n\times n$ matrices, and the big matrices are $N\times N$ for some $N > n$. In other words, we add $N-n$ rows and $N-n$ columns of zeroes.
You can do this in two ways:
Pad the original $n \times n$ matrices to $N \times N$ matrices, where $N$ is the closest power of 2. Note that $N < 2n$, so this doesn't affect the asymptotic complexity.
Pad the matrices recursively. Whenever a recursive call gets $m \times m$ matrices with $m > 1$ odd, we pad them to $(m+1) \times (m+1)$ matrices by adding a single row and a single column of zeroes. This also doesn't affect the asymptotic complexity.
A third option is to make use of, say, a 3x3 matrix multiplication algorithm if the dimension is odd but divisible by 3. Laderman found such an algorithm which uses 23 multiplications (instead of the trivial 27).
