Some counterexamples in multidimensional scaling

Abstract

Given a set X with elements x, y,... which has a partial order < on the pairs of the Cartesian product X2, one may seek a distance function ρ{variant} on such pairs (x, y) which satisfies ρ{variant}(x1, y1) < ρ{variant}(x2, y2) precisely when (x1, y1) < (x2, y2), and even demand a metric space (X, ρ{variant}) with some such compatible ρ{variant} which has an isometric imbedding into a finite-dimensional Euclidean space or a separable Hilbert space. We exhibit here systems (X, <) which cannot meet the latter demand. The space of real m-tuples (ξ1,...,ξm) with either the "city-block" norm Σi ∥ξi∥ or the "dominance" norm maxi, ∥ξi∥ cannot possibly become a subset of any finite-dimensional Euclidean space. The set of real sequences (ξ1, ξ2,...) with finitely many nonzero elements and the supremum norm supi, ∥ξi∥ cannot even become a subset of any separable Hilbert space. © 1978.