The Matrix Multiplication Exponent ω

Open any linear algebra textbook and you'll find the rule for multiplying two n × n matrices: take every row of the first, dot it with every column of the second, and record each of the $n^{2}$ results. Each dot product needs n multiplications, so the total bill is $n^{3}$ arithmetic operations.

For small matrices that's fine. But multiply two 10,000 × 10,000 matrices — routine in machine learning or physics simulations — and $n^{3}$ becomes a trillion operations. Speed matters enormously.

In 1969, Volker Strassen discovered something shocking: you don't need all those multiplications. By rearranging the computation cleverly, he shaved the exponent from 3 to roughly 2.807. The gap looks small, but it means his algorithm is about four times faster on those 10,000 × 10,000 matrices.

That discovery launched a race. Researchers have since pushed the exponent down to around 2.371 — and the conjecture is that the true minimum is exactly 2, meaning matrix multiplication might ultimately cost no more than reading the input. But despite decades of effort, $\omega$ remains unknown, making it one of the central open questions in theoretical computer science.

The chart below plots every major improvement in $\omega$ since 1969. Select a matrix size n to see how many operations each algorithm needs — then drag the slider to explore the effect of a hypothetical exponent between 2 and 3.

<div class="demo-wrap">
  <div class="controls">
    <label for="nSlider">{{label_matrix_size}} <strong id="nVal">n = 1000</strong></label>
    <input id="nSlider" type="range" min="2" max="5" step="1" value="3">
    <span class="hint-row">
      <span id="nLabel"></span>
    </span>
  </div>
  <div class="chart-area">
    <canvas id="chart" width="560" height="280"></canvas>
  </div>
  <div class="omega-row">
    <label for="omegaSlider">{{label_hyp_omega}} <strong id="omegaVal">2.37</strong></label>
    <input id="omegaSlider" type="range" min="2.00" max="3.00" step="0.01" value="2.37">
  </div>
  <div id="opTable" class="op-table"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.demo-wrap { padding: 0.6rem 0.5rem; }
.controls { margin-bottom: 0.6rem; }
label { font-size: 0.9rem; display: block; margin-bottom: 0.3rem; }
input[type=range] { width: 100%; accent-color: #1d3557; cursor: pointer; }
.hint-row { font-size: 0.78rem; color: #555; display: block; margin-top: 0.2rem; }
.chart-area { background: #f4f7fa; border-radius: 10px; padding: 0.5rem;
              margin-bottom: 0.6rem; overflow: hidden; }
canvas { display: block; width: 100%; height: auto; }
.omega-row { margin-bottom: 0.7rem; }
.op-table { font-size: 0.82rem; border-collapse: collapse; width: 100%; display: table; }
.op-table th { background: #1d3557; color: #fff; padding: 4px 8px; text-align: left; }
.op-table td { padding: 3px 8px; border-bottom: 1px solid #e0e6ec; }
.op-table tr:nth-child(even) td { background: #f0f4f8; }
.op-table .highlight td { background: #fff3cd; font-weight: 600; }

// Code not found

Notice how even a small drop in $\omega$ makes a dramatic difference at large n. A drop from 3 to 2.37 cuts the operation count by a factor of thousands for n = 10,000. If $\omega$ were exactly 2, matrices of any size would multiply in time proportional to reading them — a revolution yet to come.

The exponent $\omega$ is defined as the smallest real number such that two $n \times n$ matrices can be multiplied in time $O(n^{\omega+\varepsilon})$ for every $\varepsilon > 0$. Its status is open: the true value is unknown.

• Lower bound (trivial): $\omega \ge 2$, because you must at least read the $n^2$ entries of the output.
• Upper bound (schoolbook): $\omega \le 3$, obvious from the definition.
• Strassen (1969): $\omega \le \log_2 7 \approx$ 2.807. He multiplied $2 \times 2$ matrices with 7 multiplications instead of 8, then applied this recursively.
• Pan (1980) and others: a burst of improvements through the 1980s using sophisticated tensor methods.
• Coppersmith–Winograd (1987): $\omega \le$ 2.376, the breakthrough that set the template for 25 years. Their laser method analyzes tensor rank in a structured way.
• Stothers (2010), Vassilevska Williams (2012), Le Gall (2014): incremental improvements bringing the bound below 2.373.
• Duan, Wu, Zhou (2023): $\omega <$ 2.3719, the current record.

The $\omega = 2$ conjecture says the lower and upper bounds will eventually meet at 2. It is widely believed but entirely unproven. Every improvement since 1987 has been a small numerical refinement of the Coppersmith–Winograd framework, and it is unclear whether a fundamentally different approach is needed to reach 2.

Proving $\omega = 2$ would be a landmark result — or proving $\omega > 2$ would be equally surprising, establishing a genuine gap between reading a matrix and multiplying two of them. For context, this open question sits in the same landscape of unknowns as P vs NP, though it is a distinct (and possibly easier) problem.

Matrix multiplication is not an isolated curiosity — it is the engine behind a surprising fraction of algorithms:

• Deep learning: every forward and backward pass through a neural network is dominated by matrix multiplications. Faster matrix multiply directly speeds up training. Hardware like GPUs and TPUs are essentially optimized matrix-multiply engines.
• Graph algorithms: computing shortest paths, transitive closure, and detecting triangles in a graph all reduce to matrix multiplication. A better $\omega$ would automatically improve these algorithms.
• Linear programming: solving large linear programs and least-squares problems requires matrix operations. Faster matrix multiply feeds into faster interior-point methods.
• Polynomial multiplication and FFT: via algebraic connections, faster matrix multiplication implies faster algorithms for related algebraic problems.
• Scientific simulation: fluid dynamics, quantum chemistry, and finite-element analysis all build large matrix systems. Cutting $\omega$ by even 0.1 can halve runtimes on supercomputers.

The gap between schoolbook $O(n^{3})$ and the conjectured $O(n^{2})$ is not yet closed, but even the improvements so far have been absorbed into the standard toolkit. Any further progress on $\omega$ would propagate instantly across dozens of fields — which is why it remains one of the most actively studied open problems in algorithms. See also fast multiplication for related ideas on multiplying large integers.

Multiplying two matrices is one of the most basic operations in computing, yet after 60 years of research we still do not know the optimal algorithm. Strassen's 1969 insight broke the $n^{3}$ barrier; decades of refinement have pushed the exponent to 2.3719; the conjecture is that 2 is the true answer — but the proof, if it exists, remains out of reach.

This is not a failure of imagination. It reflects how difficult it can be to pin down the exact cost of even the most fundamental computations. The race toward $\omega = 2$ continues, and each small improvement brings practical benefits to machine learning, simulation, and graph theory.

Until $\omega$ is resolved, every matrix computation carries a small asterisk: we are probably paying more than necessary, but we do not know how much. That open question, hiding in plain sight inside the most routine of linear algebra operations, is one of the great unsolved problems in the theory of algorithms.