Gaussian elimination is one step repeated. Row k is the pivot row, with the pivot aₖₖ, and row i is a row
below it. Row i is replaced by row i minus m times row k, where the multiplier is m = aᵢₖ/aₖₖ. Every entry of
row i then changes by
- a′ᵢⱼ = aᵢⱼ − (aᵢₖ/aₖₖ) · aₖⱼ
In the pivot column, j = k, the new entry is 0, which is what the step is for. The same rule applies to the
right-hand side in the augmented matrix [A | b]. Repeat the step for every row below the pivot, move to the
next column, and continue until the matrix is in row echelon form. Then solve from the bottom up by back
substitution. The card above computes one entry after one step; the whole reduction, one line per row
operation, is in the matrix calculator.
Holds when the pivot aₖₖ is not 0. If it is 0, swap row k with a row further down that has a non-zero entry
in the same column. If there is no such row, the column has no pivot and its variable is free.
Worked example
The system 2x + y − z = 8, −3x − y + 2z = −11, −2x + y + 2z = −3 has the augmented matrix
|
x |
y |
z |
right-hand side |
| R₁ |
2 |
1 |
−1 |
8 |
| R₂ |
−3 |
−1 |
2 |
−11 |
| R₃ |
−2 |
1 |
2 |
−3 |
The pivot is 2 in R₁. For R₂ the multiplier is −3/2, so R₂ is replaced by R₂ − (−3/2)R₁, that is
R₂ + (3/2)R₁. The right-hand side becomes −11 − (−3/2) · 8 = −11 + 12 = 1.
The whole of R₂ becomes (0, 1/2, 1/2 | 1). For R₃ the multiplier is −2/2 = −1, and R₃ + R₁ gives
(0, 2, 1 | 5). The next pivot is 1/2 in R₂. The multiplier for R₃ is 2/(1/2) = 4, and R₃ − 4R₂ gives
(0, 0, −1 | 1).
Read the echelon form from the bottom: −z = 1 gives z = −1. Then (1/2)y + (1/2)(−1) = 1 gives y = 3, and
2x + 3 + 1 = 8 gives x = 2. Check in the third equation: −4 + 3 − 2 = −3.
The same system in the matrix calculator.
The sign and the direction of the multiplier
The multiplier is the entry to be cleared divided by the pivot, aᵢₖ/aₖₖ, and it is subtracted. Two slips give
a row that looks reasonable and a solution that is wrong:
| Step for the right-hand side of R₂ |
Result |
| Right: −11 − (−3/2) · 8 |
1 |
| Multiplier upside down, −11 − (2/(−3)) · 8 |
−17/3 |
| Sign dropped, −11 − (3/2) · 8 |
−23 |
Nothing in the new row looks wrong, and the final check is many steps away. The pivot column catches it at
once: with the right multiplier its entry becomes 0, −3 − (−3/2) · 2 = 0, and with either slip it does not.
A second example: a zero pivot
The system x + 2y + z = 4, 2x + 4y + 3z = 9, x + 3y + 2z = 7. With the pivot 1, R₂ − 2R₁ gives the row
(0, 0, 1 | 1) and R₃ − R₁ gives (0, 1, 1 | 3). The entry in the second column of R₂ is now 0, so it cannot be
the pivot. Swap R₂ and R₃: the rows become (0, 1, 1 | 3) and (0, 0, 1 | 1), already in echelon form. From the
bottom: z = 1, y = 2 and x = 4 − 4 − 1 = −1.
Had both rows below R₁ had 0 in the second column, no row could have been swapped in. The column then has no
pivot, y is a free variable, and the system has either infinitely many solutions or none. How many free
variables there are is given by the rank.
Where to go next
The elimination method is the same idea for
two or three equations written out in full. For a square system with a non-zero determinant,
Cramer’s rule gives one unknown at a
time. How matrices are multiplied is on the page on
matrix multiplication.
| What the echelon form shows |
Solutions |
| A pivot in every column of the unknowns, and no row 0 = c |
Exactly one |
| A column of an unknown without a pivot, and no row 0 = c |
Infinitely many |
| A row (0, 0, …, 0 | c) with c ≠ 0 |
None |
Common mistakes
- The multiplier upside down. It is aᵢₖ/aₖₖ, the entry to be cleared over the pivot.
- Forgetting the right-hand side. The row operation applies to the whole row of the augmented matrix,
the last column included.
- Changing the pivot row. The pivot row stays as it is; the rows below it are replaced.
- Using a row that has already changed. Every multiplier in a column is taken against the same pivot row.
Frequently asked questions
What is the difference between Gaussian elimination and Gauss–Jordan?
Gaussian elimination stops at row echelon form and finishes with back substitution. Gauss–Jordan goes on:
each pivot is scaled to 1 and the column is cleared above it as well, until the matrix is in reduced row
echelon form and the solution can be read off.
Does the pivot have to be 1?
No. The step works with any non-zero pivot. Dividing the pivot row by the pivot first gives multipliers
without fractions, at the cost of one more step.
How do I see that a system has no solution?
A row of the echelon form becomes (0, 0, …, 0 | c) with c ≠ 0. That row says 0 = c, which is false.
Does the order of the rows matter?
Swapping two rows does not change the solutions, since it only lists the equations in another order. The
order does decide which pivots you get, and so how many fractions you work with.