LU Factorization

Triangular Matrices. An matrix

is called a lower triangular matrix if all the “entries above the diagonal” are zeros, and an matrix

is called an upper triangular matrix if all the “entries below the diagonal” are zeros. For example,

$\displaystyle L = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & -3 & 0 & 0 \\ 1 & 4 & 2 & 0 \\ -1 & 1 & 3 & 1 \end{bmatrix}$ and $\displaystyle \quad U = \begin{bmatrix} 4 & -1 & 3 & 2 \\ 0 & 2 & 1 & -5 \\ 0 & 0 & -1 & 9 \\ 0 & 0 & 0 & 7 \end{bmatrix}$

A lower and upper triangular matrix is called a diagonal matrix. The identity matrix

is a diagonal matrix.

When Elementary Matrices are triangular? Except for row operations of interchange, the elementary matrices of row operation are triangular.

An elementary matrix for adding a multiple of the -th row by to the -th row is a lower triangular matrix if . It is an upper triangular matrix if .
An elementary matrix for multiplying the -th row by is a diagonal matrix.

Properties of Triangular Matrices. Note that and are not necessarily square matrices. But if they are square, triangular matrices have the following properties:

If both and are lower (or upper) triangular matrices, the product is also a lower (or an upper) triangular matrix.
Let be a lower (or an upper) triangular matrix. If all the diagonal entries $a_{ii}$ 's are nonzero, then (i) is invertible and (ii) the inverse $A^{-1}$ is also a lower (or an upper) triangular matrix.

EXAMPLE 1. Demonstrate each of the above properties using $3\times 3$ triangular matrices.

LU Factorization. If a matrix (not necessarily square) is expressed as the product

$\displaystyle A = L U$

of a lower triangular matrix

and an upper triangular matrix

, it is called an LU factorization.