# Probability that random Bernoulli matrix is full rank

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) 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}}$$

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$$.