Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I wonder how a matrix with positive entries can have trace 0? –  Günter Rote Apr 26 '13 at 21:40
    
@Gunter, I wondered the same. They must mean non-negative. I'll point this out to NJA Sloane. –  Victor Miller Apr 26 '13 at 21:53

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
    
@Gunter: thank you for a clear a lucid explanation. –  Victor Miller Apr 26 '13 at 22:23
    
@Gunter: not all the coefficients are positive, so that we need to add a sign to $2^k$ -- is it the sign of the permutation? –  Victor Miller Apr 26 '13 at 22:25
    
Yes, it is. I have updated my answer. –  Günter Rote Apr 28 '13 at 22:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.