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