# Given a symmetric matrix, is it ok to apply Cholesky decomposition to see if it has negative eigenvalues?

I intend to check the diagonal of L, where A = L'L, for negative elements. However, I don't know if Cholesky is meaningful in theoretical / computational sense if there are some negative eigenvalues.

• The Cholesky factorization will simply fail (due to taking the square root of a negative real number) if the matrix is not positive semidefinite. You'll never see negative entries on the diagonal of $L$. Feb 10 at 5:19
• @BrianBorchers This is true in exact arithmetic only. Counterexamples for floating point arithmetic are given hereL math.stackexchange.com/a/3095586/307944 Feb 12 at 18:50

Using the Cholesky decomposition is the quickest way I know of checking if a symmetric matrix has negative eigenvalues. Nothing wrong with that. Plus, if it succeeds, you already have the Cholesky decomposition! Of course, if there are any negative eigenvalues, it will fail. You will not need to check the entries of $$L$$.

• You may be interested in some counterexamples from floating point arithmetic: math.stackexchange.com/a/3095586/307944 Feb 12 at 19:13
• Those are nice examples. But any algorithm in floating point arithmetic will have similar cases, no? Feb 13 at 6:50
• Thank you for your kind words. Yes and no. Almost all algorithms work almost always, but there is no harm in repeating that point frequently. There are well-conditioned linear systems that cannot be solved and well-conditioned eigenvectors that cannot be computed due to the limitations of floating-point arithmetic. It doesn't matter, until the day where it suddenly does. Feb 13 at 9:36

Cholesky factorization is for symmetric positive definite matrices, and it will fail if the matrix has negative eigenvalues. You should use singular value decomposition for that purpose, or maybe a QR algorithm would suffice if you just need some of the eigenvalues.

Edit 1: Of course, I should also add that, in general, L would not give you much information aside from what you would obtain through Sylvester's law of inertia.

Edit 2: I just thought that you may be calling LDLT algorithm, which is a generalization of Cholesky factorization, as the Cholesky factorization. In which case, you can use Sylvester's law of inertia to see if there are any negative eigenvalues.

• How would you use the SVD for this? Feb 10 at 7:55
• You are right, that was bad judgment. Singular values of a symmetric matrix would be the absolute value of its eigenvalues, and that wouldn't give us sign information. Feb 10 at 16:01
• Agree with using the $LDL^T$ factorization, which solves OP's problem and can even be faster on some architectures by avoiding square roots. Feb 10 at 16:30
• You may be interested in some counterexamples from floating point arithmetic: math.stackexchange.com/a/3095586/307944 Feb 12 at 19:14
• I upvoted your answer, it is a good one. In a different way, it justifies the answer above. If Cholesky factorization does not fail, you can not actually say that there aren't any negative eigenvalues. And if it fails, that does not necessarily mean that the matrix is not SPD. Feb 12 at 20:16