Singularity of random symmetric matrices revisited

Abstract

Let M-n be drawn uniformly from all +/- 1 symmetric nxn matrices. We show that the probability that M-n is singular is at most exp(-c(n log n)(1/2)), which represents a natural barrier in recent approaches to this problem. In addition to improving on the best-known previous bound of Campos, Mattos, Morris and Morrison of exp(-cn(1/2)) on the singularity probability, our method is different and considerably simpler: we prove a "rough" inverse Littlewood-Offord theorem by a simple combinatorial iteration.