Back to Search Start Over

On the singularity of random symmetric matrices

Authors :
Campos, Marcelo
Mattos, Letícia
Morris, Robert
Morrison, Natasha
Publication Year :
2019

Abstract

A well-known conjecture states that a random symmetric $n \times n$ matrix with entries in $\{-1,1\}$ is singular with probability $\Theta\big( n^2 2^{-n} \big)$. In this paper we prove that the probability of this event is at most $\exp\big( - \Omega( \sqrt{n} ) \big)$, improving the best known bound of $\exp\big( - \Omega( n^{1/4} \sqrt{\log n} ) \big)$, which was obtained recently by Ferber and Jain. The main new ingredient is an inverse Littlewood-Offord theorem in $\mathbb{Z}_p^n$ that applies under very mild conditions, whose statement is inspired by the method of hypergraph containers.<br />Comment: 16 pages, plus a 10-page appendix

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1904.11478
Document Type :
Working Paper