# Understanding a proof of Cholesky's factorization

• fluidistic
In summary, this conversation discusses a proof involving a symmetric and positive definite matrix A, and its unique factorization into a lower triangular matrix L and its transpose L^t. The proof shows that the matrix D, which is a diagonal matrix with positive entries, plays a crucial role in the factorization. The conversation also touches on demonstrating that the matrix L' obtained from the factorization is also positive definite, and the uniqueness of this factorization.
fluidistic
Gold Member

## Homework Statement

I must understand the following proof.
Let $A \in \mathbb{R}^{n \times n}$ be a symmetric and positive definite matrix.
Thus there exist a unique factorization of $A$ such that $A=LL^t$ where $L$ is a lower triangular matrix whose diagonal is positive ($l_{ii}>0$)
Demonstration:
$A=A^t$ and $x ^t A x>0$ for $x \neq 0$. This is the hypothesis on $A$.
It follows that $A$ is invertible, so $A^{-1}$ exist.
Furthermore, considering vectors of the type $x=(x_1, x_2, ..., x_k, 0, ... , 0)$ one can see that the minors of $A$ are also definite positive.
It follows from the $LU$ decomposition theorem that $A$ admits a $LU$ decomposition. In other words I can write $A=LU \Rightarrow A^t=U^t L^t \Rightarrow U^t L^t (L^t)^{-1}=U^t$ and $U(L^t)^{-1}=L^{-1}U^t$.
Where $U(L^t)^{-1}$ is an upper triangular matrix and $L^{-1}U^t$ is a lower triangular matrix. Thus there exist a diagonal matrix $D$ such that $U(L^t)^{-1}=D$.
From this, we have that $U=DL^t$. Since $A=LU$, $A=LDL^t$. Therefore $D$ is definite positive so its diagonal elements are positive.
So I can write $A= L'L'^t$ with $L'=L \sqrt D$.
Now in order to complete the proof, I must show that $L'$ is definite positive (I think it will imply that its diagonal entries are all positive). This is where I'm stuck.
I couldn't even show that $\sqrt D$ is positive definite...

Uniqueness proof:
Suppose that there exist $L_1$ such that $A=LL^t=L_1L_1^t$. Let's show that $L=L_1$.
1)Multiplying by $L^{-1}$ we get $L^t= L^{-1}L_1L_1^t$.
2)Multiplying by $(L_1)^{-1}$ we get that $L^t (L_1^t)^{-1}=L_1 ^{-1}L_1L_1^t (L_1^t)^{-1}=L^{-1}L_1=D*$ where $D*$ is diagonal with positive entries.
It follows that:
3)$L_1=LD*$
4)$L^t =D* L_1 ^t$ I don't understand how the proof reaches this
From 3) and 4), we get (I don't understand the following implication) $D*(LD*)^t=D*D*^t L^t=(D*)^2L^t \Leftrightarrow D*=I \Rightarrow L=L_1$ which complete the proof.

Any help is greatly appreciated.
P.S.:D* is a matrix. * isn't a multiplying sign.

Hi fluidistic!

fluidistic said:

## Homework Statement

I must understand the following proof.
Let $A \in \mathbb{R}^{n \times n}$ be a symmetric and positive definite matrix.
Thus there exist a unique factorization of $A$ such that $A=LL^t$ where $L$ is a lower triangular matrix whose diagonal is positive ($l_{ii}>0$)
Demonstration:
$A=A^t$ and $x ^t A x>0$ for $x \neq 0$. This is the hypothesis on $A$.
It follows that $A$ is invertible, so $A^{-1}$ exist.
Furthermore, considering vectors of the type $x=(x_1, x_2, ..., x_k, 0, ... , 0)$ one can see that the minors of $A$ are also definite positive.
It follows from the $LU$ decomposition theorem that $A$ admits a $LU$ decomposition. In other words I can write $A=LU \Rightarrow A^t=U^t L^t \Rightarrow U^t L^t (L^t)^{-1}=U^t$ and $U(L^t)^{-1}=L^{-1}U^t$.
Where $U(L^t)^{-1}$ is an upper triangular matrix and $L^{-1}U^t$ is a lower triangular matrix. Thus there exist a diagonal matrix $D$ such that $U(L^t)^{-1}=D$.
From this, we have that $U=DL^t$. Since $A=LU$, $A=LDL^t$. Therefore $D$ is definite positive so its diagonal elements are positive.
So I can write $A= L'L'^t$ with $L'=L \sqrt D$.
Now in order to complete the proof, I must show that $L'$ is definite positive (I think it will imply that its diagonal entries are all positive). This is where I'm stuck.
I couldn't even show that $\sqrt D$ is positive definite...

You know that $\sqrt{D}$ is a diagonal matrix with positive entries. What happens if you actually perform the multiplication:

$$\left(\begin{array}{cccc} x_1 & x_2 & ... & x_n\\ \end{array}\right) = \left(\begin{array}{cccc} \sqrt{d_1} & 0 & ... & 0\\ 0 & \sqrt{d_2} & ... & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & ... & \sqrt{d_n}\\ \end{array}\right) \left(\begin{array}{c} x_1\\ x_2\\ ...\\ x_n\\ \end{array}\right)$$

Do we get something >0?

Uniqueness proof:
Suppose that there exist $L_1$ such that $A=LL^t=L_1L_1^t$. Let's show that $L=L_1$.
1)Multiplying by $L^{-1}$ we get $L^t= L^{-1}L_1L_1^t$.
2)Multiplying by $(L_1)^{-1}$ we get that $L^t (L_1^t)^{-1}=L_1 ^{-1}L_1L_1^t (L_1^t)^{-1}=L^{-1}L_1=D*$ where $D*$ is diagonal with positive entries.
It follows that:
3)$L_1=LD*$
4)$L^t =D* L_1 ^t$ I don't understand how the proof reaches this

