Hamming distance between unlabelled bipartitions ($\Delta (S,T)=\min \{|S△T|,|S△T^c|\}$)

This Hamming distance on partitions identifies a group with its complement because exchanging the two group names does not change the partition. Complementation is an isometry of the ordinary Hamming distance, so minimizing over this two-element group action gives a quotient metric and preserves the triangle inequality. Negating a zero-one indicator is not complementation; with $\pm 1$ membership vectors, it is.

Suppose $v_i=\pm 1/\sqrt{n}$ encodes the true partition and $\hat{v}$ is a unit estimated eigenvector. Every coordinate of the wrong sign contributes at least $1/n$ to ${\min }_{\sigma =\pm 1}\Vert \hat{v}-\sigma v{\Vert }_2^2=2(1-|{\hat{v}}^{\top }v|)$. Since this is at most $2(1-|{\hat{v}}^{\top }v{|}^2)$, which is the squared Frobenius distance between the rank-one orthogonal projection matrices, the bound follows. Coordinates estimated as zero may be assigned consistently to either group.