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 & 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?

 

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

 

[micromass]

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

 

[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