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 [DiaGr]DG Diaconis, P. and Graham, R., An affine walk on the hypercube, J. Comput. Appl. Math. 41 (1992), 215-235.
- 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} [Ed]E Edelman, A., Eigenvalues and condition numbers of random matrices, Ph.D. Thesis, MIT, 1989. [El]El Elkies, N., On finite sequences satisfying linear recursions. Available at http://xxx.lanl.gov/abs/math.CO/0105007.
- 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 [F1]F1 Fulman, J., Probability in the classical groups over finite fields: symmetric functions, stochastic algorithms and cycle indices, Ph.D. Thesis, Harvard University, 1997.
- 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 [F6]F6 Fulman, J., A probabilistic approach to conjugacy classes in the finite symplectic and orthogonal groups, J. Algebra 234 (2000), 207-224. [F7]F7 Fulman, J., A probabilistic proof of the Rogers-Ramanujan identities. Bull. London Math. Soc. 33 (2001), 397-407. [F8]F8 Fulman, J., New examples of potential theory on Bratteli diagrams. Available at http://xxx.lanl.gov/abs/math.CO/9912148. [F9]F9 Fulman, J., Finite affine groups: cycle indices, symmetric functions, and probabilistic algorithms. To appear in J. Algebra. [F10]F10 Fulman, J., Applications of the Brauer complex: card-shuffling, permutation statistics, and dynamical systems. To appear in J. Algebra. [FNP]FNP1 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.
- 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 [Gon]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).
- Basil Gordon, A combinatorial generalization of the Rogers-Ramanujan identities, Amer. J. Math. 83 (1961), 393–399. MR 123484, DOI 10.2307/2372962 [GuLub]GL 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.
- 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 [ItTWi]ITW 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]Jo Johansson, K., Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math. (2) 153 (2001), 259–296. [KeaSn]KeSn Keating, J.P. and Snaith, N.C., Random matrix theory and $\zeta (1/2+it)$. Comm. Math. Phys. 214 (2000), 57-89.
- 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 [Kn]Kn Knuth, D., The art of computer programming. Vol. 2. Seminumerical algorithms. Third edition. Addison-Wesley Publishing. Reading, Mass., 1997.
- 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 [LehSe]LehSe Lehrer, G. and Segal, G.P., Homology stability for classical regular semisimple varieties, Math. Z. 236 (2001), 251–290.
- 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 [LubPa]LP 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).
- 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 [Mar]Ma Marsaglia, G., A current view of random number generators. Keynote Address, Sixteenth Symposium on the Interface between Computer Science and Statistics, Elsevier Press, 1984.
- 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 [Mu]M Murray, S., Conjugacy classes in maximal parabolic subgroups of the general linear group, Ph.D. Thesis, University of Chicago, 1999.
- 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 [NP4]NP4 Neumann, P.M. and Praeger, C.E., Cyclic matrices and the meataxe, Groups and Computation III, de Gruyter, Berlin, 2001. [NP5]NP5 Neumann, P.M. and Praeger, C.E., Cyclic matrices in classical groups over finite fields, J. Algebra 234 (2000), 367–418.
- 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 [O1]O1 Okounkov, A., Infinite wedge and measures on partitions. Available at http://xxx.lanl.gov/abs/math.RT/9907127. [Pa]P Pak, I., What do we know about the product replacement algorithm?, in Groups and Computation III, deGruyter, Berlin, 2001.
- 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 [Ro]Ro Rogers, L.J., Second memoir on the expansion of certain infinite products, Proc. London Math. Soc. 25 (1894), 318-343. [RuShi]RS Rudvalis, A. and Shinoda, K., An enumeration in finite classical groups. Preprint (1988).
- 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 [Sh3]Sh3 Shalev, A., Asymptotic group theory, Notices of the AMS 48 (2001), 383-389.
- 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 [Shi]S Shinoda, K., Identities of Euler and finite classical groups, in Proceedings of Asian Mathematical Conference (Hong Kong, 1990), World Sci. Publishing (1992), 423-427. [So]So Soshnikov, A., Universality at the edge of the spectrum in Wigner random matrices, Comm. Math. Phys. 207 (1999), 697-733. [Sta]Sta2 Stanley, R., Generalized riffle shuffles and quasisymmetric functions. Available at http://xxx.lanl.gov/abs/math.CO/9912025.
- 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 [VeSc]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.
- 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 [Wi]W Wieand, K., Eigenvalue distributions of random matrices in the permutation group and compact Lie groups, Ph.D. Thesis, Harvard University, 1998.
Additional Information
- Jason Fulman
- Affiliation: Department of Mathematics, University of Pittsburgh, 301 Thackeray Hall, Pittsburgh, PA 15260
- MR Author ID: 332245
- Email: fulman@math.pitt.edu
- Received by editor(s): April 20, 2000
- Received by editor(s) in revised form: April 24, 2001
- Published electronically: October 5, 2001
- © Copyright 2001 American Mathematical Society
- 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
- MathSciNet review: 1864086