Isometric embedding of a finite set into $\mathbb{R}^n$ Consider a finite set $A$ with a distance $d$. It is easy to check whether $(A,d)$ is isometric to a finite subset of $\mathbb{R}$. Is there a known algorithm to check whether $(A,d)$ is isometric to a finite subset of the Euclidean space $\mathbb{R}^n$ for $n=2$ ? For $n=3$ ? For every $n$ ?
 A: The following theorem is well-known.
Theorem. Let $A = \{a_0,\ldots,a_m\}$ be a finite set with metric $d$, and let $M$ be the $m\times m$ matrix defined by
$$
m_{ij} \;=\; \frac{d(a_i,a_0)^2+d(a_j,a_0)^2 - d(a_i,a_j)^2}{2}
$$
Then $A$ embeds isometrically into $\mathbb{R}^n$ if and only if $M$ is positive semi-definite and $\mathrm{rank}(M) \leq n$.
Proof:  First let $\varphi\colon A\to\mathbb{R}^n$ be any isometric embedding such that $\varphi(a_0) = (0,0,\ldots,0)$.  By the polarization identity
$$
\langle v,w\rangle \;=\; \frac{\|v\|^2+\|w\|^2 - \|v-w\|^2}{2}
$$
we see that $\big\langle\varphi(a_i),\varphi(a_j)\big\rangle = m_{ij}$ for each $i$ and $j$, so the Gram matrix
$$
\begin{bmatrix}\big\langle\varphi(a_1),\varphi(a_1)\big\rangle & \big\langle\varphi(a_1),\varphi(a_2)\big\rangle & \cdots & \big\langle\varphi(a_1),\varphi(a_m)\big\rangle \\ \big\langle\varphi(a_2),\varphi(a_1)\big\rangle & \big\langle\varphi(a_2),\varphi(a_2)\big\rangle & \cdots & \big\langle\varphi(a_2),\varphi(a_m)\big\rangle \\ \vdots & \vdots & \ddots & \vdots \\ \big\langle\varphi(a_m),\varphi(a_1)\big\rangle & \big\langle\varphi(a_m),\varphi(a_2)\big\rangle & \cdots & \big\langle\varphi(a_m),\varphi(a_m)\big\rangle\end{bmatrix}
$$
is equal to $M$.  It follows that
$$
M \;=\; P^TP,
$$
where $P$ is the $n\times m$ matrix whose columns are the vectors $\varphi(a_1),\ldots,\varphi(a_m)$.  This proves that $M$ is positive semi-definite.  Moreover, it is easy to show that $M$ and $P$ have the same nullspace, and hence $\mathrm{rank}(M) = \mathrm{rank}(P)$.  Since $P$ has $n$ rows, it follows that $\mathrm{rank}(M) \leq n$.
For the converse, suppose that $M$ is positive semi-definite and $\mathrm{rank}(M) \leq n$.  The goal is to find an $n\times m$ matrix square root for $M$, i.e. an $n\times m$ matrix $P$ such that $P^TP = M$.  Since $P$ is symmetric, we know that
$$
M \;=\; RDR^{-1}
$$
for some $m\times m$ orthogonal matrix $R$, where $D$ is a diagonal matrix.  Since $\mathrm{rank}(M)\leq n$, we may assume that $D$ has the form
$$
D \;=\; \begin{bmatrix}d_1 & & & & & \\ & \ddots & & & & \\ & & d_n & & & \\ & & & 0 & & \\ & & & & \ddots & \\ & & & & & 0\end{bmatrix}
$$
for some $d_1,\ldots,d_n\in\mathbb{R}$.  Furthermore, since $M$ is positive semi-definite, we know that each $d_i\geq 0$.  Then the $n\times m$ matrix
$$
P \;=\; \begin{bmatrix}\sqrt{d_1} &  & \\  & \ddots & \\ &  & \sqrt{d_n} \\[6pt]  0 & \cdots & 0 \\[3pt] \vdots & \ddots & \vdots \\[3pt] 0 & \cdots & 0\end{bmatrix}R
$$
is the desired square root.  Now let $\varphi\colon A\to\mathbb{R}^n$ be the function for which $\varphi(a_0) = (0,\ldots,0)$ and $\varphi(a_1),\ldots,\varphi(a_m)$ are the columns of $P$.  Then the Gram matrix of $\varphi(a_1),\ldots,\varphi(a_m)$ is $M$, and it follows from the identity
$$
\|v-w\| \;=\; \sqrt{\langle v,v\rangle - 2 \langle v,w\rangle + \langle w,w\rangle}
$$
 that $\varphi$ is an isometric embedding.$\quad\square$
A few notes:


*

*The second half of the proof actually constitutes an algorithm for finding the embedding.  Given the metric $d$ on $A$, simply compute the matrix $M$, orthogonally diagonalize it, compute the matrix $P$, and use its columns to construct $\varphi$.

*The requirement of positive semi-definiteness is necessary.  In particular, there exist finite metric spaces that cannot be embedded into any Euclidean space.  For example, a metric space on four points $a_0,a_1,a_2,a_3$ defined by
$$
d(a_1,a_2) \,=\, d(a_2,a_3) \,=\, d(a_1,a_3) \,=\, 1
$$
and
$$
d(a_0,a_1) \,=\, d(a_0,a_2) \,=\, d(a_0,a_3) \,=\, r
$$
for $\dfrac12 < r < \dfrac{1}{\sqrt{3}}$ cannot be embedded in any $\mathbb{R}^n$, since these are not the possible edge lengths of a tetrahedron.  (This should be obvious geometrically—the points $a_1,a_2,a_3$ form a unit equilateral triangle, the point $a_0$ would need lie on the normal line through the center of this triangle, and every point on this line lies a distance at least $1/\sqrt{3}$ from $a_1$, $a_2$, and $a_3$.)
A: For $n=2$ embed the first two points. The third goes only in two positions (or four but its doesn't matter you can choose one). The rest only fit in one (each). 
For $n=3$ the same happens but after three points.
