Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-28T16:16:17.875Z Has data issue: false hasContentIssue false
  • English
  • Français

Hitting Time Theorems for Random Matrices

Published online by Cambridge University Press:  09 July 2014

LOUIGI ADDARIO-BERRY  and
LAURA ESLAVA
LOUIGI ADDARIO-BERRY
Affiliation:
Department of Mathematics and Statistics, McGill University (e-mail: [email protected], [email protected])
LAURA ESLAVA
Affiliation:
Department of Mathematics and Statistics, McGill University (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

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

Primary 15A52Secondary 15A1505C80
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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Ajtai, M., Komlós, J. and Szemerédi, E. (1985) First occurrence of Hamilton cycles in random graphs. In Cycles in Graphs: Burnaby, BC, 1982, Vol. 115 of North-Holland Mathematics Studies, North-Holland, pp. 173–178.Google Scholar
[2]Balogh, J., Bollobás, B., Krivelevich, M., Müller, T. and Walters, M. (2011) Hamilton cycles in random geometric graphs. Ann. Appl. Probab. 21 1053–1072.CrossRefGoogle Scholar
[3]Ben-Shimon, S., Ferber, A., Hefetz, D. and Krivelevich, M. (2012) Hitting time results for maker–breaker games. Random Struct. Alg. 41 23–46.CrossRefGoogle Scholar
[4]Bollobás, B. and Frieze, A. M. (1985) On matchings and Hamiltonian cycles in random graphs. In Random Graphs '83, Vol. 118 of North-Holland Mathematics Studies, North-Holland, pp. 23–46.Google Scholar
[5]Bollobás, B. and Thomason, A. (1985) Random graphs of small order. In Random graphs '83, Vol. 118 of North-Holland Mathematics Studies, North-Holland, pp. 47–97.Google Scholar
[6]Bourgain, J., Vu, V. H. and Wood, P. M. (2010) On the singularity probability of discrete random matrices. J. Funct. Anal. 258 559–603.CrossRefGoogle Scholar
[7]Costello, K. P. (2013) Bilinear and quadratic variants on the Littlewood–Offord problem. Israel J. Math. 194 359–394.CrossRefGoogle Scholar
[8]Costello, K. P., Tao, T. and Vu, V. H. (2006) Random symmetric matrices are almost surely nonsingular. Duke Math. J. 135 395–413.CrossRefGoogle Scholar
[9]Costello, K. P. and Vu, V. H. (2010) On the rank of random sparse matrices. Combin. Probab. Comput. 19 321–342.CrossRefGoogle Scholar
[10]Costello, K. P and Vu, V. H. (2008) The rank of random graphs. Random Struct. Alg. 33 269–285.CrossRefGoogle Scholar
[11]Erdős, L. (2011) Universality of Wigner random matrices: A survey of recent results. Uspekhi Mat. Nauk 66 67–198.Google Scholar
[12]Janson, S., Luczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization.Google Scholar
[13]Komlós, J. (1967) On the determinant of (0, 1) matrices. Studia Sci. Math. Hungar 2 7–21.Google Scholar
[14]Linh, T. V. and Vu, V. H. (2010) Random matrices I: Combinatorial problems. Acta Math. Vietnam. 35 335–354.Google Scholar
[15]McDiarmid, C. (1998) Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 1–46.Google Scholar
[16]Mendelson, S. and Pajor, A. (2006) On singular values of matrices with independent rows. Bernoulli 12 761–773.CrossRefGoogle Scholar
[17]Norris, J. R. (1998) Markov Chains, Vol. 2 of Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press. Reprint of 1997 original.Google Scholar
[18]Penrose, M. (2003) Random Geometric Graphs, Vol. 5 of Oxford Studies in Probability, Oxford University Press.Google Scholar
[19]Penrose, M. D. (1997) The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7 340–361.CrossRefGoogle Scholar
[20]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–1602.Google Scholar
[21]Stojaković, M. and Szabó, T. (2005) Positional games on random graphs. Random Struct. Alg. 26 204–223.CrossRefGoogle Scholar
[22]Tao, T. and Vu, V. H. (2005) On random ± matrices: Singularity and determinant. In STOC'05: Proc. 37th Annual ACM Symposium on Theory of Computing, ACM, pp. 431–440.CrossRefGoogle Scholar
[23]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 (Johnson, D. S. and Feige, U., eds), ACM, pp. 248–255.Google Scholar
[24]Tao, T. and Vu, V. H. (2009) Inverse Littlewood–Offord theorems and the condition number of random discrete matrices. Ann. of Math. (2) 169595–632.CrossRefGoogle Scholar
[25]Tao, T. and Vu, V. H. (2012) Random matrices: The universality phenomenon for Wigner ensembles. arXiv:1202.0068Google Scholar
[26]Vershynin, R. (2014) Invertibility of symmetric random matrices. Random Struct. Alg. 44 (2), 135–182.CrossRefGoogle Scholar