Probabilidad de cero en una matriz aleatoria

Question

Deje $M(n,k)$ el conjunto de $n\times n$ matrices de números enteros no negativos tales que cada fila y cada columna de sumas de dinero a $k$. Deje $P(n,k)$ ser la fracción de tales matrices que no tienen cero entradas, equivalente a la probabilidad de que una matriz aleatoria de una distribución uniforme en $M(n,k)$ no tiene ningún cero entradas.

Una cosa a tener en cuenta es que el $$P(n,k)=\frac{|M(n,k-n)|}{|M(n,k)|}$$ (piensa en restando 1 de cada entrada). También tenga en cuenta que $P(n,k)$ es la fracción de un número entero de puntos en la $k$-dilatación de Birkhoff polytope que se encuentran en el interior.

Parece "obvio" que $P(n,k)$ no es una función decreciente de $k$. Por lo suficientemente grande como $k$ es estrictamente creciente por Ehrhart teoría, pero me gustaría ver una prueba para todos los $k$. Así que el problema es:

Demostrar que $P(n,k)$ no es una función decreciente de $k$ fijos $n$.

COMENTARIO: Por el resultado de Stanley (véase David Speyer respuesta para refs) existen enteros no negativos $\{h_i\}$ tal que $$|M(n,k)| = \sum_{i=0}^d h_i \binom{k+i}{d}$$ donde $d=(n-1)^2$. Me pregunto si esto es suficiente. Cada polinomio de que forma tienen las propiedades deseadas? [Gjergji mostró no.]

COMMENT2: El teorema de reciprocidad de Ehrhart serie proporciona una fórmula para el número de puntos en el interior, en términos de número en el conjunto (cerrado) polytope. Haciendo uso de los de arriba, nos encontramos con que si el $H_n(k)$ es el polinomio igual a $|M(n,k)|$ para enteros positivos $k$, entonces el número de puntos del interior (ya identificados como $H_n(k-n)$) es igual a $(-1)^{n+1}H_n(-k)$. Así que lo que tenemos que demostrar es que $$(-1)^{n+1}\frac{H_n(-k)}{H_n(k)}$$ es no decreciente de enteros $k\ge n$. Experimentalmente, no es el aumento de real $k$ hasta $k$ es mayor.

Answer 1

Esto es frustrante porque hay un montón de estudio de esta clase de pregunta en la combinatoria, álgebra conmutativa de la literatura, y exactamente el ejemplo que discutir es un ejemplo favorito en este campo, pero no puedo encontrar una respuesta a su pregunta. Así que aquí están algunos consejos a los antecedentes pertinentes.

Fix $n$. Deje $R$ ser el semigroup anillo correspondiente a la semigroup de $n \times n$ número entero no negativo matrices cuyas fila y columna de sumas son iguales. Así Hilbert serie de $R$ es $$h(x) := \sum_k |M(n,k)| x^k$$ Por el teorema de Ehrhart, $|M(n,k)|$ es un polinomio en $k$, así que podemos escribir $$h(x) = \frac{\delta(x)}{(1-x)^{(n-1)^2+1}}$$ para algunos polinomio $\delta(x)$ grado $\leq (n-1)^2$. Richard Stanley fue pionero en el estudio de la relación entre álgebra conmutativa propiedades de $R$ y propiedades combinatorias de $\delta$. En particular, el anillo de $R$ es Gorenstein (es decir, la canónica módulo es generado por el todos los de la matriz) y esto implica que $\delta$ es capicúa con coeficientes positivos. El estándar de referencia para este material es de Stanley libro "la Combinatoria y Álgebra Conmutativa".

Valdría la pena hacer una pausa para un ejemplo: de Acuerdo a este documento, $$|M(3,k)| = 1 + \frac{9 k}{4} + \frac{15 k^2}{8} + \frac{3 k^3}{4} + \frac{k^4}{8}=\frac{(k + 1) (k + 2) (k^2 + 3 k + 4)}{8}$$ y podemos calcular $$h(x) = \frac{1+x+x^2}{(1-x)^5}.$$ El polinomio $\delta$ es $1+x+x^2$.

Ahora, tenemos las siguientes implicaciones:
(1) $\delta(x)$ tiene todas las raíces reales $\implies$
(2) la Escritura de $\delta(x) = \sum \delta_k x^k$, tenemos $\delta_k^2 \geq \delta_{k-1} \delta_{k+1}$ $\implies$
(3) Tenemos $M(n,k)^2 \geq M(n,k-1) M(n,k+1)$ $\implies$
(4) $M(n,k) M(n,k+n-1) \geq M(n,k-1) M(n,k+n)$, que es la relación que usted desea.

