Proving the sum of inner products between $N$ points ($N$ even) on the $k$-dimensional sphere $S^{k-1}$ is greater than or equal to $-N/2$ 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.
 A: 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$.
