An introduction to random matrices Greg W.Anderson University of Minnesota Alice Guionnet ENS Lyon Ofer Zeitouni University of Minnesota and Weizmann Institute of Science CAMBRIDGE UNIVERSITY PRESS
An Introduction to Random Matrices Greg W. Anderson University of Minnesota Alice Guionnet ENS Lyon Ofer Zeitouni University of Minnesota and Weizmann Institute of Science
Contents Preface page xiii 1 Introduction 1 2 Real and Complex Wigner matrices 6 2.1 Real Wigner matrices:traces,moments and combinatorics 6 2.1.1 The semicircle distribution,Catalan numbers,and Dyck paths 1 2.1.2 Proof#1 of Wigner's Theorem 2.1.1 10 2.1.3 Proof of Lemma 2.1.6:Words and Graphs 11 2.1.4 Proof of Lemma 2.1.7:Sentences and Graphs 17 2.1.5 Some useful approximations 21 2.1.6 Maximal eigenvalues and Furedi-Komlos enumeration 23 2.1.7 Central limit theorems for moments 29 2.2 Complex Wigner matrices 35 2.3 Concentration for functionals of random matrices and logarithmic Sobolev inequalities 38 2.3.1 Smoothness properties of linear functions of the empirical measure 38 2.3.2 Concentration inequalities for independent variables satisfying logarithmic Sobolev inequalities 39 2.3.3 Concentration for Wigner-type matrices 42 2.4 Stieltjes transforms and recursions 43 vii
Contents Preface page xiii 1 Introduction 1 2 Real and Complex Wigner matrices 6 2.1 Real Wigner matrices: traces, moments and combinatorics 6 2.1.1 The semicircle distribution, Catalan numbers, and Dyck paths 7 2.1.2 Proof #1 of Wigner’s Theorem 2.1.1 10 2.1.3 Proof of Lemma 2.1.6 : Words and Graphs 11 2.1.4 Proof of Lemma 2.1.7 : Sentences and Graphs 17 2.1.5 Some useful approximations 21 2.1.6 Maximal eigenvalues and F¨uredi-Koml´os enumeration 23 2.1.7 Central limit theorems for moments 29 2.2 Complex Wigner matrices 35 2.3 Concentration for functionals of random matrices and logarithmic Sobolev inequalities 38 2.3.1 Smoothness properties of linear functions of the empirical measure 38 2.3.2 Concentration inequalities for independent variables satisfying logarithmic Sobolev inequalities 39 2.3.3 Concentration for Wigner-type matrices 42 2.4 Stieltjes transforms and recursions 43 vii
viii CONTENTS 2.4.1 Gaussian Wigner matrices 46 2.4.2 General Wigner matrices 47 2.5 Joint distribution of eigenvalues in the GOE and the GUE 51 2.5.1 Definition and preliminary discussion of the GOE and the GUE 51 2.5.2 Proof of the joint distribution of eigenvalues 54 2.5.3 Selberg's integral formula and proof of(2.5.4) 59 2.5.4 Joint distribution of eigenvalues-alternative formu- lation 65 2.5.5 Superposition and decimation relations 66 2.6 Large deviations for random matrices 71 2.6.1 Large deviations for the empirical measure 72 2.6.2 Large deviations for the top eigenvalue 82 2.7 Bibliographical notes 86 w Hermite polynomials,spacings,and limit distributions for the Gaus- sian ensembles 91 3.1 Summary of main results:spacing distributions in the bulk and edge of the spectrum for the Gaussian ensembles 91 3.1.1 Limit results for the GUE 91 3.1.2 Generalizations:limit formulas for the GOE and GSE 94 3.2 Hermite polynomials and the GUE 95 3.2.1 The GUE and determinantal laws 95 3.2.2 Properties of the Hermite polynomials and oscillator wave-functions 100 3.3 The semicircle law revisited 103 3.3.1 Calculation of moments of Ly 103 3.3.2 The Harer-Zagier recursion and Ledoux's argument 105 3.4 Quick introduction to Fredholm determinants 108 3.4.1 The setting,fundamental estimates,and definition of the Fredholm determinant 108 3.4.2 Definition of the Fredholm adjugant,Fredholm resolvent,and a fundamental identity 111
viii CONTENTS 2.4.1 Gaussian Wigner matrices 46 2.4.2 General Wigner matrices 47 2.5 Joint distribution of eigenvalues in the GOE and the GUE 51 2.5.1 Definition and preliminary discussion of the GOE and the GUE 51 2.5.2 Proof of the joint distribution of eigenvalues 54 2.5.3 Selberg’s integral formula and proof of (2.5.4) 59 2.5.4 Joint distribution of eigenvalues - alternative formulation 65 2.5.5 Superposition and decimation relations 66 2.6 Large deviations for random matrices 71 2.6.1 Large deviations for the empirical measure 72 2.6.2 Large deviations for the top eigenvalue 82 2.7 Bibliographical notes 86 3 Hermite polynomials, spacings, and limit distributions for the Gaussian ensembles 91 3.1 Summary of main results: spacing distributions in the bulk and edge of the spectrum for the Gaussian ensembles 91 3.1.1 Limit results for the GUE 91 3.1.2 Generalizations: limit formulas for the GOE and GSE 94 3.2 Hermite polynomials and the GUE 95 3.2.1 The GUE and determinantal laws 95 3.2.2 Properties of the Hermite polynomials and oscillator wave-functions 100 3.3 The semicircle law revisited 103 3.3.1 Calculation of moments of L¯N 103 3.3.2 The Harer–Zagier recursion and Ledoux’s argument 105 3.4 Quick introduction to Fredholm determinants 108 3.4.1 The setting, fundamental estimates, and definition of the Fredholm determinant 108 3.4.2 Definition of the Fredholm adjugant, Fredholm resolvent, and a fundamental identity 111
CONTENTS 车 3.5 Gap probabilities at 0 and proof of Theorem 3.1.1. 116 3.5.1 The method of Laplace 117 3.5.2 Evaluation of the scaling limit-proof of Lemma 3.5.1 119 3.5.3 A complement:determinantal relations 122 3.6 Analysis of the sine-kernel 123 3.6.1 General differentiation formulas 123 3.6.2 Derivation of the differential equations:proof of Theorem 3.6.1 128 3.6.3 Reduction to Painleve V 130 3.7 Edge-scaling:Proof of Theorem 3.1.4 134 3.7.1 Vague convergence of the rescaled largest eigen- value:proofof Theorem 3.1.4 135 3.7.2 Steepest descent:proof of Lemma 3.7.2 136 3.7.3 Properties of the Airy functions and proofof Lemma 3.7.1 141 3.8 Analysis of the Tracy-Widom distribution and proof of Theorem 3.1.5 144 3.8.1 The first standard moves of the game 146 3.8.2 The wrinkle in the carpet 147 3.8.3 Linkage to Painleve II 148 3.9 Limiting behavior of the GOE and the GSE 150 3.9.1 Pfaffians and gap probabilities 150 3.9.2 Fredholm representation of gap probabilities 158 3.9.3 Limit calculations 163 3.9.4 Differential equations 172 3.10 Bibliographical notes 183 4 Some generalities 188 4.1 Joint distribution of eigenvalues in the classical matrix ensembles 189 4.1.1 Integration formulas for classical ensembles 189 4.1.2 Manifolds,volume measures,and the coarea formula 195
CONTENTS ix 3.5 Gap probabilities at 0 and proof of Theorem 3.1.1. 116 3.5.1 The method of Laplace 117 3.5.2 Evaluation of the scaling limit – proof of Lemma 3.5.1 119 3.5.3 A complement: determinantal relations 122 3.6 Analysis of the sine-kernel 123 3.6.1 General differentiation formulas 123 3.6.2 Derivation of the differential equations: proof of Theorem 3.6.1 128 3.6.3 Reduction to Painlev´e V 130 3.7 Edge-scaling: Proof of Theorem 3.1.4 134 3.7.1 Vague convergence of the rescaled largest eigenvalue: proof of Theorem 3.1.4 135 3.7.2 Steepest descent: proof of Lemma 3.7.2 136 3.7.3 Properties of the Airy functions and proof of Lemma 3.7.1 141 3.8 Analysis of the Tracy-Widom distribution and proof of Theorem 3.1.5 144 3.8.1 The first standard moves of the game 146 3.8.2 The wrinkle in the carpet 147 3.8.3 Linkage to Painlev´e II 148 3.9 Limiting behavior of the GOE and the GSE 150 3.9.1 Pfaffians and gap probabilities 150 3.9.2 Fredholm representation of gap probabilities 158 3.9.3 Limit calculations 163 3.9.4 Differential equations 172 3.10 Bibliographical notes 183 4 Some generalities 188 4.1 Joint distribution of eigenvalues in the classical matrix ensembles 189 4.1.1 Integration formulas for classical ensembles 189 4.1.2 Manifolds, volume measures, and the coarea formula 195
CONTENTS 4.1.3 An integration formula of Weyl type 201 4.1.4 Applications of Weyl's formula 208 4.2 Determinantal point processes 217 4.2.1 Point processes-basic definitions 217 4.2.2 Determinantal processes 222 4.2.3 Determinantal projections 225 4.2.4 The CLT for determinantal processes 229 4.2.5 Determinantal processes associated with eigenvalues 230 4.2.6 Translation invariant determinantal processes 234 4.2.7 One dimensional translation invariant determinantal processes 239 4.2.8 Convergence issues 243 4.2.9 Examples 245 4.3 Stochastic analysis for random matrices 250 4.3.1 Dyson's Brownian motion 251 4.3.2 A dynamical version of Wigner's Theorem 264 4.3.3 Dynamical central limit theorems 275 4.3.4 Large deviations bounds 279 4.4 Concentration of measure and random matrices 284 4.4.1 Concentration inequalities for Hermitian matrices with independent entries 284 4.4.2 Concentration inequalities for matrices with non independent entries 289 4.5 Tridiagonal matrix models and the B ensembles 305 4.5.1 Tridiagonal representation of B ensembles 305 4.5.2 Scaling limits at the edge of the spectrum 309 4.6 Bibliographical notes 320 5 Free probability 325 5.1 Introduction and main results 326 5.2 Noncommutative laws and noncommutative probability spaces 328
x CONTENTS 4.1.3 An integration formula of Weyl type 201 4.1.4 Applications of Weyl’s formula 208 4.2 Determinantal point processes 217 4.2.1 Point processes – basic definitions 217 4.2.2 Determinantal processes 222 4.2.3 Determinantal projections 225 4.2.4 The CLT for determinantal processes 229 4.2.5 Determinantal processes associated with eigenvalues 230 4.2.6 Translation invariant determinantal processes 234 4.2.7 One dimensional translation invariant determinantal processes 239 4.2.8 Convergence issues 243 4.2.9 Examples 245 4.3 Stochastic analysis for random matrices 250 4.3.1 Dyson’s Brownian motion 251 4.3.2 A dynamical version of Wigner’s Theorem 264 4.3.3 Dynamical central limit theorems 275 4.3.4 Large deviations bounds 279 4.4 Concentration of measure and random matrices 284 4.4.1 Concentration inequalities for Hermitian matrices with independent entries 284 4.4.2 Concentration inequalities for matrices with non independent entries 289 4.5 Tridiagonal matrix models and the β ensembles 305 4.5.1 Tridiagonal representation of β ensembles 305 4.5.2 Scaling limits at the edge of the spectrum 309 4.6 Bibliographical notes 320 5 Free probability 325 5.1 Introduction and main results 326 5.2 Noncommutative laws and noncommutative probability spaces 328
CONTENTS xi 5.2.1 Algebraic noncommutative probability spaces and laws 328 5.2.2 C*-probability spaces and the weak-*topology 332 5.2.3 W*-probability spaces 341 5.3 Free independence 351 5.3.1 Independence and free independence 351 5.3.2 Free independence and combinatorics 356 5.3.3 Consequence of free independence:free convolution 362 5.3.4 Free central limit theorem 371 5.3.5 Freeness for unbounded variables 372 5.4 Link with random matrices 377 5.5 Convergence of the operator norm of polynomials of inde- pendent GUE matrices 396 5.6 Bibliographical Notes 412 Appendices 417 A Linear algebra preliminaries 417 A.1 Identities and bounds 417 A.2 Perturbations for normal and Hermitian matrices 418 A.3 Noncommutative Matrix LP-norms 419 A.4 Brief review of resultants and discriminants 420 B Topological Preliminaries 421 B.1 Generalities 421 B.2 Topological Vector Spaces and Weak Topologies 424 B.3 Banach and Polish Spaces 425 B.4 Some elements of analysis 426 Probability measures on Polish spaces 427 C.1 Generalities 427 C.2 Weak Topology 429 D Basic notions of large deviations 431 E The skew field H of quaternions,and matrix theory over F 434 E.1 Matrix terminology over F,and factorization theorems435
CONTENTS xi 5.2.1 Algebraic noncommutative probability spaces and laws 328 5.2.2 C ∗ - probability spaces and the weak-* topology 332 5.2.3 W∗ - probability spaces 341 5.3 Free independence 351 5.3.1 Independence and free independence 351 5.3.2 Free independence and combinatorics 356 5.3.3 Consequence of free independence: free convolution 362 5.3.4 Free central limit theorem 371 5.3.5 Freeness for unbounded variables 372 5.4 Link with random matrices 377 5.5 Convergence of the operator norm of polynomials of independent GUE matrices 396 5.6 Bibliographical Notes 412 Appendices 417 A Linear algebra preliminaries 417 A.1 Identities and bounds 417 A.2 Perturbations for normal and Hermitian matrices 418 A.3 Noncommutative Matrix L p -norms 419 A.4 Brief review of resultants and discriminants 420 B Topological Preliminaries 421 B.1 Generalities 421 B.2 Topological Vector Spaces and Weak Topologies 424 B.3 Banach and Polish Spaces 425 B.4 Some elements of analysis 426 C Probability measures on Polish spaces 427 C.1 Generalities 427 C.2 Weak Topology 429 D Basic notions of large deviations 431 E The skew field H of quaternions, and matrix theory over F 434 E.1 Matrix terminology over F, and factorization theorems 435
xii CONTENTS E.2 The spectral theorem and key corollaries 437 E.3 A specialized result on projectors 438 E.4 Algebra for curvature computations 439 Manifolds 441 F1 Manifolds embedded in Euclidean space 442 F.2 Proof of the coarea formula 446 F.3 Metrics,connections,curvature,hessians,and the Laplace-Beltrami operator 449 G Appendix on Operator Algebras 454 G.1 Basic definitions 454 G.2 Spectral properties 456 G.3 States and positivity 458 G.4 von Neumann algebras 459 G.5 Noncommutative functional calculus 461 H Stochastic calculus notions 463 References 468 General Conventions 484
xii CONTENTS E.2 The spectral theorem and key corollaries 437 E.3 A specialized result on projectors 438 E.4 Algebra for curvature computations 439 F Manifolds 441 F.1 Manifolds embedded in Euclidean space 442 F.2 Proof of the coarea formula 446 F.3 Metrics, connections, curvature, hessians, and the Laplace-Beltrami operator 449 G Appendix on Operator Algebras 454 G.1 Basic definitions 454 G.2 Spectral properties 456 G.3 States and positivity 458 G.4 von Neumann algebras 459 G.5 Noncommutative functional calculus 461 H Stochastic calculus notions 463 References 468 General Conventions 484
Preface The study of random matrices,and in particular the properties of their eigenval- ues,has emerged from the applications,first in data analysis and later as statisti- cal models for heavy nuclei atoms.Thus,the field of random matrices owes its existence to applications.Over the years,however,it became clear that models related to random matrices play an important role in areas of pure mathematics. Moreover,the tools used in the study of random matrices came themselves from different and seemingly unrelated branches of mathematics. At this point in time,the topic has evolved enough that the newcomer,especially if coming from the field of probability theory,faces a formidable and somewhat confusing task in trying to access the research literature.Furthermore,the back- ground expected of such a newcomer is diverse,and often has to be supplemented before a serious study of random matrices can begin. We believe that many parts of the field of random matrices are now developed enough to enable one to expose the basic ideas in a systematic and coherent way. Indeed,such a treatise,geared toward theoretical physicists,has existed for some time,in the form of Mehta's superb book [Meh91].Our goal in writing this book has been to present a rigorous introduction to the basic theory of random matri- ces,including free probability,that is sufficiently self contained to be accessible to graduate students in mathematics or related sciences,who have mastered probabil- ity theory at the graduate level,but have not necessarily been exposed to advanced notions of functional analysis,algebra or geometry.Along the way,enough tech- niques are introduced that hopefully will allow readers to continue their journey into the current research literature. This project started as notes for a class on random matrices that two of us(G.A. and O.Z.)taught in the University of Minnesota in the fall of 2003,and notes for a course in the probability summer school in St.Flour taught by A.G.in the xiii
Preface The study of random matrices, and in particular the properties of their eigenvalues, has emerged from the applications, first in data analysis and later as statistical models for heavy nuclei atoms. Thus, the field of random matrices owes its existence to applications. Over the years, however, it became clear that models related to random matrices play an important role in areas of pure mathematics. Moreover, the tools used in the study of random matrices came themselves from different and seemingly unrelated branches of mathematics. At this point in time, the topic has evolved enough that the newcomer, especially if coming from the field of probability theory, faces a formidable and somewhat confusing task in trying to access the research literature. Furthermore, the background expected of such a newcomer is diverse, and often has to be supplemented before a serious study of random matrices can begin. We believe that many parts of the field of random matrices are now developed enough to enable one to expose the basic ideas in a systematic and coherent way. Indeed, such a treatise, geared toward theoretical physicists, has existed for some time, in the form of Mehta’s superb book [Meh91]. Our goal in writing this book has been to present a rigorous introduction to the basic theory of random matrices, including free probability, that is sufficiently self contained to be accessible to graduate students in mathematics or related sciences, who have mastered probability theory at the graduate level, but have not necessarily been exposed to advanced notions of functional analysis, algebra or geometry. Along the way, enough techniques are introduced that hopefully will allow readers to continue their journey into the current research literature. This project started as notes for a class on random matrices that two of us (G. A. and O. Z.) taught in the University of Minnesota in the fall of 2003, and notes for a course in the probability summer school in St. Flour taught by A. G. in the xiii
XIV PREFACE summer of 2006.The comments of participants in these courses,and in particular A.Bandyopadhyay,H.Dong,K.Hoffman-Credner,A.Klenke,D.Stanton and P.M.Zamfir,were extremely useful.As these notes evolved,we taught from them again at the University of Minnesota,the University of California at Berkeley,the Technion and Weizmann Institute,and received more much appreciated feedback from the participants in those courses.Finally,when expanding and refining these course notes,we have profited from the comments and questions of many col- leagues.We would like to thank in particular G.Ben Arous,P.Biane,P.Deift, A.Dembo,P.Diaconis,U.Haagerup,V.Jones,M.Krishnapur,Y.Peres,R.Pin- sky,G.Pisier,B.Rider,D.Shlyakhtenko,B.Solel,A.Soshnikov,R.Speicher,T. Suidan,C.Tracy,B.Virag and D.Voiculescu for their suggestions,corrections, and patience in answering our questions or explaining their work to us.Of course, any remaining mistakes and unclear passages are fully our responsibility. MINNEAPOLIS.MINNESOTA GREG ANDERSON LYON,FRANCE ALICE GUIONNET REHOVOT.ISRAEL OFER ZEITOUNI APRIL 2009
xiv PREFACE summer of 2006. The comments of participants in these courses, and in particular A. Bandyopadhyay, H. Dong, K. Hoffman-Credner, A. Klenke, D. Stanton and P.M. Zamfir, were extremely useful. As these notes evolved, we taught from them again at the University of Minnesota, the University of California at Berkeley, the Technion and Weizmann Institute, and received more much appreciated feedback from the participants in those courses. Finally, when expanding and refining these course notes, we have profited from the comments and questions of many colleagues. We would like to thank in particular G. Ben Arous, P. Biane, P. Deift, A. Dembo, P. Diaconis, U. Haagerup, V. Jones, M. Krishnapur, Y. Peres, R. Pinsky, G. Pisier, B. Rider, D. Shlyakhtenko, B. Solel, A. Soshnikov, R. Speicher, T. Suidan, C. Tracy, B. Virag and D. Voiculescu for their suggestions, corrections, and patience in answering our questions or explaining their work to us. Of course, any remaining mistakes and unclear passages are fully our responsibility. GREG ANDERSON ALICE GUIONNET OFER ZEITOUNI APRIL 2009 MINNEAPOLIS, MINNESOTA LYON, FRANCE REHOVOT, ISRAEL
1 Introduction This book is concerned with random matrices.Given the ubiquitous role that matrices play in mathematics and its application in the sciences and engineering, it seems natural that the evolution of probability theory would eventually pass through random matrices.The reality,however,has been more complicated (and interesting).Indeed,the study of random matrices,and in particular the properties of their eigenvalues,has emerged from the applications,first in data analysis(in the early days of statistical sciences,going back to Wishart [Wis281),and later as statistical models for heavy nuclei atoms,beginning with the seminal work of Wigner [Wig55].Still motivated by physical applications,at the able hands of Wigner,Dyson,Mehta and co-workers,a mathematical theory of the spectrum of random matrices began to emerge in the early 1960s,and links with various branches of mathematics,including classical analysis and number theory,were established.While much advance was initially achieved using enumerative combi- natorics,gradually,sophisticated and varied mathematical tools were introduced: Fredholm determinants(in the 1960s),diffusion processes (in the 1960s),inte- grable systems(in the 1980s and early 1990s),and the Riemann-Hilbert problem (in the 1990s)all made their appearance,as well as new tools such as the theory of free probability (in the 1990s).This wide array of tools,while attesting to the vi- tality of the field,present however several formidable obstacles to the newcomer, and even to the expert probabilist.Indeed,while much of the recent research uses sophisticated probabilistic tools,it builds on layers of common knowledge that,in the aggregate,few people possess Our goal in this book is to present a rigorous introduction to the basic theory of random matrices that would be sufficiently self contained to be accessible to grad- uate students in mathematics or related sciences,who have mastered probability theory at the graduate level,but have not necessarily been exposed to advanced notions of functional analysis,algebra or geometry.With such readers in mind,we
1 Introduction This book is concerned with random matrices. Given the ubiquitous role that matrices play in mathematics and its application in the sciences and engineering, it seems natural that the evolution of probability theory would eventually pass through random matrices. The reality, however, has been more complicated (and interesting). Indeed, the study of random matrices, and in particular the properties of their eigenvalues, has emerged from the applications, first in data analysis (in the early days of statistical sciences, going back to Wishart [Wis28]), and later as statistical models for heavy nuclei atoms, beginning with the seminal work of Wigner [Wig55]. Still motivated by physical applications, at the able hands of Wigner, Dyson, Mehta and co-workers, a mathematical theory of the spectrum of random matrices began to emerge in the early 1960s, and links with various branches of mathematics, including classical analysis and number theory, were established. While much advance was initially achieved using enumerative combinatorics, gradually, sophisticated and varied mathematical tools were introduced: Fredholm determinants (in the 1960s), diffusion processes (in the 1960s), integrable systems (in the 1980s and early 1990s), and the Riemann-Hilbert problem (in the 1990s) all made their appearance, as well as new tools such as the theory of free probability (in the 1990s). This wide array of tools, while attesting to the vitality of the field, present however several formidable obstacles to the newcomer, and even to the expert probabilist. Indeed, while much of the recent research uses sophisticated probabilistic tools, it builds on layers of common knowledge that, in the aggregate, few people possess. Our goal in this book is to present a rigorous introduction to the basic theory of random matrices that would be sufficiently self contained to be accessible to graduate students in mathematics or related sciences, who have mastered probability theory at the graduate level, but have not necessarily been exposed to advanced notions of functional analysis, algebra or geometry. With such readers in mind, we 1
