LU decomposition
Undergraduate
Consider a square matrix $A$. An LU decomposition of $A$ is a factorization $A = L U$, where $L$ is lower triangular (usually with ones on its diagonal) and $U$ is upper triangular.
Examples
Worked examples
-
The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\)
: \(L = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}\), \(U = \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix}\)
Undergraduate
Subtracting $2$ times row $1$ from row $2$ gives $U$, and $L$ records the multiplier $2$.
-
The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\)
: \(L = \begin{bmatrix} 1 & 0 \\ 1/2 & 1 \end{bmatrix}\), \(U = \begin{bmatrix} 4 & 2 \\ 0 & 2 \end{bmatrix}\)
Undergraduate
The matrix \(A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) is symmetric positive definite, so it has every decomposition in the table, including a Cholesky decomposition. Its eigendecomposition, Schur decomposition, Jordan normal form, and singular value decomposition all coincide, and its polar and Toeplitz decompositions are trivial.
-
The matrix \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\)
: $L = I$, $U = A$
Undergraduate
$A$ is upper triangular, so its LU decomposition is $I \cdot A$, and its QR decomposition is $I \cdot A$.
-
The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\)
: None, without exchanging rows
Undergraduate
In every product $L U$, the top-left entry $0$ would force $L$ or $U$ to be singular, but $A$ is invertible. Exchanging the rows gives $P A = I = I \cdot I$.
Properties
- Gaussian elimination without row exchanges computes an LU decomposition: $U$ is the resulting echelon form, and $L$ records the multiples of rows that were subtracted.
- Not every invertible matrix has an LU decomposition. With a permutation matrix $P$ that reorders the rows, every square matrix has a PLU decomposition $A = P L U$.
- Once $A = L U$ is known, $A x = b$ can be solved quickly by solving $L y = b$ and then $U x = y$, each by substitution.
Distinctions involving this term
- Types of matrix decompositions: A matrix decomposition writes a matrix in terms of simpler matrices. Most are products: LU, PLU, and Cholesky decompositions use triangular factors, QR and singular value decompositions use orthogonal factors, and eigendecompositions, Schur decompositions, and Jordan normal forms are similarities $A = P M P^{-1}$ to a simpler matrix $M$ (diagonal, triangular, or made of Jordan blocks). In contrast, the Jordan–Chevalley decomposition is a sum of commuting diagonalizable and nilpotent parts, and the Toeplitz decomposition is a sum $H + K$ of a symmetric matrix $H$ and a skew-symmetric matrix $K$.