Notebook 15 – Math 2121, Fall 2021

In this notebook we explore more random matrices and their eigenvalues.

Last time we saw that the eigenvalues of a large orthogonal matrix chosen uniformly at random are, with high probability, evenly spaced complex numbers in the unit circle ${z \in C : | z | = 1}$ .

This means that the process of choosing a random eigenvalue of a very large, uniformly random orthogonal matrix is indistiguishable from choosing an element of ${z \in C : | z | = 1}$ uniformly at random.

Today we will examine a similar phenomenon for random symmetric matrices.

md"# Notebook 15 -- Math 2121, Fall 2021

In this notebook we explore more random matrices and their eigenvalues.

Last time we saw that the eigenvalues of a large orthogonal matrix chosen uniformly at random are, with high probability, evenly spaced complex numbers in the unit circle $\{ z \in \mathbb{C} : |z| = 1\}$.

This means that the process of choosing a random eigenvalue of a very large, uniformly random orthogonal matrix is indistiguishable from choosing an element of $\{ z \in \mathbb{C} : |z| = 1\}$ uniformly at random.

Today we will examine a similar phenomenon for random **symmetric matrices**.

15.3 μs

using LinearAlgebra

5.9 ms

using Plots

4.1 s

using Distributions

721 ms

All matrices today have real entries.

A square matrix $S = S^{T}$ is symmetric if it is equal to its transpose. For example:

md"All matrices today have **real** entries.

A square matrix $S=S^T$ is **symmetric** if it is equal to its transpose. For example:"

12.7 μs

3×3 Matrix{Int64}:
 1  3  5
 3  0  6
 5  6  2

[1 3 5; 3 0 6; 5 6 2]

33.8 ms

All eigenvalues of a symmetric matrix are real numbers. For example:

md"All eigenvalues of a symmetric matrix are real numbers. For example:"

10.0 μs

Float64

-5.3258

-2.2393

10.5651

eigen([1 3 5; 3 0 6; 5 6 2]).values

46.6 ms

Compare with the eigenvalues of a random (non-symmetric) square matrix:

md"Compare with the eigenvalues of a random (non-symmetric) square matrix:"

11.0 μs

ComplexF64

-0.616878-0.483371im

-0.616878+0.483371im

-0.148978+0.0im

-0.0739519-0.50909im

-0.0739519+0.50909im

0.370464-0.528065im

0.370464+0.528065im

0.738654+0.0im

0.87464+0.0im

4.62409+0.0im

eigen(rand(10, 10)).values

103 ms

Here is a proof of this fact in general.

Assume $S = S^{T}$ is an $n \times n$ symmetric matrix. This means $S$ has all real entries.

Suppose $0 \neq v \in C^{n}$ is an eigenvector for $S$ with eigenvalue $λ \in C$ , so that

$S v = λ v and S \bar{v} = \bar{λ} \bar{v} .$

The product

${\bar{v}}^{T} v = ∥ v ∥^{2}$

is a positive real number since $v \neq 0$ .

On the other hand we have both

${\bar{v}}^{T} S v = {\bar{v}}^{T} (S v) = {\bar{v}}^{T} (λ v) = λ {\bar{v}}^{T} v = λ ∥ v ∥^{2}$

and, because $S = S^{T}$ , also

${\bar{v}}^{T} S v = (S^{T} \bar{v})^{T} v = (S \bar{v})^{T} v = (\bar{λ} \bar{v})^{T} v = \bar{λ} {\bar{v}}^{T} v = \bar{λ} ∥ v ∥^{2} .$

These expressions are equal, but the number $∥ v ∥^{2} \neq 0$ is nonzero, so $λ = \bar{λ} \in R$ .

md"Here is a proof of this fact in general.

Assume $S=S^T$ is an $n\times n$ symmetric matrix. This means $S$ has all real entries.

Suppose $0 \neq v \in \mathbb{C}^n$ is an eigenvector for $S$ with eigenvalue $\lambda \in \mathbb{C}$, so that

