HOME

TheInfoList



OR:

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 matrix (mathemat ...
,
geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...
, and
trigonometry Trigonometry () is a branch of mathematics concerned with relationships between angles and side lengths of triangles. In particular, the trigonometric functions relate the angles of a right triangle with ratios of its side lengths. The fiel ...
, the Cayley–Menger determinant is a formula for the content, i.e. the higher-dimensional
volume Volume is a measure of regions in 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) ...
, of a n-dimensional simplex in terms of the squares of all of the
distance Distance is a numerical or occasionally qualitative measurement of how far apart objects, points, people, or ideas are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two co ...
s between pairs of its vertices. The determinant is named after Arthur Cayley and
Karl Menger Karl Menger (; January 13, 1902 – October 5, 1985) was an Austrian-born American mathematician, the son of the economist Carl Menger. In mathematics, Menger studied the theory of algebra over a field, algebras and the dimension theory of low-r ...
. The n(n-1)/2 pairwise distance polynomials between points in a real
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
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, as well as computing the content of a -dimensional simplex, and ultimately determining if any real
symmetric matrix In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally, Because equal matrices have equal dimensions, only square matrices can be symmetric. The entries of a symmetric matrix are symmetric with ...
is a Euclidean distance matrix for some points in the field of distance geometry.


History

Karl Menger Karl Menger (; January 13, 1902 – October 5, 1985) was an Austrian-born American mathematician, the son of the economist Carl Menger. In mathematics, Menger studied the theory of algebra over a field, algebras and the dimension theory of low-r ...
was a young geometry professor at the
University of Vienna The University of Vienna (, ) is a public university, public research university in Vienna, Austria. Founded by Rudolf IV, Duke of Austria, Duke Rudolph IV in 1365, it is the oldest university in the German-speaking world and among the largest ...
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.
Six Mathematical Gems from the History of Distance Geometry
'


Definition

