Elimination with Matrices

Solving Ax = b the way software does

The method of solution will not be determinants — those come later. The method is elimination, “the way every software package solves equations.” Gauss thought of it before we did, Strang notes, “but only because he was born earlier.” If the matrix $A$ is a good one, elimination succeeds and gets the answer efficiently. And as long as we’re watching it work, it’s always good to ask: how could it fail? Elimination itself will decide whether the matrix is good or has problems.

The example for the whole lecture is three equations in three unknowns:

$$\begin{aligned} x + 2y + z &= 2 \\ 3x + 8y + z &= 12 \\ 4y + z &= 2 \end{aligned} \qquad A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 2 \\ 12 \\ 2 \end{bmatrix}$$

Writing the equal signs and pluses over and over gets to be a pain — “it’s that matrix that totally matters. Everything is in that matrix.” So elimination works on $A$ directly.

But the deeper agenda is the second half of the lecture: expressing elimination in matrix language. All the key ideas of the course get expressed as matrix operations, not as words.

Forward elimination: from A to U

Accept the first equation as it is. Its leading coefficient is the key number:

Step (2,1): the first pivot is the $1$ in position $(1,1)$. To knock out the $3$ below it, the multiplier is $3$: subtract $3 \times$ row one from row two. Three $2$s away from the $8$ leaves $2$; three $1$s away from $1$ leaves $-2$. Row three has a $0$ in column one already, so the $(3,1)$ step has multiplier $0$ — nothing to do (though MATLAB would still look at that entry unless told in advance it was zero):

$$\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} \;\longrightarrow\; \begin{bmatrix} \boxed{1} & 2 & 1 \\ 0 & \boxed{2} & -2 \\ 0 & 4 & 1 \end{bmatrix}$$

With $x$ eliminated, we’re down to two equations in $y$ and $z$, and “everything’s recursive” — just do it again. Step (3,2): the second pivot is the $2$, the multiplier is $2$. Subtract $2 \times$ row two from row three: $4 - 2(2) = 0$, and $1 - 2(-2) = 5$.

$$U = \begin{bmatrix} \boxed{1} & 2 & 1 \\ 0 & \boxed{2} & -2 \\ 0 & 0 & \boxed{5} \end{bmatrix}$$

This matrix is $U$ — U for upper triangular — and the whole purpose of elimination was to get from $A$ to $U$. “Literally, that’s the most common calculation in scientific computing.” Three nonzero pivots appeared, $1, 2, 5$, with no special maneuvers, so this matrix is great — invertible. And anticipating a later day: the determinant, which we never actually want, is just the product of the pivots, $1 \cdot 2 \cdot 5 = 10$.

Step through the whole computation yourself — the same matrix, one elimination move at a time, pivots boxed and changed entries highlighted:

How elimination fails

By fail, Strang means: fail to come up with three pivots. Run the example again with unlucky numbers.

• Trouble at the start. If the $(1,1)$ entry had been $0$, there’d be no first pivot in place. Do we quit? No — exchange rows with a lower equation that has a nonzero there. Strang refuses the phrase “zero pivot”: there may be a $0$ in the pivot position, but a pivot is never zero.
• Temporary failure. If the $8$ had been a $6$, the second row after step one would read $0 \; 0 \; -2$ — a $0$ where the second pivot should be. But there’s a $4$ below it, so a row exchange rescues us. You can get out of trouble whenever there’s a nonzero below the troublesome zero.
• Complete failure. What entry in the $(3,3)$ spot would be unfixable? The $1$ became a $5$ because elimination added $4$ to it. If that $1$ had been $-4$, the same steps would produce a $0$ in the third pivot position at the last minute — with nothing below it to exchange. No third pivot. The matrix would not be invertible.

So elimination itself is the test: temporary failure means a row exchange; complete failure — a zero in the pivot position with nothing below — means a singular matrix.

Back substitution: the augmented matrix

Now the right-hand side, which has been patiently waiting. (MATLAB actually finishes the left side first, then goes back for the right.) Tack $\mathbf{b}$ on as an extra column:

$$\left[\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 3 & 8 & 1 & 12 \\ 0 & 4 & 1 & 2 \end{array}\right] \longrightarrow \left[\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 0 & 2 & -2 & 6 \\ 0 & 4 & 1 & 2 \end{array}\right] \longrightarrow \left[\begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 0 & 2 & -2 & 6 \\ 0 & 0 & 5 & -10 \end{array}\right]$$

