5
$\begingroup$

I know that a conjugate gradient method is guaranteed to converge to the solution of a linear system if the matrix is positive definite. I'm working with a family of matrices that have the following properties:

  • sparse
  • symmetric
  • weakly diagonally dominant
  • invertible
  • all nonzero entries are strictly positive.

I don't think these conditions are sufficient to show that the matrix is positive definite, but I still suspect that it will converge. Are there other known conditions under which a system such as this is known to converge?

$\endgroup$
  • 1
    $\begingroup$ It depends on what you mean by "weakly diagonally dominant". Typically, the term "irreducibly diagonally dominant" guarantees positive definiteness $\endgroup$ – Guido Kanschat Aug 15 '14 at 13:26
15
$\begingroup$

The matrix you're referring to is positive definite.

The eigenvalues of the matrix must be real, because symetric matrices are equal to their own conjugate transpose, and are thus Hermitian. All eigenvalues of Hermitian matrices are real.

If all entries of the matrix are positive or zero and the matrix is weakly diagonally dominant, then all eigenvalues of the matrix must be positive or zero by Gershgorin's Circle Theorem.

If the matrix is invertible, zero cannot be an eigenvalue of the matrix by the invertible matrix theorem. This means that all eigenvalues of the matrix must be real and strictly greater than zero, which means the matrix is positive definite.

$\endgroup$
4
$\begingroup$

I think diagonal dominance + symmetry gives positive semidefinite (definite if the dominance is strict). Since you know it's invertible that gives positive definite.

Edit: The diagonal entries must be nonnegative for this to be true. (Thanks google/wikipedia!)

http://en.wikipedia.org/wiki/Diagonally_dominant_matrix

Still, you're looking good.

$\endgroup$

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.