Remember the equality from in (2):

$$]L^t (L_1^t)^{-1}=L_1 ^{-1}L_1L_1^t (L_1^t)^{-1}=L^{-1}L_1=D*$$

The left and right sides say

$$]L^t (L_1^t)^{-1}=D*$$

Thus

$$L^t=D*L_1^t$$

From 3) and 4), we get (I don't understand the following implication) $D*(LD*)^t=D*D*^t L^t=(D*)^2L^t \Leftrightarrow D*=I \Rightarrow L=L_1$ which complete the proof.

Well, we know that

$$D*(LD*)^t=(D*)^2L^t$$

but from 3 and 4, we also get

$$D*(LD*)^t=D*L_1^t=L^t$$

Thus we get

$$L^t=(D*)^2L^t$$

eliminate both sides gives us

$$(D*)^2=I$$

and because the entries of D* are positive, we get

$$D*=I$$

Does that help?

Hi micromass :D
micromass said:
Hi fluidistic!
You know that $\sqrt{D}$ is a diagonal matrix with positive entries.
Hmm I understand that $\sqrt a_i \cdot \sqrt a_i >0$ for $a_i \neq 0$ but $(-\sqrt a_i)\cdot (-\sqrt a_i)>0$ too. So why would $\sqrt D$ have positive entries? I mean, $D$ could still have positive entries even though $\sqrt D$ doesn't. Or I'm wrong?
What happens if you actually perform the multiplication:

$$\left(\begin{array}{cccc} x_1 & x_2 & ... & x_n\\ \end{array}\right) = \left(\begin{array}{cccc} \sqrt{d_1} & 0 & ... & 0\\ 0 & \sqrt{d_2} & ... & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & ... & \sqrt{d_n}\\ \end{array}\right) \left(\begin{array}{c} x_1\\ x_2\\ ...\\ x_n\\ \end{array}\right)$$

Do we get something >0?
Yes :) assuming of course that $\sqrt D$ has positive entries, something I'm not yet convinced of.
Remember the equality from in (2):

$$]L^t (L_1^t)^{-1}=L_1 ^{-1}L_1L_1^t (L_1^t)^{-1}=L^{-1}L_1=D*$$

The left and right sides say

$$]L^t (L_1^t)^{-1}=D*$$

Thus

$$L^t=D*L_1^t$$
Ah right! Thanks a lot.
Well, we know that

$$D*(LD*)^t=(D*)^2L^t$$
Right.

but from 3 and 4, we also get

$$D*(LD*)^t=D*L_1^t=L^t$$
Hmm I don't get this. What did you do to 3) and 4) to reach this?

Thus we get

$$L^t=(D*)^2L^t$$

