Home All Subjects Progress Videos Graphics

Progress

241 / 241 subjects

Phases

Math graphic
📐 Concept diagram

09-01 — LU Decomposition

Phase: 9 — Matrix Decompositions & Advanced Linear Algebra Subject: 09-01 Prerequisites: Phase 8 (Linear Algebra) — matrices, Gaussian elimination, row operations, matrix multiplication Next subject: 09-02 — QR Decomposition

Learning Objectives

  1. Express Gaussian elimination as a matrix factorization $A = LU$
  2. Describe the structure of lower-triangular (L) and upper-triangular (U) factors and how multipliers from elimination populate L
  3. Apply forward substitution and backward substitution to solve $Ax = b$ after computing LU
  4. Explain when partial pivoting is necessary and how $PA = LU$ extends the decomposition
  5. Identify applications of LU decomposition including determinant computation, matrix inversion, and solving multiple right-hand sides

Core Content

LU decomposition factors a square matrix A into the product $A = LU$, where L is a unit lower-triangular matrix (1s on the diagonal) and U is an upper-triangular matrix. It is the algebraic encapsulation of Gaussian elimination.

CRITICAL -- Foundational: LU decomposition is Gaussian elimination as matrix multiplication. Factorize once O(n^3), solve each system O(n^2). Every numerical library uses LU under the hood.

1. Gaussian Elimination as Factorization

Consider a 3×3 system. In Gaussian elimination, we subtract multiples of the pivot row from rows below to zero out subdiagonal entries. Each step corresponds to multiplying A on the left by an elementary elimination matrix.

For step 1 (zero out below a_{11}), define the multiplier m_{i1} = a_{i1} / a_{11} for $i = 2, 3, ..., n$. The elementary matrix $E_1$ has the form:

$E_1 = I - m_1 e_1^T
$

where $m_1 = [0, m_{21}, m_{31}, ..., m_{n1}]^T$ and $e_1$ is the first unit vector. Applying $E_1$ to A zeros out entries in column 1 below the diagonal.

After $n-1$ such steps:

$E_{n-1} ... E_2 E_1 A = U
$

Since each E_k is invertible (add the multiple back):

$A = E_1^{-1} E_2^{-1} ... E_{n-1}^{-1} U
$

The key insight: E_k^{-1} simply flips the sign of the off-diagonal entries:

$E_k^{-1} = I + m_k e_k^T
$

And the product L = E_1^{-1} E_2^{-1} ... E_{n-1}^{-1} is a unit lower-triangular matrix where column k below the diagonal contains the multipliers m_{ik} from step k. The multipliers nest perfectly without fill-in because each E_k^{-1} is simply added to the identity.

Algebraic derivation: For a 3×3 matrix:

$A = [a11 a12 a13]
    [a21 a22 a23]
    [a31 a32 a33]
$

Step 1: m_{21} = a_{21}/a_{11}, m_{31} = a_{31}/a_{11}

$E_1 = [ 1   0  0]      E_1^{-1} = [1   0  0]
      [-m21 1  0]                 [m21 1  0]
      [-m31 0  1]                 [m31 0  1]
$

After $E_1$:

$A^{(1)} = [a11  a12   a13 ]
          [ 0   a22'  a23']
          [ 0   a32'  a33']
$

Step 2: $m_{32} = a_{32}' / a_{22}'$

$E_2 = [1  0   0]       E_2^{-1} = [1  0  0]
      [0  1   0]                  [0  1  0]
      [0 -m32 1]                  [0 m32 1]
$

Then:

$E_2 E_1 A = U   =>   A = E_1^{-1} E_2^{-1} U = LU
$
$L = [1    0   0]      U = [a11  a12   a13 ]
    [m21  1   0]          [ 0   a22'  a23']
    [m31 m32  1]          [ 0    0    a33'']
$

2. Solving Ax = b with LU

Once we have $A = LU$, solving $Ax = b$ becomes a two-step process:

Step 1: Forward substitution — Solve $Ly = b$ for y.

Since L is lower-triangular with 1s on the diagonal:

$y_1 = b_1
y_2 = b_2 - L_{21} y_1
y_3 = b_3 - L_{31} y_1 - L_{32} y_2
...
y_i = b_i - sum_{j=1}^{i-1} L_{ij} y_j
$

Step 2: Backward substitution — Solve $Ux = y$ for x.

Since U is upper-triangular:

x_n = y_n / U_{nn}
x_{n-1} = (y_{n-1} - U_{n-1,n} x_n) / U_{n-1,n-1}
...
x_i = (y_i - sum_{j=i+1}^{n} U_{ij} x_j) / U_{ii}

Edge case: If any $U_{ii} = 0$, backward substitution fails — U is singular (and so is A).

The advantage of LU decomposition: if you need to solve $Ax = b$ for many different b vectors, you compute the LU factorization once (O(n³)) and then each solve costs only O(n²).

3. When Decomposition Fails and PA = LU

LU decomposition fails when a pivot (diagonal entry of the current submatrix) is zero. This happens even for invertible matrices. For example:

