# Minimum dimension to hold $N$ points with given distances?

Suppose you're given $N$ points along with an $N\times N$ matrix $D$ with entries $d_{ij}$ giving the distances between the points (assume that the $d_{ij}$ satisfy the usual requirements of a distance, i.e., $d_{ii}=0$, $d_{ij}=d_{ji}$, and $d_{ij} \leq d_{ik} + d_{jk}$).

From this information alone, can you determine what's the minimum dimension of an Euclidean space (i.e., what's the minimum $n$ in $\mathbb{R}^n$) that can hold these points?

In other words, what's the minimum $n$ such that there exist $N$ points in $\mathbb{R}^n$ with distances as given in the matrix $D$?

• When $N=2$, $n=1$ works: use the points $0$ and $d_{12}$.
• When $N=3$, $n=2$ works: draw a triangle with given sides on the plane.
• When $N\ge 4$, it depends on what the distances are: in general, there is no $n$ at all i.e., no Euclidean space can hold the given points.
A standard example of the latter is $N=4$ with distance matrix $$\begin{pmatrix} 0 & 1 & 2 & 1 \\ 1 & 0 & 1 & 2 \\ 2 & 1 & 0 & 1 \\ 1 & 2 & 1 & 0 \end{pmatrix}$$ Indeed, suppose that $A,B,C,D$ are four points in $\mathbb R^n$ for which these distances are realized. Since $|AB|+|BC|=2=|AC|$, the point $B$ must be the midpoint of $AC$. But also $|AD|+|CD|=2=|AC|$, so $D$ must be the midpoint of $AC$. Thus $B=D$, contradicting $|BD|=2$.
A necessary and sufficient condition for the existence of an isometric embedding of a finite metric space into some Euclidean space is due to Schoenberg. Let $\widehat D$ be the matrix obtained from $D$ by squaring each entry, i.e., the matrix of $d_{ij}^2$. Then, the space is embeddable into a Euclidean space if and only if $$\xi\in\mathbb R^N, \ \sum_{i=1}^N \xi_i=0\implies \xi^t \widehat{D} \xi \le 0 \tag{1}$$ For references, see Eremenko's answer here. Or better yet, see the book Geometry of Cuts and Metrics by Deza and Laurent, which is a very comprehensive source of embedding and non-embedding results on finite metric spaces.
Proposition 6.2.4 of the book gives the minimum embedding dimension $n$ under the assumption that (1) holds. Namely, let $$p_{ij}=\frac12(d_{iN}^2+d_{jN}^2-d_{ij}^2),\quad 1\le i,j \le N-1$$ The minimum dimension $n$ is the rank of the matrix $(p_{ij})_{1\le i,j \le N-1}$.