Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-09T09:34:12.364Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Rank of Random Sparse Matrices

Published online by Cambridge University Press:  12 October 2009

KEVIN P. COSTELLO  and
VAN VU
KEVIN P. COSTELLO
Affiliation:
Department of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail kcostell@math.gatech.edu)
VAN VU
Affiliation:
Department of Mathematics, Rutgers, Piscataway, NJ 08854, USA (e-mail vanvu@math.rutgers.edu)
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.

We investigate the rank of random (symmetric) sparse matrices. Our main finding is that with high probability, any dependency that occurs in such a matrix is formed by a set of few rows that contains an overwhelming number of zeros. This allows us to obtain an exact estimate for the co-rank.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 3 , May 2010 , pp. 321 - 342
Copyright
Copyright © Cambridge University Press 2009

References

[1]Costello, K., Tao, T. and Vu, V. (2006) Random symmetric matrices are almost surely non-singular. Duke Math J. 135 395–413.CrossRefGoogle Scholar
[2]Costello, K. and Vu, V. (2008) The rank of random graphs. Random Struct. Alg. 33 269–285.CrossRefGoogle Scholar
[3]Erdős, P. (1945) On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc. 51 898–902.CrossRefGoogle Scholar
[4]Halász, G. (1977) Estimates for the concentration function of combinatorial number theory and probability. Period. Math. Hungar. 8 197–211.CrossRefGoogle Scholar
[5]Komlós, J. (1967) On the determinant of (0, 1) matrices. Studia Sci. Math. Hungar. 2 7–22.Google Scholar
[6]Vu, V. (2007) Random discrete matrices. In Horizons of Combinatorics, Springer, Berlin, pp. 257–280.Google Scholar