1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$ – John Hughes Jun 15 '17 at 18:30
  • $\begingroup$ Over what range of $x$? If all of the $x_i$ are non-negative then it's trivially true... $\endgroup$ – Steven Stadnicki Jun 15 '17 at 18:31
  • $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Jun 15 '17 at 18:33
  • $\begingroup$ @JohnHughes: Yes and all entries on the diagonal of $A$ are 0. $\endgroup$ – user_lambda Jun 15 '17 at 18:34
  • $\begingroup$ @StevenStadnicki: I know about positive definiteness. I guess my question is: "Is $I+B$ positive semidefinite?" $\endgroup$ – user_lambda Jun 15 '17 at 18:35
1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Each $B_{ij}$ must be between 0 and 1. $\endgroup$ – user_lambda Jun 15 '17 at 18:39
  • $\begingroup$ Fixed. Sorry 'bout that! $\endgroup$ – John Hughes Jun 15 '17 at 18:51
  • $\begingroup$ Thanks for the counterexample! $\endgroup$ – user_lambda Jun 15 '17 at 18:54
  • $\begingroup$ Sure. Sorry for swapping the sign condition on $x$ and $A$ earlier. $\endgroup$ – John Hughes Jun 15 '17 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.