Random symmetric matrices are almost surely nonsingular.

DOI10.1215/S0012-7094-06-13527-5MaRDI QIDQ854582zbMATH OpenOpenAlexFDO

Authors Kevin P. Costello, Terence Tao, Van Vu

Publication date 5 December 2006

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3245540 (Why is no real title available?)
• scientific article; zbMATH DE number 3359487 (Why is no real title available?)
• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• Estimates for the concentration function of combinatorial number theory and probability
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Invertibility of random matrices: norm of the inverse
• On a lemma of Littlewood and Offord
• On random ±1 matrices: Singularity and determinant
• On the Probability That a Random ± 1-Matrix Is Singular
• On the singularity probability of random Bernoulli matrices

Cited in

(65)

• The least singular value of a random symmetric matrix
• Resilience for the Littlewood-Offord problem
• The singularity probability of a random symmetric matrix is exponentially small
• On the rank, kernel, and core of sparse random graphs
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• The distribution of sandpile groups of random graphs with their pairings
• Quantitative invertibility of non-Hermitian random matrices
• Almost sure behavior of the zeros of iterated derivatives of random polynomials
• Some new results in random matrices over finite fields
• Resilience for the Littlewood-Offord problem
• Fixed energy universality of Dyson Brownian motion
• Graphs with integral spectrum
• Random matrices, geometric functional analysis and algorithms. Abstracts from the workshop held May 1--7, 2011.
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Recent progress in combinatorial random matrix theory
• Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
• Random matrices: universality of local eigenvalue statistics
• Singularity of the \(k\)-core of a random graph
• scientific article; zbMATH DE number 7732139 (Why is no real title available?)
• A central limit theorem for the determinant of a Wigner matrix
• Some counting questions for matrices with restricted entries
• Anticoncentration for subgraph statistics
• On the singularity of random symmetric matrices
• Invertibility of symmetric random matrices
• Polynomial threshold functions, hyperplane arrangements, and random tensors
• What is the probability that a random integral quadratic form in \(n\) variables has an integral zero?
• Combinatorial anti-concentration inequalities, with applications
• Spectral lower bounds for the orthogonal and projective ranks of a graph
• From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
• Singularity of random symmetric matrices revisited
• Subdeterminant maximization via nonconvex relaxations and anti-concentration
• The rank of diluted random graphs
• Spectrum and pseudospectrum for quadratic polynomials in Ginibre matrices
• On the rank of random sparse matrices
• Spectrum of heavy-tailed elliptic random matrices
• Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
• Gaussian fluctuations of the determinant of Wigner 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 characteristic polynomial of a random matrix
• A generalization of Komlós's theorem on random matrices
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• Bilinear and quadratic variants on the Littlewood-Offord problem
• Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial
• The rank of random regular digraphs of constant degree
• Spectral statistics of non-Hermitian random matrix ensembles
• 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
• 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
• Permutational powers of a graph
• Eigenvectors of random graphs: nodal domains
• Anticoncentration and Berry-Esseen bounds for random tensors
• The rank of random graphs
• Hitting Time Theorems for Random Matrices
• On polynomial approximations to \(\mathrm{AC}^0\)
• Anti-concentration Inequalities for Polynomials
• Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients
• On the universality of the non-singularity of general Ginibre and Wigner random matrices

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)