On the rank of a random symmetric matrix in the large deviation regime

Abstract

Let $A$ be an $n\times n$ random symmetric matrix with independent identically distributed subgaussian entries of unit variance. We prove the following large deviation inequality for the rank of $A$: for all $1\le k\le c\sqrt{n}$, $$\mathbb{P}(\mathrm{Rank}(A)\ge n-k)\ge 1-\exp (-c^{\prime }kn),$$ for some fixed constants $c,c^{\prime }>0$. A similar large deviation inequality is proven for the rank of the adjacency matrix of dense Erdos-Renyi graphs. This corank estimate enhances the recent breakthrough of Campos, Jensen, Michelen and Sahasrabudhe that the singularity probability of a random symmetric matrix is exponentially small, and echoes a large deviation inequality of Mark Rudelson for the rank of a random matrix with independent entries.

49 pages. To appear in JLMS