Step one: three $2$s taken from $12$ leaves $6$. Step two: two $6$s taken from $2$ leaves $-10$. Call the final column $\mathbf{c}$, “once and forever”: $\mathbf{c}$ is what happens to $\mathbf{b}$, just as $U$ is what happens to $A$. The system is now $U\mathbf{x} = \mathbf{c}$:

$$\begin{aligned} x + 2y + z &= 2 \\ 2y - 2z &= 6 \\ 5z &= -10 \end{aligned}$$

Back substitution solves these in reverse order, because the system is triangular. From the last equation, $z = -2$. Go back upwards: $2y - 2(-2) = 6$ gives $2y + 4 = 6$, so $y = 1$. Then $x + 2(1) + (-2) = 2$ gives $x = 2$. That’s the whole solve: forward elimination, then the easy triangular sweep.

Matrices that act on rows

Now the second piece of the lecture: express those elimination operations as matrices. First, a point Strang singles out as especially important. Last time, the big picture was columns: a matrix times a vector is a combination of the columns —

$$\begin{bmatrix} \; & \; & \; \\ \; & A & \; \\ \; & \; & \; \end{bmatrix} \begin{bmatrix} 3 \\ 4 \\ 5 \end{bmatrix} = 3(\text{column 1}) + 4(\text{column 2}) + 5(\text{column 3})$$

But elimination is row operations, so we need the parallel fact for rows.

Elimination matrices: E₂₁ and E₃₂

So: what matrix subtracts $3 \times$ row one from row two and leaves the other rows alone? Build it row by row. The first row of the answer should be one of row one and nothing else: $1\; 0\; 0$. The last row: $0\; 0\; 1$. (If the middle row were $0\; 1\; 0$ we’d have the identity matrix $I$, which does absolutely nothing — “it’s like a one, like the number one, for matrices.”) But we want $-3$ of row one plus $1$ of row two:

$$E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \qquad E_{21}\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$$

This is an elementary matrix (or elimination matrix), “E for elementary,” indexed $2,1$ because it fixes the $(2,1)$ position. Check one entry the entry-at-a-time way: the $(2,3)$ entry of the product is row two of $E_{21}$ dotted with column three of $A$ — $(-3)(1) + (1)(1) + (0)(1) = -2$. It works.

The second step subtracted $2 \times$ row two from row three, so its matrix is $I$ with $-2$ — minus the multiplier — sitting in the $(3,2)$ position:

$$E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix}, \qquad E_{32}\,(E_{21} A) = U$$

That one line is the whole lecture — “you see why I like matrix notation.”

Permutations, and a first look at inverses

One more type of elementary matrix, the one row exchanges need: a permutation matrix. To exchange the rows of $\begin{bmatrix} a & b \\ c & d \end{bmatrix}$, exchange the rows of the identity and multiply on the left:

$$P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, \qquad \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} a & b \\ c & d \end{bmatrix} = \begin{bmatrix} c & d \\ a & b \end{bmatrix}$$

Could a matrix on the left exchange the columns? No — multiplying on the left does row operations. To exchange columns, put the permutation on the right: $\begin{bmatrix} a & b \\ c & d \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} b & a \\ d & c \end{bmatrix}$, one column at a time. In short: column operations multiply on the right, row operations on the left — and elimination is row operations.

Rather than multiplying out $E_{32}E_{21}$, Strang closes with the better way, “a little jump on what’s coming on Monday”: think not how to get from $A$ to $U$, but how to get from $U$ back to $A$. What matrix undoes $E_{21}$? In words first: if the step subtracted $3 \times$ row one from row two, the inverse step adds it back:

$$E^{-1}E = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = I$$

The matrix that multiplies $E$ to give the identity is the inverse, written $E^{-1}$. Every matrix on the board today has one — “I didn’t write any bad matrices down.”

Problems

Elimination by hand, then elimination as matrices — everything comes from the lecture’s example.

Problem 2.1 Elimination and back substitution

Solve by elimination and back substitution, keeping the right-hand side along as an augmented column:

$$\begin{aligned} x + 3y + z &= 5 \\ 2x + 7y + 5z &= 16 \\ 2y + 6z &= 10 \end{aligned}$$

Box the three pivots.

Show solution

Augmented matrix, then step $(2,1)$ with multiplier $2$, then step $(3,2)$ with multiplier $2$:

