The LU Factorization Theorem Without Pivoting

When Elimination Produces an LU Factorization

Gaussian elimination transforms a matrix into an upper triangular matrix by eliminating entries below successive pivots. When every required pivot is nonzero, the row operations can be recorded in a second matrix, giving a factorization \(\mathbf{A}=\mathbf{L}\mathbf{U}\). The factor \(\mathbf{U}\) records the result of elimination; the unit lower triangular factor \(\mathbf{L}\) records its multipliers. The condition for this process to work without row exchanges is expressed using the leading principal minors of \(\mathbf{A}\).

Throughout, \(\mathbf{A}\) is a real \(n\times n\) matrix. For \(1\leq k\leq n\), its \(k\)th leading principal submatrix is the \(k\times k\) matrix in its first \(k\) rows and first \(k\) columns. Its determinant is the \(k\)th leading principal minor, denoted \(\Delta_k\). We also set \(\Delta_0=1\). A matrix is unit lower triangular if it is lower triangular and every diagonal entry equals \(1\).

The hypothesis is important: it guarantees that every pivot needed by elimination is nonzero. It does not say that a matrix whose leading principal minors include zero can never have an LU factorization. Later examples distinguish these two claims.

Why the Leading Minors Control the Pivots

The proof uses induction on the matrix size. The central step is to eliminate the first column and examine the smaller matrix left behind. For a block matrix with a nonzero top-left entry, that smaller matrix is the Schur complement: if \(\mathbf{A}=\begin{bmatrix}a&\mathbf{r}\\ \mathbf{c}&\mathbf{B}\end{bmatrix}\), it is \(\mathbf{B}-\mathbf{c}\mathbf{r}/a\). We will use the elementary determinant facts that adding a multiple of one row to another preserves a determinant, and that the determinant of a triangular matrix is the product of its diagonal entries.

Proof. We prove existence and uniqueness together by induction on \(n\). When \(n=1\), the hypothesis says \(\mathbf{A}=[a]\) with \(a=\Delta_1\ne0\). The only possible factors are \(\mathbf{L}=[1]\) and \(\mathbf{U}=[a]\), so existence and uniqueness hold, and the pivot is \(a=\Delta_1/\Delta_0\).

Now suppose \(n\geq2\) and the claim holds for matrices of size \(n-1\). Write

where \(a=\Delta_1\ne0\), \(\mathbf{r}\) is a row, and \(\mathbf{c}\) is a column. Define \(\mathbf{S}=\mathbf{B}-\mathbf{c}\mathbf{r}/a\). For each \(j=1,\dots,n-1\), the leading \(j\times j\) submatrix of \(\mathbf{S}\) is obtained from the leading \((j+1)\times(j+1)\) submatrix of \(\mathbf{A}\) by eliminating its first column below \(a\). These row additions preserve the determinant and leave a block upper triangular matrix with diagonal blocks \([a]\) and that leading \(j\times j\) submatrix of \(\mathbf{S}\). Therefore its determinant is \(a\) times the determinant of that submatrix of \(\mathbf{S}\). In particular, the leading minors of \(\mathbf{S}\) are \(\Delta_{j+1}/a\), hence are all nonzero.

By the induction hypothesis, \(\mathbf{S}=\mathbf{L}_2\mathbf{U}_2\), with \(\mathbf{L}_2\) unit lower triangular and \(\mathbf{U}_2\) upper triangular. Set

Then \(\mathbf{L}\) is unit lower triangular, \(\mathbf{U}\) is upper triangular, and their product has blocks \(a\), \(\mathbf{r}\), \(\mathbf{c}\), and \(\mathbf{c}\mathbf{r}/a+\mathbf{L}_2\mathbf{U}_2=\mathbf{c}\mathbf{r}/a+\mathbf{S}=\mathbf{B}\). Thus \(\mathbf{A}=\mathbf{L}\mathbf{U}\), proving existence.

