Gaussian Elimination
Gaussian elimination solves a system of linear equations by using row operations to reduce its augmented matrix to row echelon form. The pivot positions in that form show whether the system has no solution, exactly one solution or infinitely many, and back substitution then gives the solutions.
Before this lesson: Augmented Matrices, Systems of Equations in Three Variables and Matrix Operations
What Gaussian elimination does
A system of linear equations is stored in an augmented matrix: one row per equation, one column per variable and a last column for the constants. Three row operations change the matrix without changing the solutions:
- Swap two rows.
- Multiply a row by a nonzero number.
- Add a multiple of one row to another row.
Each operation can be undone by another row operation, so the old and new systems have exactly the same solutions. Gaussian elimination uses them to create zeros below the diagonal, working left to right, until the matrix is in row echelon form.
Row echelon form and pivot positions
A matrix is in row echelon form when
- every row of all zeros is below every nonzero row,
- the first nonzero entry of each row (its leading entry) is to the right of the leading entry of the row above, and
- every entry below a leading entry is 0.
A pivot position is the location of a leading entry in a row echelon form, and its column is a pivot column. A matrix can have many echelon forms, but the pivot positions are always the same. Variables in pivot columns are basic variables; the others are free variables, which can take any value.
Gaussian elimination steps
- Write the augmented matrix of the system.
- Find the leftmost nonzero column. If needed, swap rows so its top entry is not 0. This entry is a pivot.
- Add multiples of the pivot row to the rows below it to make every entry under the pivot 0.
- Cover the pivot row and repeat steps 2 and 3 on the rows below, until the matrix is in row echelon form.
- Read the pivot pattern, then solve from the bottom row up (back substitution).
Existence and uniqueness of solutions
| Echelon form shows | Number of solutions |
|---|---|
| A row [0 0 … 0 | b] with b ≠ 0 (the last column is a pivot column) | None: the system is inconsistent |
| No such row, and every variable column has a pivot | Exactly one |
| No such row, and some variable column has no pivot | Infinitely many, one for each value of the free variables |
A system with a solution is called consistent. A row of all zeros, [0 0 … 0 | 0], just says 0 = 0 and is fine.
Gaussian elimination examples
Example 1: A system with one solution
Solve x + 2y − z = 3, 2x + 5y + z = 14, −x + y + 4z = 9.
\left[\begin{array}{rrr|r} 1 & 2 & -1 & 3 \\ 2 & 5 & 1 & 14 \\ -1 & 1 & 4 & 9 \end{array}\right]Write the augmented matrix. The pivot is the 1 in row 1.
\left[\begin{array}{rrr|r} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 8 \\ -1 & 1 & 4 & 9 \end{array}\right]R₂ − 2R₁ → R₂: 2 − 2 = 0, 5 − 4 = 1, 1 + 2 = 3, 14 − 6 = 8.
\left[\begin{array}{rrr|r} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 8 \\ 0 & 3 & 3 & 12 \end{array}\right]R₃ + R₁ → R₃: −1 + 1 = 0, 1 + 2 = 3, 4 − 1 = 3, 9 + 3 = 12.
\left[\begin{array}{rrr|r} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 8 \\ 0 & 0 & -6 & -12 \end{array}\right]R₃ − 3R₂ → R₃: 3 − 3 = 0, 3 − 9 = −6, 12 − 24 = −12. This is row echelon form.
-6z = -12 \Rightarrow z = 2
Pivots in all three variable columns, so there is one solution. Solve row 3.
y + 3(2) = 8 \Rightarrow y = 2
Back substitute into row 2.
x + 2(2) - 2 = 3 \Rightarrow x = 1
Back substitute into row 1.
Answer: (x, y, z) = (1, 2, 2). Check in the third equation: −1 + 2 + 8 = 9.
Example 2: A system with infinitely many solutions
Solve x + y + 2z = 4, 2x + 3y + 3z = 9, x + 2y + z = 5.
\left[\begin{array}{rrr|r} 1 & 1 & 2 & 4 \\ 0 & 1 & -1 & 1 \\ 1 & 2 & 1 & 5 \end{array}\right]R₂ − 2R₁ → R₂: 0, 3 − 2 = 1, 3 − 4 = −1, 9 − 8 = 1.
\left[\begin{array}{rrr|r} 1 & 1 & 2 & 4 \\ 0 & 1 & -1 & 1 \\ 0 & 1 & -1 & 1 \end{array}\right]R₃ − R₁ → R₃: 0, 2 − 1 = 1, 1 − 2 = −1, 5 − 4 = 1.
\left[\begin{array}{rrr|r} 1 & 1 & 2 & 4 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 0 \end{array}\right]R₃ − R₂ → R₃. Row echelon form.
z = t
Column 3 has no pivot, so z is free. Let z = t for any number t.
y - t = 1 \Rightarrow y = 1 + t
Solve row 2.
x + (1 + t) + 2t = 4 \Rightarrow x = 3 - 3t
Solve row 1 and combine like terms.
Answer: (x, y, z) = (3 − 3t, 1 + t, t) for every real number t. For example, t = 0 gives (3, 1, 0) and t = 1 gives (0, 2, 1).
Example 3: An inconsistent system
Solve x − y + z = 2, 2x + y − z = 1, 3x = 5.
\left[\begin{array}{rrr|r} 1 & -1 & 1 & 2 \\ 0 & 3 & -3 & -3 \\ 3 & 0 & 0 & 5 \end{array}\right]R₂ − 2R₁ → R₂: 0, 1 + 2 = 3, −1 − 2 = −3, 1 − 4 = −3.
\left[\begin{array}{rrr|r} 1 & -1 & 1 & 2 \\ 0 & 3 & -3 & -3 \\ 0 & 3 & -3 & -1 \end{array}\right]R₃ − 3R₁ → R₃: 0, 0 + 3 = 3, 0 − 3 = −3, 5 − 6 = −1.
\left[\begin{array}{rrr|r} 1 & -1 & 1 & 2 \\ 0 & 3 & -3 & -3 \\ 0 & 0 & 0 & 2 \end{array}\right]R₃ − R₂ → R₃: −1 − (−3) = 2.
0x + 0y + 0z = 2
Row 3 says 0 = 2, which is impossible.
Answer: no solution. The last column is a pivot column, so the system is inconsistent.
Example 4: A system with parameters
For which values of h and k does the system x + 3y = 2, 4x + hy = k have no solution, one solution or infinitely many?
\left[\begin{array}{rr|r} 1 & 3 & 2 \\ 4 & h & k \end{array}\right]Write the augmented matrix.
\left[\begin{array}{rr|r} 1 & 3 & 2 \\ 0 & h - 12 & k - 8 \end{array}\right]R₂ − 4R₁ → R₂.
h - 12 \ne 0 \Rightarrow \text{one solution}If h ≠ 12, both columns have pivots.
h = 12,\; k \ne 8 \Rightarrow \text{no solution}Row 2 becomes [0 0 | k − 8] with k − 8 ≠ 0.
h = 12,\; k = 8 \Rightarrow \text{infinitely many}Row 2 becomes all zeros, and y is free.
Answer: one solution when h ≠ 12; no solution when h = 12 and k ≠ 8; infinitely many when h = 12 and k = 8.
Example 5: Ticket sales
A theater sold 400 tickets for $3,600. Adult tickets cost $12, student tickets $8 and child tickets $5, and it sold twice as many student tickets as child tickets. How many of each did it sell?
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 400 \\ 12 & 8 & 5 & 3600 \\ 0 & 1 & -2 & 0 \end{array}\right]Let a, s and c be the numbers of adult, student and child tickets: a + s + c = 400, 12a + 8s + 5c = 3600 and s − 2c = 0.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 400 \\ 0 & -4 & -7 & -1200 \\ 0 & 1 & -2 & 0 \end{array}\right]R₂ − 12R₁ → R₂: 8 − 12 = −4, 5 − 12 = −7, 3600 − 4800 = −1200.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 400 \\ 0 & 1 & -2 & 0 \\ 0 & -4 & -7 & -1200 \end{array}\right]Swap R₂ and R₃ to get a simpler pivot.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 400 \\ 0 & 1 & -2 & 0 \\ 0 & 0 & -15 & -1200 \end{array}\right]R₃ + 4R₂ → R₃: −7 − 8 = −15.
-15c = -1200 \Rightarrow c = 80
Solve row 3.
s - 2(80) = 0 \Rightarrow s = 160
Back substitute into row 2.
a + 160 + 80 = 400 \Rightarrow a = 160
Back substitute into row 1.
Answer: 160 adult, 160 student and 80 child tickets. Check: 12(160) + 8(160) + 5(80) = 1,920 + 1,280 + 400 = 3,600.
Common mistakes
| Mistake | Example of the error | Fix |
|---|---|---|
| Sign errors when subtracting a multiple of a row | Writing 1 − 2(−1) = −1 in R₂ − 2R₁ of Example 1 | Subtracting a negative adds: 1 − 2(−1) = 3. Change only the row being replaced. |
| Calling a zero row inconsistent | Saying [0 0 0 | 0] means no solution | Only [0 0 … 0 | b] with b ≠ 0 is a contradiction. A zero row just says 0 = 0. |
| Using a 0 as a pivot | Starting elimination on a matrix whose top-left entry is 0 | Swap in a row with a nonzero entry in that column first. |
| Multiplying a row by 0 | Clearing a row by 0 · R₃ → R₃ | Scaling must use a nonzero number, or the system changes. |
| Assuming infinitely many solutions means any values work | Answering “all real numbers” for Example 2 | Write the basic variables in terms of the free variables: (3 − 3t, 1 + t, t). |
Related methods
Reduced row echelon form
If you keep going after row echelon form, scaling each pivot to 1 and clearing the entries above the pivots too, you reach reduced row echelon form. That method, Gauss-Jordan elimination, is the next lesson.
Solving small systems another way
For two or three equations, substitution and elimination work too. Gaussian elimination is the same idea written as a matrix routine, which scales to large systems and to computers. For a square system with exactly one solution, Cramer’s rule also works.
Practice problems
- Is each matrix in row echelon form? A = [1 3 −2; 0 0 5; 0 0 0] and B = [1 2; 0 0; 0 4], with rows separated by semicolons.
- The augmented matrix [2 −1 4 3 | 1; 0 0 3 −1 | 2; 0 0 0 0 | 0] is in row echelon form for variables x₁, x₂, x₃, x₄. Find the pivot columns and the free variables, and say how many solutions there are.
- Solve x + y = 5, 2x − y = 1 with Gaussian elimination.
- Solve x + y + z = 6, x + 2y + 3z = 14, 2x + y + 2z = 10.
- Solve x − 2y + z = 1, 2x − 4y + 3z = 5.
- Is the system x + 2y − z = 1, 2x + 4y − 2z = 3 consistent?
- For which values of h is the system x + hy = 4, 3x + 6y = 8 consistent?
- Solve y + 2z = 9, x + y + z = 6, 2x + y + 3z = 15.
- Solve the system in echelon form x₁ + 2x₂ − x₃ + x₄ = 5, x₃ + 2x₄ = 4, 3x₄ = 6.
- A shop mixes peanuts at $3 per pound, cashews at $9 per pound and almonds at $7 per pound to make 20 pounds of mix worth $130. The mix has as many pounds of almonds as peanuts and cashews combined. How many pounds of each does it use?
Show answers
1.
A: \text{zero row at the bottom; leading entries in columns 1 and 3}Check the three conditions. The leading entry 5 is right of the leading entry 1, and the zero row is last.
B: \text{zero row above the nonzero row } [0\;\;4]A row of zeros must be below every nonzero row.
Answer: A is in row echelon form; B is not (swap rows 2 and 3 to fix it).
2.
\text{pivots: columns 1 and 3}The leading entries are the 2 in row 1 and the 3 in row 2.
\text{free: } x_2, x_4Columns 2 and 4 have no pivots.
Answer: no row [0 0 0 0 | b] with b ≠ 0, so the system is consistent; with two free variables it has infinitely many solutions.
3.
\left[\begin{array}{rr|r} 1 & 1 & 5 \\ 0 & -3 & -9 \end{array}\right]R₂ − 2R₁ → R₂: −1 − 2 = −3, 1 − 10 = −9.
-3y = -9 \Rightarrow y = 3
Solve row 2.
x + 3 = 5 \Rightarrow x = 2
Back substitute.
Answer: (2, 3)
4.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 6 \\ 0 & 1 & 2 & 8 \\ 2 & 1 & 2 & 10 \end{array}\right]R₂ − R₁ → R₂.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 6 \\ 0 & 1 & 2 & 8 \\ 0 & -1 & 0 & -2 \end{array}\right]R₃ − 2R₁ → R₃.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 6 \\ 0 & 1 & 2 & 8 \\ 0 & 0 & 2 & 6 \end{array}\right]R₃ + R₂ → R₃.
z = 3,\; y = 8 - 2(3) = 2,\; x = 6 - 2 - 3 = 1
Back substitution, from row 3 up.
Answer: (1, 2, 3)
5.
\left[\begin{array}{rrr|r} 1 & -2 & 1 & 1 \\ 0 & 0 & 1 & 3 \end{array}\right]R₂ − 2R₁ → R₂: −4 + 4 = 0, 3 − 2 = 1, 5 − 2 = 3.
z = 3,\; y = t
Column 2 has no pivot, so y is free.
x - 2t + 3 = 1 \Rightarrow x = -2 + 2t
Solve row 1.
Answer: (−2 + 2t, t, 3) for every real number t
6.
\left[\begin{array}{rrr|r} 1 & 2 & -1 & 1 \\ 0 & 0 & 0 & 1 \end{array}\right]R₂ − 2R₁ → R₂.
Answer: no. Row 2 says 0 = 1, so the system is inconsistent.
7.
\left[\begin{array}{rr|r} 1 & h & 4 \\ 0 & 6 - 3h & -4 \end{array}\right]R₂ − 3R₁ → R₂: 8 − 12 = −4.
6 - 3h = 0 \Rightarrow h = 2
Row 2 is [0 0 | −4], a contradiction, only when h = 2.
Answer: consistent for every h ≠ 2 (and then it has exactly one solution).
8.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 6 \\ 0 & 1 & 2 & 9 \\ 2 & 1 & 3 & 15 \end{array}\right]Swap R₁ and R₂, because the first entry of row 1 is 0.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 6 \\ 0 & 1 & 2 & 9 \\ 0 & -1 & 1 & 3 \end{array}\right]R₃ − 2R₁ → R₃.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 6 \\ 0 & 1 & 2 & 9 \\ 0 & 0 & 3 & 12 \end{array}\right]R₃ + R₂ → R₃.
z = 4,\; y = 9 - 2(4) = 1,\; x = 6 - 1 - 4 = 1
Back substitution.
Answer: (1, 1, 4)
9.
x_4 = 2
Solve the last equation: 3x₄ = 6.
x_3 + 2(2) = 4 \Rightarrow x_3 = 0
Back substitute into the second equation.
x_2 = t
Column 2 has no pivot, so x₂ is free.
x_1 + 2t - 0 + 2 = 5 \Rightarrow x_1 = 3 - 2t
Solve the first equation.
Answer: (3 − 2t, t, 0, 2) for every real number t
10.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 20 \\ 3 & 9 & 7 & 130 \\ -1 & -1 & 1 & 0 \end{array}\right]With p, c and a in pounds: p + c + a = 20, 3p + 9c + 7a = 130 and a − p − c = 0.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 20 \\ 0 & 6 & 4 & 70 \\ -1 & -1 & 1 & 0 \end{array}\right]R₂ − 3R₁ → R₂.
\left[\begin{array}{rrr|r} 1 & 1 & 1 & 20 \\ 0 & 6 & 4 & 70 \\ 0 & 0 & 2 & 20 \end{array}\right]R₃ + R₁ → R₃.
a = 10,\; 6c + 40 = 70 \Rightarrow c = 5,\; p = 20 - 5 - 10 = 5
Back substitution.
Answer: 5 pounds of peanuts, 5 pounds of cashews and 10 pounds of almonds
Gaussian elimination FAQ
What is the difference between Gaussian elimination and Gauss-Jordan elimination?
Gaussian elimination stops at row echelon form and finishes with back substitution. Gauss-Jordan elimination keeps going to reduced row echelon form, where each pivot is 1 with zeros above and below it, so the solution can be read directly.
How do you know if a system has no solution?
Row reduce to echelon form. If a row looks like [0 0 … 0 | b] with b ≠ 0, the system has no solution.
What is a pivot position?
It is the location of a leading entry in a row echelon form of the matrix. The pivot positions are the same for every echelon form of a given matrix.
What are free variables?
Free variables belong to columns with no pivot. They can be any number, and the basic variables are then written in terms of them, which gives infinitely many solutions.
Summary
- Use swaps, nonzero scaling and row replacement to reach row echelon form.
- Pivots are the leading entries; their columns are pivot columns.
- A pivot in the last column means no solution.
- Otherwise, no free variables means one solution, and free variables mean infinitely many.
- Finish with back substitution, from the bottom row up.
Previous course: Calculus 3 Index
Next lesson: Reduced Row Echelon Form
Back to the Linear Algebra Index