On the singularity of random symmetric matrices

DOI10.1215/00127094-2020-0054MaRDI QIDQ2037848zbMATH OpenOpenAlexFDO

Authors Marcelo Campos, Letícia Mattos, Robert Morris, Natasha Morrison

Publication date 8 July 2021

Published in Duke Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.11478

zbMATH Keywords

containersinverse Littlewood-Offord theoremsrandom symmetric matricessingularity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: A well-known conjecture states that a random symmetric $nimesn$ matrix with entries in $-1,1$ is singular with probability $$. In this paper we prove that the probability of this event is at most $$, improving the best known bound of $$, 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.

Recommendations

• Singularity of random symmetric matrices revisited
• Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• Invertibility of symmetric random matrices
• On the smallest singular value of symmetric random matrices

Cites work

• Estimates for the concentration function of combinatorial number theory and probability
• From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
• scientific article; zbMATH DE number 6803211 (Why is no real title available?)
• scientific article; zbMATH DE number 3245540 (Why is no real title available?)
• scientific article; zbMATH DE number 3031694 (Why is no real title available?)
• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Invertibility of symmetric random matrices
• Non-asymptotic theory of random matrices: extreme singular values
• On a lemma of Littlewood and Offord
• On the Kolmogorov-Rogozin inequality for the concentration function
• On the Probability That a Random ± 1-Matrix Is Singular
• On the singularity probability of discrete random matrices
• On the singularity probability of random Bernoulli matrices
• Optimal inverse Littlewood-Offord theorems
• Random symmetric matrices are almost surely nonsingular.
• Singularity of random Bernoulli matrices
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• Small ball probability, inverse theorems, and applications
• Smallest singular value of a random rectangular matrix
• Solution of the Littlewood-Offord problem in high dimensions
• The Littlewood-Offord problem and invertibility of random matrices
• The method of hypergraph containers

Cited in

(27)

• On the singularity probability of discrete random matrices
• Extreme symmetric stochastic matrices
• On singularity of distribution of random variables with independent symbols of Oppenheim expansions
• Singularity dominated strong fluctuations for some random matrix averages
• Singularity of random symmetric matrices -- simple proof
• On the permanent of a random symmetric matrix
• Invertibility of adjacency matrices for random d-regular graphs
• Spectrum and pseudospectrum for quadratic polynomials in Ginibre matrices
• The characteristic polynomial of a random matrix
• A note about measures and Jacobians of singular random matrices
• On the singular values of random matrices
• Symmetric functionals on random matrices and random matchings problems
• On the singularity probability of random Bernoulli matrices
• Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
• On the counting problem in inverse Littlewood-Offord theory
• Singularity of random symmetric matrices revisited
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• Singularity of sparse random matrices: simple proofs
• On the smallest singular value of symmetric random matrices
• Bernoulli random matrices
• Quantitative invertibility of non-Hermitian random matrices
• The least singular value of a random symmetric matrix
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• The singularity probability of a random symmetric matrix is exponentially small
• Local and global universality of random matrix cokernels
• On the rank of a random symmetric matrix in the large-deviation regime
• Random symmetric matrices are almost surely nonsingular.

This page was built for publication: On the singularity of random symmetric matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2037848)