# Quantifying the failure of the Cholesky factorization test for indefinite matrices

The Cholesky factorization is the classic test to check if a matrix is positive definite. In infinite precision it is also an exact test: A matrix has a Cholesky factorization iff it is positive definite. However, in floating point arithmetic the Cholesky test is not perfect and two types of errors can (probably) be made:

1. A false positive error: The Cholesky test passes when the matrix is indefinite.

2. A false negative error: The Cholesky test fails when the matrix is positive definite.

The conditions for false negative errors is pretty well understood. For example, if a matrix $A$ is positive definite then defining $D = \hbox{diag}(A)^{1/2}$ and $A = DHD$, a false negative error is made if $\lambda_{\min}(H) \leq -n \gamma_{n+1}/(1-\gamma_{n+1})$, $\gamma_{n} = \mathcal{O}(n u)$ with $u$ being unit round off.

This is a satisfactory result because it can also be shown that the test makes no error on positive definite matrices if $\lambda_{\min}(H) > n \gamma_{n+1}/(1-\gamma_{n+1})$. For more details see theorem 10.7, page 200 of Accuracy and Stability of Numerical Algorithms By Nicholas J. Higham.

The situation seems more difficult for quantifying false positive error. On indefinite matrices the Cholesky factorization is numerically unstable so one would expect examples where an indefinite matrix (which is far from positive definite) still passes the Cholesky test. Does anyone know of an example? Can the Cholesky factorization be used in finite precision as a test without quantifying the false positive error? Is it just a highly improbable event that an indefinite matrix causes a false positive error?

-