LU Matrix Factorisation

1 Introduction

LU matrix factorisation involves decomposing a matrix A into a product A = LU so that L is a lower triangular matrix and U is an upper triangular matrix [1], i.e., for a 3 × 3 matrix we would have:

This can be useful for solving systems of equations because we are then able to use back-substitution on systems represented by U and L.

For a system of equations, Ax = b, after we find U and L, we solve Ly = b for y and then Ux = y for x. This works because according to operations in linear algebra, we have:

Substituting A = LU , Substituting y = Ux,

Ax = b

LUx = b

Ly = b

2 Method for decomposing A

Using Eq.(1), we can see that when L is multiplied by U, the first entry in the first row of the resulting matrix will simply be l11u11 .  In fact the entire first row will just be l11  multiplied by the first row in U .  The entries along the diagonal of either L or U can be chosen to be 1, so that the remaining values are automatically determined. Hence the steps are (if we set the diagonal of L to 1):

1.  Set lii = 1 for i = 1, . . . ,n.

2.  Obtain u1j  = a1j, for j = 1, . . . ,n, (based on multiplying the first row of L by columns in U)

3.  Obtain l21 = a21 /u11  (completing row 2 of L)

4.  Obtain u2j  = a2j  − u1jl21  for j = 2, . . . ,n (completing row 2 of U)

5.  Continue this way, completing each row of L by multiplying by the (now) completed columns of U, and then using multiplication and rearrangement to determine the values of U from A and L.

3 Worked example

We can demonstrate the method on a 3 × 3 matrix with

A =  l 」

「 1       5     7

1. We first set lii = 1 for all i. Hence we currently have,

l 」      l」  l」

2. Now the first row of U can be set to be the same as the first row of A.

l 」      l」  l」

1      5     7          l31     l32     1     0     0     u33

3.  Based on multiplying the second row of L by the first column of U, we should have 8l21  = −9, hence l21 = −9/8.

4. Then we can obtain the remaining entries along the second row of U . We have

(−9/8)(2) + u22 = −1  → u22 = 5/4

(−9/8)(1) + u23 = 6  → u23 = 57/8

and hence we have now completed our entries as follows.

l 」      l 」  l」

5.  Continuing on, we know that 8l31  = 1, hence l31  = 1/8.  Then multiplying the third row of L by the second column of U we have

(1/8)(2) + (5/4)l32 = 5  → l32 = 19/5

and so we can now obtain the last entry in u33  as

(1/8)(1) + (19/5)(57/8) + u33 = 7  → u33 = −101/5

completing our LU factorisation.

l 」      l 」  l   」

4 Can it always be applied?

LU factorisation can be applied to square matrices, with A, L and U all being n × n. However in some cases, the standard approach to LU factorisation can fail, e.g.  in the case of the following example adapted from [2].

For A = [1(0)   0(1)], the LU factorisation following our above procedure would require u1 1 = 0 at Step 2.

This means that the matrix U will have a column of zeros and hence a determinant of zero (i.e., it will be singular). However we know that |A| = |L||U| and so this is not possible since A has a determinant of -1. However it is noted both here and in other sources, e.g.  [3], that this issue can be circumvented by allowing for permutations. Corollary 3 in [2] in fact verifies that any n × n can be decomposed if permutations are allowed.  In terms of solving a system, this would still us to obtain solutions since permutations simply rearrange the order of the equations we use (not affecting the problem) for row permutations, or relabel our variables in the case of column permutations.