# How to identify symmetric positive definite matrices?

I'm working on a project, implementing Successive over-relaxation (SOR) method (http://en.wikipedia.org/wiki/Successive_over-relaxation) using Python. SOR can only apply if given matrix is,

1. symmetric positive-definite (SPD) OR
2. strictly or irreducibly diagonally dominant.

1.Java doc (http://www.codezealot.org/opensource/org.codezealot.matrix/docs/org/codezealot/matrix/Matrix.html#isPositiveDefinite())

If a Matrix ANxN is symmetric, then the Matrix is positive definite if

• For all i ≤ N, ai,i > 0 and
• For all i ≤ N, ai,i > ∑ ai,j, for all j ≤ N, where j ≠ i

2.Numerical Analysis for Engineering (https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/04LinearAlgebra/posdef/)

A symmetric matrix is positive definite if:

• all the diagonal entries are positive, and
• each diagonal entry is greater than the sum of the absolute values of all other entries in the corresponding row/column.

These articles says different about the second property.
So,
- What is the correct one?
- Is there any other SPD properties I can use?
- Any suggestions are also welcome.

-
The Javadoc is wrong (though if you download his source code, the source code is right); you need to take the absolute values of the off-diagonal entries. The matrix $\begin{bmatrix}1 & -100 \\ -100 & 1\end{bmatrix}$ is not positive definite. – Rahul Jul 7 '12 at 11:03
Note that this condition is sufficient but not necessary, that is, every symmetric diagonally dominant matrix is positive semidefinite, but there are positive semidefinite matrices which are not diagonally dominant. The Wikipedia article lists some other characterizations of positive definite matrices; at first glance, points 4 and 5 (principal minors and the Cholesky decomposition) can be used as a computational test. – Rahul Jul 7 '12 at 11:07
@DavideGiraudo thanks for showing it, I'll change it. – Sajith Janaprasad Jul 7 '12 at 11:10
@RahulNarain I'm using the java code as a sample/guidance. Is there any thing I should worry about? – Sajith Janaprasad Jul 7 '12 at 11:10
The Javadoc says the code tests the principal minors if the diagonal dominance test fails, and the source code does use the absolute values of the off-diagonal entries, so I don't see anything wrong there. – Rahul Jul 7 '12 at 11:13

The second criteria in both conditions are roughly restatements of Gershgorin's Circle Theorem. The JavaDoc statement is wrong in two regards: (1) it should include absolute values inside the summation $\sum_{j\neq i}|a_{i,j}|$ and (2) the summation should be run through $j \leq N$. As stated by @Marc, the condition is sufficient but not necessary.

-
I changed j < N to j ≤ N (It was a typo). So you are telling me that there are matrices don't satisfy these two conditions, but still SPD. – Sajith Janaprasad Jul 7 '12 at 11:48
Right. The second condition places bounds on the eigenvalues of the matrix. So the condition may not hold but the matrix may still be SPD. – Tpofofn Jul 7 '12 at 12:10
Thanks for the help. – Sajith Janaprasad Jul 7 '12 at 12:41

There is no such simple way to characterise positive definite matrices. You state neither criterion very clearly (what is the sum over in your first criterion?). However, as far as I can tell the second can only be a sufficient condition, not a necessary conditition; the first much weaker condition is certainly not sufficient, although maybe necessary (I didn't check). Note that the following matrix is positive definite without satisfying the second criterion $$\pmatrix{2&-1&-1&-1\\ -1&2&0&0\\ -1&0&2&0\\ -1&0&0&2\\ }$$ For true characterisations, see the Wikipedia article, notably Sylvester's criterion.

-
There was few typos on my first criterion, and I have corrected them. Please have a look at it again. I know that Sylvester's criterion is the best method to identify a SPD matrix, but it is not an efficient way (Specially in programming).Can you suggest another way other than Sylvester's criterion? – Sajith Janaprasad Jul 7 '12 at 11:34
Well, one way would be to first test one or two only sufficient but fast criteria, and if they fail, use Sylvester's criterion as fallback. You might also try a few fast necessary criteria, so that you quickly rule out positive definiteness for some matrices (e.g. if you find a negative value on the diagonal, there's no point running a more expensive test). Of course whether this is a worthwhile strategy depends on the nature of matrices you tend to get. It's worthwhile if the faster tests give a definite answer one way or the other in many cases. – celtschk Jul 7 '12 at 21:22
I still think using Sylvester's criterion is less computationally efficient than performing a Cholesky decomposition... – J. M. Jul 8 '12 at 3:38
@celtschk I implemented using Sylvester's criterion. Finding negative values on diagonal will help to optimize my code, thankx for the tip. – Sajith Janaprasad Jul 8 '12 at 19:44