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 ${\textstyle n}$ -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 ${n \choose 2}$ pairwise distance polynomials between n points in a real Euclidean space are Euclidean invariants that are associated via the Cayley-Menger relations.[1] 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.[2]

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.[3]

Definition

Let ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$ be $n+1$ points in $k$ -dimensional Euclidean space, with $k\geq n$ [lower-alpha 1]. These points are the vertices of an n-dimensional simplex: a triangle when $n=2$ ; a tetrahedron when $n=3$ , and so on. Let ${\textstyle d_{ij}}$ be the Euclidean distances between vertices $A_{i}$ and ${\textstyle A_{j}}$ . The content, i.e. the n-dimensional volume of this simplex, denoted by $v_{n}$ , can be expressed as a function of determinants of certain matrices, as follows:[4][5]

{\begin{aligned}v_{n}^{2}&={\frac {1}{(n!)^{2}2^{n}}}{\begin{vmatrix}2d_{01}^{2}&d_{01}^{2}+d_{02}^{2}-d_{12}^{2}&\cdots &d_{01}^{2}+d_{0n}^{2}-d_{1n}^{2}\\d_{01}^{2}+d_{02}^{2}-d_{12}^{2}&2d_{02}^{2}&\cdots &d_{02}^{2}+d_{0n}^{2}-d_{2n}^{2}\\\vdots &\vdots &\ddots &\vdots \\d_{01}^{2}+d_{0n}^{2}-d_{1n}^{2}&d_{02}^{2}+d_{0n}^{2}-d_{2n}^{2}&\cdots &2d_{0n}^{2}\end{vmatrix}}\\[10pt]&={\frac {(-1)^{n+1}}{(n!)^{2}2^{n}}}{\begin{vmatrix}0&d_{01}^{2}&d_{02}^{2}&\cdots &d_{0n}^{2}&1\\d_{01}^{2}&0&d_{12}^{2}&\cdots &d_{1n}^{2}&1\\d_{02}^{2}&d_{12}^{2}&0&\cdots &d_{2n}^{2}&1\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\d_{0n}^{2}&d_{1n}^{2}&d_{2n}^{2}&\cdots &0&1\\1&1&1&\cdots &1&0\end{vmatrix}}.\end{aligned}}

This is the Cayley–Menger determinant. For $n=2$ it is a symmetric polynomial in the $d_{ij}$ '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.[lower-alpha 2]

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 $n+1$ points which do not lie in any $(n-1)$ dimensional plane.[6] 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:[5]

$-16\Delta ^{2}={\begin{vmatrix}0&1&1&1\\1&0&c^{2}&b^{2}\\1&c^{2}&0&a^{2}\\1&b^{2}&a^{2}&0\\\end{vmatrix}}$

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.[5]

3-Simplex

Similarly, a 3-simplex occurs when $n=3$ and the simplex results in a tetrahedron.[6] Therefore, the formula for determining $V_{j}^{2}$ of a tetrahedron is provided below:[5]

$288V^{2}={\begin{vmatrix}0&1&1&1&1\\1&0&d_{12}^{2}&d_{13}^{2}&d_{14}^{2}\\1&d_{21}^{2}&0&d_{23}^{2}&d_{24}^{2}\\1&d_{31}^{2}&d_{32}^{2}&0&d_{34}^{2}\\1&d_{41}^{2}&d_{42}^{2}&d_{43}^{2}&0\\\end{vmatrix}}$

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_{ij}$ .[5]

Proof

Let the column vectors ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$ be $n+1$ points in $n$ -dimensional Euclidean space. Starting with the volume formula

v_{n}={\frac {1}{n!}}\left|\det {\begin{pmatrix}A_{0}&A_{1}&\cdots &A_{n}\\1&1&\cdots &1\end{pmatrix}}\right|\,,

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{pmatrix}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{pmatrix}}\,,

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{pmatrix}-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{pmatrix}}

has a determinant of $(-2)^{n}(-1)=(-1)^{n+1}2^{n}$ . Thus,[7]

\det {\begin{pmatrix}0&d_{01}^{2}&d_{02}^{2}&\cdots &d_{0n}^{2}&1\\d_{01}^{2}&0&d_{12}^{2}&\cdots &d_{1n}^{2}&1\\d_{02}^{2}&d_{12}^{2}&0&\cdots &d_{2n}^{2}&1\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\d_{0n}^{2}&d_{1n}^{2}&d_{2n}^{2}&\cdots &0&1\\1&1&1&\cdots &1&0\end{pmatrix}}=\det(P^{T}QP)=\det(Q)\det(P)^{2}=(-1)^{n+1}2^{n}(n!)^{2}v_{n}^{2}\,.

