Prove that if $\sum_{i=1}^n x_i=0$ and $\sum_{i=1}^n x_i^2=1$ there exist $i,j$ such that $x_ix_j\leq -{1\over n}$

Question

Problem

Let $x_1, x_2, \ldots, x_n$ be reals such that \begin{align} \sum_{i=1}^n x_i=0 \qquad \text{ and } \qquad \sum_{i=1}^n x_i^2=1 . \end{align} Prove that there exist $i,j$ such that $x_ix_j\leq -{1\over n}$.

my attempt

I found that if there exist $x_i,x_j$ such that $$x_i\geq {1\over\sqrt{n}}, x_j\leq -{1\over \sqrt{n}} $$

then the problem solved, but I can't prove this.

Answer 1

Suppose the contrary that $x_ix_j>-\frac1n$ for all $i,j$. Then $A=xx^T+\frac1nee^T$ is an entrywise positive matrix, where $e$ denotes the all-one vector. However, as $x^Te=0$, we have $Ae=e$. Thus $e$ is a positive eigenvector of a positive matrix $A$ corresponding to the eigenvalue $\lambda=1$. Therefore, by Perron-Frobenius theorem, $\lambda$ must be equal to $\rho(A)$ and it is also a simple eigenvalue of $A$.

However, by construction, $A$ has rank $2$. Therefore the other nonzero eigenvalue of $A$ is equal to $\mu=\operatorname{trace}(A)-\lambda$. Yet, as $x^Tx=1$, we have $\operatorname{trace}(A)=2$ and in turn $\mu=2-1=1=\lambda$. Thus we arrive at a contradiction, because $\lambda$ should be simple.

Answer 2

This is basically a rewrite of the answer of @user1551 in more elementary terms. Without loss of generality we can assume that $x_1$ is minimal in $\{x_1,\ldots,x_n\}$. Then also some other coordinate is strictly greater than $x_1$. Let $c_k = x_1x_k+\tfrac1n$. Then $\sum_k c_k = 1$ and $\sum_k c_k x_k=x_1$. Not all $c_k$ can be positive, otherwise this convex combination would be greater than the minimum $x_1$.

This can also be seen by rewriting as follows: $$x_1=\sum_k c_k x_k = \sum_k c_k(x_1 + x_k-x_1) = x_1 + \sum_k c_k (x_k-x_1).$$ So either all summands $c_k(x_k-x_1)$ are zero or at least one of these is negative. Both cases imply that $c_k\leq0$ for some $k$ (note that $x_k-x_1>0$ for at least one index $k$).