minimum space dimension to place n-points knowing pairwise distances

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.

-

Wikipedia

-
Why doesn't `<a href="en.wikipedia.org/wiki/Johnson–Lindenstrauss_lemma/">Wikipedia</a>' work? – Bill Johnson Oct 28 '11 at 17:39
Thanks, Suvrit (not that I have any idea why what you did is necessary). – Bill Johnson Oct 28 '11 at 17:46
Once upon a time, I thought that I had it figured out---but actually I am no longer certain. Most probably, the presence of underscores throws off the rendering software, which necessitates some workarounds. – Suvrit Oct 28 '11 at 19:56
Hi, thank you for the lead. It seems to quite fit what I had in Mind. – Castim Oct 29 '11 at 18:59

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

-

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.

-