Generalization to hyperbolic and spherical geometry

There are spherical and hyperbolic generalizations.[8] A proof can be found here.[9]

In a spherical space of dimension $(n-1)$ and constant curvature $1/R^{2}$ , any $(n+1)$ points satisfy

{\begin{vmatrix}0&f(d_{01})&f(d_{02})&\cdots &f(d_{0n})&1\\f(d_{01})&0&f(d_{12})&\cdots &f(d_{1n})&1\\f(d_{02})&f(d_{12})&0&\cdots &f(d_{2n})&1\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\f(d_{0n})&f(d_{1n})&f(d_{2n})&\cdots &0&1\\1&1&1&\cdots &1&{\frac {1}{2R^{2}}}\end{vmatrix}}=0

where $f(d)=2R^{2}\left(1-\cos {\frac {d}{R}}\right)$ , and $d_{ij}$ is the spherical distance between points $i,j$ .

In a hyperbolic space of dimension $(n-1)$ and constant curvature $-1/R^{2}$ , any $(n+1)$ points satisfy

{\begin{vmatrix}0&f(d_{01})&f(d_{02})&\cdots &f(d_{0n})&1\\f(d_{01})&0&f(d_{12})&\cdots &f(d_{1n})&1\\f(d_{02})&f(d_{12})&0&\cdots &f(d_{2n})&1\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\f(d_{0n})&f(d_{1n})&f(d_{2n})&\cdots &0&1\\1&1&1&\cdots &1&-{\frac {1}{2R^{2}}}\end{vmatrix}}=0

where $f(d)=2R^{2}\left(\cosh {\frac {d}{R}}-1\right)$ , and $d_{ij}$ is the hyperbolic distance between points $i,j$ .

Example

In the case of $n=2$ , we have that $v_{2}$ is the area of a triangle and thus we will denote this by $A$ . By the Cayley–Menger determinant, where the triangle has side lengths $a$ , $b$ and $c$ ,

{\begin{aligned}16A^{2}&={\begin{vmatrix}2a^{2}&a^{2}+b^{2}-c^{2}\\a^{2}+b^{2}-c^{2}&2b^{2}\end{vmatrix}}\\[8pt]&=4a^{2}b^{2}-(a^{2}+b^{2}-c^{2})^{2}\\[6pt]&=(a^{2}+b^{2}+c^{2})^{2}-2(a^{4}+b^{4}+c^{4})\\[6pt]&=(a+b+c)(a+b-c)(a-b+c)(-a+b+c)\end{aligned}}

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.[10]

In the case of $n=3$ , the quantity $v_{3}$ gives the volume of a tetrahedron, which we will denote by $V$ . For distances between $A_{i}$ and $A_{j}$ given by $d_{ij}$ , the Cayley–Menger determinant gives[11][12]

{\begin{aligned}144V^{2}={}&{\frac {1}{2}}{\begin{vmatrix}2d_{01}^{2}&d_{01}^{2}+d_{02}^{2}-d_{12}^{2}&d_{01}^{2}+d_{03}^{2}-d_{13}^{2}\\d_{01}^{2}+d_{02}^{2}-d_{12}^{2}&2d_{02}^{2}&d_{02}^{2}+d_{03}^{2}-d_{23}^{2}\\d_{01}^{2}+d_{03}^{2}-d_{13}^{2}&d_{02}^{2}+d_{03}^{2}-d_{23}^{2}&2d_{03}^{2}\end{vmatrix}}\\[8pt]={}&4d_{01}^{2}d_{02}^{2}d_{03}^{2}+(d_{01}^{2}+d_{02}^{2}-d_{12}^{2})(d_{01}^{2}+d_{03}^{2}-d_{13}^{2})(d_{02}^{2}+d_{03}^{2}-d_{23}^{2})\\[6pt]&{}-d_{01}^{2}(d_{02}^{2}+d_{03}^{2}-d_{23}^{2})^{2}-d_{02}^{2}(d_{01}^{2}+d_{03}^{2}-d_{13}^{2})^{2}-d_{03}^{2}(d_{01}^{2}+d_{02}^{2}-d_{12}^{2})^{2}.\end{aligned}}

Finding the circumradius of a simplex

Given a nondegenerate n-simplex, it has a circumscribed n-sphere, with radius $r$ . 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

