3
$\begingroup$

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.

  • 0
    @J.M. I read that question, but it didn't help me.2012-07-07

2 Answers 2

1

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.

  • 0
    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.2012-07-07
0

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.

  • 0
    @celtschk I implemented using Sylvester's criterion. Finding negative values on diagonal will help to optimize my code, thankx for the tip.2012-07-08