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 an $n$-dimensional simplex in terms of the squares of all the distances between pairs of its vertices. This determinant is named after Arthur Cayley and Karl Menger.

The $n(n+1)/2$ pairwise distance polynomials between $n+1$ 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, as well as computing the content of an $n$-dimensional simplex, and ultimately, in the field of distance geometry, determining whether any real symmetric matrix is a Euclidean distance matrix for some $n+1$ points.

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 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 in terms of its side lengths.

Definition

Let $A_0,A_1,\dots ,A_n$ be $n+1$ points in $k$-dimensional Euclidean space, with Template:Tmath.Template:Efn These points are the vertices of an $n$-dimensional simplex: a triangle when Template:Tmath, a tetrahedron when Template:Tmath, and so on. Let $d_{ij}$ be the Euclidean distances between vertices $A_i$ and Template:Tmath. The content, i.e., the $n$-dimensional volume of this simplex, denoted by Template:Tmath, can be expressed as a function of $n$ and the determinant of a certain matrix, in two possible ways:

$$\begin{array}{cc}{v_n}^2& =\frac{1}{(n!{)}^2{2}^n}\left|\begin{array}{cccc}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\\ ⋮& ⋮& \ddots & ⋮\\ d_{01}^2+d_{0n}^2-d_{1n}^2& d_{02}^2+d_{0n}^2-d_{2n}^2& \cdots & 2d_{0n}^2\end{array}\right|\\ & =\frac{(-1{)}^{n+1}}{(n!{)}^2{2}^n}\left|\begin{array}{cccccc}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\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ d_{0n}^2& d_{1n}^2& d_{2n}^2& \cdots & 0& 1\\ 1& 1& 1& \cdots & 1& 0\end{array}\right|.\end{array}$$

This is the Cayley–Menger determinant. For Template:Tmath, we are dealing with a triangle, where swapping edges changes orientation (if orientable), but not area, thus it is necessarily a symmetric polynomial in the $d_{ij}$'s, and invariant under permutation of these quantities. For any larger n-simplex, where Template:Tmath, only in special cases will swapping edges be invariant.Template:Efn In particular, for Template:Tmath, swapping the distances between any pair of skew edges in a sufficiently irregular tetrahedron leads (at best) to a different tetrahedron, with a different determinant; even for the less aggressive case of swapping the distances between any pair of edges that share a vertex, this will flip the orientation of one face (formed by the three vertices of the connected edges), without flipping the orientation of their three connections to the 4th vertex, potentially forming a different tetrahedron, but this mutated object might not even be a viable tetrahedron, in the general case.

The final row and column of $1$'s (and $0$) in the second form of this equation could simultaneously be moved to be the first row and column, giving the same result. Regardless, except for that row and column, the matrix is a Euclidean distance matrix.

The usual formula for the oriented volume of a simplex is $\frac{1}{n!}$ times the determinant of the $n\times n$ matrix composed of the $n$ edge vectors Template:Tmath. 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

To reiterate, an $n$-simplex is an $n$-dimensional polytope and the convex hull of $n+1$ points which do not lie in any $(n-1)$-dimensional plane.

$2$-Simplex

Hence, a $2$-simplex occurs when $n=2$ and the simplex results in a triangle. Therefore, the formula for determining ${v_2}^2$ of a triangle is provided below:

$$-16{v_2}^2=\left|\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& c^2& b^2\\ 1& c^2& 0& a^2\\ 1& b^2& a^2& 0\end{array}\right|.$$

As a result, the equation above presents the content of a $2$-simplex (area of a planar triangle with side lengths Template:Tmath, Template:Tmath, and Template:Tmath) and it is a generalised form of Heron's Formula.

$3$-Simplex

Similarly, a Template:Tmath-simplex occurs when $n=3$ and the simplex results in a tetrahedron. Therefore, the formula for determining ${v_3}^2$ of a tetrahedron is provided below:

$$288{v_3}^2=\left|\begin{array}{ccccc}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{array}\right|.$$

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 Template:Tmath.

Proof

Let the column vectors $A_0,A_1,\dots ,A_n$ be $n+1$ points in Template:Tmath-dimensional Euclidean space. Starting with the volume formula in terms of an $(n+1)\times (n+1)$ matrix,