{\begin{vmatrix}0&r^{2}&r^{2}&r^{2}&\cdots &r^{2}&1\\r^{2}&0&d_{01}^{2}&d_{02}^{2}&\cdots &d_{0n}^{2}&1\\r^{2}&d_{01}^{2}&0&d_{12}^{2}&\cdots &d_{1n}^{2}&1\\r^{2}&d_{02}^{2}&d_{12}^{2}&0&\cdots &d_{2n}^{2}&1\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\r^{2}&d_{0n}^{2}&d_{1n}^{2}&d_{2n}^{2}&\cdots &0&1\\1&1&1&1&\cdots &1&0\end{vmatrix}}=0

In particular, 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, for any three elements A, B, and C of Λ,[13]

\det {\begin{bmatrix}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{bmatrix}}=0

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 Π,[13]

\det {\begin{bmatrix}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{bmatrix}}=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 A, B, C, D and E of Φ,[13]

\det {\begin{bmatrix}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{bmatrix}}=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:

A semimetric

\rho :A\times A\rightarrow \mathbb {R} _{\geq 0}

is Euclidean of dimension n if and only if all Cayley-Menger determinants on

n+1

points is strictly positive, all determinants on

n+2

points vanish, and a Cayley-Menger determinant on at least one set of

n+3

points is nonnegative (in which case it is necessarily zero).[1]

In simpler terms, if every subset of $n+2$ points can be isometrically embedded in an $n-$ but not generally $(n-1)-$ dimensional Euclidean space, then the semimetric 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 semimetric would be classified pseudo-Euclidean.[1]

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 a 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 {\delta _{S}}})\geq 0

. For

\Delta

to have a realization in dimension

d

, if

|S|=k\geq d+2

, then

\det({\hat {\delta _{S}}})=0

.[14]

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_{k-1}$ . 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 ${p_{k}^{1},p_{k}^{2},...}$ . To place the first three points:

Put $p_{1}$ at the origin, so $p_{1}={0,0,...}$ .
Put $p_{2}$ on the first axis, so $p_{2}={(\delta _{12})^{2},0,...}$ .
To place $p_{3}$ :

${\begin{cases}(p_{1}^{1}-p_{3}^{1})^{2}+(p_{1}^{2}-p_{3}^{2})^{2}=(\delta _{13})^{2}\\(p_{2}^{1}-p_{3}^{1})^{2}+(p_{2}^{2}-p_{3}^{2})^{2}=(\delta _{23})^{2}\end{cases}}$ $\rightarrow {\begin{cases}p_{3}^{1}={\frac {(\delta _{12})^{2}+(\delta _{13})^{2}-(\delta _{23})^{2}}{2\delta _{12}}}\\p_{3}^{2}={\frac {\sqrt {(\delta _{31}+\delta _{32}+\delta _{12})(\delta _{31}+\delta _{32}-\delta _{12})(\delta _{31}-\delta _{32}+\delta _{12})(-\delta _{31}+\delta _{32}+\delta _{12})}}{2\delta _{01}}}\end{cases}}$

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_{1}p_{2}p_{3}$ having positive volume. In general, the volume of the $n-1$ dimensional simplex formed by the $n$ vertices is given by[14]

$V_{n-1}^{2}={\frac {(-1)^{n}}{2^{n-1}(n-1!)^{2}}}\det({\hat {\Delta }})$ .

In this formula above, $\det({\hat {\Delta }})$ 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 $\{x_{i}\}_{i=1}^{n}\subseteq \mathbb {R} ^{K}$ and an index set I = $\{i_{1},...,i_{K+1}\}\subseteq I_{n}$ such that

${\begin{cases}x_{i}=0\\x_{i_{j}}(j-1)\neq 0,&{\mbox{ }}j\in I_{2,K+1}\\x_{i_{j}}(i)=0,&{\mbox{ }}j\in I_{2,K},i\in I_{j,K},\end{cases}}$

where $\{x_{i}\}_{i=1}^{n}$ realizes D, where $x_{h}(l)$ denotes the $l^{th}$ component of the $h^{th}$ vector.

The extensive proof of this theorem can be found at the following reference.[15]

Algorithm - K = edmsph(D, x)

Source:[15]

$I=\{1,2\}$ $K=1$ $(x_{1},x_{2})=(0,{\sqrt {D_{12}}})$ ${\text{for i}}\in \{3,...,n\}{\text{ do}}$

Γ

=\bigcap _{j\in I}S^{K}(x_{j},D_{ij})

if Γ

=

∅; then

return ∞

else if Γ

=\{p_{i}\}{\text{  }}then

x_{i}=p_{i}

else if Γ

=\{p_{i}^{+},p_{i}^{-}\}{\text{  }}then

