Matrix Algebra

Factorization Procedure

Factorization Procedure Case I. Let

be a matrix (not necessarily square). Suppose that

can be reduced to an echelon form

(not an REF) by row operations without interchanging rows. Then we have a series of elementary matrices $E_1, E_2, \ldots, E_p$ so that $E_p \cdots E_2 E_1 A = U$ . Here each elementary matrix

corresponds to a row operation of “replacement” with

(and no need for “scaling”). Since both

and $E_i^{-1}$ are lower triangular matrices, the matrix multiplication $L = E_1^{-1} E_2^{-1} \cdots E_p^{-1}$ also becomes a lower triangular matrix. Since

is an upper triangular matrix, this precedure leads to the LU factorization

$\displaystyle L U = L (E_p \cdots E_2 E_1 A) = A.$

EXAMPLE 1. Find an LU factorization for $A = \begin{bmatrix} 2 & 4 &-1 & 5 &-2 \\ -4 &-5 & 3 &-8 & 1 \\ 2 &-5 &-4 & 1 & 8 \\ -6 & 0 & 7 &-3 & 1 \end{bmatrix}$

Factorization Procedure Case II. Suppose that we need row operations of “interchange” to obtain the echelon form . Then we can begin with interchanging rows on to create (which yields a series of elementary matrices $F_1, F_2, \ldots, F_q$ of “interchange” so that $B = F_q \cdots F_2 F_1 A$ ), and reduce to without interchanging rows. Thus, we have . Let $P = F_q \cdots F_2 F_1$ . The matrix is called a permutation matrix. Together we obtain an factorization .

EXAMPLE 2. Let $A = \begin{bmatrix} 0 & 1 &-4 & 8 \\ 2 &-3 & 2 & 1 \\ 5 &-8 & 7 & 1 \end{bmatrix}$ . Find an LU factorization of the form .