We have provenlink in the previous guide that a positive definite matrixlink $\boldsymbol{A}$ can be Cholesky-factorized into $\boldsymbol{A}= \boldsymbol{U}^T\boldsymbol{U}$ where $\boldsymbol{U}$ is an upper triangular matrixlink with positive diagonal entries. However, the theoremlink merely guarantees the existence of the Cholesky factorization without providing concrete steps to obtain it.

In this section, we will go over an algorithm to obtain the Cholesky factorization of a positive definite matrix and then prove its correctness and uniqueness.

Before proving the correctness of this algorithm, we will first go through a simple example for demonstration.

Solution. The first step of the Cholesky factorization is to row-reduce $\boldsymbol{A}$ by only performing the elementary row operation of adding a multiple of one row to another row below it:

The rightmost matrix in \eqref{eq:S4V5aGJ7dID0Iu3dhTc} is $\boldsymbol{U}_1$. For the second step, we divide each row of $\boldsymbol{U}_1$ by the square root of the diagonal entry in that row:

Therefore, the Cholesky factorization of $\boldsymbol{A}$ is:

As you can see, obtaining the Cholesky factorization of a positive definite matrix is quite simple!

Proving the correctness of the Cholesky Factorization algorithm

Let $\boldsymbol{A}$ be an $n\times{n}$ positive definite matrix. By theoremlink, because $\boldsymbol{A}$ is positive definite, $\boldsymbol{A}$ can be factorized as:

Because $\boldsymbol{U}^T$ and $\boldsymbol{U}$ are square matrices, their diagonals entries are the same by propertylink of matrix transpose. Let $\boldsymbol{D}$ be a diagonal matrix whose diagonal entries are those of $\boldsymbol{U}^T$ and $\boldsymbol{U}$. Suppose the diagonal entries of $\boldsymbol{D}$ are $d_1$, $d_2$, $\cdots$, $d_n$. By theoremlink, the inverse of $\boldsymbol{D}$ is another diagonal matrix whose diagonal entries are $1/d_1$, $1/d_2$, $\cdots$, $1/d_n$.

Now, taking a transpose of an upper triangular matrix yields a lower triangular matrix by theoremlink. $\boldsymbol{U}^T$ is thus a lower triangular matrix with diagonals $d_1$, $d_2$, $\cdots$, $d_n$. By theoremlink, the product $\boldsymbol{U}^T\boldsymbol{D}^{-1}$ is a lower triangular matrix whose diagonal entries are all ones since the reciprocals cancel out.

The inverse of a lower triangular matrix is also a lower triangular matrix whose diagonal entries are the reciprocal of the original matrix by theoremlink. This means that $(\boldsymbol{U}^T\boldsymbol{D}^{-1})^{-1}$ is also lower triangular with all diagonal entries equalling one. Let's denote this matrix as $\boldsymbol{L}$ like so:

Using equations \eqref{eq:W2mRvwhj6ndbox3IZK6} and \eqref{eq:i88wig70IwSLSdp0TEk}, we can evaluate $\boldsymbol{LA}$ as:

Here, the 2nd equality holds by propertylink of invertible matrices.

Remember, the following:

• $\boldsymbol{D}$ is a diagonal matrix with diagonal entries $d_1$, $d_2$, $\cdots$, $d_n$.

• $\boldsymbol{U}$ is an upper triangular matrix with diagonal entries $d_1$, $d_2$, $\cdots$, $d_n$.

By theoremlink, the product $\boldsymbol{DU}$ is an upper triangular matrix with diagonal entries $d_1^2$, $d_2^2$, $\cdots$, $d_n^2$.

Now, suppose matrix $\boldsymbol{A}$ is reduced to an upper triangular matrix $\boldsymbol{U}_1$ using only the elementary row operating of adding a multiple of one row to another row below it. The corresponding elementary matrixlink will always be a lower triangular matrix according to propertylink whose diagonal entries are all ones.

To understand why, suppose we have some $3\times3$ matrix. The elementary matrix corresponding to the elementary row operation of multiplying the first row by $5$ and then adding it to the $3$rd row is:

Notice how this is a lower triangular matrix whose diagonal entries are all ones. By propertylink, applying an elementary row operation on matrix $\boldsymbol{A}$ is equivalent to multiplying the corresponding elementary matrix to $\boldsymbol{A}$. The series of elementary row operations required to reduce $\boldsymbol{A}$ to $\boldsymbol{U}_1$ can therefore be represented by:

