Chapter 10

A Few Factorizations10.1 Definition Of An LU factorization

An LU factorization of a matrix involves writing the given matrix as the product of a lowertriangular matrix which has the main diagonal consisting entirely of ones L, and an uppertriangular matrix U in the indicated order. This is the version discussed here but it issometimes the case that the L has numbers other than 1 down the main diagonal. It is stilla useful concept. The L goes with “lower” and the U with “upper”. It turns out manymatrices can be written in this way and when this is possible, people get excited about slickways of solving the system of equations, Ax = y. It is for this reason that you want to studythe LU factorization. It allows you to work only with triangular matrices. It turns out thatit takes about half as many operations to obtain an LU factorization as it does to find therow reduced echelon form.

First it should be noted not all matrices have an LU factorization and so we will em-phasize the techniques for achieving it rather than formal proofs.

Example 10.1.1 Can you write

(0 11 0

)in the form LU as just described?

To do so you would need(1 0x 1

)(a b0 c

)=

(a bxa xb+ c

)=

(0 11 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 factoriza-tion. This is what we mean above by saying the method lacks generality.

10.2 Finding An LU Factorization By InspectionWhich matrices have an LU factorization? It turns out it is those whose row reduced ech-elon 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.

Example 10.2.1 Find an LU factorization of A =

 1 2 0 21 3 2 12 3 4 0

 .

One way to find the LU factorization is to simply look for it directly. You need 1 2 0 21 3 2 12 3 4 0

=

 1 0 0x 1 0y z 1

 a d h j

0 b e i0 0 c f

 .

Then multiplying these you get a d h jxa xd +b xh+ e x j+ iya yd + zb yh+ ze+ c y j+ iz+ f

205