Back to Search
Start Over
On the singularity of random symmetric matrices
- 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
- Subjects :
- Mathematics - Combinatorics
Mathematics - Probability
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1904.11478
- Document Type :
- Working Paper