Random matrix theory over finite fields

Fulman, Jason

doi:10.1090/S0273-0979-01-00920-X

Random matrix theory over finite fields
HTML articles powered by AMS MathViewer

by Jason Fulman PDF

Bull. Amer. Math. Soc. 39 (2002), 51-85 Request permission

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

David Aldous and Persi Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. (N.S.) 36 (1999), no. 4, 413–432. MR 1694204, DOI 10.1090/S0273-0979-99-00796-X
George E. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. MR 0557013
George E. Andrews, $q$-series: their development and application in analysis, number theory, combinatorics, physics, and computer algebra, CBMS Regional Conference Series in Mathematics, vol. 66, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1986. MR 858826, DOI 10.1090/cbms/066
George E. Andrews, Multiple series Rogers-Ramanujan type identities, Pacific J. Math. 114 (1984), no. 2, 267–283. MR 757501, DOI 10.2140/pjm.1984.114.267
George E. Andrews, On the proofs of the Rogers-Ramanujan identities, $q$-series and partitions (Minneapolis, MN, 1988) IMA Vol. Math. Appl., vol. 18, Springer, New York, 1989, pp. 1–14. MR 1019838, DOI 10.1007/978-1-4684-0637-5_{1}
Richard Arratia, A. D. Barbour, and Simon Tavaré, On random polynomials over finite fields, Math. Proc. Cambridge Philos. Soc. 114 (1993), no. 2, 347–368. MR 1230136, DOI 10.1017/S0305004100071620
M. Aschbacher, On the maximal subgroups of the finite classical groups, Invent. Math. 76 (1984), no. 3, 469–514. MR 746539, DOI 10.1007/BF01388470
Garrett Birkhoff and Morgan Ward, A characterization of Boolean algebras, Ann. of Math. (2) 40 (1939), 609–610. MR 9, DOI 10.2307/1968945
Rodney J. Baxter, Exactly solved models in statistical mechanics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1982. MR 690578
R. J. Baxter, Ramanujan’s identities in statistical mechanics, Ramanujan revisited (Urbana-Champaign, Ill., 1987) Academic Press, Boston, MA, 1988, pp. 69–84. MR 938961
Spencer Bloch and Andrei Okounkov, The character of the infinite wedge representation, Adv. Math. 149 (2000), no. 1, 1–60. MR 1742353, DOI 10.1006/aima.1999.1845
Johannes Blömer, Richard Karp, and Emo Welzl, The rank of sparse random matrices over finite fields, Random Structures Algorithms 10 (1997), no. 4, 407–419. MR 1608234, DOI 10.1002/(SICI)1098-2418(199707)10:4<407::AID-RSA1>3.0.CO;2-Y
Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
A. M. Borodin, 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. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 240 (1997), no. Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 2, 18–43, 290 (Russian, with English and Russian summaries); English transl., J. Math. Sci. (New York) 96 (1999), no. 5, 3455–3471. MR 1691635, DOI 10.1007/BF02175823
Alexei Borodin, Andrei Okounkov, and Grigori Olshanski, Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000), no. 3, 481–515. MR 1758751, DOI 10.1090/S0894-0347-00-00337-4
Alexei Borodin and Grigori Olshanski, Harmonic functions on multiplicative graphs and interpolation polynomials, Electron. J. Combin. 7 (2000), Research Paper 28, 39. MR 1758654
F. Celler and C. R. Leedham-Green, A constructive recognition algorithm for the special linear group, The atlas of finite groups: ten years on (Birmingham, 1995) London Math. Soc. Lecture Note Ser., vol. 249, Cambridge Univ. Press, Cambridge, 1998, pp. 11–26. MR 1647410, DOI 10.1017/CBO9780511565830.007
Frank Celler, Charles R. Leedham-Green, Scott H. Murray, Alice C. Niemeyer, and E. A. O’Brien, Generating random elements of a finite group, Comm. Algebra 23 (1995), no. 13, 4931–4948. MR 1356111, DOI 10.1080/00927879508825509
Leonard S. Charlap, Howard D. Rees, and David P. Robbins, The asymptotic probability that a random biased matrix is invertible, Discrete Math. 82 (1990), no. 2, 153–163. MR 1057484, DOI 10.1016/0012-365X(90)90322-9
Naoki Chigira, Yugen Takegahara, and Tomoyuki Yoshida, On the number of homomorphisms from a finite group to a general linear group, J. Algebra 232 (2000), no. 1, 236–254. MR 1783923, DOI 10.1006/jabr.1999.8398

J. Comput. Appl. Math.

