Universal optimality of the double-centred matrix under unitarily invariant norms for dissimilarity data

Abstract

The classical identity relating squared distances to inner products determines every off-diagonal entry of a symmetric matrix associated with a set of pairwise dissimilarities, while leaving its diagonal free. This paper studies the resulting affine family of symmetric matrices and asks which representative is selected by minimising a matrix norm. We prove that the same representative, namely the double-centred matrix used in classical multidimensional scaling and principal coordinate analysis, minimises every unitarily invariant norm on the family. The result includes the Frobenius, spectral, nuclear, Schatten, and Ky Fan norms, and requires no assumption that the dissimilarities are Euclidean distances. The proof rests on a compression-reduction principle: the centring projection maps the entire compatible set to a single element of the family, and orthogonal compression is contractive for unitarily invariant norms; the conclusion follows without solving a separate minimisation problem for each norm. We then determine how many minimisers there are: the minimiser is unique for the Frobenius norm, for the nuclear norm and for every strictly convex unitarily invariant norm, while for the spectral norm we describe the whole minimising set, a compact convex set that reduces to a single point precisely when the double-centred matrix vanishes.