La implicación $(3) \implies (4)$ es elemental; los otros son discutidos en Stanley excelente encuesta "Log-cóncavo y Unimodal secuencias en Álgebra, Combinatoria y Geometría".

En esa encuesta, Stanley hizo Conjetura 4, alegando que el de la serie de Hilbert de cualquier Cohen-Macaulay dominio debe obedecer (2). $R$ es Cohen-Macualay de dominio (normal semi-anillo de grupo es, por un resultado de Hochster), pero Conjetura 4 resultó ser falsa: según el "Log-cóncavo y Unimodal secuencias en Álgebra, Combinatoria y Geometría: una actualización" por Brenti (desplácese hacia abajo, alrededor de la décima de referencia de la parte inferior de la página), un contraejemplo puede ser encontrado en Niesi y Robbiano; no he revisado esta referencia. Stanley y Brenti sugieren que la hipótesis es más plausible para Gorenstein anillos, y un rápido descremada a través de la Mathscinet documentos que citan ellos sugieren que no Gorenstein contraejemplo es conocido.

Yo fui a Dennis Pixton del artículo que ordena la Ehrhart polinomios para este problema exacto. El valor más grande que él enumera es $n=9$. Yo calcula el correspondiente $\delta$ (coeficientes disponible bajo petición) y se determinó que se violó (1), pero obedeció (2).

