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*

EXAMPLE 2. Find an LU factorization of

Department of Mathematics