TOPICS
Search

Cayley-Menger Determinant


The Cayley-Menger determinant is a determinant that gives the volume of a simplex in j dimensions. If j and n are integers with 0<=j<=n, S is a j-simplex in R^n with vertices v_1,...,v_(j+1) and B=(beta_(ik)) denotes the (j+1)×(j+1) matrix given by

 beta_(ik)=||v_i-v_k||_2^2,
(1)

then the content V_j is given by

 V_j^2(S)=((-1)^(j+1))/(2^j(j!)^2)det(B^^),
(2)

where B^^ is the (j+2)×(j+2) matrix obtained from B by bordering B with a top row (0,1,...,1) and a left column (0,1,...,1)^T. Here, the vector l2-norms ||v_i-v_k||_2 for i!=k are the edge lengths and the determinant in (2) is the Cayley-Menger determinant (Sommerville 1958; Gritzmann and Klee 1994, p. 403).

The multiplicative inverses of the prefactors for j=0, 1, 2, ... are -1, 2, -16, 288, -9216, 460800, ... (OEIS A055546), with the content of a 0-simplex taken to be 1.

For j=2, (2) becomes

 -16Delta^2=|0 1 1 1; 1 0 c^2 b^2; 1 c^2 0 a^2; 1 b^2 a^2 0|,
(3)

which gives the area for a plane triangle with side lengths a, b, and c, and is a form of Heron's formula.

For j=3, the content of the 3-simplex (i.e., volume of the general tetrahedron) is given by the determinant

 288V^2=|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|,
(4)

where the edge between vertices i and j has length d_(ij). Setting the left side equal to 0 (corresponding to a tetrahedron of volume 0) gives a relationship between the distances between vertices of a planar quadrilateral (Uspensky 1948, p. 256).

Buchholz (1992, pp. 354-355) gives a slightly different (and slightly less symmetrical) form of this equation.

The determinant formula is exact, but its evaluation in floating-point arithmetic can lose accuracy through cancellation. For tetrahedra, Kahan (2012, pp. 11-13) discusses this issue and the distinction between roundoff in computing the volume and sensitivity to errors in the edge lengths themselves.

For j>=1, the inverse of the bordered matrix also determines the centers and radii of the circumscribed and inscribed hyperspheres of a nondegenerate simplex in its affine hull. Index the bordering row and column by 0 and define

 Q=(q_(ik))=-2B^^^(-1).
(5)

The circumcenter O and circumradius R are then

O=-1/2sum_(i=1)^(j+1)q_(0i)v_i
(6)
R=(sqrt(q_(00)))/2.
(7)

Here sum_(i=1)^(j+1)q_(0i)=-2, so the coefficients in the expression for O are normalized barycentric coordinates. Equivalently,

 R^2=-(det(B))/(2det(B^^))
(8)

(Fiedler 2011, pp. 24-26).

For i>=1, q_(ii) is the reciprocal of the square of the perpendicular distance from v_i to the affine hull of its opposite facet. In particular, q_(ii)>0. The incenter I and inradius r are

I=(sum_(i=1)^(j+1)sqrt(q_(ii))v_i)/(sum_(i=1)^(j+1)sqrt(q_(ii)))
(9)
r=1/(sum_(i=1)^(j+1)sqrt(q_(ii))).
(10)

For j=2 these formulas give the centers and radii of the circumcircle and incircle, and for j=3 they give those of the circumsphere and insphere (Fiedler 2011, p. 32).


See also

Heron's Formula, Quadrilateral, Tetrahedron

Portions of this entry contributed by Karen D. Colins

Explore with Wolfram|Alpha

References

Buchholz, R. H. "Perfect Pyramids." Bull. Austral. Math. Soc. 45, 353-368, 1992. https://doi.org/10.1017/S0004972700030252.Fiedler, M. Matrices and Graphs in Geometry. Cambridge, England: Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511973611.003.Gritzmann, P. and Klee, V. "On the Complexity of Some Basic Problems in Computational Convexity: II. Volume and Mixed Volumes." In Polytopes: Abstract, Convex and Computational (Ed. T. Bisztriczky, P. McMullen, R. Schneider, and A. Ivić Weiss). Dordrecht, Netherlands: Kluwer, pp. 373-466, 1994. https://doi.org/10.1007/978-94-011-0924-6_17.Sloane, N. J. A. Sequence A055546 in "The On-Line Encyclopedia of Integer Sequences."Sommerville, D. M. Y. An Introduction to the Geometry of n Dimensions. New York: Dover, p. 124, 1958.Uspensky, J. V. Theory of Equations. New York: McGraw-Hill, p. 256, 1948.Kahan, W. "What Has the Volume of a Tetrahedron to Do with Computer Programming Languages?" Apr. 3, 2012, pp. 11-13. https://people.eecs.berkeley.edu/~wkahan/VtetLang.pdf.

Referenced on Wolfram|Alpha

Cayley-Menger Determinant

Cite this as:

Weisstein, Eric W., with contributions by Karen D. Colins. "Cayley-Menger Determinant." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Cayley-MengerDeterminant.html

Subject classifications