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

DOI10.1215/00127094-1548344zbMATH Open1276.15019arXiv1101.3074OpenAlexW2963301182MaRDI QIDQ410097FDOQ410097

Authors: Hoi Nguyen 

Publication date: 17 April 2012

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Additive combinatorics
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
• Estimates for the concentration function of combinatorial number theory and probability
• Optimal inverse Littlewood-Offord theorems
• Random symmetric matrices are almost surely nonsingular.
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• On the Kolmogorov-Rogozin inequality for the concentration function
• Title not available (Why is that?)
• On the singularity probability of discrete random matrices
• On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
• A sharp inverse Littlewood-Offord theorem
• Two Uniform Limit Theorems for Sums of Independent Random Variables
• An Estimate for Concentration Functions
• On the singularity probability of random Bernoulli matrices
• On the Probability That a Random ± 1-Matrix Is Singular
• Über ein Problem von Erdös und Moser
• On a lemma of Littlewood and Offord
• On subspaces spanned by random selections of \(\pm 1\) vectors
• Probability inequalities for convex sets and multidimensional concentration functions
• Symmetrization and concentration inequalities for multilinear forms with applications to zero-one laws for Lévy chaos
• Bilinear and quadratic variants on the Littlewood-Offord problem
• Title not available (Why is that?)

Cited In (35)

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

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)