Factorization into A = LU

The inverse of a product

Unfinished business from last time: if $A$ and $B$ are both invertible, what is the inverse of $AB$? You multiply the separate inverses — but in reverse order:

The check is just moving parentheses around. In $AB \cdot B^{-1}A^{-1}$, do the middle multiplication first: $B B^{-1} = I$, then $A I A^{-1} = A A^{-1} = I$. On the other side, $B^{-1}A^{-1} \cdot AB$ — this time the inner pair $A^{-1}A$ squeezes down to the identity, and $B^{-1}B$ finishes the job.

Strang apologizes in advance for the example in the book, but it sticks: you take off your shoes, then your socks — so the way to invert that process is socks back on first, then shoes. Inverses come in reverse order.

While we’re at it, one fact about transposes, since the next lecture is full of them. Start from $AA^{-1} = I$ and transpose both sides. The identity doesn’t notice being transposed — it’s symmetric. And a product transposes in reverse order, so

$$(A^{-1})^{\mathsf{T}} A^{\mathsf{T}} = I$$

That equation answers the question “what is the inverse of $A^{\mathsf{T}}$?” — it’s sitting right there on the left:

From EA = U to A = LU

Now the main event. Elimination takes $A$ to $U$ — we know the steps. Today’s lecture is the right way to look at those steps: as a factorization $A = LU$. Strang calls this “the most basic factorization of a matrix” — and adds a worry: please don’t think this course is all elimination. It’s just the right algebra to do first. Throughout, assume the nice case: no row exchanges, all pivots fine.

Start with a $2 \times 2$. Take

$$A = \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}$$

The first pivot is $2$, so the multiplier is $4$ — and the $7$ was chosen so the matrix isn’t singular (a $4$ in that corner would have killed the second pivot). One elimination step, carried out by the elementary matrix $E_{21}$, produces $U$ in one shot:

$$\underbrace{\begin{bmatrix} 1 & 0 \\ -4 & 1 \end{bmatrix}}_{E_{21}} \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix} = \underbrace{\begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}}_{U}$$

But what Strang is shooting for is $A$ alone on one side and everything else on the other. Multiply through by $E_{21}^{-1}$ — and elimination matrices are easy to invert: the inverse of subtracting $4$ of row one is adding back $4$ of row one, so the sign just flips.

Sometimes it’s nicer to pull the pivots out into their own diagonal matrix $D$, leaving ones on both triangular diagonals. Divide row one of $U$ by $2$ and row two by $3$:

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

That balanced form is $A = LDU$. MATLAB would produce either one; Strang basically stays with $LU$.

Three by three: why L beats E

For a $2 \times 2$ this was easy — one $E$, and the only difference between $E$ and $L$ was a minus sign versus a plus sign. With $3 \times 3$ there’s a more significant difference. Elimination now takes three steps:

$$E_{32}\, E_{31}\, E_{21}\, A = U$$

first a zero in the $(2,1)$ position, then $(3,1)$, then $(3,2)$. Moving everything to the right side means inverting the whole bunch — separate inverses, opposite order:

$$A = E_{21}^{-1} E_{31}^{-1} E_{32}^{-1}\, U = LU$$

So $L$ is a product of inverses. But why prefer the inverses? Why is that product nicer than the product of the $E$‘s themselves? Strang makes the point with a typical case: suppose $E_{21}$ has multiplier $2$, suppose $E_{31}$ happens to be the identity (a zero was already sitting in the $(3,1)$ position), and $E_{32}$ has multiplier $5$. Multiply the $E$‘s in elimination order:

$$\underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -5 & 1 \end{bmatrix}}_{E_{32}} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{E_{21}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 10 & -5 & 1 \end{bmatrix}}_{E}$$

Everything above the diagonal stays zero — elimination only subtracts rows from lower rows, nothing moves upward as it did in Gauss–Jordan. But look at that $10$. Where did it come from? “I don’t like that ten,” Strang says — it’s right, but he doesn’t want it there. It appeared because two of row one got removed from row two, and then five of that new row two got removed from row three — so altogether ten of row one got thrown into row three. The multipliers interfere.