eliminate both sides gives us

$$(D*)^2=I$$

and because the entries of D* are positive, we get

$$D*=I$$

Does that help?
I follow you on all this. I didn't realize that $D*^t=D*$. Now I do.

fluidistic said:
Hi micromass :D
Hmm I understand that $\sqrt a_i \cdot \sqrt a_i >0$ for $a_i \neq 0$ but $(-\sqrt a_i)\cdot (-\sqrt a_i)>0$ too. So why would $\sqrt D$ have positive entries? I mean, $D$ could still have positive entries even though $\sqrt D$ doesn't. Or I'm wrong?

Yes :) assuming of course that $\sqrt D$ has positive entries, something I'm not yet convinced of.

I see your problem. The thing is that the square root of a positive definite D matrix is defined as the unique positive definite matrix such that it's square is D.
So $\sqrt{D}$ is actually positive definite by definition.

The thing is that we can choose many different square roots of D, for every diagonal entry we can choose $\sqrt{d_i}$ or $-\sqrt{d_i}$, but by definiton, we take the positive root.

Hmm I don't get this. What did you do to 3) and 4) to reach this?

Well, from step (3) we know that $L_1=LD*$. So exchange $LD*$ by $L_1$ in the equation $D*(LD*)^t$. This gives $D*L_1^t$. And (4) excactly says that this is $L^t$.

Thanks once again for the help!
micromass said:
I see your problem. The thing is that the square root of a positive definite D matrix is defined as the unique positive definite matrix such that it's square is D.
So $\sqrt{D}$ is actually positive definite by definition.

The thing is that we can choose many different square roots of D, for every diagonal entry we can choose $\sqrt{d_i}$ or $-\sqrt{d_i}$, but by definiton, we take the positive root.
I see. I blame myself for not knowing well the definitions!

Well, from step (3) we know that $L_1=LD*$. So exchange $LD*$ by $L_1$
in the equation $D*(LD*)^t$
Sorry to ask again, but in which equation? I don't find it.
This gives $D*L_1^t$. And (4) excactly says that this is $L^t$.
Ok I understand this.

fluidistic said:
Sorry to ask again, but in which equation?

In the equation

$$D*(LD*)^t=(D*)^2L^t$$

that you made in the beginning of (4)...

micromass said:
In the equation

$$D*(LD*)^t=(D*)^2L^t$$

that you made in the beginning of (4)...
Thanks for all your help! Yeah I had realized this when I last studied this this morning before running to university and take the final exam (woke up at 7:39 am and I'm back from there, it's 7:15 pm. 4 hours exam in the morning+2.5 hours of Fortran exam in the afternoon. Then waiting for my grade :/). I had no time to reply here but I understood the proof, thanks to you I must say :D

## 1. What is Cholesky's factorization?

Cholesky's factorization is a method used to decompose a symmetric positive definite matrix into the product of a lower triangular matrix and its transpose.

## 2. Why is Cholesky's factorization important?

Cholesky's factorization is important because it allows us to efficiently solve systems of linear equations involving symmetric positive definite matrices. It is also used in various other applications such as optimization and data analysis.

## 3. How does Cholesky's factorization work?

Cholesky's factorization works by finding the lower triangular matrix L that satisfies A = LL^T, where A is the original symmetric positive definite matrix. This is achieved by using the Cholesky decomposition algorithm, which involves taking the square root of the diagonal elements of A and then using them to calculate the entries of L.

## 4. What are the benefits of using Cholesky's factorization?

There are several benefits of using Cholesky's factorization, including faster computation time compared to other methods for solving systems of linear equations, less numerical error, and the ability to easily update the factorization if the original matrix changes.

## 5. Are there any limitations to Cholesky's factorization?

One limitation of Cholesky's factorization is that it can only be used on symmetric positive definite matrices. Additionally, if the matrix is ill-conditioned or has small eigenvalues, the factorization may be inaccurate. It also requires the matrix to be stored in memory, which can be a limitation for very large matrices.

Replies
1
Views
528
Replies
1
Views
870
Replies
15
Views
2K
Replies
1
Views
1K
Replies
4
Views
1K
Replies
1
Views
678
Replies
8
Views
7K
Replies
1
Views
9K
Replies
1
Views
2K
Replies
11
Views
1K