Where $\boldsymbol{E}_1$, $\boldsymbol{E}_2$, $\cdots$, $\boldsymbol{E}_r$ are the corresponding elementary matrices. As just discussed, these matrices are all lower triangular. The product of lower triangular matrices is also lower triangular by propertylink and the product would have diagonal entries of all ones by propertylink. This means that we can define a lower triangular matrix $\boldsymbol{L}_1$ whose diagonal entries are all ones such that:

With this, \eqref{eq:dYd9w6a3KJz4r8kLOfo} can be simplified as:

Now, consider $\boldsymbol{L}_1 \boldsymbol{U}^T_1$ below:

Here, note the following:

• the 2nd equality holds by the propertylink of matrix transpose.

• the 3rd equality uses the fact that $\boldsymbol{A}$ is symmetriclink (since $\boldsymbol{A}$ is positive definite), that is, $\boldsymbol{A}^T=\boldsymbol{A}$.

Now, define a diagonal matrix $\boldsymbol{D}_1$ whose diagonal entries are those of $\boldsymbol{U}_1$. Suppose these diagonal entries are $c_1$, $c_2$, $\cdots$, $c_n$.

Next, consider $\boldsymbol{L}_1( \boldsymbol{U}^T_1\boldsymbol{D}^{-1}_1)$ below:

Here, the 2nd equality follows by substituting in \eqref{eq:BDBiPwRKUmPsHaj6Phc}.

Let's now determine the nature of the matrix of both sides in \eqref{eq:kcPfPZHi6IgDt0TIMLQ}. We start with the left-hand side. The matrix $\boldsymbol{U}^T_1$ is lower triangular by propertylink and holds diagonal entries $c_1$, $c_2$, $\cdots$, $c_n$. Next, $\boldsymbol{D}_1^{-1}$ is a diagonal matrix whose diagonal entries are $1/c_1$, $1/c_2$, $\cdots$, $1/c_n$ by theoremlink. The product $\boldsymbol{U}^T_1 \boldsymbol{D}_1^{-1}$ is a lower triangular matrix and its diagonal entries are all ones by theoremlink. By theoremlink and theoremlink, because $\boldsymbol{L}_1$ and $\boldsymbol{U}^T_1\boldsymbol{D}_1^{-1}$ are both lower triangular matrices whose diagonal entries are all ones, we conclude that their product $\boldsymbol{L}_1(\boldsymbol{U}^T_1\boldsymbol{D}_1^{-1})$ is lower triangular with diagonal entries of ones.

Now, let's focus on the right-hand side of \eqref{eq:kcPfPZHi6IgDt0TIMLQ}. The matrix $\boldsymbol{L}^T_1$ is upper triangular by propertylink and has diagonal entries of all ones. Again, $\boldsymbol{D}_1^{-1}$ is a diagonal matrix with diagonal entries $1/c_1$, $1/c_2$, $\cdots$, $1/c_n$ by theoremlink. The product $\boldsymbol{L}^T_1\boldsymbol{D}^{-1}$ is therefore upper triangular with diagonal entries $1/c_1$, $1/c_2$, $\cdots$, $1/c_n$ by theoremlink. Because $\boldsymbol{U}_1$ is an upper triangular matrix with diagonal entries $c_1$, $c_2$, $\cdots$, $c_n$, the product $\boldsymbol{U}_1\boldsymbol{L}^T_1 \boldsymbol{D}^{-1}$ is another upper triangular matrix whose diagonal entries are ones by theoremlink.

What we have just shown is that:

• the left-hand side of \eqref{eq:kcPfPZHi6IgDt0TIMLQ} is a lower triangular matrix with diagonal entries of ones.

• the right-hand side of \eqref{eq:kcPfPZHi6IgDt0TIMLQ} is an upper triangular matrix with diagonal entries of ones.

The only way for this to hold is if both sides of \eqref{eq:kcPfPZHi6IgDt0TIMLQ} are equal to the identity matrix $\boldsymbol{I}_n$. Taking the left-hand side of \eqref{eq:kcPfPZHi6IgDt0TIMLQ}, we get:

Now, define a second diagonal matrix $\boldsymbol{D}_2$ whose diagonal entries are $\sqrt{c_1}$, $\sqrt{c_2}$, $\cdots$, $\sqrt{c_n}$. By theoremlink, $\boldsymbol{D}^2_2= \boldsymbol{D}_1$. In addition, define the following matrix:

The inverse $\boldsymbol{D}^{-1}_2$ is diagonal by theoremlink, which makes $\boldsymbol{U}$ upper triangular by theoremlink. Now, $\boldsymbol{U}^T\boldsymbol{U}$ is:

Here, note the following:

• for the 2nd equality, we used propertylink of transpose.

• for the 3rd equality, we used propertylink of diagonal matrices.

• for the 4th equality, we used propertylink of invertible matrices.

• for the 5th equality, we used the fact that $\boldsymbol{D}^2_2=\boldsymbol{D}_1$.

• for the 6th equality, we substituted \eqref{eq:mP4AEo8Q55fxNPl9BRB}.

• for the final equality, we used \eqref{eq:GM9sQFICSgDTohkl2CW}.

This completes the proof.

Proof. Let $\boldsymbol{A}$ be a positive definite matrix. Suppose there exist two distinct Cholesky factorizations of $\boldsymbol{A}$ below:

Now, let's define a matrix $\boldsymbol{D}$ below:

Our goal is to show that $\boldsymbol{D}$ is an identity matrix, which would make imply $\boldsymbol{U}_2= \boldsymbol{U}_1$. We will do this in two stages:

1. show that $\boldsymbol{D}$ is a diagonal matrix.

2. show that the diagonal entries of $\boldsymbol{D}$ are all $1$.

Let's start by showing that $\boldsymbol{D}$ is diagonal. Focus on \eqref{eq:WktRxXhdmllPm2xaRoW}. Since $\boldsymbol{U}_2$ is upper triangular, $\boldsymbol{U}^{-1}_2$ is also upper triangular by propertylink. Since $\boldsymbol{D}$ is a product of two upper triangular matrices, $\boldsymbol{D}$ is upper triangular by propertylink.

Now, equating \eqref{eq:z4xrkDH28cVaxeOr7nk} gives:

Substituting \eqref{eq:JdU1WATpAruyotT8aoY} into \eqref{eq:WktRxXhdmllPm2xaRoW} gives:

Here, $\boldsymbol{U}^T_1$ is lower triangular by propertylink, which means $(\boldsymbol{U}^T_1)^{-1}$ is also lower triangular by propertylink. Similarly, $\boldsymbol{U}^T_2$ is lower triangular by propertylink. This means that $\boldsymbol{D}$ is lower triangular by propertylink.

Since $\boldsymbol{D}$ is both an upper triangular matrix and a lower triangular matrix, $\boldsymbol{D}$ must be a diagonal matrix.

We now move on to the second stage of showing that the diagonal entries of $\boldsymbol{D}$ are all $1$. Let's take the transpose of both sides of \eqref{eq:WktRxXhdmllPm2xaRoW} to get:

Here, we used propertylink of diagonal matrices for the left-hand side and propertylink of matrix transpose for the right-hand side.

Now, go back to \eqref{eq:JdU1WATpAruyotT8aoY} and make $\boldsymbol{U}^T_1$ the subject:

Substituting \eqref{eq:G2NJRTQrr2strtGvtXG} into \eqref{eq:R0ed9PdC8DjQca29faI} gives:

Here, the 2nd equality holds by propertylink of matrix transpose. We have now established by \eqref{eq:WktRxXhdmllPm2xaRoW} and \eqref{eq:jSAAyRYX4ZsfXk8zNtx} that:

Let's rearrange the top equation to get $\boldsymbol{U}_2=\boldsymbol{D}^{-1}\boldsymbol{U}_1$ and substitute this into the bottom equation:

By propertylink, squaring a diagonal matrix $\boldsymbol{D}$ involves squaring all the diagonal entries of $\boldsymbol{D}$. If we let $d_{ii}$ represent the $i$-th diagonal entry of $\boldsymbol{D}$, then:

Let's now show that $d_{ii}$ must be positive. Recall from \eqref{eq:WktRxXhdmllPm2xaRoW} that we defined $\boldsymbol{D}$ like so:

By definitionlink of Cholesky factorization, the diagonal entries of $\boldsymbol{U}_1$ and $\boldsymbol{U}_2$ are positive. By propertylink, the diagonal entries of $\boldsymbol{U}_2^{-1}$ are the reciprocals of the diagonal entries of $\boldsymbol{U}_2$, which means that they are also positive. By propertylink, the diagonal entries of $\boldsymbol{D}$ are the pairwise product of the diagonal entries of $\boldsymbol{U}_1$ and $\boldsymbol{U}^{-1}_2$, which means that $\boldsymbol{D}$ has positive diagonal entries.

We have now established that $\boldsymbol{D}$ is equal to the identity matrix. Therefore, \eqref{eq:M4oy54M40H6KqXmxa1R} becomes:

This proves that the Cholesky factorization is unique. This completes the proof.