Cayley–Menger determinant

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

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

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

• Distance geometry