La singularidad de escasa matrices aleatorias

Question

El siguiente tema surgió en una conversación con mi oficina compañero de Lionel: Vamos a $p$ ser una prima fija, $c$ fijo positivo parámetro real y $n$ un gran número. Considere la posibilidad de un random $(0,1)$ matriz con entradas en $Z/p$, donde la probabilidad de un $0$ $1-\frac{c}{n}$ y que de una$1$$\frac{c}{n}$. Como $n\rightarrow \infty$, ¿cuál es la probabilidad de que esta matriz es singular? ACTUALIZACIÓN: Como cara luna llena señala, esta probabilidad es $1$. Además, su argumento señala que debemos esperar que el corank a ser algo parecido a $a*n$. Así que os pido más general, ¿qué podemos decir acerca del comportamiento de la clasificación como $n\rightarrow\infty$.

En realidad, en nuestro ejemplo muy motivador, la matriz es simétrica y la distribución de la diagonal es diferente que en el resto de la matriz. Dejé a estos detalles, pero por favor, mencionar que si este punto atrevería a efecto de su respuesta.

Answer 1

Un par de minutos de valores numéricos sugiere tentativamente que existe f=f(c) para que la corank/n se acerca f(c) con probabilidad 1. Curiosamente, en los pocos ejemplos que he intentado, f(c), parece que no dependen de p y la respuesta puede ser la misma que la sustitución de Z/pZ con Z. (Esto hace sentido intuitivo: Si usted toma una parte integral de la matriz, su rango mod p podría ser menor, pero es muy poco probable que sea mucho menor.)

Creo que uno puede dar a los límites inferior y superior que son lineales en n (de nuevo, con una alta probabilidad), pero no veo cómo llegar a converger. Estoy interesado en saber el origen de esta bonita pregunta.

Answer 2

Un par de observaciones:

-Como n tiende a infinito, la función de corank/n es altamente concentrado para cada n -- por ejemplo, podemos pensar en la exposición de la matriz menor por menor (busca en la parte superior izquierda kxk matriz para k cada vez mayor hacia la n). Desde el cambio de lo que sucede en cada nivel de exposición sólo puede afectar el rango de la matriz a la mayoría de los 2, se desprende de Azuma la desigualdad que el rango se concentra en un intervalo de ancho sobre Sqrt(n).

-Un reciente preprint de Bordenave y Lelarge (El rango de diluido grafos aleatorios) puede ser de relevancia aquí.

Hay que considerar un modelo que incluye las matrices de adyacencia de Erdos-Renyi gráficos con el borde de la probabilidad de c/n y muestran que la proporción de rango/n converge a una función explícita (que también resulta ser el tamaño de la máxima coincidente en el gráfico).

Las diferencias entre su trabajo y su modelo son

(1) Se consideran las matrices sobre los reales en lugar de sobre un campo finito.

y

(2) hacen suposiciones acerca de los grafos aleatorios convergentes localmente a un árbol. Sus resultados sin duda se aplicará si la diagonal entradas son 0, y a partir del entrelazamiento de sus resultados debe también llevar a cabo si su distribución no deje que muchas de las entradas de la diagonal se convierten en no-cero.

Sin embargo, yo esperaría un drásticamente diferentes corank si un positivo proporción de las entradas de la diagonal son cero. La principal contribución a la corank en estos gráficos vienen de no ampliación de los conjuntos de filas (conjuntos de k filas que tienen distinto de cero entradas en menos de k columnas). Mediante el ajuste de la diagonal de entradas, puedo eliminar ESA fuente de la dependencia, aunque al mismo tiempo voy a ser, posiblemente, la creación de otros. (EDIT: Por ejemplo, si todas las entradas de la diagonal iguales a 1, he creado una nueva constante*n fuentes de la dependencia correspondiente para el aislado de las aristas en el grafo.

Volviendo a la asunción (1), mi conjetura es que haga sólo una pequeña diferencia en el rango de la matriz. Mi intuición de esto es doble.

(1) Si tenemos en cuenta la no-simétrica matrices densas en lugar de la escasa (por ejemplo, haciendo que la probabilidad de cualquier entrada de la toma cualquier valor que se apartó de 1), entonces la probabilidad de que la matriz tiene rango n-k es infinitamente pequeño en k

(2) Si c es suficientemente pequeño, entonces (como se observa por Bauer y Golinelli) se puede obtener una buena estimación en el rango de la matriz aleatoria en varias ocasiones siguiendo el siguiente procedimiento: Busque un vértice con exactamente un vecino en el gráfico (una fila y una columna con exactamente una entrada distinto de cero), y retire ese vértice y su vecino de la gráfica. Al hacerlo se reduce el rango de la matriz por exactamente 2 sin importar el campo en el que estamos trabajando. Para c menos de correo, se puede seguir este procedimiento hasta que el o(n) no aislado vértices restantes, lo que implica que el campo en el que estamos trabajando sobre la voluntad sólo afectan el rango de la matriz por o(n). Para c mayor que e, no veo ninguna razón para esperar que cualquier comportamiento diferente.

Tenga en cuenta que el argumento en (2) aquí es, de nuevo, depende fuertemente de la distribución de las entradas de la diagonal y se rompe si las entradas son cero. Aún así, yo no esperaría a importar demasiado.

Answer 3

Unas palabras de precaución acerca de las matrices aleatorias sobre campos finitos: se necesita muy poca desviación del cero distribución de la fuerza de las propiedades espectrales de una matriz aleatoria a parecer uno de los elegidos con una distribución uniforme.

Por ejemplo, el Z/pZ y tener en cuenta la distribución, donde cada entrada es de 0 con probabilidad 1 - (log n)^2/n y 1 con probabilidad (log n)^2/n. La probabilidad de que el azar de la matriz es no singular, entonces converge a (1 - 1/p)(1 - 1/p^2)(1 - 1/p^3)...(1-1/p^n), que es la misma probabilidad como una manera uniforme elegido matriz de M(n,Z/pZ) no singular. En otras palabras, la singularidad de la probabilidad van a converger a una constante de alrededor de 1/p, a no a cero o a uno, y la probabilidad de que la matriz tiene corank k es aproximadamente 1/p^k. Este fenómeno se mantenga el mayor tiempo de la distribución que usted elija no se concentra más de 1 log n/n; de lo contrario, en efecto, nos espera la matriz a ser casi seguramente singular como la n -> infty, como es el caso de la matriz aleatoria en el post original.

El punto clave parece ser la delimitación de la probabilidad de que una fila es todo ceros o que la matriz tiene varias hileras iguales. Si usted puede demostrar que la probabilidad de que dicho evento se va a cero cuando n -> infty, entonces yo esperaría que la asymptotics he mencionado anteriormente para tomar el relevo.