Hitting Time Theorems for Random Matrices

DOI10.1017/S0963548314000285MaRDI QIDQ3191194zbMATH OpenFDO

Authors Louigi Addario-Berry, Laura Eslava

Publication date 24 September 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

determinants, permanents, other special matrix functionsrandom graphsrandom matrices

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Determinants, permanents, traces, other special matrix functions (15A15) Random matrices (algebraic aspects) (15B52)

Abstract: Starting from an n-by-n matrix of zeros, choose uniformly random zero entries and change them to ones, one-at-a-time, until the matrix becomes invertible. We show that with probability tending to one as n tends to infinity, this occurs at the very moment the last zero row or zero column disappears. We prove a related result for random symmetric Bernoulli matrices, and give quantitative bounds for some related problems. These results extend earlier work by Costello and Vu [arXiv:math/0606414].

Recommendations

• Hitting times and spectral gap inequalities
• Hitting times for random dynamical systems
• Limit theorems for random matrices
• scientific article; zbMATH DE number 1214059
• Asymptotics for hitting times
• Hitting probabilities of Gaussian random fields and collision of eigenvalues of random matrices
• The Hitting Time Theorem Revisited
• A theorem on random matrices and some applications
• scientific article; zbMATH DE number 4186741

Cites work

• Bilinear and quadratic variants on the Littlewood-Offord problem
• Hamilton cycles in random geometric graphs
• Hitting time results for maker-breaker games
• Invertibility of symmetric random matrices
• On singular values of matrices with independent rows
• On the rank of random sparse matrices
• On the singularity probability of discrete random matrices
• Positional games on random graphs
• Random symmetric matrices are almost surely nonsingular.
• The longest edge of the random minimal spanning tree
• The rank of random graphs

Cited in

(11)

• Hitting times and spectral gap inequalities
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• Recent progress in combinatorial random matrix theory
• An Elementary Proof of the Hitting Time Theorem
• Singularity of sparse random matrices: simple proofs
• Singularity of the \(k\)-core of a random graph
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• On the rank, kernel, and core of sparse random graphs
• The rank of sparse symmetric matrices over arbitrary fields
• Resolution of the quadratic Littlewood-Offord problem
• An upper bound on the smallest singular value of dense random combinatorial matrices

This page was built for publication: Hitting Time Theorems for Random Matrices

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