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.

Let $A$ be a symmetric $(n\times n)$-matrix.

I found a nice criterion on the web to check if $A$ is positive-definite.

Namely, $A$ 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.

See https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/04LinearAlgebra/posdef/

I couldn't find a proof for this statement. I also couldn't find a reference in my linear algebra books.

Question 1. How do we prove the above statement?

Question 2. Is the following slightly weaker statement true?

A symmetric matrix $A$ is positive-definite if all the diagonal entries are positive, each diagonal entry is greater than or equal to the sum of the absolute values of all other entries in the corresponding row/column and there exists one diagonal entry which is strictly greater than the sum of the absolute values of all other entries in the corresponding row/column.

Any help is much appreciated!

share|improve this question
    
For question 2 consider $\begin{bmatrix}1&-1\\-1&1\end{bmatrix}$. –  Jonas Meyer Dec 1 '11 at 22:31
    
The really truly practical method for checking positive definiteness is to see if your matrix has a Cholesky decomposition... –  J. M. Dec 2 '11 at 0:51
    
As pointed out in some answers, be aware that this is a sufficient but not necessary condition. A sufficient and necessary condition (and quite efficient for computation) is Sylvester's criterion: en.wikipedia.org/wiki/Sylvester%27s_criterion –  leonbloy Dec 2 '11 at 1:58

4 Answers 4

up vote 4 down vote accepted

These matrices are called (strictly) diagonally dominant. The standard way to show they are positive definite is with the Gershgorin Circle Theorem. Your weaker condition does not give positive definiteness; a counterexample is $ \left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix} \right] $.

share|improve this answer
    
Can you give an example where my weaker condition fails under the assumption that, for any i, there exists a $j\neq i$ such that $a_{ij} \neq 0$? If such an example does not exist, this would mean that my second condition can be altered into a criterion for checking positive-definiteness. –  Hannah Dec 1 '11 at 23:01
    
Ow it's not possible. Assume the matrix is weakly diagonally dominant and is strictly diagonally dominant in one row AND satisfies the new condition I just specified, then the matrix is irreducible. So by the Levy–Desplanques theorem (see Wiki page), we can conclude that our matrix is positive definite. –  Hannah Dec 1 '11 at 23:06

Here is another way to see this. Define $R_i = A_{ii} - \sum_{j\neq i} \lVert A_{ij} \rVert$. Your condition is that $R_i>0$ for all $i$.

Let $s_{ij} = \frac{A_{ij}}{\lVert A_{ij}\rVert}$ be the sign of $A_{ij}$. Then you can check algebraically (just match coefficients) that for all $x\in\mathbb{R}^n$ \[x^T A x = \sum_{i=1}^n R_ix_i^2 + \sum_{i=1}^n \sum_{j>i} \lVert A_{ij}\rVert (x_i + s_{ij} x_j)^2. \] Since squares are nonnegative and the $R_i$ are assumed positive, all summands are nonnegative for all $x\in\mathbb{R}^n$. Furthermore, if $x\neq 0$ then $x_i\neq 0$ for some $i$, so $x^TAx\geq R_ix_i^2>0$. Therefore $A$ is positive definite.

This expression for $x^TAx$ can be alternatively viewed as expressing $A$ as a weighted sum $A = \sum_k c_k v_kv_k^T$, where each $c_k>0$ and each $v_k\in\mathbb{R}^n$ is a vector with support (number of nonzero entries) at most two, each of which is $\pm 1$. But $v_kv_k^T$ is always positive semidefinite for $v_k\in\mathbb{R}^n$ and positive combinations of positive semidefinite matrices are positive semidefinite. Since each $R_i>0$, we can decrease some of the $c_k$ slightly (those which correspond to the $v_k$ which are standard unit vectors) and instead write $A = cI + \sum_k c_k v_kv_k^T$ for $c>0$, which shows that $A$ is in fact positive definite.

One nice thing about this proof: Every positive definite (or semidefinite) matrix can be written as a positive combination of matrices $vv^T$, but this proof shows that for diagonally dominant matrices we can take all the $v$ to have support at most $2$. This gives some intuition for why "most" positive definite matrices are not diagonally dominant. For example if $v$ is any vector of support size at least three then for small enough $c$, $cI + vv^T$ is positive definite but not diagonally dominant.

share|improve this answer

I cannot imagine this is difficult.

Before continuing, let me add the caution that a symmetric matrix can violate your rules and still be positive definite, give me a minute to check the eigenvalues

$$ A_3 \; = \; \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \end{array} \right) , $$

Yes, that is fine, eigenvalues are $3 - \sqrt 8, \; 3, \; 3 + \sqrt 8$

A proof is given here http://planetmath.org/?op=getobj&from=objects&id=7483 as a consequence of Gershgorin's circle theorem. For additional information, see http://en.wikipedia.org/wiki/Diagonally_dominant_matrix and http://mathworld.wolfram.com/DiagonallyDominantMatrix.html or just Google "diagonally dominant symmetric"

share|improve this answer
    
It is a sufficient condition so necessity direction might not hold anyway ;) –  user13838 Dec 1 '11 at 22:45
    
Agreed. If I have no better information, I assume the person asking is an undergraduate student, and may benefit from an example that explicitly shows lack of necessity. Also, whatever the status of the person asking, other readers may benefit from such examples. –  Will Jagy Dec 1 '11 at 23:01
    
Ah, nevermind. I have the bad habit of being arrogant where I try to make a simple funny comment. Sorry again :) –  user13838 Dec 1 '11 at 23:03
    
It's alright, and although I did not realize you were being humorous, I did think you made a valid point. –  Will Jagy Dec 1 '11 at 23:09
    
This might not be very important, but the proof given on planetmath is only for strictly diagonally dominant matrices. The same proof doesn't immediately carry over to irreducibly diagonally dominant matrices. You need a slight refinement of Gerschgorin's circle theorem. In fact, you need that if an eigenvalue $\lambda$ (of a symmetric irreducible matrix) lies on the boundary of the union of the Gerschgorin circles, then all the Gerschgorin circles pass through $\lambda$. –  Hannah Dec 2 '11 at 0:02

For the two statements mentioned above, the first one is true just based on the Gershgorin Circle Theorem. But actually, the second statement is true if you add one more condition on A: matrix A is irreducible. Then the counter-example provided below is no sense any more since they are reducible.

share|improve this answer

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.