This is probably known already, but I could not find a quick argument. 


Let $M$ be an $n\times m$ binary matrix with iid Bernoulli$(1/2)$ entries, and $n>m$. Tikhomirov recently settled that the probability that an $m\times m$ such matrix is singular is $(1/2+o(1))^m$. 


My question is: What is a good lower bound on the probability that, $\mathbb{P}({\rm rank}(M)=m)$ as a function of $m,n$? Note that, simply passing to any $m\times m$ sub matrix, $1-(1/2+o(1))^m$ is a trivial lower bound. But this does not depend on $n$, and I am interested in understanding what happens when $n\gg m$. 


**Edit** I have one argument, but would really appreciate other input. Similar to Vu's argument on Komlos' proof for the fact that Bernoulli matrix singularity probability is $o(1)$ let $M\_1,\dots,M\_m\in\mathbb{R}^n$ be the columns of $M$, and let $V\_i={\rm span}(M\_1,\dots,M\_{i-1})$. Then,
$$
\mathbb{P}({\rm rank}(M)<m) \leqslant \sum\_{i=1}^m \mathbb{P}(M\_i\in V\_i).
$$
Now, $V\_i$ is of dimension at most $i-1$, therefore, each probability above is at most $2^{i-1}/2^n$. Summing up, we get something like
$$
\mathbb{P}({\rm rank}(M)=m)\geqslant 1- \frac{2^m}{2^{n-1}}
$$



Probability that random Bernoulli matrix is full rank
Apparently, the paper "ON THE PROBABILITY THAT A RANDOM ±1-MATRIX IS SINGULAR" by Kahn, Komlos and Szemeredi (Corollary 4 therein) answers my question, and states that it is $(1+o(1))2\binom{m}{2}/2^n$, thereby improving the bound from exponential in $m$ to polynomial in $m$.


<https://www.ams.org/journals/jams/1995-08-01/S0894-0347-1995-1260107-2/S0894-0347-1995-1260107-2.pdf>