41

Persi Diaconis, Michael McGrath, and Jim Pitman, Riffle shuffles, cycles, and descents, Combinatorica 15 (1995), no. 1, 11–29. MR 1325269, DOI 10.1007/BF01294457
Robbert Dijkgraaf, Mirror symmetry and elliptic curves, The moduli space of curves (Texel Island, 1994) Progr. Math., vol. 129, Birkhäuser Boston, Boston, MA, 1995, pp. 149–163. MR 1363055, DOI 10.1007/978-1-4612-4264-2_{5}

Eigenvalues and condition numbers of random matrices

P. Erdős and P. Turán, On some problems of a statistical group-theory. I, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 4 (1965), 175–186 (1965). MR 184994, DOI 10.1007/BF00536750
W. J. Ewens, The sampling theory of selectively neutral alleles, Theoret. Population Biol. 3 (1972). MR 325177, DOI 10.1016/0040-5809(72)90035-4
Boris Feigin and Edward Frenkel, Coinvariants of nilpotent subalgebras of the Virasoro algebra and partition identities, I. M. Gel′fand Seminar, Adv. Soviet Math., vol. 16, Amer. Math. Soc., Providence, RI, 1993, pp. 139–148. MR 1237828
N. J. Fine and I. N. Herstein, The probability that a matrix be nilpotent, Illinois J. Math. 2 (1958), 499–504. MR 96677
Larry Finkelstein and William M. Kantor (eds.), Groups and computation. II, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 28, American Mathematical Society, Providence, RI, 1997. MR 1444126, DOI 10.1090/dimacs/028
Richard P. Feynman, Statistical mechanics, Advanced Book Classics, Perseus Books, Advanced Book Program, Reading, MA, 1998. A set of lectures; Reprint of the 1972 original. MR 1634071
Peter Fleischmann and Ingo Janiszczak, The number of regular semisimple elements for Chevalley groups of classical type, J. Algebra 155 (1993), no. 2, 482–528. MR 1212240, DOI 10.1006/jabr.1993.1055
Harald Fripertinger, Cycle indices of linear, affine, and projective groups, Linear Algebra Appl. 263 (1997), 133–156. MR 1453968, DOI 10.1016/S0024-3795(96)00530-7
Harald Fripertinger, Random generation of linear codes, Aequationes Math. 58 (1999), no. 1-2, 192–202. Dedicated to János Aczél on the occasion of his 75th birthday. MR 1714333, DOI 10.1007/s000100050107
Bert Fristedt, The structure of random partitions of large integers, Trans. Amer. Math. Soc. 337 (1993), no. 2, 703–735. MR 1094553, DOI 10.1090/S0002-9947-1993-1094553-1

Probability in the classical groups over finite fields: symmetric functions, stochastic algorithms and cycle indices

Jason Fulman, Cycle indices for the finite classical groups, J. Group Theory 2 (1999), no. 3, 251–289. MR 1696313, DOI 10.1515/jgth.1999.017
Jason Fulman, A probabilistic approach toward conjugacy classes in the finite general linear and unitary groups, J. Algebra 212 (1999), no. 2, 557–590. MR 1676854, DOI 10.1006/jabr.1998.7659
Jason Fulman, The Rogers-Ramanujan identities, the finite general linear groups, and the Hall-Littlewood polynomials, Proc. Amer. Math. Soc. 128 (2000), no. 1, 17–25. MR 1657747, DOI 10.1090/S0002-9939-99-05292-2
Jason Fulman, The eigenvalue distribution of a random unipotent matrix in its representation on lines, J. Algebra 228 (2000), no. 2, 497–511. MR 1764576, DOI 10.1006/jabr.1999.8278

J. Algebra

234

Bull. London Math. Soc.

33

J. Algebra

A. M. Garsia and M. Haiman, A random $q$, $t$-hook walk and a sum of Pieri coefficients, J. Combin. Theory Ser. A 82 (1998), no. 1, 74–111. MR 1616575, DOI 10.1006/jcta.1997.2842
William M. Y. Goh and Eric Schmutz, A central limit theorem on $\textrm {GL}_n(F_q)$, Random Structures Algorithms 2 (1991), no. 1, 47–53. MR 1099579, DOI 10.1002/rsa.3240020105

Bull. Acad. Sci. URSS Ser. Math

8

Amer. Math. Soc. Transl.

19

Basil Gordon, A combinatorial generalization of the Rogers-Ramanujan identities, Amer. J. Math. 83 (1961), 393–399. MR 123484, DOI 10.2307/2372962

