Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format 		Bulletin of the American Mathematical Society
Bulletin of the American Mathematical Society
ISSN 1088-9485(e) ISSN 0273-0979(p)

     

Random matrix theory over finite fields

Author(s): Jason Fulman
Journal: Bull. Amer. Math. Soc. 39 (2002), 51-85.
MSC (2000): Primary 60B15, 20G40
Posted: October 5, 2001
MathSciNet review: 1864086
Retrieve article in: 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:

[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: 10.1090/S0273-0979-01-00920-X
PII: S 0273-0979(01)00920-X
Received by editor(s): April 2000, and in revised form April 24, 2001
Posted: October 5, 2001
Copyright of article: Copyright 2001, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia