In linear algebra, geometry, and trigonometry, the Cayley–Menger determinant is a formula for the content, i.e. the higher-dimensional volume, of a
-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.
[1] These relations served multiple purposes such as generalising Heron's Formula, as well as computing the content of a n-dimensional simplex, and ultimately determining if any real symmetric matrix is a Euclidean distance matrix for some n + 1 points in the field of distance geometry.
[2] 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 results to propose a new axiom of metric spaces using the concepts of distance geometry up to congruence equivalence, 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.
[a] These points are the vertices of an n-dimensional simplex: a triangle when
The content, i.e. the n-dimensional volume of this simplex, denoted by
Compare this to the usual formula for the oriented volume of a simplex, namely
times the determinant of the n x n matrix composed of the n edge vectors
Unlike the Cayley-Menger determinant, the latter matrix changes with rotation of the simplex, though not with translation; regardless, its determinant and the resulting volume do not change.
To reiterate, a simplex is an n-dimensional polytope and the convex hull of
As a result, the equation above presents the content of a 2-simplex (area of a planar triangle with side lengths
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
we note that the determinant is unchanged when we add an extra row and column to make an
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.
Given a nondegenerate n-simplex, it has a circumscribed n-sphere, with radius
Then the (n + 1)-simplex made of the vertices of the n-simplex and the center of the n-sphere is degenerate.
, this gives the circumradius of a triangle in terms of its edge lengths.
The theorem states: In simpler terms, if every subset of
[1] 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.
This algorithm theoretically finds a realization of the full
Euclidean distance matrix in the smallest possible embedding dimension in quadratic time.
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
In order to find a realization using the above algorithm, the discriminant of the distance quadratic system must be positive, which is equivalent to
Let K be a positive integer and D be a 1n × 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
The extensive proof of this theorem can be found at the following reference.