Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 8 down vote accepted

For the basic result, start with

Wikipedia

or Google "Johnson-Lindenstrauss Lemma".

share|improve this answer
    
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.
            tetrahedron
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."

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.