×

Stein’s method and the rank distribution of random matrices over finite fields. (English) Zbl 1388.60024

Summary: With \(\mathcal{Q}_{q,n}\) the distribution of \(n\) minus the rank of a matrix chosen uniformly from the collection of all \(n\times(n+m)\) matrices over the finite field \(\mathbb{F}_{q}\) of size \(q\geq2\), and \(\mathcal{Q}_{q}\) the distributional limit of \(\mathcal{Q}_{q,n}\) as \(n\to\infty\), we apply Stein’s method to prove the total variation bound \[ \frac{1}{8q^{n+m+1}}\leq\parallel\mathcal{Q}_{q,n}-\mathcal{Q}_{q}\parallel_{\mathrm{TV}}\leq\frac{3}{q^{n+m+1}}. \] In addition, we obtain similar sharp results for the rank distributions of symmetric, symmetric with zero diagonal, skew symmetric, skew centrosymmetric and Hermitian matrices.

MSC:

60B20 Random matrices (probabilistic aspects)
15B52 Random matrices (algebraic aspects)
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Andrews, G. E. (1998). The Theory of Partitions . Cambridge Univ. Press, Cambridge. · Zbl 0996.11002
[2] Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation . Oxford Univ. Press, New York. · Zbl 0746.60002
[3] Belsley, E. D. (1993). Rates of convergence of Markov chains related to association schemes. Ph.D. thesis, Harvard Univ.
[4] Blake, I. and Studholme, C. (2006). Properties of random matrices and applications. Preprint. Available at . · Zbl 1235.94081
[5] Blömer, J., Karp, R. and Welzl, E. (1997). The rank of sparse random matrices over finite fields. Random Structures Algorithms 10 407-419. · Zbl 0877.15027
[6] Bressoud, D. M. (1999). Proofs and Confirmations. The Story of the Alternating Sign Matrix Conjecture . Mathematical Association of America, Washington, DC. · Zbl 0944.05001
[7] Carlitz, L. (1954). Representations by quadratic forms in a finite field. Duke Math. J. 21 123-137. · Zbl 0055.01301
[8] Carlitz, L. (1954). Representations by skew forms in a finite field. Arch. Math. ( Basel ) 5 19-31. · Zbl 0056.01702
[9] Carlitz, L. and Hodges, J. H. (1955). Representations by Hermitian forms in a finite field. Duke Math. J. 22 393-405. · Zbl 0065.24805
[10] Charlap, L. S., Rees, H. D. and Robbins, D. P. (1990). The asymptotic probability that a random biased matrix is invertible. Discrete Math. 82 153-163. · Zbl 0721.15003
[11] Chen, L. H. Y., Goldstein, L. and Shao, Q. M. (2010). Stein’s Method for Normal Approximation . Springer, Heidelberg. · Zbl 1213.62027
[12] Cooper, C. (2000). On the rank of random matrices. Random Structures Algorithms 16 209-232. · Zbl 0953.15025
[13] Cooper, C. (2000). On the distribution of rank of a random matrix over a finite field. In Proceedings of the Ninth International Conference “Random Structures and Algorithms” ( Poznan , 1999) 197-212. · Zbl 0966.60018
[14] Derfel, G., Gordon, A. Y. and Molchanov, S. (2004). Random matrices over \(Z_{p}\) and testing of random number generators (RNG’s). Random Oper. Stoch. Equ. 12 1-10. · Zbl 1091.15029
[15] Fulman, J. (1997). Probability in the classical groups over finite fields. Ph.D. thesis, Harvard Univ.
[16] Fulman, J. (1999). Cycle indices for the finite classical groups. J. Group Theory 2 251-289. · Zbl 0943.20048
[17] Fulman, J. (2002). Random matrix theory over finite fields. Bull. Amer. Math. Soc. ( N.S. ) 39 51-85. · Zbl 0984.60017
[18] Goldstein, L. and Reinert, G. (2013). Stein’s method for the Beta distribution and the Pólya-Eggenberger urn. J. Appl. Probab. 50 1187-1205. · Zbl 1304.60033
[19] Holmes, S. (2004). Stein’s method for birth and death chains. In Stein’s Method : Expository Lectures and Applications (P. Diaconis and S. Holmes, eds.) 45-67. IMS, Beachwood, OH.
[20] Kahn, J. and Komlós, J. (2001). Singularity probabilities for random matrices over finite fields. Combin. Probab. Comput. 10 137-157. · Zbl 0979.15022
[21] Ley, C. and Swan, Y. (2011). Discrete Stein characterizations and discrete information distances. Preprint. Available at . arXiv:1201.0143v1
[22] MacWilliams, J. (1969). Orthogonal matrices over finite fields. Amer. Math. Monthly 76 152-164. · Zbl 0186.33702
[23] MacWilliams, J. and Sloane, N. (1997). The Theory of Error-Correcting Codes , 3rd ed. North-Holland, Amsterdam. · Zbl 0369.94008
[24] Malle, G. (2010). On the distribution of class groups of number fields. Experiment. Math. 19 465-474. · Zbl 1297.11139
[25] Neumann, P. M. and Praeger, C. E. (1995). Cyclic matrices over finite fields. J. Lond. Math. Soc. (2) 52 263-284. · Zbl 0839.15011
[26] Rudvalis, A. and Shinoda, K. (1998). An enumeration in finite classical groups. Technical report, Dept. of Mathematics, Univ. Mass. Amherst.
[27] Shinoda, K.-i. (1992). Identities of Euler and finite classical groups. In Proceedings of Asian Mathematical Conference , 1990 ( Hong Kong , 1990) 423-427. World Sci. Publ., River Edge, NJ. · Zbl 0940.05507
[28] Stein, C. (1986). Approximate Computation of Expectations. Institute of Mathematical Statistics Lecture Notes-Monograph Series 7 . IMS, Hayward, CA. · Zbl 0721.60016
[29] Stong, R. (1988). Some asymptotic results on finite vector spaces. Adv. in Appl. Math. 9 167-199. · Zbl 0681.05004
[30] Swinnerton-Dyer, P. (2008). The effect of twisting on the 2-Selmer group. Math. Proc. Cambridge Philos. Soc. 145 513-526. · Zbl 1242.11041
[31] van Lint, J. H. and Wilson, R. M. (2001). A Course in Combinatorics , 2nd ed. Cambridge Univ. Press, Cambridge. · Zbl 0980.05001
[32] Washington, L. C. (1986). Some remarks on Cohen-Lenstra heuristics. Math. Comp. 47 741-747. · Zbl 0627.12002
[33] Waterhouse, W. C. (1998). On the ranks of skew centrosymmetric matrices over finite fields. Finite Fields Appl. 4 98-100. · Zbl 0909.15006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.