Linear Algebra › Section B · Matrix algebra › Topic B.5

Matrix factorizations and LU

Factoring a number such as 12 = 3 × 4 reveals its structure. Factoring a matrix does the same, and the LU factorisation, which records the work of row reduction, is how computers actually solve most square linear systems.

Why factor a matrix?

A factorisation writes a matrix as a product of two or more simpler matrices. Many problems need the same coefficient matrix with a long list of right-hand sides: a bridge model tested under hundreds of different loads, or a circuit driven by many input signals. Row reducing \([A \ \mathbf{b}]\) from scratch each time repeats almost identical work. The LU factorisation does the hard part of elimination once, stores it in two triangular matrices, and then handles each new \(\mathbf{b}\) cheaply.

What A = LU means

Suppose \(A\) is \(m \times n\) and can be row reduced to echelon form without swapping rows. Then \(A = LU\), where \(U\) is an \(m \times n\) echelon form of \(A\) and \(L\) is an \(m \times m\) unit lower triangular matrix: zeros above the diagonal and 1s on it. For a square \(A\), \(U\) is upper triangular. The letters stand for lower and upper. Because \(L\) has 1s on its diagonal it is always invertible, and the entries below its diagonal hold the multipliers used in elimination.

Solving with the two factors

Given \(A = LU\), the equation \(A\mathbf{x} = \mathbf{b}\) becomes \(L(U\mathbf{x}) = \mathbf{b}\). Write \(\mathbf{y} = U\mathbf{x}\) and solve it as a pair:

L\mathbf{y} = \mathbf{b}, \qquad U\mathbf{x} = \mathbf{y}

The first is solved by forward substitution, top equation first, since row 1 of \(L\) involves only \(y_1\). The second is solved by back substitution, bottom equation first. Both are triangular systems, so each step uses one new unknown and no elimination is needed.

Finding L and U

Reduce \(A\) to echelon form using only row replacements that add a multiple of one row to a row below it. That gives \(U\). Each time you subtract \(\ell\) times row \(j\) from row \(i\), put \(\ell\) in position \((i, j)\) of \(L\). In matrix language, the operations are elementary matrices with \(E_p \cdots E_1A = U\), so \(A = (E_p \cdots E_1)^{-1}U\) and \(L = (E_p \cdots E_1)^{-1}\). Each \(E_k\) is unit lower triangular, and so are products and inverses of such matrices, which is why \(L\) has that shape.

Worked example: factoring a 3 × 3 matrix

Factor the matrix \(A\) with rows (2, 1, 1), (4, 5, 3) and (−2, 5, 4). 1. Row 2 minus 2 times row 1 gives (0, 3, 1); multiplier 2 goes in position (2, 1). 2. Row 3 minus (−1) times row 1, that is row 3 plus row 1, gives (0, 6, 5); multiplier −1 goes in position (3, 1). 3. Row 3 minus 2 times the new row 2 gives (0, 0, 3); multiplier 2 goes in position (3, 2). So

L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 2 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 3 & 1 \\ 0 & 0 & 3 \end{bmatrix}

4. Check row 3 of \(LU\), which should be row 3 of \(A\):

-1(2, 1, 1) + 2(0, 3, 1) + 1(0, 0, 3) = (-2, 5, 4)

Worked example: solving with the factors

Use the factors above to solve \(A\mathbf{x} = \mathbf{b}\) with \(\mathbf{b} = (5, 17, 12)\). 1. Forward substitution in \(L\mathbf{y} = \mathbf{b}\): \(y_1 = 5\), then \(2y_1 + y_2 = 17\) gives \(y_2 = 7\), then \(-y_1 + 2y_2 + y_3 = 12\) gives \(y_3 = 12 + 5 - 14 = 3\). 2. Back substitution in \(U\mathbf{x} = \mathbf{y}\): \(3x_3 = 3\) gives \(x_3 = 1\); \(3x_2 + x_3 = 7\) gives \(x_2 = 2\); \(2x_1 + x_2 + x_3 = 5\) gives \(x_1 = 1\). 3. Check in \(A\): row 2 gives \(4 + 10 + 3 = 17\) and row 3 gives \(-2 + 10 + 4 = 12\). A new right-hand side would need only steps 1 and 2 again.

Counting the cost

For an \(n \times n\) matrix, computing \(L\) and \(U\) takes about \(n^3/3\) multiplications, and about as many additions. After that, the two triangular solves for each right-hand side together take about \(n^2\) multiplications. For \(n = 1{,}000\), factoring costs roughly 333 million multiplications, but each further \(\mathbf{b}\) costs only about a million. Computing \(A^{-1}\) instead would take roughly three times the work of the factorisation and is usually less accurate, which is why software solves with LU rather than with the inverse.

When rows must be swapped

Not every matrix has an LU factorisation as described. The matrix with rows (0, 1) and (1, 0) has a zero in the first pivot position, and no row replacement can fix that. Software also swaps rows on purpose, choosing the entry of largest size in each column as the pivot to limit rounding error; this is called partial pivoting. With swaps included, the factorisation becomes \(PA = LU\), where \(P\) is a permutation matrix: the identity with its rows reordered. Standard libraries such as LAPACK compute this form for general square systems.

Common mistakes to avoid

First, getting the sign of a multiplier wrong: if you subtract 2 times row 1, store \(+2\) in \(L\), not \(-2\). Second, scaling rows to make pivots equal to 1 while building \(U\); that breaks the unit diagonal of \(L\). Third, solving \(U\mathbf{x} = \mathbf{b}\) directly, skipping the forward step with \(L\). Fourth, using the old row 2 instead of the updated one when eliminating below it. Fifth, assuming every matrix has an LU factorisation without row swaps.

Key takeaways

When A can be reduced to echelon form with downward row replacements only, A = LU, with L unit lower triangular and U an echelon form. Each multiplier ℓ used in subtracting ℓ times row j from row i is stored in position (i, j) of L. To solve Ax = b, first solve Ly = b by forward substitution, then Ux = y by back substitution. Factoring costs about n³/3 multiplications once; each new right-hand side costs about n². When a pivot is zero, or for accuracy, rows are swapped and the factorisation becomes PA = LU with a permutation matrix P.

Flashcards

Flashcard

Matrix factorisation

Writing a matrix as a product of simpler matrices

Like 12 = 3 × 4 for numbers.

Test your understanding

Question 1 of 5

The matrix A has rows (3, 1) and (6, 5). Which matrix is L in its LU factorisation?

Question 2 of 5

L has rows (1, 0) and (3, 1), and b = (2, 10). What is the solution y of Ly = b?

Question 3 of 5

An engineer must solve Ax = b for 500 different vectors b with the same 1,000 × 1,000 matrix A. What is the best plan?

Question 4 of 5

Which of these matrices has no LU factorisation unless rows are swapped?

Question 5 of 5

Once A = LU is known for a 1,000 × 1,000 matrix, roughly how many multiplications does each new right-hand side cost?

← Previous topicNext topic →