We know that a positive deﬁnite matrix has a Cholesky decomposition,but I want to know how a Cholesky decomposition can be done for positive semi-deﬁnite matrices?The following sentences come from a paper. "There are two assumptions on the speciﬁed correlation matrix R. The ﬁrst is a general assumption that R is a possible correlation matrix, i.e. that it is a symmetric positive semideﬁnite matrix with 1’s on the main diagonal. While implementing the algorithm there is no need to check positive semi-deﬁniteness directly, as we do a Cholesky decomposition of the matrix R at the very start. If R is not positive semi-deﬁnite, the Cholesky decomposition will fail." Thank you for your answer.

## 2 Answers

You can either:

use a LDL^T decomposition (see e.g. here)

deflate the kernel yourself before: that is, compute a basis $Q_2$ for the kernel, complete it to a square orthonormal matrix $Q=[Q_1 \, Q_2]$, and assemble $$ Q^TRQ=\begin{bmatrix}R_{11} & 0\\ 0 & 0\end{bmatrix}, $$ where $R_{11}$ is going to be nonsingular (and hence can be Cholesky-factored).

If you don't mind including some permutations, you can get a variant of Cholesky that still has the rank-revealing property:

$$P^T R P = R_1^T R, \quad R_1 = \begin{bmatrix} R_{11} & R_{22} \\ 0 & 0 \end{bmatrix}.$$

This is a matter of simple greedy pivoting. For the algorithm and more details, see Higham's "Cholesky Factorization".

3more comments