Introduction

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 n2n^{2} results. Each dot product needs n multiplications, so the total bill is n3n^{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 n3n^{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.

Try It: The ω Timeline

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">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">Hypothetical ω: <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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Timeline of major ω upper-bound improvements:
const MILESTONES = [
  { year: 1969, omega: Math.log2(7),        label: 'Strassen' },
  { year: 1978, omega: 2.796,               label: 'Pan' },
  { year: 1979, omega: 2.780,               label: 'Bini et al.' },
  { year: 1981, omega: 2.522,               label: 'Schönhage' },
  { year: 1982, omega: 2.496,               label: 'Pan' },
  { year: 1986, omega: 2.479,               label: 'Romani' },
  { year: 1987, omega: 2.376,               label: 'Coppersmith-Winograd' },
  { year: 2010, omega: 2.374,               label: 'Stothers' },
  { year: 2012, omega: 2.3729,              label: 'Williams' },
  { year: 2014, omega: 2.3728,              label: 'Le Gall' },
  { year: 2023, omega: 2.3719,              label: 'Duan-Wu-Zhou' },
];
const SCHOOLBOOK = { year: 1900, omega: 3.0, label: 'Schoolbook (n³)' };

const N_SIZES = [100, 1000, 5000, 10000, 100000];
const N_LABELS = ['100', '1 000', '5 000', '10 000', '100 000'];

const nSlider = document.getElementById('nSlider');
const nVal = document.getElementById('nVal');
const nLabel = document.getElementById('nLabel');
const omegaSlider = document.getElementById('omegaSlider');
const omegaVal = document.getElementById('omegaVal');
const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');

function fmtOps(x) {
  if (x >= 1e15) return fmt('%v% quadrillion', { v: (x / 1e15).toFixed(2) });
  if (x >= 1e12) return fmt('%v% trillion', { v: (x / 1e12).toFixed(2) });
  if (x >= 1e9)  return fmt('%v% billion', { v: (x / 1e9).toFixed(2) });
  if (x >= 1e6)  return fmt('%v% million', { v: (x / 1e6).toFixed(2) });
  return x.toFixed(0);
}

function ops(n, omega) { return Math.pow(n, omega); }

function drawChart() {
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  const padL = 60, padR = 30, padT = 20, padB = 40;
  const chartW = W - padL - padR;
  const chartH = H - padT - padB;

  const minYear = 1965, maxYear = 2028;
  const minOmega = 2.2, maxOmega = 3.15;

  function xp(year)  { return padL + (year - minYear) / (maxYear - minYear) * chartW; }
  function yp(omega) { return padT + (1 - (omega - minOmega) / (maxOmega - minOmega)) * chartH; }

  // Grid lines
  ctx.strokeStyle = '#dde3ea'; ctx.lineWidth = 1;
  [2.2, 2.4, 2.6, 2.8, 3.0].forEach(o => {
    ctx.beginPath(); ctx.moveTo(padL, yp(o)); ctx.lineTo(padL + chartW, yp(o)); ctx.stroke();
    ctx.fillStyle = '#888'; ctx.font = '11px system-ui';
    ctx.textAlign = 'right'; ctx.fillText(o.toFixed(1), padL - 6, yp(o) + 4);
  });
  [1970, 1980, 1990, 2000, 2010, 2020].forEach(y => {
    ctx.beginPath(); ctx.moveTo(xp(y), padT); ctx.lineTo(xp(y), padT + chartH); ctx.stroke();
    ctx.fillStyle = '#888'; ctx.font = '11px system-ui';
    ctx.textAlign = 'center'; ctx.fillText(y, xp(y), padT + chartH + 16);
  });

  // ω = 2 conjecture line
  ctx.save();
  ctx.strokeStyle = '#e63946'; ctx.lineWidth = 1.4; ctx.setLineDash([5, 4]);
  ctx.beginPath(); ctx.moveTo(padL, yp(2.0)); ctx.lineTo(padL + chartW, yp(2.0)); ctx.stroke();
  ctx.restore();
  ctx.fillStyle = '#e63946'; ctx.font = '11px system-ui'; ctx.textAlign = 'left';
  ctx.fillText('ω = 2 (conjecture)', xp(2000), yp(2.0) - 5);

  // Hypothetical slider line
  const hyp = parseFloat(omegaSlider.value);
  if (hyp > 2.01) {
    ctx.save();
    ctx.strokeStyle = '#f4a261'; ctx.lineWidth = 1.4; ctx.setLineDash([3, 3]);
    ctx.beginPath(); ctx.moveTo(padL, yp(hyp)); ctx.lineTo(padL + chartW, yp(hyp)); ctx.stroke();
    ctx.restore();
  }

  // Schoolbook
  ctx.fillStyle = '#555'; ctx.font = '11px system-ui'; ctx.textAlign = 'left';
  ctx.fillText('Schoolbook 3.0', xp(1967), yp(3.0) - 6);

  // Step-down path of milestones
  const allPts = [SCHOOLBOOK, ...MILESTONES];
  ctx.save();
  ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 2.5; ctx.setLineDash([]);
  ctx.beginPath();
  allPts.forEach((m, i) => {
    const x = xp(m.year), y = yp(m.omega);
    if (i === 0) { ctx.moveTo(x, y); }
    else {
      // horizontal then vertical step
      const prevX = xp(allPts[i - 1].year);
      ctx.lineTo(x, yp(allPts[i - 1].omega));
      ctx.lineTo(x, y);
    }
  });
  // extend to right edge
  ctx.lineTo(padL + chartW, yp(MILESTONES[MILESTONES.length - 1].omega));
  ctx.stroke();
  ctx.restore();

  // Dots + labels for milestones
  MILESTONES.forEach(m => {
    ctx.beginPath();
    ctx.arc(xp(m.year), yp(m.omega), 4, 0, Math.PI * 2);
    ctx.fillStyle = '#1d3557'; ctx.fill();
  });

  // Axes labels
  ctx.fillStyle = '#444'; ctx.font = 'bold 12px system-ui';
  ctx.textAlign = 'center'; ctx.fillText('Year', padL + chartW / 2, H - 4);
  ctx.save(); ctx.translate(14, padT + chartH / 2); ctx.rotate(-Math.PI / 2);
  ctx.textAlign = 'center'; ctx.fillText('ω upper bound', 0, 0); ctx.restore();
}

function buildTable() {
  const n = N_SIZES[parseInt(nSlider.value) - 2];
  const hyp = parseFloat(omegaSlider.value);
  const rows = [SCHOOLBOOK, ...MILESTONES];
  if (Math.abs(hyp - 3.0) > 0.005 && !rows.some(r => Math.abs(r.omega - hyp) < 0.001)) {
    rows.push({ year: '—', omega: hyp, label: 'Your slider' });
    rows.sort((a, b) => b.omega - a.omega);
  }
  let html = fmt('<table class="op-table"><thead><tr><th>Algorithm</th><th>Year</th><th>ω</th><th>Operations (n=%n%)</th><th>Speedup vs n³</th></tr></thead><tbody>', { n: n.toLocaleString() });
  const base = ops(n, 3.0);
  rows.forEach(r => {
    const o = ops(n, r.omega);
    const sp = (base / o).toFixed(1) + '×';
    const cls = r.label === 'Your slider' ? ' class="highlight"' : '';
    html += `<tr${cls}><td>${r.label}</td><td>${r.year}</td><td>${r.omega.toFixed(4)}</td><td>${fmtOps(o)}</td><td>${sp}</td></tr>`;
  });
  html += '</tbody></table>';
  document.getElementById('opTable').innerHTML = html;
}

function update() {
  const idx = parseInt(nSlider.value) - 2;
  const n = N_SIZES[idx];
  nVal.textContent = 'n = ' + N_LABELS[idx];
  nLabel.textContent = fmt('Matrix size: %n% × %n%', { n: n.toLocaleString() });
  omegaVal.textContent = parseFloat(omegaSlider.value).toFixed(2);
  drawChart();
  buildTable();
}

nSlider.addEventListener('input', update);
omegaSlider.addEventListener('input', update);
update();
Result
Console

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 Real Complexity

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

  • Lower bound (trivial): ω≥2\omega \ge 2, because you must at least read the n2n^2 entries of the output.
  • Upper bound (schoolbook): ω≤3\omega \le 3, obvious from the definition.
  • Strassen (1969): ω≤log⁡27≈\omega \le \log_2 7 \approx 2.807. He multiplied 2×22 \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 ω=2\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 ω=2\omega = 2 would be a landmark result — or proving ω>2\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.

Where It Matters

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(n3)O(n^{3}) and the conjectured O(n2)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.

Conclusion

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 n3n^{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 ω=2\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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/matrix-multiplication-exponent/Content licensed under CC BY-NC 4.0.