{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T06:22:57Z","timestamp":1772605377284,"version":"3.50.1"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2014,7,9]],"date-time":"2014-07-09T00:00:00Z","timestamp":1404864000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2014,9]]},"abstract":"<jats:p>Starting from an<jats:italic>n<\/jats:italic>-by-<jats:italic>n<\/jats: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<jats:italic>n<\/jats:italic>\u2192 \u221e, 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].<\/jats:p>","DOI":"10.1017\/s0963548314000285","type":"journal-article","created":{"date-parts":[[2014,7,9]],"date-time":"2014-07-09T13:37:12Z","timestamp":1404913032000},"page":"635-669","source":"Crossref","is-referenced-by-count":7,"title":["Hitting Time Theorems for Random Matrices"],"prefix":"10.1017","volume":"23","author":[{"given":"LOUIGI","family":"ADDARIO-BERRY","sequence":"first","affiliation":[]},{"given":"LAURA","family":"ESLAVA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,7,9]]},"reference":[{"key":"S0963548314000285_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20219"},{"key":"S0963548314000285_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20059"},{"key":"S0963548314000285_ref17","volume-title":"Cambridge Series in Statistical and Probabilistic Mathematics","author":"Norris","year":"1998"},{"key":"S0963548314000285_ref13","first-page":"7","article-title":"On the determinant of (0, 1) matrices.","volume":"2","author":"Koml\u00f3s","year":"1967","journal-title":"Studia Sci. Math. Hungar"},{"key":"S0963548314000285_ref2","doi-asserted-by":"publisher","DOI":"10.1214\/10-AAP718"},{"key":"S0963548314000285_ref5","first-page":"47","volume-title":"Random graphs '83","author":"Bollob\u00e1s","year":"1985"},{"key":"S0963548314000285_ref1","first-page":"173","volume-title":"Cycles in Graphs: Burnaby, BC, 1982","author":"Ajtai","year":"1985"},{"key":"S0963548314000285_ref22","doi-asserted-by":"crossref","unstructured":"Tao T. and Vu V. H. (2005) On random \u00b1 matrices: Singularity and determinant. In STOC'05: Proc. 37th Annual ACM Symposium on Theory of Computing, ACM, pp. 431\u2013440.","DOI":"10.1145\/1060590.1060655"},{"key":"S0963548314000285_ref26","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20429"},{"key":"S0963548314000285_ref11","first-page":"67","article-title":"Universality of Wigner random matrices: A survey of recent results.","volume":"66","author":"Erd\u0151s","year":"2011","journal-title":"Uspekhi Mat. Nauk"},{"key":"S0963548314000285_ref14","first-page":"335","article-title":"Random matrices I: Combinatorial problems.","volume":"35","author":"Linh","year":"2010","journal-title":"Acta Math. Vietnam."},{"key":"S0963548314000285_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990447"},{"key":"S0963548314000285_ref15","first-page":"1","article-title":"Concentration","author":"McDiarmid","year":"1998","journal-title":"Probabilistic Methods for Algorithmic Discrete Mathematics"},{"key":"S0963548314000285_ref16","doi-asserted-by":"publisher","DOI":"10.3150\/bj\/1161614945"},{"key":"S0963548314000285_ref19","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1214\/aoap\/1034625335","article-title":"The longest edge of the random minimal spanning tree.","volume":"7","author":"Penrose","year":"1997","journal-title":"Ann. Appl. Probab."},{"key":"S0963548314000285_ref20","unstructured":"Rudelson M. and Vershynin R. (2010) Non-asymptotic theory of random matrices: Extreme singular values. In Proc. International Congress of Mathematicians, Vol. III, Hindustan Book Agency, pp. 1576\u20131602."},{"key":"S0963548314000285_ref23","unstructured":"Tao T. and Vu V. H. (2007) The condition number of a randomly perturbed matrix. In Proc. 39th Annual ACM Symposium on Theory of Computing: STOC '07 ( D. S. Johnson and U. Feige , eds), ACM, pp. 248\u2013255."},{"key":"S0963548314000285_ref18","volume-title":"Oxford Studies in Probability","author":"Penrose","year":"2003"},{"key":"S0963548314000285_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-012-0082-4"},{"key":"S0963548314000285_ref24","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.169.595"},{"key":"S0963548314000285_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20392"},{"key":"S0963548314000285_ref25","unstructured":"Tao T. and Vu V. H. (2012) Random matrices: The universality phenomenon for Wigner ensembles. arXiv:1202.0068"},{"key":"S0963548314000285_ref4","first-page":"23","volume-title":"Random Graphs '83","author":"Bollob\u00e1s","year":"1985"},{"key":"S0963548314000285_ref12","doi-asserted-by":"crossref","unstructured":"Janson S. , Luczak T. and Ruci\u0144ski A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization.","DOI":"10.1002\/9781118032718"},{"key":"S0963548314000285_ref8","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-06-13527-5"},{"key":"S0963548314000285_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2009.04.016"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T15:55:22Z","timestamp":1565625322000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000285\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,9]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["S0963548314000285"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000285","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,9]]}}}