MHB Such a decomposition exists iff A is positive definite

[mathmari]

Hey!

Let $A=L^TDL$ be the Cholesky decomposition of a symmetric matrix, at which the left upper triangular $L$ hat only $1$ on the diagonal and $D$ is a diagonal matrix with positiv elements on the diagonal.

I want to show that such a decomposition exists if and only if $A$ is positive definite.

Could you give me a hint how we could show that?

If we suppose that $A=L^TDL$ is the Cholesky decomposition then if $A$ positiv definite the diagonal elements must be positiv and so the elements of $D$ are positive, or not?

 

[GJA]

Hey mathmari,

Let's start with the "forward" direction; i.e., suppose the symmetric matrix $A$ can be decomposed as $A=L^{T}DL$. To prove that $A$ is positive definite, we need to show $x^{T}Ax>0$ for any $x\neq 0$. Try calculating $x^{T}Ax$ using the decomposition to see if you can establish the necessary inequality.

For the "backwards" direction we assume $A$ is a symmetric, positive-definite matrix. According to the Cholesky decomposition, there is an upper triangular matrix $L_{0}$ such that $A = L_{0}^{T}L_{0}.$ Note that if we could write $L_{0} = D_{0}L$ for $D_{0}$ diagonal and $L$ upper triangular with 1's on the diagonal we would then have $$A = L^{T}D_{0}^{2}L = L^{T}DL,$$ where $D = D_{0}^{2}$. Hence, our goal becomes factoring $L_{0}$ in this way. Here are a few hints to hopefully help get you there:

1. Argue that since $A$ is positive definite it is invertible and therefore the diagonal elements of $L_{0}$ must be non-zero.
2. Note that multiplying a matrix on the left by a diagonal matrix scales the rows of the matrix on the right by the diagonal elements. For example, $$\begin{bmatrix} 2 & 0\\ 0 & 3\end{bmatrix} \begin{bmatrix} 1 & 2\\ 3 & 4 \end{bmatrix} = \begin{bmatrix} 2\cdot 1 & 2\cdot 2\\ 3\cdot 3 & 3\cdot 4\end{bmatrix}.$$
3. Combine points (1) and (2) above to define $L$ via $L = D_{1}L_{0}$ for an appropriately chosen $D_{1}$ (this is the part you will need to do) so that $L$ is upper triangular with 1's along the main diagonal. Then let $D_{0} = D_{1}^{-1}$, so that $L_{0} = D_{0}L$ and use the discussion outlined above to conclude $A = L^{T}DL$, where $D = D_{0}^{2}$.

I'm more than happy to help with any follow-up questions, especially if there is a step in the above process that isn't quite clear. Let me know if I can help any further :)

 

[mathmari]

$\Rightarrow$ :

Let $x\neq 0$. Then we have that:
\begin{equation*}x^{T}Ax=x^{T}L^{T}DLx=(Lx)^TDLx\end{equation*}
It holds that $(Lx)^TDLx>0$ since the eigenvalues of $D$, so the elements of the diagonal, are positiv.

So $x^{T}Ax>0$, and therefore $A$ is positive definite, right? :unsure:
$\Leftarrow$:

Argue that since $A$ is positive definite it is invertible and therefore the diagonal elements of $L_0$ must be non-zero.

If $A$ is invertible then the diagonal elements have to be non-zero, right? For this reason must the diagonal elements of $L_0$ be non-zero?

I got stuck right now. We want to show that there is a matrix $L_0$ such that $A=L_0^TL_0$, or not? Can we either way have the result that the diagonal elements of $L_0$ must be non-zero?

 

[GJA]

There are a lot of details to get right in this proof, so let's try to walk through it together.

$\Rightarrow$ :

Let $x\neq 0$. Then we have that:
\begin{equation*}x^{T}Ax=x^{T}L^{T}DLx=(Lx)^TDLx\end{equation*}
It holds that $(Lx)^TDLx>0$ since the eigenvalues of $D$, so the elements of the diagonal, are positiv.

So $x^{T}Ax>0$, and therefore $A$ is positive definite, right? :unsure:

The basic idea you've got here is correct, nicely done. Let's walk through it a bit more carefully though. Essentially there are three matrix multiplications that must happen:

1. $Lx$
2. $D(Lx)$
3. $(Lx)^{T}D(Lx)$

