Expected rank of a random binary matrix?
Solution 1:
The rank of a random $n$ by $n$ matrix with entries in ${\Bbb F}_2$ which are independently chosen and equally likely to be $0$ or $1$ is analyzed in Kolchin's book Random Graphs in $\S 3.2$. He concludes that the probability that the rank of a random $n$ by $n$ matrix is $n-s$ equals
$$
P_{n,s}:=2^{-s^2}\left( \prod_{0\le i\le n-s-1} (1-2^{-(n-i)}) \right)\left(\sum_{0\le i_1\le \cdots \le i_s \le n-s} 2^{-i_1-\cdots-i_s}\right). \ \ (*)
$$
This is obtained by building up the matrix row by row. If, after a given number of rows, the space spanned by these rows has dimension $k$, then the next row increases the rank with probability $1-2^{-(n-k)}$, and leaves it unchanged with probability $2^{-(n-k)}$. Assuming that the rank of the full matrix is $n-s$, there must be $n-s$ rows which increase the rank and $s$ which leave it unchanged. Which rows leave it unchanged can be specified by giving the partial ranks of the matrix at the times when these rows are added. If these ranks, in nondecreasing order, are $n-s-i_s$, $n-s-i_{s-1}$, $\dots$, $n-s-i_1$ ($0\le i_1\le\cdots\le i_s\le n-s$), then the probability of getting a rank $n-s$ matrix in this way can be written as the product
\begin{eqnarray*}
&&(1-2^{-n})(1-2^{-(n-1)})\cdots(1-2^{-(i_s+s+1)})2^{-(i_s+s)}\\
&&(1-2^{-(i_s+s)})(1-2^{-(i_s+s-1)})\cdots(1-2^{-(i_{s-1}+s+1)})2^{-(i_{s-1}+s)}\\
&&\vdots\\
&&(1-2^{-(i_2+s)})(1-2^{-(i_2+s-1)})\cdots(1-2^{-(i_1+s+1)})2^{-(i_1+s)}\\
&&(1-2^{-(i_1+s)})(1-2^{-(i_1+s-1)})\cdots(1-2^{-(s+1)}).
\end{eqnarray*}
Simplifying the product and summing over $i_1$, $\dots$, $i_s$ yields $(*)$.
If $s=0$, this is easy to see: the $j$th row must always increase the rank from $j-1$ to $j$, which it does with probability $1-2^{-(n-(j-1))}$, so the probability that the matrix is of full rank is
$$
P_{n,0}=\prod_{1\le k\le n} (1-2^{-k}).
$$
For fixed $s$, as $n$ becomes large, $P_{n,s}$ approaches the limiting value
$$
Q_s:=2^{-s^2} \left( \prod_{i\ge s+1} (1-2^{-i}) \right)\left(\prod_{1\le i\le s} (1-2^{-i})^{-1}\right).
$$
Numerically,
\begin{eqnarray*}
Q_0&\approx&0.2887880950866, \qquad \text{(OEIS A048651)}\\
Q_1&\approx&0.5775761901732,\\
Q_2&\approx&0.1283502644829,\\
Q_3&\approx&0.0052387863054,\\
Q_4&\approx&4.656698938156\cdot 10^{-5},\\
Q_5&\approx&9.691360953499\cdot 10^{-8},\\
Q_6&\approx&4.883527817334\cdot 10^{-11},\\
& & \text{and so on}:
\end{eqnarray*}
the random matrix is very likely to have rank only slightly less than $n$. The expected value of the rank of the matrix will equal $n-\sum_{0\le s\le n} s P_{n,s}$. As $n$ becomes large, this approaches $n-\eta$, where
$$
\eta:=\sum_{s\ge 0} s Q_s\approx0.850179830874.
$$
If the matrix is over $\Bbb Q$ instead of over ${\Bbb F}_2$, still with entries which are independently chosen and equally likely to be $0$ or $1$, then, when $n$ becomes large, the probability that the matrix has full rank approaches $1$. Bourgain, Vu, and Wood 2009 estimates it as at least $1-(2^{-1/2}+o(1))^n$. (The estimate is stated for random matrices with entries in $\{\pm 1\}$, but it can be transferred to matrices with entries in $\{0,1\}$.) Therefore, as $n$ becomes large, the expected rank approaches $n$. The number of singular rational matrices with a given size and entries in $\{0,1\}$ is OEIS A046747.