Publication Details
Title: The Rank of Sparse Random Matrices Over Finite Fields
Author: J. Blömer, R. Karp, and E. Welzl
Group: ICSI Technical Reports
Date: January 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-004.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-96-004
Bibliographic Reference:
J. Blömer, R. Karp, and E. Welzl. The Rank of Sparse Random Matrices Over Finite Fields. ICSI Technical Report TR-96-004, January 1996
Author: J. Blömer, R. Karp, and E. Welzl
Group: ICSI Technical Reports
Date: January 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-004.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-96-004
Bibliographic Reference:
J. Blömer, R. Karp, and E. Welzl. The Rank of Sparse Random Matrices Over Finite Fields. ICSI Technical Report TR-96-004, January 1996