Now do it in the reverse direction, inverses in opposite order:

$$\underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{E_{21}^{-1}} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 5 & 1 \end{bmatrix}}_{E_{32}^{-1}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 5 & 1 \end{bmatrix}}_{L}$$

A happy result: the $2$ and the $5$ don’t interfere to produce any $10$. In the right order, the multipliers just sit in the matrix $L$.

The unattractive matrix is $E$, the product of elimination matrices — you can’t see what it is without multiplying. Put the inverses on the other side, in the opposite order, and $L$ comes out just right. That’s the new insight elimination gains from being done in matrix form: $EA = U$, whereas $A = LU$.

How expensive is elimination?

Today is a practical day, so a practical question: how many operations does elimination cost on an $n \times n$ matrix? Can we solve a system of order a thousand in a second, a minute, a week? Suppose there are no convenient zeros — count a multiply-and-subtract pair as one operation.

Take $n = 100$. The first stage of elimination fixes the first row and clears the first column, changing essentially every entry of the matrix — about $100^2$ operations, since $100^2$ is the total number of entries and only the insignificant first row is left alone. The second stage works on the remaining $99 \times 99$ block: about $99^2$. Then $98^2$, $97^2$, all the way down to $2^2$ and $1^2$. The big numbers come first; the problem keeps shrinking. So the total is

$$n^2 + (n-1)^2 + (n-2)^2 + \cdots + 2^2 + 1^2 \;\approx\; \tfrac{1}{3}n^3$$

Is it proportional to $n$? Certainly not. Is it $n!$ — a hundred times longer each time $n$ grows by one? No (Strang puts in “a bad mark against determinants,” where $n!$ really does show up). There are $n$ terms and the biggest is $n^2$, so the worst it could be is $n^3$ — and the shrinking brings in the factor $\tfrac{1}{3}$. Strang allows exactly one mention of calculus: summing $x^2$ is like integrating it, and $\int_1^n x^2\,dx = \tfrac{1}{3}n^3$. Calculus is like sums, except it’s continuous; algebra is discrete.

That gap is why the factorization matters in practice: pay the $\tfrac{1}{3}n^3$ price once to split $A$ into $L$ and $U$, then process every new right-hand side at the low $n^2$ cost. This is the most fundamental algorithm for a system of equations.

Permutations: allowing row exchanges

Finally, drop the nice-case assumption. When do we need row exchanges? When a zero shows up in the pivot position. The matrices that do the exchanging are permutation matrices — the identity matrix with its rows rearranged.

For $3 \times 3$ there is a nice little family of them — all six ways to rearrange the rows of $I$. The identity itself (exchanges nothing), the three single exchanges,

$$P_{12} = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad P_{13} = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}, \quad P_{23} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}$$

and the two cycles that move every row:

$$\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}, \qquad \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$$

Multiply any two of these together and the answer is on the list — doing some row exchanges and then some more row exchanges is, all together, row exchanges. Invert any one and you’re still inside the family. “Group is the right name for this subject”: the six matrices form a group.

How many $4 \times 4$ permutation matrices? Twenty-four. The next lecture puts them to work.

Problems

Work these before revealing the solutions — everything you need is in the lecture.

Problem 4.1 Inverses in reverse order

Let

$$A = \begin{bmatrix} 1 & 0 \\ 5 & 1 \end{bmatrix}, \qquad B = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}$$

Write down $A^{-1}$ and $B^{-1}$ (no computation needed — these are elimination-type matrices). Then compute $(AB)^{-1}$ using the reverse-order rule and verify it against $AB$.

Show solution

Flip the signs of the off-diagonal entries: $A^{-1} = \begin{bmatrix} 1 & 0 \\ -5 & 1 \end{bmatrix}$, $B^{-1} = \begin{bmatrix} 1 & -2 \\ 0 & 1 \end{bmatrix}$.

Reverse order:

$$(AB)^{-1} = B^{-1}A^{-1} = \begin{bmatrix} 1 & -2 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ -5 & 1 \end{bmatrix} = \begin{bmatrix} 11 & -2 \\ -5 & 1 \end{bmatrix}$$

