Introduction

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?"

Try It

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">A 3×3 system as an <b>augmented matrix</b>: coefficients left of the bar, right-hand side after it. Press <b>Step</b> to eliminate one entry below the diagonal at a time. Once it's triangular, the demo back-substitutes to the solution.</p>
<div id="matrix" class="matrix"></div>
<div class="status" id="status">Press Step to begin forward elimination.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="solve" type="button">Solve all</button>
  <button id="shuffle" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Gaussian elimination on a 3x3 augmented matrix [A | b].
// FORWARD ELIMINATION: for each pivot column, subtract a multiple of the pivot
// row from each row below so that entries under the pivot become 0 — this is the O(n^3) heavy lifting.
// Then BACK-SUBSTITUTION reads the unknowns from the bottom row upward in O(n^2). The demo animates one elimination at a time.
const N = 3;
let M, plan, idx, solved, sol;

function makeSystem(){
  // Build a system with a known integer solution so display stays clean.
  let A, x;
  do {
    A = [];
    for(let i=0;i<N;i++){ const r=[]; for(let j=0;j<N;j++) r.push(rint(-3,3)); A.push(r); }
  } while (!nonsingular(A) || A.some(r=>r[0]===0));
  x = [rint(-3,3), rint(-3,3), rint(-3,3)];
  M = A.map((r,i)=> [...r, r.reduce((s,a,j)=>s+a*x[j],0)] );
  sol = x;
  plan = buildPlan(); idx = 0; solved = false;
}
function rint(a,b){ return Math.floor(Math.random()*(b-a+1))+a; }
function det3(a){ return a[0][0]*(a[1][1]*a[2][2]-a[1][2]*a[2][1])
  - a[0][1]*(a[1][0]*a[2][2]-a[1][2]*a[2][0])
  + a[0][2]*(a[1][0]*a[2][1]-a[1][1]*a[2][0]); }
function nonsingular(a){ return Math.abs(det3(a)) > 1e-9; }

// List of (pivot col, target row) eliminations, top-left to bottom-right.
function buildPlan(){ const p=[]; for(let c=0;c<N;c++) for(let r=c+1;r<N;r++) p.push({c,r}); return p; }

function render(hi){
  const box=document.getElementById('matrix'); box.innerHTML='';
  for(let r=0;r<N;r++){
    for(let c=0;c<N;c++){ box.appendChild(cell(M[r][c], cls(r,c,hi))); }
    const bar=document.createElement('div'); bar.className='bar'; bar.textContent='|'; box.appendChild(bar);
    box.appendChild(cell(M[r][N], solved?'sol':''));
  }
}
function cell(v,k){ const d=document.createElement('div'); d.className='num'+(k?' '+k:'');
  d.textContent = fmt(v); return d; }
function fmt(v){ const r=Math.round(v*100)/100; return Object.is(r,-0)?'0':String(r); }
function cls(r,c,hi){ if(!hi) return ''; if(r===hi.c&&c===hi.c) return 'pivot';
  if(r===hi.r&&c<=hi.c) return c===hi.c?'target':'zeroed'; return ''; }

function setStatus(t,ok){ const s=document.getElementById('status'); s.textContent=t; s.className='status'+(ok?' ok':''); }

function step(){
  if(solved) return;
  if(idx < plan.length){
    const {c,r}=plan[idx];
    const f = M[r][c]/M[c][c];            // multiplier
    for(let j=c;j<=N;j++) M[r][j] -= f*M[c][j];
    M[r][c]=0;                            // exact zero below the pivot
    idx++;
    render({c,r});
    setStatus(i18nFmt('Eliminated entry (%r%%v%,%c%%v%) using pivot row %c%%v%.', { r: r, v: 1, c: c }), false);
    if(idx===plan.length) setStatus('Matrix is now upper-triangular. Step again to back-substitute.', false);
  } else {
    // Back-substitution from bottom row up.
    const x=new Array(N);
    for(let i=N-1;i>=0;i--){ let s=M[i][N];
      for(let j=i+1;j<N;j++) s-=M[i][j]*x[j]; x[i]=s/M[i][i]; }
    solved=true; render(null);
    setStatus(i18nFmt('Solution: x=%fmt%, y=%fmt2%, z=%fmt3%.', { fmt: fmt(x[0]), fmt2: fmt(x[1]), fmt3: fmt(x[2]) }), true);
    console.log('Solution', x.map(fmt).join(', '), '| expected', sol.join(', '));
  }
  sync();
}
function solveAll(){ let guard=0; while(!solved && guard++<50) step(); }
function sync(){ document.getElementById('step').disabled=solved;
  document.getElementById('solve').disabled=solved; }

document.getElementById('step').addEventListener('click',step);
document.getElementById('solve').addEventListener('click',solveAll);
document.getElementById('shuffle').addEventListener('click',()=>{ makeSystem(); render(null);
  setStatus('New system — press Step to begin.', false); sync(); });

makeSystem(); render(null); sync();
Result
Console

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 n2n^{2}/2 such steps, each touching a whole row — roughly n3n^{3}/3 arithmetic operations in total. Press Shuffle for a fresh random system and watch the same machine grind out a new solution.

The Real Complexity

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 n3n^{3}/3 multiply-add operations — so the cost is O(n3)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(n2)O(n^{2}) work.
  • The same work, reused. Recording the multipliers turns elimination into the LU decomposition A = LU. Factor once in O(n3)O(n^{3}); then every new right-hand side b is solved in just O(n2)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 n3n^{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(n3)O(n^{3}) elimination remains the method of choice — a textbook example of solved beating asymptotically faster.

Where It Matters

"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.

Conclusion

Gaussian elimination is the rare problem that is genuinely finished: a fixed recipe, an exact answer, a predictable O(n3)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.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/gaussian-elimination/Content licensed under CC BY-NC 4.0.