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.

Definition[]

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

$${\displaystyle {\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 ${\displaystyle n=2}$ it is a symmetric polynomial in the ${\displaystyle d_{ij}}$'s and is thus invariant under permutation of these quantities. This fails for ${\displaystyle n>2,}$ but it is always invariant under permutation of the vertices^[b].

Proof[]

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

${\displaystyle 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 ${\displaystyle (n+2)\times (n+2)}$ matrix,

${\displaystyle 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 ${\displaystyle \|A_{j}\|^{2}}$ is the square of the length of the vector ${\displaystyle A_{j}}$. Additionally, we note that the ${\displaystyle (n+2)\times (n+2)}$ matrix

${\displaystyle 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 ${\displaystyle (-2)^{n}(-1)=(-1)^{n+1}2^{n}}$. Thus,

${\displaystyle \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}\,.}$^[2]

Generalization to hyperbolic and spherical geometry[]

There are spherical and hyperbolic generalizations.^[3] A proof can be found here.^[4]

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

${\displaystyle {\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 ${\displaystyle f(d)=2R^{2}\left(1-\cos {\frac {d}{R}}\right)}$, and ${\displaystyle d_{ij}}$ is the spherical distance between points ${\displaystyle i,j}$.

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

${\displaystyle {\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 ${\displaystyle f(d)=2R^{2}\left(\cosh {\frac {d}{R}}-1\right)}$, and ${\displaystyle d_{ij}}$ is the hyperbolic distance between points ${\displaystyle i,j}$.

Example[]

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

${\displaystyle {\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.^[5]

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

${\displaystyle {\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 ${\displaystyle 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

${\displaystyle {\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 ${\displaystyle n=2}$, this gives the circumradius of a triangle in terms of its edge lengths.

See also[]

• Distance geometry

Notes[]

References[]