Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.
So,
- 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.

share|improve this question
1  
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
2  
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
show 3 more comments

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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