Random symmetric matrices are almost surely nonsingular.

DOI10.1215/S0012-7094-06-13527-5zbMATH Open1110.15020arXivmath/0505156OpenAlexW2050767937MaRDI QIDQ854582FDOQ854582

Van Vu, Terence Tao, Kevin P. Costello

Publication date: 5 December 2006

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

Abstract: Let $Q_n$ denote a random symmetric $n$ by $n$ matrix, whose upper diagonal entries are i.i.d. Bernoulli random variables (which take values 0 and 1 with probability 1/2). We prove that $Q_n$ is non-singular with probability $1-O(n^{-1/8+delta})$ for any fixed $delta>0$. The proof uses a quadratic version of Littlewood-Offord type results concerning the concentration functions of random variables and can be extended for more general models of random matrices.

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

Recommendations

• Singularity of random symmetric matrices -- simple proof
• On the singularity of random symmetric matrices
• Singularity of random symmetric matrices revisited
• On the least singular value of random symmetric matrices
• The eigenvalues of random symmetric matrices
• On the permanent of a random symmetric matrix
• Invertibility of symmetric random matrices
• The probability of a rational random matrix to be nonsingular
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial

zbMATH Keywords

quadratic formsLittlewood-Offord inequalitynon-singular

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Inequalities; stochastic orderings (60E15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Estimates for the concentration function of combinatorial number theory and probability
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Title not available (Why is that?)
• Invertibility of random matrices: norm of the inverse
• On the singularity probability of random Bernoulli matrices
• On the Probability That a Random ± 1-Matrix Is Singular
• Title not available (Why is that?)
• On a lemma of Littlewood and Offord
• On random ±1 matrices: Singularity and determinant
• Title not available (Why is that?)

Cited In (64)

• The least singular value of a random symmetric matrix
• Almost sure behavior of the zeros of iterated derivatives of random polynomials
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• The singularity probability of a random symmetric matrix is exponentially small
• Resilience for the Littlewood-Offord problem
• The distribution of sandpile groups of random graphs with their pairings
• On the rank, kernel, and core of sparse random graphs
• Quantitative invertibility of non-Hermitian random matrices
• Singularity of the \(k\)-core of a random graph
• Combinatorial anti-concentration inequalities, with applications
• Gaussian fluctuations of the determinant of Wigner matrices
• Some new results in random matrices over finite fields
• From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
• Singularity of random symmetric matrices revisited
• Geometric and o-minimal Littlewood-Offord problems
• Anti-concentration Inequalities for Polynomials
• Resilience for the Littlewood-Offord problem
• SINGULARITY OF RANDOM SYMMETRIC MATRICES—A COMBINATORIAL APPROACH TO IMPROVED BOUNDS
• Anticoncentration for subgraph statistics
• Random matrices, geometric functional analysis and algorithms. Abstracts from the workshop held May 1--7, 2011.
• Invertibility of symmetric random matrices
• Spectral lower bounds for the orthogonal and projective ranks of a graph
• On the smallest singular value of symmetric random matrices
• Random matrices: universality of local eigenvalue statistics
• The characteristic polynomial of a random matrix
• Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• Permutational powers of a graph
• Hitting Time Theorems for Random Matrices
• Graphs with integral spectrum
• A central limit theorem for the determinant of a Wigner matrix
• The rank of random regular digraphs of constant degree
• The distribution of sandpile groups of random graphs
• 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
• Singularity of random symmetric matrices -- simple proof
• On the universality of the non-singularity of general Ginibre and Wigner random matrices
• On the singularity of random symmetric matrices
• Inverse Littlewood-Offord problems and 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
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Recent progress in combinatorial random matrix theory
• Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors
• On polynomial approximations to AC
• The rank of random graphs
• Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
• Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients
• The rank of diluted random graphs
• On the Rank of Random Sparse Matrices
• Title not available (Why is that?)
• Some counting questions for matrices with restricted entries
• A generalization of Komlós's theorem on random matrices
• Invertibility of adjacency matrices for random \(d\)-regular graphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Spectrum and pseudospectrum for quadratic polynomials in Ginibre matrices
• Spectrum of heavy-tailed elliptic random matrices
• Eigenvectors of random graphs: Nodal Domains
• Fixed energy universality of Dyson Brownian motion
• Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration
• Spectral statistics of non-Hermitian random matrix ensembles
• Anticoncentration and Berry-Esseen bounds for random tensors

This page was built for publication: Random symmetric matrices are almost surely nonsingular.

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