Pivots and back substitution: clear the columns, then solve from the bottom up
Slide 2 removed one unknown from two equations. With three equations and three unknowns we repeat that step in a fixed order: one column at a time, from left to right. The first pivot, the top-left number, clears everything below it in column 1. The second pivot clears column 2. Now the system is a triangle, and the last equation has just one unknown. Solve it, and its value is the key to the equation above, which in turn unlocks the one above that. Climbing back up like this is back substitution.
Lesson 2 · slide 3Pivots- Elimination works column by column, from left to right.
- Each multiplier uses the current pivot, after the earlier steps.
- The result is an upper triangular matrix U: zeros below the diagonal (the entries U₁₁, U₂₂, U₃₃, from top-left to bottom-right). The diagonal entries are the pivots.
- Back substitution solves the last row first, then moves up one row at a time.
From two equations to three
Bigger systems need nothing new. We repeat slide 2's step in a fixed order. Take
As on slide 2, we work on the augmented matrix [A | b]. Its first row 211|5 means 2x + y + z = 5: numbers in front of x, y and z, then the bar, then the right side. Every step acts on the whole row, bar included. Change only the left side and you get a different system.
ℓᵢⱼ is the multiplier that clears row i, column j.
Column 1
The first pivot is the 2 in the top-left corner. Below it we clear the 4 and the −2:
- ℓ₂₁ = 4 ÷ 2 = 2. Subtract 2 times row 1 from row 2: 4−60|−2 − 2·211|5 = 0−8−2|−12.
- ℓ₃₁ = −2 ÷ 2 = −1. Subtract −1 times row 1 from row 3, which means adding row 1: −272|9 + 211|5 = 083|14.
Column 2
Row 2 now starts 0, −8. The second pivot is −8. It clears the 8 below: ℓ₃₂ = 8 ÷ (−8) = −1, so add row 2 to row 3: 083|14 + 0−8−2|−12 = 001|2.
Use the pivot as it is now (−8), not the −6 that sat there at the start. This is the most common mistake by hand.
The triangle
The new right side, c, is b after the same steps. Ux = c has the same solution as Ax = b.
U is upper triangular, with the pivots on its diagonal. A pivot can't be zero, because we divide by it. Slide 4 covers what happens when one is.
Back substitution: a chain of keys
The last equation has one unknown. Its value is the key to the equation above, and so on up to the top.
Computers solve systems with thousands of unknowns in exactly this order: clear column 1, then column 2, and so on, then back substitution from the bottom row up.
Next: Every pivot here was a nonzero number. What if a 0 lands in a pivot position? Slide 4 shows when a row swap fixes it, and when the system has no single answer.
Examples
Example 1 · A full 3 by 3 solve
Solve x + y + z = 3, x + 2y + 2z = 5, x + 2y + 3z = 6.
Show solutionHide solution
The pivots are 1, 1, 1.
Example 2 · Back substitution on its own
Solve Ux = c with U = 213012004 and c = 948.
Show solutionHide solution
Example 3 · Check the answer
Back substitution gave x = 1, y = 1, z = 2. Put them back into the three equations 2x + y + z = 5, 4x − 6y = −2 and −2x + 7y + 2z = 9. Every one must come out right:
Show solutionHide solution
Always check this way. One small slip in elimination shows up here at once.
Example 4
Solve x + 2y + z = 4, 2x + 5y + z = 8, 3x + 7y + 4z = 14.
Show solutionHide solution
ℓ₂₁ = 2: (0, 1, −1 | 0). ℓ₃₁ = 3: (0, 1, 1 | 2). ℓ₃₂ = 1: (0, 0, 2 | 2).
z = 1, then y − 1 = 0 so y = 1, then x + 2 + 1 = 4 so x = 1.
Example 5
Find the pivots of A = 120251013.
Show solutionHide solution
ℓ₂₁ = 2 gives row 2 = 011. ℓ₃₁ = 0, since that entry is already 0. ℓ₃₂ = 1 gives row 3 = 002. The pivots are 1, 1 and 2. None is zero, so elimination works without a row swap.
Questions and comments
Stuck on something, or found a mistake? Ask here and I'll answer. You sign in with GitHub.