$A = [0 1]
    [1 0]
$

Here $a_{11} = 0$, so we cannot form m_{21}. However, A is invertible (det = -1). The fix: partial pivoting — swap rows to bring a nonzero entry to the pivot position.

Common Pitfall: LU without pivoting can fail even for invertible matrices. PA = LU works for EVERY invertible matrix. Always use pivoting for stability.

This is captured by the decomposition $PA = LU$, where P is a permutation matrix. The algorithm:

  1. At step k, find the largest absolute value in column k at or below row k
  2. Swap rows to bring it to the pivot position (record in P)
  3. Proceed with elimination

Key property: The permutation matrix P is orthogonal: $P^{-1} = P^T$.

For the example above:

$P = [0 1]    PA = [1 0]     L = [1 0]    U = [1 0]
    [1 0]         [0 1]         [0 1]        [0 1]
$

PA = LU = A (identity). So $A = P^T LU$.

4. Computational Complexity and Efficiency

5. Applications

Computing the determinant:

det(A) = det(P^{-1}) · det(L) · det(U) = (-1)^{#swaps} · 1 · ∏_{i=1}^{n} U_{ii}

Matrix inversion: Solve $A x_j = e_j$ for each column j of the identity matrix. LU decomposition lets you solve all n systems efficiently.

Common misconceptions: - LU decomposition is NOT unique in general (but unique if we require L to have 1s on diagonal) - Not every matrix has an LU decomposition (need nonzero leading principal minors), but every invertible matrix has a PA = LU - Symmetric matrices don't necessarily have symmetric LU factors (that's LDL^T or Cholesky)

Key Terms

Worked Examples

Example 1: Basic 3×3 LU Decomposition

Find the LU decomposition of:

$A = [2  1  1]
    [4 -6  0]
    [-2 7  2]
$

Solution:

Step 1: Zero out below $a_{11} = 2$. Multipliers: $m_{21} = 4/2 = 2$, $m_{31} = -2/2 = -1$

$Row2 ← Row2 - 2·Row1: [4, -6, 0] - 2[2, 1, 1] = [0, -8, -2]
Row3 ← Row3 - (-1)·Row1 = Row3 + Row1: [-2, 7, 2] + [2, 1, 1] = [0, 8, 3]
$
$A^{(1)} = [2  1   1]
          [0 -8  -2]
          [0  8   3]
$

Step 2: Zero out below $a_{22}' = -8$. Multiplier: $m_{32} = 8/(-8) = -1$

$Row3 ← Row3 - (-1)·Row2 = Row3 + Row2: [0, 8, 3] + [0, -8, -2] = [0, 0, 1]
$
$U = [2  1   1]
    [0 -8  -2]
    [0  0   1]

L = [1   0  0]
    [2   1  0]
    [-1 -1  1]
$

Verify: $LU = [[2,1,1],[4,-6,0],[-2,7,2]] = A$ ✓

Example 2: Solving with LU Decomposition

Solve $Ax = b$ where $b = [5, -2, 9]^T$ using the LU from Example 1.

Forward substitution (Ly = b):

$y_1 = 5
y_2 = b_2 - L_{21} y_1 = -2 - 2(5) = -12
y_3 = b_3 - L_{31} y_1 - L_{32} y_2 = 9 - (-1)(5) - (-1)(-12) = 9 + 5 - 12 = 2
$

So $y = [5, -12, 2]^T$.

Backward substitution (Ux = y):

$x_3 = y_3 / U_{33} = 2/1 = 2
x_2 = (y_2 - U_{23} x_3) / U_{22} = (-12 - (-2)(2)) / (-8) = (-12 + 4)/(-8) = 1
x_1 = (y_1 - U_{12} x_2 - U_{13} x_3) / U_{11}
    = (5 - 1(1) - 1(2)) / 2 = (5 - 1 - 2)/2 = 1
$

So $x = [1, 1, 2]^T$.

Verify: $A[1,1,2]^T = [2+1+2, 4-6+0, -2+7+4]^T = [5,-2,9]^T$ ✓

Example 3: PA = LU with Pivoting

$A = [1  2  3]
    [2  4  5]
    [3  5  6]
$

Step 1: Pivot column 1. Max(|1|, |2|, |3|) = 3 at row 3. Swap rows 1 and 3.

$P = [0 0 1]    After swap: [3  5  6]
    [0 1 0]                [2  4  5]
    [1 0 0]                [1  2  3]
$

Multipliers: $m_{21} = 2/3$, $m_{31} = 1/3$

After elimination:

$[3    5      6   ]
[0  4-10/3  5-4 ] = [0  2/3  1  ]
[0  2-5/3   3-2 ]   [0  1/3  1  ]
$

Step 2: Pivot column 2. Max(|2/3|, |1/3|) = 2/3 at row 2. No swap needed.

Multiplier: $m_{32} = (1/3)/(2/3) = 1/2$

After elimination:

$U = [3    5    6  ]
    [0   2/3   1  ]
    [0    0   1/2 ]
