Inverse Littlewood-Offord problems and the singularity of random symmetric matrices

DOI10.1215/00127094-1548344MaRDI QIDQ410097zbMATH OpenOpenAlexFDO

Authors Hoi Nguyen

Publication date 17 April 2012

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

Full work available at URL https://arxiv.org/abs/1101.3074, https://projecteuclid.org/euclid.dmj/1330610807

zbMATH Keywords

singularityrandom matricesBernoulli random variablesquadratic formssymmetric matricesarithmetic combinatoricsinverse Littlewood-Offord problemsrandom matrices (probabilistic aspects)relations with random matrices

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Quadratic and bilinear forms, inner products (15A63) Arithmetic combinatorics; higher degree uniformity (11B30) Relations with random matrices (11M50)

Abstract: Let $M_n$ denote a random symmetric $n$ by $n$ matrix, whose upper diagonal entries are iid Bernoulli random variables (which take value -1 and 1 with probability 1/2). Improving the earlier result by Costello, Tao and Vu, we show that $M_n$ is non-singular with probability $1-O(n^{-C})$ for any positive constant $C$. The proof uses an inverse Littlewood-Offord result for quadratic forms, which is of interest of its own.

Recommendations

• The Littlewood-Offord problem and invertibility of random matrices
• On the singularity of random symmetric matrices
• Singularity of random symmetric matrices revisited
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• On the least singular value of random symmetric matrices
• Invertibility of symmetric random matrices
• On the smallest singular value of symmetric random matrices
• Singularity of random symmetric matrices -- simple proof
• An inverse problem for symmetric doubly stochastic matrices

Cites work

• scientific article; zbMATH DE number 5296054 (Why is no real title available?)
• scientific article; zbMATH DE number 3230288 (Why is no real title available?)
• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• A sharp inverse Littlewood-Offord theorem
• Additive combinatorics
• An Estimate for Concentration Functions
• Bilinear and quadratic variants on the Littlewood-Offord problem
• Estimates for the concentration function of combinatorial number theory and probability
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• On a lemma of Littlewood and Offord
• On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
• On subspaces spanned by random selections of \(\pm 1\) vectors
• 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
• Probability inequalities for convex sets and multidimensional concentration functions
• Random symmetric matrices are almost surely nonsingular.
• Symmetrization and concentration inequalities for multilinear forms with applications to zero-one laws for Lévy chaos
• Two Uniform Limit Theorems for Sums of Independent Random Variables
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
• Über ein Problem von Erdös und Moser

Cited in

(36)

• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• The least singular value of a random symmetric matrix
• Recent progress in combinatorial random matrix theory
• Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
• Random integral matrices: universality of surjectivity and the cokernel
• Anticoncentration for subgraph statistics
• On the counting problem in inverse Littlewood-Offord theory
• On the singularity of random symmetric matrices
• Invertibility of symmetric random matrices
• Polynomial threshold functions, hyperplane arrangements, and random tensors
• Singularity of random symmetric matrices revisited
• Spectrum and pseudospectrum for quadratic polynomials in Ginibre matrices
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• The distribution of sandpile groups of random graphs
• The singularity probability of a random symmetric matrix is exponentially small
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• Small ball estimates for quasi-norms
• Bilinear and quadratic variants on the Littlewood-Offord problem
• Concentration of distances in Wigner matrices
• Random doubly stochastic matrices: the circular law
• The rank of random regular digraphs of constant degree
• Invertibility of adjacency matrices for random \(d\)-regular graphs
• Adjacency matrices of random digraphs: singularity and anti-concentration
• On the number of integral graphs
• On the smallest singular value of symmetric random matrices
• On the permanent of a random symmetric matrix
• Non-abelian Littlewood-Offord inequalities
• Geometric and o-minimal Littlewood-Offord problems
• On the concentration of random multilinear forms and the universality of random block matrices
• Singularity of random symmetric matrices -- simple proof
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• The Littlewood-Offord problem and invertibility of random matrices
• Surjectivity of near-square random matrices
• Quantitative invertibility of non-Hermitian random matrices
• Anti-concentration Inequalities for Polynomials

This page was built for publication: Inverse Littlewood-Offord problems and 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 Q410097)