As you've correctly indicated, the fact that $D$ is a diagonal matrix with positive entries is important for parts (2) and (3). However, how do we know that $Lx\neq 0$? We need to come up with a reason why $Lx\neq 0$, otherwise $(Lx)^{T}D(Lx)$ could equal zero, even though $D$ is a diagonal matrix with positive entries.

$\Leftarrow$:

If $A$ is invertible then the diagonal elements have to be non-zero, right? For this reason must the diagonal elements of $L_0$ be non-zero?

I got stuck right now. We want to show that there is a matrix $L_0$ such that $A=L_0^TL_0$, or not? Can we either way have the result that the diagonal elements of $L_0$ must be non-zero?

We need to be careful here as well. To answer your question about $A$, consider the matrix $$A=\begin{bmatrix} 0 & 1\\ 1 & 0\end{bmatrix},$$ which corresponds to a reflection about the line $y=x$. This matrix swaps the basis vectors with one another and has non-zero determinant, so it is invertible. However, its main diagonal is zero. Hence, we arrive at an important conclusion: $A$ invertible does not imply the diagonal elements of $A$ need to be non-zero.

To answer your question about $L_{0}$: The matrix $L_{0}$ comes to us from the Cholesky factorization theorem, we do not need to show its existence. The Cholesky factorization theorem for a symmetric, positive definite matrix -- which we are now assuming $A$ is -- says that there is $L_{0}$ such that $A = L_{0}^{T}L_{0}$. See the "Statement" section of Cholesky Decomposition Theorem; specifically "When $A$ is symmetric,..."

Going back to step (1) in my previous post, we need to establish a few things:

• $A$ positive definite implies $A$ invertible;
• $A$ invertible implies the diagonal elements of $L_{0}$ are non-zero.

For the first bullet point, suppose $A$ is not invertible. Then there is a non-zero $x$ such that $Ax = 0.$ Can you use the assumption that $A$ is positive definite to derive a contradiction from here?

For the second bullet point, the fact that $A$ is invertible means that its determinant is non-zero. Hence, $0\neq \det(A) = \det(L_{0}^{T}L_{0}) = \det(L_{0})^{2}$ (because $\det(L_{0}^{T}) = \det(L_{0})$). Taking a square root, we see it follows that $\det(L_{0})\neq 0$. So we now know $\det(L_{0})\neq 0$ and that $L_{0}$ is an upper triangular matrix. Do you know what the relationship between these two facts is? In other words, given that $\det(L_{0})\neq 0$ and $L_{0}$ is upper triangular, can we conclude anything about the diagonal elements of $L_{0}$?

As I mentioned above, there are many details to go through on this proof. In an effort to not overload you, I will stop here for now and wait to hear what other questions you have. We'll get there!

 

[mathmari]

At the direction $\Rightarrow$ :

We have that $L$ is an upper triangular matrix with $1$s on the diagonal, so for $x\neq 0$ we know that the at $Lx$ the last component is equal to the last component of $x$, right? Do we know that this is unequal $0$ ? :unsure:At the direction $\Leftarrow$ :

Since $\det (L_0)\neq 0$ and since the determinant of an upper triangular matrix is equal to the product of the diagonal elements, all the diagonal elements must be non-zero, right? :unsure:

Then we define the diagonal matrix $D_1$ to have on the diagonal the inverse elements of the diagonal elements of $L_0$, or not?

 

[GJA]

You've correctly identified the important facts to solving this question, nicely done. In particular, the determinant of a diagonal matrix is the product of its diagonal elements is critical here.

At the direction $\Rightarrow$ :

We have that $L$ is an upper triangular matrix with $1$s on the diagonal, so for $x\neq 0$ we know that the at $Lx$ the last component is equal to the last component of $x$, right? Do we know that this is unequal $0$ ? :unsure:

Since $L$ is upper triangular with $1$'s on the diagonal, $\det(L)\neq 0$. Thus, $L$ is invertible and $Lx\neq 0.$ To simplify the notation, let $v = Lx$ and note $v\neq 0.$ Then $$x^{T}Ax = (Lx)^{T}D(Lx) = v^{T}Dv = D_{11}v_{1}^{2} + D_{22}v_{2}^{2} + \ldots + D_{nn}v_{n}^{2} > 0,$$ where the inequality follows from the fact that $v\neq 0$ and $D$ is a diagonal matrix with positive entries on the diagonal.

At the direction $\Leftarrow$ :

