LU Decomposition

An LU decomposition writes a square matrix A as A = LU, where L is lower triangular with 1s on its diagonal and U is upper triangular. U is the echelon form from Gaussian elimination, and L stores the multipliers used. To solve Ax = b, solve Ly = b by forward substitution, then Ux = y by back substitution.

Before this lesson: Gaussian Elimination, Elementary Matrices and Invertible Matrix Theorem

Why factor a matrix?

Gaussian elimination does most of its work on A, not on b. If you must solve Ax = b for many different right-hand sides b, repeating the elimination each time wastes effort. An LU decomposition does the elimination once and saves the result.

A matrix is lower triangular if every entry above the main diagonal is 0, and upper triangular if every entry below it is 0. Triangular systems are easy: you can solve them one variable at a time, from the top down for L or from the bottom up for U.

How LU decomposition works

Suppose A can be reduced to echelon form U using only row replacements of the form Rᵢ − mRⱼ → Rᵢ with j less than i (no row swaps and no scaling). Each step is an elementary matrix Eₖ that is lower triangular, so

E_k \cdots E_2 E_1 A = U \quad\Longrightarrow\quad A = (E_k \cdots E_1)^{-1}U = LU

The inverse of each Eₖ adds back what Eₖ subtracted, so L = E₁⁻¹⋯Eₖ⁻¹ is also lower triangular. Better still, no multiplication is needed: the multiplier m from the step Rᵢ − mRⱼ → Rᵢ goes straight into row i, column j of L.

L = \begin{bmatrix} 1 & 0 & 0 \\ m_{21} & 1 & 0 \\ m_{31} & m_{32} & 1 \end{bmatrix}

How to find an LU decomposition

1. Reduce A to echelon form U using only steps Rᵢ − mRⱼ → Rᵢ, working down one column at a time. Each multiplier is m = (entry to remove) ÷ (pivot above it).
2. Record each multiplier m in row i, column j of L. Put 1s on the diagonal of L and 0s above it.
3. Check that LU = A by multiplying.
4. To solve Ax = b, solve Ly = b from the top down (forward substitution), then Ux = y from the bottom up (back substitution).

If a 0 shows up in a pivot position, elimination needs a row swap and A has no LU decomposition in this form. Then one uses PA = LU, where P is a permutation matrix that does the swaps first.

LU decomposition examples

Example 1: A 2 × 2 matrix

Find the LU decomposition of A = [2 3; 4 7] (rows separated by semicolons).

m_{21} = \dfrac{4}{2} = 2

\begin{bmatrix} 2 & 3 \\ 4 & 7 \end{bmatrix} \to \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix} = U

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

LU = \begin{bmatrix} 1(2) + 0(0) & 1(3) + 0(1) \\ 2(2) + 1(0) & 2(3) + 1(1) \end{bmatrix} = \begin{bmatrix} 2 & 3 \\ 4 & 7 \end{bmatrix}

Answer: L = [1 0; 2 1] and U = [2 3; 0 1].

Example 2: A 3 × 3 matrix

Find the LU decomposition of A = [2 1 1; 4 3 3; −2 1 4].

m_{21} = \dfrac{4}{2} = 2,\quad m_{31} = \dfrac{-2}{2} = -1

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

\to \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 2 & 5 \end{bmatrix}

m_{32} = \dfrac{2}{1} = 2

\to \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 3 \end{bmatrix} = U

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

\text{row 3 of } LU = -1(2, 1, 1) + 2(0, 1, 1) + 1(0, 0, 3) = (-2, 1, 4)

Answer: L = [1 0 0; 2 1 0; −1 2 1] and U = [2 1 1; 0 1 1; 0 0 3]. Rows 1 and 2 of LU also match A: (2, 1, 1) and 2(2, 1, 1) + (0, 1, 1) = (4, 3, 3).

Example 3: Solve a system with the factorization

Use the LU decomposition from Example 2 to solve Ax = b for b = (5, 13, 4).

y_1 = 5

2(5) + y_2 = 13 \Rightarrow y_2 = 3

-1(5) + 2(3) + y_3 = 4 \Rightarrow y_3 = 3

3x_3 = 3 \Rightarrow x_3 = 1

x_2 + 1 = 3 \Rightarrow x_2 = 2

2x_1 + 2 + 1 = 5 \Rightarrow x_1 = 1

Answer: x = (1, 2, 1). Check in A: (2 + 2 + 1, 4 + 6 + 3, −2 + 2 + 4) = (5, 13, 4).

Example 4: A matrix with no LU decomposition

Show that A = [0 2; 3 1] has no LU decomposition, and fix it with a row swap.

\begin{bmatrix} 1 & 0 \\ \ell & 1 \end{bmatrix}\begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix} = \begin{bmatrix} u_{11} & u_{12} \\ \ell u_{11} & \ell u_{12} + u_{22} \end{bmatrix}

u_{11} = 0

\ell u_{11} = \ell(0) = 0 \ne 3

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

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

Answer: A has no LU decomposition because its first pivot is 0, even though A is invertible (det A = −6). With the swap, PA = LU with L = I and U = [3 1; 0 2].

Example 5: The same matrix, many right-hand sides

A workshop makes two products, X and Y. Each X needs 2 hours on machine 1 and 4 hours on machine 2; each Y needs 3 hours and 7 hours. In week 1 the machines have 18 and 40 hours available; in week 2, 13 and 29 hours. How many of each product use all the hours each week?

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

y_1 = 18,\quad 2(18) + y_2 = 40 \Rightarrow y_2 = 4

x_2 = 4,\quad 2x_1 + 3(4) = 18 \Rightarrow x_1 = 3

