Editing Distance geometry (section)

== Characterization via Cayley–Menger determinants ==
The following results are proved in Blumethal's book.<ref name="blumenthal" />

=== Embedding ''n'' + 1 points in the real numbers ===
Given a semimetric space <math>
 (S,d)</math> , with <math>S = \{P_0, \ldots, P_n\}</math>, and  <math>d(P_i, P_j) = d_{ij}\ge 0</math>, <math>0 \le i < j \le n</math>, an isometric embedding of <math>(S, d)</math> into <math>\mathbb{R}^n</math> is defined by <math display="inline">A_0, A_1,\ldots, A_n \in \mathbb R^n</math>, such that <math>d(A_i, A_j) = d_{ij}</math> for all <math>0 \le i < j \le n</math>.

Again, one asks whether such an isometric embedding exists for <math>(S,d)</math>.

A necessary condition is easy to see: for all <math>k = 1, \ldots, n</math>, let <math>v_k</math> be the ''k''-simplex formed by  <math display="inline">A_0, A_1,\ldots, A_k</math>, then

:<math>(-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 \ge 0</math>

The converse also holds. That is, if for all <math>k = 1, \ldots, n</math>,

:<math>(-1)^{k+1}\operatorname{CM}(P_0, \ldots, P_k) \ge 0,</math>

then such an embedding exists.

Further, such embedding is unique up to isometry in <math>\mathbb{R}^n</math>. That is, given any two isometric embeddings defined by <math>A_0, A_1,\ldots, A_n</math>, and <math>A'_0, A'_1,\ldots, A'_n</math>, there exists a (not necessarily unique) isometry <math>T :  \mathbb R^n \to \mathbb R^n</math>, such that <math>T(A_k) = A'_k</math> for all <math>k = 0, \ldots, n</math>. Such <math>T</math> is unique if and only if <math>\operatorname{CM}(P_0, \ldots, P_n) \neq 0</math>, that is, <math>A_0, A_1,\ldots, A_n</math> are affinely independent.

=== Embedding ''n'' + 2 and ''n'' + 3 points ===
If <math>n+2</math> points <math>P_0, \ldots, P_{n+1}</math> can be embedded in <math>\mathbb{R}^n</math> as <math>A_0, \ldots, A_{n+1}</math>, then other than the conditions above, an additional necessary condition is that  the <math>(n+1)</math>-simplex formed by  <math>A_0, A_1,\ldots, A_{n+1}</math>, must have no <math>(n+1)</math>-dimensional volume. That is, <math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+1}) = 0</math>.

The converse also holds. That is, if for all <math>k = 1, \ldots, n</math>,

: <math>(-1)^{k+1} \operatorname{CM}(P_0, \ldots, P_k) \ge 0,</math>

and

: <math> \operatorname{CM}(P_0, \ldots, P_n, P_{n+1}) = 0, </math>

then such an embedding exists.

For embedding <math>n+3</math> points in <math>\mathbb{R}^n</math>, the necessary and sufficient conditions are similar:

# For all <math>k = 1, \ldots, n</math>, <math>(-1)^{k+1} \operatorname{CM}(P_0, \ldots, P_k) \ge 0</math>;
#<math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+1}) = 0;</math>
# <math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+2}) = 0;</math>
#<math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+1},  P_{n+2}) = 0.</math>

=== Embedding arbitrarily many points ===
The <math>n+3</math> case turns out to be sufficient in general.

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

#<math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+1}) = 0;</math>
#<math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+2}) = 0;</math>
#<math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+1},  P_{n+2}) = 0.</math>

And such embedding is unique up to isometry in <math>\mathbb{R}^n</math>.

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

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