# Identity for K-Means Clustering

The property (12.18) from here states that $$\frac{1}{|C_k|} \sum_{i, i' \in C_k} \sum_{j = 1}^{p} \left(x_{ij} - x_{i'j}\right)^2 = 2 \sum_{i \in C_k} \sum_{j = 1}^{p} \left(x_{ij} - \frac{1}{|C_k|} \sum_{i' \in C_k} x_{i'j}\right)^2$$ where $$|C_k|$$ denotes the number of observations in the k-th cluster. This property is used when tackling the K-means clustering optimization problem.

I can see that $$LHS = \frac{1}{|C_k|} \sum_{i \in C_k} \sum_{j = 1}^{p} \sum_{i' \in C_k} \left(x_{ij} - x_{i'j}\right)^2 = \frac{1}{|C_k|} \sum_{i \in C_k} \sum_{j = 1}^{p} \left[x_{ij}^2 + \sum_{i' \in C_k} \left(-2x_{ij}x_{i'j} + x_{i'j}^2\right)\right].$$ However, it is not clear if this is the proper way to verify the identity. Any help is greatly appreciated.

Define

$$\overline x_{kj}=\frac1{|C_k|}\sum_{i \in C_k} x_{ij} \quad\small,\,j=1,\ldots,p\,;\,k=1,\ldots,K$$

Then looks to me that

\begin{align} \sum_{i, i' \in C_k} \sum_{j = 1}^{p} \left(x_{ij} - x_{i'j}\right)^2 &=\sum_{i, i' \in C_k}\sum_{j = 1}^{p}\left\{(x_{ij}-\overline x_{kj})-(x_{i'j}-\overline x_{kj})\right\}^2 \\&=\sum_{i, i' \in C_k}\sum_{j = 1}^{p} (x_{ij}-\overline x_{kj})^2+\sum_{i, i' \in C_k}\sum_{j = 1}^{p} (x_{i'j}-\overline x_{kj})^2 \\&=2\sum_{i, i' \in C_k}\sum_{j = 1}^{p} (x_{ij}-\overline x_{kj})^2 \\&=2|C_k|\sum_{i \in C_k}\sum_{j = 1}^{p} (x_{ij}-\overline x_{kj})^2 \end{align}

The product term in the second step vanishes because

$$\sum_{i \in C_k}(x_{ij}-\overline x_{kj})=|C_k|\overline x_{kj}-|C_k|\overline x_{kj}=0$$

So I think this works the same way as the following formula does:

$$\frac1{n^2}\sum_{1\le i,j\le n}(x_i-x_j)^2=\frac{2}n\sum_{i=1}^n (x_i-\overline x)^2$$