A square matrix is said to have a Cholesky decomposition if it can be written as the product of a lower triangular matrix and its transpose (conjugate transpose in the complex case); the lower triangular matrix is required to have strictly positive real entries on its main diagonal.
In this lecture we are going to prove that all positive definite matrices possess a Cholesky factorization. Moreover, the decomposition is unique.
We start with a definition.
Definition
Let
be a
matrix. We say that
possesses a Cholesky decomposition if and only if there exists a
lower triangular
matrix
such that its diagonal entries are strictly positive real numbers
and
where
denotes the conjugate
transpose of
.
When
is real (its entries have zero complex parts), then the conjugate transpose
coincides with the transpose
and the Cholesky factorization
is
Example
Consider the lower triangular
matrixand
its conjugate
transpose
Then,
the
matrix
has
the Cholesky
decomposition
Remember that a
complex matrix
is said to be positive
definite if and only if the quadratic form
is real (i.e., it has zero complex part) for any vector
and
whenever
.
We have proved that if a complex matrix is positive definite, then it is also
Hermitian.
When we restrict our attention to real vectors and matrices, then we say that
a real matrix
is positive definite if and only if
is symmetric and
for
any non-zero real vector
.
Note that, in the real case, symmetry is an explicit requirement and not a
consequence of positive definiteness.
Positive definiteness is a necessary and sufficient condition for the existence of a Cholesky factorization.
Proposition A square matrix possesses a Cholesky factorization if and only if it is positive definite.
Let us prove the "if" part, starting from
the hypothesis that
is positive definite. Since a positive definite matrix
is Hermitian (i.e.,
),
it is also normal. Therefore, it
can be diagonalized
as
where
is a unitary matrix and
is a diagonal matrix having the
eigenvalues of
on its main diagonal. Moreover, since
is positive definite, its eigenvalues are strictly positive real numbers.
Thus, we can
write
where
is a diagonal matrix such that its
-th
entry
satisfies
for
.
Therefore,
The
matrix
,
being unitary, is full-rank. The matrix
is diagonal (hence triangular) and its diagonal entries are strictly positive.
Thus, by the properties of
triangular matrices,
is full-rank . The product
of two full-rank matrices is full-rank. Therefore,
is full-rank and, as a consequence, it has a
QR
decomposition
where
is a unitary matrix and not only
is upper triangular, but it also has strictly positive real entries on its
main diagonal (remember that all square matrices have a QR decomposition, and
the latter strict positivity condition is satisfied if the matrix being
decomposed is full-rank). Thus, we
have
where
is a lower triangular matrix having strictly positive diagonal entries on its
main diagonal. Hence,
has the Cholesky
decomposition
Let
us now prove the "only if" part, starting from the hypothesis that
has a Cholesky decomposition, as in the previous equation. Since the diagonal
entries of
are strictly positive,
and
are full-rank. Therefore, for any
,
we
have
and
quadratic forms
satisfy
where
the last inequality follows from the
positive definiteness property of the
norm. Moreover, the norm
is guaranteed to be a real number. Therefore,
is positive definite.
The Cholesky factorization is unique.
Proposition
A
positive definite matrix
possesses a unique Cholesky factorization, in the sense that there exists a
unique lower triangular matrix
with strictly positive real entries on its main diagonal that
satisfies
Suppose that there exists another
decompositionThen,
we
have
and
where
the existence of the inverses
and
is guaranteed by the fact that
and
are triangular with strictly positive diagonal entries. Since
and
are lower triangular,
is lower triangular. Since
and
are upper triangular,
is upper triangular. The lower triangular matrix
can be equal to the upper triangular matrix
only if both matrices are diagonal.
Therefore,
where
is a diagonal matrix. Note
that
As
a
consequence,
Thus,
any diagonal entry of
(denote it by
)
satisfies
In
other words, the diagonal entries of
are all located on the unit circle. Moreover, they need to satisfy the
constraint
where
the diagonal entries of both
and
are real and strictly positive. The only way to satisfy this constraint by
remaining on the unit circle is to
pick
for
all
.
Therefore,
and
The Cholesky factorization of a
matrix
can be computed by directly solving the
equation
In particular, by the definition of
matrix product, the
latter equation implies
thatfor
any entry
located at the intersection of the
-th
row and
-th
column (for
and
).
Since
is lower triangular,
whenever
.
Therefore,
We derive the entries of
from the latter equation, by following the rules:
we solve one column at a time, starting from the first column
(),
and then solving the other columns in order
(
);
in each column, we first derive the diagonal entry
and then the other entries
(only for
because
when
).
By solving equation (1), we find that the diagonal entries
are
Since the entries on the main diagonal of
need to be real and strictly positive, we always choose the positive root.
Moreover, if the number under the square root is not strictly positive, then
we stop the algorithm and we conclude that
is not positive definite.
Again by solving equation (1), we find that the other entries
(for
)
are
where
we have used the fact that
because the entries on the main diagonal are real.
Example
Let us find the Cholesky factorization of
We
need to find a
matrix
such
that
We
start from the first column and its diagonal
entry
The
next entry in the first column
is
We
now move to the second column and its diagonal
entry
Therefore,
the lower triangular matrix used in the Cholesky decomposition
is
Below you can find some exercises with explained solutions.
Compute the Cholesky decomposition
of
We start from the first row. The diagonal
entry
isThe
second entry
is
and
the third one
is
We
now proceed to the second column, where we start with the
entry
The
entry below it
is
We
can now go to the third column and
find
Thus,
the triangular matrix used in the decomposition
is
Please cite as:
Taboga, Marco (2021). "Cholesky decomposition", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/Cholesky-decomposition.
Discover why thousands of students and professionals use StatLect textbooks.