LU Factorization
Chapter 2 • Section 2-7
"Breaking up is hard to do... unless you're a matrix! 💔"
🧩 The Factorization
An LU Factorization of a matrix $A$ writes it as the product of two simpler matrices:
L (Lower Triangular)
Zeros above the diagonal. Often has 1s on the diagonal.
U (Upper Triangular)
Zeros below the diagonal. This is usually the Row Echelon Form of $A$.
Why do we care?
Solving $A\vec{x} = \vec{b}$ becomes two easy steps:
- Solve $L\vec{y} = \vec{b}$ for $\vec{y}$ (Forward Substitution).
- Solve $U\vec{x} = \vec{y}$ for $\vec{x}$ (Back Substitution).
Existence Condition
An invertible matrix $A$ has an LU factorization if and only if it can be reduced to row echelon form without row swaps.
If row swaps are needed, we need a Permutation Matrix $P$, giving $PA = LU$.
👀 Spot the L Win $10
Which of these is a Lower Triangular matrix?
Finding L and U
We can find $L$ and $U$ by performing Gaussian Elimination, but keeping track of our steps.
Start with $L = I$ and $U = A$.
Perform row operations to reduce $U$ to Row Echelon Form.
For every operation $R_i \leftarrow R_i - k R_j$, place the multiplier $k$ into $L$ at position $(i, j)$.
🧪 Interactive Demo
Let's factor $A = \begin{bmatrix} 2 & 4 \\ 1 & 3 \end{bmatrix}$.
Step 1: Initialization
L
$$ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$U (initially A)
$$ \begin{bmatrix} 2 & 4 \\ 1 & 3 \end{bmatrix} $$🧠 Logic Check Win $20
When does LU factorization fail?