# Such a decomposition exists iff A is positive definite

#### mathmari

##### Well-known member
MHB Site Helper
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

##### Well-known member
MHB Math Scholar
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

##### Well-known member
MHB Site Helper
$\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?

$\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

##### Well-known member
MHB Math Scholar
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?
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

##### Well-known member
MHB Site Helper
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$ ?

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?

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?

Last edited:

#### GJA

##### Well-known member
MHB Math Scholar
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$ ?
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?

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

##### Well-known member
MHB Site Helper
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?

GJA

#### GJA

##### Well-known member
MHB Math Scholar
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

##### Well-known member
MHB Site Helper
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?

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?

GJA

#### GJA

##### Well-known member
MHB Math Scholar
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$.

Last edited:

#### mathmari

##### Well-known member
MHB Site Helper
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?

#### GJA

##### Well-known member
MHB Math Scholar
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

##### Well-known member
MHB Site Helper
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?

GJA

#### GJA

##### Well-known member
MHB Math Scholar
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.