Matrix Multiplication

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 $n^{3}$ scalar multiplications in total. Double the size and the work grows eightfold.

For decades everyone assumed $n^{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.

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">{{hint}}</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">{{status_initial}}</div>
<div class="btns">
  <button id="naive" type="button">{{btn_naive}}</button>
  <button id="strassen" type="button">{{btn_strassen}}</button>
  <button id="rand" type="button" class="ghost">{{btn_new}}</button>
</div>
<div class="scale">
  <button id="scaleup" type="button" class="ghost">{{btn_scale}}</button>
  <table id="scaletbl"><thead><tr><th>n</th><th>{{th_naive}}</th><th>{{th_strassen}}</th><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; }

// Code not found

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 $n^{3}$ while Strassen climbs as $n^{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.

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^\omega$.

• Naive (schoolbook): $O(n^{3})$. One multiplication per row-column-term triple. $\omega$ would be 3.
• Strassen, 1969: $O(n^{2.807})$. Volker Strassen showed 2×2 blocks need only 7 products instead of 8; applied recursively this gives $\omega \le \log_2 7 \approx \mathbf{2.807}$. This was the shock — $n^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 $\omega \le 2.371$.
• The lower bound is only $\omega \ge 2$. You must at least read the $n^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 $n^{2}$" and "we can do $n^{2.371}$" is one of the most stubborn unknowns in algorithm theory.

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.

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 $n^{3}$ fell to Strassen's $n^{2.807}$ in 1969, the record now sits near $n^{2.371}$, and the only certainty is that you can't beat $n^{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.