LU Decomposition¶

Definition¶

An LU decomposition factors a matrix, after possible row permutations, as $\boldsymbol{P}\boldsymbol{A}=\boldsymbol{L}\boldsymbol{U}$ $L U$ , where $\boldsymbol{P}$ is a permutation matrix, $\boldsymbol{L}$ is lower triangular, and $\boldsymbol{U}$ is upper triangular.

Interpretation¶

LU decomposition records the forward phase of Gaussian elimination (row reduction to row echelon form) as a matrix factorization: $\boldsymbol{U}$ is the echelon form that elimination produces, and $\boldsymbol{L}$ stores the multipliers used to get there.

A 3 by 3 matrix A written as the product of a lower triangular matrix L, holding the elimination multipliers, and an upper triangular matrix U, its echelon form.

The figure factors

\boldsymbol{A}=\begin{pmatrix}2&1&1\\4&3&3\\-2&1&3\end{pmatrix}.

Subtracting $2$ times row 1 from row 2, adding row 1 to row 3 (multiplier $-1$ ), and then subtracting $2$ times the new row 2 from row 3 leaves $\boldsymbol{U}$ ; the multipliers $2$ , $-1$ , $2$ fill $\boldsymbol{L}$ below its diagonal of ones.

Multiplying $\boldsymbol{L}\boldsymbol{U}$ undoes the elimination and rebuilds $\boldsymbol{A}$ row by row. For instance, row 3 of $\boldsymbol{A}$ is $-1$ times row 1 of $\boldsymbol{U}$ , plus $2$ times row 2, plus row 3: $-(2,1,1)+2(0,1,1)+(0,0,2)=(-2,1,3)$ $(- 2, 1, 3)$ . Since $\boldsymbol{L}$ and $\boldsymbol{U}$ are triangular, the factorization also gives the determinant: $\det\boldsymbol{A}=\det\boldsymbol{L}\det\boldsymbol{U}=2\cdot1\cdot2=4$ $4$ .

To solve $\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$ $b$ , first solve $\boldsymbol{L}\boldsymbol{y}=\boldsymbol{P}\boldsymbol{b}$ by forward substitution, then $\boldsymbol{U}\boldsymbol{x}=\boldsymbol{y}$ by back substitution. The elimination is done once, so each further right-hand side costs only these two triangular solves. Row swaps are needed when a zero appears in a pivot position: $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ has no decomposition $\boldsymbol{A}=\boldsymbol{L}\boldsymbol{U}$ $L U$ , since its first pivot would be $0$ , but swapping its rows gives $\boldsymbol{P}\boldsymbol{A}=\boldsymbol{I}=\boldsymbol{I}\boldsymbol{I}$ $I I$ . When no row swaps are needed, $\boldsymbol{P}=\boldsymbol{I}$ $I$ .

A common slip concerns the signs in $\boldsymbol{L}$ . Its entries are the multipliers $m$ in "subtract $m$ times row $j$ from row $i$ ", so adding row 1 to row 3 enters $\boldsymbol{L}$ as $-1$ , not $+1$ .

Key Results¶

If no row interchanges are needed, the factorization is $\boldsymbol{A}=\boldsymbol{L}\boldsymbol{U}$ $L U$ .
LU decomposition helps solve $\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$ efficiently by forward and back substitution.

Examples¶

For $\boldsymbol{A}=\begin{pmatrix}1&1&1\\2&4&8\\3&9&27\end{pmatrix}$ $1231491827$ , subtract $2$ and $3$ times row 1 from rows 2 and 3, then $3$ times the new row 2 from row 3. This gives $\boldsymbol{U}=\begin{pmatrix}1&1&1\\0&2&6\\0&0&6\end{pmatrix}$ $100120166$ , the multipliers fill $\boldsymbol{L}=\begin{pmatrix}1&0&0\\2&1&0\\3&3&1\end{pmatrix}$ $123013001$ , and $\boldsymbol{A}=\boldsymbol{L}\boldsymbol{U}$ $L U$ .
$\boldsymbol{P}\boldsymbol{A}=\boldsymbol{L}\boldsymbol{U}$ includes pivoting through the permutation matrix $\boldsymbol{P}$ .

Prerequisites¶

Sources¶

Math II: Linear Algebra · Week 5

Aliases: LU factorization, LU factorisation, PLU decomposition

Last updated: 20 October 2026 03:02