On the singularity of random symmetric matrices

2019/04/25 by Campos, Marcelo, Mattos, Letícia, Morris, Robert +1 · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1904.11478

Abstract

A well-known conjecture states that a random symmetric n × n matrix with entries in \-1,1\ is singular with probability Θ( n² 2^-n ). In this paper we prove that the probability of this event is at most exp( - Ω( √(n) ) ), improving the best known bound of exp( - Ω( n^1/4 √(log n) ) ), which was obtained recently by Ferber and Jain. The main new ingredient is an inverse Littlewood-Offord theorem in ℤ_pⁿ that applies under very mild conditions, whose statement is inspired by the method of hypergraph containers.

Cited by

• Probabilistic combinatorics at exponentially small scales
• Invertibility for non-Hermitian and symmetric random band matrices with sublinear bandwidth and discrete entries

Related

• Singularity of random symmetric matrices revisited
• Singularity of random symmetric matrices -- simple proof
• The singularity probability of a random symmetric matrix is exponentially small
• On the singularity of random combinatorial matrices
• Random symmetric matrices are almost surely non-singular