Report

Random Matrix Laws & Jacobi Operators Alan Edelman MIT May 19, 2014 joint with Alex Dubbs and Praveen Venkataramana (acknowledging gratefully the help from Bernie Wang) Conference Blurb • Recent years have seen significant progress in the understanding of asymptotic spectral properties of random matrices and related systems. • One particularly interesting aspect is the multifaceted connection with properties of orthogonal polynomial systems, encoded in Jacobi matrices (and their analogs) 2/55 At a Glance Random Matrix Idea Jacobi Operator Idea Key Point Moment Matching Algorithm 1. Probability Densities as Jacobi Operators • Key Limit Density Laws • Other Limit Density Laws • Toeplitz + Boundary • Asymptotically Toeplitz 2. Multivariate Orthogonal Polynomials • Multivariate weights for β-Ensembles • Generalization of triangular and tridiagonal structure Young Diagrams • Genus Expansion • q-Hermite Jacobi operator • Application of Algorithm in 1 Explicit Generalized Harer-Zagier Formula 3. Natural q-GUE integrals (q-theory) 3/55 Jacobi Operators (Symmetric Tridiagonal Format) Three term recurrence coefficients for orthogonal polynomials displayed as a Jacobi matrix Classically derived through Gram-Schmidt… 4/55 Encoding Probability Densities Density Moments Random Number Generator Fourier Transform BetaRand(3/2,3/2) (then x 4x-2) (Bessel Function) [Wigner] Cauchy Transform R-Transform Orthogonal Polynomials (Cheybshev of 2nd kind) Jacobi Matrix 5/55 Gil Strang’s Favorite Matrix encoded in Cupcakes 6/55 Computing the Jacobi encoding From the moments [Golub,Welsch 1969] 1. Form Hankel matrix of moments 2. R=Cholesky(H) 3. 7/55 Computing the Jacobi encoding From the weight (Continuous Lanczos) • Inner product: • Computes Jacobi Parameters and orthogonal polynomials • Discrete version very successful for eigenvalues of sparse symmetric matrices • May be computed with Chebfun 8/55 Example: Normal Distribution Moments Hermite Recurrence 9/55 Example Chebfun Lanczos Run [Verbatim from Pedro Gonnet’s November 2011 Run] Thanks to Bernie Wang 10/55 RMT Law Formula 0.4 Hermite Semicircle Law Wigner 1955 Free CLT 0.3 0.2 0.1 0 Laguerre MarcenkoPastur Law 1967 −0.1 −2.5 1.5 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 2.5 1 0.5 0 Jacobi Wachter Law 1980 0 0.5 1 1.5 2 Too Small Gegenbauer random regular graphs Mckay Law 1981 (a=b=v/2) 11/55 RMT Big laws: Toeplitz + Boundary Hermite Law Jacobi Encoding Semicircle Law 1955 x=a y=b Free CLT Laguerre MarcenkoPastur Law 1967 x=parameter y=b Free Poisson [Anshelevich, 2010] (Free Meixner) [E, Dubbs, 2014] Jacobi That’s pretty special! Corresponds to 2nd order differences with boundary Wachter Law 1980 x=parameter y=parameter Free Binomial Gengenbauer Mackay Law 1981 x=a y=parameter 12/55 Anshelevich Theory [Anshelevich, 2010] • Describe all weight Functions whose Jacobi encoding is Toeplitz off the first row and column • This is a terrific result, which directly lets us characterize • McKay often thrown in with Wachter, but seems worth distinguishing as special • Known as “free Meixner,” but I prefer to emphasize the Toeplitz plus boundary aspect 13/55 Semicircle Law 14/55 Marcenko-Pastur Law 15/55 McKay Law 16/55 Wachter Law 17/55 What RM are these other three? [Anshelevich, 2010] 18/55 Another interesting Random Matrix Law • The singular values (squared) of • Density: • Moments: 19/55 Jacobi Matrix J= 20/55 Jacobi Matrix J= 21/55 Implication? • The four big laws are Toeplitz + size 1 border • The svd law seems to be heading towards Toeplitz • Enough laws “want” to be Toeplitz Idea A moment algorithm that “looks for” an eventually Toeplitz form 22/55 Algorithm 1. Compute truncated Jacobi from a few initial moments 1a. (or run a few steps of Lanczos on the density) 2. Compute g(x)= 5x5 example 3. Approximate density = 23/55 Algorithm 1. Compute truncated Jacobi from a few initial moments 1a. (or run a few steps of Lanczos on the density) 2. Compute g(x)= k x kexample example 5x5 “It’s like replacing .1666… with 1/6 and not .16” “No need to move off real axis” 3. Approximate density = Replaces infinitely equal α’s and β’s 24/55 Mathematica 25/55 Fast convergence! Theory g[2] approx 26/55 Even the normal distribution • (not particularly well approximated by Toeplitz) • It’s not a random matrix law! 27/55 Moments 28/55 Free Cumulants 29/55 Narayana Photo Unavailable Wigner and Narayana [Wigner, 1957] (Narayana was 27) • Marcenko-Pastur = Limiting Density for Laguerre • Moments are Narayana Polynomials! • Narayana probably would not have known 30/55 At a Glance Random Matrix Idea Jacobi Operator Idea Key Point Moment Matching Algorithm 1. Probability Densities as Jacobi Operators • Key Limit Density Laws • Other Limit Density Laws • Toeplitz + Boundary • Asymptotically Toeplitz 2. Multivariate Orthogonal Polynomials • Multivariate weights for β-Ensembles • Generalization of triangular and tridiagonal structure Young Diagrams • Genus Expansion • q-Hermite Jacobi operator • Application of Algorithm in 1 Explicit Generalized Harer-Zagier Formula 3. Natural q-GUE integrals (q-theory) 31/55 Multivariate Orthogonal Polynomials • In random matrix theory and elsewhere • The orthogonal polynomials associated with the weight of general beta distributions 32/55 Classical Orthogonal Polynomials • Triangular Sparsity structure of monomial expansion: • Hermite: even/odd: • Generally Pn goes from 0 to n • Tridiagonal sparsity of 3-term recurrence 33/55 Classical Orthogonal Polynomials • Triangular Sparsity structure of monomial expansion: • Hermite: even/odd: • Generally Pn goes from 0 to n • Tridiagonal sparsity of 3-term recurrence Extensions to multivariate case?? Before extending, a few slides about these multivariate polynomials and their applications. 34/55 Hermite Polynomials become Multivariate Hermite Polynomials Orthogonal with respect to Orthogonal with respect to Indexed by degree k=0,1,2,3,… Symmetric scalar valued polynomials Indexed by partitions (multivariate degree): (),(1),(2),(1,1),(3),(2,1),(1,1,1),… 35/55 Monomials become Jack Polynomials Orthogonal on the unit circle Orthogonal on copies of the unit circle with respect to circular ensemble measure Symmetric scalar valued polynomials Indexed by partitions (multivariate degree): (),(1),(2),(1,1),(3),(2,1),(1,1,1),… 36/55 Multivariate Hermite Polynomials (β=1) [Chikuse, 1992] X … matrix Polynomial evaluated at eigenvalues of37/55 X (Selberg Integrals and) Combinatorics of mult polynomials: Graphs on Surfaces (Thanks to Mike LaCroix) • Hermite: Maps with one Vertex Coloring • Laguerre: Bipartite Maps with multiple Vertex Colorings • Jacobi: We know it’s there, but don’t have it quite yet. 38/55 Special case β=2 • Balderrama, Graczyk and Urbina (original proof) • β=2 (only!): explicit formula for multivariate orthogonal polynomials in terms of univariate orthogonal polynomials. • Generalizes Schur Polynomial construction in an important way • New proof reduces to orthogonality of Schur’s 39/55 Classical Orthogonal Polynomials • Triangular Sparsity structure of monomial expansion: • Hermite: even/odd: • Generally Pn goes from 0 to n • Tridiagonal sparsity of 3-term recurrence Extensions to multivariate case?? Before extending, a few slides about these multivariate polynomials and their applications. 40/55 What we know about the first question • Sometimes follows the Young Diagram • Hermite always follows Young diagram for all β • Laguerre always follows Young diagram for all β • (Baker and Forrester 1998) Young Diagram 41/55 What we know • Young Diagram for Hermite, Laguerre for all β • Young Diagram for all weight functions for β=2 (can be derived from schur polynomials) • Numerical evidence suggests answer does not follow Young diagram for all weight functions for all beta • Open Questions remain β=2 General β Hermite, Laguerre YOUNG (Baker,Forrester) YOUNG (Baker,Forrester) Jacobi ???? ???? General Weight Functions YOUNG (Venkataramana, E) Probably NOT YOUNG ????? (Venkataramana, E) 42/55 The second question • What Is the sparsity pattern of the analog of = = ? 43/55 Answer You, your parents and children in the Young Diagram 44/55 At a Glance Random Matrix Idea Jacobi Operator Idea Key Point Moment Matching Algorithm 1. Probability Densities as Jacobi Operators • Key Limit Density Laws • Other Limit Density Laws • Toeplitz + Boundary • Asymptotically Toeplitz 2. Multivariate Orthogonal Polynomials • Multivariate weights for β-Ensembles • Generalization of triangular and tridiagonal structure Young Diagrams • Genus Expansion • q-Hermite Jacobi operator • Application of Algorithm in 1 Explicit Generalized Harer-Zagier Formula 3. Natural q-GUE integrals (q-theory) 45/55 Hermite Jacobi Matrix 46/55 The Jacobi matrix Defines the moments of the normal Similarly there is a recipe for that does not require knowledge of the multivariate β=2 Hermite weight 47/55 Theorem: This is true for any weight function for which you have the Jacobi matrix • Proof: (Venkataramana, E 2014) 48/55 Proof Idea • We can use the wonderful formula • To compute integrals of any symmetric polynomial against • without needing to know w(x) explicitly 49/55 q-Hermite Jacobi Matrix q1 recovers classical Hermite 50/55 Genus expansion formula (β=2) Harer-Zagier formula 51/55 When β=2: MurnaghanNakayama Rule • Power function can be expanded in schur functions • For example 52/55 q-Harer Zagier formula [Venkataramana, E 2014] 53/55 Extension to general q 54/55 Conclusion • This conference theme is fantastic Jacobi Operators Random Matrices • Multivarite Jacobi: Much to Explore 55/55