Since $\det (L_0)\neq 0$ and since the determinant of an upper triangular matrix is equal to the product of the diagonal elements, all the diagonal elements must be non-zero, right? :unsure:

Then we define the diagonal matrix $D_1$ to have on the diagonal the inverse elements of the diagonal elements of $L_0$, or not?

This is correct, well done! Defining $D_{1}$ in this way and $L = D_{1}L_{0}$, $L$ is upper triangular with $1$'s along the main diagonal. From here you're basically done and can refer back to my initial post on how to wrap this proof up.

 

[mathmari]

Thank you very much for your help! Now I am looking at a similar one...

Let $A=L^TL$ be the unique Cholesky factorization of a matrix. Show that such a factorization exists iff $A$ is symmetric and positive definite.

For the direction $\Rightarrow$ I have done the following:

We assume that there is a unique Cholesky factorization of $A$, $A=L^TL$.

Then $A^T=(L^TL)^T=L^TL=A$ and so $A$ is symmetric.

Let $x\neq 0$ then $x^TAx=x^TL^TLx=(Lx)^T(Lx)=\|Lx\|^2\geq 0$.

It is left to show that $x^TAx\iff x=0$. Could you give me a hint for that? Do we maybe get an information about $L$ knowing that the Cholesky decomposition is unique? Do we get that $L$ is invertible?

:unsure:

 

[GJA]

Hi mathmari,

Any time, very happy to help! Glad you were able to make sense of everything.

Great new question as well! Note: I am assuming you're using the statement of the theorem we discussed previously (see Cholesky Decomposition - Wikipedia). You'll notice that $L$ is a lower triangular matrix with real, positive values along the diagonal. As you correctly pointed out before, the determinant of a lower (or upper) triangular matrix is the product of its diagonal entries. Hence, $L$ is invertible $\Rightarrow$ $Lx\neq 0$ $\Rightarrow \|Lx\|^{2}>0$ for $x\neq 0$.

 

[mathmari]

Great new question as well! Note: I am assuming you're using the statement of the theorem we discussed previously (see Cholesky Decomposition - Wikipedia). You'll notice that $L$ is a lower triangular matrix with real, positive values along the diagonal. As you correctly pointed out before, the determinant of a lower (or upper) triangular matrix is the product of its diagonal entries. Hence, $L$ is invertible $\Rightarrow$ $Lx\neq 0$ $\Rightarrow \|Lx\|^{2}>0$ for $x\neq 0$.

Ahh so if we are considering a unique Cholesky decomposition then the diagonal elements of $L$ must be positive, right?

Ok! Now the direction $\Rightarrow$ is clear!

Let's consider the other direction. We suppose that $A$ is a symmetric and positive definite matrix.
For this direction do we have to show the uniqueness of the decomposition or also the existence? :unsure:

If we have to show just the uniqueness, then we assume that there are two different Cholesky decompositions for $A$, let $A=L^TL$ and $A=P^TP$. Then we have that $L^TL=P^TP\Rightarrow LP^{-1}=(L^T)^{-1}P^T$.
$L$ and $P$ are lower triangular matrices, and so also $P^{-1}$.
$L^T$ and $P^T$ are upper triangular matrices, and so also $(L^T)^{-1}$.
The products $LP^{-1}$ and $(L^T)^{-1}P^T$ can be equal only if they are diagonal matrices, i.e. $LP^{-1}=(L^T)^{-1}P^T=D$.
We have that $LP^{-1}=D\Rightarrow L=DP$. Therefore: $$L^TL=P^TP\Rightarrow (DP)^T(DP)=P^TP \Rightarrow P^TD^TDP=P^TP\Rightarrow P^TD^2P=P^TP$ \Rightarrow D^2=I \Rightarrow D=I$$ That means that $LP^{-1}=I$, i.e. $L=P$, which means that the Choesky decmposition is unique.

Is everything correct? :unsure:

 

[GJA]

That is a very nice argument!

A small but important comment: $D^{2} = I$ does not imply $D = I$; e.g., consider $D = -I$. The key to the uniqueness, then, is that $L$ must have positive elements along the main diagonal. Combining this -- via $L = DP$ -- with $D^{2} = I$ does imply $D=I$, as desired.

