THE RANK OF SPARSE RANDOM MATRICES OVER FINITE-FIELDS

Let M be a random (n x n)-matrix over GF[q] such that for each entry M -ij in M and for each nonzero field element alpha the probability Pr[M -ij = alpha] is p/(q - 1), where p = (log n - c)/n and c is an arbitra ry 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 t he expected difference between the rank of nrl and n is unbounded. (C) 1997 John Wiley & Sons, Inc.