Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T20:25:43.148Z 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 [email protected])
VAN VU
Affiliation:
Department of Mathematics, Rutgers, Piscataway, NJ 08854, USA (e-mail [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

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]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