0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ – Brian Borchers Feb 10 at 5:19
  • $\begingroup$ @BrianBorchers This is true in exact arithmetic only. Counterexamples for floating point arithmetic are given hereL math.stackexchange.com/a/3095586/307944 $\endgroup$ – Carl Christian Feb 12 at 18:50
3
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ You may be interested in some counterexamples from floating point arithmetic: math.stackexchange.com/a/3095586/307944 $\endgroup$ – Carl Christian Feb 12 at 19:13
  • $\begingroup$ Those are nice examples. But any algorithm in floating point arithmetic will have similar cases, no? $\endgroup$ – Amit Hochman Feb 13 at 6:50
  • $\begingroup$ 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. $\endgroup$ – Carl Christian Feb 13 at 9:36
3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ How would you use the SVD for this? $\endgroup$ – Amit Hochman Feb 10 at 7:55
  • $\begingroup$ 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. $\endgroup$ – Abdullah Ali Sivas Feb 10 at 16:01
  • $\begingroup$ Agree with using the $LDL^T$ factorization, which solves OP's problem and can even be faster on some architectures by avoiding square roots. $\endgroup$ – Daniel Shapero Feb 10 at 16:30
  • 1
    $\begingroup$ You may be interested in some counterexamples from floating point arithmetic: math.stackexchange.com/a/3095586/307944 $\endgroup$ – Carl Christian Feb 12 at 19:14
  • $\begingroup$ 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. $\endgroup$ – Abdullah Ali Sivas Feb 12 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.