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

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.

-
This was also posted to math.SE. Please note that crossposting between SE sites is highly frowned upon - try one site first, and if you don't get a satisfactory response, ask a moderator to migrate the 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. –  Zev Chonoles Jul 27 '13 at 21:34

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$.)

-

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)$.

-

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.

-
Yes! As I thought more, I saw that the structure of $A$ is just saying $A$ is symmetric and $A 1_n = 0$ where $1_n$ is $n\times 1$ vector of $1$s, which I doubt they provides significant information regarding positive (semi-)definiteness of $A$. –  Mohammad Khosravi Jul 28 '13 at 8:31