What Is the Matrix Multiplication Exponent?

Multiplying two n×n matrices the way it’s taught in school takes roughly n³ arithmetic operations. It turns out that’s not the fastest possible method — and how much faster it can go is still an open question. The matrix multiplication exponent, written ω, is defined as the smallest number such that n×n matrices can be multiplied using O(n^ω) operations. Trivially ω ≥ 2 — you at least have to read every entry of both matrices — but nobody knows whether that lower bound is actually achievable.

A sequence of surprising improvements

In 1969, Volker Strassen showed ω ≤ log₂7 ≈ 2.807 with a recursive trick that beats the schoolbook method by avoiding one multiplication per recursive step. Over the following decades, a series of increasingly intricate results — based on a technique called the laser method, applied to combinatorial objects that have nothing obviously to do with matrices — pushed the bound steadily down: Coppersmith and Winograd reached 2.376 in 1990, and refinements since have inched it lower still.

Where the record stands

The current best proven upper bound is ω < 2.371339, from a 2024 paper by Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. Each improvement in this line of work has gotten smaller — the gap between successive records is now measured in the fourth or fifth decimal place — while the lower bound has stayed put at exactly 2 since the question was first posed.

Why the gap won’t obviously close

Many researchers suspect ω = 2 is the true answer — that matrix multiplication can, in principle, be done almost as fast as just reading the input. But every known technique for proving upper bounds has hit a wall, formalized by results showing the laser method itself cannot get below a certain threshold without new ideas. Closing the gap between 2 and 2.371339 would need a genuinely different approach, not just a sharper version of the current one.

Why it’s here

Matrix multiplication underlies enough of computing — graphics, machine learning, scientific simulation — that even asymptotic improvements attract serious attention, even though the fastest known algorithms are not used in practice due to large constant factors. The Registry tracks the proven bound as a two-sided frontier: 2 as the floor nobody has beaten, 2.371339 as the ceiling nobody has broken through.

Primary source

Williams, Xu, Xu & Zhou, “New Bounds for Matrix Multiplication: from Alpha to Omega” ↗