$$\left[\begin{array}{ccc|c} 1 & 3 & 1 & 5 \\ 2 & 7 & 5 & 16 \\ 0 & 2 & 6 & 10 \end{array}\right] \longrightarrow \left[\begin{array}{ccc|c} 1 & 3 & 1 & 5 \\ 0 & 1 & 3 & 6 \\ 0 & 2 & 6 & 10 \end{array}\right] \longrightarrow \left[\begin{array}{ccc|c} \boxed{1} & 3 & 1 & 5 \\ 0 & \boxed{1} & 3 & 6 \\ 0 & 0 & \boxed{0} & -2 \end{array}\right]$$

Trouble! The third pivot position is $0$ with nothing below — and the equation reads $0z = -2$, which is impossible. This system has no solution: elimination exposed a singular case. (If the last right-hand entry had been $12$ instead of $10$, we’d get $0 = 0$ and infinitely many solutions — but that story comes later. The point here: elimination itself delivers the verdict.)

Problem 2.2 Which entry causes failure?

For the matrix

$$A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & c \end{bmatrix}$$

(the lecture’s matrix with the corner entry replaced by $c$), which value of $c$ produces complete failure — no third pivot and no rescue by row exchange? For that $c$, write out $U$.

Show solution

Elimination proceeds as in lecture: after the $(2,1)$ step with multiplier $3$, rows are $1\;2\;1$, $0\;2\;-2$, $0\;4\;c$. The $(3,2)$ step subtracts $2 \times$ row two from row three: the corner becomes $c - 2(-2) = c + 4$.

This is $0$ when $c = -4$ — exactly the number Strang identified. Then

$$U = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 0 \end{bmatrix}$$

Only two pivots, a $0$ in the third pivot position, and no row below to exchange with: the matrix is not invertible.

Problem 2.3 Elimination as matrices

For the system in the lecture, with $A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix}$, multiply out $E = E_{32}E_{21}$ — the single matrix that does all of elimination in one shot. Verify that $EA = U$.

Show solution

$$E = E_{32}E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 6 & -2 & 1 \end{bmatrix}$$

(Row three of $E$ is $-2$ of row two of $E_{21}$ plus $1$ of row three: $-2(-3, 1, 0) + (0, 0, 1) = (6, -2, 1)$.)

Check $EA$ row by row: row one of $EA$ is row one of $A$: $1\;2\;1$. Row two is $-3(\text{row 1}) + (\text{row 2}) = 0\;2\;-2$. Row three is $6(\text{row 1}) - 2(\text{row 2}) + (\text{row 3}) = (6 - 6 + 0,\; 12 - 16 + 4,\; 6 - 2 + 1) = 0\;0\;5$. So $EA = U$ with pivots $1, 2, 5$. By the associative law, $(E_{32}E_{21})A = E_{32}(E_{21}A)$ — the same $U$ either way.

Problem 2.4 Left vs right multiplication

Let $P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ and $B = \begin{bmatrix} 1 & 4 \\ 2 & 9 \end{bmatrix}$. Compute $PB$ and $BP$. Which one exchanges rows and which exchanges columns? Is $PB = BP$?

Show solution

$$PB = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 1 & 4 \\ 2 & 9 \end{bmatrix} = \begin{bmatrix} 2 & 9 \\ 1 & 4 \end{bmatrix}, \qquad BP = \begin{bmatrix} 1 & 4 \\ 2 & 9 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 4 & 1 \\ 9 & 2 \end{bmatrix}$$

$P$ on the left does a row operation — it exchanges the rows of $B$. $P$ on the right does a column operation — it exchanges the columns. And $PB \neq BP$: a concrete reminder that the commutative law is false for matrices.

Problem 2.5 Undoing a step

Write the elementary matrix $E$ that subtracts $5$ times row one from row three of a 3×3 matrix. Then write $E^{-1}$, say in words what it does, and verify $E^{-1}E = I$.

Show solution

$$E = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -5 & 0 & 1 \end{bmatrix}, \qquad E^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 5 & 0 & 1 \end{bmatrix}$$

In words: what $E$ subtracted away, $E^{-1}$ adds back — it adds $5$ times row one to row three. Check the product row by row: rows one and two of $E^{-1}E$ are rows one and two of $E$, i.e. $1\;0\;0$ and $0\;1\;0$. Row three is $5(\text{row 1 of } E) + (\text{row 3 of } E) = (5, 0, 0) + (-5, 0, 1) = (0, 0, 1)$. So

$$E^{-1}E = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = I$$