Verify: $AB = \begin{bmatrix} 1 & 2 \\ 5 & 11 \end{bmatrix}$, and

$$\begin{bmatrix} 1 & 2 \\ 5 & 11 \end{bmatrix}\begin{bmatrix} 11 & -2 \\ -5 & 1 \end{bmatrix} = \begin{bmatrix} 11 - 10 & -2 + 2 \\ 55 - 55 & -10 + 11 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \checkmark$$

Problem 4.2 LU by hand

Factor into $A = LU$ by elimination:

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

Record the multipliers as you go, and check your factorization by multiplying $LU$ back together.

Show solution

Multiplier $\ell_{21} = 3$: subtract $3$ of row one from row two.

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

The $(3,1)$ entry is already zero, so $\ell_{31} = 0$. Multiplier $\ell_{32} = 2$: subtract $2$ of the new row two from row three.

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

The multipliers go directly into $L$:

$$L = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 2 & 1 \end{bmatrix}$$

Check row three of $LU$: $0 \cdot (1,2,1) + 2 \cdot (0,2,-2) + (0,0,5) = (0,4,1)$. ✓ Row two: $3(1,2,1) + (0,2,-2) = (3,8,1)$. ✓

Problem 4.3 Why E is worse than L

Suppose $E_{21}$ subtracts $3$ times row one from row two, $E_{31} = I$, and $E_{32}$ subtracts $4$ times row two from row three (all $3 \times 3$). Compute the product $E = E_{32}E_{21}$ and the product $L = E_{21}^{-1}E_{32}^{-1}$. Which entry of $E$ is “interference,” and why is it absent from $L$?

Show solution

$$E = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -4 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 12 & -4 & 1 \end{bmatrix}$$

The $12$ in the $(3,1)$ position is the interference: three of row one was removed from row two, then four of that new row two from row three, so twelve of row one got thrown into row three.

In reverse order with plus signs:

$$L = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 4 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 4 & 1 \end{bmatrix}$$

No $12$: in this order the multipliers $3$ and $4$ don’t interact — they just sit in their own positions. That is exactly why $A = LU$ is the preferred form: $L$ is free.

Problem 4.4 Operation counts

Elimination on a $1000 \times 1000$ matrix takes roughly how many operations? If you then need to solve $A\mathbf{x} = \mathbf{b}$ for $50$ different right-hand sides $\mathbf{b}$, roughly what does that add? Finally: if $n$ doubles, by what factor does the cost of elimination on $A$ grow?

Show solution

Cost on $A$: about $\tfrac{1}{3}n^3 = \tfrac{1}{3}(1000)^3 \approx 3.3 \times 10^8$ operations.

Each right-hand side costs about $n^2 = 10^6$ operations, so $50$ of them add about $5 \times 10^7$ — still much less than the one-time cost of factoring $A$. That’s the payoff of $A = LU$: factor once, then every new $\mathbf{b}$ is cheap.

Doubling $n$ multiplies $\tfrac{1}{3}n^3$ by $2^3 = 8$: a $2000 \times 2000$ system costs about eight times as much as a $1000 \times 1000$ one.

Problem 4.5 The permutation group

Let

$$P = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}$$

(the cycle that moves row two up to row one, row three up to row two, and row one down to row three). Find $P^{-1}$, verify that $P^{-1} = P^{\mathsf{T}}$, and say how many $5 \times 5$ permutation matrices there are.

Show solution

To undo the cycle, send each row back where it came from: row one back down to row two, row two down to row three, row three up to row one. That is the other cycle:

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

Check: $PP^{-1}$ — row one of $P$ picks out row two of $P^{-1}$, which is $(1,0,0)$; row two picks out row three, $(0,1,0)$; row three picks out row one, $(0,0,1)$. So $PP^{-1} = I$. ✓

Transposing $P$ (exchange rows and columns) gives exactly the same matrix as $P^{-1}$ above, confirming $P^{-1} = P^{\mathsf{T}}$.

The number of $n \times n$ permutation matrices is the number of ways to rearrange $n$ rows: $n!$. For $n = 5$ that is $120$.