x_{i}=p_{i}^{+}

x

← expand(

x

)

I ← I ∪ {i}

K ← K + 1

else

error: dim aff(span(

x_{j}

)) < K - 1

end if

end for return K

Notes

An n-dimensional body can't be immersed into k-dimensional space if $k<n.$
The (hyper)volume of a figure does not depend on its vertices' numbering order.

References

Sitharam, Meera; St. John, Audrey; Sidman, Jessica. Handbook of Geometric Constraint Systems Principles. Boca Raton, FL: CRC Press. ISBN 978-1-4987-3891-0
http://ufo2.cise.ufl.edu/index.php/Distance_Geometry Distance Geometry
Six Mathematical Gems from the History of Distance Geometry
Sommerville, D. M. Y. (1958). An Introduction to the Geometry of n Dimensions. New York: Dover Publications.
Cayley-Menger Determinant
Simplex Encyclopedia of Mathematics
"Simplex Volumes and the Cayley–Menger Determinant". www.mathpages.com. Archived from the original on 16 May 2019. Retrieved 2019-06-08.
Blumenthal, L. M.; Gillam, B. E. (1943). "Distribution of Points in n-Space". The American Mathematical Monthly. 50 (3): 181. doi:10.2307/2302400. JSTOR 2302400.
Tao, Terrence (2019-05-25). "The spherical Cayley–Menger determinant and the radius of the Earth". What's new. Retrieved 2019-06-10.
Heath, Thomas L. (1921). A History of Greek Mathematics (Vol II). Oxford University Press. pp. 321–323.
Audet, Daniel. "Déterminants sphérique et hyperbolique de Cayley–Menger" (PDF). Bulletin AMQ. LI: 45–52.
Dörrie, Heinrich (1965). 100 Great Problems of Elementary Mathematics. New York: Dover Publications. pp. 285–9.
Distance Geometry Wiki Page
Sitharam, Meera. "Lecture 1 through 6"." Geometric Complexity CIS6930, University of Florida. Received 28 Mar.2020
Realizing Euclidean Distance Matrices by Sphere Intersection

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[4] An n-dimensional body can't be immersed into k-dimensional space if $k<n.$

[7] The (hyper)volume of a figure does not depend on its vertices' numbering order.

[s1-1] Sitharam, Meera; St. John, Audrey; Sidman, Jessica. Handbook of Geometric Constraint Systems Principles. Boca Raton, FL: CRC Press. ISBN 978-1-4987-3891-0

[2] ttp://ufo2.cise.ufl.edu/index.php/Distance_Geometry Distance Geometry

[s2-3] Six Mathematical Gems from the History of Distance Geometry

[5] Sommerville, D. M. Y. (1958). An Introduction to the Geometry of n Dimensions. New York: Dover Publications.

[s3-6] Cayley-Menger Determinant

[s6-8] Simplex Encyclopedia of Mathematics

[9] "Simplex Volumes and the Cayley–Menger Determinant". www.mathpages.com. Archived from the original on 16 May 2019. Retrieved 2019-06-08.

[:0-10] Blumenthal, L. M.; Gillam, B. E. (1943). "Distribution of Points in n-Space". The American Mathematical Monthly. 50 (3): 181. doi:10.2307/2302400. JSTOR 2302400.

[11] Tao, Terrence (2019-05-25). "The spherical Cayley–Menger determinant and the radius of the Earth". What's new. Retrieved 2019-06-10.

[12] Heath, Thomas L. (1921). A History of Greek Mathematics (Vol II). Oxford University Press. pp. 321–323.

[13] Audet, Daniel. "Déterminants sphérique et hyperbolique de Cayley–Menger" (PDF). Bulletin AMQ. LI: 45–52.

[14] Dörrie, Heinrich (1965). 100 Great Problems of Elementary Mathematics. New York: Dover Publications. pp. 285–9.

[sFinal-15] Distance Geometry Wiki Page

[s7-16] Sitharam, Meera. "Lecture 1 through 6"." Geometric Complexity CIS6930, University of Florida. Received 28 Mar.2020

[s8-17] Realizing Euclidean Distance Matrices by Sphere Intersection

Cayley–Menger determinant

History

Definition

Special cases

2-Simplex

3-Simplex

Proof

Generalization to hyperbolic and spherical geometry

Example

Finding the circumradius of a simplex

Set Classifications

Straight

Plane

Flat

Menger's Theorem

Realization of a Euclidean distance matrix

Theorem (d is given)

Algorithm

Example

Theorem (d not given)

Algorithm - K = edmsph(D, x)

See also

Notes

References