Course contentsShow
← Computer Science
Lesson 849 of 2,87220. Recursion Patterns and TechniquesFree lesson

Strassen's Matrix Multiplication

Multiplying matrices faster than O(n³) by reducing 8 recursive calls to 7 using clever algebra.

Strassen's Matrix Multiplication

You'll learn how a clever algebraic trick can multiply matrices faster than the straightforward approach.

The Standard Matrix Multiplication Problem

When you multiply two n×n matrices using the textbook method, you perform 8 multiplications for each 2×2 block if you divide the matrices into quadrants. Using divide-and-conquer recursively gives you O(n³) time—the same as the iterative triple-nested-loop approach.

Strassen's Brilliant Insight

In 1969, Volker Strassen discovered something remarkable: you can compute the product of two 2×2 matrices using only 7 multiplications instead of 8, at the cost of doing more additions (which are cheaper).

Here's the magic: instead of computing each quadrant of the result matrix directly, Strassen defined 7 intermediate products using strategic combinations of the input submatrices. These products are then combined with additions to produce the final result.

Why This Matters

When you apply this recursively to large matrices (dividing them into quadrants repeatedly), that reduction from 8 to 7 recursive calls compounds dramatically. The recurrence becomes:

T(n) = 7T(n/2) + O(n²)

By the Master Theorem, this gives approximately O(n^2.807) instead of O(n³)—a genuine improvement for large matrices!

The Tradeoff

The downside? More additions, more bookkeeping, and the algorithm is less numerically stable. For small matrices, the overhead isn't worth it. In practice, hybrid approaches switch to standard multiplication below a certain size threshold.

Key Takeaway: Strassen's algorithm shows that the "obvious" way isn't always optimal—creative algebra can reduce the number of expensive recursive calls, breaking through what seemed like a fundamental barrier.