This article is cited in 2 papers

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

A. N. Alekseichuk


Abstract: 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.

UDC: 519.21

Received: 28.09.2005

DOI: 10.4213/dm23

 English version: Discrete Mathematics and Applications, 2007, 17:3, 269–278

Bibliographic databases:

• 
• 
• 
•