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.

Bibliographie

[1] Levitskaya A. A., “Sistemy sluchainykh uravnenii nad konechnymi algebraicheskimi strukturami”, Kibernetika i sistemnyi analiz, 41:1 (2005), 82–116 | MR | Zbl

[2] Masol V. V., “Explicit representation of some coefficients in the expansion of the random matrix rank distribution in the field $GF(2)$”, Theory Stoch. Process., 6(22):3–4 (2000), 122–126 | Zbl

[3] Masol V. V., “Razlozhenie po stepenyam malogo parametra raspredeleniya maksimalnogo ranga sluchainoi bulevoi matritsy”, Kibernetika i sistemnyi analiz, 38:6 (2002), 176–180 | Zbl

[4] Balakin G. V., “Sistemy sluchainykh uravnenii nad konechnym polem”, Trudy po diskretnoi matematike, 2 (1998), 21–37 | MR | Zbl

[5] Lidl R., Niderraiter G., Konechnye polya, t. 1, 2, Mir, Moskva, 1988 | Zbl

[6] Marshall A., Olkin I., Neravenstva: teoriya mazhorizatsii i ee prilozheniya, Mir, Moskva, 1983 | MR | Zbl