Non-asymptotic bounds for probabilities of the rank of a~random matrix over a~finite field

A. N. Alekseichuk

Diskretnaya Matematika, Tome 19 (2007) no. 2, pp. 85-93

Résumé

We consider a random $(n+s)\times n$ matrix $A$ with independent rows over a field of $q$ elements. In terms of the Fourier coefficients of distributions of the rows of this matrix we obtain expressions of upper and (in the case where the Fourier coefficients are non-negative quantities) lower bounds for probabilities of values of its rank. We find an upper bound for the distance in variation between the distributions of ranks of the matrix $A$ and a random equiprobable matrix. We present a condition for this distance to tend to zero as $n\to\infty$ and $s$ is fixed and demonstrate that this condition, in some natural sense, cannot be weakened.