3
$\begingroup$

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?

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

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.)

$\endgroup$
  • $\begingroup$ 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'$). $\endgroup$ – darij grinberg Oct 14 '18 at 23:40
  • $\begingroup$ 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). $\endgroup$ – Misha Lavrov Oct 14 '18 at 23:44
  • $\begingroup$ But I'll edit to make this more precise. $\endgroup$ – Misha Lavrov Oct 14 '18 at 23:44
  • $\begingroup$ 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. $\endgroup$ – darij grinberg Oct 14 '18 at 23:47
  • $\begingroup$ I like the terminology "northwestern principal minors" :) $\endgroup$ – Misha Lavrov Oct 14 '18 at 23:52
0
$\begingroup$

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 \begin{equation} b_{i,j}=\det\left( \operatorname{sub}_{1,2,\ldots,i}^{1,2,\ldots ,i-1,j}A\right) . \end{equation} 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 \begin{equation} 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} \end{equation} 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 \begin{equation} 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} \end{equation}

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 \begin{equation} 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} \end{equation} 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 \begin{equation} \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) . \end{equation} 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 \begin{equation} \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} \end{equation} (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<i$, 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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.