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 $n+1$ points in $k$-dimensional Euclidean space, with $k\geq n$. 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 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:

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

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,

$\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. A proof can be found here.

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.

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

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

See also

• Distance geometry