Gaussian Elimination

Three unknowns, three equations, all tangled together. 2x + y − z = 8. −3x − y + 2z = −11. −2x + y + 2z = −3. Stare at it and nothing jumps out. Yet there is a single, mechanical recipe that will hand you x = 2, y = 3, z = −1 every time, with no cleverness required.

That recipe is Gaussian elimination. You add multiples of one equation to another to knock out variables, until the system collapses into a neat staircase: the last equation has one unknown, the one above it has two, and so on. Then you walk back up, substituting as you go.

The method is named after Carl Friedrich Gauss (early 1800s), though versions of it appear in the Chinese Nine Chapters on the Mathematical Art around 2,000 years ago. It is not an open problem or a hard one — it is solved, fast, and everywhere. Understanding it is understanding how computers actually answer "what makes all these equations true at once?"

Below is a 3×3 system written as an augmented matrix — the coefficients on the left, the right-hand side after the bar. Press Step to apply one elimination at a time and watch zeros march down below the diagonal. When the matrix reaches triangular form, the demo back-substitutes to read off the answer.

<p class="hint">{{hint}}</p>
<div id="matrix" class="matrix"></div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="shuffle" type="button" class="ghost">{{btn_shuffle}}</button>
</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; }
.matrix { display: inline-grid; grid-template-columns: repeat(3, 58px) 14px 58px;
          gap: 6px; padding: .6rem .8rem; border-left: 3px solid #1d3557;
          border-right: 3px solid #1d3557; border-radius: 6px; margin: .3rem 0 .6rem; }
.num { height: 40px; display: flex; align-items: center; justify-content: center;
       font: 600 15px ui-monospace, monospace; background: #eef2f6;
       border: 1px solid #d4dde6; border-radius: 6px; transition: all .25s; }
.num.pivot { background: #1d3557; color: #fff; border-color: #1d3557; }
.num.target { background: #ffe9b8; border-color: #e8b84b; }
.num.zeroed { background: #d6f0dd; border-color: #8fcfa3; color: #0a7d33; }
.num.sol { background: #e63946; color: #fff; border-color: #c92f3c; }
.bar { display: flex; align-items: center; justify-content: center; color: #1d3557; font-weight: 700; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
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; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice the rhythm: pick a pivot on the diagonal, then subtract the right multiple of its row from every row beneath it so that column becomes zero. For an n×n system this is about $n^{2}$/2 such steps, each touching a whole row — roughly $n^{3}$/3 arithmetic operations in total. Press Shuffle for a fresh random system and watch the same machine grind out a new solution.

How expensive is it to solve Ax = b? Gaussian elimination gives a clean answer.

• Forward elimination does the heavy lifting. Clearing each column below the pivot touches every entry in the rows beneath it, and summing over all columns gives about $n^{3}$/3 multiply-add operations — so the cost is $O(n^{3})$.
• Back-substitution is cheap by comparison: once the matrix is triangular, reading off the unknowns from the bottom up takes only $O(n^{2})$ work.
• The same work, reused. Recording the multipliers turns elimination into the LU decomposition A = LU. Factor once in $O(n^{3})$; then every new right-hand side b is solved in just $O(n^{2})$.
• Stability needs pivoting. Naively dividing by a tiny pivot magnifies rounding error. Partial pivoting — swapping in the largest available pivot each step — keeps the answer trustworthy at negligible extra cost.

Can we beat $n^{3}$? In theory, yes: solving a system is no harder than multiplying two matrices, and fast matrix multiplication brings the exponent below 2.4. But those algorithms carry huge constants and shaky stability, so for the dense systems that actually arise, plain $O(n^{3})$ elimination remains the method of choice — a textbook example of solved beating asymptotically faster.

"Solve these linear equations at once" is one of the most common requests in all of computing, and Gaussian elimination is the engine that answers it:

• Engineering and physics: finite-element and circuit simulations reduce bridges, airflow and electronics to enormous linear systems solved by elimination (or its LU cousin).
• Statistics and machine learning: fitting a least-squares regression means solving the normal equations — a linear system — and many neural-network building blocks rest on the same algebra.
• Computer graphics: lighting, physics solvers and mesh deformation all funnel into Ax = b dozens of times per frame.
• Optimization: interior-point methods for linear programming solve a linear system at every single iteration.

Learn Gaussian elimination and you've met the quiet subroutine inside simulation, graphics, data science and optimization alike — the step where the math finally turns into a number.

Gaussian elimination is the rare problem that is genuinely finished: a fixed recipe, an exact answer, a predictable $O(n^{3})$ cost. Row-reduce to a triangular staircase, back-substitute up the steps, and the tangle of equations resolves into a single point.

Its quiet ubiquity is the lesson. Behind a weather forecast, a rendered frame, a fitted model or an optimized supply chain, the same humble subroutine is running — turning a grid of coefficients into an answer, exactly as it did two centuries ago. For the deeper question of whether every such workhorse could be made faster still, see matrix multiplication and linear programming.