Why is matrix multiplication o n 3?

Matrix Multiplication: Why Does It Take So Long? (And Can We Make It Faster?)

Matrix multiplication. It’s one of those things that hums away in the background of so many technologies we use every day. Think graphics in video games, the simulations scientists run, or even how neural networks learn. But have you ever stopped to wonder why multiplying two matrices takes so much computational effort? Specifically, why is it usually O(n^3)? Let’s unpack that, shall we?

The “schoolbook” method – you know, the one you probably learned in math class – is the most straightforward way to multiply matrices. If you’ve got two n x n matrices, A and B, the result, C, is also n x n. Each element in C is found by taking the “dot product” of a row from A and a column from B. Easy peasy, right?

Well, not so fast. The formula looks like this: Cij = Σ (Aik * Bkj) for k = 1 to n. What that really means is you’re doing a whole lot of multiplying and adding. For every single element in the resulting matrix, you’re doing n multiplications and n-1 additions. When you add it all up, you end up with n * n * n operations. That’s where the O(n^3) complexity comes from. It’s a lot of work!

But here’s where things get interesting. For a long time, everyone just assumed that O(n^3) was as good as it could get. Then, in 1969, along came Volker Strassen, who basically said, “Hold my beer.” He came up with an algorithm that could do it in roughly O(n^2.8074) time. That was a big deal.

Strassen’s trick? Divide and conquer. He chopped the matrices into smaller submatrices and then cleverly rearranged the calculations to use only seven recursive multiplications instead of the usual eight. More additions and subtractions, sure, but fewer multiplications overall.

Now, I remember when I first learned about Strassen’s algorithm. I was so excited, thinking it would solve all my matrix multiplication problems! But here’s the thing: it’s not always faster in practice. All those extra additions and subtractions add overhead. For smaller matrices, the standard algorithm is often quicker. It’s only when you get to really large matrices (think n greater than 100 or so) that Strassen’s algorithm starts to shine.

And the story doesn’t end there. Strassen opened up a whole can of worms, and researchers have been trying to find even faster algorithms ever since.

We’ve seen some wild stuff, like the Coppersmith-Winograd algorithm and its descendants. As of this year, the fastest known algorithm clocks in at around O(n^2.371552). It’s mind-boggling!

The catch? These super-fast algorithms are often impractical. They’re what we call “galactic algorithms” – they’re only faster for matrices so huge you’d never encounter them in real life. The constant factors are just too enormous. Still, they’re important because they show us what’s theoretically possible.

So, what’s the ultimate goal? Well, the theoretical lower limit for matrix multiplication is O(n^2). That’s because you have to look at all the elements in the matrices at least once. Whether we can actually reach that limit is one of the big unsolved mysteries in computer science.

Even with all these fancy algorithms floating around, the good old standard algorithm and Strassen’s algorithm are still the workhorses of matrix multiplication. They’re simple, relatively efficient, and well-understood. But research is always pushing forward, looking for ways to squeeze out every last bit of performance.

And just recently, in May 2025, an AI system called AlphaEvolve made a surprising discovery. It found a way to multiply 4×4 complex-valued matrices using only 48 scalar multiplications, beating a 56-year-old record held by Strassen’s algorithm, which required 49 multiplications! It may seem like a small improvement, but it shows the potential of AI to discover new and more efficient algorithms.

In conclusion, matrix multiplication is a deceptively complex topic. While the standard algorithm gets the job done, there’s a whole universe of faster algorithms out there, each with its own trade-offs. The quest for the ultimate matrix multiplication algorithm continues, and who knows? Maybe someday we’ll crack that O(n^2) barrier. It’s an exciting field to watch!