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

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(A^2k)₁₁= mean(l^2k) = (2k)th moment

Verify that the semicircle is the only distribution with these moments

(A^2k)₁₁= SA_1xA_xy…A_wzA_z1 “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)) A₁₂A₂₃A₃₂A₂₄A₄₂A₂₁

(((12)3)4) A₁₂A₂₁A₁₃A₃₁A₁₄A₄₁

(1(2(34))) A₁₂A₂₃A₃₄A₄₃A₃₂A₂₁

((12)(34)) A₁₂A₂₁A₁₃A₃₄A₄₃A₃₁

((1(23))4) A₁₂A₂₃A₃₂A₂₁A₁₄A₄₁

= 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?

The Probability that a matrix has all real eigenvalues is exactly

P_n,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) = s_max/s_min .

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||₂

||AM-I||₂< 200k²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 d^2n-1-S d^2j-1(d-1)^n-j+1C_n-j

The Riemann Zeta Function

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!!


	Alan Edelman
	MIT: Dept of Mathematics,
	Lab for Computer Science &
	Akamai Technologies
	Princeton – Wednesday, April 4


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


	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.


	Compute E(A^2k)₁₁= mean(l^2k) = (2k)th moment
	Verify that the semicircle is the only distribution with these moments
	(A^2k)₁₁= SA_1xA_xy…A_wzA_z1 “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!


	=# ways to “parenthesize” (n+1) objects
	Matrix Power Term Graph
	(1((23)4)) A₁₂A₂₃A₃₂A₂₄A₄₂A₂₁
	(((12)3)4) A₁₂A₂₁A₁₃A₃₁A₁₄A₄₁
	(1(2(34))) A₁₂A₂₃A₃₄A₄₃A₃₂A₂₁
	((12)(34)) A₁₂A₂₁A₁₃A₃₄A₄₃A₃₁
	((1(23))4) A₁₂A₂₃A₃₂A₂₁A₁₄A₄₁
	= number of special paths on n departing from 1 once
	Pass 1, (load=advance, multiply=retreat), Return to 1


	The Probability that a matrix has all real eigenvalues is exactly
	P_n,n=2^-n(n-1)/4

	^{Proof based on Schur Form}


	k(A) = “condition number of A”
	If A=USV’ is the svd, then k(A) = s_max/s_min .
	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???



	Solve Ax=b via x= (A’A)^-1A’ b

	M »A^-1

	Matrix Residual: \|\|AM-I\|\|₂

	\|\|AM-I\|\|₂< 200k²n e


	How should we estimate k?

	Assume, as a model, that the elements of A are independent standard normals!



“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


	Edelman, Eriksson, Strang
	Eigenvalues of A=T+PTP’, P=randperm(n)
	Incidence matrix of graph with two
	superimposed cycles.


	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;


	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


	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!!