Introduction

Almost every heavy computation you can name eventually boils down to multiplying two matrices. Spinning a 3D scene, training a neural network, simulating airflow, ranking web pages — under the hood it's grids of numbers being multiplied together.

The recipe you learn in school is simple: to get each entry of the result, walk across one row and down one column, multiplying pairs and adding them up. For two n × n matrices that's one multiplication for every (row, column, term) triple — about n3n^{3} scalar multiplications in total. Double the size and the work grows eightfold.

For decades everyone assumed n3n^{3} was simply the cost — you obviously need to touch every combination. Then in 1969 someone showed that assumption was wrong. And the deepest version of the question is still open today.

Count the Multiplications

Below are two 2 × 2 matrices. The schoolbook method needs 8 scalar multiplications to multiply them. In 1969 Volker Strassen found a way to do it with only 7 — using clever sums and differences instead of one of the products.

<p class="hint">Two 2×2 matrices. The <b>schoolbook</b> method uses 8 scalar
multiplications; <b>Strassen</b> uses only 7. Run both — the answer is the
same, but the multiplication count differs. Then scale the matrices up and watch
the gap explode.</p>
<div class="grids">
  <div class="mwrap"><span class="lab">A</span><div id="A" class="mat"></div></div>
  <div class="times">&times;</div>
  <div class="mwrap"><span class="lab">B</span><div id="B" class="mat"></div></div>
  <div class="times">=</div>
  <div class="mwrap"><span class="lab">C</span><div id="C" class="mat res"></div></div>
</div>
<div class="status" id="status">Press a method to multiply A × B.</div>
<div class="btns">
  <button id="naive" type="button">Schoolbook (8×)</button>
  <button id="strassen" type="button">Strassen (7×)</button>
  <button id="rand" type="button" class="ghost">New numbers</button>
</div>
<div class="scale">
  <button id="scaleup" type="button" class="ghost">Scale it up →</button>
  <table id="scaletbl"><thead><tr><th>n</th><th>Schoolbook n³</th><th>Strassen n^2.807</th><th>Saved</th></tr></thead><tbody></tbody></table>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.grids { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin: .4rem 0 .2rem; }
