# Necessary condition for positive-semidefiniteness — is it sufficient?

Suppose that I have a symmetric square $n\times n$ matrix $A$ such that:

$a_{ii}\geq 0$ for all $1\leq i\leq n$, and that $a_{ii}a_{jj} - a_{ij}^2 \geq 0$ for all $1\leq i\leq n$ and $i < j \leq n$.

Clearly this is a necessary condition for positive semidefiniteness because of Sylvester's criterion, and the fact that $P^TAP$ is positive semidefinite for any positive semidefinite $A$ and permutation matrix $P$.

This question hints that this condition is not sufficient. Can you list any simple counterexamples to the claim that this condition is sufficient for $A$ to be positive semidefinite? Thanks.

P.S. I won't be offended if you flag this as a duplicate, but it's the counterexamples I'm interested in, so please consider that before you flag.

-
So for example (referencing the previous question) you'd be interested in an example that satisfies the above condition but doesn't have a Cholesky decomposition ? –  Suresh Venkat Nov 11 '12 at 21:43
@SureshVenkat That would be a good example, yes. –  John Moeller Nov 11 '12 at 21:45
John, I put a third answer generalizing things. I had to do it. The voices made me. –  Will Jagy Nov 12 '12 at 1:20

Sorry for being slow. There is a good reason this did not occur to me first, but still an error of sorts. Take

$$\left( \begin{array}{rrr} 1 & -1 & -1 \\ -1 & 1 & -1 \\ -1 & -1 & 1 \end{array} \right)$$

Your conditions are fulfilled but it is evident that $-1$ is an eigenvalue with eigenvector $$\left( \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \right)$$

To get strict inequalities use some $0 < \delta < 1$ and the matrix

$$\left( \begin{array}{ccc} 1 + \delta & -1 & -1 \\ -1 & 1 + \delta & -1 \\ -1 & -1 & 1 + \delta \end{array} \right)$$ which keeps that eigenvector but now the eigenvalue is $\delta -1.$

-
This is great. I changed this one to be the accepted answer. –  John Moeller Nov 11 '12 at 23:06

$$\left( \begin{array}{rrr} 1 & -2 & -3 \\ -2 & 4 & -6 \\ -3 & -6 & 9 \end{array} \right)$$

determinant is $-144.$

If you want strict inequalities, $$\left( \begin{array}{rrr} 1001 & -2000 & -3000 \\ -2000 & 4001 & -6000 \\ -3000 & -6000 & 9001 \end{array} \right)$$

This determinant is $-143999985999.$

-
This is a great example because all of the 2x2 submatrices are p.s.d., but the matrix isn't (edit: actually I just realized that that's exactly what I asked for). May I ask how you thought of this example? –  John Moeller Nov 11 '12 at 22:13
@JohnMoeller, I mostly do integral quadratic forms in three variables. So I just programmed my calculator to do the determinant. Putting squares on the diagonal allowed your conditions, but when I had positive elements off-diagonal the determinant was $0.$ Then I realized that if I negated all off-diagonal entries, I would be subtracting off a strictly positive quantity and that would do it. –  Will Jagy Nov 11 '12 at 22:23

I won't need to show a matrix this time. For a square $n$ by $n$ matrix with $n \geq 3,$ let $M$ be the symmetric matrix with all off-diagonal entries equal to $-1$ and all diagonal entries equal to $n-2.$ It is not difficult to show, using the eigenvalues, that all the principal minors up to size $n-1$ are nonnegative, so those submatrices are positive semidefinite. However, once again we get an eigenvalue of $-1$ with the eigenvector made up of all $1$'s. To get the submatrices positive definite, make the diagonal entries $n-2+ \delta$ with $0 < \delta < 1.$

Lost my nerve: $$\left( \begin{array}{rrrr} 2 & -1 & -1 & -1 \\ -1 & 2 & -1 & -1 \\ -1 & -1 & 2 & -1 \\ -1 & -1 & -1 & 2 \end{array} \right)$$ and $$\left( \begin{array}{rrrrr} 3 & -1 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 & -1 \\ -1 & -1 & 3 & -1 & -1 \\ -1 & -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & -1 & 3 \end{array} \right)$$

Anyway, a $k$ by $k$ matrix consisting of all $1$'s has eigenvalues $0,0,0,\ldots, 0,k.$ If all the entries are $-1$ instead the eigenvalues are $0,0,0,\ldots, 0,-k.$ In order to put some number $w$ on the diagonal we need to add $(1 + w)I,$ where $I$ is the identity matrix. So the eigenvalues of the $k$ by $k$ matrix with all off-diagonal entries $-1$ and all diagonal entries $w$ are $1+w, \; 1+w, \; 1+w,\ldots, \; 1+w, \; 1 + w-k.$ This is how you quickly confirm the example above.

-