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.
Best Answer
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.