A nice necessary and sufficient condition on positive semi-definiteness of a matrix with a special structure

Question

Let $$ A = \begin{pmatrix} \sum_{j\ne 1}a_{1j} & -a_{12} & \cdots & -a_{1n}\\ -a_{21} & \sum_{j\ne 2}a_{2j} & \cdots & -a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ -a_{n1} & -a_{n2} & \cdots & \sum _{j\ne n}a_{nj}\\ \end{pmatrix} $$ be an $n$ by $n$ symmetric matrix, i.e. for all distinct $i,j \in \{1,2, \ldots, n\}$, we have that $a_{ij} = a_{ji}$.

Here is the question: Is there any nice necessary and sufficient condition for positive semi-definiteness of $A$?

*) Note that the non-negativity of $a_{ij}$s is a sufficient condition, since then $A$ is a diagonally dominant matrix.

**) Also note that if $f({\rm x}) = {\rm x}^T A {\rm x}$, then $ f({\rm x}) = \sum_{i<j} a_{ij} (x_i - x_j)^2 $. Considering this quadratic form might be useful.

Answer 1

Such a matrix can be written in block form: $$ \mathbf{A} = \begin{pmatrix}\mathbf{B} & -\mathbf{B1}_{n-1}\\-\mathbf{1}_{n-1}^T \mathbf{B} & \mathbf{1}_{n-1}^T \mathbf{B} \mathbf{1}_{n-1} \end{pmatrix} $$ where $\mathbf{B}$ is an arbitrary symmetric matrix of size $n-1 \times n-1$. It's easy to show that $\mathbf{A}$ is positive semidefinite if and only if $\mathbf{B}$ is. (Of course, this argument applies to any principal submatrix of size $n-1$.)

Answer 2

This is more of a comment than the answer, but it's a bit too long to fit in the comments area.

It was suggested on math.SE that a fortunate combination of $x_k$ should be found if any $a_{ij}$ is negative, so that $f(x) < 0$. However, this is not the case. For example:

$$A = \begin{bmatrix} 1 & -2 & 1 \\ -2 & 2+x & -x \\ 1 & -x & -1+x \end{bmatrix}.$$

It is easy to see that for $x \ge 2$ all the eigenvalues of $A$ are nonnegative, even though $a_{13} = -1 < 0$. This means that there are some positive semidefinite matrices $A$ that have $a_{ij} < 0$ for some $(i,j)$.

Answer 3

I very much doubt that a necessary and sufficient condition exists. For example, for finite element approximations to the Laplacian in a planar domain, you will get the (potentially non-zero) off-diagonal elements corresponding to the edges of the triangulation, and the weight $a_{ij}$ will be equal to the sum of cotangents of the two angles opposite that edge. This will be positive if and only if the sum of the opposite angles is less than $\pi,$ which means that the triangulation is a Delaunay triangulation. However, the finite element approximation will always be positive semi-definite.