# What is K means objective function?

In elements of statistical learning book it is given like below image, i am not able to understand how it got to second line. Can someone help ?

## 2 Answers

It is an important statistical result to be able to show the following:

$$\sum_{i=1}^n \sum_{j=1}^n (x_i - x_j)^2 = 2n \sum_{i=1}^n (x_i - \bar{x})^2$$

The proof is with double summation:

$$\begin{eqnarray} \sum_{i=1}^n \sum_{j=1}^n (x_i - x_j)^2 &=& \sum_{i=1}^n \sum_{j=1}^n (x_i - \bar{x} + \bar{x} - x_j)^2 \\ &=& \sum_{i=1}^n \sum_{j=1}^n (x_i - \bar{x})^2 + (x_j - x_j)^2 - 2(x_i - \bar{x})(x_j - \bar{x})\\ &=& \sum_{i=1}^n \sum_{j=1}^n (x_i - \bar{x})^2 + (x_j - x_j)^2\\ &=& 2n \sum_{i=1}^n (x_i - \bar{x})^2 \end{eqnarray}$$

Where the third term in the RHS of the second line is orthogonal and sums to 0 .

• I guess second term is x_j - X¯ – Siddharth Shakya Jun 4 '18 at 20:05

It's a non-obvious thing, so you'll have to chew on the math a little bit.

First thing to do: show that it is sufficient to solve this for the one dimensional case.

It's not too hard, so this is a good exercise to practice your statistics 101 skills. Give it a try. Try approaching it from both sides, and use the binomial expansion.

The key result in here is the Konig-Huygens theorem.

• good to know that its a non obvious thing, i was like i am having to ask even obvious things nowadays – Siddharth Shakya Jun 4 '18 at 18:39