Some new results in random matrices over finite fields. (English) Zbl 1472.15044
Authors’ abstract: In this note, we give various characterizations of random walks with possibly different steps that have relatively large discrepancy from the uniform distribution modulo a prime \(p\), and use these results to study the distribution of the rank of random matrices over \(\mathbb{F}_p\) and the equi-distribution behavior of normal vectors of random hyperplanes. We also study the probability that a random square matrix is eigenvalue-free, or when its characteristic polynomial is divisible by a given irreducible polynomial in the limit \(n \to \infty\) in \(\mathbb{F}_p\). We show that these statistics are universal, extending results of R. Stong [Adv. Appl. Math. 9, No. 2, 167–199 (1988; Zbl 0681.05004)]
and P. M. Neumann and C. E. Praeger [J. Lond. Math. Soc., II. Ser. 58, No. 3, 564–586 (1999; Zbl 0936.15020); J. Algebra 234, No. 2, 367–418 (2000; Zbl 1020.20032)] beyond the uniform model.
Reviewer: Sistla Ragamayi (Khammam)
MSC:
| 15B52 | Random matrices (algebraic aspects) |
| 15B33 | Matrices over special rings (quaternions, finite fields, etc.) |
| 20G40 | Linear algebraic groups over finite fields |
References:
| [1] | G. V.Balakin, ‘The distribution of the rank of random matrices over a finite field (Russian, with English summary)’, Teor. Veroyatn. Primen.13 (1968) 631-641. · Zbl 0181.20102 |
| [2] | J.Blomer, R.Karp and E.Welzl, ‘The rank of sparse random matrices over finite fields’, Random Structures Algorithms10 (1997) 407-419. · Zbl 0877.15027 |
| [3] | J.Bourgain, V.Vu and P. M.Wood, ‘On the singularity probability of discrete random matrices’, J. Funct. Anal.258 (2010) 559-603. · Zbl 1186.60003 |
| [4] | R. P.Brent and B. D.McKay, ‘Determinants and ranks of random matrices over \(\mathbb{Z}_m\)’, Discrete Math.66 (1987) 35-49. · Zbl 0628.15010 |
| [5] | L. S.Charlap, H. D.Rees and D. P.Robbins, ‘The asymptotic prob‐ ability that a random biased matrix is invertible’, Discrete Math.82 (1990) 153-163. · Zbl 0721.15003 |
| [6] | J.Clancy, T.Leake, N.Kaplan, S.Payne and M. M.Wood, ‘On a Cohen‐Lenstra heuristic for Jacobians of random graphs’, J. Algebraic Combin.42 (2015) 701-723. · Zbl 1325.05146 |
| [7] | C.Cooper, ‘On the rank of random matrices’, Random Structures Algorithms16 (2000) 209-232. · Zbl 0953.15025 |
| [8] | K.Costello, T.Tao and V.Vu, ‘Random symmetric matrices are almost surely non‐singular’, Duke Math. J.135 (2006) 395-413. · Zbl 1110.15020 |
| [9] | A.Ferber, V.Jain, K.Luh and W.Samotij, ‘On the counting problem in inverse Littlewood-Offord theory’, J. Lond. Math. Soc., to appear. · Zbl 1470.60012 |
| [10] | N. J.Fine and I. N.Herstein, ‘The probability that a matrix be nilpotent’, Illinois J. Math.2 (1958) 499-508. · Zbl 0081.01504 |
| [11] | E.Friedman and L. C.Washington, ‘On the distribution of divisor class groups of curves over a finite field’, Theorie des nombres (eds J. M. deKoninck (ed.) and C.Levesque (ed.); de Gruyter, Berlin, 1989) 227-239. · Zbl 0693.12013 |
| [12] | J.Fulman, ‘Probability in the classical groups over finite fields: symmetric functions, stochastic algorithms and cycle indices’, PhD Thesis, Harvard University, Cambridge, MA, 1997. |
| [13] | J.Fulman, ‘Random matrix theory over finite fields’, Bull. Amer. Math. Soc.39 (2002) 51-85. · Zbl 0984.60017 |
| [14] | J.Fulman and L.Goldstein, ‘Stein’s method and the rank distribution of random matrices over finite fields’, Ann. Probab.43 (2015) 1274-1314. · Zbl 1388.60024 |
| [15] | G.Halász, ‘Estimates for the concentration function of combinatorial number theory and probability’, Period. Math. Hungar.8 (1977) 197-211. · Zbl 0336.10050 |
| [16] | J.Hansen and E.Schmutz, ‘How random is the characteristic polynomial of a random matrix?’, Math. Proc. Cambridge Philos. Soc.114 (1993) 507-515. · Zbl 0793.15013 |
| [17] | J.Kahn and J.Komlós, ‘Singularity probabilities for random matrices over finite fields’, Combin. Probab. Comput.10 (2001) 137-157. · Zbl 0979.15022 |
| [18] | J.Kahn, J.Komlós and E.Szemerédi, ‘On the probability that a random \(\pm 1\) matrix is singular’, J. Amer. Math. Soc.8 (1995) 223-240. · Zbl 0829.15018 |
| [19] | I. N.Kovalenko and A. A.Levitskaya, ‘Limiting behavior of the number of solutions of a system of random linear equations over a finite field and a finite ring (Russian)’, Dokl. Akad. Nauk SSSR221 (1975) 778-781. |
| [20] | I. N.Kovalenko, A. A.Levitskaya and M. N.Savchuk, Izbrannye zadachi veroyatnostnoi kombinatoriki (Russian), (Naukova Dumka, Kiev, 1986). |
| [21] | M. V.Kozlov, ‘On the rank of matrices with random Boolean elements’, Sov. Math. Dokl.7 (1966) 1048-1051. · Zbl 0171.38702 |
| [22] | J.Kung, ‘The cycle structure of a linear transformation over a finite field’, Linear Algebra Appl.36 (1981) 141-155. · Zbl 0477.05008 |
| [23] | K.Maples, ‘Singularity of random matrices over finite fields’, Preprint, 2010, arXiv.org/abs/1012.2372. |
| [24] | K.Maples, ‘Cokernels of random matrices satisfy the Cohen‐Lenstra heuristics’, Preprint, 2013, arXiv.org/abs/1301.1239. |
| [25] | P. M.Neumann and C. E.Praeger, ‘Derangements and eigenvalue‐free elements in finite classical groups’, J. Lond. Math. Soc. (2)58 (1998) 562-586. · Zbl 0936.15020 |
| [26] | P. M.Neumann and C. E.Praeger, ‘Cyclic matrices in classical groups over finite fields’, J. Algebra234 (2000) 367-418. · Zbl 1020.20032 |
| [27] | H.Nguyen and E.Paquette, ‘Surjectivity of near square matrices’, Combin.Probab. Comput.29 (2020) 267-292. · Zbl 1467.60011 |
| [28] | H.Nguyen and V.Vu, ‘Optimal inverse Littlewood‐Offord theorems’, Adv. Math.226 (2011) 5298-5319. · Zbl 1268.11020 |
| [29] | H.Nguyen and V.Vu, ‘Normal vector of a random hyperplane’, Int. Math. Res. Not. (2018) 1754-1778. · Zbl 1405.15005 |
| [30] | H.Nguyen and M. M.Wood, ‘Random integral matrices: universality of surjectivity and the cokernel’, Preprint, 2018, arXiv:1806.00596. |
| [31] | M.Rudelson and R.Vershynin, ‘The Littlewood‐Offord problem and invertibility of random matrices’, Adv. Math.218 (2008) 600-633. · Zbl 1139.15015 |
| [32] | M.Rudelson and R.Vershynin, ‘Smallest singular value of a random rectangular matrix’, Comm. Pure Appl. Math.62 (2009) 1707-1739. · Zbl 1183.15031 |
| [33] | R.Stanley, ‘Smith normal form in combinatorics’, J. Combin. Theory Ser. A144 (2016) 476-495. · Zbl 1343.05026 |
| [34] | R.Stanley and Y.Wang, ‘The Smith normal form distribution of a random integer matrix’, SIAM J. Discrete Math.31 (2017) 2247-2268. · Zbl 1372.05006 |
| [35] | R.Stong, ‘Some asymptotic results on finite vector spaces’, Adv. Appl. Math.9 (1988) 167-199. · Zbl 0681.05004 |
| [36] | T.Tao and V.Vu, Additive combinatorics, vol. 105 (Cambridge University Press, Cambridge, 2006). · Zbl 1127.11002 |
| [37] | T.Tao and V.Vu, ‘On the singularity probability of random Bernoulli matrices’, J. Amer. Math. Soc.20 (2007) 603-673. · Zbl 1116.15021 |
| [38] | T.Tao and V.Vu, ‘John‐type theorems for generalized arithmetic progressions and iterated sumsets’, Adv. Math.219 (2008) 428-449. · Zbl 1165.11016 |
| [39] | T.Tao and V.Vu, ‘Inverse Littlewood‐Offord theorems and the condition number of random matrices’, Ann. of Math. (2)169 (2009) 595-632. · Zbl 1250.60023 |
| [40] | R.Vershynin, ‘Invertibility of symmetric random matrices’, Random Structures Algorithms44 (2014) 135-182. · Zbl 1291.15088 |
| [41] | M. M.Wood, ‘The distribution of sandpile groups of random graphs’, J. Amer. Math. Soc.30 (2017) 915-958. · Zbl 1366.05098 |
| [42] | M. M.Wood, ‘Random integral matrices and the Cohen‐Lenstra Heuristics’, Amer. J. Math., to appear. · Zbl 1446.11170 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
