In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...
,
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, and
trigonometry
Trigonometry () is a branch of mathematics that studies relationships between side lengths and angles of triangles. The field emerged in the Hellenistic world during the 3rd century BC from applications of geometry to astronomical studies. T ...
, the Cayley–Menger determinant is a formula for the content, i.e. the higher-dimensional
volume
Volume is a measure of occupied three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch). The de ...
, of a
-dimensional
simplex
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
in terms of the squares of all of the
distance
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
s between pairs of its vertices. The determinant is named after
Arthur Cayley
Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific United Kingdom of Great Britain and Ireland, British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics.
As a child, C ...
and
Karl Menger
Karl Menger (January 13, 1902 – October 5, 1985) was an Austrian-American mathematician, the son of the economist Carl Menger. In mathematics, Menger studied the theory of algebras and the dimension theory of low- regularity ("rough") curves a ...
.
The
pairwise distance polynomials between ''n'' points in a real
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
are Euclidean invariants that are associated via the Cayley-Menger relations.
[Sitharam, Meera; St. John, Audrey; Sidman, Jessica. ''Handbook of Geometric Constraint Systems Principles''. Boca Raton, FL: CRC Press. ] 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 Distance geometry is the branch of mathematics concerned with characterizing and studying sets of points based ''only'' on given values of the distances between pairs of points. More abstractly, it is the study of semimetric spaces and the isome ...
.
History
Karl Menger
Karl Menger (January 13, 1902 – October 5, 1985) was an Austrian-American mathematician, the son of the economist Carl Menger. In mathematics, Menger studied the theory of algebras and the dimension theory of low- regularity ("rough") curves a ...
was a young geometry professor at the University of Vienna and
Arthur Cayley
Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific United Kingdom of Great Britain and Ireland, British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics.
As a child, C ...
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 Distance geometry is the branch of mathematics concerned with characterizing and studying sets of points based ''only'' on given values of the distances between pairs of points. More abstractly, it is the study of semimetric spaces and the isome ...
,
Heron's formula
In geometry, Heron's formula (or Hero's formula) gives the area of a triangle in terms of the three side lengths , , . If s = \tfrac12(a + b + c) is the semiperimeter of the triangle, the area is,
:A = \sqrt.
It is named after first-century ...
, which computes the area of a triangle given its side lengths.
Six Mathematical Gems from the History of Distance Geometry
'
Definition
Let
be
points in
-dimensional
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
, with
. These points are the vertices of an ''n''-dimensional simplex: a triangle when
; a tetrahedron when
, and so on. Let
be the
Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
s between vertices
and
. The content, i.e. the ''n''-dimensional volume of this simplex, denoted by
, can be expressed as a function of
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
s of certain matrices, as follows:
[Cayley-Menger Determinant](_blank)
' ''
:
This is the Cayley–Menger determinant. For
it is a
symmetric polynomial
In mathematics, a symmetric polynomial is a polynomial in variables, such that if any of the variables are interchanged, one obtains the same polynomial. Formally, is a ''symmetric polynomial'' if for any permutation of the subscripts one has ...
in the
's and is thus invariant under permutation of these quantities. This fails for
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 In mathematics, a Euclidean distance matrix is an matrix representing the spacing of a set of points in Euclidean space.
For points x_1,x_2,\ldots,x_n in -dimensional space , the elements of their Euclidean distance matrix are given by squares o ...
.
Special cases
2-Simplex
To reiterate, a simplex is an ''n''-dimensional polytope and the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of
points which do not lie in any
dimensional plane.
[Simplex ''Encyclopedia of Mathematics'']
Therefore, a 2-simplex occurs when
and the simplex results in a triangle. Therefore, the formula for determining
of a triangle is provided below:
As a result, the equation above presents the content of a 2-simplex (area of a planar triangle with side lengths
,
, and
) and it is a generalised form of Heron's Formula.
3-Simplex
Similarly, a 3-simplex occurs when
and the simplex results in a tetrahedron.
Therefore, the formula for determining
of a tetrahedron is provided below:
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
and
has length
.
Proof
Let the column vectors
be
points in
-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
matrix,
:
where
is the square of the length of the vector
. Additionally, we note that the
matrix
:
has a determinant of
. 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
and constant curvature
, any
points satisfy
:
where
, and
is the
spherical distance
The great-circle distance, orthodromic distance, or spherical distance is the distance along a great circle.
It is the shortest distance between two points on the surface of a sphere, measured along the surface of the sphere (as opposed to a s ...
between points
.
In a
hyperbolic space
In mathematics, hyperbolic space of dimension n is the unique simply connected, n-dimensional Riemannian manifold of constant sectional curvature equal to -1. It is homogeneous, and satisfies the stronger property of being a symmetric space. Th ...
of dimension
and constant curvature
, any
points satisfy
:
where
, and
is the hyperbolic distance between points
.
Example
In the case of
, we have that
is the
area
Area is the quantity that expresses the extent of a region on the plane or on a curved surface. The area of a plane region or ''plane area'' refers to the area of a shape
A shape or figure is a graphics, graphical representation of an obje ...
of a
triangle
A triangle is a polygon with three Edge (geometry), edges and three Vertex (geometry), vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC.
In Euclidean geometry, an ...
and thus we will denote this by
. By the Cayley–Menger determinant, where the triangle has side lengths
,
and
,
:
The result in the third line is due to the
Fibonacci identity. The final line can be rewritten to obtain
Heron's formula
In geometry, Heron's formula (or Hero's formula) gives the area of a triangle in terms of the three side lengths , , . If s = \tfrac12(a + b + c) is the semiperimeter of the triangle, the area is,
:A = \sqrt.
It is named after first-century ...
for the area of a triangle given three sides, which was known to Archimedes prior.
In the case of
, the quantity
gives the volume of a
tetrahedron
In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the o ...
, which we will denote by
. For distances between
and
given by
, the Cayley–Menger determinant gives
:
Finding the circumradius of a simplex
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. Thus, we have
:
In particular, when
, 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
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
, for any three elements ''A'', ''B'', and ''C'' of Λ,
[Distance Geometry Wiki Page]
::
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
In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices.
Proved by Karl Menger in ...
. The theorem states:
:: ''A semimetric''
''is Euclidean of dimension n if and only if all Cayley-Menger determinants on''
''points is strictly positive, all determinants on''
''points vanish, and a Cayley-Menger determinant on at least one set of''
''points is nonnegative (in which case it is necessarily zero)''.
In simpler terms, if every subset of
points can be isometrically embedded in an
but not generally
dimensional Euclidean space, then the semimetric is Euclidean of dimension
unless
consists of exactly
points and the Cayley-Menger determinant on those
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,
, via
geometric constraint solvingalgorithm. The second algorithm does so when the dimension,
, is not provided. This algorithm theoretically finds a realization of the full
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
dimensional simplex below than above.
: Theorem. An
matrix
is a Euclidean Distance Matrix if and only if for all
submatrices
of
, where
,
. For
to have a realization in dimension
, if
, then
.
[ Sitharam, Meera. "Lecture 1 through 6"." Geometric Complexity CIS6930, University of Florida. Received 28 Mar.2020 ]
As stated before, the purpose to this theorem comes from the following algorithm for realizing a Euclidean Distance Matrix or a Gramian Matrix.
Algorithm
; Input
: Euclidean Distance Matrix or Gramian Matrix .
; Output
: Pointset
; Procedure
* If the dimension is fixed, we can solve a system of polynomial equations, one for each inner product entry of , where the variables are the coordinates of each point in the desired dimension .
* Otherwise, we can solve for one point at a time.
** Solve for the coordinates of using its distances to all previously placed points . Thus, is represented by at most coordinate values, ensuring minimum dimension and complexity.
Example
Let each point
have coordinates
. To place the first three points:
# Put
at the origin, so
.
# Put
on the first axis, so
.
# To place
:
In order to find a realization using the above algorithm, the
discriminant
In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the roots without computing them. More precisely, it is a polynomial function of the coefficients of the origi ...
of the distance quadratic system must be positive, which is equivalent to
having positive volume. In general, the volume of the
dimensional simplex formed by the
vertices is given by
.
In this formula above,
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 '''' and an index set I = '' ''such that''
:
''where'' ''realizes D, where'' ''denotes the component of the vector.''
The extensive proof of this theorem can be found at the following reference.
[Realizing Euclidean Distance Matrices by Sphere Intersection](_blank)
Algorithm - K = edmsph(''D, x'')
Source:
: Γ
: if Γ
∅; then
:: return ∞
: else if Γ
::
: else if Γ
::
::
← expand(
)
:: ''I'' ← ''I'' ∪
:: ''K'' ← ''K'' + 1
: else
:: error: dim aff(span(
)) < ''K'' - 1
: end if
end for
return K
See also
*
Distance Geometry Distance geometry is the branch of mathematics concerned with characterizing and studying sets of points based ''only'' on given values of the distances between pairs of points. More abstractly, it is the study of semimetric spaces and the isome ...
''
''
*
Euclidean Space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
''
''
*
Euclidean Distance Matrix In mathematics, a Euclidean distance matrix is an matrix representing the spacing of a set of points in Euclidean space.
For points x_1,x_2,\ldots,x_n in -dimensional space , the elements of their Euclidean distance matrix are given by squares o ...
''
''
*
Simplex
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
''
''
*
Heron's Formula
In geometry, Heron's formula (or Hero's formula) gives the area of a triangle in terms of the three side lengths , , . If s = \tfrac12(a + b + c) is the semiperimeter of the triangle, the area is,
:A = \sqrt.
It is named after first-century ...
Notes
References
{{DEFAULTSORT:Cayley-Menger determinant
Determinants