Strassen's matrix multiplication algorithm when $n$ is not a power of 2
The solution is to pad the matrices with zeroes, using the block matrix identity
$$
\begin{bmatrix}
A &amp; 0 \\
0 &amp; 0
\end{bmatrix}
\begin{bmatrix}
B &amp; 0 \\
0 &amp; 0
\end{bmatrix}
=
\begin{bmatrix}
AB &amp; 0 \\
0 &amp; 0
\end{bmatrix}
.
$$

Here $A,B$ are $n\times n$ matrices, and the big matrices are $N\times N$ for some $N &gt; 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 &lt; 2n$, so this doesn't affect the asymptotic complexity.
Pad the matrices recursively. Whenever a recursive call gets $m \times m$ matrices with $m &gt; 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).