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.

up vote 10 down vote accepted

For the basic result, start with


or Google "Johnson-Lindenstrauss Lemma".

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


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.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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