The Cayley Menger Theorem and integer matrices with row sum 2

Question

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.

Answer 1

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