On random matrices with large corank

Abstract

Let $1\le k\le n$ and $M$ be a random $n\times n$ matrix with independent uniformly random $\{\pm 1\}$-entries. We show that there exists an absolute constant $c>0$ such that \[\mathbf{P}[\operatorname{rank}(M)\le n-k]\le \exp(-c nk).\]

8 pages