4. Factorization into A = LU

Overview

Gilbert Strang derives the inverse-product and transpose-inverse rules, then uses them to express Gaussian elimination without row exchanges as A = LU. The lecture shows how elimination multipliers fill the unit lower-triangular L, estimates dense elimination at about one-third of n cubed operations and each additional right-hand side at n squared, and introduces permutation matrices for row exchanges.

Key takeaways

The inverse of a product reverses its factors: (AB)⁻¹ = B⁻¹A⁻¹; likewise, (Aᵀ)⁻¹ = (A⁻¹)ᵀ.
When elimination requires no row exchanges, A = LU, where U is upper triangular and L is unit lower triangular with the elimination multipliers below its diagonal.
The reversed order of inverse elimination matrices is essential: it prevents multipliers from interacting and yields the clean lower-triangular L.
Dense Gaussian elimination requires approximately n³/3 multiply-and-subtract updates, giving cubic scaling with matrix dimension.
Once A is factored into L and U, each additional right-hand-side vector costs about n² operations rather than another cubic factorization.
Permutation matrices encode row exchanges; an n-by-n permutation matrix is formed by rearranging identity-matrix rows, and its inverse equals its transpose.

Chapters

0:00 Why the Inverse of AB Reverses the Factor Order

For invertible A and B, the inverse of AB is B⁻¹A⁻¹, not A⁻¹B⁻¹.
Associativity lets the middle factors B and B⁻¹ cancel, followed by A and A⁻¹.
Strang illustrates reversal with the order of putting socks and shoes back on.

4:00 Transposing a Matrix Also Reverses Product Order

Transposing AA⁻¹ = I gives (A⁻¹)ᵀAᵀ = I because the identity matrix is unchanged by transposition.
The inverse of Aᵀ is (A⁻¹)ᵀ, so inversion and transposition can be performed in either order for one matrix.
The transpose-of-a-product rule reverses factor order, just as the inverse-of-a-product rule does.

6:40 From Gaussian Elimination to the A = LU Factorization

Elimination transforms A into upper-triangular U; Strang seeks a matrix relationship that recovers A from U.
For the initial derivation, he assumes no row exchanges and no zero pivots.
The factorization A = LU is presented as a basic matrix description of elimination, with L lower triangular and U upper triangular.

8:30 A 2-by-2 Example Builds L from an Elimination Multiplier

Strang uses A = [[2, 1], [8, 7]] and eliminates the 8 with multiplier 4, producing U = [[2, 1], [0, 3]].
The elimination matrix E₂₁ = [[1, 0], [-4, 1]] satisfies EA = U.
Moving E₂₁ to the other side requires its inverse, giving L = E₂₁⁻¹ = [[1, 0], [4, 1]].
L has diagonal entries 1, while U carries the pivots 2 and 3; alternatively, the pivots can be separated into a diagonal matrix.

14:00 Why Reversing Elimination Matrices Produces a Clean L

For a 3-by-3 matrix, elimination uses E₂₁, E₃₁, and E₃₂ to clear entries below successive pivots.
Since EA = U for the combined elimination operations, recovering A uses the inverses in reverse order.
If the first elimination subtracts 2 times row 1 from row 2 and the next subtracts 5 times row 2 from row 3, multiplying the original elimination matrices creates an unwanted 10 entry.
The reversed product of inverse elimination matrices avoids that interaction and places the multipliers in their corresponding positions in L.

23:00 Store Each Elimination Multiplier Directly in L

With no row exchanges, the multipliers used to eliminate entries go directly into L below its diagonal.
During elimination, save the resulting rows of U and the multipliers for L; once saved, the original entries of A are no longer needed.
The product of elimination matrices is less useful to inspect than the reversed product of their inverses, which forms L in the desired triangular structure.

26:30 Dense Gaussian Elimination Costs About One-Third n Cubed Operations

For a dense n-by-n matrix, the successive elimination stages work on shrinking trailing blocks, approximately n-by-n, then (n−1)-by-(n−1), down to 1-by-1.
The rough operation count is n² + (n−1)² + … + 1².
That sum grows as approximately n³/3, so doubling n increases the dominant work by about a factor of eight.
Strang counts a multiply-and-subtract update as one combined operation for the rough estimate; counting multiplication and subtraction separately changes the constant, not the cubic growth.

38:00 Reuse LU for Multiple Right-Hand Sides at n Squared Cost Each

Factoring A into L and U incurs the main cost, approximately n³/3 for a dense matrix.
Afterward, carrying one right-hand-side vector b through elimination and back substitution costs about n² operations.
When several right-hand sides share the same A, the LU factorization is reused and each additional vector can be solved much more cheaply.

40:19 Permutation Matrices Represent Row Exchanges

A zero in a pivot position can require a row exchange, so the no-exchange factorization needs to be extended with permutation matrices.
For 3-by-3 matrices, rearranging the rows of the identity produces 6 permutation matrices, including the identity, pairwise swaps, and two three-row cycles.
Multiplying permutation matrices composes row exchanges, and their inverses undo them; the inverse of a permutation matrix is its transpose.
There are 4! = 24 permutation matrices of size 4-by-4, setting up their use in the next lecture.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, MIT OpenCourseWare.