I've been going through an optimization problem, and found that the optimal solution has a certain value but now I'd like to prove its optimality. To solve it, I need to show the following inequality. Now I have $N$ points $x_1,\dots,x_N \in S^{k-1} $, where $N$ is even and $S^{k-1} = \{ x\in \mathbb{R}^k : ||x ||=1 \}$. I'd like to prove that:
\begin{align*} \sum_{i=1}^N\sum_{j=i+1}^N x_i^Tx_j \geq -\frac{N}{2}. \end{align*} Of course we have \begin{align*} x_i^Tx_j \geq -1, \end{align*}
however for more points on the sphere I just can't figure out how to go about it. Any help is much appreciated.
Let $x_i$ be $N$ unit vectors in $\Bbb R^k$. And let $x_i x_j$ denote the usual dot product. Then
$$\begin{align} 0\leqslant \left(\sum_{i=1}^N x_i\right)^2 &= \sum_{i=1}^N \sum_{j=1}^N x_i x_j \tag1 \\ &= \sum_{i=1}^N x_i^2 + \sum_{\textstyle {1\leqslant i,j \leqslant N \atop j\neq i}} \!\!\! x_i x_j \tag2\\ &= N + 2 \!\!\!\sum_{1\leqslant i < j \leqslant N} \!\!\! x_i x_j \tag 3\\ \end{align}$$
In $(1)$ is used that the dot product is positive semi-definite. The square is just multiplied out. $(2)$ splits the sum into two, one sum over $i=j$ and one sum over $i\neq j$. In $(3)$ use that $x_i^2=1$ and that the dot product is symmetric, thus can sum over indices $i < j$ provided that sum is multiplied by 2. Finally, subtract $N$ and divide by 2:
$$ \sum_{1\leqslant i < j \leqslant N} \!\!\! x_i x_j \geqslant -\frac N2 $$
which is your inequality written in a bit different notation.
Notice that nowhere is needed that $N$ is even, so the inequality holds for any $N\in\Bbb N$.
And notice that this also gives an upper bound of $(N^2-N)/2$ for the sum. This upper bound cannot be improved because it is attained if all vectors coincide, say $x_i=x_1$ so that $x_ix_j = 1$ for all $i$, $j$.