The Rank of Sparse Random Matrices Over Finite Fields

TitleThe Rank of Sparse Random Matrices Over Finite Fields
Publication TypeTechnical Report
Year of Publication1996
AuthorsBlömer, J., Karp R. M., & Welzl E.
Other Numbers1014
Abstract

Let M be a random matrix over GF[q] such that for each entry M_ij in M and for each non-zero field element w the probability Pr[M_i} = ?] is p/(q-1), where p = (log(n)-c)/n and c is an arbitrary but fixed positive constant. The probability for a matrix entry to be zero is 1-p. It is shown that the expected rank of M is n-O(1). Furthermore, there is a constant A such that the probability that the rank is less than n-k is less than A/q^k. It is also shown that if c grows depending on n and is unbounded as n goes to infinity then the expected difference between the rank of M and n is unbounded.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-004.pdf
Bibliographic Notes

ICSI Technical Report TR-96-004

Abbreviated Authors

J. Blömer, R. Karp, and E. Welzl

ICSI Publication Type

Technical Report