# How to prove the sum of squares is minimum?

Given $n$ nonnegative values. Their sum is $k$. $$x_1 + x_2 + \cdots + x_n = k$$ The sum of their squares is defined as: $$x_1^2 + x_2^2 + \cdots + x_n^2$$

I think that the sum of squares is minimum when $x_1 = x_2 = \cdots = x_n$. But I can't figure out how to prove it. Can anybody help me on this? Thanks.

• The standard method for problems of this overall shape is Lagrange multipliers, though that may be overkill in this simple case. Sep 24, 2011 at 14:37

HINT: By Cauchy-Schwarz we know

$$\left(\sum x_i y_i\right)^2 \leq \left(\sum x_i^2\right) \left(\sum y_i^2\right)$$

Take $y_i = 1$ for all $i$ to get a lower bound on $\sum x_i^2$. Then show that $x_i = \frac{k}{n}$ achieves this bound.

• Thijs, your answer also works. Thanks. Sep 24, 2011 at 15:10
• This also can be used to prove: If $\sum_{i=1}^{n}x_i=k\text{ }(x_i \le 0), \sum_{i=1}^{n}y_i=l \text{ }(y_i \le 0)$, $\sum_{i=1}^{n}x_i\cdot y_i$ minimizes when $x_1 = x_2 = ... = x_n$ and $y_1 = y_2 = ... = y_n$. Aug 28, 2016 at 5:49

Let $c = k/n$. Then, for all $(x_1,\ldots,x_n)$ such that $\sum_i x_i = k$, $$\newcommand{\s}{\sum_{i=1}^n} \s x_i^2 = \s (c + x_i - c)^2 = c^2 n + \s (x_i - c)^2 \>,$$ since $2 \s c(x_i-c) = 0$. The right-hand side is obviously minimized by taking $x_i = c$ for all $i$ and so the result follows.

I think this reeks of AM-QM inequality. The $x_i$ have a fixed arithmatic mean of $\frac{k}{n}$, while the quadratic mean: $$\sqrt{\frac{x_1^2 + \cdots + x_n^2}{n}}$$ is bounded below by that same number, which means that the sum of squares is bounded below by $\frac{k^2}{n}$, attained exactly when the $x_i$ are all equal.

• +1. For those (like me) who hadn't heard the term "quadratic mean" before; it is also known as the root mean square. Sep 24, 2011 at 20:12
• In fact, I think this is my favorite of the answers. Since $x^2_{rms}$ is $n$ times the sum of squares, and $\bar{x}$ is fixed, it's clear from the relationship $x^2_{rms} = \bar{x}^2 + \sigma_x^2$ that $x^2_{rms}$ is minimized when $\sigma_x^2 = 0$; i.e., all variables are equal. Sep 24, 2011 at 20:27
• Mike. Your explanation is nice. Sep 28, 2011 at 15:39

You can use Lagrange multipliers.

We want to minimize $\sum_{i=1}^{n} x_{i}^{2}$ subject to the constraint $\sum_{i=1}^{n} x_{i} = k$.

Set $J= \sum x_{i}^{2} + \lambda\sum_{i=1}^{n} x_{i}$. Then $\frac{\partial J}{\partial x_i}=0$ implies that $x_{i} = -\lambda/2$. Substituting this back into the constraint give $\lambda = -2k/n$. Thus $x_{i} = k/n$, as you thought.

• Quinn, Thanks for your help. Sep 24, 2011 at 14:46

If you haven't had Lagrange multipliers yet, here is the idea behind them.

If $\{x_i\}_{i=1}^n$ is a critical point, then for every vector $\{u_i\}_{i=1}^n$ so that $$\frac{\mathrm{d}}{\mathrm{d}t}\sum_{i=1}^n(x_i+tu_i)=0\tag{1}$$ at $t=0$, we also have $$\frac{\mathrm{d}}{\mathrm{d}t}\sum_{i=1}^n(x_i+tu_i)^2=0\tag{2}$$ at $t=0$.

Evaluating $(1)$ and $(2)$, this says that for every $\{u_i\}_{i=1}^n$ so that $$\sum_{i=1}^nu_i=0\tag{3}$$ we also have $$\sum_{i=1}^nx_iu_i=0\tag{4}$$ This means that $x$ is perpendicular to the space of all vectors that are perpendicular to $v$ where $v_i=1$. This means that $x$ is in the subspace spanned by $v$. Thus, the $x_i$ are all the same, and therefore, $x_i=k/n$.

More generally, if the objective function is strictly convex (objective is quadratic, check), the feasible region is convex (constraint is linear, check), and the problem is symmetric (i.e., the variables can be interchanged without changing the problem, check), then the global minimum has all the variables equal to each other. (See for, example Boyd and Vandenberghe, Convex Optimization, Exercise 4.4.). That immediately gives $x_i = \frac{k}{n}$ as well.

@Quinn Culver

Quinn Culver's answer is not enough.

It's not enough to say that $x_i=k/n$ is the local optima. Based on the Second Order Sufficiency Conditions, we need to prove $y^T\nabla_{xx}J y>0$ for all $y\ne0$ with $\nabla h(x)^Ty=0$. After some computation, we find $\nabla_{xx}J=2I$, where $I$ is the identity matrix and the vector $y$ satisfies $\nabla h(x)^Ty=0$ is $y^T1=0, \ y\ne 0$. In the end, we find $y^T\nabla_{xx}J y=2y^Ty >0$. Therefore, we prove that $x_i=k/n$ is the local optima. Furthermore, because $x_i=k/n$ is the unique solution, therefore, it is the global optima.

For the sake of completion, here's a hint to complete squares:

$$\sum \left(x_i-\frac{k}n\right)^2\ge0 \iff \sum x_i^2\ge\frac{k^2}n$$

You can prove this by induction. Start with this lemma. For $$a, b, c \geq 0$$ we have:

$$a^2 + (a + b + c)^2 \geq (a + b)^2 + (a + c)^2$$

The proof just involves expanding out all terms and noticing that there is an extra $$bc$$ term on the LHS.

Let $$m = \frac{k}{n}$$. Let $$S = \sum_{i = 1}^n x_i^2$$. Let $$M = nm^2$$. We want to show that $$S \geq M$$.

Then we can proceed by induction on the number of terms $$x_i$$ which are not equal to $$m$$. In the base case, all terms are equal to $$m$$, and so $$S = M$$, and we're done.

In the inductive case, then WLOG assume that the terms $$x_i$$ are ordered in increasing order. And so $$x_n > m$$ and therefore $$x_1 < m$$. Let $$a = x_n - m$$ and let $$b = m - x_1$$. Then:

$$x_n = x_1 + a + b$$

Now let $$x_1' = x_1 + a$$ and let $$x_n' = x_1 + b = m$$. Then by our lemma, $$x_1^2 + x_n^2 \geq x_1'^2 + x_n'^2$$. So letting $$S' = x_1'^2 + \sum_{i = 2}^{n - 1} x_i^2 + x_n'^2$$ we have that $$S \geq S'$$. Also, clearly replacing $$x_1$$ and $$x_n$$ with $$x_1'$$ and $$x_n'$$ respectively preserves the total sum $$k$$. And since $$x_n' = m$$, then the number of terms that are not equal to $$m$$ has decreased after we make the replacement. So we can apply the inductive hypothesis yielding $$S' \geq M$$. Putting it all together:

$$S \geq S' \geq M$$

And that completes the proof.