.mwrap { text-align: center; }
.lab { font: 700 13px ui-monospace, monospace; color: #1d3557; display: block; margin-bottom: 3px; }
.mat { display: grid; grid-template-columns: repeat(2, 44px); gap: 4px; }
.mat > div { width: 44px; height: 40px; display: flex; align-items: center; justify-content: center;
             font: 700 15px ui-monospace, monospace; background: #e8eef3; color: #1d3557;
             border: 1px solid #cdd9e3; border-radius: 7px; }
.mat.res > div { background: #f3f5f7; color: #555; }
.mat.res.done > div { background: #d6f0df; color: #0a7d33; border-color: #aedcc0; }
.times { font: 700 20px system-ui; color: #888; }
.status { font-size: .95rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: 1rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.scale { border-top: 1px solid #e3e7ec; padding-top: .8rem; }
table { border-collapse: collapse; font: 13px ui-monospace, monospace; margin-top: .6rem; width: 100%; }
th, td { border: 1px solid #dfe4ea; padding: .35rem .5rem; text-align: right; }
th { background: #f1f4f7; color: #1d3557; }
td.saved { color: #0a7d33; font-weight: 700; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Matrix multiplication: checking a product is trivial, but how FEW scalar
// multiplications does it take? Schoolbook uses 8 for a 2x2 block; Strassen
// (1969) uses 7. Recursively that lowers the exponent from 3 to log2(7)~2.807.
// The true optimal exponent omega is an OPEN problem (only known: 2 <= omega).
let A = [[1,2],[3,4]], B = [[5,6],[7,8]];

function drawMat(id, m){ const el=document.getElementById(id); el.innerHTML='';
  for(let r=0;r<2;r++)for(let c=0;c<2;c++){ const d=document.createElement('div'); d.textContent=m[r][c]; el.appendChild(d);} }
function drawRes(m, done){ const el=document.getElementById('C'); el.className='mat res'+(done?' done':''); el.innerHTML='';
  for(let r=0;r<2;r++)for(let c=0;c<2;c++){ const d=document.createElement('div'); d.textContent=(m?m[r][c]:'?'); el.appendChild(d);} }
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

// Schoolbook: 8 scalar multiplications for a 2x2 result.
function naive(A,B){ let mults=0; const C=[[0,0],[0,0]];
  for(let i=0;i<2;i++)for(let j=0;j<2;j++){ let s=0;
    for(let k=0;k<2;k++){ s+=A[i][k]*B[k][j]; mults++; } C[i][j]=s; }
  return {C, mults}; }

// Strassen: 7 products (the m1..m7), recombined with adds/subtracts only.
function strassen(A,B){ const a=A[0][0],b=A[0][1],c=A[1][0],d=A[1][1];
  const e=B[0][0],f=B[0][1],g=B[1][0],h=B[1][1];
  const m1=(a+d)*(e+h), m2=(c+d)*e, m3=a*(f-h), m4=d*(g-e),
        m5=(a+b)*h, m6=(c-a)*(e+f), m7=(b-d)*(g+h);
  const C=[[m1+m4-m5+m7, m3+m5],[m2+m4, m1-m2+m3+m6]];
  return {C, mults:7}; }

function runNaive(){ const {C,mults}=naive(A,B); drawRes(C,true);
  setStatus(fmt('Schoolbook done with %mults% scalar multiplications.', { mults: mults }),'ok'); }
function runStrassen(){ const {C,mults}=strassen(A,B); drawRes(C,true);
  setStatus(fmt('Strassen done with %mults% scalar multiplications — same answer, one fewer product.', { mults: mults }),'ok'); }
function newNums(){ const rnd=()=>Math.floor(Math.random()*9)+1;
  A=[[rnd(),rnd()],[rnd(),rnd()]]; B=[[rnd(),rnd()],[rnd(),rnd()]];
  drawMat('A',A); drawMat('B',B); drawRes(null,false); setStatus('Press a method to multiply A × B.',''); }

function scaleUp(){ const body=document.querySelector('#scaletbl tbody'); body.innerHTML='';
  for(let p=1;p<=8;p++){ const n=Math.pow(2,p);
    const naiveOps=Math.round(Math.pow(n,3));
    const strOps=Math.round(Math.pow(7,p)); // exactly 7^log2(n) products, recursive Strassen
    const tr=document.createElement('tr');
    tr.innerHTML='<td>'+n+'</td><td>'+naiveOps.toLocaleString()+'</td><td>'+strOps.toLocaleString()+
      '</td><td class="saved">'+(100*(1-strOps/naiveOps)).toFixed(0)+'%</td>';
    body.appendChild(tr); } }

document.getElementById('naive').addEventListener('click',runNaive);
document.getElementById('strassen').addEventListener('click',runStrassen);
document.getElementById('rand').addEventListener('click',newNums);
document.getElementById('scaleup').addEventListener('click',scaleUp);
drawMat('A',A); drawMat('B',B); drawRes(null,false);
Result
Console

One saved multiplication sounds trivial. But the trick is recursive: split big matrices into blocks and apply it again and again. Press Scale it up and watch the counts diverge — the naive method climbs as n3n^{3} while Strassen climbs as n2.807n^{2.807}. Verifying that a result is correct is easy (just check the entries); finding the fewest possible multiplications is the hard, still-open part.

The Real Complexity

How fast can you multiply two n × n matrices? Theorists track a single number, the matrix multiplication exponent ω\omega (omega): the smallest value such that the work scales like nωn^\omega.

  • Naive (schoolbook): O(n3)O(n^{3}). One multiplication per row-column-term triple. ω\omega would be 3.
  • Strassen, 1969: O(n2.807)O(n^{2.807}). Volker Strassen showed 2×2 blocks need only 7 products instead of 8; applied recursively this gives ω≤log⁡27≈2.807\omega \le \log_2 7 \approx \mathbf{2.807}. This was the shock — n3n^3 is not optimal.
  • Coppersmith–Winograd (1990) and successors pushed the bound down further, and the current record (Alman, Duan, Vassilevska Williams, Wu, Zhou and others, 2020s) sits at roughly ω≤2.371\omega \le 2.371.
  • The lower bound is only ω≥2\omega \ge 2. You must at least read the n2n^2 entries of the answer, so ω\omega can't be below 2. Whether the truth is 2, or 2.371, or somewhere between, nobody knows — finding the exact value of ω\omega is a famous open problem.

That's the punchline: matrix multiplication is firmly in P — it's easy in the grand scheme — yet we still cannot pin down its exact cost. The gap between "must take at least n2n^{2}" and "we can do n2.371n^{2.371}" is one of the most stubborn unknowns in algorithm theory.

Where It Matters

Shave the exponent on matrix multiplication and you speed up an astonishing amount of computing at once:

  • Machine learning: every layer of a neural network is a matrix multiply. It's why GPUs and TPUs are built to do little else, and why training cost is dominated by this one operation.
  • Graphics and simulation: transforming, rotating and projecting 3D scenes, plus solving the linear systems behind physics engines, all reduce to matrix products.
  • Algorithm building block: many problems — graph transitive closure, all-pairs shortest paths, context-free parsing — are provably no harder than matrix multiplication, so any speedup ripples outward.
  • Theory of the possible: the chase for ω\omega drives deep mathematics (tensor rank, group theory), even when the record-setting algorithms are too impractical to run.

In practice, libraries usually stick close to the naive method or Strassen, because the record-holders carry huge hidden constants. But the question of how fast we could go shapes the whole field.

Conclusion

Matrix multiplication is a quiet paradox: it's one of the most-run operations on Earth, taught to teenagers, and yet we genuinely do not know how fast it can be done. The schoolbook n3n^{3} fell to Strassen's n2.807n^{2.807} in 1969, the record now sits near n2.371n^{2.371}, and the only certainty is that you can't beat n2n^{2}.

So the next time a model trains or a game renders, remember that under the floods of arithmetic sits an honest mystery. Unlike the truly hard problems like P vs NP, this one is easy to compute — we just can't agree on exactly how easy.

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/Content licensed under CC BY-NC 4.0.