How Does Strassen’s Recursive Matrix Multiplication Work?

Strassen’s algorithm is a divide-and-conquer method for multiplying square matrices. Its key idea is to reduce the number of recursive block multiplications from eight to seven, at the cost of doing more additions and subtractions.

For sufficiently large matrices, that tradeoff can reduce the number of arithmetic operations. Here is the block formula, a worked example, and the complexity analysis.

Split each matrix into four blocks

Write two $n \times n$ matrices, with $n$ a power of 2 (or after padding to such a size), as

$$A = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix}, \qquad B = \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix}.$$

Each block is an $n/2 \times n/2$ matrix. Ordinary block multiplication uses eight block multiplications to calculate the four blocks of $C=AB$. Strassen’s method replaces those eight products with seven:

$$\begin{aligned} M_1 &= (A_{11}+A_{22})(B_{11}+B_{22}),\\ M_2 &= (A_{21}+A_{22})B_{11},\\ M_3 &= A_{11}(B_{12}-B_{22}),\\ M_4 &= A_{22}(B_{21}-B_{11}),\\ M_5 &= (A_{11}+A_{12})B_{22},\\ M_6 &= (A_{21}-A_{11})(B_{11}+B_{12}),\\ M_7 &= (A_{12}-A_{22})(B_{21}+B_{22}). \end{aligned}$$

The products are matrix products of half-size blocks. They can be calculated by applying Strassen’s method recursively, until the blocks are small enough for ordinary multiplication.

Combine the seven products

Construct the four blocks of the result from the $M_i$ values:

$$\begin{aligned} C_{11} &= M_1+M_4-M_5+M_7,\\ C_{12} &= M_3+M_5,\\ C_{21} &= M_2+M_4,\\ C_{22} &= M_1-M_2+M_3+M_6. \end{aligned}$$

These identities produce the same result as ordinary matrix multiplication. Matrix multiplication is not generally commutative, so keep the factor order in each $M_i$ exactly as written.

Worked example

Take

$$A=\begin{pmatrix}1&2\\3&4\end{pmatrix}, \qquad B=\begin{pmatrix}5&6\\7&8\end{pmatrix}.$$

For $2 \times 2$ matrices, each block is a single number. Substituting the entries into the seven formulas gives

$$\begin{aligned} M_1&=(1+4)(5+8)=65, & M_2&=(3+4)5=35,\\ M_3&=1(6-8)=-2, & M_4&=4(7-5)=8,\\ M_5&=(1+2)8=24, & M_6&=(3-1)(5+6)=22,\\ M_7&=(2-4)(7+8)=-30. \end{aligned}$$

Now combine them:

$$\begin{aligned} C_{11}&=65+8-24-30=19, & C_{12}&=-2+24=22,\\ C_{21}&=35+8=43, & C_{22}&=65-35-2+22=50. \end{aligned}$$

Thus

$$AB=\begin{pmatrix}19&22\\43&50\end{pmatrix}.$$

As a check, the top-left entry from ordinary multiplication is $1\cdot5+2\cdot7=19$, and the other entries agree as well.

Why the algorithm is faster asymptotically

At each recursive level, Strassen makes seven multiplications on matrices of size $n/2$. The additions and subtractions of blocks take $O(n^2)$ operations, so the recurrence, for power-of-two sizes, is

$$T(n)=7T(n/2)+O(n^2).$$

By the Master Theorem,

$$T(n)=O(n^{\log_2 7})\approx O(n^{2.807}).$$

This grows more slowly than the $O(n^3)$ arithmetic complexity of the standard algorithm. The bound describes asymptotic operation counts, not a guarantee that Strassen is faster for every matrix size or computer. For small blocks, the extra additions and implementation overhead can outweigh the saved multiplications, so practical implementations switch to ordinary multiplication below a chosen cutoff.

Implementation details and common mistakes

• Stopping condition: Use ordinary matrix multiplication at a base-case size rather than recursing indefinitely. The best cutoff depends on the implementation and hardware.
• Uneven dimensions: The simplest recursive version assumes a power-of-two matrix size. For arbitrary sizes, pad matrices with zero rows and columns to a power-of-two size, then remove the padding from the result, or use a variant that handles uneven blocks.
• More additions: Strassen reduces multiplications but performs extra additions and subtractions. Its practical speed depends on matrix size, memory use, data type, and implementation.
• Floating-point accuracy: With floating-point entries, different operation orders can produce different rounding errors. Strassen can be less numerically stable than conventional multiplication in some settings, so consider the required accuracy and use an appropriate implementation.
• Wrong signs or factor order: A sign error in one combination formula changes the result. Also, do not reverse factors in a block product: in general, $XY \ne YX$.

For integer, real, or complex matrices, the same block identities apply; the entries must support the additions, subtractions, and multiplications used by the algorithm.