Específicamente, para $n=9$, el polinomio $\delta$ tiene el grado $56$. De sus raíces, $52$ son reales y claramente aislado. Los cuatro restantes raíces se $(-170629.9 \pm 70111.4 i)^{\pm 1}$. (Todo esto supone que confías en Mathematica's de algoritmos numéricos.)

Finalmente, usted probablemente sabe un par de palabras clave: La polytope de $n \times n$ matrices con no negativo de entradas y fila y columna de cantidades iguales a $1$ es la "Birkhoff polytope". El caso más general donde se acaba de arreglar $(a_1, a_2, \ldots, a_n)$ e $(b_1, b_2, \ldots, b_n)$ con $\sum a_i = \sum b_i$ y pedir sumas de fila $a_i$ y la columna sumas $b_i$ es el "transporte polytope".

Answer 2

Aquí están algunas de las otras maneras de reformular el problema. Deje $A_k$ denotar un $kn\times kn$ matriz, compuesta de $k\times k$ bloques, donde el $ij$ bloque está lleno de copias de un estándar exponencial de la variable aleatoria $\gamma_{ij}$. El $\gamma_{ij}$'s son independientes. A. Barvinok mostró que $$M(n,k)=\frac{\mathbb{E}(\operatorname{per}(A_k))}{(k!)^{2n}}$$ y la usó para demostrar que $M(n,k)$ es casi de registro-cóncava en $k$. Más específicamente, se mostró en "Brunn-Minkowski desigualdades para las tablas de contingencia y entero de los flujos", Adv. en Matemáticas., 211 (2007), 105-122, que la siguiente desigualdad se cumple $$\alpha(k)M(n,k)^2\geq M(n,k-1)M(n,k+1)$$ con $\alpha(k)=O(k^n)$. Él conjeturas de que esta desigualdad se cumple para $\alpha=1$, pero hasta donde yo sé, este permanece abierto. No estoy seguro de cuál es la mejor cota superior para $$\frac{M(n,k)M(n,n+k+1)}{M(n,k+1)M(n,k+n)}$$ que se obtiene mediante esta metodología analítica.

---

Otra forma de enunciar el problema es a través de la RSK, y convertirlo en una desigualdad en términos de números de Kostka. Si $\tau(k)$ representa la partición de $(k,k,\dots,k)$, con $k$ partes. A continuación, inicie sesión-concavidad es equivalente a $$\left(\sum_{\lambda} K_{\lambda \tau(k)}\right)^2\geq \left(\sum_{\lambda} K_{\lambda \tau(k-1)}\right)\left(\sum_{\lambda} K_{\tau(k+1)}\right)$$ y su desigualdad puede escribirse de manera similar. Uno podría esperar que existe una prueba haciendo uso de los más conocidos de las desigualdades entre Kostka números o conocido Schur la positividad de los resultados.

Otra equivalente formulación proviene de Pietro de la respuesta. Tenemos que demostrar que el coeficiente de $(x_1y_1\cdots x_ny_n)^k(z_1t_1\cdots z_nt_n)^{k+1}$ es no negativo en $$\frac{\left(z_1t_1\cdots z_nt_n-x_1y_1\cdots x_ny_n\right)}{\prod_{i,j=1}^n(1-x_iy_j)(1-t_iz_j)}.$$

---

En una dirección diferente, tenemos $$M(n,k)=\sum_{i=0}^d h_i\binom{k+i}{d}$$ donde $d=(n-1)^2$. En "Ehrhart polinomios, simplicial polytopes, los cuadrados mágicos y una hipótesis de Stanley", C. A. Athanasiadis demostrado que $(h_0,h_1-h_0,\dots,h_{\lfloor d/2\rfloor}-h_{\lfloor d/2\rfloor-1})$ g es un vector, por lo que satisface las desigualdades de Mcmullen del g-teorema. En particular, $h$ es simétrica unimodal de la secuencia. Dudo que esto es suficiente para concluir registro de la concavidad de $M(n,k)$ o de su propiedad para el caso, pero tal vez da una idea de cuán duro es el problema.

Answer 3

Vamos a ampliar el conjunto de variables y considerar de manera más general, para $a\in\mathbb{N}^n$ e $b\in\mathbb{N}^m$, el número de $n\times m$ matrices con entero no negativo de los coeficientes cuyas $i$-ésima fila sumas de dinero a $a_i$ y cuyas $j$-ésima columna de sumas de dinero a $b_j$, para $1\le i\le n$ e $1\le j\le m$: $$\mu(a,b):= \Big| \big\{v\in\mathbb{N}^{n\times m}\ :\ \sum_{1\le j\le m}v_{ij}=a_i\ , \sum_{1\le i\le n}v_{ij}=b_j\big\}\Big|\, .$$ Entonces, para $x:=(x_1,\dots,x_n)$ e $y:=(y_1,\dots,y_m)$ $$\sum_{a\in\mathbb{N}^n\cima b\in\mathbb{N}^m}\mu(a,b)x^ay^b=\sum_{v\in\mathbb{N}^{n\times m} } \prod_{1\le i\le n \encima de 1\le j\le m} x_i ^{\sum_jv_{ij}} y_j ^{\sum_iv_{ij}}=\prod_{1\le i\le n \encima de 1\le j\le m}(1-x_iy_j)^{-1}\, . $$ Por lo tanto $\mu$ es la convolución discreta de ciertos $nm$ log-cóncava funciones de $\delta _{ij}:\mathbb{N}^{n+m}\to[0,\infty)$ , es decir, los coeficientes de las secuencias de $(1-x_iy_j)^{-1}$. Una convolución discreta de registro-cóncavo funciones discretas $\mathbb{N}^p\a [0,\infty)$ es log-cóncava [editar: este tiene que ser activada!].
En particular, para $n=m$ e $u=(1,\dots,1)$ la secuencia de $|M(n,k)|=\mu(ku,ku)$ es registro-cóncavo w.r.a $k\in\mathbb{N}\, .$

Answer 4

Bien, esto está lejos de una solución completa, pero esto es como lo que yo tengo y espero que alguien más lo ve desde aquí:

Está claro que $P(2,k) = \frac{k-1}{k+1}~$ que sin duda es no decreciente en $k$.

Al $n=3$, las matrices en $M(3,k)$ corresponden a cuatro enteros $a_{11},a_{12},a_{21},a_{22}~$ de $0,\ldots,k~$ tal que

1. Para $i = 1$ o $2~$, $\sum_j a_{ij} \leq k$
2. Para $j = 1$ o $2~$, $\sum_i a_{ij} \leq k$
3. Y por último, $\sum_{ij} a_{ij} \geq k$.

Estos hyperplane desigualdades labrarse una región convexa $C \subset \mathbb{R}^4$ desde el cubo de $[0,k]^4$ y el "cero" de entrada de los casos de $M(3,k)$ son precisamente la delimitación de las caras de esta región.

Por lo tanto, si un teorema establece que la relación de $$\frac{\text{integral points on the boundary of } C}{\text{ total number of integral points in }C}$$ decreases as one increases $k$, entonces obtendremos el resultado deseado. No sé lo suficiente acerca de la convexo polytopes citar algo, pero suena razonable de la dimensión consideraciones...

Idealmente, este proceso podría generalizar a dimensiones superiores. Un elemento de $M(n,k)$ tiene cero entradas si y sólo si el vector de entradas de la primera $(n-1) \times (n-1)$ bloque se encuentra en el límite de convexo polytope tallada en el cubo de $[0,1]^{(n-1)^2}$ por $2n-1$ hyperplanes.