$S v = \lambda v \qquad\text{and}\qquad S \overline{v} = \overline{\lambda} \overline{v}.$

The product

$\overline{v}^T v = \|v\|^2$

is a positive real number since $v\neq 0$.

On the other hand we have both

$\overline{v}^T S v = \overline{v}^T (Sv) = \overline{v}^T (\lambda v) = \lambda \overline{v}^T v = \lambda \|v\|^2$

and, because $S=S^T$, also

$\overline{v}^T S v = (S^T\overline{v})^T v = (S\overline{v})^T v = (\overline \lambda \overline v)^T v = \overline \lambda \overline v^T v = \overline \lambda \|v\|^2.$

These expressions are equal, but the number $\|v\|^2 \neq 0$ is nonzero, so $\lambda = \overline \lambda \in \mathbb{R}$.

15.8 μs

Enter cell code...

115 ns

The set of symmetric $n \times n$ matrices has infinite volume, so it does not make sense to talk about a symmetric matrices chosen uniformly at random.

Here is a different way of sampling a random symmetric matrix.

md"The set of symmetric $n\times n$ matrices has infinite volume, so it does not make sense to talk about a symmetric matrices chosen uniformly at random.

Here is a different way of sampling a random symmetric matrix."

13.2 μs

First, we generate a random matrix with entries from the standard normal distribution.

md"First, we generate a random matrix with entries from the standard normal distribution."

9.5 μs

begin

h1 = histogram(

rand(Normal(0, 1), 1000000, 1),

normalize=:pdf, legend=false, xlim=(-4,4),

title="Histogram of 1000000 standard normal samples")

h2 = plot(

x -> exp(-x^2/2) / sqrt(2 * pi),

legend=false, xlim=(-4,4),

title="Standard normal density function")

plot(h1, h2, layout=(2,1), size=(680, 560))

end

418 ms

n = 5000

49 ns

A = rand(Normal(0, 1), n, n);

364 ms

Now to get a random symmetric matrix, we can just form the sum $A + A^{T}$ .

To make later plots nicer, we also divide by the normalizing constant $\sqrt{8 n}$ .

md"Now to get a random symmetric matrix, we can just form the sum $A+A^T$.

To make later plots nicer, we also divide by the normalizing constant $\sqrt{8n}$."

9.4 μs

5000×5000 Matrix{Float64}:
 -0.00762735  -0.00839509    0.00283356  …  -0.00623271    0.00374244   -0.00661463
 -0.00839509   0.0102949    -0.00884654     -0.0056233     0.000217301  -0.0096792
  0.00283356  -0.00884654    0.0229113       0.00176405   -0.00233944    0.00427864
  3.95906e-5  -8.645e-5     -0.00112023     -0.00405236    0.00124829   -0.00813669
  0.00241812   0.000690574   0.00379743     -0.00498116    0.00155456    0.00771613
 -0.00506289  -0.00326857   -0.00877366  …   0.0028971    -0.00281076   -0.00480432
 -0.00771719   0.0109026     0.00850002      0.00854183    0.00714828   -0.00378453
  ⋮                                      ⋱                              
  0.00683102  -0.00293006    0.00159171     -0.00428931    0.00441445    0.00174952
  0.00451836   0.00975552   -0.0104133   …   0.00257625   -0.00338708   -0.00745812
 -0.00676979  -0.011701     -0.00597049     -0.0107335     0.00902357   -0.00275118
 -0.00623271  -0.0056233     0.00176405     -0.000608546  -0.00379707    0.00189137
  0.00374244   0.000217301  -0.00233944     -0.00379707    0.00629238    0.00544397
 -0.00661463  -0.0096792     0.00427864      0.00189137    0.00544397    0.00489177

S = (A + transpose(A)) / sqrt(8 * n)

383 ms

true

S == transpose(S)

185 ms

Here are the (real) eigenvalues of this matrix, in sorted order:

md"Here are the (real) eigenvalues of this matrix, in sorted order:"

6.2 μs