Week 3: Elimination and LU Factorization

You eliminate a $3 \times 3$ system and the last row reads $0 = 1$. You look for the two parallel planes that must cause it, and there are none. The usual picture of "no solution" is wrong for three planes, and elimination shows why.

Before you move anything, commit to an answer.

Each translucent sheet is one row of $[A \mid b]$, the thin dark lines are where two planes cross, and the dot is where all three meet. Slide $t$ from $0$ to $3$ to run elimination one step at a time. The point does not move. Then set $a_{33}$ to $7$ and change $b_3$ between $2$ and $1$.

Elimination on the scene's system#

The scene opens on the first $[A \mid b]$ below. Gaussian elimination uses each pivot to clear the entries under it. Pivot $2$ gives multipliers $\ell_{21} = 2$ and $\ell_{31} = 4$. Then pivot $1$ gives $\ell_{32} = 3$:

Back-substitution gives $x_3 = 1$, $x_2 = -2$ and $x_1 = 1$.

Why the point stays. Row 2 becomes row 2 − 2 × row 1. Any $x$ on planes 1 and 2 satisfies that combination, so the new plane 2 swings about the line where the old planes 1 and 2 crossed. Adding $2 \times$ row 1 back undoes the step, so no point is gained either. The original planes are only $7°$ to $18°$ apart and read as one thick sheet. The planes of $U$ are $45°$ to $66°$ apart. Elimination does not move the answer. It makes the answer legible.

Elimination as matrices, and A = LU#

Subtracting $\ell$ times row $j$ from row $i$ is left-multiplication by $E_{ij}$, the identity with $-\ell$ at $(i, j)$. So $EA = U$ with $E = E_{32}E_{31}E_{21}$. Each $E_{ij}$ is undone by $+\ell$, so $E$ is invertible: the algebra of "the point stays".

$L = E^{-1}$ is unit lower triangular and holds the multipliers below its diagonal. That is the LULower-Upper (matrix factorization) factorization $A = LU$:

Factoring costs $O(n^3)$ once. Each new $b$ then costs a forward solve $Ly = b$ and a back solve $Ux = y$, about $n^2$ operations. With no row exchanges, $\det A$ is the product of the pivots, here $2$.

When a pivot is zero#

Keep the first two rows and let $a_{33} = a$ vary. Elimination gives a third pivot of $a - 7$ and a third right side of $b_3 - 1$, so

Rows 1 and 2 never change, so the point slides along their crossing line as $a$ nears $7$. At $a = 7$ plane 3 turns parallel to that line, and the left side of row 3 is $-2 \times$ row 1 $+ 3 \times$ row 2. The right side decides:

• $b_3 = 1$: row 3 reduces to $0 = 0$, and the planes share the line through $(1, -1, 0)$ along $(0, -1, 1)$.
• $b_3 \ne 1$: row 3 reads $0 = b_3 - 1$, and the three crossing lines are parallel.

Neither case needs parallel planes. Strang's instructor manual (5th ed., Problem Set 2.2, Problem 20) puts it this way: "No parallel planes but still no solution. The three planes in the row picture form a triangular tunnel."

A zero pivot with a nonzero entry below it is a different problem. The matrix is fine and the rows are in the wrong order. Exchange them with a permutation matrix $P$ and factor $PA = LU$. Libraries always pick the largest entry below (partial pivoting), so their $L$ and $U$ can differ from yours and still be correct.

Knowledge Check#

Browser lab: elimination on the scene's system#

Run plain elimination (no pivoting) on the scene's matrix for any $a_{33}$ and $b_3$, then read the last row.

import numpy as np

def eliminate(a33, b3):
    M = np.array([[2., 1., 1., 1.],
                  [4., 3., 3., 1.],
                  [8., 7., a33, b3]])
    L = np.eye(3)
    for k in range(2):
        for i in range(k + 1, 3):
            L[i, k] = M[i, k] / M[k, k]
            M[i] -= L[i, k] * M[k]
    return L, M

L, M = eliminate(8, 2)
U, c = M[:, :3], M[:, 3]
print("L =\n", L)
print("U =\n", U, "\nc =", c)
print("pivots:", np.diag(U), " LU == A:", np.allclose(L @ U, [[2, 1, 1], [4, 3, 3], [8, 7, 8]]))
print("x =", np.linalg.solve(U, c))

for a33, b3 in [(7.5, 2), (7, 2), (7, 1)]:
    _, M = eliminate(a33, b3)
    print(f"a33 = {a33}, b3 = {b3}: last row {M[2].round(3)}")

It prints pivots $2$, $1$, $1$ and $x = (1, -2, 1)$, then last rows $[0, 0, 0.5 \mid 1]$, $[0, 0, 0 \mid 1]$ and $[0, 0, 0 \mid 0]$: one point, no point, a line. Match each to the scene at $t = 3$.

Key takeaways#

Elimination replaces a plane with another plane through the same crossing line, so the solution never moves. The multipliers fill $L$ and the result is $U$, with $A = LU$. A zero last pivot makes $A$ singular without any parallel planes: the last row of $U$ reads $0 = 0$ for a common line, or $0 =$ nonzero for a triangular tunnel.

Further reading#

• Gilbert Strang, Introduction to Linear Algebra (6th ed., Wellesley-Cambridge Press, 2023), Chapter 2. Elimination, the row picture and $A = LU$.
• Gilbert Strang, Introduction to Linear Algebra, 5th ed.: Manual for Instructors, Problem Sets 2.1 and 2.2. The triangular tunnel.
• Lloyd N. Trefethen & David Bau, Numerical Linear Algebra (SIAM, 1997), Lectures 20–21. $LU$ with partial pivoting.