Chapter 5

Some Factorizations

5.1 LU Factorization

An LU factorization of a matrix involves writing the given matrix as the product of alower triangular matrix which has the main diagonal consisting entirely of ones, L, and anupper triangular matrix U in the indicated order. The L goes with “lower” and the U with“upper”. It turns out many matrices can be written in this way and when this is possible,people get excited about slick ways of solving the system of equations, Ax = y. The methodlacks generality but is of interest just the same.

Example 5.1.1 Can you write

(0 1

1 0

)in the form LU as just described?

To do so you would need(1 0

x 1

)(a b

0 c

)=

(a b

xa xb+ c

)=

(0 1

1 0

).

Therefore, b = 1 and a = 0. Also, from the bottom rows, xa = 1 which can’t happen andhave a = 0. Therefore, you can’t write this matrix in the form LU. It has no LU factorization.This is what I mean above by saying the method lacks generality.

Which matrices have an LU factorization? It turns out it is those whose row reducedechelon form can be achieved without switching rows and which only involve row operationsof type 3 in which row j is replaced with a multiple of row i added to row j for i < j.

5.2 Finding an LU Factorization

There is a convenient procedure for finding an LU factorization. It turns out that it isonly necessary to keep track of the multipliers which are used to row reduce to uppertriangular form. This procedure is described in the following examples and is called themultiplier method. It is due to Dolittle.

Example 5.2.1 Find an LU factorization for A =

 1 2 3

2 1 −4

1 5 2

Write the matrix next to the identity matrix as shown. 1 0 0

0 1 0

0 0 1

 1 2 3

2 1 −4

1 5 2

 .

The process involves doing row operations to the matrix on the right while simultaneouslyupdating successive columns of the matrix on the left. First take −2 times the first row andadd to the second in the matrix on the right. 1 0 0

2 1 0

0 0 1

 1 2 3

0 −3 −10

1 5 2

129