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.

migratethe question to a different site. If you insist on posting in many sites, at least provide links to the other posts - as you can imagine, it would be frustrating for someone to put time into answering your question here, only to find out that you'd already gotten the solution elsewhere. $\endgroup$ – Zev Chonoles Jul 27 '13 at 21:34