Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-06T19:11:20.722Z 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: louigi@math.mcgill.ca, laura.eslavafernandez@mail.mcgill.ca)
LAURA ESLAVA
Affiliation:
Department of Mathematics and Statistics, McGill University (e-mail: louigi@math.mcgill.ca, laura.eslavafernandez@mail.mcgill.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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