## LU factorization

Let be a (not necessarily square) matrix, and let be an echelon form obtained from  by basic row operations; note that is an upper triangular matrix. Suppose that can be reduced to without interchanging rows. Then we have a series of elementary matrices  so that . Since each elementary matrix is given by (a) with  or by (c), both and are lower triangular matrices. Furthermore, the matrix multiplication also gives a lower triangle matrix. This leads to the LU factorization

Suppose that there are row operations of type (b) in obtaining the echelon form . Then we can begin with interchanging rows on  to create  (which yields a series of elementary matrices of type (b) so that ), and reduce  to  without interchanging rows. Thus, we have . By letting , together we obtain .

EXAMPLE 2. Find an LU factorization of

Department of Mathematics