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 \mathbb{R}^n for a metric space of cardinality n \leq 3, there exist four-point metric spaces which cannot be emdebbed into any euclidean space:

Let X= \{a,b,c,d\} be a metric space satisfying d(a,d)=d(b,d)= \ell/2 and d(a,b)=d(a,c)=d(b,c)=\ell for some \ell >0. If \varphi : X \to \mathbb{R}^n is an isometric embedding, then \{ \varphi(a), \varphi(b), \varphi(c) \} are the vertices of an equilateral triangle and \varphi(d) is the middle point of the segment [\varphi(a),\varphi(b)], hence d(\varphi(d),\varphi(c))= \frac{\sqrt{5}}{2} \ell. Therefore, if X embeds into an euclidean space then d(c,d)= \frac{\sqrt{5}}{2} \ell. Taking another value for d(c,d) (so that triangular inequalities hold) makes (X,d) 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 X cannot be embedded isometrically into \mathbb{R}^n it is sufficient to find a finite subset Y \subset X having that property.

In fact, our previous example have such an interpretation. Let \mathbb{S}^2 \subset \mathbb{R}^3 be the two-dimensional sphere and d be the metric on \mathbb{S}^2 defined by: if x,y \in \mathbb{S}^2, d(x,y) is the length of the shortest great circle between x and y. Let a=(1,0,0), b=(0,1,0), c=(0,0,1) and d= \left( \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}},0 \right). Then d(a,b)=d(a,c)=d(b,c)= \frac{\pi}{2}, d(a,d)=d(b,d)= \frac{\pi}{4} and d(c,d)= \frac{\pi}{2} \neq \frac{\sqrt{5}\pi}{4}.

We deduce that there is no isometry \mathbb{S}^2 \hookrightarrow \mathbb{R}^n for every n \geq 0.

More generally, if \Omega \subset \mathbb{S}^2 is a nonempty open subset, we may suppose without loss of generality that (0,0,1) \in \Omega and then \Omega contains a (small) triangle similar to (a,b,c). With the same argument, we deduce that there is no isometry \Omega \hookrightarrow \mathbb{R}^n for every n \geq 0, hence:

Theorem: The sphere \mathbb{S}^2 is not locally flat, ie. for every nonempty open subset \Omega \subset \mathbb{S}^2 and integer n \geq 0 there does not exist any isometry \Omega \hookrightarrow \mathbb{R}^n.

The same thing can be done for the hyperbolic plane \mathbb{D} = \{ z \in \mathbb{C} \mid |z| < 1 \} endowed with the metric

\displaystyle d(x,y)= \mathrm{arcosh} \left( 1+2 \frac{|x-y|^2}{ (1-|x|^2) (1- |y|^2)} \right).

For example, if x = \frac{1}{2}, y= \frac{1}{2} e^{i 2 \pi/3}, z= \frac{1}{2} e^{i4 \pi/3} and w=-3/4, then x,y,z defines an equilateral triangle of length \mathrm{arcosh} (35/3), w is the midle point of [y,z] and we have d(x,w)= \mathrm{arcosh} (11). Therefore, if \varphi : \mathbb{H} \to \mathbb{R}^n were an isometry, the triangle defined by \varphi(x), \varphi(y) , \varphi(z) would be equilateral, \varphi (w) would the midle point of [\varphi(y),\varphi(z)], and from an elementary argument of euclidean geometry we would have

d(f(x),f(w))= \frac{\sqrt{3}}{2} d(f(x),f(y)) = \frac{\sqrt{3}}{2} \mathrm{arcosh} (35/3) \neq \mathrm{arcosh} (11) = d(x,w),

a contradiction. The more general case is left as an exercice of elementary geometry:

Theorem: The hyperbolic plane \mathbb{H} is not locally flat, ie. for every nonempty open subset \Omega \subset \mathbb{H} and integer n \geq 0 there does not exist any isometry \Omega \hookrightarrow \mathbb{R}^n.

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 X= \{x_0,\dots,x_m\} be a finite metric space and n \geq 0. Does there exist an isometry X \hookrightarrow \mathbb{R}^n?

Suppose that \varphi : X \to \mathbb{R}^n is such an isometry; without loss of generality, we may suppose \varphi(x_0)=0. Then the equations \| y_k- \varphi(x_i)\|= d(x_i,x_k) have solutions.

