La probabilidad de una $1000 \times 1000$ matriz cuadrada sobre $\mathbb{Z}_2$ tener rango completo

Question

Sólo hay dos entradas, $0$$1$,$\mathbb{Z}_2$. Por lo tanto, sólo $16$ $2\times2$ matrices de más de $\mathbb{Z}_2$, e $6$ de ellos tiene rango completo:

$$\begin{pmatrix}0&1\\ 1&0\end{pmatrix} \quad \begin{pmatrix}1&1\\ 1&0\end{pmatrix} \quad \begin{pmatrix}0&1\\ 1&0\end{pmatrix} \quad \begin{pmatrix}0&1\\ 1&1\end{pmatrix} \quad \begin{pmatrix}1&1\\ 0&1\end{pmatrix} \quad \begin{pmatrix}1&0\\ 0&1\end{pmatrix}$$

Generar aleatoriamente una $n \times n$ matriz $\mathbb{Z}_2$ (donde $n$ es grande, dicen, $1000$). ¿Cuál es la probabilidad de que la matriz tiene rango completo?

Answer 1

La probabilidad de que un random $n$a$n$ matriz sobre un campo de $q$ elementos es no singular, es $$P(n,q)=\prod_{k=1}^n\left(1-\frac1{q^k}\right).$$ Para probar esto, demostrar que la probabilidad de que el $k$-ésima fila es linealmente independiente de las filas anteriores, con la condición de aquellos anterior filas linealmente independientes, es $1-1/q^{n+1-k}$.

Como $n\to\infty$ fijo $q$, $P(n,q)$ tiende a una positiva límite. De hecho $$\prod_{k=1}^\infty\left(1-\frac1{q^k}\right) =1-\frac1{q}-\frac1{p^2}+\frac1{q^5}+\frac1{q^7}-\cdots =1+\sum_{m=1}^\infty(-1)^m(q^{-m(3m-1)/2}+p^{{-m(3m+1)/2}})$$ por Euler pentagonal número teorema. Para un gran $n$, un par de términos de esto le dará una buena aproximación a $P(n,q)$.

Answer 2

El grupo lineal general $GL(n,q)$ es el grupo de invertible $n\times n$ matrices sobre un campo con $q$ elementos (nota: $q=p^k$ para algunos prime $p$).

El orden de $$|GL(n,q)|=\prod_{k=0}^{n-1}(q^n-q^k)$$

Por lo que la probabilidad es $$\dfrac{1}{q^{n^2}}\prod_{k=0}^{n-1}(q^n-q^k)$$

Para $n=2$ $q=2$ consigue $\frac{1}{2^4}(2^2-2)(2^2-1)=\frac{6}{16}$