LU decomposition

Definition 1

Let $A$ be an $n\mathrm{\times }m$ matrix. An LU decomposition (sometimes also called an LU factorization) of $A$, if it exists, is an $n\mathrm{\times }n$ unit lower triangular matrix $L$ and an $n\mathrm{\times }m$ matrix U, in (upper) echelon form, such that

$$A=LU$$

The LU factorization is closely related to the row reduction algorithm. In a very real sense, the factorization is a record of the steps taken in row reducing a matrix to echelon form. The matrix $L$ “encodes” the sequence of row replacement operations that row reduce the given matrix $A$ to echelon form $U$.

Proposition 2

Suppose that $A\mathrm{=}L\mathit{}U$ is an LU factorization, and let $L_{i\mathit{}j}$ denote the entries of $L$. Then, the row reduction $A\stackrel{\rho }{\mathrm{⟹}}U$ is accomplished by the following sequence $\rho$ of $\frac{\mathrm{1}}{\mathrm{2}}\mathit{}n\mathit{}\mathrm{(}n\mathrm{-}\mathrm{1}\mathrm{)}$ row replacement operations:

${\mathrm{row}}_j\mapsto {\mathrm{row}}_j-L_{j1}{\mathrm{row}}_1,j=2,\mathrm{\dots },n;$

${\mathrm{row}}_j\mapsto {\mathrm{row}}_j-L_{j2}{\mathrm{row}}_2,j=3,\mathrm{\dots },n;$

$\mathrm{ }\mathrm{⋮}$

${\mathrm{row}}_j\mapsto {\mathrm{row}}_j-L_{jk}{\mathrm{row}}_k,j=k+1,\mathrm{\dots },n,k=1,\mathrm{\dots },n-1$

$\mathrm{ }\mathrm{⋮}$

Note: the first $n-1$ steps clear out column $1$, the next $n-2$ steps clear out column $2$, etc.

Proposition 3

Not every matrix admits an LU factorization. Indeed, an LU factorization exists if and only if $A$ can be reduced to echelon without using row exchange operations. However, if an LU factorization exists, then it is unique.

In the most general case, one has to employ row exchange operations.

Proposition 4

Let $A$ be an $n\mathrm{\times }m$ matrix. Then, there exists an $n\mathrm{\times }n$ permutation matrix $P$ (indeed, many such) such that the matrix $P\mathit{}A$ admits an LU factorization, i.e., there exist matrices $P\mathrm{,}L\mathrm{,}U$ such that

$$PA=LU.$$

The key idea behind LU factorization is that one does not need to employ row scalings to do row reduction until the second half (the back-substitution phase) of the algorithm. This has significant implication for numerical stability of the algorithm.

The LU decomposition of a given matrix $A$ is useful for the solution of the systems of linear equations of the form $Ax=b$. Indeed, it suffices to first solve the linear system $Ly=b$, and second, to solve the system $Ux=y$. This two-step procedure is easy to implement, because owing to the lower and upper-triangular nature of the matrices $L$ and $U$, the required row operations are determined, more or less, directly from the entries of $L$ and $U$. Indeed, the first step,

$$[Lb]\stackrel{{\rho }_1}{⟹}[Iy]$$

a sequence of row operations ${\rho }_1$, and the second step

$$[Uy]\stackrel{{\rho }_2}{⟹}[E{x}_0]$$

a sequence of row operations ${\rho }_2$, are exactly the same row operations one has to perform to row reduce $A$ directly to reduced echelon form $E$:

$$[Ab]\stackrel{{\rho }_1}{⟹}[Uy]\stackrel{{\rho }_2}{⟹}[E{x}_0].$$

Note: $x_0$ is the particular solution of $Ax=b$ that sits in the rightmost colulmn of the augmented matrix at the termination of the row-reduction algorithm.

Title	LU decomposition
Canonical name	LUDecomposition
Date of creation	2013-03-22 12:06:37
Last modified on	2013-03-22 12:06:37
Owner	rmilson (146)
Last modified by	rmilson (146)
Numerical id	10
Author	rmilson (146)
Entry type	Definition
Classification	msc 65-00
Classification	msc 15-00
Synonym	LU factorization
Synonym	LU-factorization
Synonym	LU-decomposition
Related topic	QRDecomposition