I have been reading Introduction to Algorithms by Cormen. Before explaining Strassen algorithm the book says this:

Strassen’s algorithm is not at all obvious. (This might be the biggest understatement in this book.)

The book just states the algorithm but don't explain why it works. So if we take the case of multiplication of two $2 \times 2$ matrices, it reduces the number of multiplications from $8$ to $7$ thereby reducing the complexity from $n^{3}$ to $n^{\lg 7}$ which is roughly $n^{2.8}$.

My question is why $7$ and say not $5$ or even lesser number? I mean they could have made the recursion tree even less "bushier".

  • 11
    $\begingroup$ You are more than welcome to try and come up with an algorithm that only needs $O(n^{\log_25})$ multiplications. $\endgroup$ Aug 3, 2012 at 17:09
  • 5
    $\begingroup$ ...and if you manage to do so, that'd certainly be journal-worthy. $\endgroup$ Aug 3, 2012 at 17:14
  • $\begingroup$ $O(n^{2.3727})$ seems to be the best known solution at the moment (google.com/…). These algorithms, opposed to Strassen, only pay of for very, very large matrices far beyond practical use. $\endgroup$
    – B0rk4
    Aug 3, 2012 at 17:33

1 Answer 1


Allow me to shamelessly copy an answer of mine to this question first.

The idea behind Strassen multiplication is the same as the idea behind Karatsuba multiplication.

In this, if we have two numbers and a base $B$ (maybe $10^6$, say), and the numbers are written $a = x_0B + x_1$, $b = y_0B + y_1$, and we want to calculate $ab$, then naively we might say that it's

$ab = x_0 y_0 B^2 + (x_0 y_1 + x_1 y_0)B + x_1 y_1 \qquad$ (requiring 4 multiplications)

But we can be wittier, as $x_0y_1 + x_1y_0 = (x_0 + x_1)(y_0 + y_1) - x_0y_0 - x_1y_1 $

So we can calculate $ab$ by knowing $x_0y_0, x_1y_1$ and $(x_0 + x_1)(y_0 + y_1)$, which only uses 3 multiplications. This is just a slick idea, akin to the many other slick arithmetic tricks out there that might be found by inspection, and it became popular in the 1960s. (There's a good story behind it - Karatsuba responded to a challenge of Kolmogorov, ultimately culminating with Kolmogorov writing a paper in Karatsuba's name).

For matrices, a direct port of Karatsuba doesn't quite work. But it's easy to verify that Strassen is true (just write it out). But it's very unclear how Strassen came across them. But it should be mentioned that Strassen was working on many numerical-methods style techniques to improve matrix calculations. It should also be mentioned that Strassen has an improved algorithm, better than this technique, using fast fourier transforms as well.

One might ask: well, we can do it with 7 multiplications. Can we do it with 6? Strassen multiplication has been around since 1969, so surely it's known? This was an open problem until just a few years ago, when Landsberg showed that 7 is optimal. It's nontrivial and a bit far afield for me, but his (corrected after it was published) article can be found on the arXiv.

One might also wonder about $3 \times 3$ matrices. How few multiplications are necessary? Naively, it takes 27 multiplications. But it can be done in 23. (See Julian D. Laderman, A noncommutative algorithm for multiplying 3×3 matrices using 23 muliplications, Bull. Amer. Math. Soc. 82 (1976) 126–128, MR0395320 (52 #16117).) Is that optimal? That's unknown - all that's known is that it takes at least 19. (But if you're just interested in computational savings, even 19 gives less savings when iterated than the $2 \times 2$ case).

So in short, $7$ is optimal. It's not obvious that it's optimal. It was a very clever idea, even, to find the $7$.

  • 4
    $\begingroup$ As commented in the article, it was known that 7 "essential multiplications" are necessary already in 1971 (two years after Strassen's original 1969 paper), and a simple proof appears in Algebraic Complexity Theory. Landsberg proved that the border rank is 7. $\endgroup$ Aug 3, 2012 at 20:44
  • 1
    $\begingroup$ I don't understand the last part claiming that 19 multiplications for 3x3 gives less savings than 7 for 2x2. $\log_3{19} \approx 2.68 < \log_2{7} \approx 2.81$. If we were able to multiply two 3x3 matrices using $19$ multiplications, this would be a major breakthrough. $\endgroup$
    – user66307
    Nov 18, 2014 at 21:25
  • $\begingroup$ As a fun add-on, while the $3\times3$ case is worse than the $2\times2$ case, it is known that the $4\times4$ is ever so slightly better in fact, using precisely what you mentioned at the start. $\endgroup$ Aug 30, 2019 at 23:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .