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}$[lower-alpha 1]. 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[lower-alpha 2].

A proof of the second equation can be found.[2] From the second equation, the first can be derived by elementary row and column operations:

${\displaystyle {\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}}={\begin{vmatrix}0&0&0&\cdots &0&1\\0&-2d_{01}^{2}&d_{12}^{2}-d_{02}^{2}-d_{01}^{2}&\cdots &d_{1n}^{2}-d_{0n}^{2}-d_{01}^{2}&0\\0&d_{12}^{2}-d_{01}^{2}-d_{02}^{2}&-2d_{02}^{2}&\cdots &d_{2n}^{2}-d_{0n}^{2}-d_{02}^{2}&0\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\0&d_{1n}^{2}-d_{01}^{2}-d_{0n}^{2}&d_{2n}^{2}-d_{02}^{2}-d_{0n}^{2}&\cdots &-2d_{0n}^{2}&0\\1&0&0&\cdots &0&0\end{vmatrix}}}$then exchange the first and last column, gaining a ${\displaystyle -1}$, and multiply each of its ${\displaystyle n}$ inner rows by ${\displaystyle -1}$.

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}$, 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}$, 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

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

References

1. Sommerville, D. M. Y. (1958). An Introduction to the Geometry of n Dimensions. New York: Dover Publications.
2. "Simplex Volumes and the Cayley-Menger Determinant". www.mathpages.com. Archived from the original on 16 May 2019. Retrieved 2019-06-08.
3. 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.
4. Tao, Terrence (2019-05-25). "The spherical Cayley-Menger determinant and the radius of the Earth". What's new. Retrieved 2019-06-10.
5. Heath, Thomas L. (1921). A History of Greek Mathematics (Vol II). Oxford University Press. pp. 321–323.
6. Audet, Daniel. "Déterminants sphérique et hyperbolique de Cayley–Menger" (PDF). Bulletin AMQ. LI: 45–52.
7. Dörrie, Heinrich (1965). 100 Great Problems of Elementary Mathematics. New York: Dover Publications. pp. 285–9.