Checking if matrix $A$ is positive definite via Cholesky decomposition

Question

How can we show that a matrix $A$ is not a positive definite matrix using the Cholesky decomposition?

If we are not able to complete the algorithm and we cannot factor the matrix with a Cholesky decomposition does it then mean that the matrix is not positiv definite?

Or is there an other way to check whether the matrix is positiv definite or not?

Answer 1

Cholesky decomposition will fail only when the matrix is not symmetric positive semi definite. Thus, if the algorithm doesn’t work, then you know your matrix is not symmetric positive semidefinite.

Answer 2

The answer to this question hinges on on the choice of arithmetic: exact or finite precision arithmetic.

In exact arithmetic arithmetic Cholesky's algorithm runs to completion and produces a lower triangular matrix $L$ with positive diagonal entries such that $A = LL^T$ if and only if $A$ is symmetric positive definite (SPD).

In finite precision arithmetic, the following two examples demonstrate that Cholesky's algorithm cannot be used to determine if a matrix is SPD. The calculations will be done in-place, i.e., I overwrite the lower triangular half of the matrices and ignore the strictly upper triangular portion. I use $\text{fl}(x)$ to denote the floating point representation of $x$.

Example 1: A matrix $M$ which is SPD for which Cholesky's algorithm fails due to rounding errors. Let $M$ be given by $$ M = \begin{bmatrix} 1 + 2u & 1 \\ 1 & 1 - u \end{bmatrix}.$$ This matrix is exactly representable. It is clear that $M$ is symmetric positive definite, because the trace is $$ \text{Tr}(M) = 2 + u > 0$$ and the determinant is $$ \text{det}(M) = u - 2u^2 > 0.$$

It is vital understand that $\text{fl}(\sqrt{1+2u}) = 1$. We have $$ 1 < 1 + 2u = (1 + u)^2 - u^2 < (1+u)^2$$ which implies $$ 1 < \sqrt{1 + 2u} < 1 + u. $$ Since there are no floating point numbers in the open interval between $1$ and $1+2u$, it follows that $1$ is the floating point number which is closest to $\sqrt{1+2u}$, i.e., $\text{fl}(\sqrt{1+2u}) = 1$.

After processing the first column of $M$ and performing the linear update of the lower right corner, we are left with $$ M^{(1)} = \begin{bmatrix} 1 & 1 \\ 1 & - u \end{bmatrix}.$$ The algorithm will now fail because the final pivot is strictly negative.

Example 2: A symmetric matrix which has a positive and a negative eigenvalue for which Cholesky's algorithm runs to completion due to rounding errors. Let $N$ be given by $$ N = \begin{bmatrix} 1 & 1-u \\ 1-u & 1-2u \end{bmatrix}.$$ The determinant is $$\text{det}(N) = -u^2 < 0.$$ It follows that one eigenvalue is strictly negative while the other eigenvalue is strictly positive.

For this example it vital to understand that $$\text{fl}((1-u)^2) = 1 - 2u.$$ After processing the first column of $N$ and completing the linear update we are left with $$N^{(1)} = \begin{bmatrix} 1 & 1-u \\ 1-u & 0 \end{bmatrix}.$$ The algorithm will now run to completion because the last pivot is not negative.

In general, if Cholesky's algorithm runs to completion, then the input matrix $A$ is close to a matrix which is symmetric positive definite. Similarly, if $A$ is symmetric positive definite and if the smallest eigenvalue is sufficiently large, then Cholesky's algorithm will run to completion. The statements can be made precise, but that is perhaps a subject for another day.

---

My first example is copied from my answer to a this related question. At the time, I had not constructed the second example presented here. I feel comfortable repeating the first example as they supplement each other nicely.