MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There are $\binom{n}{2}$ distances between $n$ points in $\mathbb{R}^d$. Not all of them can be chosen freely if $n$ exceeds the number $n_d = d + 1$. If $n = n_d$ we obviously have $\binom{d+1}{2}$ distances which can be chosen (more or less) independently (restricted only by the triangle inequality).

I see two ways to count $N_n^d$, the number of independent distances between $n\geq d$ points in $\mathbb{R}^d$, which is given by $nd - \binom{d+1}{2}$

The first one: $nd$ coordinates minus one translation ($d$) minus one rotation ($\binom{d}{2}$):

$N_n^d = nd - d - \binom{d}{2} = nd - (\binom{d}{2} + d) = nd - \binom{d+1}{2}$

The second one: $\binom{d+1}{2}$ distances between $d + 1$ base points plus $d\ (\ n - (d + 1)\ )$ distances between the remaining points and $d$ of the base points (the remaining one serving to say in which half-space with respect to the $d$ base points the point is located):

$N_n^d = \binom{d+1}{2} + d\ (\ n - (d + 1)\ ) = nd - d (d + 1) + \binom{d+1}{2} = nd - \binom{d+1}{2}$. (Is this sound?)

Observation: The binomials seem to come from two very different directions (with two seemingly different interpretations), also the term $nd$. Does this tell something deep about (Euclidean) geometry? And what?

Are there further "independent" ways to compute $N_n^d$?

share|cite|improve this question
You write "restricted only by the triangle equality"; I see what you mean, but that is not quite correct --- you can choose 6 distances between 4 points so that it does not come from Euclidean space, but triangle inequality holds. – Anton Petrunin Jan 2 '10 at 17:58
Sorry, this was a typo: I wanted to write "triangle inequality". (By the way, what would be the "triangle equality"?) – Hans Stricker Jan 2 '10 at 18:45
up vote 2 down vote accepted

Here is a little generalisation of your observation. Suppose we have a manfiold $M$ of dimension d with a metric. The isometry group $I(M)$ of the manifold has dimension at most $\frac{d(d+1)}{2}$. The maximal dimension of $I(M)$ is attained for $R^d$, $H^d$, $S^d$ and $RP^d$ with a constant curvature metric. Now we want to know what is the number of independent distances among $n$ points in $M^d$ with $n\ge d$. This number can be estimated from above by the reasoning identical to yours, namelly it is $nd-dim(I(M))$. But in reality this is only an estimation from above, because for the universal cover of $M$ the dimension will be the same as for $M$ but its group of symmetries can be larger. This is what happen for $T^n$ and $R^n$ with flat metric.

So I wonder if the following is true. Let $M$ be a simply connected Riemannian manifold of dimension $d$. Let $Dim(M)(n)$ be the dimension of the space of independent distances among $n$ points in $M$. Is it true that $nd-Dim(M)(n)$ is the dimesnion of the group of isometries $dim(I(M))$ of $M$ for $n$ large enough?

share|cite|improve this answer
If this was true: would/could its proof go along one of the two lines I sketched in my question? – Hans Stricker Jan 2 '10 at 15:42
I think, the proof would go along slightly different lines and should use some notions of Riemannian geometry. For example, suppose that the dimension is always nd-(d+1)d/2 for large n. Then we should deduce from this that the metric on your space is of constant curvature. This should be some local calculation. I think, one should take a point x where the Riemann tensor is not proporitonal to one of unite $S^d$ and try to prove that if we take n points close to x then the corresponding dimension is larger than nd-d(d+1)/2. Maybe this is a known fact, but I have not seen it. – Dmitri Jan 2 '10 at 17:15

The additional `constraints' missing from these $N \choose 2$ interparticle distances are rank constraints on the corresponding matrix $M$ of (squared) distances.

There is a matrix parameterization of your space, essentially due to Cayley. Consider the matrix $M$ whose ij entries arethe squared distance $\| p_i - p_j \|$ between your $n$ points $p_i$ in $R^d$. It is pretty clear that $M$ is a symmetric positive semi-definite real matrix. What is less obvious is that the rank of $M$ is less than or equal to $min(n-1, d)$ ( equality if and only if the points are in general position).
The converse is also true: any symmetric n by n positive semi-definite matrix $M$ of rank less than or equal to $min(n-1, d)$ is realized as having its entries as the squared distances
between $n$ points in $R^d$.

Standard formulae for the dimensions of the space of symmetric matrices of a given rank verify that the dimension formula is as you have have written. These formulae - and the method behind them -- can be found in
papers or book of Arnol'd on singularity theory.

For a wonderful way to see this fact, and for the historical references to Cayley and others, see Le problème des n corps et les distances mutuelles'', Alain Albouy and Alain Chenciner, Inventiones mathematicae 131 pp. 151-184 (1998). The crux of their argument is to make up an n-1 dimensional abstract vector space ofdispostions''. Then $M$ can be expressed as $x \circ g \circ x^t$ where $x$ is a linear map from the disposition space to $R^d$ encoding the particle positions modulo translations, and $g$ encodes the metric on $R^d$. The fact that $rank(M) \le min(n-1, d)$ follows immediately.

share|cite|improve this answer

Your Answer


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.