When is the symmetric product of a matrix and a diagonal matrix negative definite on $\sum_i x_i=0$?

Question

Let $A$ be a matrix and $b$ be a strictly positive vector. Denote by $B=\text{diag}(b)$, a matrix with $b$ on its diagonal and zeros elsewhere. I am interested in the symmetric matrix $$ C = AB+(AB)'. $$

Now, consider the subspace $S:\sum_i x_i=0$. I want to find sufficient conditions on $A$ such that $C$ is negative definite on $S$, i.e. for all $x\in S$ we have $x'Cx\leq -d \left\Vert x\right\Vert $ for some $d>0$.

I can show that this is true if $A$ is full of ones except for the diagonal which is full of zeros. In this case, we can write $A=O-I$, where $O$ denotes a matrix full of 1 and $I$ the identity, and $$\begin{align} x'Cx &= x'((O-I)B+((O-I)B)')x \\ &= -2x'Bx \\ &< 0. \end{align}$$ for $x\neq 0$ and where I used the fact that $x'OBx=0$.

I can find other hollow matrices $A$ (zeros on the diagonal) such that $C$ seems negative definite but there are also counterexamples, mostly when $A$ has many zeros. I am hoping that a more general result exists. I'm mostly interested in matrices $A$ that are binary, so if a result exists for these matrices it would be great.

Answer 1

$$x^T C x = 2 x^T A B x$$ But $(B x)_j = b_j x_j$, so $B x$ can be any vector with the same signs as $x$. Now for any $i \ne j$, consider $x$ of the form $x_i = 1$, $x_j = -1$, $x_k=0$ otherwise. Then $(Ax)_i = a_{ii} - a_{ij}$. If $C$ is negative definite on the subspace $S$ for all $B$, it must be that $a_{ii} \le a_{ij}$.

Answer 2

With your definition of negative definiteness, $C$ is never negative definite when $n>2$. Note that your example is not correct: you do have $x'Cx=-2x'Bx<0$ for all nonzero $x\in S$, but you cannot find $d>0$ such that $-2x'Bx\le-d\|x\|^2$ on $S$ for every positive diagonal matrix $B$. In fact, when $x'=(1,-1,0)$ and $B=\operatorname{diag}(\epsilon,\epsilon,1)$, we have $-2x'Bx=-4\epsilon>-2d=-d\|x\|^2$ when $\epsilon$ is sufficiently small.

We can obtain, however, a necessary and sufficient condition for $x'Cx$ to be $\le0$ on $S$, regardless of $B$. Let $\{e_1,\ldots,e_n\}$ be the standard basis of $\mathbb R^n$. If $C$ is negative semidefinite on $S$, then when we pass $B$ to the limit $\operatorname{diag}(e_j)$, we have $$ x'A\operatorname{diag}(e_j)\,x=\sum_ia_{ij}x_ix_j\le0\text{ on }S. $$ We claim that $a_{ij}=a_{kj}$ for every $i,k\ne j$. Suppose the contrary that $a_{ij}>a_{kj}$. Then $x=me_i+(-m-1)e_k+e_j\in S$ and $$ \lim_{m\to+\infty}\sum_ia_{ij}x_ix_j=\lim_{m\to+\infty}\left(ma_{ij}+(-m-1)a_{kj}+a_{jj}\right)=+\infty, $$ which is a contradiction to the negative semidefiniteness of $C$ on $S$.

Now, suppose all off-diagonal entries among each column are equal to each other. Then $$ \sum_ia_{ij}x_ix_j= a_{1j}\left(\sum_{i\ne j}x_i\right)x_j + a_{jj}x_j^2 =-(a_{1j}-a_{jj})x_j^2. $$ So, for this quantity to be $\le0$ on $S$, we must have $a_{jj}\le a_{1j}$. Conversely, suppose $a_{jj}\le a_{ij}=a_{kj}$ whenever $i,k\ne j$. Then $$ x'ABx=\sum_jb_{jj}x'A\operatorname{diag}(e_j)\,x=\sum_j-(a_{1j}-a_{jj})b_{jj}x_j^2 \le0. $$