# LU factorization of a nonsingular matrix exists if and only if all leading principal submatrices are nonsingular.

I'm struggling to prove this theorem. I can prove that if the $$LU$$ factorization exists, then the leading principal submatrices are nonsingular.

To do that, I can show that the determinant of every leading principal submatrix is not zero. (The leading principal submatrix is the product of $$L$$ and $$U$$ corresponding leading principal submatrices , and determinant of every $$L$$ leading principal submatrix is $$1$$ and determinant of the $$U$$ leading principal submatrix is product of the diagonal elements).

To prove that if the leading principal submatrices are nonsingular, then $$LU$$ factorization exists, I believe I should use induction, but I'm getting nowhere. Can anyone help me with the proof?

• this is stated poorly. – воитель Oct 13 '18 at 22:17
• @RyanHowe I'd appreciate any help on stating the question properly. Could you point out the shortcomings? – moonesque Oct 14 '18 at 19:31
• when you refer to every submatrix, are you referring to every the block LU decomposition? – воитель Oct 14 '18 at 19:56
• @RyanHowe I'm referring to leading principal submatrices. Edited. Thank you for pointing that out. – moonesque Oct 14 '18 at 20:14

We show by induction that every $$n \times n$$ matrix $$A$$ with nonsingular leading principal minors has a factorization $$A = LU$$ where $$L$$ is strictly lower triangular, $$U$$ is upper triangular, and $$L$$ and $$U$$ are both nonsingular. (This statement, as you show, is an if-and-only-if.)

The $$1\times 1$$ base case is just factoring $$a = 1 \cdot a$$. To induct, write your $$n \times n$$ matrix $$A$$ as a leading principal $$(n-1) \times (n-1)$$ matrix $$A'$$ and some leftover entries: $$A = \left[\begin{array}{ccc|c} & & & \\ & A' & & \vec{b} \\ & & & \\ \hline & \vec{c}^{\mathsf T} & & d \\\end{array}\right].$$ By the inductive hypothesis (since all leading principal minors of $$A'$$ are also leading principal minors of $$A$$), $$A'$$ has an $$LU$$ factorization as $$A' = L' U'$$ with nonsingular $$L'$$, $$U'$$. We want to use this to make the factorization $$\left[\begin{array}{ccc|c} & & & \\ & A' & & \vec{b} \\ & & & \\ \hline & \vec{c}^{\mathsf T} & & d \\\end{array}\right] = \left[\begin{array}{ccc|c} & & & \\ & L' & & \vec{0} \\ & & & \\ \hline & \vec{x}^{\mathsf T} & & 1 \\\end{array}\right]\left[\begin{array}{ccc|c} & & & \\ & U' & & \vec{y} \\ & & & \\ \hline & \vec{0}^{\mathsf T} & & z \\\end{array}\right]$$ work, by picking appropriate $$\vec x$$, $$\vec y$$, and $$z$$.

By doing the block multiplication, we get four equations.

• We have $$A' = L'U' + \vec{0}\vec{0}^{\mathsf T}$$, which we know is true, so that's done.
• We have $$\vec b = L'\vec y + \vec 0 z$$, so we want to set $$\vec y = L'^{-1}\vec b$$. Fortunately that's possible since $$L'$$ is invertible.
• We have $$\vec c^{\mathsf T} = \vec{x}^{\mathsf T}U' + \vec{0}^{\mathsf T}$$, so we want to set $$\vec{x}^{\mathsf T} = \vec{c}^{\mathsf T}U'^{-1}$$. This is possible since $$U'$$ is also invertible.
• We have $$d = \vec{x}^{\mathsf T}\vec y + z$$, so we want to set $$z = d - \vec{x}^{\mathsf T} \vec y$$.

For future inductive steps, we also want to know that the resulting matrices $$L$$ and $$U$$ are nonsingular. This is immediate for $$L$$ since its diagonal is $$1$$; for $$U$$, it's not obvious how to check that the value of $$z$$ we get is nonzero. But once we have $$A = LU$$ where $$A$$ and $$L$$ are nonsingular, we know that $$U = L^{-1}A$$ is nonsingular.

There are also $$LU$$ factorizations out there for which $$U$$ is singular (some of the diagonal entries of $$U$$ are zero). For these, there is not an if-and-only-if condition this nice.

You can see from the above proof, for instance, that if $$A$$ is possibly singular but all of its proper leading principal minors are still nonsingular, then we get a factorization $$A = LU$$ in which the bottom right entry is possibly $$0$$. (This is because arguing $$z\ne 0$$ is the only place where we needed $$A$$ to be nonsingular.)

