Distance geometry

Consider three ground radio stations A, B, C, whose locations are known. A radio receiver is at an unknown location. The times it takes for a radio signal to travel from the stations to the receiver, ${\displaystyle t_{A},t_{B},t_{C}}$, are unknown, but the time differences, ${\displaystyle t_{A}-t_{B}}$ and ${\displaystyle t_{A}-t_{C}}$, are known. From them, one knows the distance differences ${\displaystyle c(t_{A}-t_{B})}$ and ${\displaystyle c(t_{A}-t_{C})}$, from which the position of the receiver can be found.

In data analysis, one is often given a list of data represented as vectors ${\displaystyle \mathbf {v} =(x_{1},\ldots ,x_{n})\in \mathbb {R} ^{n}}$, and one needs to find out whether they lie within a low-dimensional affine subspace. A low-dimensional representation of data has many advantages, such as saving storage space, computation time, and giving better insight into data.

Now we formalize some definitions that naturally arise from considering our problems.

Given a list of points on ${\displaystyle R=\{P_{0},\ldots ,P_{n}\}}$, ${\displaystyle n\geq 0}$, we can arbitrarily specify the distances between pairs of points by a list of ${\displaystyle d_{ij}>0}$, ${\displaystyle 0\leq i<j\leq n}$. This defines a semimetric space: a metric space without triangle inequality.

Explicitly, we define a semimetric space as a nonempty set ${\displaystyle R}$ equipped with a semimetric ${\displaystyle d:R\times R\to [0,\infty )}$ such that, for all ${\displaystyle x,y\in R}$,

1. Positivity: ${\displaystyle d(x,y)=0}$   if and only if  ${\displaystyle x=y}$.
2. Symmetry: ${\displaystyle d(x,y)=d(y,x)}$.

Any metric space is a fortiori a semimetric space. In particular, ${\displaystyle \mathbb {R} ^{k}}$, the ${\displaystyle k}$-dimensional Euclidean space, is the canonical metric space in distance geometry.

The triangle inequality is omitted in the definition, because we do not want to enforce more constraints on the distances ${\displaystyle d_{ij}}$ than the mere requirement that they be positive.

In practice, semimetric spaces naturally arise from inaccurate measurements. For example, given three points ${\displaystyle A,B,C}$ on a line, with ${\displaystyle d_{AB}=1,d_{BC}=1,d_{AC}=2}$, an inaccurate measurement could give ${\displaystyle d_{AB}=0.99,d_{BC}=0.98,d_{AC}=2.00}$, violating the triangle inequality.

Given two semimetric spaces, ${\displaystyle (R,d),(R',d')}$, an isometric embedding from ${\displaystyle R}$ to ${\displaystyle R'}$ is a map ${\displaystyle f:R\to R'}$ that preserves the semimetric, that is, for all ${\displaystyle x,y\in R}$, ${\displaystyle d(x,y)=d'(f(x),f(y))}$.

For example, given the finite semimetric space ${\displaystyle (R,d)}$ defined above, an isometric embedding into is defined by points ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$, such that ${\displaystyle d(A_{i},A_{j})=d_{ij}}$ for all ${\displaystyle 0\leq i<j\leq n}$.

Given the points ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$, they are defined to be affinely independent, iff they cannot fit inside a single ${\displaystyle l}$-dimensional affine subspace of ${\displaystyle \mathbb {R} ^{k}}$, for any ${\displaystyle \ell <n}$, iff the ${\displaystyle n}$-simplex they span, ${\displaystyle v_{n}}$, has positive ${\displaystyle n}$-volume, that is, ${\displaystyle \operatorname {Vol} _{n}(v_{n})>0}$.

In general, when ${\displaystyle k\geq n}$, they are affinely independent, since a generic n-simplex is nondegenerate. For example, 3 points in the plane, in general, are not collinear, because the triangle they span does not degenerate into a line segment. Similarly, 4 points in space, in general, are not coplanar, because the tetrahedron they span does not degenerate into a flat triangle.

When ${\displaystyle n>k}$, they must be affinely dependent. This can be seen by noting that any ${\displaystyle n}$-simplex that can fit inside ${\displaystyle \mathbb {R} ^{k}}$ must be "flat".

Given a semimetric space ${\displaystyle (S,d)}$ , with ${\displaystyle S=\{P_{0},\ldots ,P_{n}\}}$, and ${\displaystyle d(P_{i},P_{j})=d_{ij}\geq 0}$, ${\displaystyle 0\leq i<j\leq n}$, an isometric embedding of ${\displaystyle (S,d)}$ into ${\displaystyle \mathbb {R} ^{n}}$ is defined by ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{n}}$, such that ${\displaystyle d(A_{i},A_{j})=d_{ij}}$ for all ${\displaystyle 0\leq i<j\leq n}$.

