# sum of squared distances from mean equals all-pairs sum of square distances?

In this variance based k-clustering paper they claim that for a cluster with S points:

$$|S|\sum_{i \in S}{\|x_i-\bar{x}\|^2} = \sum_{a,b \in S,\ a<b}{\|x_a-x_b\|^2}\,.$$

Why is that? can you please show me the derivation?

This can be easily seen by a change of coordinates that makes the average $\bar{x} = 0$. This can be done by translating the whole plane, preserving all distances. Since the equation depends only on distances, its validity does not change.

Let us denote $|S|$ by $n$. The left hand side becomes $n \sum_{i \in S} ||x_i||^2$. The right hand side can be simplified as follows:

$$\sum_{a < b} ||x_a - x_b||^2 = \frac{1}{2} \sum_{a, b} ||x_a - x_b||^2 = \frac{1}{2} \sum_{a, b} ||x_a||^2 + ||x_b||^2 - 2 x_a \cdot x_b$$

The first equality follows from the fact that $||x_a - x_b||^2 = ||x_b - x_a||^2$. The second is simple expansion of quadratic expression of vectors.

If you split the sum and notice that the first two terms are equal to $n \sum_{i} ||x_i||^2$. You get that $\sum_{a, b} x_a \cdot x_b = 0$. This is easy to see since:

$$\sum_{a, b} x_a \cdot x_b = \sum_{a} x_a \cdot \sum_b{} x_b = (\sum_{i} x_i)^2 = (n \bar{x})^2$$

which is zero since the mean vector is zero.

Of course this calculation is all well known as an identity on variance. If you have a random variable $x$ such that $Pr[x = x_i] = 1/n$. Then, your left hand side is $n^2 Var(x)$ and the right hand side is the right hand side of the last equation stated here.

• cool. In the first equality you used the fact that $||x_a-x_a||^2 = 0$ – ihadanny Nov 2 '16 at 8:40