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.

The three row operations	$\begin{gathered}R_i\leftrightarrow R_j,\qquad R_i\to kR_i\ (k\neq0)\\R_i\to R_i+kR_j\end{gathered}$
Exactly one solution when	$\operatorname{rank}A=\operatorname{rank}[A\,\|\,b]=n$

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.

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.

Open this problem in the tool
1. Write it as an augmented matrix. The letters are doing no work, so drop them and keep the columns.
  
  $\begin{bmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{bmatrix}$
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 \quad (|-3| > |2|)$
3. Clear the rest of the first column by subtracting multiples of the pivot row.
  
  $R_2 \to R_2 - \tfrac{2}{-3}R_1, \qquad R_3 \to R_3 - \tfrac{-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 \quad (\tfrac{5}{3} > \tfrac{1}{3}) \;\Rightarrow\; \tfrac{1}{5}z = -\tfrac{1}{5}$
5. Back-substitute upwards. The last row gives z, the middle row then gives y, and the top gives x.
  
  $z = -1, \qquad y = 3, \qquad 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)\left(\tfrac{5}{3}\right)\left(\tfrac{1}{5}\right)(-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.
  
  $\max_i |A_i x - b_i| \approx 9 \times 10^{-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.

Open this problem in the tool
Show solution
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.
  
  $\begin{bmatrix} 1 & 1 & 1 & 3 \\ 2 & 2 & 2 & 7 \\ 3 & 1 & 2 & 5 \end{bmatrix} \xrightarrow{\;R_1 \leftrightarrow R_3\;} \begin{bmatrix} 3 & 1 & 2 & 5 \\ 2 & 2 & 2 & 7 \\ 1 & 1 & 1 & 3 \end{bmatrix} \qquad (|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 - \tfrac{2}{3}R_1, \quad R_3 \to R_3 - \tfrac{1}{3}R_1: \qquad \begin{bmatrix} 3 & 1 & 2 & 5 \\ 0 & \tfrac{4}{3} & \tfrac{2}{3} & \tfrac{11}{3} \\ 0 & \tfrac{2}{3} & \tfrac{1}{3} & \tfrac{4}{3} \end{bmatrix}$
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 - \tfrac{1}{2}R_2: \qquad \begin{bmatrix} 3 & 1 & 2 & 5 \\ 0 & \tfrac{4}{3} & \tfrac{2}{3} & \tfrac{11}{3} \\ 0 & 0 & 0 & -\tfrac{1}{2} \end{bmatrix}$
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.
  
  $\text{pivots } 3,\ \tfrac{4}{3} \ \text{— two, not three} \;\Longrightarrow\; \det A = 0, \qquad \text{last row: } 0 = -\tfrac{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.
  
  $\operatorname{rank} A = 2 \;<\; \operatorname{rank}[A\,|\,b] = 3 \;\Longrightarrow\; \text{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.
  
  $\text{Infinitely many: } \operatorname{rank} A = \operatorname{rank}[A\,|\,b] = 1, \quad \det A = 0, \quad \dim = 3 - 1 = 2 \quad (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: \quad \operatorname{rank}[A\,|\,b] = 2 = \operatorname{rank} A \;\Longrightarrow\; \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 - \operatorname{rank} A \ \text{ when } \operatorname{rank}[A|b] = \operatorname{rank} A; \qquad \det A = 0 \;\Longrightarrow\; \text{no } b \ \text{gives exactly one}$
Three equations by hand 5 steps
Solve x + y + z = 6, 2x − y + z = 3, x + 2y − z = 2.

Open this problem in the tool
Show solution
1. Clear x from the second row: take away twice the first row.
  
  $R_2\to R_2-2R_1:\quad-3y-z=-9$
2. Clear x from the third row: take away the first row.
  
  $R_3\to R_3-R_1:\quad y-2z=-4$
3. Clear y from the third row with a third of the new second row. Only z is left.
  
  $\begin{gathered}R_3\to R_3+\tfrac13R_2\\-\tfrac73z=-7\ \Rightarrow\ z=3\end{gathered}$
4. Back-substitute: z into the second row gives y, then y and z into the first give x.
  
  $y=2,\qquad x=6-2-3=1$
5. Check in the two equations not used last.
  
  $2-2+3=3,\qquad1+4-3=2\ \checkmark$
Answer

x = 1, y = 2, z = 3. The determinant is 7, so this is the only solution.

$x=1,\quad y=2,\quad z=3$
Infinitely many, written with a parameter 4 steps
Solve x + y + z = 3, x − y + z = 1, 2x + 2z = 4.
Show solution
1. Take the first row from the second: y = 1.
  
  $R_2\to R_2-R_1:\quad-2y=-2\ \Rightarrow\ y=1$
2. Take twice the first row from the third: the same equation again, so the third row adds nothing.
  
  $R_3\to R_3-2R_1:\quad-2y=-2$
3. Two independent rows for three unknowns, and no contradiction: one unknown is free.
  
  $\operatorname{rank}A=\operatorname{rank}[A\,|\,b]=2<3$
4. Let z = t, any number. The first row then gives x.
  
  $z=t:\quad x=3-1-t=2-t$
Answer

(x, y, z) = (2 − t, 1, t) for every t. t = 0 gives (2, 1, 0) and t = 2 gives (0, 1, 2); both check in all three equations.

$(x,y,z)=(2-t,\ 1,\ t),\quad t\in\mathbb{R}$

Supplementary problems, answers only

Solve x + y + z = 2, y + z = 1, z = −1.

Show answer

z = −1, y = 2, x = 1. The system is already triangular, so back-substitution is all it needs.

$z=-1,\quad y=2,\quad x=1$
Solve x + 2y + z = 4, 2x + y − z = −1, x − y + 2z = 7.

Show answer

x = 1, y = 0, z = 3.

$x=1,\quad y=0,\quad z=3$
Show that x + y + z = 1, x + 2y + 3z = 2, 2x + 3y + 4z = 5 has no solution.

Show answer

R₃ − R₁ − R₂ turns the left side into 0 and the right side into 2, and 0 = 2 is impossible.

$R_3-R_1-R_2:\quad0=2$

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.

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.