Again, one asks whether such an isometric embedding exists for ${\displaystyle (S,d)}$.

A necessary condition is easy to see: for all ${\displaystyle k=1,\ldots ,n}$, let ${\displaystyle v_{k}}$ be the k-simplex formed by ${\textstyle A_{0},A_{1},\ldots ,A_{k}}$, then

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})=(-1)^{k+1}\operatorname {CM} (A_{0},\ldots ,A_{k})=2^{k}(k!)^{k}\operatorname {Vol} _{k}(v_{k})^{2}\geq 0}$

The converse also holds. That is, if for all ${\displaystyle k=1,\ldots ,n}$,

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0,}$

then such an embedding exists.

Further, such embedding is unique up to isometry in ${\displaystyle \mathbb {R} ^{n}}$. That is, given any two isometric embeddings defined by ${\displaystyle A_{0},A_{1},\ldots ,A_{n}}$, and ${\displaystyle A'_{0},A'_{1},\ldots ,A'_{n}}$, there exists a (not necessarily unique) isometry ${\displaystyle T:\mathbb {R} ^{n}\to \mathbb {R} ^{n}}$, such that ${\displaystyle T(A_{k})=A'_{k}}$ for all ${\displaystyle k=0,\ldots ,n}$. Such ${\displaystyle T}$ is unique if and only if ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0}$, that is, ${\displaystyle A_{0},A_{1},\ldots ,A_{n}}$ are affinely independent.

If ${\displaystyle n+2}$ points ${\displaystyle P_{0},\ldots ,P_{n+1}}$ can be embedded in ${\displaystyle \mathbb {R} ^{n}}$ as ${\displaystyle A_{0},\ldots ,A_{n+1}}$, then other than the conditions above, an additional necessary condition is that the ${\displaystyle (n+1)}$-simplex formed by ${\displaystyle A_{0},A_{1},\ldots ,A_{n+1}}$, must have no ${\displaystyle (n+1)}$-dimensional volume. That is, ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0}$.

The converse also holds. That is, if for all ${\displaystyle k=1,\ldots ,n}$,

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0,}$

and

${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0,}$

then such an embedding exists.

For embedding ${\displaystyle n+3}$ points in ${\displaystyle \mathbb {R} ^{n}}$, the necessary and sufficient conditions are similar:

1. For all ${\displaystyle k=1,\ldots ,n}$, ${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0}$;
2. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0;}$
3. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+2})=0;}$
4. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1},P_{n+2})=0.}$

The ${\displaystyle n+3}$ case turns out to be sufficient in general.

In general, given a semimetric space ${\displaystyle (R,d)}$, it can be isometrically embedded in ${\displaystyle \mathbb {R} ^{n}}$ if and only if there exists ${\displaystyle P_{0},\ldots ,P_{n}\in R}$, such that, for all ${\displaystyle k=1,\ldots ,n}$, ${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0}$, and for any ${\displaystyle P_{n+1},P_{n+2}\in R}$,

1. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0;}$
2. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+2})=0;}$
3. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1},P_{n+2})=0.}$

And such embedding is unique up to isometry in ${\displaystyle \mathbb {R} ^{n}}$.

Further, if ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0}$, then it cannot be isometrically embedded in any ${\displaystyle \mathbb {R} ^{m},m<n}$. And such embedding is unique up to unique isometry in ${\displaystyle \mathbb {R} ^{n}}$.

Thus, Cayley–Menger determinants give a concrete way to calculate whether a semimetric space can be embedded in ${\displaystyle \mathbb {R} ^{n}}$, for some finite ${\displaystyle n}$, and if so, what is the minimal ${\displaystyle n}$.