17
$\begingroup$

If $S = \{ A_{m \times n} : m > n, A_{ij} \in \{0,1\} \}, $ is the set of all $m \times n$ binary matrices, and I choose a random matrix $r \in S$, what would be the probability that $r$ would have full column rank (each of the n columns would be linearly independent)?

Several papers simply claim that this probability is very high, but I'm curious as to what the exact probability would be, and how to compute it.

$\endgroup$
2
  • 3
    $\begingroup$ This seems to be already hard to answer in the case $m=n$ (even if it is excluded in the question it would probably follow from a solution). See math.stackexchange.com/questions/54246/… $\endgroup$
    – Listing
    Commented Nov 12, 2013 at 22:07
  • $\begingroup$ Even for the $n\times n$ case the probability is only conjectured. (ref) $\endgroup$
    – Alexander Gruber
    Commented Nov 12, 2013 at 23:04

1 Answer 1

13
$\begingroup$

Let $m>n$, and $\{v_1,\ldots,v_{n+1}\}$ be random vectors in $\mathbb{F}^m_2$. Call $p_n$ the probability that $\{v_1,\ldots,v_n\}$ are linearly independent.

In that case, $\{v_1,\ldots,v_{n+1}\}$ are independent (event $A_n$) if and only if $\{v_1,\ldots, v_n\}$ are independent and $v_{n+1} \notin \left<v_1,\ldots,v_n\right>$ (event $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})$, since a single vector is independent if and only if it's not $0$, so: $$p_n = \prod_{i=1}^n (1-2^{i-1-m})$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .