Definition · applies to square matrices · also called LU factorization

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$. $A$ is not diagonalizable, so its Jordan–Chevalley decomposition has a nonzero nilpotent part $N$.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : None, without exchanging rows Undergraduate
    In any 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$.

All definitions · All distinctions · All examples