Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Random matrix theory over finite fields


Author: Jason Fulman
Journal: Bull. Amer. Math. Soc. 39 (2002), 51-85
MSC (2000): Primary 60B15, 20G40
DOI: https://doi.org/10.1090/S0273-0979-01-00920-X
Published electronically: October 5, 2001
MathSciNet review: 1864086
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The first part of this paper surveys generating functions methods in the study of random matrices over finite fields, explaining how they arose from theoretical need. Then we describe a probabilistic picture of conjugacy classes of the finite classical groups. Connections are made with symmetric function theory, Markov chains, Rogers-Ramanujan type identities, potential theory, and various measures on partitions.


References [Enhancements On Off] (What's this?)

  • [AlDia] Aldous, D. and Diaconis, P., Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. AMS (N.S.) 36 (1999), 413-432. MR 2000g:60013
  • [A1] Andrews, G., The theory of partitions. Encyclopedia of Mathematics and its Applications, Vol. 2. Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. MR 58:27738
  • [A2] Andrews, G., $q$-Series: Their development and application in analysis, number theory, combinatorics, physics, and computer algebra. American Math Society, 1986. MR 88b:11063
  • [A3] Andrews, G., Multiple series Rogers-Ramanujan type identities, Pacific J. Math. 114 (1984), 267-283. MR 86c:11084
  • [A4] Andrews, G., On the proofs of the Rogers-Ramanujan identities, in $q$-series and partitions, IMA Vol. Math. Appl. 18, 1989. MR 91e:11112
  • [ArBarT] Arratia, R., Barbour, A.D., and Tavare, S., On random polynomials over finite fields, Math. Proc. Cambridge Phil. Soc. 114 (1993), 347-368. MR 95a:60011
  • [As] Aschbacher, M., On the maximal subgroups of the finite classical groups, Invent. Math. 76 (1984), 469-514. MR 86a:20054
  • [Bai] Bailey, W.N., Identities of the Rogers-Ramanujan type, Proc. London Math. Soc. (2) 50 (1948), 1-10. MR 9:585b
  • [Bax1] Baxter, R., Exactly solved models in statistical mechanics, Academic Press, London/New York, 1982. MR 86i:82002a
  • [Bax2] Baxter, R., Ramanujan's identities in statistical mechanics, in Ramanujan revisited (1988), 69-84. MR 89h:82043
  • [BlO] Bloch, S. and Okounkov, A., The character of the infinite wedge representation, Adv. Math. 149 (2000), 1-60. MR 2001g:11059
  • [BKW] Bl$\ddot{o}$mer, J., Karp, R., and Welzl, E., The rank of sparse random matrices over finite fields, Random Structures Algorithms 10 (1997) 407-419. MR 99b:15028
  • [Bo] Bollobas, B., Random graphs, Academic Press, London, 1985. MR 87f:05152
  • [B] Borodin, A., The law of large numbers and the central limit theorem for the Jordan normal form of large triangular matrices over a finite field, Zap. Nauchn. Sem. LOMI, Vol. 240, 1997, pg. 18-43 (Russian); English translation in J. Math. Sci. (New York) 96 (1997), 3455-3471. MR 2000f:60044
  • [BOOl] Borodin, A., Okounkov, A., and Olshanki, G., Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000), 481-515. MR 2001g:05103
  • [BOl] Borodin, A. and Ohlshanski, G., Harmonic functions on multiplicitive graphs and interpolation polynomials, Electron. J. Combin. 7 (2000), 39 pp. MR 2001f:05160
  • [CeLg] Celler, F. and Leedham-Green, C.R., A constructive recognition algorithm for the special linear group, in The atlas of finite groups: ten years on (Birmingham, 1995), London Math. Soc. Lecture Note Ser., 249, Cambridge Univ. Press (1998), 11-26. MR 99g:20001
  • [CeLgMuNiOb] Celler, F., Leedham-Green, C.R., Murray, S.H., Niemeyer, A.C., and O'Brien, E.A., Generating random elements of a finite group, Commun. in Algebra 23 (1995), 4931-4948. MR 96h:20115
  • [ChReRo] Charlap, L., Rees, H., and Robbins, D., The asymptotic probability that a random biased matrix is invertible, Discrete Math. 82 (1990), 153-163. MR 91g:05009
  • [CTY] Chigira, N., Takegahara, Y., and Yoshida, T., On the number of homomorphisms from a finite group to a general linear group, J. Algebra 232 (2000), 236-254. MR 2001h:20069
  • [DiaGr] Diaconis, P. and Graham, R., An affine walk on the hypercube, J. Comput. Appl. Math. 41 (1992), 215-235.
  • [DiaMcPi] Diaconis, P., McGrath, M., and Pitman, J., Riffle shuffle, cycles, and descents, Combinatorica 15 (1995), 11-29. MR 96g:05009
  • [Dij] Dijkgraaf, R., Mirror symmetry and elliptic curves, in The Moduli Space of Curves, Prog. in Math. 129 (1995). MR 96m:14072
  • [Ed] Edelman, A., Eigenvalues and condition numbers of random matrices, Ph.D. Thesis, MIT, 1989.
  • [El] Elkies, N., On finite sequences satisfying linear recursions. Available at http://xxx.lanl.gov/abs/math.CO/0105007.
  • [ErT] Erd$\ddot{o}$s, P. and Turan, P., On some problems of statistical group theory. I, Zeit. Wahr. Verw. Gabiete 4 (1965), 175-186. MR 32:2465
  • [Ew] Ewens, W.J., The sampling theory of selectively neutral alleles, Theoret. Population Biology 3 (1972), 87-112. MR 48:3526
  • [FeigFre] Feigin, B. and Frenkel, E., Coinvariants of nilpotent subalgebras of the Virasoro algebra and partition identities. I. M. Gelfand Seminar, Adv. Soviet Math. 16, Part 1, 139-148, Amer. Math. Soc., Providence, RI, 1993. MR 94g:17054
  • [FineHer] Fine, N.J. and Herstein, I. N., The probability that a matrix be nilpotent, Illinois J. Math. 2 (1958), 499-504. MR 20:3160
  • [FinkKa] Finkelstein, L. and Kantor, W. (editors), Groups and computation II, DIMACS Series 28, Amer. Math. Soc., Providence, RI, 1997. MR 97m:20003
  • [Fey] Feynman, R., Statistical mechanics. A set of lectures. Reprint of the 1972 original. Perseus Books, Reading, MA, 1998. MR 99i:82001
  • [FlJ] Fleischmann, P. and Janiszczak, I., The number of regular semisimple elements for Chevalley groups of classical type. J. Algebra 155 (1993), 482-528. MR 94f:20090
  • [Frip1] Fripertinger, H., Cycle indices of linear, affine, and projective groups, Lin. Alg. Appl. 263 (1997), 133-156. MR 98h:05179
  • [Frip2] Fripertinger, H., Random generation of linear codes, Aequationes Math. 58 (1999), 192-202. MR 2001d:94028
  • [Fris] Fristedt, B., The structure of random partitions of large integers, Trans. Amer. Math. Soc. 337 (1993), 703-735. MR 93h:11090
  • [F1] Fulman, J., Probability in the classical groups over finite fields: symmetric functions, stochastic algorithms and cycle indices, Ph.D. Thesis, Harvard University, 1997.
  • [F2] Fulman, J., Cycle indices for the finite classical groups. J. Group Theory 2 (1999), 251-289. MR 2001d:20045
  • [F3] Fulman, J., A probabilistic approach to conjugacy classes in the finite general linear and unitary groups, J. Algebra 212 (1999), 557-590. MR 2000c:20072
  • [F4] Fulman, J., The Rogers-Ramanujan identities, the finite general linear groups, and the Hall-Littlewood polynomials, Proc. Amer. Math. Soc. 128 (2000), 17-25. MR 2000h:05229
  • [F5] Fulman, J., The eigenvalue distribution of a random unipotent matrix in its representation on lines, J. Algebra 228 (2000), 497-511. MR 2001d:20072
  • [F6] Fulman, J., A probabilistic approach to conjugacy classes in the finite symplectic and orthogonal groups, J. Algebra 234 (2000), 207-224. CMP 2001:05
  • [F7] Fulman, J., A probabilistic proof of the Rogers-Ramanujan identities. Bull. London Math. Soc. 33 (2001), 397-407.
  • [F8] Fulman, J., New examples of potential theory on Bratteli diagrams. Available at http://xxx.lanl.gov/abs/math.CO/9912148.
  • [F9] Fulman, J., Finite affine groups: cycle indices, symmetric functions, and probabilistic algorithms. To appear in J. Algebra.
  • [F10] Fulman, J., Applications of the Brauer complex: card-shuffling, permutation statistics, and dynamical systems. To appear in J. Algebra.
  • [FNP] Fulman, J., Neumann, P.M., and Praeger, C.E., A generating function approach to the enumeration of cyclic and separable matrices in the finite classical groups. Preprint.
  • [GarsH] Garsia, A. and Haiman, M., A random $q,t$-hook walk and a sum of Pieri coefficients, J. Combin. Theory Ser. A 82 (1998), 74-111. MR 2000b:05133
  • [GoSchm] Goh, W. and Schmutz, E., A central limit theorem on $GL(n,q)$, Random Struc. Alg. 2 (1991), 47-53. MR 92f:11176
  • [Gon] Goncharov, V., Du domaine d'analyse combinatoire, Bull. Acad. Sci. URSS Ser. Math 8 (1944), 3-48, translated in Amer. Math. Soc. Transl. 19 (1950).
  • [Gor] Gordon, B., A combinatorial generalization of the Rogers-Ramanujan identities, Amer. J. Math. 83 (1961), 393-99. MR 23:A809
  • [GuLub] Guralnick, R. and L$\ddot{u}$beck, F., The proportion of $p$-singular elements in simple groups of Lie type, to appear in Groups and Computation III.
  • [HSchm] Hansen, J. and Schmutz, E., How random is the characteristic polynomial of a random matrix?, Math. Proc. Cambridge Philos. Soc. 114 (1993), 507-515. MR 94j:05009
  • [Her] Herstein, I.N., Topics in algebra. Second edition. Xerox College Publishing, Lexington, Mass.-Toronto, Ont., 1975. MR 50:9456
  • [IsKanSp] Isaacs, I.M., Kantor, W.M., and Spaltenstein, N., On the probability that a group element is $p$-singular, J. Algebra 176 (1995), 139-181. MR 96f:20035
  • [IsKar] Isaacs, I. and Karagueuzian, D., Conjugacy in groups of upper triangular matrices, J. Algebra 202 (1998), 704-711. MR 99b:20011
  • [ItTWi] Its, A.R., Tracy, C.A., and Widom, H., Random words, Toeplitz determinants and integrable systems, I. Preprint math.CO/9909169 at xxx.lanl.gov.
  • [Jo] Johansson, K., Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math. (2) 153 (2001), 259-296. CMP 2001:11
  • [KeaSn] Keating, J.P. and Snaith, N.C., Random matrix theory and $\zeta(1/2+it)$. Comm. Math. Phys. 214 (2000), 57-89.
  • [Ke1] Kerov, S.V., The boundary of Young lattice and random Young tableaux, Formal power series and algebraic combinatorics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 24, Amer. Math. Soc., Providence, RI, (1996), 133-158. MR 96i:05177
  • [Ke2] Kerov, S.V., Generalized Hall-Littlewood symmetric functions and orthogonal polynomials, Adv. Sov. Math. 9 (1992), 67-94. MR 94b:05208
  • [Ke3] Kerov, S.V., Combinatorial examples in $AF$-algebras, Differential geometry, Lie groups and mechanics X, Zap. Nauchn. Sem. LOMI, Vol. 172, 1989, pp. 55-67 (Russian); English translation in J. Soviet Math. 59 (1992), 1063-1071. MR 90j:46062
  • [KeOOl] Kerov, S.V., Okounkov, A., and Olshanksi, G., The boundary of Young graph with Jack edge multiplicities, Intern. Math. Res. Notices 4 (1998), 173-199. MR 99f:05120
  • [Kin] Kingman, J.F.C., Random partitions in population genetics, Proc. R. Soc. Lond. A 361 (1978), 1-20. MR 58:26167
  • [Kir] Kirillov, A.A., Variations on the triangular theme, Amer. Math. Soc. Transl. 169 (1995), 43-73. MR 97a:20072
  • [Kn] Knuth, D., The art of computer programming. Vol. 2. Seminumerical algorithms. Third edition. Addison-Wesley Publishing. Reading, Mass., 1997.
  • [Ko] Kolchin, V., Random mappings. Optimization Software, Inc., New York, 1986. MR 88a:60022
  • [Kun] Kung, J., The cycle structure of a linear transformation over a finite field, Lin. Alg. Appl. 36 (1981), 141-155. MR 82d:15012
  • [Leh] Lehrer, G., The cohomology of the regular semisimple variety, J. Algebra 199 (1998), 666-689. MR 98k:20080
  • [LehSe] Lehrer, G. and Segal, G.P., Homology stability for classical regular semisimple varieties, Math. Z. 236 (2001), 251-290. CMP 2001:09
  • [LiSh] Liebeck, M.W. and Shalev, A., The probability of generating a finite simple group, Geom. Dedicata 56 (1995), 103-113. MR 96h:20116
  • [LiSh2] Liebeck, M.W. and Shalev, A., Simple groups, permutation groups, and probability. J. of AMS 12 (1999), 497-520. MR 99h:20004
  • [LubPa] Lubotzky, A. and Pak, I., The product replacement algorithm and Kazhdan's property $(T)$, J. of AMS 52 (2000), 5525-5561; J. of AMS 14 (2001), 347-363 (electronic).
  • [Mac] Macdonald, I.G., Symmetric functions and Hall polynomials, Second Edition. Clarendon Press, Oxford. 1995. MR 96h:05207
  • [MaSl] MacWilliams, F. and Sloane, N., The theory of error-correcting codes, Third printing, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. MR 57:5408a; MR 57:5408b
  • [Mar] Marsaglia, G., A current view of random number generators. Keynote Address, Sixteenth Symposium on the Interface between Computer Science and Statistics, Elsevier Press, 1984.
  • [MarTs] Marsaglia, G. and Tsay, L.H., Matrices and the structure of random number sequences, Lin. Alg. Appl. 67 (1985), 147-156. MR 86g:65018
  • [Mu] Murray, S., Conjugacy classes in maximal parabolic subgroups of the general linear group, Ph.D. Thesis, University of Chicago, 1999.
  • [NP1] Neumann, P.M. and Praeger, C.E., A recognition algorithm for special linear groups, Proc. London Math. Soc. (3) 65 (1992), 555-603. MR 93m:20063
  • [NP2] Neumann, P.M. and Praeger, C.E., Cyclic matrices over finite fields, J. London Math. Soc. (2) 52 (1995), 263-284. MR 96j:15017
  • [NP3] Neumann, P.M. and Praeger, C.E., Derangements and eigenvalue-free elements in finite classical groups, J. London Math. Soc. (2) 58 (1998), 562-586. MR 2000a:20153
  • [NP4] Neumann, P.M. and Praeger, C.E., Cyclic matrices and the meataxe, Groups and Computation III, de Gruyter, Berlin, 2001. CMP 2001:12
  • [NP5] Neumann, P.M. and Praeger, C.E., Cyclic matrices in classical groups over finite fields, J. Algebra 234 (2000), 367-418. CMP 2001:06
  • [NiP] Niemeyer, A. and Praeger, C.E., A recognition algorithm for classical groups over finite fields, Proc. London Math. Soc. 77 (1998), 117-169. MR 99k:20002
  • [O1] Okounkov, A., Infinite wedge and measures on partitions. Available at http://xxx.lanl.gov/abs/math.RT/9907127.
  • [Pa] Pak, I., What do we know about the product replacement algorithm?, in Groups and Computation III, deGruyter, Berlin, 2001. CMP 2001:12
  • [PoRe] Polya, G. and Read, R.C., Combinatorial enumeration of groups, graphs, and chemical compounds. Springer-Verlag. New York, 1987. MR 89f:05013
  • [Py1] Pyber, L., Asymptotic results for permutation groups, in Groups and computation, DIMACS Ser. 11, Amer. Math. Soc., Providence, RI (1993). MR 94g:20003
  • [Py2] Pyber, L., Asymptotic results for simple groups and some applications, in Groups and Computation II, DIMACS Ser. 28, Amer. Math. Soc., Providence, RI (1997). MR 98a:20030
  • [Py3] Pyber, L., Group enumeration and where it leads us, in European Congress of Mathematics, Vol. II (Budapest 1996), Birkhäuser, 1998. MR 99i:20037
  • [Ro] Rogers, L.J., Second memoir on the expansion of certain infinite products, Proc. London Math. Soc. 25 (1894), 318-343.
  • [RuShi] Rudvalis, A. and Shinoda, K., An enumeration in finite classical groups. Preprint (1988).
  • [Schm] Schmutz, E., The order of a typical matrix with entries in a finite field, Israel J. Math. 91 (1995), 349-71. MR 97e:15011
  • [Sh1] Shalev, A., A theorem on random matrices and some applications, J. Algebra 199 (1998), 124-141. MR 99a:20048
  • [Sh2] Shalev, A., Probabilistic group theory, in Groups St. Andrews 1997, London Math. Soc. Lecture Note Ser. 261, Cambridge Univ. Press (1999), 648-678. MR 2001b:20117
  • [Sh3] Shalev, A., Asymptotic group theory, Notices of the AMS 48 (2001), 383-389. CMP 2001:09
  • [ShLl] Shepp, L.A. and Lloyd, S.P. , Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc. 121 (1966), 340-357. MR 33:3320
  • [Shi] Shinoda, K., Identities of Euler and finite classical groups, in Proceedings of Asian Mathematical Conference (Hong Kong, 1990), World Sci. Publishing (1992), 423-427. CMP 92:13
  • [So] Soshnikov, A., Universality at the edge of the spectrum in Wigner random matrices, Comm. Math. Phys. 207 (1999), 697-733. CMP 2000:05
  • [Sta] Stanley, R., Generalized riffle shuffles and quasisymmetric functions. Available at http://xxx.lanl.gov/abs/math.CO/9912025.
  • [Stei] Steinberg, R., Regular elements of semisimple algebraic groups, R. Publ. Math. Inst. Hautes Etudes Sci. 25 (1965), 49-80. MR 31:4788
  • [St1] Stong, R., Some asymptotic results on finite vector spaces, Adv. Appl. Math. 9 (1988), 167-199. MR 89c:05007
  • [St2] Stong, R., The average order of a matrix, J. Combin. Theory Ser. A 64 (1993), 337-343. MR 94j:11094
  • [T] Thoma, E., Die unzerlegbaren, positiv-definiten Klassenfunktionen der abtahlbar unendlichen, symmetrischen Gruppe, Math. Zeitschr. 85 (1964), 40-61. MR 20:3382
  • [VAr] Vera López, A. and Arregi, J., Some algorithms for the calculation of conjugacy classes in the Sylow $p$-subgroups of $GL(n,q)$, J. Algebra 177 (1995), 899-925. MR 96j:20029
  • [VArV] Vera López, A., Arregi, J., and Vera López, F.J., On the number of conjugacy classes of the Sylow $p$-subgroups of $GL(n,q)$, Bull. Austral. Math. Soc. 52 (1995), 431-439. MR 96k:20041
  • [VeSc] Vershik, A. and Schmidt, A., Limit measures arising in the asymptotic theory of the symmetric group, Theory Probab. Appl. 22 (1978), 72-88; 23 (1979), 42-54.
  • [W1] Wall, G.E., On conjugacy classes in the unitary, symplectic, and orthogonal groups, J. Austr. Math. Soc. 3 (1963), 1-63. MR 27:212
  • [W2] Wall, G.E., Counting cyclic and separable matrices over a finite field, Bull. Austral. Math. Soc. 60 (1999), 253-284. MR 2000k:11137
  • [Wi] Wieand, K., Eigenvalue distributions of random matrices in the permutation group and compact Lie groups, Ph.D. Thesis, Harvard University, 1998.

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 60B15, 20G40

Retrieve articles in all journals with MSC (2000): 60B15, 20G40


Additional Information

Jason Fulman
Affiliation: Department of Mathematics, University of Pittsburgh, 301 Thackeray Hall, Pittsburgh, PA 15260
Email: fulman@math.pitt.edu

DOI: https://doi.org/10.1090/S0273-0979-01-00920-X
Received by editor(s): April 1, 2000
Received by editor(s) in revised form: April 24, 2001
Published electronically: October 5, 2001
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society