1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.