(G.6), p. 46 — for the optimal rotation O, ‖Û − U⁰O‖²_F ≤ 8‖X̂ − X⁰‖₁/n²_min

Let $\varphi : [n]\to[r]$ be a labelling with every cluster nonempty ($r \ge 1$), $X^0$ the true clustering matrix and $U^0 = Z^0\,\mathrm{Diag}(1/\sqrt{n_k})$. Let $\hat X \in \mathbb R^{n\times n}$ be symmetric with $0 \le \hat X_{ij} \le 1$, and let $\hat U \in \mathbb R^{n \times r}$ consist of orthonormal top-$r$ eigenvectors of $\hat X$. Let $O$ be an optimal rotation, i.e. an orthogonal $r\times r$ matrix minimising $\|\hat U - U^0 O'\|_F$ over all orthogonal $O'$. Then

This is the eigenvector-perturbation step of the proof of Theorem 2: it combines the Davis–Kahan theorem, the eigengap $n_{\min}$ of $X^0$ and the box constraint on $\hat X$.

Formalization Note The page writes $\|\hat U - U^0O\|_F^2$ without naming $O$; §4.2 (p. 17) calls it "the optimal rotation matrix". The statement is made for every minimiser $O$ (minimisers exist since the orthogonal group is compact), which is stronger than the existence of one good $O$.