Gaussian Elimination

Choose which row to pivot on at each column and watch the elimination run. On the second preset the choice decides the answer: pivot on the tiny number and x comes back 0 instead of 1.

Worked example — Gaussian Elimination

Determinant	-1
Residual	8.8818 × 10⁻¹⁶

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Gaussian Elimination253 words

Elimination turns a system into an equivalent triangular one, which can then be read off from the bottom up. Its importance is not that it works — several methods work — but what it costs, because that is what decides which method a machine actually runs.

What each symbol means

n: the number of unknowns, and the only thing the cost depends on.
pivot: the coefficient a row is divided by. The order the algorithm fixes is what makes the procedure decision-free; which number lands there is what makes it survivable in floating point.

Assumes: A dense system with no exploitable structure. Sparse, banded or symmetric systems are cheaper, and choosing the right specialised method is most of numerical linear algebra.
Breaks when: The cost is cubic, and cubic is a wall. Elimination on n unknowns takes about n³/3 multiplications and as many additions — counted directly on a real elimination, 333,300 multiplications at n = 100 against the estimate’s 333,333. What that exponent costs you is a fixed penalty for growth: doubling the unknowns multiplies the work by exactly 8, so 100 unknowns take 333,300 multiplications and 200 take 2,666,600. A machine that clears a thousand unknowns in a second therefore needs eight seconds for two thousand and about two and a quarter hours for twenty thousand. That is the shape of the wall, and it is why the interesting question in numerical linear algebra is almost never how to solve a dense system but how to avoid having one.

The same two moves, in an order that removes every decision 🖖

Two equations needed one move: subtract a multiple of one row from another. Three equations need that move and one more, and the step list names both — a swap, to put a usable number in the pivot, and an elimination. The order is fixed: clear the first column, then the second, then read the answer off the bottom row and work upwards. Follow it and you never have to be clever about which equation to attack. That is the difference between a puzzle and a procedure, and it is why this scales: the same routine on a thousand unknowns is what every engineering package on earth still runs, sixty years after it was worth naming.

The determinant is the product of the pivots 🖖

Watch the pivots as the elimination proceeds and multiply them together, then flip the sign once for each row swap. That is the determinant, and it comes out of the work you were already doing. Most people meet determinants through the cofactor expansion instead, and it is worth knowing why nobody computes them that way: cofactors cost roughly n! operations against elimination's n³, and on a 20 × 20 that is 2 × 10¹⁸ against 8,000. A factor of 10¹⁴ is what decides which of the two a machine can actually be asked to run. The formula everyone is taught first is the one no machine has ever used.

One choice inside the procedure changes the answer 🖖

Press Pivoting off. The leading coefficient is 10⁻¹⁷, the algorithm dutifully divides by it, and x comes back as 0 when the true answer is 1. Nothing is broken and no rule was violated. Dividing by something small multiplies whatever rounding error is already there, and by the time it reaches the top of the back-substitution it has eaten the answer. It is a cliff, not a slope: sweeping that coefficient down, 10⁻¹² still gives four correct digits and 10⁻¹⁵ gives three, then 10⁻¹⁶ returns 2.22 and 10⁻¹⁷ returns 0. The edge sits at machine epsilon, the gap between 1 and the next number a double can represent. Tick the box and the algorithm divides by the largest available number instead, and every one of those cases solves exactly. That is why the residual card is on the page: it puts the answer back into the original equations, and it is the only way to tell a real solution from a confident one.

Problems solved in full

Solving 2x + y − z = 8 and the cost in accuracy 7 steps
Solve 2x + y − z = 8, −3x − y + 2z = −11, −2x + y + 2z = −3 — and then work out what the elimination cost you in accuracy.
1. Write it as an augmented matrix. The letters are doing no work, so drop them and keep the columns.
  
  $2 - 3 - 2 1 - 1 1 - 1 22 8 - 11 - 3$
2. Pivot on the largest first-column entry, which is −3 in row two, and swap it up. Every row swap flips the sign of the determinant, so keep count.
  
  $R_{1} \leftrightarrow R_{2} (∣ - 3∣ > ∣2∣)$
3. Clear the rest of the first column by subtracting multiples of the pivot row.
  
  $R_{2} \to R_{2} - \frac{2}{- 3} R_{1}, R_{3} \to R_{3} - \frac{- 2}{- 3} R_{1}$
4. Repeat on the second column, then read the bottom row: it holds one unknown and its value.
  
  $R_{2} \leftrightarrow R_{3} (\frac{5}{3} > \frac{1}{3}) \Rightarrow \frac{1}{5} z = - \frac{1}{5}$
5. Back-substitute upwards. The last row gives z, the middle row then gives y, and the top gives x.
  
  $z = - 1, y = 3, x = 2$
6. Multiply the pivots and apply the sign for two swaps to get the determinant, and check the answer by substituting into the original equations rather than the reduced ones.
  
  $det = (- 3) (\frac{5}{3}) (\frac{1}{5}) (- 1)^{2} = - 1$
