I just filled a gap in my education by learning about the Cayley-Menger theorem, and the Cayley-Menger determinant:


If $P\_0, \dots, P\_n$ are $n+1$ point in $\mathbb{R}^n$, and $d\_{i,j} = |P\_i - P\_j|$ is the Euclidean distance from $P\_i$ to $P\_j$, we first form the $n+1 \times n+1$ matrix of squares of the distances (say $B$) and then form an $n+2 \times n+2$ matrix $A$ which has $B$ in the lower right hand corner, and has all the elements in the first row and column $=1$ except for the one in the upper left hand corner, which is 0.


The Cayley-Menger theorem (which is an $n$ dimensional generalization of Heron's formula for the area of a triangle) says that if $V$ is the volume of simplex whose vertices are the $P\_i$, then


$(-1)^{n-1} 2^n (n!)^2 V^2 = \det(A)$.


I was interested in the structure of $\det(A)$ as a polynomial. There is a nice paper "The Cayley-Menger Determinant is Irreducible for $n \ge 3$" by Carlos d'Andrea and Martin Sombra (arXiV:math/0406359). When I calculated the number of monomials in each of the polynomials obtained by evaluating $\det(A)$, I got the sequence (starting with $n=1$):


1,1,6,22,130,822, 6202, 52552


which is sequence A002137 in the OEIS: Number of n X n symmetric matrices with positive entries, trace 0 and all row sums 2. There's no mention there of the Cayley-Menger determinant.


So the question I have, is there a one-to-one correspondence that one can find between the matrices and monomials in $\det(A)$? Even nicer, would be to find the value for the coefficient of the monomial from the matrix.


Added Later: I should have looked at the reference in the OEIS: A. C. Aitken, On the number of distinct terms in the expansion of symmetric and skew determinants, Edinburgh Math. Notes, No. 34 (1944), 1-5.


In it he gives a recurrence for the number terms in a symmetric matrix with 0's on the diagonal, and produces the same sequence. However, I still can't find a connection with the coefficients.



The Cayley Menger Theorem and integer matrices with row sum 2
Let us first consider an $n\times n$ matrix with zero diagonal and $n(n-1)$ indeterminates.
Every term (monomial) of the determinant corresponds to a permutation matrix $P$ with zero diagonal (i.e., an integer nonnegative matrix with trace 0 and row and column sums 1).


Let us now consider a *symmetric* $n\times n$ matrix with zero diagonal and $n(n-1)/2$ indeterminates $a\_{ij}=a\_{ji}$. Then every term corresponds to a permutation matrix $P$ as before, but the correspondence is not one-to-one, since symmetric elements are equal. We can get a one-to-one correspondence by associating the term to $P+P^T$ (the "symmetrized version" of $P$): an integer nonnegative symmetric matrix with trace 0 and row sums 2. The coefficient of the term is $\det(P+P^T)$.


Now, in the Cayley-Menger determinant, the entries of the first row and column are not indeterminates but ones. We have to argue that this does not cause a "loss of information". In fact, the matrix $P+P^T$ is the adjacency matrix of a 2-regular undirected graph $G$ on $n$ vertices, without loops but potentially with multiple edges. This graph is a straightforward representation of every monomial in the determinant. Setting all variables $a\_{12},a\_{13},\ldots,a\_{1n}$ to $1$ corresponds to eliminating the edges incident to vertex 1, resulting in a graph $G'$ on $n-1$ vertices. However, since $G$ was 2-regular without loops, we can uniquely identify the missing edges: they are incident to the vertices of degree less than 2 in $G'$.


The coefficient of the monomial is still the determinant of $P+P^T$, which equals $\pm2^k$, where $k$ is the number of cycles of length at least 3 in the graph $G$. The sign is the sign of the (more precisely, of any) permutation $P$.


