A first preliminary remark is that embedding isometrically a finite metric space into an euclidean space is not a trivial problem. Indeed, although there exists always such an embedding into for a metric space of cardinality , there exist four-point metric spaces which cannot be emdebbed into any euclidean space:
Let be a metric space satisfying and for some . If is an isometric embedding, then are the vertices of an equilateral triangle and is the middle point of the segment , hence . Therefore, if embeds into an euclidean space then . Taking another value for (so that triangular inequalities hold) makes an example of four-point metric space that does not embed into any euclidean space.
A second remark is that our problem may be applied to infinite metric spaces. Indeed, to show that an arbitrary metric space cannot be embedded isometrically into it is sufficient to find a finite subset having that property.
In fact, our previous example have such an interpretation. Let be the two-dimensional sphere and be the metric on defined by: if , is the length of the shortest great circle between and . Let , , and . Then , and .
We deduce that there is no isometry for every .
More generally, if is a nonempty open subset, we may suppose without loss of generality that and then contains a (small) triangle similar to . With the same argument, we deduce that there is no isometry for every , hence:
Theorem: The sphere is not locally flat, ie. for every nonempty open subset and integer there does not exist any isometry .
The same thing can be done for the hyperbolic plane endowed with the metric
For example, if , , and , then defines an equilateral triangle of length , is the midle point of and we have . Therefore, if were an isometry, the triangle defined by would be equilateral, would the midle point of , and from an elementary argument of euclidean geometry we would have
a contradiction. The more general case is left as an exercice of elementary geometry:
Theorem: The hyperbolic plane is not locally flat, ie. for every nonempty open subset and integer there does not exist any isometry .
More information can be found in The Sphere Is Not Flat, P. L. Robison, The American Mathematical Monthly, Vol. 113, No. 2 (Feb. 2006), pp. 171-173.
From now on, let us back to our main problem: Let be a finite metric space and . Does there exist an isometry ?
Suppose that is such an isometry; without loss of generality, we may suppose . Then the equations have solutions.
Noticing that , and , we deduce that
For convenience, let denote the expression in the right-hand of the previous equality; in particular, depends only on the metric space .
Therefore, if and ,
In particular, taking , we deduce that the matrix can be written as for some . Conversely, if where then is an isometry . Indeed, for all hence
We just showed that embeds isometrically into if and only if the matrix can be written as for some .
An equivalent condition is that is positive semi-definite and . Indeed, the matrix is symmetric so there exist and such that
If we may suppose when , and if is positive semi-definite then . Consequently, with
Conversely, suppose that for some . Then for all so is positive semi-definite, and implies so and have the same nullspace hence since has only rows.
We finally showed:
Theorem: A finite metric space embeds isometrically into if and only if the matrix whose coefficients are is positive semi-definite and of rank .
Notice that our proof gives an algorithm to find an embedding when it exists. As an exercice, the reader may verify that the matrices associated to our two previous examples are not positive semi-definite or of rank .
A geometrical interpretation of the criterion given in this note can be found in Embedding Metric Spaces in Euclidean Spaces, C. L. Morgan, Journal of Geometry, 5 (1974).