Notes

Outline

Why are random matrix eigenvalues cool? Alan Edelman MIT: Dept of Mathematics, Lab for Computer Science &  Akamai Technologies Princeton – Wednesday, April 4

Some fun tidbits The circular law The semi-circular law Infinite vs finite How many are real? Condition Numbers Small networks Riemann Zeta Function

Girko’s Circular Law, n=2000

Wigner’s Semi-Circle The classical & most famous rand eig theorem Let S = random symmetric Gaussian MATLAB: A=randn(n);  S=(A+A’)/2; Normalized eigenvalue histogram is a semi-circle Precise statements require n®¥ etc.

Elements of Wigner’s Proof Compute E(A2k)11= mean(l2k) = (2k)th moment Verify that the semicircle is the only distribution with these moments (A2k)11 = SA1xAxy…AwzAz1 “paths” of length 2k Need only count number of special paths of length 2k on k objects  (all other terms 0 or negligible!) This is a Catalan Number!

Catalan Numbers                  =# ways to “parenthesize” (n+1) objects Matrix Power Term Graph (1((23)4)) A12A23A32A24A42A21 (((12)3)4) A12A21A13A31A14A41 (1(2(34))) A12A23A34A43A32A21 ((12)(34)) A12A21A13A34A43A31 ((1(23))4) A12A23A32A21A14A41 = number of special paths on n departing from 1 once Pass 1, (load=advance, multiply=retreat), Return to 1

Finite Versions n=2;                                        n=4; n=3;                                        n=5;

How many eigenvalues of a random matrix are real?

How many eigenvalues of a random matrix are real?

How many eigenvalues of a random matrix are real? The Probability that a matrix has all real eigenvalues is exactly Pn,n=2-n(n-1)/4 Proof based on Schur Form

Numerical Analysis: Condition Numbers k(A) = “condition number of A” If A=USV’ is the svd, then k(A) = smax/smin . Alternatively, k(A) = Öl max (A’A)/l min  (A’A) One number that measures digits lost in finite precision and general matrix “badness” Small=good Large=bad The condition of a random matrix???

Von Neumann & co. Solve Ax=b via x= (A’A) -1A’ b                                       M »A-1 Matrix Residual: ||AM-I||2 ||AM-I||2< 200k2 n e How should we estimate k? Assume, as a model, that the elements of A are independent standard normals!

Von Neumann & co. estimates  (1947-1951) “For a ‘random matrix’ of order n the expectation value has been shown to be about n” Goldstine, von Neumann “… we choose two different values of k, namely n and Ö10n” Bargmann, Montgomery, vN “With a probability ~1 … k < 10n” Goldstine, von Neumann

Random cond numbers, n®¥

Finite n           n=10                                       n=25          n=50                                         n=100

Small World Networks:  & 6 degrees of separation Edelman, Eriksson, Strang Eigenvalues of A=T+PTP’,  P=randperm(n)                                        Incidence matrix of graph with two         superimposed  cycles.

Small World Networks:  & 6 degrees of separation Edelman, Eriksson, Strang Eigenvalues of A=T+PTP’,  P=randperm(n)                                        Incidence matrix of graph with two         superimposed  cycles. Wigner style derivation counts number of paths on a tree starting and ending at the same point (tree = no accidents!)  (McKay) We first discovered the formula using the superseeker Catalan number answer d2n-1-S d2j-1(d-1)n-j+1Cn-j

The Riemann Zeta Function

The Riemann Hypothesis

The Riemann Hypothesis

Computation of Zeros Odlyzko’s fantastic computation of  10^k+1 through 10^k+10,000 for k=12,21,22. See http://www.research.att.com/~amo/zeta_tables/ Spacings behave like the eigenvalues of A=randn(n)+i*randn(n); S=(A+A’)/2;

Nearest Neighbor Spacings & Pairwise Correlation Functions

Spacings Take a large collection of consecutive zeros/eigenvalues. Normalize so that average spacing = 1. Spacing Function = Histogram of consecutive differences (the (k+1)st – the kth) Pairwise Correlation Function = Histogram of all possible differences (the kth – the  jth) Conjecture: These functions are the same for random matrices and Riemann zeta

Some fun tidbits The circular law The semi-circular law Infinite vs finite How many are real? Condition Numbers Small networks Riemann Zeta Function

Why cool? Why is numerical linear algebra cool? Mixture of theory and applications Touches many topics Easy to jump in to, but can spend a lifetime studying & researching Tons of activity in many areas Mathematics: Combinatorics, Harmonic Analysis, Integral Equations, Probability, Number Theory Applied Math: Chaotic Systems, Statistical Mechanics, Communications Theory, Radar Tracking, Nuclear Physics Applications BIG HUGE SUBJECT!!