Sufficient condition for matrix with -1 off-diagonal to be PSD

Question

Can anyone give examples of sufficient conditions for a matrix with $-1$ in all off-diagonal entries to be positive semidefinite or positive definite?

One example is when $a_{ii} \geq \sum_j \left|a_{ij}\right|$ for all $i$.

However, I was hoping for some less restrictive conditions for this special case. I am particularly interested in whether it can be shown using some form of bound on the sum of values on the diagonal.

An example matrix would be
$\left( \begin{array}{ccc} 1 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 2 \\ \end{array} \right)$

Answer 1

For every $(a_1,\ldots,a_n)$, let $Q(a_1,\ldots,a_n)$ denote any quadratic form whose matrix has diagonal $(a_1,\ldots,a_n)$ and off-diagonal entries $-1$.

For every $c\gt0$, $Q(c,a_1,\ldots,a_n)$ evaluated at $(z,x_1,\ldots,x_n)$ is $$cz^2-2\sum_izx_i+\sum_ia_ix_i^2-\sum_{i\ne j}x_ix_j=c\cdot\left(z-c^{-1}\sum_ix_i\right)^2+(1+c^{-1})\cdot R(x_1,\ldots,x_n),$$ with $$R(x_1,\ldots,x_n)=\sum_i\frac{ca_i-1}{c+1}x_i^2-\sum_{i\ne j}x_ix_j.$$ Thus:

For every $c\gt0$, the quadratic form $Q(c,a_1,\ldots,a_n)$ is nonnegative if and only if the quadratic form $Q(a_1^{(c)},\ldots,a_n^{(c)})$ is nonnegative, where, for every $a$, $$a^{(c)}=\frac{ac-1}{c+1}.$$

Applying this recursively to any quadratic form $Q(a_1,\ldots,a_n)$ shows whether it is nonnegative or not in at most $n-1$ steps. To wit, after $n-1$ steps, one arrives at some $1\times1$ quadratic form, that is, a number, and $Q(a_1,\ldots,a_n)$ is nonnegative if and only if every diagonal entry met in the process is nonnegative.

The case in your post is $Q(1,2,3)$, then, $2^{(1)}=1/2$ and $3^{(1)}=1$. Either one recognizes directly that the quadratic form $Q(1/2,1)$ is not nonnegative, or one goes one step further and one computes $(1/2)^{(1)}=-1/4$, which is negative. In any case:

The quadratic form $Q(1,2,3)$ is not nonnegative.

Note that $$\left( \begin{array}{ccc} 2&1 & 1\end{array} \right)\left( \begin{array}{ccc} 1 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 2 \\ \end{array} \right)\left( \begin{array}{c} 2\\ 1 \\ 1\end{array} \right)=-1.$$ The same approach shows that:

The quadratic form $Q(1,2,c)$ is nonnegative if and only if $c\geqslant5$.

To wit, $2^{(1)}=1/2$ and $c^{(1)}=a$ with $a=(c-1)/2$. If $c\geqslant1$, $a^{(1/2)}=(c-5)/4$, QED.