To expand briefly on the above: you've discovered that if we remove the positivity requirement on $L$'s diagonal, then there are actually $2^{n}$ "Cholesky" factorizations of an $n\times n$ symmetric positive definite matrix because the $n$ diagonal terms of $D$ can be $\pm 1$. For example, consider the matrix $$\begin{bmatrix}1 & 2\\ 2 & 14 \end{bmatrix}.$$ Then $$\begin{bmatrix}1 & 0\\ 2 & 3 \end{bmatrix},\,\,\begin{bmatrix}-1 & 0\\ -2 & 3 \end{bmatrix},\,\,\begin{bmatrix}1 & 0\\ 2 & -3 \end{bmatrix},\,\,\text{and}\,\,\begin{bmatrix}-1 & 0\\ -2 & -3 \end{bmatrix}$$ are all possible choices for $L$ in the "Cholesky" factorization of $A$.

 

[mathmari]

A small but important comment: $D^{2} = I$ does not imply $D = I$; e.g., consider $D = -I$. The key to the uniqueness, then, is that $L$ must have positive elements along the main diagonal. Combining this -- via $L = DP$ -- with $D^{2} = I$ does imply $D=I$, as desired.

To expand briefly on the above: you've discovered that if we remove the positivity requirement on $L$'s diagonal, then there are actually $2^{n}$ "Cholesky" factorizations of an $n\times n$ symmetric positive definite matrix because the $n$ diagonal terms of $D$ can be $\pm 1$. For example, consider the matrix $$\begin{bmatrix}1 & 2\\ 2 & 14 \end{bmatrix}.$$ Then $$\begin{bmatrix}1 & 0\\ 2 & 3 \end{bmatrix},\,\,\begin{bmatrix}-1 & 0\\ -2 & 3 \end{bmatrix},\,\,\begin{bmatrix}1 & 0\\ 2 & -3 \end{bmatrix},\,\,\text{and}\,\,\begin{bmatrix}-1 & 0\\ -2 & -3 \end{bmatrix}$$ are all possible choices for $L$ in the "Cholesky" factorization of $A$.

Ahh ok! I have also an other question. At the direction $\Leftarrow$ do we have to show also the existence of the Cholesky decomposition? Or only the uniqueness? :unsure:

 

[GJA]

Indeed, we need to prove the existence of the decomposition as well. There are a few different options for that. If you're able to make use of the work we did on the previous exercise in this post, I would suggest starting there. If your assignment requires a more constructive approach (i.e., not using the previous exercise), we can discuss that as well :)

 

[mathmari]

Indeed, we need to prove the existence of the decomposition as well. There are a few different options for that. If you're able to make use of the work we did on the previous exercise in this post, I would suggest starting there. If your assignment requires a more constructive approach (i.e., not using the previous exercise), we can discuss that as well :)

But at the previous exercise we said that teh Cholesky decomposition exists and we showed the properties that the matrix $L$ has.
What do we have to do in this case? The same? Or do we have to show also that it exists and then that $L$ has the specific properties? :unsure:

 

[GJA]

Yes, you're 100% right. Given how we argued previously, we should provide a constructive proof for the existence of the Cholesky decomposition. One method for doing this is to use induction on the dimension of the matrix $A$.

Base Case
Suppose $A=[a] = a$ is a $1\times 1$ symmetric, positive definite matrix. $A$ positive definite here means $a>0$. Taking $L=\sqrt{a}$ completes the base case proof.

Inductive Step
Suppose that every $n\times n$ symmetric, positive definite matrix admits a Cholesky decomposition. Now, let $A$ be an $(n+1)\times (n+1)$ symmetric, positive definite matrix, and write $$A=\begin{bmatrix}a_{11} & x^{T} \\ x & \tilde{A} \end{bmatrix},$$ where $x$ is an $n\times 1$ matrix/vector and $\tilde{A}$ is $n\times n$. Note that $A$ being symmetric implies $\tilde{A}$ is also symmetric and that $A$ being positive definite implies $a_{11}>0$ (Hint: consider $e_{1}^{T}Ae_{1}$>0 to prove this).

The key technique is now to consider the matrix defined by $$S = \tilde{A} - \frac{1}{a_{11}}xx^{T}.$$ This matrix is called the Schur complement of $A$ and, intuitively, it is like we took a determinant of $A$'s block form and divided it by $a_{11}.$ I will let you pick up the proof at this point. What you'll need to do is show that $S$ is a symmetric, positive definite matrix $n\times n$ matrix. Once we've established that, we can discuss how to utilize the induction hypothesis to define $L$ and complete the proof. Certainly feel free to let me know if you have any questions about this going forward.