# $\sum_i x_i^2 +\sum_i\sum_{i\neq j}B_{ij}x_i x_j \geq 0$?

Let $0\leq B_{ij}\leq 1$. Is it true that $$\sum_i x_i^2 +\sum_i\sum_{i\neq j}B_{ij}x_i x_j \geq 0$$ for $x\in\mathbb{R}^n$? In other words, is the matrix $I+B$ (with $B_{ii}=0$) positive semidefinite?

It is true when $B_{ij}=1$ for $i\neq j$, since $$\left(\sum_i x_i\right)^2=\sum_i x_i^2 +\sum_i\sum_{i\neq j}x_i x_j \geq 0$$ but I would like to have a more general result.

• Rephrased: "Is $x^t (I + A)x \ge 0$ for $x \in S^n$, where all entries of $A$ are between $0$ and $1$, and $a_{ii} = 0$ for all $i$. – John Hughes Jun 15 '17 at 18:30
• Over what range of $x$? If all of the $x_i$ are non-negative then it's trivially true... – Steven Stadnicki Jun 15 '17 at 18:31
• The magic phrase is 'positive definite' (and 'positive semidefinite') - look for information on positive definite matrices and quadratic forms and you should be able to find useful information. – Steven Stadnicki Jun 15 '17 at 18:33
• @JohnHughes: Yes and all entries on the diagonal of $A$ are 0. – user_lambda Jun 15 '17 at 18:34
• @StevenStadnicki: I know about positive definiteness. I guess my question is: "Is $I+B$ positive semidefinite?" – user_lambda Jun 15 '17 at 18:35

No. $$B = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 0\\ 1 & 0 & 0 \end{bmatrix}\\ x = \begin{bmatrix} 1\\ -1\\ -1 \end{bmatrix}$$ Then $x^t (I+B) x = -1$, if I've calculated correctly.
• Each $B_{ij}$ must be between 0 and 1. – user_lambda Jun 15 '17 at 18:39
• Sure. Sorry for swapping the sign condition on $x$ and $A$ earlier. – John Hughes Jun 15 '17 at 19:02