Número de determinantes únicos de una matriz NxN (0,1)

Question

Estoy interesado en los límites para el número de determinantes únicos de NxN (0,1)-matrices. Obviamente algunas de estas matrices serán singulares y por lo tanto trivialmente tendrán determinante cero. Aunque también podría ser interesante preguntar qué número de NxN (0,1)-matrices son singulares o no singulares, me gustaría ignorar las matrices singulares por completo en esta pregunta.

Para comprender mejor el problema, he escrito un programa informático que busca los valores dados como entrada N. A continuación se muestra el resultado:
1x1: 2 posibles determinantes
2x2: 3 ...
3x3: 5 ...
4x4: 9 ...
5x5: 19 ...

Dado que el programa está diseñado simplemente para realizar una fuerza bruta sobre todas las matrices posibles, el tiempo de cálculo crece con respecto a $O(2^{N^2})$ . Computar 6x6 parece que me va a llevar cerca de un mes y 7x7 está más allá de toda esperanza sin acceso a un cluster. No creo que esta cantidad limitada de resultados sea suficiente para hacer una conjetura sólida.

Tengo en mente una aplicación práctica, pero también me gustaría conseguir los límites para saciar mi curiosidad.

Answer 1

He dado algunos detalles en un comentario a otra respuesta. Tengo una prueba de que el número de determinantes es mayor que 4 veces el n-ésimo número de Fibonacci para (n+1)x(n+1) (0,1) matrices, y conjeturo que para grandes n el número de determinantes distintos se aproxima a una constante veces n^(n/2). Math Overflow tiene algunas pistas de la prueba en las respuestas que hice en otras preguntas.

Me interesa su idea para una aplicación, y estoy dispuesto a compartir más información sobre este tema.

Gerhard "Ask Me About System Design" Paseman, 2010.03.19

Answer 2

A partir del límite de Hadamard, el mayor determinante posible de un $n\times n$ (0,1) es $h_n=2^{-n}(n+1)^{(n+1)/2}$ . Los datos en http://www.indiana.edu/~maxdet/espectro.html sugieren varias conjeturas:

1. El espectro es "denso" hasta cierto punto, a partir del cual se vuelve "disperso". Un número entero en la parte "densa" es casi seguro que sea el determinante de algún $n\times n$ (0,1); y entero en la parte "dispersa" es casi seguro que no lo sea. El punto en el que el espectro se vuelve disperso es asintóticamente una constante de tiempo $h_n$ . Los datos sugieren que la constante se aproxima a 0,5. Creo que esta es básicamente la conjetura que hace Gerhard Paseman en su respuesta.
2. Una afirmación más contundente es la siguiente: sea $g_n$ sea la posición del primer "hueco", es decir, el primer entero positivo que no sea el determinante de algún $n\times n$ (0,1) matriz. Entonces, asintóticamente $g_n$ es una constante multiplicada por $h_n$ y de nuevo la constante parece ser cercana a 0,5. Si $D_n$ denota el conjunto de $n\times n$ determinantes, y si las ideas anteriores van por buen camino, entonces parece probable que asintóticamente $g_n/|D_n|$ es 1.

No tengo ni siquiera una explicación heurística de por qué tales conjeturas deberían ser ciertas, y uno siempre puede preocuparse de hasta qué punto uno debería intentar concluir a partir de datos que, de hecho, sólo llegan tan alto como $n=21$ . Como se menciona en algunos de los comentarios a otras respuestas, $D_n$ sólo es conocido por $n\le 10$ y $n=12$ . Los conjuntos $D_n$ para estos $n$ en el enlace anterior, así como las conjeturas para todos los $n$ hasta 16. Datos para $17\le n\le21$ aún no se han añadido al sitio. (Tenga en cuenta que el $n$ en el sitio web se refiere a $(-1,1)$ matrices, por lo que habría que restarle 1 si se trata de $(0,1)$ matrices). Confío plenamente en que los conjuntos enumerados $D_n$ hasta $n=16$ no les falta ningún valor, ni siquiera los que no se han demostrado completos.

Answer 3

Hay algunas respuestas en W P Orrick, The maximal {-1,1}-determinant of order 15, http://arXiv.org/pdf/math/0401179v1 . A pesar del título, hacia el final del artículo el autor se fija en las matrices {0,1}, y en todo el rango, no sólo en el máximo. El autor también hace referencia a un artículo más antiguo sobre el tema, R Craigen, The range of the determinant function on the set of $n\times n$ (0,1), J Combin Math Combin Comput 8 (1990) 161-171.