Probabilidad de que un azar de la matriz binaria tendrá pleno de la columna de rango?

Question

Si $S = \{ A_{m \times n} : m > n, A_{ij} \in \{0,1\} \}, $ es el conjunto de todos los $m \times n$ binario matrices, y puedo elegir una matriz aleatoria $r \in S$, ¿cuál sería la probabilidad de que $r$ total columna de rango de cada una de las n columnas sería linealmente independientes)?

Varios de los documentos, simplemente, afirman que esta probabilidad es muy alta, pero soy curioso en cuanto a lo exacto sería, y cómo se calcula.

Answer 1

Deje $m>n$, e $\{v_1,\ldots,v_{n+1}\}$ aleatorios vectores en $\mathbb{F}^m_2$. Llame a $p_n$ la probabilidad de que $\{v_1,\ldots,v_n\}$ son linealmente independientes.

En ese caso, $\{v_1,\ldots,v_{n+1}\}$ son independientes (evento $A_n$) si y sólo si $\{v_1,\ldots, v_n\}$ son independientes y $v_{n+1} \notin \left<v_1,\ldots,v_n\right>$ ($B_n$).

$$p_{n+1} = P(A_n \cap B_n) = P(A_n)P(B_n|A_n) = (1-2^{n-m})p_n$$

$p_1 = (1-2^{-m})$, desde un único vector es independiente si y sólo si no $0$, así: $$p_n = \prod_{i=1}^n (1-2^{i-1-m})$$