Zero pivots: swap rows, or the system is singular
Slides 2 and 3 divided by each pivot to get the multipliers. But you can't divide by zero. So what if a 0 lands in a pivot position? Think of a relay race where the runner for the next leg is missing. If a teammate further down the list can run it, you swap the order and carry on: that is a row exchange. If nobody can, the race stops, and the matrix is called singular. Then Ax = b has no solution or infinitely many, and the right side b decides which.
Lesson 2 · slide 4Zero pivots- A zero in a pivot position stops elimination, because we cannot divide by it.
- Temporary failure: a row below has a nonzero entry in that column. Exchange the rows and continue.
- Permanent failure: no row can help. The matrix is singular: no solution or infinitely many.
- Singular means the columns are dependent: one column is a combination of the others. With two columns, one is a multiple of the other (lesson 1).
A temporary failure
Same equations, new order, same solution.
Two permanent failures
- No solution. x − 2y = 1 and 2x − 4y = 11. Subtracting 2 times the first leaves 0 = 9. Impossible: the lines are parallel.
- Infinitely many solutions. x − 2y = 1 and 2x − 4y = 2. Subtracting leaves 0 = 0. The second equation adds nothing, so every point on the line x − 2y = 1 works.
Both times, subtracting 2 times equation 1 leaves 0x + 0y on the left (0x + 0y = 9, or 0x + 0y = 0). The second pivot, the y coefficient, is 0, and there is no row below to swap in. The left sides are the same: columns 12 and −2−4, the second −2 times the first. Dependent columns: they lie on one line, lesson 1's dependent case. The right side only picks which failure we get.
A bigger example: a zero pivot in a 3 × 3
Clear column 1 with ℓ₂₁ = 2 and ℓ₃₁ = 1. Row 2 becomes 001|1: its x and its y both disappeared, so the second pivot spot holds 0. Row 3 becomes 011|2, with a 1 in that spot. Swap rows 2 and 3, and the triangle is done: z = 1, then y + 1 = 2 gives y = 1, then x + 2 + 1 = 4 gives x = 1.
Solvers with thousands of unknowns check every pivot spot like this, and swap rows when it helps.
Small pivots are dangerous too
A computer keeps about 16 significant digits. Dividing by a tiny pivot like 0.0000001 makes huge multipliers and blows up rounding errors. So real solvers, NumPy's included, swap rows at every step to put the entry largest in absolute value in the pivot position. This is called partial pivoting.
Next: So far each step was written in words: "subtract ℓ times row 1 from row 2". Slide 5 writes each step as a matrix, so the whole elimination becomes one product.
Examples
Example 1 · A swap fixes it
0x + y = 2 and x + y = 3.
Show solutionHide solution
Example 2 · Infinitely many solutions
x + y = 2 and 2x + 2y = 4.
Show solutionHide solution
Every point 2 − tt is a solution: the whole line.
Example 3 · A zero pivot in the middle of a 3 by 3
A = 111112123.
Show solutionHide solution
A temporary breakdown: after the swap there are three nonzero pivots, so Ax = b has exactly one solution for every b. Whatever b is, back substitution can always divide by each nonzero pivot, so it never gets stuck.
Example 4
For which b does x − y = 1, 3x − 3y = b have a solution? How many?
Show solutionHide solution
ℓ = 3 leaves 0 = b − 3. Only b = 3 works, and then there are infinitely many solutions (x = 1 + y for any y).
Example 5
For which k is kx + y = 1, x + ky = 1 singular? What happens in each case?
Show solutionHide solution
For k ≠ 0, ℓ = 1 ÷ k. Subtract: (x + ky) − (1/k)(kx + y) = 1 − 1/k gives (k − 1/k)y = 1 − 1/k. So the second pivot is k − 1/k = (k² − 1)/k. It is zero for k = 1 or k = −1. (For k = 0, swapping the rows fixes the first pivot.)
k = 1: both equations are x + y = 1, the same line, infinitely many solutions. k = −1: −x + y = 1 and x − y = 1 are parallel, no solution.
Questions and comments
Stuck on something, or found a mistake? Ask here and I'll answer. You sign in with GitHub.