Question

Hi everyone,

Let P be a set of n points. Assuming I know the pairwise distances for each pair of points. What would be the minimum dimension of the space in which I could place those n points with respect to the different pairwise distances.

The idea would be to set a first point at random coordinates in a multi-dimensional space. Then, add the other n-1 points so that the pairwise distances are respected.

Sorry, it's maybe a trivial question for mathematicians but I'm still wondering if the relation: "number of points-> minimum dimension of space" does exist.

Thank you for your comments.

Answer 1

For the basic result, start with

Wikipedia

or Google "Johnson-Lindenstrauss Lemma".

Answer 2

Suppose your $\binom{n}{2}$ distances are all exactly 1. Then they determine an $(n{-}1)$-simplex in $\mathbb{R}^{n-1}$, and those distances cannot be realized in a lower dimension. For example, three points at unit distance determine an equilateral triangle in $\mathbb{R}^{2}$; four points at unit distance determine a regular tetrahedron in $\mathbb{R}^{3}$, whose six edge lengths are each 1.
            
Generally, the more interesting question is how to embed the distances in a space of modest dimension without significant distortion. See, e.g., the chapter by Indyk and Matoušek, "Low-distortion embeddings of finite metric spaces," Handbook of Discrete and Computational Geometry, 2004, or the 2006 paper by Bartal, "Embedding finite metric spaces in low dimension."

Answer 3

Obviously, for some special distances, you can embed the points in a fewer-dimensional space. If this is important, one way to count the correct dimension would be the rank of a certain matrix.

$(b-a,c-a)=(d(a,b)^2+d(a,c)^2-d(b,c)^2)/2$

If you fix a point $a$ and place the other values of this dot product into an $n-1$ by $n-1$ symmetric matrix, the rank of that matrix will be the dimension of the space you can embed the points in.