• Nice! But you put the nonsingularity argument at the wrong place -- the singularity of $A$ is not given (singular matrices can have LU-decompositions too). You should rather argue during the induction step that $A'$ is nonsingular (since $\det A'$ is one of those nonzero principal minors) and therefore $L'$ and $U'$ are nonzero as well (since $A' = L'U'$). – darij grinberg Oct 14 '18 at 23:40
• That would not be fully general either. In general, this approach can't tell when a singular matrix has an $LU$ decomposition where some diagonal entries of $U$ are zero. Your suggestion would let us handle the case where the last diagonal entry is $0$, but other cases exist (cases where at every step after the first awkward zero entry, the equation $\vec c^{\mathsf T} = \vec x^{\mathsf T}U'$ happens to have a solution anyway). – Misha Lavrov Oct 14 '18 at 23:44
• But I'll edit to make this more precise. – Misha Lavrov Oct 14 '18 at 23:44
• It's not a necessary and sufficient criterion, true. But if the proper northwestern principal minors (not $\det A$ itself) are nonzero, then the matrix definitely has a LU-decomposition, and this is proven by the induction you did, with the nonsingularity being argued in the induction step rather than afterwards. – darij grinberg Oct 14 '18 at 23:47
• I like the terminology "northwestern principal minors" :) – Misha Lavrov Oct 14 '18 at 23:52

Here is an explicit proof, for the enjoyment of a commenting troll. The following goes back to Gauss, from what I've been told.

## Explicit LU-decomposition

### Theorems

Notation. Fix a commutative ring $$\mathbb{K}$$. Let $$A = \left(a_{i,j}\right)_{1\leq i\leq n,\ 1\leq j\leq m} \in \mathbb{K}^{n \times m}$$ be an $$n\times m$$-matrix over $$\mathbb{K}$$. Let $$u_1, u_2, \ldots, u_p$$ be any elements of $$\left\{1,2,\ldots,n\right\}$$. Let $$v_1, v_2, \ldots, v_q$$ be any elements of $$\left\{1,2,\ldots,m\right\}$$. Then, $$\operatorname{sub}^{v_1, v_2, \ldots, v_q}_{u_1, u_2, \ldots, u_p} A$$ shall denote the $$p\times q$$-matrix $$\left(a_{u_i, v_j}\right)_{1\leq i\leq p,\ 1\leq j\leq q} \in \mathbb{K}^{p\times q}$$.

(Thus, when $$u_1 < u_2 < \cdots < u_p$$ and $$v_1 < v_2 < \cdots < v_q$$, this matrix $$\operatorname{sub}^{v_1, v_2, \ldots, v_q}_{u_1, u_2, \ldots, u_p} A$$ is the matrix obtained from $$A$$ by crossing out all rows except for the rows numbered $$u_1, u_2, \ldots, u_p$$ and crossing out all columns except for the columns numbered $$v_1, v_2, \ldots, v_q$$. It is called a submatrix of $$A$$. This is the only case we shall use below.)

