LU
Decomposition
Learn how to factor any square matrix into the product of a lower triangular and an upper triangular matrix: the key to solving systems efficiently.
Linear Algebra
What is LU Decomposition?
LU Decomposition is a method of factoring a square matrix \( A \) into two simpler matrices:
$$ A = LU $$
L : Lower Triangular
All entries above the main diagonal are zero. Diagonal entries are all \( 1 \).
U : Upper Triangular
All entries below the main diagonal are zero. Contains the pivots from elimination.
Structure of L and U
Why LU Decomposition Matters
Once you have \( A = LU \), solving \( Ax = b \) becomes two easy steps instead of one hard one:
1
Forward substitution: Solve \( Ly = b \) for \( y \). Since \( L \) is lower triangular, start from the top row.
2
Back substitution: Solve \( Ux = y \) for \( x \). Since \( U \) is upper triangular, start from the bottom row.
Connection to Gaussian Elimination
LU Decomposition is Gaussian elimination in disguise. Each elementary row operation has a corresponding elementary matrix \( E \).
$$ E_k \cdots E_2 E_1 A = U $$
Rearranging:
$$ A = E_1^{-1} E_2^{-1} \cdots E_k^{-1} U = LU $$
The LU Factorization Theorem
Existence
LU exists when all leading principal minors of \( A \) are nonzero (no zero pivots encountered).
Uniqueness
If \( A \) is invertible and \( L \) has 1s on its diagonal, then the factorization \( A = LU \) is unique.
LU vs PLU Decomposition
When a zero pivot appears, a row swap is needed. This is captured by a permutation matrix \( P \):
$$ PA = LU $$
| LU | PLU | |
|---|---|---|
| Row swaps needed? | No | Yes |
| Formula | \( A = LU \) | \( PA = LU \) |
| Always exists? | Not always | Yes, for any invertible \( A \) |
| Extra matrix | None | \( P \) (permutation) |
How to Find L and U
1
Start with \( A \). Initialize \( L \) as the identity matrix \( I \).
2
Eliminate below each pivot. For each column \( j \), compute multiplier: \( \ell_{ij} = \frac{a_{ij}}{a_{jj}} \).
3
Record the multiplier. Place \( \ell_{ij} \) in position \( (i, j) \) of \( L \).
4
Perform the row operation: \( R_i \leftarrow R_i - \ell_{ij} R_j \) on the working matrix.
5
Repeat for every column. The final working matrix is \( U \).
Example 1: \( 2 \times 2 \) Matrix
Find the LU decomposition of:
$$ A = \begin{bmatrix} 2 & 6 \\ 1 & 8 \end{bmatrix} $$
1
Multiplier: \( \ell_{21} = \dfrac{1}{2} \)
2
Row operation: \( R_2 \leftarrow R_2 - \tfrac{1}{2}R_1 \): row 2 becomes \( [0,\, 5] \)
$$ L = \begin{bmatrix} 1 & 0 \\ \frac{1}{2} & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & 6 \\ 0 & 5 \end{bmatrix} $$
Example 2: \( 3 \times 3 \) Matrix
Find the LU decomposition of:
$$ A = \begin{bmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{bmatrix} $$
1
Column 1 multipliers: \( \ell_{21} = \frac{4}{2} = 2 \), \( \ell_{31} = \frac{8}{2} = 4 \)
2
Eliminate column 1: \( R_2 \leftarrow R_2 - 2R_1 \to [0,\,1,\,1] \), \( R_3 \leftarrow R_3 - 4R_1 \to [0,\,3,\,5] \)
3
Column 2 multiplier: \( \ell_{32} = \frac{3}{1} = 3 \). Then \( R_3 \leftarrow R_3 - 3R_2 \to [0,\,0,\,2] \)
Example 2: Result
$$ L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 4 & 3 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{bmatrix} $$
Solving \( Ax = b \) with LU
Using our \( 3 \times 3 \) example, solve \( Ax = b \) where \( b = \begin{bmatrix}1\\1\\3\end{bmatrix} \).
1
Forward solve \( Ly = b \):
\( y_1 = 1 \), then \( y_2 = 1 - 2(1) = -1 \), then \( y_3 = 3 - 4(1) - 3(-1) = 2 \)
2
Back solve \( Ux = y \):
\( 2x_3 = 2 \Rightarrow x_3 = 1 \), then \( x_2 = -1 - 1 = -2 \), then \( x_1 = \frac{1 - 1 - (-2)}{2} = 1 \)
$$ x = \begin{bmatrix} 1 \\ -2 \\ 1 \end{bmatrix} $$
Efficiency of LU Decomposition
Factoring \( A = LU \)
\( \sim \frac{2}{3}n^3 \) operations: done once.
Each \( Ax = b \) Solve
\( \sim 2n^2 \) operations: forward + back substitution.
Without LU
\( \sim \frac{2}{3}n^3 \) operations every time you solve a new \( b \).
Real-World Applications
Engineering
Structural analysis, circuit simulation: same stiffness/admittance matrix, many load vectors.
Determinants
\( \det(A) = \det(L)\det(U) = \prod u_{ii} \). Just multiply the pivots!
Inverses
Solve \( Ax_i = e_i \) for each column of \( A^{-1} \), reusing the same LU factorization.
Common Mistakes
✕ Wrong multiplier sign
The multiplier \( \ell_{ij} \) is stored without a negative sign in \( L \). The subtraction happens in the row operation, not in \( L \).
✕ Forgetting to update all entries
When eliminating below a pivot, you must update every entry in the row: not just the entry being zeroed out.
✕ Ignoring zero pivots
If a pivot is zero, plain LU fails. You need to use PLU (partial pivoting) instead.
Summary at a Glance
| Concept | Key Fact |
|---|---|
| Factorization | \( A = LU \) |
| \( L \) structure | Lower triangular, 1s on diagonal |
| \( U \) structure | Upper triangular (row echelon form) |
| Entries of \( L \) | Multipliers from elimination |
| Solving \( Ax = b \) | \( Ly = b \) then \( Ux = y \) |
| Factoring cost | \( \sim \frac{2}{3}n^3 \) |
| Each solve cost | \( \sim 2n^2 \) |
| Row swaps needed? | Use \( PA = LU \) |
Question 1 of 5
In the LU decomposition \( A = LU \), what is always true about the diagonal entries of \( L \)?
In the standard (Doolittle) LU decomposition, \( L \) is a unit lower triangular matrix: all diagonal entries are \( 1 \). The pivots appear on the diagonal of \( U \).
Question 2 of 5
If \( A = LU \) and \( U = \begin{bmatrix}3 & 1\\0 & 4\end{bmatrix} \), what is \( \det(A) \)?
Since \( \det(L) = 1 \) (product of 1s on diagonal), we get \( \det(A) = \det(L)\det(U) = 1 \cdot (3 \times 4) = 12 \).
Question 3 of 5
To eliminate the entry below the pivot in column 1 of \( A = \begin{bmatrix}4 & 2\\6 & 5\end{bmatrix} \), what multiplier \( \ell_{21} \) do you use?
The multiplier is \( \ell_{21} = \frac{a_{21}}{a_{11}} = \frac{6}{4} = \frac{3}{2} \). Remember: the multiplier is stored positive in \( L \); the subtraction is done in the row operation.
Question 4 of 5
When does a matrix \( A \) require a permutation matrix \( P \) (i.e., PLU instead of LU)?
A zero pivot means you cannot continue elimination without swapping rows. The permutation matrix \( P \) records these row swaps, giving \( PA = LU \).
Question 5 of 5
What is the main computational advantage of using LU decomposition to solve multiple systems \( Ax = b_1, Ax = b_2, \ldots \)?
Factoring costs \( \sim \frac{2}{3}n^3 \) and is done once. Each subsequent solve (forward + back substitution) costs only \( \sim 2n^2 \), saving enormous computation when many right-hand sides are involved.