For uniqueness, suppose \(\mathbf{A}=\widetilde{\mathbf{L}}\widetilde{\mathbf{U}}\) is any factorization of the required form. Partition these factors into first row and column and lower-right blocks. Since the first row of \(\widetilde{\mathbf{L}}\) is \([1,\mathbf{0}]\), the first row of \(\widetilde{\mathbf{U}}\) must be \([a,\mathbf{r}]\). The first column of the product then gives the entries below the first diagonal entry of \(\widetilde{\mathbf{L}}\) as \(\mathbf{c}/a\). The lower-right block equation becomes \(\mathbf{B}=(\mathbf{c}/a)\mathbf{r}+\widetilde{\mathbf{L}}_2\widetilde{\mathbf{U}}_2\), so \(\mathbf{S}=\widetilde{\mathbf{L}}_2\widetilde{\mathbf{U}}_2\). By uniqueness for \(\mathbf{S}\), its two factors must equal \(\mathbf{L}_2,\mathbf{U}_2\). All blocks are therefore forced, proving uniqueness.

Finally, the first pivot is \(a=\Delta_1/\Delta_0\). After that pivot, the leading minors of the remaining matrix \(\mathbf{S}\) are \(\Delta_{j+1}/\Delta_1\). Induction gives its pivots as \((\Delta_{j+1}/\Delta_1)/(\Delta_j/\Delta_1)=\Delta_{j+1}/\Delta_j\). These are precisely the subsequent pivots of elimination on \(\mathbf{A}\). This proves the pivot formula and completes the induction. \(\square\)

Constructing the Factors by Elimination

The theorem’s uniqueness claim also has a useful determinant interpretation. For any factorization of the stated form, the leading \(k\times k\) block of \(\mathbf{A}\) is the product of the leading \(k\times k\) blocks of \(\mathbf{L}\) and \(\mathbf{U}\). The determinant product rule and the triangular form of these blocks give \(\Delta_k=u_{11}u_{22}\cdots u_{kk}\), since the diagonal entries of \(\mathbf{L}\) are all \(1\). Thus nonzero leading minors force each diagonal entry of \(\mathbf{U}\) to be nonzero.

What the Hypothesis Does—and Does Not—Say

The nonzero-minor condition is sufficient for a unique factorization with a unit lower triangular factor. It is not necessary for some LU factorization to exist. If a leading minor vanishes, the no-pivot elimination procedure may encounter a zero pivot, but an LU factorization may still be possible, and such a factorization need not be unique.

Common Pitfall: Using the Elimination Matrix as \(\mathbf{L}\)

It is easy to confuse the matrices that perform elimination with the factor that appears in \(\mathbf{A}=\mathbf{L}\mathbf{U}\). In the first worked example, the elimination matrices are \(\mathbf{E}_1=\begin{bmatrix}1&0&0\\-2&1&0\\1&0&1\end{bmatrix}\) and \(\mathbf{E}_2=\begin{bmatrix}1&0&0\\0&1&0\\0&-\tfrac43&1\end{bmatrix}\). They satisfy \(\mathbf{E}_2\mathbf{E}_1\mathbf{A}=\mathbf{U}\), so the incorrect calculation would be \(\mathbf{A}=(\mathbf{E}_2\mathbf{E}_1)\mathbf{U}\). The correction is to invert the elimination operations: \(\mathbf{A}=\mathbf{E}_1^{-1}\mathbf{E}_2^{-1}\mathbf{U}\). Those inverse operations put the original multipliers, not their negatives, below the diagonal in \(\mathbf{L}\). In this case the resulting factor is \(\begin{bmatrix}1&0&0\\2&1&0\\-1&\tfrac43&1\end{bmatrix}\), as direct multiplication confirms.

The distinction is practical as well as notational. Elimination matrices turn \(\mathbf{A}\) into \(\mathbf{U}\); the factor \(\mathbf{L}\) reverses those operations and allows the original matrix to be recovered as \(\mathbf{L}\mathbf{U}\). When no row exchanges are made and the pivots are nonzero, the multipliers can be recorded directly in \(\mathbf{L}\).