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

$\endgroup$
4
  • $\begingroup$ For question 2 consider $\begin{bmatrix}1&-1\\-1&1\end{bmatrix}$. $\endgroup$ Dec 1, 2011 at 22:31
  • 2
    $\begingroup$ The really truly practical method for checking positive definiteness is to see if your matrix has a Cholesky decomposition... $\endgroup$ Dec 2, 2011 at 0:51
  • 1
    $\begingroup$ 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 $\endgroup$
    – leonbloy
    Dec 2, 2011 at 1:58
  • $\begingroup$ Just to clarify, I wouldnt call Sylvester's criterion "efficient." The best way to check Sylvester's would be to try Cholesky; if it fails then youve checked Sylvester's up to machine precision...and it cost you $O(n^3)$. $\endgroup$
    – jvdillon
    Apr 2, 2020 at 17:57

5 Answers 5

23
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hannah
    Dec 1, 2011 at 23:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hannah
    Dec 1, 2011 at 23:06
  • 1
    $\begingroup$ Please show how the Gershgorin theorem proves the positive definiteness of the matrix $\endgroup$
    – dtn
    Feb 1, 2022 at 5:05
12
$\begingroup$

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

$$ H \; = \; \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \end{array} \right) . $$ This is positive by Sylvester's Law of Inertia, https://en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia

A proof is given here 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"

Later methodology, amounting to repeated completing the square:

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ P^T H P = D $$

$$\left( \begin{array}{rrr} 1 & 0 & 0 \\ - \frac{ 2 }{ 3 } & 1 & 0 \\ \frac{ 4 }{ 5 } & - \frac{ 6 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - \frac{ 2 }{ 3 } & \frac{ 4 }{ 5 } \\ 0 & 1 & - \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 0 \\ 0 & 0 & \frac{ 3 }{ 5 } \\ \end{array} \right) $$ $$ $$

$$ Q^T D Q = H $$

$$\left( \begin{array}{rrr} 1 & 0 & 0 \\ \frac{ 2 }{ 3 } & 1 & 0 \\ 0 & \frac{ 6 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 0 \\ 0 & 0 & \frac{ 3 }{ 5 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right) $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

Algorithm discussed at reference for linear algebra books that teach reverse Hermite method for symmetric matrices
https://en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia
$$ H = \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right) $$ $$ D_0 = H $$ $$ E_j^T D_{j-1} E_j = D_j $$ $$ P_{j-1} E_j = P_j $$ $$ E_j^{-1} Q_{j-1} = Q_j $$ $$ P_j Q_j = Q_j P_j = I $$ $$ P_j^T H P_j = D_j $$ $$ Q_j^T D_j Q_j = H $$

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

==============================================

$$ E_{1} = \left( \begin{array}{rrr} 1 & - \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{1} = \left( \begin{array}{rrr} 1 & - \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{1} = \left( \begin{array}{rrr} 1 & \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{1} = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 2 \\ 0 & 2 & 3 \\ \end{array} \right) $$

==============================================

$$ E_{2} = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & - \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{2} = \left( \begin{array}{rrr} 1 & - \frac{ 2 }{ 3 } & \frac{ 4 }{ 5 } \\ 0 & 1 & - \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{2} = \left( \begin{array}{rrr} 1 & \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{2} = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 0 \\ 0 & 0 & \frac{ 3 }{ 5 } \\ \end{array} \right) $$

==============================================

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ P^T H P = D $$

$$\left( \begin{array}{rrr} 1 & 0 & 0 \\ - \frac{ 2 }{ 3 } & 1 & 0 \\ \frac{ 4 }{ 5 } & - \frac{ 6 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - \frac{ 2 }{ 3 } & \frac{ 4 }{ 5 } \\ 0 & 1 & - \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 0 \\ 0 & 0 & \frac{ 3 }{ 5 } \\ \end{array} \right) $$ $$ $$

$$ Q^T D Q = H $$

$$\left( \begin{array}{rrr} 1 & 0 & 0 \\ \frac{ 2 }{ 3 } & 1 & 0 \\ 0 & \frac{ 6 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 0 \\ 0 & 0 & \frac{ 3 }{ 5 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right) $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$\endgroup$
5
  • $\begingroup$ It is a sufficient condition so necessity direction might not hold anyway ;) $\endgroup$
    – user13838
    Dec 1, 2011 at 22:45
  • $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Dec 1, 2011 at 23:01
  • $\begingroup$ 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$. $\endgroup$
    – Hannah
    Dec 2, 2011 at 0:02
  • $\begingroup$ 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, 1996 $\endgroup$
    – Will Jagy
    Dec 2, 2011 at 0:26
  • 1
    $\begingroup$ @hardmath seems fine. I also added a Sylvester approach... $\endgroup$
    – Will Jagy
    Feb 11, 2022 at 19:35
9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How do you get your formula for $x^T A x$? Can you provide more detail please? $\endgroup$
    – jjjjjj
    Nov 7, 2017 at 18:58
  • $\begingroup$ @jjjjjj Multiply out both sides and compare the coefficients of $x_i^2$ and $x_ix_j$ on both sides. $\endgroup$
    – Noah Stein
    Nov 11, 2017 at 16:54
5
$\begingroup$

This is in part a rehash of Noah Stein answer, without too much clutter. More importantly, it gives you an algorithmic way to determine what type of matrix you have.

It's easy if you follow Cholesky method in here.

A squared matrix is positive definite if it is symmetric (!) and $x^TAx>0$ for any $x\neq0$. Then by Cholesky decomposition theorem $A$ can be decomposed in exactly one way into a product

$$ A = R^TR $$

where $R$ is upper triangular and $r_{ii}>0$.

If this is true, then (see the reference!), the diagonal elements of $R$ must fulfill

$$ r_{ii} = +\sqrt{a_{ii}-\sum_{k=1}^{i-1}r_{ki}^2}\; j=i+1,\dots,n, $$

where $n$ is the real vector space dimension. If at some point this square root is either complex or zero, then $A$ cannot be positive definite.

Nice and neat! You just have to squared, take the difference and the square root to find if $A$ is positive. It is even easy to program this method even for arbitrary $n$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Please show how the Gershgorin theorem proves the positive definiteness of the matrix $\endgroup$
    – dtn
    Feb 1, 2022 at 5:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .