Patterns in eigenvalues: the 70th Josiah Willard Gibbs lecture Persi Diaconis diaconis@math.stanford.edu ]]> Typical large unitary matrices show remarkable patterns in their eigenvalue distribution. These same patterns appear in telephone encryption, the zeros of Riemann's zeta function, a variety of physics problems, and in the study of Toeplitz operators. This paper surveys these applications and what is currently known about the patterns. AdVan Adler, M.; Van Moerbeke, P. , Integrals over Classical Groups, Random Permutations, Toda and Toeplitz Lattices. Comm. Pure Appl. Math. 2001 , 54 , 153--205. AdShVM Adler, M.; Van Moerbeke, P. , Recursion Relations for Unitary Integrals, Combinatorics and the Toeplitz Lattice. Technical Report, Dept. of Mathematics, Brandeis, 2002. AdShVM1 Adler, M.; Shiota, T.; Van Moerbeke, P. , Random Matrices, Virasoro Algebras, and Non-Commutative KP. Duke Math. J. 1998 , 94 , 379--431. 99e:58088 AlDi Aldous, D.; Diaconis, P. , Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem. Bull. Amer. Math. Soc. 1999 , 36 , 413--432. 2000g:60013 And Anderson, T. , Asymptotic Theory for Principal Component Analysis. Ann. Math. Statist. 1963 , 34 , 122--148. 26:3149 d'Ari d'Aristotle, A. , An Invariance Principle for Triangular Arrays. Jour. Theoret. Probab. 2000 , 13 , 327--342. d'ADiNe d'Aristotle, A.; Diaconis, P; Newman, C. , Brownian Motion and the Classical Groups. Technical Report, Stanford University, 2002. Bai Bai, Z. , Methodologies in Spectral Analysis of Large Dimensional Random Matrices: A Review. Statistica Sinica 1999 , 9 , 611-677. 2000e:60044 BaDeJo Baik, J.; Deift, P.; Johansson, K. , On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations. Jour. Amer. Math. Soc. 1999 , 12 , 1119--1178. 2000e:05006 Basor Basor, E. , Distribution Functions for Random Variables for Ensembles of Positive Hermitian Matrices. Comm. Math. Phys. 1997 , 188 , 327--350. 99b:82046 Basor1 Basor, E. , Connections Between Random Matrices and Szego Limit Theorem. In Spectral Problems in Geometry and Arithmetic ; Branson, T., Ed.; Amer. Math. Soc.: Providence, RI, 1999; 1--7. 2000e:47049 BeKe Berry, M.; Keating, J. , The Riemann Zeros and Eigenvalue Asymptotics. Siam Review 1999 , 41 , 236--266. 2000f:11107 Biane Biane, P. , Free Probability for Probabilists , 2000, preprint. BoGi Bohigas, O.; Giannoni, M. , Chaotic Motion and Random Matrix Theories. In Mathematical and Computational Methods in Nuclear Physics ; Dehesa, J.L., Ed.; Springer Lecture Notes in Physics, 1984, 209 , 1--99. 86c:58129 Borel Borel, E. , Sur les Principes de la Theorie Cinetique des Gaz. Annales, L'Ecole Normal Sup. 1906 , 23 , 9--32. BoOl Borodin, A.; Olshansky, G. , Correlation Kernels Arising from the Infinite-Dimensional Unitary Group and Its Representations. University of Pennsylvania, Department of Mathematics, 2001, preprint. BoSi Bottcher, A. and Silbermann, B. , Introduction to Large Truncated Toeplitz Matrices. Springer-Verlag: New York, 1999. 2001b:47043 BoJe Bougerol, Ph. and Jeulin, Th. , Paths in Weyl Chambers and Random Matrices. Laboratoire de Probabilities: Paris 2001 , preprint. BdMPS Boutet de Monvel, A.; Pastur, L.; Shcherbina, M. , On the Statistical Mechanics Approach in the Random Matrix Theory: Integrated Density of States. Jour. Statist. Phys. 1995 , 79 , 585--611. 96d:82033 BuDi Bump, D. and Diaconis, P. , Toeplitz Minors. Jour. Combin. Th. A. 2002 , 97 , 252--271. 2002j:47052 BuDiKe Bump, D.; Diaconis, P.; Keller, J. , Unitary Correlations and the Fejer Kernel. Mathematical Phys., Analysis, Geometry 2002 , 5 , 101--123. Conrey Conrey, B. , L -Functions and Random Matrices. In Mathematics Unlimited 2001 and Beyond ; Enquist, B., Schmid, W. Eds.; Springer-Verlag: Berlin, 2001; 331--352. CKRS Conrey, B.; Farmer, D.; Keating, J.; Rubinstein, M.; Snaith, W. , Correlation of Random Matrix Polynomials. Technical Report, American Institute of Mathematics, 2002. CoDi Coram, M.; Diaconis, P. , New Tests of the Correspondence Between Unitary Eigenvalues and the Zeros of Riemann's Zeta Function. Jour. Phys. A. 2002 , to appear. DaVe Daley, D.; Verre-Jones, D. , An Introduction to the Theory of Point Processes. Springer-Verlag: New York, 1988. 90e:60060 Dei1 Deift, P. , Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach. Courant Lecture Notes 3, NYU Courant Institute: New York, and Amer. Math. Soc.: Providence, RI, 1999. 2000g:47048 Dei2 Deift, P. , Integrable Systems and Combinatorial Theory. Notices, Amer. Math. Soc. 2000 , 47, 631--640. 2001g:05012 Diac Diaconis, P. , Group Representations in Probability and Statistics. Ins. Math. Statist., Hayward, CA, 1986. 90a:60001 Diaconis Diaconis, P. , Applications of the Method of Moments in Probability and Statistics. In Moments in Mathematics ; Landau, H., Ed.; Amer. Math. Soc.: Providence, RI, 1987; 125--142. 89m:60006 DiSh Diaconis, P.; Shahshahani, M. , Products of Random Matrices as They Arise in the Study of Random Walks on Groups. Contemp. Math. 1986 , 50 , 183--195. 87k:60025 DiSh1a Diaconis, P.; Shahshahani, M. , The Subgroup Algorithm for Generating Uniform Random Variables. Prob. Eng. and Info. Sci. 1987 , 1 , 15--32. DiSh1 Diaconis, P.; Shahshahani, M. , On the Eigenvalues of Random Matrices. In Studies in Applied Probablility ; Gani, J., Ed.; Jour. Appl. Probab.: Special Vol. 31A, 1994; 49--62. 95m:60011 DiEv1 Diaconis, P.; Evans, S. , Linear Functionals of Eigenvalues of Random Matrices. Transactions Amer. Math. Soc. 2001 , 353 , 2615--2633. 2002d:60003 DiEv2 Diaconis, P.; Evans, S. , Immanants and Finite Point Processes. Jour. Combin. Th. A. 2000 , 91 , 305--321. 2001m:15018 DiEv3 Diaconis, P.; Evans, S. , A Different Construction of Gaussian Fields from Markov Chains: Dirichlet Covariances. Ann. Inst. Henri Poincare, 2002 , to appear. DiFr Diaconis, P.; Freedman, D. , A Dozen deFinetti-Style Results in Search of a Theory. Ann. Inst. Henri Poincare, 1987 , 23 , 397--423. 88f:60072 DiEaLa Diaconis, P.; Eaton, M.; Lauritzan, S. , Finite deFinetti Theorems in Linear Models and Multivariate Analysis. Scand. Jour. Statist. 1992 , 19 , 289--315. 94g:60065 Dyson1 Dyson, F. , Statistical Theory of the Energy Levels of Complex Systems, I, II, III. J. Math. Phys. 1962 , 3 , 140--156, 157--165, 166--175. , 26:111126:111226:1113 Dyson2 Dyson, F. , Correlations Between Eigenvalues of a Random Matrix. Comm. Math. Phys. 1970 , 19 , 235--250. 43:4398 Eaton Eaton, M. , Multivariate Statistics ; Wiley: New York, 1983. 86i:62086 EdKoSh Edelman, A.; Kostlan, E.; Shub, M. , How Many Eigenvalues of a Random Matrix Are Real Jour. Amer. Math. Soc. 1994 , 7 , 297--267. 94f:60053 FoRa Forrester, P.; Rains, E. , Inter-Relationships Between Orthogonal, Unitary and Symplectic Matrix Ensembles. MSRI Publications 2001 , 40 , 171--207. 2002h:82008 Fullman Fulman, J. , Random Matrix Theory Over Finite Fields. Bull. Amer. Math. Soc. 2002 , 39 , 51--86. 2002i:60012 Fulton Fulton, W. , Eigenvalues, Invariant Factors, Highest Weights and Schubert Calculus. Bull. Amer. Math. Soc. 2000 , 37 , 209--249. 2001g:15023 FyKhSo Fyodorov, Y.; Khoruzhenko, B.; Sommers, H. , Universality in the Random Matrix Spectra in the Regime of Weak Non-Hermiticity. Ann. Inst. Henri Poincare: Physique Theorique 1998 , 68 , 440--489. 99i:60080 GoKh Goldsheid, I.; Khoruzhenko, B. , Eigenvalue Curves of Asymmetric Tri-Diagonal Random Matrices. Electronic Jour. Probab. 2000 , 5 , Paper 16. 2002j:82061 GoRhWa Goodman, R.; Wallach, W. , Representations and Invariants of the Classical Groups . Cambridge Press: Cambridge, 1998. 99b:20073 GrSz Grenander, U.; Szego, G. , Toeplitz Forms and Their Applications. University of California Press: Berkeley, 1958. 20:1349 Haake1 Haake, F. , Secular Determinants of Random Unitary Matrices. Jour. Pys. A. 1996 , 29 , 3641--3658. 97g:82002 Haake2 Haake, F. , Quantum Signatures of Chaos , 2nd Ed.; Springer-Verlag: Berlin, 2001. HaSt Hanlon, P.; Stanley, R.; Stembridge, J. , Some Combinatorial Aspects of the Spectra of Normally Distributed Random Matrices. Contemp. Math. 1992 , 138 , 151--174. 93j:05164 Hirsh Hirschman, I. , The Strong Szego Limit Theorem for Toeplitz Determinants. Amer. Jour. Math. 1966 , 88 , 577--614. 35:2064 HuKeO' Hughes, C.; Keating, J.; O'Connell, W. , On the Characteristic Polynomial of a Random Unitary Matrix. Comm. Math. Phys. 2001 , 220 , 429--451. 2002m:82028 HuRu Hughes, C.; Rudnick, Z. , Mock-Gaussian Behavior for Linear Statistics of Classical Compact Groups. Department of Mathematics, Tel Aviv University, 2002, preprint. Johan1 Johansson, K. , On Szego's Asymptotic Formula for Toeplitz Determinants and Generalizations. Bull. Sc. Math. 1988 , 112 , 257--304. 89m:47021 Johan2 Johansson, K. , On Random Matrices from the Compact Classical Groups. Ann. Math. 1997 , 145 , 519--545. 98e:60016 Johan3 Johansson, K. , The Longest Increasing Subsequence in a Random Permutation and a Unitary Random Matrix Model. Math. Res. Lett. 1998 , 5 , 63--82. 99e:60033 Johnstone Johnstone, I. , On the Distribution of the Largest Eigenvalue in Principal Component Analysis. Ann. Statist. 2001 , 29 , 295--327. 2002i:62115 KaSa Katz, N.; Sarnak, P. , Random Matrices, Frobenius Eigenvalues, and Monodromy. Amer. Math. Soc.: Providence, RI, 1999. 2000b:11070 KeSn1 Keating, J.; Snaith, N. , Random Matrix Theory and (12 it) . Commun. Math. Phys. 2000 , 214 , 57--89. 2002c:11107 KeSn2 Keating, J.; Snaith, N. , Random Matrix Theory and L -Functions at s 12 . Commun. Math. Phys. 2000 , 214 , 91--110. 2002c:11108 KiSp Kiessling, M.; Spohn, H. , A Note on the Eigenvalue Density of Random Matrices. Comm. Math. Phys. 1999 , 199 , 638--695. 2000a:82031 Ma1 Macchi, O. , Stochastic Processes and Multicoincidences. IEEE Transactions 1971 , 17 , 1--7. Ma2 Macchi, O. , The Coincidence Approach to Stochastic Point Processes. Adv. Appl. Probab. 1975 , 7 , 83--122. 52:1876 Mac MacDonald, I. , Symmetric Functions and Hall Polynomials , 2nd Ed.; Clarendon Press: Oxford, 1995. 96h:05207 MaPa Marchenko, V.; Pastur, L. , Distribution of Some Sets of Random Matrices. Mat. Sb. 1967 , 1 , 507--536. MaKeBi Mardia, K.; Kent, J.; Bibby, J. , Multivariate Analysis. Academic Press: New York, 1979. 81h:62003 Mehta Mehta, M. , Random Matrices , 2nd Ed.; Acad. Press: New York, 1991. 92f:82002 Mezz Mezzadri, F. , Random Matrix Theory and the Zeros of (s) . Dept. of Mathematics, University of Bristol, 2002 , preprint. Muir Muirhead, R. , Latent Roots and Matrix Variates: A Review of Some Aymptotic Results. Ann. Statist. 1978 , 6 , 5--33. 56:16919 Odlyz1 Odlyzko, A. , On the Distribution of Spacings Between Zeros of the Zeta Function. Math. Comp. 1987 , 48 , 273--308. 88d:11082 Odlyz2 Odlyzko, A. , The 10 20 -th Zero of the Riemann Zeta Function and 175 Million of Its Neighbors. ATT Laboratories, 1992, preprint. O'Con1 O'Connell, N. , Random Matrices, Non-Colliding Processes and Queues. Laboratoire de Probabilites, Paris 6, 2002, preprint. O'Con2 O'Connell, N.; Yor, M. , Brownian Analogues of Burke's Theorem. Stoch. Proc. Appl. 2001 , 96 , 285--304. 2002h:60175 Okou Okounkov, A. , Random Matrices and Random Permutations. Math. Res. Notices 2000 , 20 , 1043--1095. 2002c:15045 Olsh Olshansky, G. , An Introduction to Harmonic Analysis on the Infinite-Dimensional Unitary Group. University of Pennsylvania, Dept. of Mathematics, 2001, preprint. OlVe Olshanski, G.; Vershik, A. , Ergodic Unitarily Invariant Measures on the Space of Infinite Hermitian Matrices. In Contemporary Mathematical Physics ; Amer. Soc. Transl. Ser. 2, 1996, 175 , 137--175. 98e:28015 Pick Pickrell, D. , Mackey Analysis of Infinite Classical Motion Groups. Pacific Jour. 1991 , 150 , 139--166. 92g:22041 Porod Porod, U. , The Cut-Off Phenomenon for Random Reflections. Ann. Probab. 1996 , 24 , 74--96. 97e:60012 Rai1 Rains, E. , High Powers of Random Elements of Compact Lie Groups. Probab. Th. Related Fields 107 , 219--241. 98b:15026 Rai2 Rains, E. , Images of Eigenvalue Distributions Under Power Maps. ATT Laboratories, 1999, preprint. Rai3 Rains, E. , Probability Theory on Compact Classical Groups. , Harvard University: Department of Mathematics, 1991, Ph.D. thesis. Ros Rosenthal, J. , Random Rotations, Characters and Random Walks on SO(N). Ann Probab. 1994 , 22 , 398--423. 95c:60008 SiSo Sinai, Y.; Soshnikov, A. , Central Limit Theorem for Traces of Large Random Symmetric Matrices with Independent Matrix Elements. Bol. Soc. Brasil. Mat. (N.S.) 1998 , 29 , 1--24. 99f:60053 Sloane Sloane, N. , Encrypting by Random Rotations. Technical Memorandum, Bell Laboratories, 1983. Sosh1 Soshnikov, A. , The Central Limit Theorem for Local Linear Statistics in Classical Compact Groups and Related Combinatorial Identities. Ann. Probab. 2000 , 28 , 1353--1370. 2002f:15035 Sosh2 Soshnikov, A. , Level Spacings Distribution for Large Random Matrices: Gaussian Fluctuations. Ann. Math. 1998 , 148 , 573--617. 2000f:15014 Sosh3 Soshnikov, A. , Determinantal Random Point Fields. Russian Math. Surveys 2000 , 55 , 923--975. 2002f:60097 Stan Stanley, R. , Enumerative Combinatorics. Vol. 2 ,; Cambridge University Press: Cambridge, 1999. 2000k:05026 TrWi1 Tracy, C.; Widom, H. , Introduction to Random Matrices. In Geometric and Quantum Aspects of Integrable Systems ; Springer-Verlag: Berlin, 1993, 103--130. 95a:82050 TrWi2 Tracy, C.; Widom, H. , Random Unitary Matrices, Permutations and Painleve. Comm. Math. Physics 1999 , 207 , 665--685. 2001h:15019 TrWi3 Tracy, C.; Widom, H. , On the Relations Between Orthogonal, Symplectic and Unitary Ensembles. Jour. Statist. Phys. 1999 , 94 , 347--363. TrWi4 Tracy, C.; Widom, H. , Universality of the Distribution Functions of Random Matrix Theory. CRM Proceedings 2000 , 26 , 251--264. 2002f:15036 TrWi5 Tracy, C.; Widom, H. , On the Limit of Some Toeplitz-Like Determinants. SIAM J. Matrix Anal. Appl. 2002 , 23 , 1194--1196. Voi Voiculescu, D. , Lectures on Free Probability Theory. Springer Lecture Notes in Mathematics 2000 , 1738 , 279--349. 2001g:46121 Wie1 Wieand, K. , Eigenvalue Distributions of Random Matrices in the Permutation Group and Compact Lie Groups , Harvard University: Department of Mathematics, 1998, Ph.D. thesis. Wie2 Wieand, K. , Eigenvalue Distributions of Random Permutation Matrices. Ann. Probab. 2000 , 28 , 1563--1587. 2002d:15027
1.
Adler, M.; Van Moerbeke, P., Integrals over Classical Groups, Random Permutations, Toda and Toeplitz Lattices. Comm. Pure Appl. Math. 2001, 54, 153-205.

2.
Adler, M.; Van Moerbeke, P., Recursion Relations for Unitary Integrals, Combinatorics and the Toeplitz Lattice. Technical Report, Dept. of Mathematics, Brandeis, 2002.

3.
Adler, M.; Shiota, T.; Van Moerbeke, P., Random Matrices, Virasoro Algebras, and Non-Commutative KP. Duke Math. J. 1998, 94, 379-431. MR 99e:58088

4.
Aldous, D.; Diaconis, P., Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem. Bull. Amer. Math. Soc. 1999, 36, 413-432. MR 2000g:60013

5.
Anderson, T., Asymptotic Theory for Principal Component Analysis. Ann. Math. Statist. 1963, 34, 122-148. MR 26:3149

6.
d'Aristotle, A., An Invariance Principle for Triangular Arrays. Jour. Theoret. Probab. 2000, 13, 327-342.

7.
d'Aristotle, A.; Diaconis, P; Newman, C., Brownian Motion and the Classical Groups. Technical Report, Stanford University, 2002.

8.
Bai, Z., Methodologies in Spectral Analysis of Large Dimensional Random Matrices: A Review. Statistica Sinica 1999, 9, 611-677. MR 2000e:60044
9.
Baik, J.; Deift, P.; Johansson, K., On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations. Jour. Amer. Math. Soc. 1999, 12, 1119-1178. MR 2000e:05006

10.
Basor, E., Distribution Functions for Random Variables for Ensembles of Positive Hermitian Matrices. Comm. Math. Phys. 1997, 188, 327-350. MR 99b:82046
11.
Basor, E., Connections Between Random Matrices and Szegö Limit Theorem. In Spectral Problems in Geometry and Arithmetic; Branson, T., Ed.; Amer. Math. Soc.: Providence, RI, 1999; 1-7. MR 2000e:47049
12.
Berry, M.; Keating, J., The Riemann Zeros and Eigenvalue Asymptotics. Siam Review 1999, 41, 236-266. MR 2000f:11107
13.
Biane, P., Free Probability for Probabilists, 2000, preprint.
14.
Bohigas, O.; Giannoni, M., Chaotic Motion and Random Matrix Theories. In Mathematical and Computational Methods in Nuclear Physics; Dehesa, J.L., Ed.; Springer Lecture Notes in Physics, 1984, 209, 1-99. MR 86c:58129
15.
Borel, E., Sur les Principes de la Theorie Cinetique des Gaz. Annales, L'Ecole Normal Sup. 1906, 23, 9-32.

16.
Borodin, A.; Olshansky, G., Correlation Kernels Arising from the Infinite-Dimensional Unitary Group and Its Representations. University of Pennsylvania, Department of Mathematics, 2001, preprint.
17.
Böttcher, A. and Silbermann, B., Introduction to Large Truncated Toeplitz Matrices. Springer-Verlag: New York, 1999. MR 2001b:47043
18.
Bougerol, Ph. and Jeulin, Th., Paths in Weyl Chambers and Random Matrices. Laboratoire de Probabilities: Paris 2001, preprint.
19.
Boutet de Monvel, A.; Pastur, L.; Shcherbina, M., On the Statistical Mechanics Approach in the Random Matrix Theory: Integrated Density of States. Jour. Statist. Phys. 1995, 79, 585-611. MR 96d:82033
20.
Bump, D. and Diaconis, P., Toeplitz Minors. Jour. Combin. Th. A. 2002, 97, 252-271. MR 2002j:47052

21.
Bump, D.; Diaconis, P.; Keller, J., Unitary Correlations and the Fejer Kernel. Mathematical Phys., Analysis, Geometry 2002, 5, 101-123.

22.
Conrey, B., $L$-Functions and Random Matrices. In Mathematics Unlimited 2001 and Beyond; Enquist, B., Schmid, W. Eds.; Springer-Verlag: Berlin, 2001; 331-352.

23.
Conrey, B.; Farmer, D.; Keating, J.; Rubinstein, M.; Snaith, W., Correlation of Random Matrix Polynomials. Technical Report, American Institute of Mathematics, 2002.

24.
Coram, M.; Diaconis, P., New Tests of the Correspondence Between Unitary Eigenvalues and the Zeros of Riemann's Zeta Function. Jour. Phys. A. 2002, to appear.

25.
Daley, D.; Verre-Jones, D., An Introduction to the Theory of Point Processes. Springer-Verlag: New York, 1988. MR 90e:60060

26.
Deift, P., Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach. Courant Lecture Notes #3, NYU/Courant Institute: New York, and Amer. Math. Soc.: Providence, RI, 1999. MR 2000g:47048

27.
Deift, P., Integrable Systems and Combinatorial Theory. Notices, Amer. Math. Soc. 2000, 47, 631-640. MR 2001g:05012

28.
Diaconis, P., Group Representations in Probability and Statistics. Ins. Math. Statist., Hayward, CA, 1986. MR 90a:60001

29.
Diaconis, P., Applications of the Method of Moments in Probability and Statistics. In Moments in Mathematics; Landau, H., Ed.; Amer. Math. Soc.: Providence, RI, 1987; 125-142. MR 89m:60006

30.
Diaconis, P.; Shahshahani, M., Products of Random Matrices as They Arise in the Study of Random Walks on Groups. Contemp. Math. 1986, 50, 183-195. MR 87k:60025

31.
Diaconis, P.; Shahshahani, M., The Subgroup Algorithm for Generating Uniform Random Variables. Prob. Eng. and Info. Sci. 1987, 1, 15-32.

32.
Diaconis, P.; Shahshahani, M., On the Eigenvalues of Random Matrices. In Studies in Applied Probablility; Gani, J., Ed.; Jour. Appl. Probab.: Special Vol. 31A, 1994; 49-62. MR 95m:60011

33.
Diaconis, P.; Evans, S., Linear Functionals of Eigenvalues of Random Matrices. Transactions Amer. Math. Soc. 2001, 353, 2615-2633. MR 2002d:60003

34.
Diaconis, P.; Evans, S., Immanants and Finite Point Processes. Jour. Combin. Th. A. 2000, 91, 305-321. MR 2001m:15018

35.
Diaconis, P.; Evans, S., A Different Construction of Gaussian Fields from Markov Chains: Dirichlet Covariances. Ann. Inst. Henri Poincaré, 2002, to appear.

36.
Diaconis, P.; Freedman, D., A Dozen deFinetti-Style Results in Search of a Theory. Ann. Inst. Henri Poincaré, 1987, 23, 397-423. MR 88f:60072

37.
Diaconis, P.; Eaton, M.; Lauritzan, S., Finite deFinetti Theorems in Linear Models and Multivariate Analysis. Scand. Jour. Statist. 1992, 19, 289-315. MR 94g:60065

38.
Dyson, F., Statistical Theory of the Energy Levels of Complex Systems, I, II, III. J. Math. Phys. 1962, 3, 140-156, 157-165, 166-175. MR 26:1111, MR 26:1112, MR 26:1113

39.
Dyson, F., Correlations Between Eigenvalues of a Random Matrix. Comm. Math. Phys. 1970, 19, 235-250. MR 43:4398

40.
Eaton, M., Multivariate Statistics; Wiley: New York, 1983. MR 86i:62086

41.
Edelman, A.; Kostlan, E.; Shub, M., How Many Eigenvalues of a Random Matrix Are Real? Jour. Amer. Math. Soc. 1994, 7, 297-267. MR 94f:60053

42.
Forrester, P.; Rains, E., Inter-Relationships Between Orthogonal, Unitary and Symplectic Matrix Ensembles. MSRI Publications 2001, 40, 171-207. MR 2002h:82008

43.
Fulman, J., Random Matrix Theory Over Finite Fields. Bull. Amer. Math. Soc. 2002, 39, 51-86. MR 2002i:60012

44.
Fulton, W., Eigenvalues, Invariant Factors, Highest Weights and Schubert Calculus. Bull. Amer. Math. Soc. 2000, 37, 209-249. MR 2001g:15023

45.
Fyodorov, Y.; Khoruzhenko, B.; Sommers, H., Universality in the Random Matrix Spectra in the Regime of Weak Non-Hermiticity. Ann. Inst. Henri Poincaré: Physique Théorique 1998, 68, 440-489. MR 99i:60080

46.
Goldsheid, I.; Khoruzhenko, B., Eigenvalue Curves of Asymmetric Tri-Diagonal Random Matrices. Electronic Jour. Probab. 2000, 5, Paper 16. MR 2002j:82061

47.
Goodman, R.; Wallach, W., Representations and Invariants of the Classical Groups. Cambridge Press: Cambridge, 1998. MR 99b:20073

48.
Grenander, U.; Szegö, G., Toeplitz Forms and Their Applications. University of California Press: Berkeley, 1958. MR 20:1349

49.
Haake, F., Secular Determinants of Random Unitary Matrices. Jour. Pys. A. 1996, 29, 3641-3658. MR 97g:82002

50.
Haake, F., Quantum Signatures of Chaos, 2nd Ed.; Springer-Verlag: Berlin, 2001.

51.
Hanlon, P.; Stanley, R.; Stembridge, J., Some Combinatorial Aspects of the Spectra of Normally Distributed Random Matrices. Contemp. Math. 1992, 138, 151-174. MR 93j:05164

52.
Hirschman, I., The Strong Szegö Limit Theorem for Toeplitz Determinants. Amer. Jour. Math. 1966, 88, 577-614. MR 35:2064

53.
Hughes, C.; Keating, J.; O'Connell, W., On the Characteristic Polynomial of a Random Unitary Matrix. Comm. Math. Phys. 2001, 220, 429-451. MR 2002m:82028

54.
Hughes, C.; Rudnick, Z., Mock-Gaussian Behavior for Linear Statistics of Classical Compact Groups. Department of Mathematics, Tel Aviv University, 2002, preprint.

55.
Johansson, K., On Szegö's Asymptotic Formula for Toeplitz Determinants and Generalizations. Bull. Sc. Math. 1988, 112, 257-304. MR 89m:47021

56.
Johansson, K., On Random Matrices from the Compact Classical Groups. Ann. Math. 1997, 145, 519-545. MR 98e:60016

57.
Johansson, K., The Longest Increasing Subsequence in a Random Permutation and a Unitary Random Matrix Model. Math. Res. Lett. 1998, 5, 63-82. MR 99e:60033

58.
Johnstone, I., On the Distribution of the Largest Eigenvalue in Principal Component Analysis. Ann. Statist. 2001, 29, 295-327. MR 2002i:62115

59.
Katz, N.; Sarnak, P., Random Matrices, Frobenius Eigenvalues, and Monodromy. Amer. Math. Soc.: Providence, RI, 1999. MR 2000b:11070

60.
Keating, J.; Snaith, N., Random Matrix Theory and $\xi (\frac{1}{2} + it)$. Commun. Math. Phys. 2000, 214, 57-89. MR 2002c:11107

61.
Keating, J.; Snaith, N., Random Matrix Theory and $L$-Functions at $s = \frac{1}{2}$. Commun. Math. Phys. 2000, 214, 91-110. MR 2002c:11108

62.
Kiessling, M.; Spohn, H., A Note on the Eigenvalue Density of Random Matrices. Comm. Math. Phys. 1999, 199, 638-695. MR 2000a:82031

63.
Macchi, O., Stochastic Processes and Multicoincidences. IEEE Transactions 1971, 17, 1-7.

64.
Macchi, O., The Coincidence Approach to Stochastic Point Processes. Adv. Appl. Probab. 1975, 7, 83-122. MR 52:1876

65.
MacDonald, I., Symmetric Functions and Hall Polynomials, 2nd Ed.; Clarendon Press: Oxford, 1995. MR 96h:05207

66.
Marchenko, V.; Pastur, L., Distribution of Some Sets of Random Matrices. Mat. Sb. 1967, 1, 507-536.

67.
Mardia, K.; Kent, J.; Bibby, J., Multivariate Analysis. Academic Press: New York, 1979. MR 81h:62003

68.
Mehta, M., Random Matrices, 2nd Ed.; Acad. Press: New York, 1991. MR 92f:82002

69.
Mezzadri, F., Random Matrix Theory and the Zeros of $\xi^\prime (s)$. Dept. of Mathematics, University of Bristol, 2002, preprint.

70.
Muirhead, R., Latent Roots and Matrix Variates: A Review of Some Aymptotic Results. Ann. Statist. 1978, 6, 5-33. MR 56:16919

71.
Odlyzko, A., On the Distribution of Spacings Between Zeros of the Zeta Function. Math. Comp. 1987, 48, 273-308. MR 88d:11082

72.
Odlyzko, A., The $10^{20}$-th Zero of the Riemann Zeta Function and 175 Million of Its Neighbors. ATT Laboratories, 1992, preprint.

73.
O'Connell, N., Random Matrices, Non-Colliding Processes and Queues. Laboratoire de Probabilites, Paris 6, 2002, preprint.

74.
O'Connell, N.; Yor, M., Brownian Analogues of Burke's Theorem. Stoch. Proc. Appl. 2001, 96, 285-304. MR 2002h:60175

75.
Okounkov, A., Random Matrices and Random Permutations. Math. Res. Notices 2000, 20, 1043-1095. MR 2002c:15045

76.
Olshansky, G., An Introduction to Harmonic Analysis on the Infinite-Dimensional Unitary Group. University of Pennsylvania, Dept. of Mathematics, 2001, preprint.

77.
Olshanski, G.; Vershik, A., Ergodic Unitarily Invariant Measures on the Space of Infinite Hermitian Matrices. In Contemporary Mathematical Physics; Amer. Soc. Transl. Ser. 2, 1996, 175, 137-175. MR 98e:28015

78.
Pickrell, D., Mackey Analysis of Infinite Classical Motion Groups. Pacific Jour. 1991, 150, 139-166. MR 92g:22041

79.
Porod, U., The Cut-Off Phenomenon for Random Reflections. Ann. Probab. 1996, 24, 74-96. MR 97e:60012

80.
Rains, E., High Powers of Random Elements of Compact Lie Groups. Probab. Th. Related Fields 107, 219-241. MR 98b:15026

81.
Rains, E., Images of Eigenvalue Distributions Under Power Maps. ATT Laboratories, 1999, preprint.

82.
Rains, E., Probability Theory on Compact Classical Groups., Harvard University: Department of Mathematics, 1991, Ph.D. thesis.

83.
Rosenthal, J., Random Rotations, Characters and Random Walks on SO(N). Ann Probab. 1994, 22, 398-423. MR 95c:60008

84.
Sinai, Y.; Soshnikov, A., Central Limit Theorem for Traces of Large Random Symmetric Matrices with Independent Matrix Elements. Bol. Soc. Brasil. Mat. (N.S.) 1998, 29, 1-24. MR 99f:60053

85.
Sloane, N., Encrypting by Random Rotations. Technical Memorandum, Bell Laboratories, 1983.

86.
Soshnikov, A., The Central Limit Theorem for Local Linear Statistics in Classical Compact Groups and Related Combinatorial Identities. Ann. Probab. 2000, 28, 1353-1370. MR 2002f:15035

87.
Soshnikov, A., Level Spacings Distribution for Large Random Matrices: Gaussian Fluctuations. Ann. Math. 1998, 148, 573-617. MR 2000f:15014

88.
Soshnikov, A., Determinantal Random Point Fields. Russian Math. Surveys 2000, 55, 923-975. MR 2002f:60097

89.
Stanley, R., Enumerative Combinatorics. Vol. 2; Cambridge University Press: Cambridge, 1999. MR 2000k:05026

90.
Tracy, C.; Widom, H., Introduction to Random Matrices. In Geometric and Quantum Aspects of Integrable Systems; Springer-Verlag: Berlin, 1993, 103-130. MR 95a:82050

91.
Tracy, C.; Widom, H., Random Unitary Matrices, Permutations and Painlevé. Comm. Math. Physics 1999, 207, 665-685. MR 2001h:15019

92.
Tracy, C.; Widom, H., On the Relations Between Orthogonal, Symplectic and Unitary Ensembles. Jour. Statist. Phys. 1999, 94, 347-363.

93.
Tracy, C.; Widom, H., Universality of the Distribution Functions of Random Matrix Theory. CRM Proceedings 2000, 26, 251-264. MR 2002f:15036

94.
Tracy, C.; Widom, H., On the Limit of Some Toeplitz-Like Determinants. SIAM J. Matrix Anal. Appl. 2002, 23, 1194-1196.

95.
Voiculescu, D., Lectures on Free Probability Theory. Springer Lecture Notes in Mathematics 2000, 1738, 279-349. MR 2001g:46121

96.
Wieand, K., Eigenvalue Distributions of Random Matrices in the Permutation Group and Compact Lie Groups, Harvard University: Department of Mathematics, 1998, Ph.D. thesis.

97.
Wieand, K., Eigenvalue Distributions of Random Permutation Matrices. Ann. Probab. 2000, 28, 1563-1587. MR 2002d:15027 ]]> 2003 American Mathematical Society Bulletin of the American Mathematical Society Bull. Amer. Math. Soc. bull 40 02 20030212 October 10, 2002 February 12, 2003 155 155-178 24 S0273-0979-03-00975-3 10.1090/S0273-0979-03-00975-3 0273-0979 1088-9485 English 00-02 60B15 2000 http://www.ams.org/jourcgi/jour-getitem?pii=S0273-0979-03-00975-3 Introduction This paper surveys what we know about the distribution of the eigenvalues of typical large unitary matrices. The topic occurs naturally in problems of statistics, physics and number theory. The mathematical interconnections are also fascinating, and it is hard to escape the feeling that there is something unseen to be discovered. To keep the paper within bounds, the following classical compact groups will be featured: list O n the n n real matrices M such that MM T id . U n the n n complex matrices M such that MM id . S n the n n permutation matrices . list Typical elements'' are studied by using Haar measure. This is a probability measure P on a group G which is translation invariant: for any measurable set A in G and any element M in G equation P(A) P(MA). equation For the symmetric group, we all have an intuitive feel for what it means to pick a permutation at random, at least via shuffling cards. For the other groups this is less familiar. The following method for picking a group element at random may help. Consider the orthogonal group O n . Here is a simple algorithm: fill out an empty n n array with independent picks from the standard Gaussian bell-shaped curve. Then perform the Gram-Schmidt algorithm on this array: normalize the first row to have norm one, take the first row out of the second row and normalize to have norm one, and so on. This constructs an orthogonal matrix which is Haar distributed. Put more formally, put product measure on n 2 with each factor having density e -x 2 2 2 . The Gram-Schmidt algorithm gives a map T from almost all of n 2 onto O n . The image of the product measure is Haar measure. This is easy to prove and understand. Each row of the original array has density proportional to e -12x 2 i dx 1dx n . This measure on R n is invariant under orthogonal transformations. By inspection, T(MX) MT(X) where X is the original array. Hence, P(MT(X) A) P(T(MX) A) P(T(X) A) . A more analytical proof can be found in Eaton Eaton . Perhaps more convenient: if an n n matrix of independent Gaussian entries is input to the QR algorithm, the resulting orthogonal piece is Haar distributed. See DiSh1 for a survey of constructions of Haar measure. The same construction works for the unitary group U n using the usual complex inner product. Here the original entries of the array are chosen as independent, standard, complex Gaussian variables with density e - z 2 on C . For any of the groups O n, U n, S n in its standard matrix representation, any element is diagonalizable with all eigenvalues on the unit circle. Call these e i 1 ,, e i n . The main question to be studied is: pick M G from Haar measure; how are e i 1 ,, e i n distributed To begin our study, Figures 1 through 3 show eigenvalues for five independent realizations from O n, U n, S n when n 100 . Also shown for comparison are five realizations of 100 points chosen uniformly and independently on the unit circle. figure bull975el-fig-1-4.eps Figures 1-4: Five realizations for n 100 from Haar measure on O n , U n , S n , and independent uniform points. f:circles figure figure 4 Figures 1 and 2 are similar. Each shows sets of 100 points neatly arranged around the unit circle. There are slight variations, but the points are close to 1 100 apart. A careful look shows the eigenvalues for O n come in complex conjugate pairs. In contrast, Figure 4 shows that completely random points have much greater variability than the eigenvalues of random matrices. Figure 3 corresponds to the symmetric group. It shows neatly arranged points with varying densities. The rest of this paper presents a fairly detailed theoretical understanding of these and more subtle patterns. Before this, let us pose a basic question. center WHO CARES center There are many questions; why study these The next four sections of the paper offer motivation; the eigenvalues appear in applied problems of telephone encryption (Section One) and in routine statistical work (Section Two). They appear in the mathematical understanding of the zeros of Riemann's zeta function (Section Three). They also have remarkable internal properties suggesting study for their own sake (Section Four). Section Five gives a general picture for understanding and proving things about unitary eigenvalues. This uses tools of representation theory. Section Six gives pointers to the literature on topics not covered: other ensembles, free probability, de Finetti-type theorems, largest eigenvalues and much else. As an applied mathematician who is not a physicist, connecting my interests to Gibbs' legacy seemed like an impossible task. Despite my limitations, mathematical physics runs throughout random matrix theory. The physics of the telephone drives the analysis of Section One. Particle scattering directly connects physics and random matrices. Szego's strong limit theorem was proved in answer to a question of Onsager on Ising phase transitions. The first rigorous proof of the equivalence of ensembles for Gibbs' measures can also be understood as a part of random matrix theory. Physics illuminates much of mathematics. We hope for the converse. I thank my coauthors---Dan Bump, Steve Evans and Mehrdad Shahshahani---along with my students---Joe Blitzstein, Marc Coram, Jason Fulman, Eric Rains and Kelly Wieand---for their contributions to this work. Thanks, too, to my random matrix friends---Percy Deift, Kurt Johansson, Alexei Borodin, Neil O'Connell, Andre Okunkov, Craig Tracy and Harold Widom. Telephone encryption My interest in random orthogonal matrices began with an applied problem in telephone encryption. While it is well understood how to cryptographically scramble up bits, telephone encryption must make the scrambling commensurate with the physics of the telephone and be done rapidly enough to permit normal conversation. One scheme due to Aaron Wyner Sloane digitized speech into 8 -bit blocks and treated these as real numbers. Vectors of 256 such blocks can be encrypted by rotating with a 256 256 random orthogonal matrix. This scrambled vector is transmitted, and the receiver decrypts the message by multiplying by the inverse matrix. Keeping the length of the signal constant is crucial to practical encryption of speech. All of this requires a stream of random orthogonal matrices. The Gram-Schmidt procedure previously described takes order n 3 steps to generate an n n matrix. After all, the rows above the i th have to be removed by an inner product of length n . The number of operations is thus of order equation n i 1 in 0(n 3). equation When n 256 , putting in the constants, this algorithm takes approximately 16 10 6 operations and is simply too slow to allow natural speech on the telephone. Neil Sloane suggested that perhaps approximately random orthogonal matrices would be practically as good. He suggested forming an approximately random element of O n by multiplying a few random reflections: matrices of the form I-2uu T with u chosen uniformly on the unit sphere. One can multiply a matrix by a reflection in order n 2 operations. This raised the following problem: how many reflections are required to have an approximately uniform product Preliminary work with Shahshahani DiSh , brilliantly completed by Rosenthal Ros and Porod Porod , shows that 12n n products are necessary and suffice to achieve approximate uniformity. The lower bound of this theorem proceeds as follows: consider a single product I-2uu T . Why isn't this random on its own For one thing, it fixes an n-1 dimensional subspace. Similarly, the product of k reflections fixes an n-k dimensional subspace. Thus if k is not large enough, the trace of the product will be large. This raises the question, how large will the trace of a uniformly chosen element of O n typically be We have finally arrived at an eigenvalue question. Consider a uniformly chosen matrix M O n . Its diagonal entries are small numbers (about size 1 ), and different rows should not be too dependent. The basic central limit theorem of probability says that if you add up a large number of approximately independent random numbers, the sum should be approximately distributed like the bell-shaped curve e -x 2 2 2 . Mallows and I were able to prove this: unnumthm Let M be chosen uniformly in O n . Then, as n tends to , equation P tr ; M x - x - e -t 2 2 2 dt 0, equation uniformly in x . unnumthm This result will be extended and refined in later sections. It implies that no matter how large n is, the trace of a random orthogonal matrix is less than three in absolute value with high probability. Using character theory, it is not hard to show that 12 n n cn random reflections are required to make the trace this small under the convolution measure. Returning to the original telephone encryption problem, the bounds show that 12 n n cn reflections suffice to be close to random. If all that is wanted is the image of a vector following a product of reflections, this is available at cost of order n 2 n (it takes order n steps to multiply a vector by a reflection). This gives a substantial speedup. In summary, for this example, the eigenvalues of random orthogonal matrices came in the back door as a tool for proving lower bounds on running times in an applied problem. Statistics and eigenvalues The earliest manifestations of random matrix theory may be the fluctuation theory of correlations. Statisticians frequently analyze high dimensional data by looking at covariance matrices and their eigen-decompositions into principal components. To explain by example MaKeBi , consider the scores of 100 pupils on 5 math exams through the term. If the i th students' scores are X i (X i1 ,, X i5 ) , then the data matrix X is the 100 5 matrix with the X i as rows. It is natural to look at linear functions of the scores, say, X i 5 j 1 j X ij . The norm one vector which maximizes the variance of the hundred numbers X 1,, X 100 is called the first principal component of X . The vector maximizing variance subject to orthogonality to is the second principal component, and so on. In the example, the first principal component is approximately the average of the five scores, while the second principal component is approximately the difference between the average of the first two tests and the last three tests. Histograms of the data on these first two principal component directions might well be used to assign final grades and assess the progress of the class. If we are to look at the patterns in and , it is natural to ask about their stability. If the data had come out slightly different, would the inferences change much It is not hard to see that the principal components are the eigenvectors of a suitably scaled version of the 5 5 covariance matrix X TX . The variance of the data projected onto the maximizing eigendirections are the eigenvalues. If the data is a sample from a larger population or modelled as stochastic in other ways, understanding fluctuations of the eigenanalysis is random matrix theory. In general, n p data matrices are considered with rows which are independent samples from some fixed population. R. A. Fisher and J. Wishart found the sampling distribution of X TX when the population is Gaussian. In the 1930's, Wilks, Hsu, Girshick and others derived the joint distribution of the eigenvalues and eigenvectors for the Gaussian case. Anderson And and Muirhead Muir give a normal approximation for the eigenvalues when n is large and p is fixed for general distributions for X . The mathematical development, largely due to Alan James, is intimately linked to zonal polynomials, the spherical functions associated to the action of the orthogonal group O(p) on the positive definite matrices. See Mac for details and references. Modern statistical work, as applied in areas such as data mining or search engines, deals also with cases with p large. The empirical distribution of the bulk of eigenvalues of covariance matrices was studied by Marcenko--Pastur MaPa . They showed that if n,p with n p , then equation 1p e.v.nt G(t) equation with G a distribution function having density equation g(t) 2 t (b-t)(t-a) , a t b, a (1- 12) 2, b (1 12) 2. equation These distributions vary considerably in shape with . Following work of Johansson, Johnstone Johnstone derived the fluctuation theory of the extreme eigenvalues for the Gaussian case. He showed that the largest eigenvalue 1 satisfies equation 1 - np np F 1 equation where denotes weak convergence, equation np ( n-1 ) 2 , np ( n-1 ) ( 1 n-1 1 ) 13 equation and F 1 is the Tracy-Widom distribution equation F 1(s) e -12 s q(x) (x-s) q 2 (x) dx , equation where q solves the Painleve equation equation q xq(x) 2q 3(x), q(x) Ai(x) as x. equation Here the scaling is non-classical -- the standard deviation grows with sample size as n 13 . Johnstone has shown that this approximation is useful for n as small as ten. Much of the mathematical work on eigenvalues in statistics was done for Gaussian random variables. Because of the orthogonal invariance of Gaussian vectors, the mathematical development is closely related to the orthogonal group. Useful surveys of available results for Gaussian and more general populations appear in Bai Bai and Muirhead Muir . Connections with the Riemann zeta function There is a surprising, unexplained connection between the eigenvalues of random matrices and the zeros of Riemann's zeta function. We give a brief fresh look at this from a statistical point of view, following joint work with Marc Coram CoDi . Pointers to the large literature are given at the end of the section. For complex s with re (s) 1 the Riemann zeta function is defined by equation (s) n 1 1 n s p (1-1 p s ) -1 equation where the product is over all primes. The zeta function can be continued to the whole complex plane with a simple pole at s 1 . Riemann showed that knowledge of the zeros of (s) would give information about the distribution of primes. It is known that, except for trivial zeros" at -2, -4, -6,, all the zeros are in the critical strip 0 re (s) 1 . Riemann showed that the number of zeros in the strip with imaginary parts between zero and T is equation N(T) 2 2e 0 ( T) as T . equation This means that the zeros get denser higher up with local density 2 at height T . The Riemann hypothesis says that all the zeros are on the critical line re (s) 12 . We next connect the zeros in a neighborhood of the strip at height T to the eigenvalues of typical unitary matrices in U n . To have the same density of eigenvalues as zeros, following an idea of Keating and Snaith KeSn1 , KeSn2 , choose n 2 . In the data to be described below, 50,000 zeros starting at the 10 20 zero are considered. Here T .15 10 20 and n 2 42 . To compare the zeros with eigenvalues, we wrap blocks of 42 zeros around the unit circle. More precisely, given zeros Z 1, Z 2, , Z N of the form Z j 12 i j , with , 1 j N, , form spacing , j j 1 - j . Split the spacings into disjoint groups of size n 1 . Each group of spacings 1, , n is mapped onto the unit circle by taking x j (2 i( j n )) for 1 j n , where j j n 1 n and U is a uniform random variable on 0, 2 chosen independently for each group. When N 50,000 and n 42 this gives about 50,000 43 1190 different wrapped data sets. The claim is that these data sets are distributed like the eigenvalues of matrices chosen from Haar measure on the unitary group U 42 . This well-posed hypothesis was exhaustively tested in CoDi . We present a few of the results here, but the bottom line is that the wrapped zeta data passes virtually all the tests thrown at it. One approach to testing goodness of fit of the wrapped zeta data to unitary eigenvalues is to look at the trace. As explained in the section above equation P n ( M 2 t ) e -t uniformly in t as n . equation For application to the zeta data, n 42 . Work of Johansson, described in fact two of Section Four below, shows that the exponential approximation in (3.3) is remarkably good. figure minipage t .48 -90 bull975el-fig-5 Zeta data f:hist minipage minipage t .48 -90 bull975el-fig-6 Null data f:randhist minipage 1pc minipage t 24pc Figures 5-6: On the left, a histogram of 1190 zeta-function-based norm-squared traces'' with the standard exponential density function superimposed. On the right, a histogram of 1190 independent standard exponential random variables. minipage figure Figure 5 shows a histogram of the 1190 traces" based on the wrapped zeta data with the exponential density imposed. To help the reader calibrate, Figure 6 shows a sample from a true exponential distribution. The two pictures seem interchangeable. More formal tests also show the traces match the exponential distribution remarkably closely. A second test may be based on strange correlations found by Kelly Wieand Wie1 , Wie2 . For 0 a b 2 let X ab (M) be the number of eigenvalues of M satisfying a j b . Because of the neat distribution of eigenvalues, this random quantity has expected value n(b-a) 2 . Wieand shows that equation Y ab X ab -n(b-a) 2 n 2 N(0,1). equation Thus the fluctuations are at a logarithmic level, and the normalized error follows the bell-shaped normal distribution. To understand the limiting process, Wieand calculated the correlation between Y ab , Y cd . She found that in the large n limit equation Corr (Y ab , Y cd ) array lll 0 if (a,b)(c,d) 0 -12 if b c 12 if a c array . equation These are strange correlations. They say that if a, b contains c, d properly, then Y ab , Y cd are approximately independent, while if the two intervals share a single endpoint, the limiting variables have correlation 12 . Experienced probabilists found this surprising. (At first I did not think these correlations were positive definite ) In retrospect, the limiting variables make perfect sense. Suppose each point on the circle is assigned an independent Gaussian variable Z with mean zero and variance 12 . Assign the interval a, b to Z b-Z a . These variables have the correlations reported above. Clearly, if the intervals have distinct endpoints, the variables Z b-Z a and Z d-Z c are independent, while for example: E(Z b-Z a) (Z d-Z b) -12 . This being observed, the obvious question is, where is the white noise" Z hidden in random matrices A lovely, simple answer was given by Hughes et al. HuKeO' . They showed that for each , with M chosen uniformly in U n , equation Z n im ; ; DET (e i -M) ; n 2 equation has a limiting normal distribution with the limits being independent for different . Thus the log characteristic polynomial is approximately normal. Using the principle of the argument, they showed that Wieand's results follow. With all of this background, let us ask if we can find these strange correlations hidden in the zeros of the zeta function. To begin with, Wieand's results are large n limits and here n 42 . A finite sample correlation was calculated by Bump-Diaconis BuDi , with uniform approximation available through Bump-Diaconis-Keller BuDiKe . The correlations for intervals (0, 4) , (, 4 ) are shown in Figure 7. Of course, when 0 , the correlation is one. As varies, the correlation drops, and when 4 (so the intervals share an endpoint) it is -12 . Also shown are the empirical correlations based on the wrapped zeta data. We again see a striking match. The work with Coram reports extensive further testing of both specific features and an omnibus test. The upshot is a remarkable fit between the zeta data and the unitary eigenvalues. The only question to be answered now is, where is the operator figure 90 bull975el-fig-7 Correlations for (0, 4) and (, 4) . Solid line is the theoretical curve for Haar measure on U n . The circles depict the empirical correlations calculated from wrapped zeta data. figure The first connections between zeta zeros and random matrix theory were drawn by Hugh Montgomery following a conversation with Freeman Dyson. Montgomery suggested (and roughly proved) that the pair correlations -- chance of finding a zero at distance x from a first zero -- should match up with the pair correlations of the eigenvalues of stochastic Hermitian matrices (GUE) after suitable density adjustment to make the mean spacing one in both cases. Odlyzko Odlyz1 , Odlyz2 carried out a remarkable study of data from consecutive zeros and eigenvalues. Marvelous new methods were invented for accurate computation of zeros far up. Michael Berry posited remarkable correction terms to the Dyson-Montgomery 2-point correlations, and Odlyzko was able to show an amazing match to zeta data. Much of this work is carefully reviewed in Conrey Conrey , Berry and Keating BeKe and Katz-Sarnak KaSa . In particular, the last authors suggest that random matrix theory works for general families of L -functions. Keating and Snaith KeSn1 , KeSn2 opened a new chapter by suggesting unambiguously that the characteristic polynomial Z(M,) n j 1 (1-e i j- ) was a useful surrogate for the zeta function. They showed that moments of the zeta function along the critical line matched moments of Z(M,) over U n and, in joint work with several sets of coauthors (see e.g. , CKRS ), make remarkable predictions about zeta behavior which matches data and number theoretic heuristics. This has led number theorists to ask even more detailed questions of probabilists. For example, to understand the biggest gap between zeros, one would like to understand the biggest gap between unitary eigenvalues. This is open at this writing. Five surprising facts Another reason for studying the eigenvalues is that the mathematics is surprising and beautiful. The joint probability density for the eigenvalues of a Haar-distributed random matrix in U n is well known as the Weyl denominator formula, equation f 2( 1,, n) 1 (2) nn j k e i j -e i k 2. equation This is a probability density on (0,2) n with respect to product Lebesgue measure. See GoRhWa for the classical derivation. Alas, this elegant, explicit formula is not of much use in understanding the distribution of eigenvalues. All one can see is that f 2 tends to zero as j and k approach each other, so the eigenvalues tend to repel. Physicists write the product as equation e -H( 1 n) with 2, H - j k e i j - e i k equation and invoke statistical physics intuition for a Coulomb Gas" of n repelling electrical particles around a circle. The following theorems make some of this intuition precise, but show there are many surprises hidden in the simple formula (4.1). factone This can be seen visually in Figure 2. To interpret the mathematical statement below, note two things: First, the sum of n complex numbers equally spaced around the unit circle is zero. Second, the sum of n complex numbers put on the unit circle at random (independently and uniformly) is of order . This follows from the classical central limit theorem of probability theory. In joint work with Mallows Diaconis we proved: factone unnumthm For M chosen from Haar measure, n large and any ball B , equation P (M) B B - z 2 dz. equation unnumthm Here the trace is not divided by , so the eigenvalues practically cancel out. If B r is the ball in centered at zero with radius r , the right side of (4.3) equals 1 - e -r 2 . I still find it mysterious, looking at (4.1) and asking how the cancellation occurs. Of course, things do not cancel perfectly. Wieand's theorem described in Section Three above shows that the number of eigenvalues in a fixed interval of the unit circle is n times the interval's length, plus fluctuations of order n . facttwo Consider the error term in the Gaussian approximation to the trace at (4.3). Johansson Johan2 proved: facttwo unnumthm There are universal constants c, 0 such that equation P M B - B - z 2 dz n n equation uniformly in Borel sets B . unnumthm People used to the usual error terms in probability find this result fantastic; for the classical central limit theorem for the sum of n points randomly put on the unit circle, the error is of order n . Here, the error is super-exponential. Two closely related findings: (a) The moments of the trace equal the normal moments equation ( ; M) a ; ;() b ; dM z a ; b ; - z 2 ; dz. equation The equality (4.4) for all integers a, b smaller than n is joint work with Colin Mallows, which is discussed at length in Section Five below. (b) An analogous result is proved for the trace of a random permutation matrix. unnumthm For , a uniformly chosen permutation matrix gather P ; ; ; ; B - P ;(B) 2 n (n 1) with P (B) 1e iB 1 i for B 1, 2, 3, . gather unnumthm In summary, the first thoughts suggesting a Gaussian limit for the trace were that the trace is the sum of a lot of small, approximately uncorrelated random terms. While this is true, there is some mysterious global constraint that forces the high order contact with the Gaussian law. factthree In investigating the fine structure of the eigenvalues, traces of higher powers are studied. In joint work with Shahshahani DiSh1 discussed in Section Five below, we proved: factthree unnumthm For M chosen from Haar measure on U n , for j fixed and n , equation P (M j) ; ; B P ; Z ; ;B equation with Z a standard complex Gaussian variable. unnumthm As j increases, Z becomes more spread out. Eric Rains Rai1 proved that a kind of phase transition occurs for j n . unnumthm Let M be chosen from Haar measure on U n . For any n , and any j n , the eigenvalues of M j are exactly distributed as n points chosen independently and uniformly on the unit circle. unnumthm Thus high powers of M have no structure in their eigenvalues. The trace of M n is approximately Gaussian, but with error 1n. I find the contrast between facts one, two and three unsettling. I still have no mental picture that explains how these can all hold. I have tried to think about generating Haar-distributed eigenvalues by putting down n uniform points independently and taking appropriate n th roots. Rains' result can be demystified slightly by computation: The joint mixed moments of the eigenvalues of M j are equation n k 1 e ij k(b k-a k) ;f 2( 1,, k) ; d 1,,d n. equation Expanding f 2 from (4.1) as a polynomial, we see that for jn we get zero unless b k a k for 1 k n . These are just the joint mixed moments for independent uniform points. Rains Rai1 proved similar results for all the classical compact Lie groups. There is a subtlety here. Take the orthogonal group O 2n . The eigenvalues come in conjugate pairs, and this is preserved for powers. Rains shows that for suitably large j the eigenvalues of M j are exactly distributed as n random points and their conjugates. Some light on these strange doings follows from work of Forrester-Rains FoRa , Haake Haake1 and Rains Rai2 . For simplicity, consider M chosen from Haar measure on U 2n . They prove that for all n , the eigenvalues of M 2 are exactly distributed as the union of two independent sets of eigenvalues from M 1, M 2 chosen from Haar measure on U n . Similarly, the eigenvalues of M 3U 3n are exactly distributed as the union of eigenvalues of M 1, M 2, M 3 independently chosen in U n . Their final result has no divisibility requirements and applies for all powers j . It shows that the eigenvalues of M n U n are exactly distributed as independent points from U 1 . These extra facts compound the mystery. factfour factfour The foundations of random matrix theory were laid out in a great series of papers by Dyson Dyson1 , Dyson2 , who labeled the unitary ensemble CUE (Compact Unitary Ensemble). Dyson showed that the marginal distribution of n eigenvalues has a neat form. Physicists call these n -point correlations" for mysterious historical reasons (they are not correlations ). Thus f 2 from (4.1), which could be written f n 2 , is the n -point distribution. Informally, f k 2 ( 1,, k) is the probability density for an eigenvalue in d 1, d 2,,d k from a Haar-distributed matrix in U n . The elegant fact (due to Dyson) is a simple, closed-form formula: equation f k 2 ( 1 k) DET ( (n( a- b)) ( a- b) ) 1 a,bk. equation For example, f 1 Constant, f 2 1-( n( 1 - 2) ( 1- 2) ) 2. Maachi Ma1 , Ma2 created a general theory for point processes with k -point distributions having determinental form. See Daley-Verre-Jones DaVe for a concise and very readable treatment of point processes and Macchi's work. Soshnikov Sosh3 gives a marvelous survey showing how surprisingly many ensembles admit neat determinental forms, and how a wide variety of limit theorems can be proved from these forms. Following work of Macchi, Diaconis-Evans DiEv2 survey developments where determinants are replaced by permanents or immanents. factfive factfive I find the following connection surprising. Shahshahani and I proved that if M is chosen from Haar measure on U n , the trace of successive powers has limiting Gaussian distributions. As n , for any fixed k and Borel sets B 1,,B k equation P (M B 1,, M k B k) ; k j 1 ; P( ,Z B j) equation with Z a standard complex Gaussian variable. In a seemingly very different sphere, G. Szego derived the limiting asymptotics for the eigenvalues of Toeplitz matrices. This is a rich subject, and I will not try to develop it in detail. Bottcher and Silbermann BoSi is a remarkably good introduction. Briefly, a Toeplitz matrix is an nn matrix with complex entries which are constant down the main diagonals, such as array cccc a b c d e a b c f e a b g f e a array Szego determined the asymptotics of the determinants of a sequence of Toeplitz matrices T n(g) constructed with (j,k) entry (j-k) where (m) 1 2 2 0 g(e im ) ;d is the Fourier transform of a function on the unit circle. unnumthm Strong-Szego equation Let g(e i ) e f(e i ) with - ;(k) 2 k . equation Then equation DET ;T n(g) e n(0) k 1 f(k)f(-k)k o(1) . equation unnumthm Szego's theorem has dozens of variations and applications from time series and electrical engineering to the first proof of phase transitions in the Ising model. Grenander-Szego GrSz is a classical, readable overview of this material, as is Chapter Five in Bottcher-Silbermann BoSi . The point of the present presentation is that (4.6) and (4.7) seem completely unconnected, and yet they are easily equivalent. The key connection is a classical determinant identity of Heine and Szego. unnumprop For f as above and g e f(e i ) , equation 1 (2) n 2 0 2 0 n j 1 ; e f(e i j ) ; 1 ; a ; b ; n e i a - e i b 2 ; d 1d n ; T n(g). equation unnumprop It is not hard to see this directly; expand the determinant on the right side as a sum of products of n terms. Each term is a Fourier transform, and so the product is an n -fold integral of the same form as the left side. Recognizing a Vandermonde and elementary manipulations complete the proof. Alternatively, in joint work with Bump BuDi , we have shown that (4.8) follows from the classical Jacobi-Trudi identity of symmetric function theory. With (4.8) established we can now see the equivalence of (4.6) and (4.7). Begin with (4.6). This is a limit theorem for the traces. Passing to Fourier transforms, let equation f(e i ) k j 1 a j ; (j) b j ; (j). equation Then, for MU n with eigenvalues e i 1 ,,e i n equation a 1 re ; (M) b 1 im ; (M) a k ; re ; (M k) b k im ; (M k) n j 1 f (e i j ). equation We will use a j, b j as transform variables. Noting next that the transform of a Gaussian variable Z (X i Y) is equation e (ax by) - x 2 - y 2 dxdy e 4(a 2 b 2) , equation we see that the limiting normality of (4.6) is equivalent to convergence of the transforms equation 1 (2) n n j 1 e f(e i 1 ) 1j k n e i j - e i k 2 d 1d n ( k j 1 4 (a 2 j b 2 j)) . equation This is just Szego's theorem for the trigonometric polynomial f . Thus Szego's theorem implies (4.6). Conversely, (4.6) shows the Fourier transforms converge, and so Szego's theorem holds for trigonometric polynomials. It is not hard to pass to the limit and derive the result for general f . There are many proofs of Szego's theorem in the references above. Johansson Johan1 gives a careful development of the asymptotic analysis required to go from polynomials to more general functions. The present approach leads to straightforward generalizations in two directions. First, the limiting normality of traces of powers for other groups such as O n or SP 2n gives Szego-type theorems for determinants with entries the coefficients of expansions in Jacobi polynomials. To be fair, these are classically known Hirsh . A second generalization was determined in joint work with Bump BuDi . This gives asymptotics for the determinants of Toeplitz minors. These seem new, but closely related work has been done by Tracy-Widom TrWi5 . Here is a simple example. Let be a partition of m . Define the Toeplitz minor equation T n (g) det ; (( i - i j) 1i, , j n . equation Then, for fixed and n , and g e f as in (4.7) equation T n (g) T n (g) 1 m S m x () k 1 (k (k)) n() . equation Here the sum is over the symmetric group S m , x () is the irreducible character associated to , and n() is the number of cycles of length k in . The minor T n (g) is obtained from the original Toeplitz matrix by striking the first 1 columns, keeping the first row but striking the next 1 - 2 rows, keeping the next row and so on. For example, when (1) the minor is obtained by striking the first column and the second row, and the right side is (1) . It seems strange that characters appear. See BuDi for extensions. A third benefit of the present approach: it offers some explanation for the form k 1 k (k) (-k) in the Szego corrections. The k appears because var (M k) k. I do not want to leave this area without pointing to a beautiful related development due to Estelle Basor. She has derived the limit theory for the spectrum of a variety of operators of Hankel, Toeplitz and mixed-type in sweeping generality. Her results are paired with Gaussian limit theorems of the same flavor as those of this section. A readable survey with extensive references is in Basor , Basor1 . I do not feel we understand the parallel between (4.6) and (4.7). The determinant identity seems like a magic trick A general approach A general approach to studying unitary eigenvalues has gradually been developed. This begins in joint work with Mallows Diaconis and Shahshahani DiSh1 . The present refined account was developed with Steve Evans DiEv1 . For M n U n with eigenvalues e i j , let n be the measure on the unit circle T which puts mass one at each eigenvalue. We may study n via linear, quadratic, , functionals. Thus if f:T C has Fourier expansion f(e i ) j j e ij equation n(f) n j 1 f(e i j ) n 0 j 1 j (M j n) j 1 -j ; (M j n) . equation The key to studying such functionals is an explicit formula for the joint mixed moments of the traces. It was proved in joint work with Evans and Shahshahani. unnumprop (a) Consider a (a 1,,a k) and b (b 1,, b k) with a j, b j 0,1,2, . Let Z 1, Z 2,, Z n be independent standard complex normal random variables. Then, for n max ( k 1 ja j, k 1 jb j) gather U n k j 1 (trM j n) a j (M j n) b j dM n ab k j 1 j a j a j E ( k j 1 ( j) a j (j j) b j ). gather (b) For any j, k, ; (M j n) ; (M k n) dM n jk ; min ;(j,k). unnumprop The proof of this proposition is basic Schur-Weyl duality. First, introduce the power sum symmetric functions P j (x 1, , x n) x j 1 x j n and for a partition of some integer K with a i parts equal to i , let P j P j a j . Since M j n P j (e i 1 , , e i n ) , the left side in (a) is P , P for the inner product given by integration over U n . The power sums form a basis for the homogeneous symmetric polynomials of degree K in x 1, , x n . A second basis is given by the Schur functions s . All needed properties are in MacDonald Mac or Stanley Stan . The two key properties for present purposes are: (5.2) Orthogonality: s , s () n for any partitions , with () the number of parts in . (5.3) Schur-Weyl Duality: For any partition of K , equation P K s equation where the sum is over partitions of K , and is the irreducible character of the symmetric group S K associated with on the th conjugacy class. Using these formulae we simply compute: If is a partition of K and is a partition of L , gather P , P K s , L r s KL K (()n). gather When Kn , all partitions of K appear and the second orthogonality relation for characters shows our expression equals equation KL K j 1 j a j a j ab j a j a j equation This last equals the joint mixed moments of j by an easy calculation. This proves (a) . To prove (b) , observe that the calculation above gives, for any j, k , equation (M j n) (M k n) dM n jn j (j) 2 (() n). equation Here (j) is the character of a j -cycle. These are explicitly known. They are zero unless is a hook shape and (-1) ()-1 if is a hook shape. Now (b) follows. The proposition shows that (M j n) behaves asymptotically like Z j , and one can then plug into Fourier series expansions. My work with Evans exploits this carefully for a variety of functionals. Of course, care is needed in bounding the tail of these sums and that is where (b) comes in. Here is one carefully stated example: Let ; H 12 2 denote the space of functions f in L 2(T) such that f 2 12 j j 2 j . For example, f(z) z j H 12 2 ; H 12 2 is precisely the functions such that (n) Z n converges almost surely, where Z n are independent, standard, complex Gaussian variables. unnumprop If f 1, f 2, , f k H 12 2 with i(0) 0 , 1i k , then the random vector ( n (f 1), , n (f k)) converges in distribution to a jointly normal, centered random vector (V 1, V 2, , V k) with E(V a V b) f a, f b 12 . unnumprop This proposition shows there is a limiting Gaussian field indexed by H 12 2 naturally associated with unitary eigenvalues. As discussed in Diaconis-Evans DiEv1 , DiEv3 , the Hilbert space H 12 2 of 12 differentiable functions" or functions of finite energy" appears in many contexts, and it is natural to seek an explanation for its appearance here. This is lacking at present. Let P M n (Z) det (M n - Iz) be the characteristic polynomial of M n U n . Then P M n P M n n j 1 (z - e i j ) -1 j 1 (M j n) z j . From the proposition, this random power series converges in distribution to the random analytic function equation G(z) j 1 Z j z j z 1 equation where the Z j are independent, standard Gaussian random variables. With a bit more work, one can check that this convergence occurs in the space of continuous -valued functions on z : z 1 in the topology of uniform convergence on compacts. Random analytic functions like G have been intensely studied, and one can show that G takes all values in infinitely, often with probability one. More precise statements are in DiEv1 . Figure 8 shows a plot of the size of P M n P M n for a single random choice of M n when n 100 . The zeros show up as the tree-like shape, and the original eigenvalues show up as the crosses on the unit circle. Figure 9 shows a similar plot of G(z) . Similar tree-like shapes appear when the plots are based on the zeta zeros as explained in Section Three. This section shows how functions of the eigenvalues can be studied using traces. The method works for non-smooth functions such as the number of eigenvalues in an interval and for functions of several eigenvalues. There are other approaches available as well. Soshnikov Sosh1 gives a determinental expression for the Laplace transform of a linear statistic and uses it to derive Gaussian limits such as the proposition above. Hughes and Rudnick HuRu use Soshnikov's method to derive non-Gaussian limit theorems for the number of eigenvalues in intervals of length 1 n . Adler and Van Moerbeke AdVan , AdShVM , AdShVM1 have studied the eigenvalues by studying the joint Laplace transform of the traces of all powers. They show the transform satisfies a hierarchy of non-linear equations with Virasoro constraints, similar to the well-studied Toda lattice. This puts them into the well-studied territory of integrable systems, and some of the remarkable tools developed there can be used to get novel asymptotics and even simple recursions for quantities, like the distribution of the length of the longest increasing sequence in a random permutation. The eigenvalues can also be studied by looking at the joint distribution of the coefficients of the characteristic polynomial. This is instituted in Haake Haake1 . Of course, the coefficients are just the elementary symmetric functions in the eigenvalues, and the traces are the power sum symmetric functions. Change of basis formulae between these two sets of symmetric functions give some information. For example, Alex Gamburd and I have shown that the k th moment of the j th coefficient equals the number of k k magic squares" with all row and column sums equal to j . Nonetheless, the coefficients of the characteristic polynomial are less tractable than the traces -- the limiting distribution of e.g., the middle coefficient, is not known at this writing. figure t -90 scale .46 bull975el-fig-8 A realization of P M n P M n for M n drawn from Haar on U n and n 100 is depicted here. The grayscale indicates the of the absolute value of real part of this function. figure figure h -90 scale .46 bull975el-fig-9 A realization of the random analytic function G(z) (truncated to 1000 terms) is depicted here. The grayscale indicates the of the absolute value of real part of this function. figure Some topics not covered I want to point readers to three rich, related areas. The first enumeration" sets the present topic in a much broader context: study a group through understanding what typical elements" look like. The second free probability" is a growing set of tools to answer questions like: Suppose you know the eigenvalues of each of two symmetric matrices. For typical matrices, what can you say about the eigenvalues of their sum " The third topic describes a different application of random matrix theory to de Finetti's theorem in statistics and the equivalence of ensembles. To keep with the title of this section, the treatment is brief. Enumeration One way of understanding a group is to ask about the properties of typical elements. For the symmetric group S n this is actively developed as the subject of permutation enumeration. Thus consider the following questions: Pick w S n at random: itemize How many fixed points does w have How many cycles What is the length of the longest cycle What is the order of w (smallest k so w k 1 ) itemize All of these questions only depend on w through its conjugacy class -- they are invariant under irrelevant relabeling. The results are given in terms of the proportions of permutations: itemize P FP(w) j 1e 1 j O ( 2 n n ) Monmort ; (1708) P ; cycles - (n) n x x - e -t 2 2 ; dt 2 Goncharov ; (1942) AV ; length ; of ; longest ; cycle ; is ; cn ; with ; c .624... Shepp-Lloyd ; (1966) P order (w) - (n) 2 2 ((n) 3) 32 x x - e -t 2 2 dt 2 Erdos-Turan ; (1965) itemize These theorems give a good feel for the behavior of typical permutations. Related questions also arise in practical statistical problems Diac and in the analysis of the running time of computer algorithms. The results on the length of the longest cycle explain the fluctuations in the density of Figure 3 above. As an abstraction, let G be a finite or compact group. Pick g G from the uniform distribution. One may ask for the limiting distribution of the conjugacy class containing g . All of the problems discussed in the bulk of this paper are of this type. Indeed, two unitary matrices are conjugate if and only if they have the same eigenvalues. Of course, put this bald way, the question seems strange. It is an empirical fact that the general question seems to lead to elegant mathematics which has surprisingly useful consequences. A marvelous survey, making just these points and verifying them on finite groups of Lie type, is given in Fulman Fullman . With all this evidence, what are you waiting for Go get a group you'd like to learn about and try a simple case. Eigenvalues of typical conjugates How are the eigenvalues of a sum of symmetric matrices related to the eigenvalues of the summands Of course, the traces add up, and an amazing host of further inequalities are satisfied. The exact determination of these inequalities is a great achievement of modern mathematics. Fulton Fulton gives an inspiring account. These theorems give extreme or worst case bounds. The calculus of free probability may be presented as the typical case answer. Thus let 1, 2 be real symmetric matrices with eigenvalues 1 , , n , 1, , n . Conjugate 1 and 2 by randomly chosen orthogonal matrices. The eigenvalues of the sum will now be random, and their distribution can be described via the free convolution of and . Here is a specific example drawn from the splendid introduction of Biane Biane . Let n 2m be even. Choose an m -dimensional subspace at random (uniformly) and let 1 be the matrix for projection onto this subspace. Thus, 1 has m zero eigenvalues and m eigenvalues equal to one. Let 2 be independently formed in a similar way. How are the eigenvalues of 1 2 distributed Free probability shows that for large n , equation P ; e.v. ( 1 2) n x x 0 1 t (1-t) dt. equation This striking result is the tip of a remarkable set of results and tools which are rapidly becoming a major area of probability and functional analysis. Free probability was created by Dan Voiculescu to answer questions in Von Neumann algebras. It is not known if the Von Neumann algebras associated to the free groups on 2-generators and on 3-generators are isomorphic. Voiculescu hoped to introduce an entropy-like invariant to distinguish these cases. Voiculescu's summary Voi is replete with many pointers to the huge emerging literature. Beyond eigenvalues The eigenvalues capture the coordinate-free aspects of a matrix. A different set of properties is captured by the actual matrix entries. Consider the following result: unnumthm E. Borel Pick from the uniform distribution on the orthogonal group O n . Then equation P , 11 x x - e -t 2 2 dt. equation unnumthm Borel Borel proved the result in studying Equivalence of Ensembles" in statistical mechanics. There, the microcanonical distribution" is a suitable uniform distribution U(dx) on the constant energy surface x N:H(x) h . One can predict properties by calculating averages as f (x) U (dx) . Maxwell, Boltzmann and Gibbs also considered a canonical measure U (dx) Z -1 e -H(x) dx on N with chosen so H(x) U (dx) h . The equivalence of ensembles asserts that (under conditions) equation f(x) ; U(dx) f(x) ; U (dx), equation when N is large. Borel took the simplest case: H(x) x 2 1 x 2 N . Then the microcanonical measure becomes uniform on the sphere, and the canonical measure becomes product Gauss measure. Taking f to be a continuous function depending only on x 1 and using the fact that the first row of a random orthogonal matrix is Haar-distributed show that the stated theorem on matrices gives a version of equivalence of ensembles. Borel himself, followed by Paul Levy and others, extended the result to functions depending on many coordinates. In joint work with D'Aristotle, Eaton, Freedman, Lauritzan and Newman, this result has been extended and applied to give a variety of results in mathematical statistics d'ADiNe , DiFr , DiEaLa . The results show that in a suitable sense, the entries , i,j are jointly distributed as independent standard Gaussian variables. While this is true in a suitable sense (arbitrary linear combinations), it is not true for the eigenvalues. The eigenvalues of ; O n lie on the unit circle. The eigenvalues of a matrix of independent Gaussian variables fill out the disc with radius uniformly, with order on the real axis Bai , EdKoSh . Determining the right class of functions for equivalence of ensembles is still an open problem. The behavior of the matrix entries under conjugation by a random unitary matrix has been studied by Pickrell Pick , Olshansky-Vershik OlVe , and Borodin-Olshansky BoOl . Their interest is in the representation theory of the injective limit U () . Results are often proved by passage to the limit from U(n) . Their elegant results are too rich to state completely, but for a broad class of examples, the resulting conjugation is approximately a constant times the identity when the dimension is large. Topics really not covered The present paper is based on my Gibbs Lecture but incorporates a few recent developments. The field of random matrix theory has had an explosive growth. Much of this has been on the distribution of the largest eigenvalue of random symmetric or Hermitian matrices. There have been many fine surveys. The work of Baik-Deift-Johansson on an integrable systems approach to largest eigenvalues and the longest increasing subsequence of a random permutation is surveyed in Dei2 . The work of Tracy-Widom on a wide variety of random matrix results and applications using Painleve transcendents is surveyed in TrWi1 , TrWi2 and TrWi3 , TrWi4 . The work of Adler-Van Moerbeke linking random matrices to Virasoro algebras and much else is surveyed in AdShVM1 . For work of Okounkov, connecting random matrices and random permutations through Riemann surfaces, see Okou . A wonderful connection between classical queuing theory, tableaux combinatorics and random matrix theory has been developed by Bougerol-Jeulin BoJe and by O'Connell-Yor O'Con2 . I have not really touched on the physical applications of random matrix theory, though Mehta Mehta and Bohigas et al. BoGi give extensive pointers. Similarly, I lament not describing the many interactions with algebraic combinatorics. See AlDi , Fullman , HaSt . Many of the results stated here for unitary matrices are universal", applying to many other matrix ensembles (just as the central limit theorem): see Tracy-Widom TrWi4 for an overview of the many great results. I have focused on eigenvalues of unitary or Hermitian matrices. There are remarkable probabilistic theorems for non-Hermitian matrices. See Bai and FyKhSo , GoKh for pointers. I hope I have given a picture of a thriving zoo with a wealth of novel findings that touch many areas of pure and applied mathematics.