$$v_n=\frac{1}{n!}|det\left(\begin{array}{cccc}{A}_0& A_1& \cdots & A_n\\ 1& 1& \cdots & 1\end{array}\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=\left(\begin{array}{ccccc}{A}_0& A_1& \cdots & A_n& 0\\ 1& 1& \cdots & 1& 0\\ \Vert A_0{\Vert }^2& \Vert A_1{\Vert }^2& \cdots & \Vert A_n{\Vert }^2& 1\end{array}\right),$$

where $\Vert A_j{\Vert }^2$ is the square of the length of the vector Template:Tmath. Additionally, we note that the $(n+2)\times (n+2)$ matrix

$$Q=\left(\begin{array}{cccccc}-2& 0& \cdots & 0& 0& 0\\ 0& -2& \cdots & 0& 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 0& 0& \cdots & -2& 0& 0\\ 0& 0& \cdots & 0& 0& 1\\ 0& 0& \cdots & 0& 1& 0\end{array}\right)$$

has a determinant of Template:Tmath. Thus,

$$det\left(\begin{array}{cccccc}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\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ d_{0n}^2& d_{1n}^2& d_{2n}^2& \cdots & 0& 1\\ 1& 1& 1& \cdots & 1& 0\end{array}\right)=det(P^{T}QP)=det(Q)det(P{)}^2=(-1{)}^{n+1}{2}^n(n!{)}^2{v}_n^2.$$

Examples

In the case Template:Tmath, $v_2$ is the area of a triangle and thus we will denote this by Template:Tmath. By the Cayley–Menger determinant, where the triangle has side lengths Template:Tmath, Template:Tmath, and Template:Tmath,

$$\begin{array}{cc}16A^2& =\left|\begin{array}{cc}2a^2& a^2+b^2-c^2\\ a^2+b^2-c^2& 2b^2\end{array}\right|\\ & =4a^2{b}^2-(a^2+b^2-c^2{)}^2\\ & =(a^2+b^2+c^2{)}^2-2(a^4+b^4+c^4)\\ & =(a+b+c)(a+b-c)(a-b+c)(-a+b+c).\end{array}$$

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 its three sides, which was known to Archimedes prior.

In the case Template:Tmath, the quantity $v_3$ gives the volume of a tetrahedron, which we will denote by Template:Tmath. For distances between $A_i$ and $A_j$ denoted by Template:Tmath, the Cayley–Menger determinant gives

$$\begin{array}{cc}144V^2=& \frac{1}{2}\left|\begin{array}{ccc}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{array}\right|\\ =& 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)\\ & -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{array}$$

Finding the circumradius of a simplex

Given a nondegenerate $n$-simplex, it has a circumscribed $n$-sphere, with radius Template:Tmath. Then the Template:Tmath-simplex made of the vertices of the Template:Tmath-simplex and the center of the Template:Tmath-sphere is degenerate. Thus, we have

$$\left|\begin{array}{ccccccc}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\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ r^2& d_{0n}^2& d_{1n}^2& d_{2n}^2& \cdots & 0& 1\\ 1& 1& 1& 1& \cdots & 1& 0\end{array}\right|=0.$$

Using $\left|\begin{array}{cc}A& B\\ C& D\end{array}\right|=\left|\begin{array}{c}D\end{array}\right|\left|\begin{array}{c}A-B{D}^{-1}C\end{array}\right|$,$\left|\begin{array}{c}D\end{array}\right|\ne 0$, and $A=\left(\begin{array}{c}0\end{array}\right)$, this is equivalent to

$$\left(\begin{array}{cccccc}{r}^2& r^2& r^2& \cdots & r^2& 1\end{array}\right){\left(\begin{array}{cccccc}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\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ d_{0n}^2& d_{1n}^2& d_{2n}^2& \cdots & 0& 1\\ 1& 1& 1& \cdots & 1& 0\end{array}\right)}^{-1}\left(\begin{array}{c}{r}^2\\ r^2\\ r^2\\ ⋮\\ r^2\\ 1\end{array}\right)=0,$$ which is a quadratic equation for Template:Tmath. Solving for Template:Tmath, we get

$$r={\left(2\left(\begin{array}{ccccc}1& 1& 1& \cdots & 1\end{array}\right){\left(\begin{array}{ccccc}0& d_{01}^2& d_{02}^2& \cdots & d_{0n}^2\\ d_{01}^2& 0& d_{12}^2& \cdots & d_{1n}^2\\ d_{02}^2& d_{12}^2& 0& \cdots & d_{2n}^2\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ d_{0n}^2& d_{1n}^2& d_{2n}^2& \cdots & 0\end{array}\right)}^{-1}\left(\begin{array}{c}1\\ 1\\ 1\\ ⋮\\ 1\end{array}\right)\right)}^{-1/2}.$$

For example, when Template:Tmath, 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 Template:Math (with at least three distinct elements) is called straight if and only if, for any three elements Template:Mvar, Template:Mvar, and Template:Mvar of Template:Math,

$det\left[\begin{array}{cccc}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{array}\right]=0$

Plane

A set Template:Math (with at least four distinct elements) is called plane if and only if, for any four elements Template:Mvar, Template:Mvar, Template:Mvar and Template:Mvar of Template:Math,

$det\left[\begin{array}{ccccc}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{array}\right]=0$

but not all triples of elements of Template:Math are straight to each other;

Flat

A set Template:Mvar (with at least five distinct elements) is called flat if and only if, for any five elements Template:Mvar, Template:Mvar, Template:Mvar, Template:Mvar and Template:Mvar of Template:Mvar,

$det\left[\begin{array}{cccccc}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{array}\right]=0$

but not all quadruples of elements of Template:Mvar 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 (unrelated to the theorem of that name in graph theory). The theorem states:

For a finite set of points Template:Tmath, a semi-metric $\rho :A\times A\to {ℝ}_{\ge 0}$ 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 Template:Tmath-dimensional, but not generally Template:Tmath-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, Template:Tmath, via a geometric constraint solving algorithm. The second algorithm does so when the dimension, Template:Tmath, 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 $\mathrm{\Delta }$ is a Euclidean Distance Matrix if and only if for all $k\times k$ submatrices $S$ of Template:Tmath, where Template:Tmath, Template:Tmath. For $\mathrm{\Delta }$ to have a realization in dimension Template:Tmath, if Template:Tmath, then Template:Tmath.

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 $\mathrm{\Delta }$ or Gramian Matrix Template:Tmath.

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 Template:Tmath, where the variables are the coordinates of each point $p_1,\dots ,p_n$ in the desired dimension Template:Tmath.
• 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 Template:Tmath. 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 Template:Tmath. To place the first three points:

1. Put $p_1$ at the origin, so Template:Tmath.
2. Put $p_2$ on the first axis, so Template:Tmath.
3. To place $p_3$:

$$\{\begin{array}{c}(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{array}$$ $$\to \{\begin{array}{c}{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{array}$$

In order to find a realization using the above algorithm, the discriminant of the distance quadratic system must be positive, which is equivalent to $\mathrm{\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

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

In this formula above, $det(\hat{\mathrm{\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 Template:Mvar be a positive integer and Template:Mvar be a Template:Math symmetric hollow matrix with nonnegative elements, with Template:Math. Template:Mvar is a Euclidean distance matrix with Template:Math if and only if there exist $\{x_i{\}}_{i=1}^n\subseteq {ℝ}^K$ and an index set Template:Math$\{i_1,\dots ,i_{K+1}\}\subseteq I_n$ such that

$$\{\begin{array}{c}{x}_i=0\\ x_{i_j}(j-1)\ne 0,& j\in I_{2,K+1}\\ x_{i_j}(i)=0,& j\in I_{2,K},i\in I_{j,K},\end{array}$$

where $\{x_i{\}}_{i=1}^n$ realizes Template:Mvar, 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.

Algorithm - K = edmsph(D, x)

Source:

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

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

if Γ $=$ ∅; then

return ∞

else if Γ $=\{p_i\}then$

$x_i=p_i$

else if Γ$=\{p_i^{+},p_i^{-}\}then$

$x_i=p_i^{+}$

$x$ ← expand($x$)

Template:Math

Template:Math

else

error: Template:Math

end if

end for return K

See also

• Distance geometry
  
• Euclidean space
  
• Euclidean distance matrix
  
• Simplex
  
• Heron's formula