7. The residual comes out at about 10⁻¹⁶, which is not zero. It is the size of the rounding a computer cannot avoid, and it is the honest thing to report — an answer that claims to be exact is either from integer arithmetic or is not looking. Change the leading coefficient to 10⁻¹⁷ with pivoting off and the same residual becomes 1, which is the same warning shouting.
  
  $i max ∣ A_{i} x - b_{i} ∣ \approx 9 \times 1 0^{- 16}$
Answer

x = 2, y = 3, z = −1, determinant −1. The residual of about 10⁻¹⁶ is the arithmetic being as exact as floating point allows. Turn pivoting off on a badly scaled system and that number is the one that tells you the answer is wrong.
A determinant of 0, twice, meaning two different things 7 steps
The Contradictory preset has no solution and One equation three times has infinitely many, and both print a determinant of 0. Work out what actually separates them, and decide what changing the right-hand side could ever buy you.
1. Partial pivoting looks down the first column for the largest coefficient. It finds 3 in the bottom row, so the first move is a swap.
  
  $123121122375 R_{1} \leftrightarrow R_{3} 321121221573 (∣3∣ > ∣2∣ > ∣1∣)$
2. Clear the column: subtract ⅔ of the new first row from the second, and ⅓ of it from the third.
  
  $R_{2} \to R_{2} - \frac{2}{3} R_{1}, R_{3} \to R_{3} - \frac{1}{3} R_{1} : 300 1 \frac{4}{3} \frac{2}{3} 2 \frac{2}{3} \frac{1}{3} 5 \frac{11}{3} \frac{4}{3}$
3. In the second column 4/3 already sits above 2/3, so nothing needs swapping. Subtract half of row 2 from row 3.
  
  $R_{3} \to R_{3} - \frac{1}{2} R_{2} : 300 1 \frac{4}{3} 0 2 \frac{2}{3} 0 5 \frac{11}{3} - \frac{1}{2}$
4. Row 3 is now empty on the left with −½ on the right, which reads 0 = −½. Only two pivots were laid down, 3 and 4/3, where three unknowns need three, and a missing pivot makes the product zero.
  
  $pivots 3, \frac{4}{3} — two, not three ⟹ det A = 0, last row: 0 = - \frac{1}{2}$
5. Rank is what the determinant is hiding. The coefficient matrix has two independent rows. The augmented matrix has three, because that leftover −½ is a row nothing can cancel. Rank 2 against rank 3 is what "no solution" means.
  
  $rank A = 2 < rank [A ∣ b] = 3 ⟹ no solution$
6. The One equation three times preset does the same arithmetic and says something else. Every row is a multiple of the first, so both ranks are 1 and the determinant is 0 again. The solution set has 3 − 1 = 2 free directions: the whole plane x + y + z = 3. The tool says "infinitely many" without saying in how many directions.
  
  $Infinitely many: rank A = rank [A ∣ b] = 1, det A = 0, dim = 3 - 1 = 2 (x + y + z = 3)$
7. Change one number and see which quantity moves. Put 6 where the 7 is on the right of row 2. The coefficient matrix is untouched, so the determinant does not stir, but the augmented rank drops to 2 and the answer becomes a line of solutions instead of none.
  
  $b_{2} = 7 \to 6 : rank [A ∣ b] = 2 = rank A ⟹ dim = 3 - 2 = 1$
Answer

The determinant only reports whether the coefficient matrix has a full set of pivots. It never looks at the right-hand side, which is why it cannot separate the two presets, and the two ranks can: no solution when they disagree, and a solution set of dimension 3 − rank when they agree. Once the determinant is 0, no right-hand side will buy you a single answer — you get none or a whole family, and the choice between those two is all that b decides. The residual card goes dark for the same reason it exists: a residual needs a solution to put back into the equations.

$dim = n - rank A when rank [A ∣ b] = rank A; det A = 0 ⟹ no b gives exactly one$

Learning path

Solving for x, from the minus sign upward

References (1)

Two centuries of the method being reinvented and misattributed, including how Gauss's name came to be on it: J. F. Grcar, "How ordinary elimination became Gaussian elimination." Historia Mathematica 38:2 (2011), 163–218.

By the 42Math team · Updated 2026-08-26

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Mathematics lessons →

Example problems

A system that solves - Two swaps and three eliminations give x = 2, y = 3, z = −1. The residual is around 10⁻¹⁶, which is the arithmetic being as exact as a computer can be.
Pivoting off - The first coefficient is 10⁻¹⁷ and pivoting is off, so the algorithm divides by it. The answer comes back as x = 0 when it should be 1, and the residual is 1 instead of 0. Tick the box and the same system solves exactly.
One equation three times - Every row is a multiple of the first, so after elimination two rows are entirely zero. The determinant is 0 and the system does not pin down a point — it pins down a plane.
Contradictory - The second row contradicts the first: the same left side with a different right side. Elimination leaves 0 = 1, and no amount of arithmetic will rescue that.