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.

So I want identify that given matrix is SPD or not.I found two articles about this.

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.
- What is the correct one?
- Is there any other SPD properties I can use?
- Any suggestions are also welcome.

Thank you in advance. Sorry for my bad English.

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

2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$ Jul 7, 2012 at 11:48
  • $\begingroup$ 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. $\endgroup$
    – Tpofofn
    Jul 7, 2012 at 12:10

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.

  • $\begingroup$ 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? $\endgroup$ Jul 7, 2012 at 11:34
  • $\begingroup$ 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. $\endgroup$
    – celtschk
    Jul 7, 2012 at 21:22
  • $\begingroup$ I still think using Sylvester's criterion is less computationally efficient than performing a Cholesky decomposition... $\endgroup$ Jul 8, 2012 at 3:38
  • $\begingroup$ @celtschk I implemented using Sylvester's criterion. Finding negative values on diagonal will help to optimize my code, thankx for the tip. $\endgroup$ Jul 8, 2012 at 19:44

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.