Lloyd iteration is objective-decreasing and terminates

Fix the current centers. For each observation, the old label is one of the available centers, so choosing a nearest center cannot increase its squared distance. If the label changes, its new distance is strictly smaller: an equal-distance tie would retain the old label by [F2]. Summing the pointwise inequalities gives nonincrease of $J$, strict when any label changes.

Fix a nonempty cluster $C$ and set $T(u)=(u{)}_{i\in C}$ from ${\mathbb{R}}^p$ to $({\mathbb{R}}^p{)}^C$, with product inner product, and $b=(x_i{)}_{i\in C}$. For $u,v\in {\mathbb{R}}^p$, $⟨Tu,Tv⟩=\mathrm{\mid }C\mathrm{\mid }⟨u,v⟩$, so $T^{\ast }T=\mathrm{\mid }C\mathrm{\mid }I$; also $⟨Tu,b⟩=⟨u,{\sum }_{i\in C}{x}_i⟩$, so $T^{\ast }b={\sum }_{i\in C}{x}_i$. Minimizing $\mathrm{\parallel }Tu-b\mathrm{\parallel }$ is equivalent to minimizing its square, since squaring is increasing on nonnegative reals. Thus [F3] gives the unique minimizer ${\bar{x}}_C=\mathrm{\mid }C{\mathrm{\mid }}^{-1}{\sum }_{i\in C}{x}_i$; uniqueness follows because $T$ is injective for nonempty $C$. Replacing a center by this mean cannot increase the cluster contribution and strictly decreases it if the old center differed. Empty clusters contribute zero and retain their centers.

A nonterminal iteration changes either the labels or at least one nonempty center. By steps 1.1 and 1.2, its full assignment-and-center update therefore strictly decreases $J$. For every $t\ge 1$, the state $(z^{(t)},{\mu }^{(t)})$ follows a center update: its nonempty centers are the means for $z^{(t)}$, so its objective value is determined by that labeling alone; empty centers do not affect it. Consequently, among these post-update states, a labeling cannot recur across nonterminal iterations, since its objective value would repeat despite strict decrease. There are only $K^n$ labelings, so after the first update there are at most $K^n-1$ further nonterminal iterations before a terminal iteration occurs. This proves finite termination without requiring the arbitrary initial centers to be cluster means or excluding $z^{(1)}=z^{(0)}$.

At termination the labels and centers are unchanged by the next iteration. The assignment rule therefore certifies that each label is nearest under the retention convention, while the center update certifies that every nonempty-cluster center is its sample mean. This is the stated coordinatewise fixed point.