A large deviation inequality for the rank of a random matrix

Abstract

Let $A$ be an $n\times n$ random matrix with independent identically distributed non-constant subgaussian entries. Then for any $k\le c\sqrt{n}$, \[ \text{rank}(A) \ge n-k \] with probability at least $1-\exp (-c^{\prime }kn)$.