Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices

Abstract

An approximate Spielman-Teng theorem for the least singular value $s_n(M_n)$ of a random $n\times n$ square matrix $M_n$ is a statement of the following form: there exist constants $C,c>0$ such that for all $\eta \ge 0$, $\mathrm{Pr}(s_n(M_n)\le \eta )\lesssim n^C\eta +\exp (-n^c)$. The goal of this paper is to develop a simple and novel framework for proving such results for discrete random matrices. As an application, we prove an approximate Spielman-Teng theorem for $\{0,1\}$-valued matrices, each of whose rows is an independent vector with exactly $n/2$ zero components. This improves on previous work of Nguyen and Vu, and is the first such result in a `truly combinatorial' setting.

28 pages; comments welcome!

Cited by in corpus (2)

• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• Resilience of the Rank of Random Matrices