Every square matrix \( A \) satisfies the trivial identity \( A = I\,A \), where \( I \) is the identity matrix. Our goal is to factor \( A \) as the product of a unit lower triangular matrix \( L \) and an upper triangular matrix \( U \):
\( A = L\,U \).
We obtain this factorization by applying Gaussian elimination to the right factor \( A \). Each row operation \( R_m \leftarrow R_m + k\,R_j \) corresponds to left-multiplication by an elementary matrix \( E_k \). Applying the full sequence of eliminations \( E_1, E_2, \dots, E_p \) gives
\( E_p \cdots E_2 E_1 \, A = U \),
where \( U \) is the resulting upper triangular matrix. Solving for \( A \):
\( A = \bigl( E_p \cdots E_2 E_1 \bigr)^{-1} U = E_1^{-1} E_2^{-1} \cdots E_p^{-1} \, U \).
The product of the inverses of the elementary matrices is exactly the lower triangular matrix \( L \):
\( L = E_1^{-1} E_2^{-1} \cdots E_p^{-1}. \)
Because each \( E_k^{-1} \) is itself an elementary matrix — obtained from the identity by the opposite row operation — the matrix \( L \) is automatically unit lower triangular, with the multipliers of the elimination recorded (with signs flipped) in the off-diagonal entries. Thus the classical rule “the multiplier that zeroes entry \( (m,j) \) becomes \( -k \) in \( L_{mj} \)” is just a restatement of the elementary-matrix identity \( E_k^{-1} = I - k\,e_m e_j^{T} \).
This is why LU decomposition works: it is nothing but a product of elementary matrices, rearranged so that all the “inverse” operations are collected into one factor \( L \) and all the “forward” eliminations are collected into another factor \( U \).
The intro above framed LU using elementary matrices. Here we describe the same process from the perspective of row operations and the matching column operations on \( I \) — the two viewpoints are equivalent.
Every square matrix \( A \) satisfies the trivial identity \( A = I\,A \).
Our goal is to transform the right factor \( A \) into an upper triangular matrix \( U \) using row operations \( R_m \leftarrow R_m + k\,R_j \) with \( m > j \). Each such row operation corresponds to left‑multiplication by an elementary matrix \( E \), so the right factor evolves as \( A \to E\,A \).
To keep the product \( L \cdot U \) equal to \( A \), we must simultaneously apply the inverse operation to the left factor. The inverse of the row operation \( R_m \leftarrow R_m + k\,R_j \) is the row operation \( R_m \leftarrow R_m - k\,R_j \), and applying it to the left factor \( I \) from the right is the same as the column operation \( C_j \leftarrow C_j - k\,C_m \).
Left-multiplying a matrix by an elementary matrix \( E^{-1} \) performs the row operation \( R_m \leftarrow R_m - kR_j \). The same matrix \( E^{-1} \) right-multiplied performs the transposed operation on the columns: \( C_j \leftarrow C_j - kC_m \). The indices swap because right-multiplication is the transpose (in the matrix sense) of left-multiplication: \[ (M E^{-1})^T = (E^{-1})^T M^T \] So the row operation on the right factor is naturally paired with the transposed column operation on the left factor — and because the left factor starts as \( I \), that column operation simply inserts \( -k \) at position \( (m, j) \), building up \( L \).
In other words, the row operation on the right factor and the column operation on the left factor are inverses of each other, in the sense that \( E^{-1} E = I \). Because they are inverses, the product is preserved at every step.
Since we start with the left factor equal to \( I \), the column operation simply inserts the value \( -k \) at position \( (m, j) \) — building up the lower triangular matrix \( L \). When the right factor has become upper triangular, we have \( A = L\,U \). You can verify any result with the Online LU Matrix Decomposition Calculator.
An LU decomposition of a square matrix \( A \) is a factorization \( A = L\,U \) where
To zero out entry \( (m, j) \) of the current right factor, we apply the row operation
\( R_m \leftarrow R_m + k\,R_j \qquad (m > j) \)
To keep the product unchanged, we simultaneously apply the inverse column operation to the left factor:
\( C_j \leftarrow C_j - k\,C_m \)
\( U \leftarrow E\,U \)
Effect: entry \( (m,j) \) becomes \( 0 \).
\( L \leftarrow L\,E^{-1} \)
Effect: entry \( (m,j) \) becomes \( -k \).
| Row operation on \( U \) (right factor) | Column operation on \( L \) (left factor) |
|---|---|
| \( R_m \leftarrow R_m + k R_j \) | \( C_j \leftarrow C_j - k C_m \) |
| Left‑multiply by \( E \) | Right‑multiply by \( E^{-1} \) |
| Effect: entry \( (m, j) \) of \( U \) becomes \( 0 \) | Effect: entry \( (m, j) \) of \( L \) becomes \( -k \) |
| The two operations are inverses: \( E^{-1} E = I \), so the product \( L\,U = A \) is preserved. | |
Because \( E \cdot E^{-1} = I \), the product \( L \cdot U = A \) is preserved at every step. Since we start with \( L = I \), each column operation simply fills in one off‑diagonal entry of \( L \), and the diagonal entries of \( L \) stay equal to \( 1 \).
Let \( E \) be the elementary matrix performing \( R_m \leftarrow R_m + kR_j \). Its inverse \( E^{-1} \) performs \( R_m \leftarrow R_m - kR_j \). Starting from \( A = I \cdot A \) and inserting \( E^{-1}E = I \):
\( A = I \cdot A = (I\,E^{-1})(E\,A) \)
Left‑multiplying the right factor by \( E \) performs the row operation \( R_m \leftarrow R_m + kR_j \). Right‑multiplying the left factor by \( E^{-1} \) performs the inverse row operation on \( L \), which — because \( L \) is being multiplied on the right — is equivalent to the column operation \( C_j \leftarrow C_j - kC_m \).
The two operations are therefore inverses of each other:
\( E \cdot E^{-1} = I \)
so their combined effect leaves the product unchanged. This is exactly why every stage maintains \( L^{(k)} U^{(k)} = A \).
Repeating for every stage gives the invariant chain:
\( A = L^{(0)}U^{(0)} = L^{(1)}U^{(1)} = L^{(2)}U^{(2)} = \cdots = L\,U \)
Below, both the row operation on \( U \) and the inverse column operation on \( L \) are shown at every step, along with the updated matrices.
An invertible matrix \( A \) has an LU decomposition (without row interchanges) if and only if all its leading principal minors are non‑zero.
The \( k^{\text{th}} \)-order leading principal minor \( M_k \) is the determinant of the submatrix formed by keeping the first \( k \) rows and the first \( k \) columns of \( A \).
Example. For
\[ A = \begin{bmatrix} 1 & 0 & -2 & 5 \\ 0 & -2 & 1 & 4 \\ 3 & 3 & 1 & -3 \\ 4 & 0 & 1 & 2 \end{bmatrix}, \]
the four leading principal minors are:
\[ M_1 = \det[1] = 1, \]
\[ M_2 = \det\begin{bmatrix} 1 & 0 \\ 0 & -2 \end{bmatrix} = -2, \]
\[ M_3 = \det\begin{bmatrix} 1 & 0 & -2 \\ 0 & -2 & 1 \\ 3 & 3 & 1 \end{bmatrix} = -17, \]
\[ M_4 = \det\begin{bmatrix} 1 & 0 & -2 & 5 \\ 0 & -2 & 1 & 4 \\ 3 & 3 & 1 & -3 \\ 4 & 0 & 1 & 2 \end{bmatrix} = 90. \]
Since all leading principal minors are non‑zero, \( A \) has an LU decomposition. (We do not compute it explicitly here — the purpose of this example is to illustrate the existence test.)
Find the LU decomposition of \( A = \begin{bmatrix} 1 & -1 \\ 2 & -1 \end{bmatrix} \).
Start with \( L^{(0)} = I \), \( U^{(0)} = A \):
\[ A = \underbrace{\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}}_{L^{(0)}} \cdot \underbrace{\begin{bmatrix} 1 & -1 \\ 2 & -1 \end{bmatrix}}_{U^{(0)}} \]
\[ L^{(0)} U^{(0)} = \begin{bmatrix} 1 & -1 \\ 2 & -1 \end{bmatrix} = A \quad \checkmark \]
Stage 1 — Zero out \( U_{21} \) with multiplier \( k = -2 \).
\( R_2 \leftarrow R_2 + (-2)R_1 \)
\( C_1 \leftarrow C_1 - (-2)C_2 \Rightarrow L_{21} = 2 \)
\[ \begin{bmatrix} 1 & -1 \\ 2 & -1 \end{bmatrix} \xrightarrow{\;R_2 - 2R_1\;} \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix} \]
\[ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \xrightarrow{\;C_1 \leftarrow C_1 + 2C_2\;} \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} \]
Final factors:
\[ L = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}, \qquad U = \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix} \]
\[ L\,U = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ 2 & -1 \end{bmatrix} = A \quad \checkmark \]
Find the LU decomposition of \( A = \begin{bmatrix} -1 & -1 & 2 \\ 2 & 0 & 3 \\ -3 & 2 & -1 \end{bmatrix} \).
Start with \( L^{(0)} = I \), \( U^{(0)} = A \):
\[ A = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{L^{(0)}} \cdot \underbrace{\begin{bmatrix} -1 & -1 & 2 \\ 2 & 0 & 3 \\ -3 & 2 & -1 \end{bmatrix}}_{U^{(0)}} \]
\[ L^{(0)} U^{(0)} = \begin{bmatrix} -1 & -1 & 2 \\ 2 & 0 & 3 \\ -3 & 2 & -1 \end{bmatrix} = A \quad \checkmark \]
Stage 1 — Zero out column 1 below the pivot. Multipliers \( k = 2 \) (row 2) and \( k = -3 \) (row 3).
\( R_2 \leftarrow R_2 + 2R_1 \)
\( R_3 \leftarrow R_3 - 3R_1 \)
\( C_1 \leftarrow C_1 - 2C_2 \Rightarrow L_{21} = -2 \)
\( C_1 \leftarrow C_1 - (-3)C_3 \Rightarrow L_{31} = 3 \)
\[ \begin{bmatrix} -1 & -1 & 2 \\ 2 & 0 & 3 \\ -3 & 2 & -1 \end{bmatrix} \xrightarrow{\;R_2 + 2R_1,\; R_3 - 3R_1\;} \begin{bmatrix} -1 & -1 & 2 \\ 0 & -2 & 7 \\ 0 & 5 & -7 \end{bmatrix} \]
\[ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \xrightarrow{\;C_1 \leftarrow C_1 - 2C_2,\; C_1 \leftarrow C_1 + 3C_3\;} \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & 0 & 1 \end{bmatrix} \]
After Stage 1:
\[ L^{(1)} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & 0 & 1 \end{bmatrix}, \qquad U^{(1)} = \begin{bmatrix} -1 & -1 & 2 \\ 0 & -2 & 7 \\ 0 & 5 & -7 \end{bmatrix} \]
\[ L^{(1)} U^{(1)} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & 0 & 1 \end{bmatrix} \begin{bmatrix} -1 & -1 & 2 \\ 0 & -2 & 7 \\ 0 & 5 & -7 \end{bmatrix} = \begin{bmatrix} -1 & -1 & 2 \\ 2 & 0 & 3 \\ -3 & 2 & -1 \end{bmatrix} = A \quad \checkmark \]
Stage 2 — Zero out \( U_{32} \) with multiplier \( k = \tfrac{5}{2} \).
\( R_3 \leftarrow R_3 + \tfrac{5}{2}R_2 \)
\( C_2 \leftarrow C_2 - \tfrac{5}{2}C_3 \Rightarrow L_{32} = -\tfrac{5}{2} \)
\[ \begin{bmatrix} -1 & -1 & 2 \\ 0 & -2 & 7 \\ 0 & 5 & -7 \end{bmatrix} \xrightarrow{\;R_3 + \tfrac{5}{2}R_2\;} \begin{bmatrix} -1 & -1 & 2 \\ 0 & -2 & 7 \\ 0 & 0 & \tfrac{21}{2} \end{bmatrix} \]
\[ \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & 0 & 1 \end{bmatrix} \xrightarrow{\;C_2 \leftarrow C_2 + \tfrac{5}{2}C_3\;} \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & -\tfrac{5}{2} & 1 \end{bmatrix} \]
Final factors:
\[ L = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & -\tfrac{5}{2} & 1 \end{bmatrix}, \qquad U = \begin{bmatrix} -1 & -1 & 2 \\ 0 & -2 & 7 \\ 0 & 0 & \tfrac{21}{2} \end{bmatrix} \]
\[ L\,U = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & -\tfrac{5}{2} & 1 \end{bmatrix} \begin{bmatrix} -1 & -1 & 2 \\ 0 & -2 & 7 \\ 0 & 0 & \tfrac{21}{2} \end{bmatrix} = \begin{bmatrix} -1 & -1 & 2 \\ 2 & 0 & 3 \\ -3 & 2 & -1 \end{bmatrix} = A \quad \checkmark \]
Determine which of the following invertible matrices have an LU decomposition:
a) \( \begin{bmatrix} 0 & -1 \\ -1 & 2 \end{bmatrix} \) b) \( \begin{bmatrix} -1 & -1 & -4 \\ -2 & 0 & -4 \\ 1 & -1 & 2 \end{bmatrix} \) c) \( \begin{bmatrix} 2 & 2 & 8 & 2 \\ 0 & 2 & 4 & -2 \\ 1 & 0 & 2 & 0 \\ 0 & 4 & -1 & 0 \end{bmatrix} \)
a) \( M_1 = 0 \), \( M_2 = -1 \). Since \( M_1 = 0 \), there is no LU decomposition — Gaussian elimination cannot even start (pivot \( a_{11}=0 \)).
b) \( M_1 = -1,\; M_2 = -2,\; M_3 = -4 \). All non‑zero, so an LU decomposition exists:
\( \begin{bmatrix} -1 & -1 & -4 \\ -2 & 0 & -4 \\ 1 & -1 & 2 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -1 & 1 \end{bmatrix} \begin{bmatrix} -1 & -1 & -4 \\ 0 & 2 & 4 \\ 0 & 0 & 2 \end{bmatrix} \)
c) \( M_1 = 2,\; M_2 = 4,\; M_3 = 0,\; M_4 = -72 \). Since \( M_3 = 0 \), there is no LU decomposition.
| Example | Matrix | \( L \) | \( U \) |
|---|---|---|---|
| 1 | \(2 \times 2\) | \( \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} \) | \( \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix} \) |
| 2 | \(3 \times 3\) | \( \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & -\tfrac{5}{2} & 1 \end{bmatrix} \) | \( \begin{bmatrix} -1 & -1 & 2 \\ 0 & -2 & 7 \\ 0 & 0 & \tfrac{21}{2} \end{bmatrix} \) |
Find the LU decomposition, if any, of the following matrices: