Series expansion for the probability that a random Boolean matrix is of maximal rank
Author:
V. V. Masol
Translated by:
V. Semenov
Journal:
Theor. Probability and Math. Statist. 70 (2005), 93-104
MSC (2000):
Primary 60C05, 15A52, 15A03
DOI:
https://doi.org/10.1090/S0094-9000-05-00633-2
Published electronically:
August 5, 2005
MathSciNet review:
2109823
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We consider a random $(N\times n)$ matrix in the field $GF(2)$ and establish relations that allow one to find the coefficients of the expansion of the probability that a given matrix is of maximal rank into a series in powers of a small parameter. We give explicit formulas for the cases of $n=1$ and $n=2$, $N\geq n$.
References
- V. V. Masol, An expansion in a small parameter of the probability that a random determinant in the field ${\rm GF}(2)$ is equal to one, Teor. Ĭmovīr. Mat. Stat. 64 (2001), 102–105 (Ukrainian, with Ukrainian summary); English transl., Theory Probab. Math. Statist. 64 (2002), 117–121. MR 1922957
- V. V. Masol, Explicit representation of some coefficients in the expansion of the random matrix rank distribution in the field $GF(2)$, Theory Stoch. Process. 6(22) (2000), no. 3–4, 122–126.
- V. V. Masol, Expansion in terms of powers of small parameter of the maximum rank distribution of a random Boolean matrix, Kibernetika i Sistemnyi Analiz 38 (2002), no. 6, 176–180; English transl. in Cybernetics and Systems Analysis 38 (2003), no. 6, 938–942.
- I. N. Kovalenko, Invariance theorems for random Boolean matrices, Kibernetika (Kiev) 5 (1975), 138–152 (Russian, with English summary). MR 458552
- A. A. Levit⋅skaya, Invariance theorems for a system of random linear equations over an arbitrary finite ring, Dokl. Akad. Nauk SSSR 263 (1982), no. 2, 289–291 (Russian). MR 650154
- C. Cooper, On the rank of random matrices, Random Structures Algorithms 16 (2000), no. 2, 209–232. MR 1742352, DOI https://doi.org/10.1002/%28SICI%291098-2418%28200003%2916%3A2%3C209%3A%3AAID-RSA6%3E3.3.CO%3B2-T
References
- V. V. Masol, An expansion in a small parameter of the probability that a random determinant in the field $GF(2)$ is 1, Teor. Imovirnost. Mat. Stat. 64 (2001), 102–105; English transl. in Theor. Probability Math. Statist. 64 (2002), 117–121. MR 1922957 (2003g:60015)
- V. V. Masol, Explicit representation of some coefficients in the expansion of the random matrix rank distribution in the field $GF(2)$, Theory Stoch. Process. 6(22) (2000), no. 3–4, 122–126.
- V. V. Masol, Expansion in terms of powers of small parameter of the maximum rank distribution of a random Boolean matrix, Kibernetika i Sistemnyi Analiz 38 (2002), no. 6, 176–180; English transl. in Cybernetics and Systems Analysis 38 (2003), no. 6, 938–942.
- I. N. Kovalenko, Invariance theorems for random Boolean matrices Kibernetika 11 (1975), no. 5, 138–152; English transl. in Cybernetics 11 (1976), no. 5, 818–834. MR 0458552 (56:16752)
- A. A. Levitskaya, Invariance theorems for a system of random linear equations over an arbitrary finite ring, Dokl. AN SSSR 263 (1982), no. 2, 289–291; English transl. in Soviet Math. Dokl. 25 (1982), 340–342. MR 0650154 (83g:60046)
- C. Cooper, On the rank of random matrices, Random Structures and Algorithms 16 (2000), no. 2, 209–232. MR 1742352 (2000k:15050)
Similar Articles
Retrieve articles in Theory of Probability and Mathematical Statistics
with MSC (2000):
60C05,
15A52,
15A03
Retrieve articles in all journals
with MSC (2000):
60C05,
15A52,
15A03
Additional Information
V. V. Masol
Affiliation:
Department of Probability Theory and Mathematical Statistics, Mechanics and Mathematics Faculty, National Taras Shevchenko University, Academician Glushkov Avenue 6, Kyiv 03127, Ukraine
Email:
vicamasol@pochtamt.ru
Received by editor(s):
April 15, 2003
Published electronically:
August 5, 2005
Article copyright:
© Copyright 2005
American Mathematical Society