# Strassen's matrix multiplication algorithm when $n$ is not a power of 2

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$$?

• I don't have my copy of CLR to hand, so I can't check: is this one of the exercises later in the chapter? If so, does that give any hints? Commented Oct 1, 2018 at 13:35
• Pad the matrices with zeros. Commented Oct 1, 2018 at 13:52
• In the first edition, this was exercise 31.2-2. Commented Oct 2, 2018 at 18:57

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).

• this would alter the complexity of the algorithm. Commented Oct 2, 2018 at 10:05
• Say for n=27 and n=32 we would have same asymptotic complexity. Commented Oct 2, 2018 at 10:06
• because we would actually be multiplying 32 X 32 matrix padded with zeros instead of 27 X 27 matrix. So can't the algorithm be modified keeping the complexity of the algorithm unaltered ? Commented Oct 2, 2018 at 10:09
• @Sc00by_d00, it doesn't affect the complexity of the algorithm, assuming it's in $P$, because the padding is by a bounded factor. Commented Oct 2, 2018 at 11:45
• The asymptotic complexity doesn’t depend on constant factors, which is all you lose here. Commented Oct 2, 2018 at 15:04