LU factorization

Let $ A$ be a (not necessarily square) matrix, and let $ U$ be an echelon form obtained from $ A$ by basic row operations; note that $ U$ is an upper triangular matrix. Suppose that $ A$ can be reduced to $ U$ 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$. Since each elementary matrix $ E_i$ is given by (a) with $ i < j$ or by (c), both $ E_i$ and $ E_i^{-1}$ are lower triangular matrices. Furthermore, the matrix multiplication $ L = E_1^{-1} E_2^{-1} \cdots E_p^{-1}$ also gives a lower triangle matrix. This leads to the LU factorization

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

Suppose that there are row operations of type (b) in obtaining the echelon form $ U$. Then we can begin with interchanging rows on $ A$ to create $ B$ (which yields a series of elementary matrices $ F_1, F_2, \ldots, F_q$ of type (b) so that $ B = F_1 F_2 \cdots F_q A$), and reduce $ B$ to $ U$ without interchanging rows. Thus, we have $ B = L U$. By letting $ P = F_1, F_2, \ldots, F_q$, together we obtain $ P A = L U$.

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



Department of Mathematics
Last modified: 2005-10-21