Understanding a proof of Cholesky's factorization

[fluidistic]

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.

 

[micromass]

Hi fluidistic!

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 &amp; x_2 &amp; ... &amp; x_n\\ \end{array}\right) =<br /> \left(\begin{array}{cccc} \sqrt{d_1} &amp; 0 &amp; ... &amp; 0\\ 0 &amp; \sqrt{d_2} &amp; ... &amp; 0\\ \vdots &amp; \vdots &amp; \ddots &amp; \vdots\\ 0 &amp; 0 &amp; ... &amp; \sqrt{d_n}\\ \end{array}\right)<br /> \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?

 

[fluidistic]

Hi micromass :D

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 &gt;0 for a_i \neq 0 but (-\sqrt a_i)\cdot (-\sqrt a_i)&gt;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 &amp; x_2 &amp; ... &amp; x_n\\ \end{array}\right) =<br /> \left(\begin{array}{cccc} \sqrt{d_1} &amp; 0 &amp; ... &amp; 0\\ 0 &amp; \sqrt{d_2} &amp; ... &amp; 0\\ \vdots &amp; \vdots &amp; \ddots &amp; \vdots\\ 0 &amp; 0 &amp; ... &amp; \sqrt{d_n}\\ \end{array}\right)<br /> \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.

 

[micromass]

Hi micromass :D
Hmm I understand that \sqrt a_i \cdot \sqrt a_i &gt;0 for a_i \neq 0 but (-\sqrt a_i)\cdot (-\sqrt a_i)&gt;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.

 

[fluidistic]

Thanks once again for the help!

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

I follow you until here

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.

 

[micromass]

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

 

[fluidistic]

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