Teorema de Cayley Menger y matrices enteras con suma de filas 2

Question

Acabo de llenar un vacío en mi educación aprendiendo sobre el teorema de Cayley-Menger y el determinante de Cayley-Menger:

Si $P_0, \dots, P_n$ son $n+1$ punto en $\mathbb{R}^n$ y $d_{i,j} = |P_i - P_j|$ es la distancia euclidiana desde $P_i$ a $P_j$ formamos primero el $n+1 \times n+1$ matriz de cuadrados de las distancias (digamos $B$ ) y, a continuación, formar un $n+2 \times n+2$ matriz $A$ que tiene $B$ en la esquina inferior derecha, y tiene todos los elementos de la primera fila y columna $=1$ excepto el de la esquina superior izquierda, que es 0.

El teorema de Cayley-Menger (que es un $n$ generalización dimensional de la fórmula de Heron para el área de un triángulo) dice que si $V$ es el volumen del simplex cuyos vértices son los $P_i$ entonces

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

Me interesaba la estructura de $\det(A)$ como un polinomio. Hay un buen artículo "The Cayley-Menger Determinant is Irreducible for $n \ge 3$ "de Carlos d'Andrea y Martín Sombra (arXiV:math/0406359). Cuando calculé el número de monomios en cada uno de los polinomios obtenidos evaluando $\det(A)$ Obtuve la secuencia (empezando por $n=1$ ):

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

que es la secuencia A002137 en la OEIS: Número de matrices simétricas n X n con entradas positivas, traza 0 y todas las sumas de fila 2. Allí no se menciona el determinante de Cayley-Menger.

Así que la pregunta que tengo, ¿hay una correspondencia uno-a-uno que uno puede encontrar entre las matrices y monomios en $\det(A)$ ? Aún mejor sería encontrar el valor del coeficiente del monomio a partir de la matriz.

Añadido más tarde: Debería haber mirado la referencia en la 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.

En él da una recurrencia para los términos numéricos de una matriz simétrica con 0 en la diagonal, y produce la misma secuencia. Sin embargo, todavía no puedo encontrar una conexión con los coeficientes.

Answer 1

Consideremos en primer lugar un $n\times n$ matriz con diagonal cero y $n(n-1)$ indeterminados. Cada término (monomio) del determinante corresponde a una matriz de permutación $P$ con diagonal cero (es decir, una matriz entera no negativa con traza 0 y sumas de filas y columnas 1).

Consideremos ahora un simétrico $n\times n$ matriz con diagonal cero y $n(n-1)/2$ indetermina $a_{ij}=a_{ji}$ . Entonces cada término corresponde a una matriz de permutación $P$ como antes, pero la correspondencia no es uno a uno, ya que los elementos simétricos son iguales. Podemos obtener una correspondencia uno a uno asociando el término a $P+P^T$ (la "versión simetrizada" de $P$ ): matriz simétrica entera no negativa con traza 0 y suma de filas 2. El coeficiente del término es $\det(P+P^T)$ .

Ahora, en el determinante de Cayley-Menger, las entradas de la primera fila y columna no son indeterminadas sino unos. Debemos argumentar que esto no provoca una "pérdida de información". De hecho, la matriz $P+P^T$ es la matriz de adyacencia de un grafo 2-regular no dirigido $G$ en $n$ vértices, sin bucles pero potencialmente con múltiples aristas. Este grafo es una representación directa de cada monomio en el determinante. Fijando todas las variables $a_{12},a_{13},\ldots,a_{1n}$ a $1$ corresponde a la eliminación de las aristas incidentes en el vértice 1, lo que da como resultado un grafo $G'$ en $n-1$ vértices. Sin embargo, dado que $G$ era 2-regular sin bucles, podemos identificar unívocamente las aristas que faltan: son incidentes en los vértices de grado inferior a 2 en $G'$ .

El coeficiente del monomio sigue siendo el determinante de $P+P^T$ que es igual a $\pm2^k$ donde $k$ es el número de ciclos de longitud igual o superior a 3 en el gráfico $G$ . El signo es el signo de la (más precisamente, de cualquier) permutación $P$ .