Number of independent distances between n points in d-dimensional Euclidean space?

Question

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$?

Answer 1

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?

Answer 2

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.