Let $$A$$ be an $$n\times n$$-matrix. Define an $$n \times n$$-matrix $$R_A =\left( b_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ by $$$$b_{i,j}=\det\left( \operatorname{sub}_{1,2,\ldots,i}^{1,2,\ldots ,i-1,j}A\right) .$$$$ Define an $$n \times n$$-matrix $$L_A =\left( \left( -1\right) ^{i+j}c_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ by $$$$c_{i,j} = \begin{cases} \det\left( \operatorname{sub}_{1,2,\ldots,\widehat{j},\ldots,i}^{1,2,\ldots,i-1}A\right) , & \text{ if } j \leq i; \\ 0, & \text{ if } j > i . \end{cases}$$$$ Here, the hat over the $$j$$ is a "magician's hat", which makes whatever comes under it disappear (so "$$1,2,\ldots,\widehat{j},\ldots,i$$" means "$$1,2,\ldots,j-1,j+1,j+2,\ldots,i$$").

Then:

Theorem 1. We have $$R_A = L_A A$$.

Proposition 2. The matrix $$R_A$$ is upper-triangular, while the matrix $$L_A$$ is lower-triangular.

We will prove these two facts below. Once they are proven, you can conclude that $$A$$ has the LU-decomposition $$A = L_A^{-1} R_A$$ when $$L_A$$ is invertible (since Proposition 2 shows that $$L_A^{-1}$$ is lower-triangular and $$R_A$$ is upper-triangular, but Theorem 1 yields $$A = L_A^{-1} R_A$$). When is $$L_A$$ invertible? The matrix $$L_A$$ is lower-triangular, so its invertibility is equivalent to the invertibility (in the base ring $$\mathbb{K}$$) of its diagonal entries. But its diagonal entries are $$c_{i,i} = \det\left( \operatorname{sub}_{1,2,\ldots,\widehat{i},\ldots,i}^{1,2,\ldots,i-1}A\right) = \det\left( \operatorname{sub}_{1,2,\ldots,i-1}^{1,2,\ldots,i-1}A\right)$$ for $$i \in \left\{1,2,\ldots,n\right\}$$, which are exactly the "proper northwestern principal minors" of $$A$$ (that is, all northwestern principal minors except for $$\det A$$ itself). Thus, you can conclude the following:

Corollary 3. If the "proper northwestern principal minors" of $$A$$ (that is, all the determinants $$\det\left( \operatorname{sub}_{1,2,\ldots,i-1}^{1,2,\ldots,i-1}A\right)$$ for $$i \in \left\{1,2,\ldots,n\right\}$$) are invertible (in the base ring $$\mathbb{K}$$), then $$A$$ has the LU-decomposition $$A = L_A^{-1} R_A$$.

Note that Corollary 3 is only a sufficient condition for the existence of an LU-decomposition. It is not a necessary one (as the example in which $$n \geq 2$$ and $$A$$ is the zero matrix shows: the zero matrix has an LU-decomposition, but for $$n \geq 2$$ it has a proper northwestern principal minor equal to $$0$$). But it is necessary if $$A$$ is invertible (since then, both the L and the U factors must be invertible, but this means that their diagonal entries are invertible; but the northwestern principal minors of $$A$$ are merely products of these diagonal entries).

### Proofs

Proof of Theorem 1. Write the $$n\times n$$-matrix $$A$$ in the form $$A=\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$.

From $$L_{A}=\left( \left( -1\right) ^{i+j}c_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ and $$A=\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$, we obtain $$$$L_{A}A=\left( \sum_{k=1}^{n}\left( -1\right) ^{i+k}c_{i,k}a_{k,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}. \label{darij1.pf.t1.LAA=} \tag{1}$$$$

We must prove that $$R_{A}=L_{A}A$$. In view of \eqref{darij1.pf.t1.LAA=} and $$R_{A}=\left( b_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$, this boils down to proving that $$$$b_{i,j}=\sum_{k=1}^{n}\left( -1\right) ^{i+k}c_{i,k}a_{k,j} \label{darij1.pf.t1.goal} \tag{2}$$$$ for each $$i\in\left\{ 1,2,\ldots,n\right\}$$ and $$j\in\left\{ 1,2,\ldots,n\right\}$$. So let us prove \eqref{darij1.pf.t1.goal}.

Fix $$i\in\left\{ 1,2,\ldots,n\right\}$$ and $$j\in\left\{ 1,2,\ldots ,n\right\}$$. Consider the $$i\times i$$-matrix $$$$\operatorname{sub}_{1,2,\ldots,i}^{1,2,\ldots,i-1,j}A=\left( \begin{array} [c]{ccccc} a_{1,1} & a_{1,2} & \cdots & a_{1,i-1} & a_{1,j}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,i-1} & a_{2,j}\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ a_{i-1,1} & a_{i-1,2} & \cdots & a_{i-1,i-1} & a_{i-1,j}\\ a_{i,1} & a_{i,2} & \cdots & a_{i,i-1} & a_{i,j} \end{array} \right) .$$$$ Expanding the determinant of this matrix along its $$i$$-th column (whose entries are the first $$i$$ entries $$a_{1,j},a_{2,j},\ldots,a_{i,j}$$ of the $$j$$-th column of $$A$$) yields \begin{align*} & \det\left( \operatorname{sub}_{1,2,\ldots,i}^{1,2,\ldots,i-1,j}A\right) \\ & =\sum_{k=1}^{i}\left( -1\right) ^{i+k}a_{k,j}\det\left( \operatorname{sub}_{1,2,\ldots,\widehat{k},\ldots,i}^{1,2,\ldots ,i-1,j}A\right) \end{align*} (indeed, if $$k\in\left\{ 1,2,\ldots,i\right\}$$, then removing the $$k$$-th row and the $$i$$-th column from the matrix $$\operatorname{sub}_{1,2,\ldots,i}^{1,2,\ldots,i-1,j}A$$ yields the matrix $$\operatorname{sub} _{1,2,\ldots,\widehat{k},\ldots,i}^{1,2,\ldots,i-1,j}A$$). Comparing this with \begin{align*} & \sum_{k=1}^{n}\left( -1\right) ^{i+k}c_{i,k}a_{k,j}\\ & =\sum_{k=1}^{i}\left( -1\right) ^{i+k}\underbrace{c_{i,k}} _{\substack{=\det\left( \operatorname{sub}_{1,2,\ldots,\widehat{k},\ldots ,i}^{1,2,\ldots,i-1}A\right) \\\text{(by the definition of }c_{i,k} \text{,}\\\text{since }k\leq i\text{)}}}a_{k,j}+\sum_{k=i+1}^{n}\left( -1\right) ^{i+k}\underbrace{c_{i,k}}_{\substack{=0\\\text{(by the definition of }c_{i,k}\text{,}\\\text{since }k>i\text{)}}}a_{k,j}\\ & =\sum_{k=1}^{i}\left( -1\right) ^{i+k}\det\left( \operatorname{sub} _{1,2,\ldots,\widehat{k},\ldots,i}^{1,2,\ldots,i-1}A\right) a_{k,j} +\underbrace{\sum_{k=i+1}^{n}\left( -1\right) ^{i+k}0a_{k,j}}_{=0}\\ & =\sum_{k=1}^{i}\left( -1\right) ^{i+k}\det\left( \operatorname{sub} _{1,2,\ldots,\widehat{k},\ldots,i}^{1,2,\ldots,i-1}A\right) a_{k,j}\\ & =\sum_{k=1}^{i}\left( -1\right) ^{i+k}a_{k,j}\det\left( \operatorname{sub}_{1,2,\ldots,\widehat{k},\ldots,i}^{1,2,\ldots ,i-1,j}A\right) , \end{align*} we obtain $$$$\sum_{k=1}^{n}\left( -1\right) ^{i+k}c_{i,k}a_{k,j}=\det\left( \operatorname{sub}_{1,2,\ldots,i}^{1,2,\ldots,i-1,j}A\right) =b_{i,j}$$$$ (by the definition of $$b_{i,j}$$). This proves \eqref{darij1.pf.t1.goal}.

Thus, $$R_{A}=L_{A}A$$ holds. This proves Theorem 1. $$\blacksquare$$

Proof of Proposition 2. For any $$i\in\left\{ 1,2,\ldots,n\right\}$$ and $$j\in\left\{ 1,2,\ldots,n\right\}$$ satisfying $$j>i$$, we have $$c_{i,j}=0$$ (by the definition of $$c_{i,j}$$) and thus $$\left( -1\right) ^{i+j} \underbrace{c_{i,j}}_{=0}=0$$. Hence, the matrix $$\left( \left( -1\right) ^{i+j}c_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ is lower-triangular. In other words, the matrix $$L_{A}$$ is lower-triangular (since $$L_{A}=\left( \left( -1\right) ^{i+j}c_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$).

It remains to prove that the matrix $$R_{A}$$ is upper-triangular. Indeed, let $$i\in\left\{ 1,2,\ldots,n\right\}$$ and $$j\in\left\{ 1,2,\ldots,n\right\}$$ be such that $$i>j$$. Hence, $$j, so that $$j\in\left\{ 1,2,\ldots ,i-1\right\}$$. Thus, the matrix $$\operatorname{sub}_{1,2,\ldots ,i}^{1,2,\ldots,i-1,j}A$$ has two equal columns (namely, its $$j$$-th column equals its $$i$$-th column). Thus, its determinant is $$0$$. In other words, $$\det\left( \operatorname{sub}_{1,2,\ldots,i}^{1,2,\ldots,i-1,j}A\right) =0$$. The definition of $$b_{i,j}$$ yields $$b_{i,j}=\det\left( \operatorname{sub}_{1,2,\ldots,i}^{1,2,\ldots,i-1,j}A\right) =0$$.

Now, forget that we fixed $$i$$ and $$j$$. We thus have shown that $$b_{i,j}=0$$ for all $$i\in\left\{ 1,2,\ldots,n\right\}$$ and $$j\in\left\{ 1,2,\ldots ,n\right\}$$ satisfying $$i>j$$. In other words, the matrix $$\left( b_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ is upper-triangular. In other words, the matrix $$R_{A}$$ is upper-triangular. This completes the proof of Proposition 2. $$\blacksquare$$

• if there is an answer here I can't tell whether it is hidden in you simply defining stuff.. – воитель Oct 15 '18 at 1:43
• See the very last sentence of the post. – darij grinberg Oct 15 '18 at 1:45
• was most of this necessary? – воитель Oct 15 '18 at 1:47
• I think it was. This is an explicit formula for the U part of the LU decomposition. – darij grinberg Oct 15 '18 at 1:48
• web.mit.edu/humor/Incoming/proof.techniques proof by cumbersome notation. – воитель Oct 15 '18 at 1:56