15
$\begingroup$

Let $A$ be a symmetric $n\times n$ matrix.

I found a method on the web to check if $A$ is positive definite:

$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.

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

I've a few questions.

  1. How do we prove the above statement?

  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.

  • 1
    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: http://en.wikipedia.org/wiki/Sylvester%27s_criterion2011-12-02

5 Answers 5

11

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] $.

  • 0
    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.2011-12-01
5

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"

  • 0
    Hannah, you know a fair amount in your own right. You might want to look at the text mentioned on Wikipedia, Matrix Analysis by Roger A. Horn & Charles R. Johnson. I think they have another book with slightly different title. Also Gene H. Golub & Charles F. Van Loan. Matrix Computations, 19962011-12-02
5

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.

  • 0
    @jjjjjj Multiply out both sides and compare the coefficients of $x_i^2$ and $x_ix_j$ on both sides.2017-11-11
1

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.