Groups and Computation III

Jennie C. Hansen and Eric Schmutz, How random is the characteristic polynomial of a random matrix?, Math. Proc. Cambridge Philos. Soc. 114 (1993), no. 3, 507–515. MR 1235998, DOI 10.1017/S0305004100071796
I. N. Herstein, Topics in algebra, 2nd ed., Xerox College Publishing, Lexington, Mass.-Toronto, Ont., 1975. MR 0356988
I. M. Isaacs, W. M. Kantor, and N. Spaltenstein, On the probability that a group element is $p$-singular, J. Algebra 176 (1995), no. 1, 139–181. MR 1345299, DOI 10.1006/jabr.1995.1238
I. M. Isaacs and Dikran Karagueuzian, Conjugacy in groups of upper triangular matrices, J. Algebra 202 (1998), no. 2, 704–711. MR 1617655, DOI 10.1006/jabr.1997.7311

153

Comm. Math. Phys.

214

S. Kerov, The boundary of Young lattice and random Young tableaux, Formal power series and algebraic combinatorics (New Brunswick, NJ, 1994) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 24, Amer. Math. Soc., Providence, RI, 1996, pp. 133–158. MR 1363510, DOI 10.1007/bf02362775
S. V. Kerov, Generalized Hall-Littlewood symmetric functions and orthogonal polynomials, Representation theory and dynamical systems, Adv. Soviet Math., vol. 9, Amer. Math. Soc., Providence, RI, 1992, pp. 67–94. MR 1166196
S. V. Kerov, Combinatorial examples in the theory of AF-algebras, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 172 (1989), no. Differentsial′naya Geom. Gruppy Li i Mekh. Vol. 10, 55–67, 169–170 (Russian, with English summary); English transl., J. Soviet Math. 59 (1992), no. 5, 1063–1071. MR 1015698, DOI 10.1007/BF01480687
Sergei Kerov, Andrei Okounkov, and Grigori Olshanski, The boundary of the Young graph with Jack edge multiplicities, Internat. Math. Res. Notices 4 (1998), 173–199. MR 1609628, DOI 10.1155/S1073792898000154
J. F. C. Kingman, Random partitions in population genetics, Proc. Roy. Soc. London Ser. A 361 (1978), no. 1704, 1–20. MR 526801, DOI 10.1098/rspa.1978.0089
A. A. Kirillov, Variations on the triangular theme, Lie groups and Lie algebras: E. B. Dynkin’s Seminar, Amer. Math. Soc. Transl. Ser. 2, vol. 169, Amer. Math. Soc., Providence, RI, 1995, pp. 43–73. MR 1364453, DOI 10.1090/trans2/169/05
Valentin F. Kolchin, Random mappings, Translation Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York, 1986. Translated from the Russian; With a foreword by S. R. S. Varadhan. MR 865130
Joseph P. S. Kung, The cycle structure of a linear transformation over a finite field, Linear Algebra Appl. 36 (1981), 141–155. MR 604337, DOI 10.1016/0024-3795(81)90227-5
G. I. Lehrer, The cohomology of the regular semisimple variety, J. Algebra 199 (1998), no. 2, 666–689. MR 1489931, DOI 10.1006/jabr.1997.7195

Math. Z.

236

Martin W. Liebeck and Aner Shalev, The probability of generating a finite simple group, Geom. Dedicata 56 (1995), no. 1, 103–113. MR 1338320, DOI 10.1007/BF01263616
Martin W. Liebeck and Aner Shalev, Simple groups, permutation groups, and probability, J. Amer. Math. Soc. 12 (1999), no. 2, 497–520. MR 1639620, DOI 10.1090/S0894-0347-99-00288-X

J. of AMS

52

J. of AMS

14

I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
S. Bergmann and J. Marcinkiewicz, Sur les fonctions analytiques de deux variables complexes, Fund. Math. 33 (1939), 75–94 (French). MR 57, DOI 10.4064/fm-33-1-75-94
George Marsaglia and Liang-Huei Tsay, Matrices and the structure of random number sequences, Linear Algebra Appl. 67 (1985), 147–156. MR 787372, DOI 10.1016/0024-3795(85)90192-2

Conjugacy classes in maximal parabolic subgroups of the general linear group