Let A_0, A_1,\ldots, A_n be n+1 points in k -dimensional
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
, with k \ge n. These points are the vertices of an -dimensional simplex: a triangle when n = 2; a
tetrahedron In geometry, a tetrahedron (: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular Face (geometry), faces, six straight Edge (geometry), edges, and four vertex (geometry), vertices. The tet ...
when n = 3, and so on. Let d_ be the
Euclidean distance In mathematics, the Euclidean distance between two points in Euclidean space is the length of the line segment between them. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, and therefore is o ...
s between vertices A_i and A_j. The content, i.e. the -dimensional volume of this simplex, denoted by v_n, can be expressed as a function of
determinant In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
s of certain matrices, as follows:Cayley-Menger Determinant
' ''
: \begin v_n^2 & = \frac \begin 2d_^2 & d_^2 + d_^2 - d_^2 & \cdots & d_^2 + d_^2 - d_^2 \\ d_^2 + d_^2 - d_^2 & 2d_^2 & \cdots & d_^2 + d_^2 - d_^2 \\ \vdots & \vdots & \ddots & \vdots \\ d_^2 + d_^2 - d_^2 & d_^2 + d_^2 - d_^2 & \cdots & 2d_^2 \end \\ 0pt& = \frac \begin 0 & d_^2 & d_^2 & \cdots & d_^2 & 1 \\ d_^2 & 0 & d_^2 & \cdots & d_^2 & 1 \\ d_^2 & d_^2 & 0 & \cdots & d_^2 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ d_^2 & d_^2 & d_^2 & \cdots & 0 & 1 \\ 1 & 1 & 1 & \cdots & 1 & 0 \end. \end This is the Cayley–Menger determinant. For n=2 it is a symmetric polynomial in the d_ 's and is thus invariant under permutation of these quantities. This fails for n>2, 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. Compare this to the usual formula for the oriented volume of a simplex, namely \tfrac1 times the determinant of the matrix composed of the edge vectors A_1-A_0,\ldots, A_n-A_0. 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.


Special cases


2-Simplex

To reiterate, a simplex is an -dimensional polytope and the
convex hull In geometry, the convex hull, 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 n+1 points which do not lie in any (n-1) dimensional plane.Simplex ''Encyclopedia of Mathematics''
/ref> Therefore, a 2-simplex occurs when n=2 and the simplex results in a triangle. Therefore, the formula for determining V_j^2 of a triangle is provided below: -16\Delta^2 = \begin 0 & 1 & 1 & 1\\ 1 & 0 & c^2 & b^2\\ 1 & c^2 & 0 & a^2\\ 1 & b^2 & a^2 & 0\\ \end As a result, the equation above presents the content of a 2-simplex (area of a planar triangle with side lengths a, b, and c) and it is a generalised form of Heron's Formula.


3-Simplex

Similarly, a 3-simplex occurs when n=3 and the simplex results in a tetrahedron. Therefore, the formula for determining V_j^2 of a tetrahedron is provided below: 288 V^2 = \begin 0 & 1 & 1 & 1 & 1\\ 1 & 0 & d_^2 & d_^2 & d_^2\\ 1 & d_^2 & 0 & d_^2 & d_^2\\ 1 & d_^2 & d_^2 & 0 & d_^2\\ 1 & d_^2 & d_^2 & d_^2 & 0\\ \end 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 i and j has length d_.


Proof

Let the column vectors A_0, A_1,\ldots, A_n be n+1 points in n-dimensional Euclidean space. Starting with the volume formula v_n = \frac \left, \det \begin A_0 & A_1 & \cdots & A_n \\ 1 & 1 & \cdots & 1 \end \\,, we note that the determinant is unchanged when we add an extra row and column to make an (n+2)\times(n+2) matrix, P = \begin A_0 & A_1 & \cdots & A_n & 0 \\ 1 & 1 & \cdots & 1 & 0 \\ \, A_0\, ^2 & \, A_1\, ^2 & \cdots & \, A_n\, ^2 & 1 \end\,, where \, A_j\, ^2 is the square of the length of the vector A_j. Additionally, we note that the (n+2)\times(n+2) matrix Q = \begin -2 & 0 & \cdots & 0 & 0 & 0 \\ 0 & -2 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & -2 & 0 & 0 \\ 0 & 0 & \cdots & 0 & 0 & 1 \\ 0 & 0 & \cdots & 0 & 1 & 0 \end has a determinant of (-2)^n(-1) = (-1)^ 2^n. Thus, \det \begin 0 & d_^2 & d_^2 & \cdots & d_^2 & 1 \\ d_^2 & 0 & d_^2 & \cdots & d_^2 & 1 \\ d_^2 & d_^2 & 0 & \cdots & d_^2 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ d_^2 & d_^2 & d_^2 & \cdots & 0 & 1 \\ 1 & 1 & 1 & \cdots & 1 & 0 \end = \det(P^T Q P) = \det(Q) \det(P)^2 = (-1)^ 2^n (n!)^2 v_n^2\,.


Example

In the case of n = 2 , we have that v_2 is the
area Area is the measure of a region's size on a surface. The area of a plane region or ''plane area'' refers to the area of a shape or planar lamina, while '' surface area'' refers to the area of an open surface or the boundary of a three-di ...
of a
triangle A triangle is a polygon with three corners and three sides, one of the basic shapes in geometry. The corners, also called ''vertices'', are zero-dimensional points while the sides connecting them, also called ''edges'', are one-dimension ...
and thus we will denote this by A . By the Cayley–Menger determinant, where the triangle has side lengths a, b and c, \begin 16A^2 &= \begin 2a^2 & a^2+b^2-c^2 \\ a^2+b^2-c^2 & 2b^2 \end \\ pt&= 4a^2b^2 - (a^2+b^2-c^2)^2 \\ pt&= (a^2+b^2+c^2)^2 - 2(a^4+b^4+c^4) \\ pt&= (a+b+c)(a+b-c)(a-b+c)(-a+b+c) \end 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 n=3, the quantity v_3 gives the volume of a
tetrahedron In geometry, a tetrahedron (: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular Face (geometry), faces, six straight Edge (geometry), edges, and four vertex (geometry), vertices. The tet ...
, which we will denote by V. For distances between A_i and A_j given by d_, the Cayley–Menger determinant gives \begin 144V^2 = & \frac \begin 2d_^2 & d_^2+d_^2-d_^2 & d_^2+d_^2-d_^2 \\ d_^2+d_^2-d_^2 & 2d_^2 & d_^2+d_^2-d_^2 \\ d_^2+d_^2-d_^2 & d_^2+d_^2-d_^2 & 2d_^2 \end \\ pt= & 4d_^2 d_^2 d_^2 + (d_^2+d_^2-d_^2)(d_^2+d_^2-d_^2)(d_^2+d_^2-d_^2) \\ pt& -d_^2(d_^2+d_^2-d_^2)^2 - d_^2(d_^2+d_^2-d_^2)^2 - d_^2(d_^2+d_^2-d_^2)^2. \end


Finding the circumradius of a simplex

Given a nondegenerate -simplex, it has a circumscribed -sphere, with radius r. Then the -simplex made of the vertices of the -simplex and the center of the -sphere is degenerate. Thus, we have \begin 0 & r^2 & r^2 & r^2 & \cdots & r^2 & 1 \\ r^2 & 0 & d_^2 & d_^2 & \cdots & d_^2 & 1 \\ r^2 & d_^2 & 0 & d_^2 & \cdots & d_^2 & 1 \\ r^2 & d_^2 & d_^2 & 0 & \cdots & d_^2 & 1 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ r^2 & d_^2 & d_^2 & d_^2 & \cdots & 0 & 1 \\ 1 & 1 & 1 & 1 & \cdots & 1 & 0 \end = 0\,. Using \beginA & B \\ C & D\end = \beginD\end \beginA - B D^ C\end, \beginD\end \ne 0, and A = \left(\begin0\end\right), this is equivalent to \left( \begin r^2 & r^2 & r^2 & \cdots & r^2 & 1 \end \right) \left( \begin 0 & d_^2 & d_^2 & \cdots & d_^2 & 1 \\ d_^2 & 0 & d_^2 & \cdots & d_^2 & 1 \\ d_^2 & d_^2 & 0 & \cdots & d_^2 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ d_^2 & d_^2 & d_^2 & \cdots & 0 & 1 \\ 1 & 1 & 1 & \cdots & 1 & 0 \end \right)^ \left( \begin r^2 \\ r^2 \\ r^2 \\ \vdots \\ r^2 \\ 1 \end \right) = 0\,. It is a quadratic function of . For example, when n = 2 , 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" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
, for any three elements , , and of ,Distance Geometry Wiki Page
/ref> :: \det \begin 0 & d(AB)^2 & d(AC)^2 & 1 \\ d(AB)^2 & 0 & d(BC)^2 & 1 \\ d(AC)^2 & d(BC)^2 & 0 & 1 \\ 1 & 1 & 1 & 0 \end = 0


Plane

A set (with at least four distinct elements) is called plane if and only if, for any four elements , , and of , :: \det \begin 0 & d(AB)^2 & d(AC)^2 & d(AD)^2 & 1 \\ d(AB)^2 & 0 & d(BC)^2 & d(BD)^2 & 1 \\ d(AC)^2 & d(BC)^2 & 0 & d(CD)^2 & 1 \\ d(AD)^2 & d(BD)^2 & d(CD)^2 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end = 0 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 , , , and of , :: \det \begin 0 & d(AB)^2 & d(AC)^2 & d(AD)^2 & d(AE)^2 & 1 \\ d(AB)^2 & 0 & d(BC)^2 & d(BD)^2 & d(BE)^2 & 1 \\ d(AC)^2 & d(BC)^2 & 0 & d(CD)^2 & d(CE)^2 & 1 \\ d(AD)^2 & d(BD)^2 & d(CD)^2 & 0 & d(DE)^2 & 1 \\ d(AE)^2 & d(BE)^2 & d(CE)^2 & d(DE)^2 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 \end = 0 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: :: For a
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, is a finite set with five elements. Th ...
of points A, a semi-metric \rho: A \times A \rightarrow \mathbb_ can be obtained from a Euclidean metric of dimension n if and only if every Cayley-Menger determinant on n+1 points is strictly positive, every determinant on n+2 points vanishes, and a Cayley-Menger determinant on at least one set of n+3 points is nonnegative (in which case it is necessarily zero). In simpler terms, if every subset of n+2 points can be isometrically embedded in an n-dimensional, but not generally (n-1)-dimensional Euclidean space, then the semi-metric is Euclidean of dimension n unless A consists of exactly n+3 points and the Cayley–Menger determinant on those n+3 points is strictly negative. This type of semi-metric would be classified as ''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, d, via
geometric constraint solving
algorithm. The second algorithm does so when the dimension, d, is not provided. This algorithm theoretically finds a realization of the full n \times n 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 n-1 dimensional simplex below than above. : Theorem. An n \times n matrix \Delta is a Euclidean Distance Matrix if and only if for all k \times k submatrices S of \Delta , where k \leq n , \det (\hat) \geq 0 . For \Delta to have a realization in dimension d , if , S, = k \geq d + 2 , then \det (\hat) = 0 .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 \Delta or Gramian Matrix \Gamma . ; Output : Pointset P ; Procedure * If the dimension d is fixed, we can solve a system of polynomial equations, one for each inner product entry of \Gamma , where the variables are the coordinates of each point p_1, ..., p_n in the desired dimension d. * Otherwise, we can solve for one point at a time. ** Solve for the coordinates of p_k using its distances to all previously placed points p_1, ..., p_ . Thus, p_k is represented by at most k - 1 coordinate values, ensuring minimum dimension and complexity.


Example

Let each point p_k have coordinates . To place the first three points: # Put p_1 at the origin, so p_1 = . # Put p_2 on the first axis, so p_2 = . # To place p_3 : \begin (p^1_1 - p^1_3)^2 + (p^2_1 - p^2_3)^2 = (\delta_)^2\\ (p^1_2 - p^1_3)^2 + (p^2_2 - p^2_3)^2 = (\delta_)^2 \end \rightarrow \begin p^1_3 = \frac\\ p^2_3 = \frac \end In order to find a realization using the above algorithm, the discriminant of the distance quadratic system must be positive, which is equivalent to \Delta p_1p_2p_3 having positive volume. In general, the volume of the n-1 dimensional simplex formed by the n vertices is given by V^_ = \frac \det (\hat) . In this formula above, \det (\hat) 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 be a positive integer and be a symmetric hollow matrix with nonnegative elements, with . is a Euclidean distance matrix with if and only if there exist \_^n \subseteq \mathbb^K and an index set \ \subseteq I_n such that \begin x_i = 0 \\ x_ (j -1) \ne 0, & \mbox j \in I_ \\ x_ (i) = 0, & \mbox j \in I_, i \in I_, \end where \_^n realizes , where x_h(l) denotes the l^ component of the h^ vector.
The extensive proof of this theorem can be found at the following reference.Realizing Euclidean Distance Matrices by Sphere Intersection
/ref>


Algorithm - K = edmsph(''D'', ''x'')

Source: I = \ K = 1 (x_1, x_2) = (0, \sqrt) \text \in \\text : Γ = \bigcap_ S^K(x_j, D_) : if Γ = ∅; then :: return ∞ : else if Γ = \ \text then :: x_i = p_i : else if Γ = \ \text then :: x_i = p_i^+ :: x ← expand(x) :: :: : else :: error: : end if end for return K


See also

* Distance Geometry''
'' *
Euclidean Space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
''
'' * Euclidean Distance Matrix''
'' * Simplex''
'' * Heron's Formula


Notes


References

{{DEFAULTSORT:Cayley-Menger determinant Determinants