Cayley–Menger determinant

In linear algebra, geometry, and trigonometry, the Cayley–Menger determinant is a formula for the content, i.e. the higher-dimensional volume, of a formula_1-dimensional simplex in terms of the squares of all of the distances between pairs of its vertices. The determinant is named after Arthur Cayley and Karl Menger.
The formula_2 pairwise distance polynomials between "n" points in a real Euclidean space are Euclidean invariants that are associated via the Cayley-Menger relations. These relations served multiple purposes such as generalising Heron's Formula, computing the content of a "n"-dimensional simplex, and ultimately determining if any real symmetric matrix is a Euclidean distance matrix in the field of Distance geometry.
History.
Karl Menger was a young geometry professor at the University of Vienna and Arthur Cayley was a British mathematician who specialized in algebraic geometry. Menger extended Cayley's algebraic excellence to propose a new axiom of metric spaces using the concepts of distance geometry and relation of congruence, known as the Cayley-Menger determinant. This ended up generalising one of the first discoveries in distance geometry, Heron's formula, which computes the area of a triangle given its side lengths.
Definition.
Let formula_3 be formula_4 points in formula_5-dimensional Euclidean space, with formula_6. These points are the vertices of an "n"-dimensional simplex: a triangle when formula_7; a tetrahedron when formula_8, and so on. Let formula_9 be the Euclidean distances between vertices formula_10 and formula_11. The content, i.e. the "n"-dimensional volume of this simplex, denoted by formula_12, can be expressed as a function of determinants of certain matrices, as follows:
This is the Cayley–Menger determinant. For formula_14 it is a symmetric polynomial in the formula_15's and is thus invariant under permutation of these quantities. This fails for formula_16 but it is always invariant under permutation of the vertices.
Except for the final row and column of 1s, the matrix in the second form of this equation is a Euclidean distance matrix.
Special cases.
2-Simplex.
To reiterate, a simplex is an "n"-dimensional polytope and the convex hull of formula_4 points which do not lie in any formula_18 dimensional plane. Therefore, a 2-simplex occurs when formula_14 and the simplex results in a triangle. Therefore, the formula for determining formula_20 of a triangle is provided below:
formula_21
As a result, the equation above presents the content of a 2-simplex (area of a planar triangle with side lengths formula_22, formula_23, and formula_24) and it is a generalised form of Heron's Formula.
3-Simplex.
Similarly, a 3-simplex occurs when formula_25 and the simplex results in a tetrahedron. Therefore, the formula for determining formula_20 of a tetrahedron is provided below:
formula_27
As a result, the equation above presents the content of a 3-simplex, which is the volume of a tetrahedron where the edge between vertices formula_28 and formula_29 has length formula_30.
Proof.
Let the column vectors formula_3 be formula_4 points in formula_33-dimensional Euclidean space. Starting with the volume formula
we note that the determinant is unchanged when we add an extra row and column to make an formula_35 matrix,
where formula_37 is the square of the length of the vector formula_38. Additionally, we note that the formula_35 matrix
has a determinant of formula_41. Thus,
Generalization to hyperbolic and spherical geometry.
There are spherical and hyperbolic generalizations. A proof can be found here.
In a spherical space of dimension formula_18 and constant curvature formula_44, any formula_45 points satisfy
where formula_47, and formula_30 is the spherical distance between points formula_49.
In a hyperbolic space of dimension formula_18 and constant curvature formula_51, any formula_45 points satisfy
where formula_54, and formula_30 is the hyperbolic distance between points formula_49.
Example.
In the case of formula_57, we have that formula_58 is the area of a triangle and thus we will denote this by formula_59. By the Cayley–Menger determinant, where the triangle has side lengths formula_22, formula_23 and formula_24,
The result in the third line is due to the Fibonacci identity. The final line can be rewritten to obtain Heron's formula for the area of a triangle given three sides, which was known to Archimedes prior.
In the case of formula_25, the quantity formula_65 gives the volume of a tetrahedron, which we will denote by formula_66. For distances between formula_10 and formula_38 given by formula_30, the Cayley–Menger determinant gives
Finding the circumradius of a simplex.
Given a nondegenerate "n"-simplex, it has a circumscribed "n"-sphere, with radius formula_71. Then the ("n" + 1)-simplex made of the vertices of the "n"-simplex and the center of the "n"-sphere is degenerate. Thus, we have 
In particular, when formula_73, this gives the circumradius of a triangle in terms of its edge lengths.
Set Classifications.
From these determinants, we also have the following classifications:
Straight.
A set Λ (with at least three distinct elements) is called straight if and only if, for any three elements "A", "B", and "C" of Λ,
Plane.
A set Π (with at least four distinct elements) is called plane if and only if, for any four elements "A", "B", "C" and "D" of Π,
but not all triples of elements of Π are straight to each other;
Flat.
A set Φ (with at least five distinct elements) is called flat if and only if, for any five elements "A", "B", "C", "D" and "E" of Φ,
but not all quadruples of elements of Φ are plane to each other; and so on.
Menger's Theorem.
Karl Menger made a further discovery after the development of the Cayley-Menger determinant, which became known as Menger's Theorem. The theorem states: 
In simpler terms, if every subset of formula_79 points can be isometrically embedded in an formula_82 but not generally formula_83dimensional Euclidean space, then the semimetric is Euclidean of dimension formula_33 unless formula_85 consists of exactly formula_80 points and the Cayley-Menger determinant on those formula_80 points is strictly negative. This type of semimetric would be classified "pseudo-Euclidean".
Realization of a Euclidean distance matrix.
Given the Cayley-Menger relations as explained above, the following section will bring forth two algorithms to decide whether a given matrix is a distance matrix corresponding to a Euclidean point set. The first algorithm will do so when given a matrix AND the dimension, formula_88, via a geometric constraint solving algorithm. The second algorithm does so when the dimension, formula_88, is not provided. This algorithm theoretically finds a realization of the full formula_90 Euclidean distance matrix in the smallest possible embedding dimension in quadratic time.
Theorem (d is given).
For the sake and context of the following theorem, algorithm, and example, slightly different notation will be used than before resulting in an altered formula for the volume of the formula_91 dimensional simplex below than above.
As stated before, the purpose to this theorem comes from the following algorithm for realizing a Euclidean Distance Matrix or a Gramian Matrix.
Example.
Let each point formula_110 have coordinates formula_115. To place the first three points:
formula_121
formula_122
In order to find a realization using the above algorithm, the discriminant of the distance quadratic system must be positive, which is equivalent to formula_123 having positive volume. In general, the volume of the formula_91 dimensional simplex formed by the formula_125 vertices is given by
formula_126.
In this formula above, formula_127 is the Cayley-Menger determinant. This volume being positive is equivalent to the determinant of the volume matrix being positive.
Theorem (d not given).
"Let K be a positive integer and D be a n" × "n symmetric hollow matrix with nonnegative elements, with n" ≥ 2." D is a Euclidean distance matrix with dim(D) = K if and only if there exist "formula_128" and an index set I = "formula_129 "such that"
"where" formula_131 "realizes D, where" formula_132 "denotes the formula_133 component of the formula_134 vector."
The extensive proof of this theorem can be found at the following reference.
Algorithm - K = edmsph("D, x").
formula_135
formula_136
formula_137
formula_138
end for 
return K