Hitting Time Theorems for Random Matrices. (September 2014)

• Record Type: Journal Article
• Authors: ADDARIO-BERRY, LOUIGI; ESLAVA, LAURA; Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 5(2014:Sep.)
• Page Start: 635
• Page End: 669
• Publication Date: 2014-09
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000285
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>Starting from an <italic>n</italic>-by-<italic>n</italic> 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 <italic>n</italic> → ∞, 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].</p> </abstract>