# 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.
– user856
Jul 7, 2012 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.
– user856
Jul 7, 2012 at 11:07
• @DavideGiraudo thanks for showing it, I'll change it. Jul 7, 2012 at 11:10
• @RahulNarain I'm using the java code as a sample/guidance. Is there any thing I should worry about? Jul 7, 2012 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.
– user856
Jul 7, 2012 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.
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.