Peter M. Neumann and Cheryl E. Praeger, A recognition algorithm for special linear groups, Proc. London Math. Soc. (3) 65 (1992), no. 3, 555–603. MR 1182102, DOI 10.1112/plms/s3-65.3.555
Peter M. Neumann and Cheryl E. Praeger, Cyclic matrices over finite fields, J. London Math. Soc. (2) 52 (1995), no. 2, 263–284. MR 1356142, DOI 10.1112/jlms/52.2.263
Peter M. Neumann and Cheryl E. Praeger, Derangements and eigenvalue-free elements in finite classical groups, J. London Math. Soc. (2) 58 (1998), no. 3, 564–586. MR 1678151, DOI 10.1112/S0024610798006772

Groups and Computation III

J. Algebra

234

Alice C. Niemeyer and Cheryl E. Praeger, A recognition algorithm for classical groups over finite fields, Proc. London Math. Soc. (3) 77 (1998), no. 1, 117–169. MR 1625479, DOI 10.1112/S0024611598000422

Groups and Computation III

G. Pólya and R. C. Read, Combinatorial enumeration of groups, graphs, and chemical compounds, Springer-Verlag, New York, 1987. Pólya’s contribution translated from the German by Dorothee Aeppli. MR 884155, DOI 10.1007/978-1-4612-4664-0
László Pyber, Asymptotic results for permutation groups, Groups and computation (New Brunswick, NJ, 1991) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, RI, 1993, pp. 197–219. MR 1235804
László Pyber, Asymptotic results for simple groups and some applications, Groups and computation, II (New Brunswick, NJ, 1995) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, RI, 1997, pp. 309–327. MR 1444143
L. Pyber, Group enumeration and where it leads us, European Congress of Mathematics, Vol. II (Budapest, 1996) Progr. Math., vol. 169, Birkhäuser, Basel, 1998, pp. 187–199. MR 1645826

Proc. London Math. Soc.

25

Eric Schmutz, The order of a typical matrix with entries in a finite field, Israel J. Math. 91 (1995), no. 1-3, 349–371. MR 1348322, DOI 10.1007/BF02761656
Aner Shalev, A theorem on random matrices and some applications, J. Algebra 199 (1998), no. 1, 124–141. MR 1489358, DOI 10.1006/jabr.1997.7167
Aner Shalev, Probabilistic group theory, Groups St. Andrews 1997 in Bath, II, London Math. Soc. Lecture Note Ser., vol. 261, Cambridge Univ. Press, Cambridge, 1999, pp. 648–678. MR 1676661, DOI 10.1017/CBO9780511666148.028

Notices of the AMS

48

L. A. Shepp and S. P. Lloyd, Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc. 121 (1966), 340–357. MR 195117, DOI 10.1090/S0002-9947-1966-0195117-8

Proceedings of Asian Mathematical Conference (Hong Kong, 1990)

Comm. Math. Phys.

207

Robert Steinberg, Regular elements of semisimple algebraic groups, Inst. Hautes Études Sci. Publ. Math. 25 (1965), 49–80. MR 180554, DOI 10.1007/BF02684397
Richard Stong, Some asymptotic results on finite vector spaces, Adv. in Appl. Math. 9 (1988), no. 2, 167–199. MR 937520, DOI 10.1016/0196-8858(88)90012-7
Richard Stong, The average order of a matrix, J. Combin. Theory Ser. A 64 (1993), no. 2, 337–343. MR 1245166, DOI 10.1016/0097-3165(93)90102-E
Walter Littman, Remarks on the Dirichlet problem for general linear partial differential equations, Comm. Pure Appl. Math. 11 (1958), 145–151. MR 96900, DOI 10.1002/cpa.3160110108
Antonio Vera López and J. M. Arregi, Some algorithms for the calculation of conjugacy classes in the Sylow $p$-subgroups of $\textrm {GL}(n,q)$, J. Algebra 177 (1995), no. 3, 899–925. MR 1358490, DOI 10.1006/jabr.1995.1333
Antonio Vera López, J. M. Arregi, and F. J. Vera López, On the number of conjugacy classes of the Sylow $p$-subgroups of $\textrm {GL}(n,q)$, Bull. Austral. Math. Soc. 52 (1995), no. 3, 431–439. MR 1358698, DOI 10.1017/S000497270001491X

Theory Probab. Appl.

22

23

G. E. Wall, On the conjugacy classes in the unitary, symplectic and orthogonal groups, J. Austral. Math. Soc. 3 (1963), 1–62. MR 0150210, DOI 10.1017/S1446788700027622
G. E. Wall, Counting cyclic and separable matrices over a finite field, Bull. Austral. Math. Soc. 60 (1999), no. 2, 253–284. MR 1711918, DOI 10.1017/S000497270003639X

Eigenvalue distributions of random matrices in the permutation group and compact Lie groups