I'm trying to create a program, that will decompose a matrix using the Cholesky decomposition.
The decomposition itself isn't a difficult algorithm, but a matrix, to be eligible for Cholesky decomposition, must be symmetric and positive-definite. Checking whether a matrix is symmetric is easy, but the positive part proves to be more complex.
I've read about the Sylvester's criterion, but that leads to determinants, and based on what I found on the web, those are quite extensive and hard on computers.
In a nutshell – is there something I might be missing? Due to the fact the the matrix is square or something like that, is there possibly a simpler way to determine whether it's positive?
Regards,
Paul
Best Answer
Mathcast had it; in fact, in practical work, one uses the Cholesky decomposition $\mathbf G\mathbf G^T$ for efficiently testing if a symmetric matrix is positive definite. The only change you need to make to turn your decomposition program into a check for positive definiteness is to insert a check before taking the required square roots that the quantity to be rooted is positive. If it is zero, you have a positive semidefinite matrix; if neither zero nor positive, then your symmetric matrix isn't positive (semi)definite. (Programming-wise, it should be easy to throw an exception within a loop! If your language has no way to break a loop, however, you have my pity.)
Alternatively, one uses the $\mathbf L\mathbf D\mathbf L^T$ decomposition here (an equivalent approach in the sense that $\mathbf G=\mathbf L\sqrt{\mathbf D}$); if any nonpositive entries show up in $\mathbf D$, then your matrix is not positive definite. Note that one could set things up that the loop for computing the decomposition is broken once a negative element of $\mathbf D$ is encountered, before the decomposition is finished!
In any event, I don't understand why people are shying away from using Cholesky here; the statement is "a matrix is positive definite if and only if it possesses a Cholesky decomposition". It's a biconditional; exploit it! It's exceedingly cheaper than successively checking minors or eigendecomposing, FWIW.