Maximum value of $\sum_{i\neq j}a_ia_j$ subject to $\sum_{i=1}^n a_i=1$ 
Find the maximum value of $\sum_{i\neq j }a_ia_j$ subject to $\sum_{i=1}^n a_i=1$. Here, $a_i\in\mathbb R$, for all $i$.

Can I take $a_i>0$ for all $i$? If yes, then I can actually use AM-GM and I'm done. But if no, how do I go about it?
I have a feeling (after putting small values of $n$) that maximization of $\sum_{i\neq j}a_ia_j$ will actually involve all $a_i>0$. But can we do it rigorously?
 A: Let $S = \displaystyle \sum_{ i \neq j} a_ia_j, P = \displaystyle \sum_{i} a_i^2\implies 1 = P + S$. Also using the well-known inequality: $xy \leq \dfrac{x^2+y^2}{2}$, we have: $\dfrac{S}{2} \leq \dfrac{(n-1)P}{2}$. Thus we have:
$\dfrac{S}{2} \leq \dfrac{(n-1)(1-S)}{2}\implies nS \leq n-1 \implies S \leq \dfrac{n-1}{n}\implies S_{\text{max}} = \dfrac{n-1}{n}$
A: You can solve the whole problem with a Lagrance multiplier.
$\displaystyle \sum_{i\neq j} a_i a_j = \sum_{i,j}a_i a_j-\sum_{l}a_l a_l$
So take the derivative w/ respect to any $a_p$ like so:
$\displaystyle \partial_{a_p}\left(\sum_{i,j}a_i a_j-\sum_{l}a_l a_l  -\lambda (\sum_l a_l -1)\right) = 0$
and
$\displaystyle 2\sum_i a_i - 2a_p -\lambda = 0$
which, with the condition on the sum, reduces to
$\displaystyle 2-2a_p = \lambda$
The upshot here is that we now know that regardless of the value of $\lambda$, $\lambda$ is a constant, so all $a_p$ are equal.  The value of all $a$'s then immediately follows from the condition on the sum: $a=1/N$.  The value of the sum of of the products follows immediately:
$\displaystyle \sum_{i\neq j} a_i a_j = \frac{N-1}{N}$
