Article contents
Hitting Time Theorems for Random Matrices
Published online by Cambridge University Press: 09 July 2014
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 → ∞, 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 [10].
Keywords
- Type
- Paper
- Information
- Combinatorics, Probability and Computing , Volume 23 , Issue 5: Honouring the Memory of Philippe Flajolet - Part 1 , September 2014 , pp. 635 - 669
- Copyright
- Copyright © Cambridge University Press 2014
References
- 6
- Cited by