y_1 = 13,\quad 2(13) + y_2 = 29 \Rightarrow y_2 = 3

x_2 = 3,\quad 2x_1 + 3(3) = 13 \Rightarrow x_1 = 2

Answer: week 1, make 3 X and 4 Y (check: 2(3) + 3(4) = 18 and 4(3) + 7(4) = 40); week 2, make 2 X and 3 Y (check: 4 + 9 = 13 and 8 + 21 = 29). The elimination was done once and reused.

Common mistakes

Related ideas

Why LU saves time. Finding L and U for an n × n matrix takes about ⅔n³ arithmetic operations, but each later solve with forward and back substitution takes only about 2n². For a large matrix and many right-hand sides, that is far less work than repeating elimination or computing A⁻¹.

Determinants from LU. Since det L = 1, det A = det U, the product of the pivots on the diagonal of U. In Example 2, det A = 2 · 1 · 3 = 6. See the determinant of a matrix lesson for other methods; Cofactor Expansion begins the next unit. Partial pivoting, which swaps rows to avoid small pivots and rounding errors, is part of Numerical Methods.

Practice problems

1. Find the LU decomposition of A = [1 2; 3 8].
2. Find the LU decomposition of A = [4 −2; 2 5].
3. Solve Ly = b by forward substitution, where L = [1 0 0; 2 1 0; −3 4 1] and b = (2, 7, 1).
4. Solve Ux = y by back substitution, where U = [2 −1 3; 0 1 2; 0 0 4] and y = (9, 4, 8).
5. Find the LU decomposition of A = [1 2 0; 3 7 2; −2 −2 5].
6. Use your answer to Problem 5 to solve Ax = b for b = (3, 12, 1).
7. L = [1 0; −2 1] and U = [3 1; 0 4]. Find A = LU.
8. Does A = [0 1; 1 1] have an LU decomposition without row swaps? If not, find P with PA = LU.
9. Use the LU decomposition from Problem 5 to find det A.
10. The workshop in Example 5 has 11 hours on machine 1 and 25 hours on machine 2 in week 3. How many of each product use all the hours?

m_{21} = \dfrac{3}{1} = 3

\begin{bmatrix} 1 & 2 \\ 3 & 8 \end{bmatrix} \to \begin{bmatrix} 1 & 2 \\ 0 & 2 \end{bmatrix}

m_{21} = \dfrac{2}{4} = \dfrac{1}{2}

\begin{bmatrix} 4 & -2 \\ 2 & 5 \end{bmatrix} \to \begin{bmatrix} 4 & -2 \\ 0 & 6 \end{bmatrix}

y_1 = 2

2(2) + y_2 = 7 \Rightarrow y_2 = 3

-3(2) + 4(3) + y_3 = 1 \Rightarrow y_3 = -5

4x_3 = 8 \Rightarrow x_3 = 2

x_2 + 2(2) = 4 \Rightarrow x_2 = 0

2x_1 - 0 + 3(2) = 9 \Rightarrow 2x_1 = 3

x_1 = \dfrac{3}{2}

m_{21} = 3,\quad m_{31} = \dfrac{-2}{1} = -2

\to \begin{bmatrix} 1 & 2 & 0 \\ 0 & 1 & 2 \\ -2 & -2 & 5 \end{bmatrix}

\to \begin{bmatrix} 1 & 2 & 0 \\ 0 & 1 & 2 \\ 0 & 2 & 5 \end{bmatrix}

\to \begin{bmatrix} 1 & 2 & 0 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix}

y_1 = 3

3(3) + y_2 = 12 \Rightarrow y_2 = 3

-2(3) + 2(3) + y_3 = 1 \Rightarrow y_3 = 1

x_3 = 1

x_2 + 2(1) = 3 \Rightarrow x_2 = 1

x_1 + 2(1) + 0 = 3 \Rightarrow x_1 = 1

LU = \begin{bmatrix} 1(3) + 0(0) & 1(1) + 0(4) \\ -2(3) + 1(0) & -2(1) + 1(4) \end{bmatrix}

= \begin{bmatrix} 3 & 1 \\ -6 & 2 \end{bmatrix}

a_{11} = 0 = u_{11}

P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix},\; PA = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}

\det A = \det L \cdot \det U

= 1 \cdot (1 \cdot 1 \cdot 1) = 1

y_1 = 11,\quad 2(11) + y_2 = 25 \Rightarrow y_2 = 3

x_2 = 3,\quad 2x_1 + 3(3) = 11 \Rightarrow x_1 = 1

LU decomposition FAQ

What is LU decomposition used for?

It solves Ax = b quickly for many different b with the same A, because the elimination is done once. It also gives det A as the product of the pivots in U.

Does every matrix have an LU decomposition?

No. If a zero pivot appears and a row swap is needed, A has no LU decomposition in this form. Every invertible matrix does have one after reordering its rows, written PA = LU.

Is LU decomposition the same as Gaussian elimination?

It is Gaussian elimination with a record kept. U is the echelon form that elimination produces, and L stores the multipliers so the same steps can be applied to any b later.

What is the difference between forward and back substitution?

Forward substitution solves a lower triangular system from the first equation down. Back substitution solves an upper triangular system from the last equation up.

Summary

• A = LU, where L is lower triangular with 1s on the diagonal and U is the echelon form of A.
• The multiplier m from Rᵢ − mRⱼ → Rᵢ goes in row i, column j of L.
• To solve Ax = b: forward substitution for Ly = b, then back substitution for Ux = y.
• If elimination needs a row swap, use PA = LU instead.
• det A is the product of the diagonal entries of U.

Previous lesson: Invertible Matrix Theorem

Next lesson: Cofactor Expansion

Back to the Linear Algebra Index