# Sufficient conditions to ensure convergence of the conjugate gradient method

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?

• It depends on what you mean by "weakly diagonally dominant". Typically, the term "irreducibly diagonally dominant" guarantees positive definiteness Aug 15 '14 at 13:26

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.

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.