$
$L = [  1    0  0]     P = [0 0 1]
    [ 2/3   1  0]         [0 1 0]
    [ 1/3 1/2 1]         [1 0 0]
$

Verify: $PA = [[3,5,6],[2,4,5],[1,2,3]]$. $LU = [[3,5,6],[2,4,5],[1,2,3]]$ ✓

Quiz

Q1: What does the concept of End-of-Subject Quiz primarily refer to in this subject?

A) A visual representation of End-of-Subject Quiz B) A computational error related to End-of-Subject Quiz C) The definition and application of End-of-Subject Quiz D) A historical anecdote about End-of-Subject Quiz

Correct: C)

Q2: What is the primary purpose of LU decomposition?

A) It is used only in advanced research contexts B) It replaces all other methods in this domain C) It is primarily a historical notation system D) It is used to lu decomposition in mathematical analysis

Correct: D)

Q3: Which statement about Common Pitfalls is TRUE?

A) Common Pitfalls is not related to this subject B) Common Pitfalls is an advanced topic beyond this subject's scope C) Common Pitfalls is a fundamental concept covered in this subject D) Common Pitfalls is mentioned only as a historical footnote

Correct: C)

Q4: Based on the worked examples in this subject, what is the correct result?

A) b.** B) An unrelated numerical value C) A different result from a common mistake D) The inverse of the correct answer

Correct: A)

Practice Problems

  1. Compute the LU decomposition of $A = [[3, 1], [6, -2]]$. Verify $LU = A$.

  2. Solve $Ax = b$ for $A = [[1, 2, 3], [2, 5, 7], [3, 7, 13]]$ and $b = [1, 3, 3]^T$ by first computing $A = LU$ and then using forward/backward substitution.

  3. Show that the matrix $A = [[0, 1], [1, 0]]$ has no LU decomposition but has a PA = LU decomposition. Compute P, L, U.

  4. Use LU decomposition to compute $det(A)$ for $A = [[2, -1, 1], [4, 1, -1], [-2, 5, 3]]$.

  5. For which values of $α$ does $A = [[α, 1], [1, α]]$ fail to have an LU decomposition? Hint: check when the first pivot is zero.

  6. Given $A = LU$ where $L = [[1,0],[2,1]]$ and $U = [[3,5],[0,-1]]$, solve $Ax = [4, 3]^T$ in two steps.

Answers 1. `L = [[1,0],[2,1]]`, `U = [[3,1],[0,-4]]` 2. First compute LU: Step 1: `m_{21}=2, m_{31}=3`. `U^{(1)} = [[1,2,3],[0,1,1],[0,1,4]]` Step 2: `m_{32}=1`. `U = [[1,2,3],[0,1,1],[0,0,3]]` `L = [[1,0,0],[2,1,0],[3,1,1]]` Forward: `y = [1, 1, -1]^T` Backward: `x = [2, 2/3, -1/3]^T` 3. First pivot is zero, so naive LU fails. With pivot: `P = [[0,1],[1,0]]`, `PA = [[1,0],[0,1]]` so `L = I`, `U = I`. Then `PA = LU = I`, so `A = P^T LU`. 4. `det(A) = U_{11} · U_{22} · U_{33}`. After LU: `U_{11}=2, U_{22}=3, U_{33}=4`. So `det(A) = 24`. 5. When `α = 0`, first pivot is zero, so LU fails. `α = 0` is the only problematic case since the leading principal minor of size 1 is `α`. 6. Forward: `y = [4, -5]^T`. Backward: `x = [3, 5]^T`.

Summary

Pitfalls

  1. Attempting LU without pivoting on matrices with zero pivots. A zero on the diagonal during elimination does not mean the matrix is singular — it means you need row swaps. Always use PA = LU (partial pivoting) for robustness, especially in numerical code.

  2. Solving Ly = b in the wrong order. Forward substitution with a lower-triangular L goes top-to-bottom: y₁ depends only on b₁, then y₂ depends on y₁, etc. Attempting bottom-to-top (which is correct for backward substitution with U) gives wrong results.

  3. Forgetting to account for row swaps when computing det(A). For PA = LU, det(A) = det(P⁻¹)·det(L)·det(U) = (−1)^(#swaps)·∏ U_{ii}. Omitting the sign from row swaps is a common mistake that gives the wrong determinant.

  4. Building L incorrectly after pivoting. When row swaps occur, the multipliers m_{ik} must also be swapped to keep L unit lower-triangular. Simply copying multipliers without tracking permutations produces an incorrect L.

  5. Expecting symmetric LU factors for symmetric matrices. A symmetric matrix does NOT generally have L = U^T in an LU decomposition. For symmetric positive definite matrices, use Cholesky decomposition (A = LL^T) instead. For indefinite symmetric matrices, use LDL^T decomposition.

Next Steps

Continue to 09-02 QR Decomposition to learn about orthogonal factorization, Gram-Schmidt, Householder reflections, and their applications to least squares and eigenvalue problems.