# A proof of within-cluster sum of squares?

Anyone can provide a proof of the following equation as in @cardinal 's answer?

$$x_i$$ and $$x_j$$ are vectors from the same clusters。

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

If we extract the inside of the 2nd expression above: $$||(x_i-\bar{x})-(x_j-\bar{x})||^2=||x_i-\bar{x}||^2+||x_j-\bar{x}||^2-2(x_i-\bar{x})^T(x_j-\bar{x})$$ Due to symmetry, we can evaluate the first two expressions easily: $$\sum_{i\neq j}||x_i-\bar{x}||^2=\sum_{i\neq j}||x_j-\bar{x}||^2=(n-1)\sum_{i=1}^n||x_i-\bar{x}||^2$$ The last expression is:
(Note that $$\sum_{j\neq i}(x_j-\bar{x})=[\sum_{j=1}^n(x_j-\bar{x})]-(x_i-\bar{x})=n\bar{x}-n\bar{x}-(x_i-\bar{x})=-(x_i-\bar{x})$$) $$\sum_{i\neq j}{-2(x_i-\bar{x})^T}{(x_j-\bar{x})}=-2\sum_{i=1}^n(x_i-\bar{x})^T\sum_{j\neq i}(x_j-\bar{x})=2\sum_{i=1}^n(x_i-\bar{x})^T(x_i-\bar{x})\\ =2\sum_{i=1}^{n}{||x_i-\bar{x}||^2}$$
Finally, combining all, we have $$(2(n-1)+2)\sum||x_i-\bar{x}||^2=2n\sum||x_i-\bar{x}||^2$$