Noticing that \|y_k- \varphi(x_i)\|^2= \|y_k\|^2+ \|\varphi(x_i)\|^2-2 \langle y_k, \varphi(x_i) \rangle, \|y_k\|^2= \|y_k- \varphi(x_0)\|^2=d(x_0,x_k)^2 and \|\varphi(x_i)\|^2= \| \varphi(x_i)- \varphi(x_0)\|^2=d(x_i,x_0)^2, we deduce that

\displaystyle \langle y_k, \varphi(x_i) \rangle = \frac{1}{2} \left( d(x_k, x_0)^2 + d(x_0, x_i)^2 - d(x_k, x_i)^2 \right).

For convenience, let m_{ik} denote the expression in the right-hand of the previous equality; in particular, m_{ik} depends only on the metric space (X,d).

Therefore, if \varphi(x_i)= \sum\limits_{j=1}^n \xi_{ij} e_j and y_i= \sum\limits_{j=1}^n \zeta_{ij}e_j,

\left( \begin{matrix} \xi_{11} & \xi_{12} & \dots & \xi_{1n} \\ \xi_{21} & \xi_{22} & \dots & \xi_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ \xi_{m1} & \xi_{m2} & \dots & \xi_{mn} \end{matrix} \right) \left( \begin{matrix} \zeta_{11} & \zeta_{21} & \dots & \zeta_{m1} \\ \zeta_{12} & \zeta_{22} & \dots & \zeta_{m2} \\ \vdots & \vdots & \ddots & \vdots \\ \zeta_{1n} & \zeta_{2n} & \dots & \zeta_{mn} \end{matrix} \right) = \left( \begin{matrix} m_{11} & m_{12} & \dots & m_{1n} \\ m_{21} & m_{22} & \dots & m_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ m_{n1} & m_{n2} & \dots & m_{nn} \end{matrix} \right).

In particular, taking \zeta_{ij}= \xi_{ij}, we deduce that the matrix M=(m_{ij}) can be written as ^tPP for some P \in M_{nm}(\mathbb{R}). Conversely, if M= \ ^tPP where P=(v_1, \dots, v_m) \in M_{nm}(\mathbb{R}) then \varphi : x_i \mapsto v_i is an isometry X \hookrightarrow \mathbb{R}^n. Indeed, \langle v_i,v_j \rangle = (^tPP)_{ij}=m_{ij} for all i,j hence

\| v_i-v_j \|^2 = \langle v_i, v_j \rangle -2 \langle v_i, v_j \rangle + \langle v_j, v_j \rangle = m_{ii} -2m_{ij} + m_{jj} = d(x_i, x_j)^2.

We just showed that X embeds isometrically into \mathbb{R}^n if and only if the matrix M can be written as ^tPP for some P \in M_{nm}(\mathbb{R}).

An equivalent condition is that M is positive semi-definite and \mathrm{rank}(M) \leq n. Indeed, the matrix M is symmetric so there exist R \in O_m(\mathbb{R}) and \lambda_1,\dots,\lambda_m \in \mathbb{R} such that

M= \ ^tR \left( \begin{matrix} \lambda_1 & & 0 \\ & \ddots & \\ 0 & & \lambda_m \end{matrix} \right) R.

If \mathrm{rank}(M) \leq n we may suppose \lambda_k=0 when k \geq n+1, and if M is positive semi-definite then \lambda_i \geq 0. Consequently, M= \ ^tPP with

P = \left( \begin{matrix} \sqrt{\lambda_1} & & 0 & \\ & \ddots & & 0 \\ 0 & & \sqrt{\lambda_n} & \end{matrix} \right)R \in M_{nm}(\mathbb{R}).

Conversely, suppose that M= \ ^t PP for some P \in M_{nm}(\mathbb{R}). Then t^xMx= \ ^tx^tPPx= \|P(x)\|^2 \geq 0 for all x so M is positive semi-definite, and Mx=0 implies \|Px\|^2= \ ^txMx=0 so M and P have the same nullspace hence \mathrm{rank}(M)= \mathrm{rank}(P) \leq n since P has only n rows.

We finally showed:

Theorem: A finite metric space X=\{x_0,\dots,x_m\} embeds isometrically into \mathbb{R}^n if and only if the matrix M \in M_n(\mathbb{R}) whose coefficients are \frac{1}{2} \left( d(x_i,x_0)^2+d(x_0,x_j)^2-d(x_i,x_j)^2 \right) is positive semi-definite and of rank \leq n.

Notice that our proof gives an algorithm to find an embedding X \hookrightarrow \mathbb{R}^n 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 \leq n.

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).

Advertisements