Such a decomposition exists iff A is positive definite

In summary, the discussion revolved around the Cholesky decomposition of a symmetric matrix $A$, where $A=L^TDL$ and $L$ is an upper triangular matrix with 1's on the main diagonal and $D$ is a diagonal matrix with positive elements on the diagonal. It was shown that such a decomposition exists if and only if $A$ is positive definite. Hints were given for both the forward and backward directions of the proof, with a focus on carefully considering the properties of the matrices involved and using them to establish the necessary conditions.
  • #1
mathmari
Gold Member
MHB
5,049
7
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?
 
Mathematics news on Phys.org
  • #2
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 :)
 
  • #3
$\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? 🤔
 
  • #4
There are a lot of details to get right in this proof, so let's try to walk through it together.

mathmari said:
$\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.

mathmari said:
$\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!
 
  • #5
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?
 
Last edited by a moderator:
  • #6
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.

mathmari said:
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.

mathmari said:
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.
 
  • #7
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:
 
  • #8
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$.
 
  • #9
GJA said:
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:
 
  • #10
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:
  • #11
GJA said:
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:
 
  • #12
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 :)
 
  • #13
GJA said:
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:
 
  • #14
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.
 

Related to Such a decomposition exists iff A is positive definite

1. What does it mean for a matrix to be positive definite?

A matrix is positive definite if all of its eigenvalues are positive. This means that when the matrix is multiplied by any non-zero vector, the resulting vector will always have a positive length or magnitude.

2. How is positive definiteness related to the existence of a decomposition?

A positive definite matrix can be decomposed into the product of a lower triangular matrix and its conjugate transpose, known as a Cholesky decomposition. This decomposition only exists for positive definite matrices.

3. Can a non-square matrix be positive definite?

No, a matrix must be square in order to be positive definite. This is because the definition of positive definiteness relies on the eigenvalues of the matrix, which can only be calculated for square matrices.

4. Is positive definiteness a necessary condition for a decomposition to exist?

Yes, positive definiteness is a necessary condition for a Cholesky decomposition to exist. If a matrix is not positive definite, then the decomposition cannot be calculated.

5. Are there any other types of decompositions that exist for positive definite matrices?

Yes, there are other types of decompositions that exist for positive definite matrices, such as the LU decomposition and the QR decomposition. However, the Cholesky decomposition is specifically designed for positive definite matrices and is often the preferred method for such matrices.

Similar threads

  • General Math
Replies
8
Views
815
  • General Math
Replies
12
Views
1K
Replies
22
Views
3K
Replies
13
Views
3K
  • General Math
Replies
2
Views
1K
  • Calculus
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
2K
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
Replies
7
Views
865
Back
Top