¿Cuál es el número de $n \times n$ matrices binarias $A$ tal que $\det(A) = \text{perm}(A)$ ?

Question

Recordemos que el permanente es el "análogo positivo" del determinante por el que los signos en el proceso de expansión del cofactor se toman como positivos. Es decir, el permanente es el inmanente correspondiente al carácter trivial .

Muchos problemas enumerativos que involucran permutaciones y muchos problemas enumerativos que involucran la teoría de grafos pueden ser reformulados usando la permanentes de las matrices binarias .

Anteriormente he considerado el problema combinatorio natural de determinar el número A192892 $(n)$ de $n \times n$ matrices binarias $A$ tal que $\det\left(A\right) = \text{perm}\left(A\right)$ . Observe que A192892 $(n)$ también es igual al número de matrices binarias $\left( a_{i, j} \right)_{n \times n}$ tal que el producto $$a_{1, \sigma(1)}a_{2, \sigma(2)}\cdot \cdots \cdot a_{n, \sigma(n)}$$ desaparece para todas las permutaciones de impar $\sigma \in S_{n}$ .

He calculado A192892 $(n)$ para $n \leq 4$ . Obviamente, los algoritmos de fuerza bruta para este problema enumerativo son muy ineficientes. Así que es natural preguntarse:

(1) ¿Existe una fórmula combinatoria sencilla para A192892 $(n)$ ?

(2) ¿Existe un algoritmo de tiempo polinómico para calcular A192892 $(n)$ ?

Answer 1

Para abordar las preguntas (1) y (2), empecemos por el comentario de hardmath. El conjunto de matrices con permanente cero es un subconjunto del conjunto que queremos contar, y es más fácil de describir. No obstante, el número de tales matrices se registra en https://oeis.org/A088672 sólo hasta $6\times6$ La Comisión Europea ha creado una nueva página web, en la que se combinan los esfuerzos de tres contribuyentes. En la literatura, encontramos este artículo:

• C. J. Everett y P. R. Stein, El número asintótico de matrices (0,1) con cero permanente , Disco. Matemáticas. 6 (1973), 29-34.

Los autores aplican técnicas estándar como la de Inclusión-Exclusión, pero sólo pueden obtener límites asintóticos. Todo esto me sugiere que no hay una fórmula o algoritmo obvio y sencillo. Tal vez exista una fórmula sencilla, pero para encontrarla habrá que tener una visión novedosa de estos problemas.

Ahora pasemos a la fuerza bruta. Si iteramos ingenuamente a través de todos los $2^{n^2}$ matrices y comprobar cada una de ellas con todas $n!/2$ impar permutaciones, entonces podemos calcular sólo algunos términos de la secuencia. Incluso si realizamos 20.000 millones de comprobaciones por segundo, el cálculo de $a(7)$ tardaría dos años, y $a(8)$ tardaría 600.000 años.

Ahora, es difícil borrar eso $2^{n^2}$ plazo. Sin embargo, hay varias mejoras de velocidad clave, cada una de las cuales hace que sea factible aproximadamente otro término. Pueden aplicarse en este orden:

1. En lugar de iterar sobre los posibles valores de la última fila, calcula cuántos espacios de la última fila están "libres", lo que significa que poner un $1$ no se completaría una permutación impar con los valores dados en la anterior $n-1$ filas. Si $k$ es el número de espacios libres, entonces $2^k$ es el número de valores de la última fila que evitan todas las permutaciones de impar, por lo que podemos añadir inmediatamente ese número a nuestro total en funcionamiento. Esto aumenta nuestra eficiencia en un factor de $2^n/n$ .
2. Programación dinámica. A medida que iteramos por las filas de la matriz, rellenando valores, reducimos el conjunto de permutaciones Impares a comprobar agrupándolas según sus valores en las filas restantes. Cuando enumeramos la penúltima fila, sólo tenemos $n^2$ permutaciones para comprobar. Esto aumenta nuestra eficiencia en un factor de $n!/n^2$ .
3. Intercambio de columnas. Modulando el signo de las permutaciones, realmente sólo tenemos que inspeccionar las matrices representativas de las órbitas bajo la acción del grupo de simetría $(S_n\times S_n)\rtimes\mathbb Z/2$ que actúa permutando las filas y columnas y transponiendo la matriz. En otras palabras, sólo tenemos que comprobar los grafos bipartitos hasta el isomorfismo del grafo. Ahora bien, es un poco incómodo resolver el problema del isomorfismo del grafo en el bucle interno del algoritmo. Una táctica mejor es dividir las órbitas en trozos más predecibles. En primer lugar, no queremos renunciar al gran aumento de velocidad que obtuvimos al proyectar la última fila, así que el grupo de simetría se reduce a $S_{n-1}\times S_n$ . Aprovechemos la mayor $S_n$ que intercambia las columnas. Lo hacemos enumerando sólo las columnas en orden creciente, donde el orden se define tomando el valor de una columna como una expansión binaria, donde la fila superior es el bit más significativo. Esto puede calcularse fila por fila, y reduce drásticamente el número de matrices consideradas, en casi $n!$ . Digo "casi" por dos razones. Una, algunas matrices tendrán grandes estabilizadores bajo esta acción, equivalentes a órbitas pequeñas. En segundo lugar, ahora tenemos que hacer un seguimiento de las matrices de permutación pares, así como de las matrices de permutación impar, ya que algunas órbitas tendrán que incluir permutaciones impar de las columnas. Y se necesita un poco de esfuerzo para hacer cumplir el ordenamiento y calcular los estabilizadores. Pero dejando de lado estos problemas, esto aumenta nuestra eficiencia en $n!$ .
4. Intercambio de filas. No podemos conseguir un $(n-1)!$ aceleración al hacer que se mantenga el mismo orden entre las filas, ya que las permutaciones de columnas anteriores no preservan el valor binario de una fila. Sin embargo, podemos acercarnos ordenando las filas según su peso Hamming, que es conservado por las permutaciones de columnas. Sólo hay $n+1$ pesos posibles, por lo que este esquema da lugar a estabilizadores desgraciadamente grandes, y por tanto a órbitas desgraciadamente pequeñas. Pero incluso si el orden típico de los estabilizadores es $2^{n-1}$ , eso sigue siendo un aumento de la velocidad de $(n-1)!/2^{n-1}$ que vale totalmente la pena.
5. Optimización del código. Un subconjunto del conjunto de $2\times n$ Las matrices de permutaciones parciales pueden representarse como un $n^2$ campo de bits. Si $n\leq8$ , esto encaja es un solo $64$ -registro de la máquina de bits, y utilizando $256$ -instrucciones SIMD de bits, podemos procesar $4$ de ellos por ciclo. Utilice un lenguaje de bajo nivel con soporte para la programación genérica, como C++, para eliminar la asignación dinámica, minimizar el espacio de las matrices y optimizar cada fila individualmente. Además, el problema es vergonzosamente fácil de paralelizar a múltiples núcleos de CPU, o incluso a múltiples máquinas.

Las mejoras 1-4 se aplican en https://github.com/Culter/PermDet . Dan como resultado los siguientes valores:

$a(0)=1$
$a(1)=2$
$a(2)=12$
$a(3)=343$
$a(4)=34997$
$a(5)=12515441$
$a(6)=15749457081$
$a(7)=72424550598849$
$a(8)=1282759836215548737$

De hecho, $a(9)$ está al alcance de la mano con este algoritmo, pero se necesitaría un $64$ -aritmética de bits para implementar, lo cual no he hecho.