J Theor Probab (2013) 26:1020–1060
DOI 10.1007/s10959-011-0391-2

The Limiting Spectral Measure for Ensembles
of Symmetric Block Circulant Matrices
Murat Koloğlu · Gene S. Kopp · Steven J. Miller

Received: 28 June 2011 / Revised: 25 October 2011 / Published online: 23 November 2011
© Springer Science+Business Media, LLC 2011

Abstract Given an ensemble of N × N random matrices, a natural question to ask
is whether or not the empirical spectral measures of typical matrices converge toa limiting spectral measure as N → ∞. While this has been proved for many thinpatterned ensembles sitting inside all real symmetric matrices, frequently there isno nice closed form expression for the limiting measure. Further, current theorems
provide few pictures of transitions between ensembles. We consider the ensembleof symmetric m-block circulant matrices with entries i.i.d.r.v. These matrices havetoroidal diagonals periodic of period m. We view m as a “dial” we can “turn” from thethin ensemble of symmetric circulant matrices, whose limiting eigenvalue density is a
Gaussian, to all real symmetric matrices, whose limiting eigenvalue density is a semicircle. The limiting eigenvalue densities fm show a visually stunning convergence tothe semi-circle as m → ∞, which we prove.
In contrast to most studies of patterned matrix ensembles, our paper gives explicit
closed form expressions for the densities. We prove that fm is the product of a Gaussian and a certain even polynomial of degree 2m − 2; the formula is the same as thatfor the m × m Gaussian Unitary Ensemble (GUE). The proof is by derivation of the
moments from the eigenvalue trace formula. The new feature, which allows us to obtain closed form expressions, is converting the central combinatorial problem in the
moment calculation into an equivalent counting problem in algebraic topology. We
end with a generalization of the m-block circulant pattern, dropping the assumption
M. Koloğlu · S.J. Miller ()Department of Mathematics and Statistics, Williams College, Williamstown, MA 01267, USAe-mail: Steven.J.Miller@williams.edu
M. Koloğlue-mail: Murat.Kologlu@williams.edu
G.S. Kopp
Department of Mathematics, University of Chicago, Chicago, IL 60637, USAe-mail: gkopp@uchicago.edu

J Theor Probab (2013) 26:1020–1060

1021

that the m random variables be distinct. We prove that the limiting spectral distribution exists and is determined by the pattern of the independent elements within an
m-period, depending not only on the frequency at which each element appears, butalso on the way the elements are arranged.
Keywords Limiting spectral measure · Circulant and Toeplitz matrices · Randommatrix theory · Convergence · Method of moments · Orientable surfaces · Euler
characteristic
Mathematics Subject Classification (2000) Primary 15B52 · 60F05 · 11D45 ·Secondary 60F15 · 60G57 · 62E20

1 Introduction
1.1 History and Ensembles
Random matrix theory is the study of properties of matrices chosen according to somenotion of randomness, which can range from taking the structurally independent entries as independent, identically distributed random variables to looking at subgroupsof the classical compact groups under Haar measure. While the origins of the subject
go back to Wishart’s [44] investigations in statistics in the 1920s, it was Wigner’s
work [39–43] in the 1950s and Dyson’s [11, 12] a few years later that showed its
incredible power and utility, as random matrix ensembles successfully modeled the
difficult problem of the distribution of energy levels of heavy nuclei. The next milestone was twenty years later, when Montgomery and Dyson [33] observed that the
behavior of eigenvalues in certain random matrix ensembles correctly describe thestatistical behavior of the zeros of the Riemann zeta function. The subject continues to grow, with new applications ranging from chemistry to network theory [31] totransportation systems [2, 26]. See [15, 21] for a history of the development of thesubject and the discovery of some of these connections.
One of the most studied matrix ensembles is the ensemble of N × N real symmetric matrices. The N entries on the main diagonal and the 12 N (N − 1) entries in
the upper right are taken to be independent, identically distributed random variablesfrom a fixed probability distribution with density p having mean 0, variance 1, andfinite higher moments. The remaining entries are filled in so that the matrix is real
symmetric. Thus
Prob(A) =p(aij ),

1≤i≤j ≤N
Prob A : aij ∈ [αij , βij ] =



(1.1)

 βij

1≤i≤j ≤N xij =αij

p(xij ) dxij .

1022

J Theor Probab (2013) 26:1020–1060

We want to understand the eigenvalues of A as we average over the family. Letδ(x − x0 ) denote the shifted Delta functional (i.e., a unit point mass at x0 , satisfying
f (x)δ(x − x0 ) dx = f (x0 )). To each A we associate its empirical spectral measure:N 
1 
λi (A).
δ x− √
μA,N (x) =
N
N

(1.2)

i=1

Using the Central Limit Theorem,√ one readily sees that the correct scale to study the
eigenvalues is on the order of N .1 The most natural question to ask is: How many
normalized eigenvalues of a ‘typical’ matrix lie in a fixed interval as N → ∞? Wigner
proved that the answer is a semi-ellipse. This means that as N → ∞, the empirical
spectral measures of almost all A converge to the density of the semi-ellipse (withour normalization), whose density is
fWig (x) =1π0

1 − ( x2 )2

if |x| ≤ 2,

(1.3)

otherwise.

√√
If we normalized
the eigenvalues by 2 N instead of N , we would obtain the den√sity π2 1 − x 2 for |x| ≤ 1, which is known in the literature as Wigner’s semi-circle
law (although this density, too, is really a semi-ellipse).
As the eigenvalues of any real symmetric matrix are real, we can ask whether or
not a limiting distribution exists for the density of normalized eigenvalues for otherensembles. There are many interesting families to study. McKay [32] proved that thelimiting spectral measure for adjacency matrices attached to d-regular graphs on N
vertices exists, and as N → ∞, for almost all such graphs the associated measuresconverge to Kesten’s measure
fKesten,d (x) =d
2π(d 2 −x 2 )04(d − 1) − x 2 ,√|x| ≤ 2 d − 1,otherwise(1.4)(note that the measures may be scaled such that as d → ∞ they converge to thesemi-circle distribution).
This example and its behavior are typical for what we hope to find and prove.
Specifically, we are looking for a thin subfamily that has different behavior but, as
we fatten the ensemble to the full family of all real symmetric matrices, the limiting
spectral measure converges to the semi-circle. Numerous researchers have studied a
multitude of special, patterned matrices; we do not attempt to do this vast subject
justice, but rather concentrate on a few ensembles closely related to our work.
All of the ensembles we consider here are linked ensembles (see [5]). A linked
ensemble of N × N matrices is specified by a link function LN : {1, 2, . . . , N}2 → S
N λ2 = Trace(A2 ) =2i,j ≤N aij ; as the mean is zero and the variance is one for each aij , this sum
i=1 i
2
is of the order N , implying the average square of an eigenvalue is N .

1

J Theor Probab (2013) 26:1020–1060

1023

to some set S. To s ∈ S, assign random variables xs which are independent, identically distributed from a fixed probability distribution with density p having mean
0, variance 1, and finite higher moments. Set the (i, j )th entry of the matrix ai,j :=xLN (i,j ) .2 For some linked ensembles, including those we examine here, it is be moreconvenient to specify the ensemble not by the link function, but by the equivalence
relation ∼ it induces on {1, 2, . . . , N}2 . A link function may be uncovered as thequotient map to the set of equivalence classes {1, 2, . . . , N}2  {1, 2, . . . , N }2 /∼.
For example, the real symmetric ensemble is specified by the equivalence relation(i, j ) ∼ (j, i).
One interesting thin linked ensemble is that of real symmetric Toeplitz matrices,which are constant along its diagonals. The limiting measure is close to but not a
Gaussian (see [7, 10, 18]); however, in [29] the sub-ensemble where the first row isreplaced with a palindrome is shown to have the Gaussian as its limiting measure.
While the approach in [29] involves an analysis of an associated system of Diophantine equations, using Cauchy’s interlacing property one can show that this problem is
equivalent to determining the limiting spectral measure of symmetric circulant matrices (also studied in [9]).
While these and other ensembles related to circulant, Toeplitz, and patterned matrices are a very active area [3–5, 7–10, 18, 28, 29], of particular interest to us are
ensembles of patterned matrices with a variable parameter controlling the symmetry.
We desire to deform a family of matrices, starting off with a highly structured family
and ending with the essentially structureless case of real symmetric matrices. This is
in contrast to some other work, such as Kargin [24] (who studied banded Toeplitz matrices) and Jackson, Miller, and Pham [22] (who studied Toeplitz matrices whose firstrow had a fixed but arbitrarily number of palindromes). In these cases the ensembles
are converging to the full Toeplitz ensemble (either as the band grows or the numberof palindromes decreases). Other patterned matrices are possible. Meckes [30] considered matrices whose (i, j )th entry is f (ai aj−1 ) for f a complex valued function ona finite Abelian group, and proved in many cases that the limiting behavior is either
Gaussian or the sum of two Gaussians. Beckwith, Miller and Shen [6] study weighted
patterned matrices, generalizing these investigations.
Our main ensemble is what we call the ensemble of m-block circulant matrices. A real symmetric circulant matrix (also called a symmetric circulant matrix) is a real symmetric matrix that is constant along diagonals and has first row(x0 , x1 , x2 , . . . , x2 , x1 ). Note that except for the main diagonal, a diagonal of length
N − k in the upper right is paired with a diagonal of length k in the bottom left, andall entries along these two diagonals are equal. We study block Toeplitz and circulant
matrices with m × m blocks. The diagonals of such matrices are periodic of period m.

2 For general linked ensembles, it may make more sense to weight the random variables by how often−1they occur in the matrix: ai,j := cN |L−1
N ({LN (i, j )})| xLN (i,j ) . For the real symmetric ensemble, thiscorresponds to weighting the entries along the diagonal by 2. In that case, and for the ensembles we
examine here, this modification changes only lower order terms in the calculations of the limiting spectral
measure.

1024

J Theor Probab (2013) 26:1020–1060

Definition 1.1 (m-Block Toeplitz and Circulant Matrices) Let m|N . An N × N real
symmetric m-block Toeplitz matrix is a Toeplitz matrix of the form
⎛

B0
⎜ B−1
⎜
⎜
⎜ B−2
⎜
⎜ ..
⎝ .
B1− N

m

B1
B0
B−1
..
.
B2− N

m

B2
B1
B0
..
.
B3− N

m

···
···
···
..
.
···

⎞
B N −1m
B N −2 ⎟⎟m⎟
B N −3 ⎟ ,
m
⎟
.. ⎟
. ⎠
B0

with each Bi an m × m real matrix. An m-block circulant matrix is one of the above
form for which B−i = Bn−i .
We investigate real symmetric m-block Toeplitz and circulant matrices. In such
matrices, a generic set of paired diagonals is composed of m independent entries,
placed periodically; however, as the matrix is real symmetric, this condition occasionally forces additional entries on the paired diagonals of length N2 to be equal.
For example, an 8 × 8 symmetric 2-block Toeplitz matrix has the form⎛⎞
c0 c1 c2 c3 c4 c5 c6 c7⎜ c1 d0 d1 d2 d3 d4 d5 d6 ⎟⎜⎟⎜ c2 d1 c0 c1 c2 c3 c4 c5 ⎟⎜⎟⎜ c3 d2 c1 d0 d1 d2 d3 d4 ⎟
⎜
⎟
(1.5)
⎜ c4 d3 c2 d1 c0 c1 c2 c3 ⎟ ,⎜⎟⎜ c5 d4 c3 d2 c1 d0 d1 d2 ⎟⎜⎟⎝ c6 d5 c4 d3 c2 d1 c0 c1 ⎠c7 d6 c5 d4 c3 d2 c1 d0
while a 6 × 6 and an 8 × 8 symmetric 2-block circulant matrices have the form⎛⎞
c0 c 1 c 2 c 3 c 2 d 1⎜ c1 d0 d1 d2 c3 d2 ⎟⎜⎟⎜ c2 d1 c0 c1 c2 c3 ⎟⎜⎟⎜ c3 d2 c1 d0 d1 d2 ⎟ ,⎜⎟⎝ c2 c3 c2 d1 c0 c1 ⎠d1 d2 c3 d2 c1 d0⎛⎞
c0 c 1 c 2 c 3 c 4 d 3 c 2 d 1(1.6)⎜ c1 d0 d1 d2 d3 d4 c3 d2 ⎟⎜⎟⎜ c2 d1 c0 c1 c2 c3 c4 d3 ⎟⎜⎟⎜ c3 d2 c1 d0 d1 d2 d3 d4 ⎟⎜⎟⎜ c4 d3 c2 d1 c0 c1 c2 c3 ⎟ ;⎜⎟⎜ d3 d4 c3 d2 c1 d0 d1 d2 ⎟⎜⎟⎝ c2 c3 c4 d3 c2 d1 c0 c1 ⎠d1 d2 d3 d4 c3 d2 c1 d0
Note for the 6 × 6 matrix that being real symmetric forces the paired diagonals oflength N2 (i.e., 3) to have just one and not two independent random variables. An

J Theor Probab (2013) 26:1020–1060

1025

equivalent viewpoint is that each ‘wrapped’ diagonal is periodic with period m andhas m distinct random variables. Note that the diagonals are wrapped toroidally, andeach such diagonal has N elements.
Clearly if m = 1 these ensembles reduce to the previous cases, and as m → ∞ they
approach the full family of real symmetric matrices; in other words, the circulant
or Toeplitz structure vanishes as m → ∞, but for any finite m there is additional
structure. The goal of this paper is to determine the limiting spectral measures forthese families and to quantify how the convergence to the semi-circle depends on m.
We find an explicit closed form expression for the limiting spectral density of them-block circulant family as a product of a Gaussian and a degree 2m − 2 polynomial.
1.2 Results
Before stating our results, we must define the probability spaces where our ensemble
lies and state the various types of convergence that we can prove. We provide fulldetails for the m-block circulant matrices, as the related Toeplitz ensemble is similar.
The following definitions and setup are standard, but are included for completeness.
We paraphrase from [22, 29] with permission.
Fix m and for each integer N let Ωm,N denote the set of m-block circulant matricesof dimension N . Define an equivalence relation  on {1, 2, . . . , N}2 . Say that (i, j ) (i , j ) if and only if aij = ai j for all m-block circulant matrices; in other words, if• j − i ≡ j − i (mod N ) and i ≡ i (mod m), or• j − i ≡ −(j − i )(mod N ) and i ≡ j (mod m).
Consider the quotient {1, 2, . . . , N}2  {1, 2, . . . , N}2 / . This induces an injec2
2
2tion R{1,2,...,N } / → RN . The set R{1,2,...,N } / has the structure of a probability space with the product measure of p(x) dx with itself |{1, 2, . . . , N}2 /| times,
where dx is Lebesgue measure. We define the probability space (Ωm,N , Fm,N , Pm,N )2
to be its image in RN = MN 2 (R) under the injection, with the same distribution.
To each AN ∈ Ωm,N we attach a measure by placing a point mass of size N1 ateach normalized eigenvalue λi (AN ):μm,AN (x) dx =N 1 λi (AN )dx,δ x− √
N
N

(1.7)

i=1

where δ(x) is the standard Dirac delta√function; see Footnote 1 for an explanationof the normalization factor equaling N . We call μm,AN the normalized spectral
measure associated with AN .
Definition 1.2 (Normalized Empirical Spectral Distribution) Let AN ∈ Ωm,N haveeigenvalues λN ≥ · · · ≥ λ1 . The normalized empirical spectral distribution (the emA√Npirical distribution of normalized eigenvalues) Fm N is defined byA√NN

Fm (x) =#{i ≤ N : √λi ≤ x}
N

N

.

(1.8)

1026

J Theor Probab (2013) 26:1020–1060

√
√
x
A / N
A / N
As Fm N(x) = −∞ μm,AN (t) dt, we see that Fm N
is the cumulative distribution function associatedwiththemeasureμ.
We
areinterested
in the behavior
n,A
N
√
A / N

of a typical Fm N
as we vary AN in our ensembles Ωm,N as N → ∞.
Consider any probability space Ωm which has the Ωm,N as quotients. (The mostobvious example is the independent product.) This paper build on a line of papers [18,22, 29] concerning various Toeplitz ensembles which fix Ωm to be the space of Nindexed strings of real numbers picked independently from p, with quotient maps toeach Ωm,N mapping a string to a matrix whose free parameters come from an initial
segment of the right length. There is no need for the specificities of this construction,so we consider the general case.
√A / N

Definition 1.3 (Limiting Spectral Distribution) If as N → ∞ we have Fm N
converging in some sense (for example, in probability or almost surely) to a distribution
Fm , then we say Fm is the limiting spectral distribution of the ensemble.
We investigate the symmetric m-block Toeplitz and circulant ensembles. We mayview these as structurally weakened real symmetric Toeplitz and circulant ensembles.
When m is 1 we regain the Toeplitz (circulant) structure, while if m = N we have thegeneral real symmetric ensemble. If m is growing with the size of the matrix, we
expect the eigenvalues to be distributed according to the semi-circle law, while for
fixed m we expect to see new limiting spectral distributions.
(T )Following the notation of the previous subsection, for each integer N , we let Ωm,N(C)

and Ωm,N denote the probability space of real symmetric m-block Toeplitz and circulant matrices of dimension N , respectively. We now state our main results.
Theorem 1.4 (Limiting Spectral Measures of Symmetric Block Toeplitz and Circulant Ensembles) Let m|N .
(1) The characteristic function of the limiting spectral measure of the symmetric mblock circulant ensemble is
 2
t2
t2
t
1
(1)
φm (t) = e− 2m e− 2m Lm−1
m
m

t2
t2
,
(1.9)
= e− 2m M m + 1, 2, −m
(1)

where Lm−1 is a generalized Laguerre polynomial and M a confluent hypergeometric function. The expression equals the spectral characteristic function forthe m × m GUE. The limiting spectral density function (the Fourier transform ofφm ) ism−r 
mx 2 m−1m(2r + 2s)!
1e− 2  1
fm (x) = √−22πm r=0 (2r)! s=0 r + s + 1 (r + s)!s!

s 2 rmx .
(1.10)

J Theor Probab (2013) 26:1020–1060

1027

Fig. 1 Plots for
f1 , f2 , f4 , f8 , f16 and thesemi-circle density

Fig. 2 (Left) Plot for f2 and histogram of eigenvalues of 1000 symmetric period 2-block circulant matrices of size 400 × 400. (Right) Plot for f3 and histogram of eigenvalues of 1000 symmetric period 3-block
circulant matrices of size 402 × 402

For any fixed m, the limiting spectral density is the product of a Gaussian and an
even polynomial of degree 2m − 2, and has unbounded support.
(2) If m tends to infinity with N (at any rate) then the limiting spectral distribution of
the symmetric m-block circulant and Toeplitz ensembles, normalized by rescaling
x to x/2, converges to the semi-circle distribution; without the renormalization,
the convergence is to a semi-ellipse, with density fWig (see (1.3)).
(3) As m → ∞, the limiting spectral measures fm of the m-block circulant ensemble
converge uniformly and in Lp for any p ≥ 1 to fWig , with |fm (x) − fWig (x)|2m− 9 + for any > 0.
(4) The empirical spectral measures of the m-block circulant and Toeplitz ensembles converge weakly and in probability to their corresponding limiting spectral
measures, and we have almost sure convergence if p is an even function.
Figure 1 illustrates the convergence of the limiting measures to the semi-circle;
numerical simulations (see Figs. 2, 3 and 4) illustrate the rapidity of the convergence.
We see that even for small m, in which case there are only mN
2 non-zero entries in theadjacency matrices (though these can be any of the N 2 − N non-diagonal entries ofthe matrix), the limiting spectral measure is close to the semi-circle. This behavior issimilar to what happens with d-regular graphs, though in our case the convergence isfaster and the support is unbounded for any finite m.
Finally, the limiting eigenvalue density for m-block circulant matrices is the sameas the eigenvalue density of a certain Gaussian Hermitian ensemble. Specifically, we

1028

J Theor Probab (2013) 26:1020–1060

Fig. 3 (Left) Plot for f4 and histogram of eigenvalues of 1000 symmetric period 4-block circulant matrices of size 400 × 400. (Right) Plot for f8 and histogram of eigenvalues of 1000 symmetric period 8-block
circulant matrices of size 400 × 400

Fig. 4 (Left) Plot for f1 and histogram of eigenvalues of 1000 symmetric period 1-block circulant matrices of size 400 × 400. (Right) Plot for f20 and histogram of eigenvalues of 1000 symmetric period
20-block circulant matrices of size 400 × 400

consider m × m Hermitian matrices with off-diagonal entries picked independently
2from a complex Gaussian with density function p(z) = π1 e−|z| , and diagonal entries
picked independently from a real Gaussian of mean 0 and variance 1. We provide aheuristic for why these densities are the same in Sect. 5.1; see also [46] (especially
Sect. 5.2) for a proof.
Our results generalize to related ensembles. For example, the (wrapped) diagonals of our m-block circulant ensembles have the following structure (remember weassume m|N ):(b1,j , b2,j , . . . , bm,j , b1,j , b2,j , . . . , bm,j , . . . , b1,j , b2,j , . . . , bm,j ).

(1.11)

Note that we have a periodic repeating block of size m with m independent randomvariables; for brevity, we denote this structure by(d1 , d2 , . . . , dm ).

(1.12)

Similar arguments handle other related ensembles, such as the subfamily of period m-circulant matrices in which some entries within the period are forced to beequal. Interesting comparisons are (d1 , d2 ) = (d1 , d2 , d1 , d2 ) versus (d1 , d1 , d2 , d2 )

J Theor Probab (2013) 26:1020–1060

1029

Fig. 5 Eigenvalue histograms for 200 patterned m-block circulant, 1200 × 1200 matrices; the first is thepattern {a, b} (which may also be written as {a, b, a, b} or {d1 , d2 }), the second is {a, a, b, b} and the thirdis {a, b, b, a}or (d1 , d2 , d2 , d1 ). While it is a natural guess that the limiting spectral measure isdetermined solely by the frequency at which each letter appears, this is false as Theorem 1.5 shows, though the differences are often so small that visually different patterns seem to give rise to the same limiting distribution (see Fig. 5 and Tables 1, 2
and 3 in Appendix B).
Theorem 1.5 Let P = (di1 , di2 , . . . , dim ) where each dij ∈ {d1 , . . . , dν } and eachdi occur exactly ri times in the pattern P, with r1 + · · · + rν = m; equivalently,
P is a permutation of (d1 , . . . , d1 , d2 , . . . , d2 , . . . , dν , . . . , dν ) with ri copies of di .
Modify the N × N period m-block circulant matrices by replacing the pattern(d1 , d2 , . . . , dm ) with P (remember m|N ). Then for any P as N → ∞ the limiting
spectral measure exists. The resulting measure does not depend solely on the frequencies of the letters in the pattern but also on their locations; in particular, while thefourth moments of the measures associated with {d1 , d2 , d1 , d2 } and {d1 , d1 , d2 , d2 }are equal (interestingly, the fourth moment of any pattern depends only on the frequencies), the sixth moments differ.
We prove our main results using the method of moments. As the proof of Theorem 1.5 is similar to that of Theorem 1.4, we just sketch the ideas and computationsin Appendix B. For our ensembles, we first show that the average of the kth moments
over our ensemble converge to the moments of a probability density. By studying thevariance or fourth moment of the difference of the moments of the empirical spectral
measures and the limits of the average moments, we obtain the various types of convergence by applications of Chebyshev’s inequality and the Borel–Cantelli Lemma.
These arguments are similar to previous works in the literature, and yield only theexistence of the limiting spectral measure.
Unlike other works for related ensembles, however, we are able to obtain explicit
closed form expressions for the moments for the symmetric m-block circulant ensemble. This should be compared to the Toeplitz ensemble case, where previous studies
could only relate these moments to volumes of Eulerian solids or solutions to systemsof Diophantine equations. Similarly to other ensembles, we show that the only contribution in the limit is when k = 2 and the indices are matched in pairs with opposite
orientation. We may view this as a 2 -gon with vertices (i1 , i2 ), (i2 , i3 ), . . . , (i2 , i1 ).
The first step is to note that when m = 1, similarly to the circulant and palindromic
Toeplitz ensembles, each matching contributes 1; as there are (2 −1)!! ways to match

1030

J Theor Probab (2013) 26:1020–1060

2 objects in pairs, and as (2 − 1)!! is the 2 th moment of the standard normal, thisyields the Gaussian behavior. For general m, the key idea is to look at the dual picture. Instead of matching indices we match edges. In the limit as N → ∞, the only
contribution occurs when the edges are matched in pairs with opposite orientation.
Topologically, these are exactly the pairings which give orientable surfaces. If g is
the genus of the associated surface, then the matching contributes m−2g . Harer andZagier [19] determined formulas for εg ( ), the number of matchings that form theseorientable surfaces. This yields the N → ∞ limit of the average 2 th moment is2εg ( )m−2g .

(1.13)

g=0

After some algebra, we express the characteristic function (which is the inverse
Fourier transform; see Footnote 3) of the limiting spectral measure as a certain term in
the convolution of the associated generating function of the εg ’s and the normal distribution, which we can compute using Cauchy’s residue theorem. Taking the Fouriertransform (appropriately normalized) yields an explicit, closed form expression forthe density. We note that the same formulas arise in investigations of the moments for
Gaussian ensembles; see Sect. 1.6 of [16] and [46] (as well as the references therein)
for additional comments and examples.
The paper is organized as follows. In Sect. 2 we describe the method of proof
and derive useful expansions for the moments in terms of quantities from algebraic
topology. We use these in Sect. 3 to determine the limiting spectral measures, andshow convergence in Sect. 4. We conclude in Sect. 5 with a description of future workand related results. Appendix A provides some needed estimates for proving the rateof convergence in Theorem 1.4, and we conclude in Appendix B with a discussion of
the proof of Theorem 1.5 (see [45] for complete details).

2 Moments Preliminaries
In this section we investigate the moments of the associated spectral measures. We
first describe the general framework of the convergence proofs and then derive useful
expansions for the average moments for our ensemble for each N (Lemma 2.2). The
average odd moments are easily seen to vanish, and we find a useful expansion forthe 2kth moment in Lemma 2.4, relating this moment to the number of pairings ofthe edges of a 2k-gon giving rise to a genus g surface.
2.1 Markov’s Method of Moments
For the eigenvalue density of a particular N × N symmetric m-block circulant matrix
A, we use the redundant notation μm,A,N (x) dx (to emphasize the N dependence),settingN 
1 
λi (A)dx.
(2.1)
δ x− √
μA,N (x) dx :=N
N
i=1

J Theor Probab (2013) 26:1020–1060

1031

To prove Theorem 1.4, we must show
(1) as N → ∞ a typical matrix has its spectral measure close to the system average;(2) these system averages converge to the claimed measures.
The second claim follows easily from Markov’s Method of Moments, which we
now briefly describe. To each integer k ≥ 0 we define the random variable Xk;m,N on
Ωm by
 ∞
A
√N
Xk;m,N (A) =x k dFm N (x);
(2.2)
−∞

note that this is the kth moment of the measure μm,A,N .
Ourmain tool to understand the average over all A in our ensemble of the√
A / N’s is the Moment Convergence Theorem (see [36] for example); while theFm N
analysis in [29] was simplified by the fact that the convergence was to the standard
normal, similar arguments (see also [22]) hold in our case as the growth rate of the
moments of our limiting distribution implies that the moments uniquely determine aprobability distribution.
Theorem 2.1 (Moment Convergence Theorem) Let {FN (x)} be a sequence of distribution functions such that the moments
Mk;N =

 ∞−∞x k dFN (x)(2.3)

exist for all k. Let {Mk }∞k=1 be a sequence of moments that uniquely determine aprobability distribution, and denote the cumulative distribution function by Ψ . If
limN →∞ Mk,N = Mk then limN →∞ FN (x) = Ψ (x).
We will see that the average moments uniquely determine a measure, and willbe left with proving that a typical matrix has a spectral measure close to the systemaverage. The nth moment of A’s measure, given by integrating x n against μm,A,N , isMn;m (A, N ) =N 
1  λi (A)
√
N
N
i=1

n

=

1

N


N 2 +1 i=1nλni (A).

(2.4)

We defineMn;m (N ) := E Mn;m (A, N ) ,(2.5)

Mn;m := lim Mn;m (N )(2.6)

and setN →∞(we will show later that the limit exists). By E(Mn;m (A, N )), we mean the expectedvalue of Mn;m (A, N ) for a random symmetric m-block circulant matrix A ∈ Ωm,N .

1032

J Theor Probab (2013) 26:1020–1060

2.2 Moment Expansion
We use a standard method to compute the moments. By the eigenvalue trace lemma,N  Tr An =
λni ,

(2.7)

i=1

so
Mn;m (A, N ) = 
Tr An .

(2.8)

ai 1 i 2 ai 2 i 3 · · · ai n i 1 ,(2.9)

E(ai1 i2 ai2 i3 · · · ain i1 ).

(2.10)

1
N

n
2 +1

Expanding out Tr(An ),Mn;m (A, N ) =



1
N

n
2 +1

1≤i1 ,...,in ≤N

so by linearity of expectation,
Mn;m (N ) =



1
N

n
2 +1

1≤i1 ,...,in ≤N

Recall that we have defined the equivalence relation  on {1, 2, . . . , N}2 by(i, j )  (i , j ) if and only if aij = ai j for all real symmetric m-block circulant
matrices. That is, (i, j )  (i , j ) if and only if• j − i ≡ j − i (mod N ) and i ≡ i (mod m), or• j − i ≡ −(j − i )(mod N ) and i ≡ j (mod m).
For each term in the sum in (2.10),  induces an equivalence relation ∼ on{(1, 2), (2, 3), . . . , (n, 1)} by its action on {(i1 , i2 ), (i2 , i3 ), . . . , (in , i1 )}. Let η(∼)
denote the number of n-tuples with 0 ≤ i1 , . . . , in ≤ N whose indices inherit ∼from . Say ∼ splits up {(1, 2), (2, 3), . . . , (n, 1)} into equivalence classes with sizes
d1 (∼), . . . , dl (∼). Because the entries of our random matrices are independent, identically distributed,E(ai1 i2 ai2 i3 · · · ain i1 ) = md1 (∼) · · · mdl (∼) ,(2.11)

where the md are the moments of p. Thus, we may write
Mn;m (N ) =

1
N

n
2 +1



η(∼)md1 (∼) · · · mdl (∼) .

(2.12)∼As p has mean 0, md1 (∼) · · · mdl (∼) = 0 unless all of the dj ’s are greater than 1.
So all the terms in the above sum vanish except for those coming from a relation ∼which matches at least in pairs.
The η(∼) denotes the number of solutions modulo N following the system ofDiophantine equations: whenever (s, s + 1) ∼ (t, t + 1),• is+1 − is ≡ it+1 − it (mod N ) and is ≡ it (mod m), orJ Theor Probab (2013) 26:1020–10601033• is+1 − is ≡ −(it+1 − it )(mod N ) and is ≡ it+1 (mod m).
This system has at most 2n−l N l+1 solutions, a bound we obtain by completely
ignoring the (mod m) constraints (see also [29]). Specifically, we pick one difference
is+1 − is from each congruence class of ∼ freely, and we are left with at most 2
choices for the remaining ones. Finally, we pick i1 freely, and this now determines
all the is = i1 + s <s (is +1 − is ). This method will not always produce a legitimate
solution, even without the (mod m) constraints, but it suffices to give an upper boundon the number of solutions.
When n is odd, say n = 2k + 1, then l is at most k. Thus n1+1 η(∼) ≤
N2


1
1
n−l N l+1 ≤n−l N k+1 = √1 2n−l = O √1 . This implies the odd mo2
2
n
3
3
k+
k+
N

2

N

N

2

N

ments vanish in the limit, as
1
M2k+1;m (N ) = Ok √.
N

(2.13)

When n is even, say n = 2k, then l is at most k. If l < k, then l ≤ k − 1,11
and we have, similarly to the above, n1+1 η(∼) ≤ N k+1
2n−l N l+1 ≤ N k+1
2n−l N k =

N2
1 n−l
= On ( N1 ). If l = k, then the entries are exactly matched in pairs, that is, all the
N2
dj = 2. As p has variance 1 (i.e., m2 = 1), the formula for the even moments, (2.12),

becomes
M2k;m (N ) =

1
N k+1


σ


η(σ ) + Ok

1.
N

(2.14)We have changed notation slightly. The sum is now over pairings σ on {(1, 2), (2, 3),. . . , (n, 1)}, which we may consider as functions (specifically, involutions with no
fixed points) as well as equivalence relations. We have thus shown the following:
Lemma 2.2 For the ensemble of symmetric m-block circulant matrices,1
M2k+1;m (N ) = Ok √
,
N

1
1 
M2k;m (N ) = k+1,
η(σ ) + Ok
NNσ

(2.15)

where the sum is over pairings σ on {(1, 2), (2, 3), . . . , (n, 1)}. In particular, as N →∞, the average odd moment is zero.
2.3 Even Moments
We showed that the odd moments go to zero like √1 as N → ∞; we now calcuNlate the 2kth moments. From Lemma 2.2, the only terms which contribute in thelimit are those in which the ais is+1 ’s are matched in pairs. We can think of thepairing as a pairing of the edges of a 2k-gon with vertices 1, 2, . . . , 2k and edges(1, 2), (2, 3), . . . , (2k, 1). The vertices are labeled i1 , . . . , i2k and the edges are labeled ai1 i2 , . . . , ai2k i1 . See Fig. 6.

1034

J Theor Probab (2013) 26:1020–1060

Fig. 6 Diagram for a pairing
arising in computing the 6th
momentFig. 7 Some possible
orientations of paired edges forthe 6-gonNote that this is dual to the diagrams for pairings that appear in [18, 29], in which
the ais is+1 ’s are represented as vertices. For more on such an identification and its application in determining moments for random matrix ensembles, see [16] (Sect. 1.6)and [46].
If ais is+1 and ait it+1 are paired, we have either• is+1 − is ≡ it+1 − it (mod N ) and is ≡ it (mod m), or• is+1 − is ≡ −(it+1 − it )(mod N ) and is ≡ it+1 (mod m).
We think of these two cases as pairing (s, s + 1) and (t, t + 1) with the same or
opposite orientation, respectively. For example, in Fig. 7 the hexagon on the left has
all edges paired in opposite orientation, and the one on the right has all but the rededges paired in opposite orientation.
We now dramatically reduce the number of pairings we must consider by showingthat the only pairings which contribute in the limit are those in which all edges are
paired with opposite orientation. Topologically, these are exactly the pairings whichgive orientable surfaces [19, 20]. This result and its proof are a minor modification of
their analogs in the Toeplitz and palindromic Toeplitz cases [18, 22, 29].
Lemma 2.3 Consider a pairing σ with orientations εj . If any εj is equal to 1, thenthe pairing contributes Ok ( N1 ).
Proof The size of the contribution is equal to the number of solutions to the k equations
is+1 − is ≡ εj (iσ (s)+1 − iσ (s) ) (mod N ),(2.16)

as well as some (mod m) equations, divided by N k+1 . We temporarily ignore the(mod m) constraints and bound the contribution from above by the number of so-

J Theor Probab (2013) 26:1020–1060

1035

lutions to the (mod N ) equations over N k+1 . Because the is ’s are restricted to thevalues 1, 2, . . . , N , we can consider them as elements of Z/N Z, and we now notatethe (mod N) congruences with equality.
The pairing puts the numbers 1, 2, . . . , 2k into k equivalence classes of size two;
arbitrarily order the equivalence classes and pick an element from each to call sj ,naming the other element tj = σ (sj ).
Our Z/N Z equations now look like
isj +1 − isj = εj (itj +1 − itj ) mod N.

(2.17)

Defining
xj := isj +1 − isj(2.18)

yj := itj +1 − itj ,our equations now look like xj = εj yj . Thus
0=

2k


is+1 − is =

k

j =1

s=1

xj +

k


yj =

j =1

k

(εj + 1)yj .
j =1

If any one of the εj = 1, this gives a non-trivial relation among the yj , and we losea degree of freedom. We may choose k − 1 of the yj freely (in Z/N Z), and we areleft with 1 or possibly 2 choices for the remaining yj (depending on the parity of N ).
The xj ’s are now determined as well, so is+1 − is is now determined for every s. If
we choose i1 freely, this now determines all the is = i1 + s <s (is +1 − is ). Thus,
we have at most N k−1 · 2 · N = 2N k solutions to (2.16). So the contribution from akpairing with a positive sign is at most Ok (2 NNk+1 ) = Ok ( N1 ). (The reason for the bigOh constant depending on k is that if some of the different pairs have the same value,
we might not have k copies of the second moment but instead maybe four second
moments and two eighth moments; however, the contribution is trivially bounded by
max1≤ ≤k (1 + m2 )k , where m2 is the 2 th moment of p.)Thus we haveM2k;m (N ) =w(σ )N−(k+1)

σ


+ Ok

1
,
N

(2.19)

where w(σ ) denotes the number of solutions to
ij +1 − ij ≡ −(iσj +1 − iσj ) mod N(2.20)

andij ≡ iσ (j )+1 ,ij +1 ≡ iσ (j ) mod m(2.21)(the second (mod m) constraint is redundant). We discuss how to evaluate this moment in closed form, culminating in Lemma 2.4.

1036

J Theor Probab (2013) 26:1020–1060

We now consider a given pairing as a topological identification (see [20] for an
exposition of the standard theory); this is the crux of our argument. Specifically, consider a 2k-gon with the interior filled in (homeomorphic to the disk), and identify thepaired edges with opposite orientation. Under the identification, some vertices are
identified; let v denote the number of vertices in the quotient.
Consider the (Z/NZ)-submodule A of (Z/NZ)2k in which the (mod N ) constraints hold. We have that A is isomorphic to (Z/NZ)k+1 . Specifically, we may
freely choose the value of exactly half of the differences is+1 − is , and then the rest
are determined. Because all the pairings are with opposite orientation, these “differences” sum to zero, so they are actually realizable as differences. Now choose i1
freely, and the rest of the is = i1 + s <s (is +1 − is ) are determined.
Let Ā denote the quotient of A in which everything is reduced modulo m, andconsider the (Z/mZ)-submodule B ⊆ Ā in which the modulo m constraints hold.
By (2.21), we can see that the labels at two vertices of our 2k-gon are forced to becongruent (mod m) if and only if the vertices are identified in the quotient, and these
are all the (mod m) constraints. In other words, B is isomorphic to (Z/mZ)v . Anelement of A for which the (mod m) constraints also hold is exactly one in the prek+1 ways toimage of B. We have mv choices for an element in B, and there are ( Nm)lift such an element to an element of A in its fiber. Thus, the equations have a total of
k+1 = m−(k+1−v) N k+1 , so the pairing has a contribution of m−(k+1−v) .
mv ( Nm)
Let X be the 2-dimensional cell complex described by the pairing σ of the edges ofthe 2k-gon. Because all edges were paired in the reverse direction, X is an orientablesurface. After identifications, the complex we have described has 1 face, k edges, and,say, v vertices. If we denote by g the genus of the surface, we obtain two expressions
for the Euler characteristic of X. By the standard (homological) definition of Euler
characteristic, we have χ(X) = 1 − k + v. On the other hand, for a genus g surfaceX, χ(X) = 2 − 2g [20]. Equating and rearranging,
2g = k + 1 − v.

(2.22)

Thus the pairing σ contributes m−2g , and we have shown the following:
Lemma 2.4 For the ensemble of symmetric m-block circulant matrices,
1,
M2k;m (N ) =εg (k)m−2g + OkNg

(2.23)

where εg (k) denotes the number of pairings of the edges of a 2k-gon which give rise
to a genus g surface.

3 Determining the Limiting Spectral Measures
We prove parts (1) and (2) of Theorem 1.4. Specifically, we derive the density formulafor the limiting spectral density of symmetric m-block circulant matrices. We show
that, if m grows at any rate with N , then the limiting spectral density is the semi-circle
for both the symmetric m-block circulant and Toeplitz ensembles.

J Theor Probab (2013) 26:1020–1060

1037

3.1 The Limiting Spectral Measure of the Symmetric m-Block Circulant Ensemble

Proof of Theorem 1.4(1) By deriving an explicit formula, we show that the limiting
spectral density function fm of the real symmetric m-block circulant ensemble isequal to the spectral density function of the m × m GUE.
From Lemma 2.4, the N → ∞ limit of the average 2kth moment equals2kM2k;m =εg (k)m−2g ,

(3.1)

g=0

with εg (k) the number of pairings of the edges of a 2k-gon giving rise to a genus gsurface. Harer and Zagier [19] give formulas for the εg (k). They prove

 x
(2k)!
2g
2
× coefficient of x in
εg (k) =(k + 1)!(k − 2g)!
tanh( x2 )

k+1

(3.2)

and
2

k

εg (k)r k+1−2g = (2k − 1)!!c(k, r),

(3.3)

g=0

where
1+2

∞



c(k, r)x k+1 =

1+x
1−x

r

.

(3.4)

M2k;m = m−(k+1) (2k − 1)!!c(k, m).

(3.5)

k=0

Thus, we may write

We construct the characteristic function3 of the limiting spectral distribution. Let
Xm be a random variable with density fm . Then (remembering that the odd moments
vanish)∞ (it) M ;mφm (t) = E eitXm =
!
=0

=

∞

k=0

=

∞

k=0

(it)2k M2k;m
(2k)!
k

1
m−(k+1) (2k − 1)!!c(k, m) −t 2 .
(2k)!

(3.6)


3 The characteristic function is φ (t) = E[eitXm ] = ∞ f (x)eitx dx. This is the inverse Fourier transm−∞ mform of fm .

1038

J Theor Probab (2013) 26:1020–1060

In order to obtain a closed form expression, we rewrite the characteristic function
as


∞
1
1 −t 2c(k, m)φm (t) =
m
k! 2m

k

(3.7)

,

k=0

using (2k − 1)!! = (2k)!
. The reason for this is that we can interpret the above as a
2k k!
certain coefficient in the convolution of two known generating functions, which canbe isolated by a contour integral. Specifically, consider the two functions
F (y) :=

12yG(y) := ey =

m

1+y
1−y

∞


−1 =

c(k, m)y k

and

k=0

yk

k=0

∞


k!

(3.8)

.

Note that φm (t) is the function whose power series is the sum of the products ofy2
the kth coefficients of G(− 2m) (which is related to the exponential distribution) andF (y) (which is related to the generating function of the εg (k)). Thus, we may use a
multiplicative convolution to find a formula for the sum. By Cauchy’s residue theo2
rem, integrating F (z−1 )G(− t2mz )z−1 over the circle of radius 2 yields
φm (t) =

1
2πim



 2
 
t z dz,F z−1 G −
2m z
|z|=2

(3.9)

2

since the constant term in the expansion of F (z−1 )G(− t2mz ) is exactly the sum of the
products of coefficients for which the powers of y in F (y) and G(y) are the same.4
We are integrating along the circle of radius 2 instead of the unit circle to have thepole inside the circle and not on it. Thus2
1 + z−1 m
1− t2mz dz
−
1
e
−1
z
1 − z−1|z|=2 2z


t2z
z+1 m
1
− 1 e− 2m dz=
4πim |z|=2z−1

φm (t) =

1
2πim

t2

e− 2m
=
4πim
t2

e− 2m
=
4πim




|z|=2


1+

2
z−1

m


m 

m
2
l
z
−
1
|z|=2



l=0

− 1 e−∞l
s=0t 2 (z−1)2mdz


1 −t 2s! 2ms(z − 1)s dz

4 All functions are meromorphic in the region with finitely many poles; thus, the contour integral yields thesum of the residues. See e.g. [35].

J Theor Probab (2013) 26:1020–1060
t2

e− 2m
−
4πim

1039


|z|=2

e−

t 2 (z−1)2m(3.10)dz.

By Cauchy’s Residue Theorem the second integral vanishes and the only surviving
terms in the first integral are when l − s = 1, whose coefficient is the residue. Thus
 2
t2
m 
−t
e− 2m  m l 1
φm (t) =2l2m(l − 1)! 2m

l−1

l=1

 2
m 
1
−t
1 − t2  me 2m=l (l − 1)! m
m

l−1

l=1


1 − t 2 (1) t 2, (3.11)= e 2m Lm−1mmwhich equals the spectral density function of the m × m GUE (see [27]).
As the density and the characteristic function are a Fourier transform pair, eachcan be recovered from the other through either the Fourier or the inverse Fouriertransform (see for example [34, 35]). Since the characteristic function is given byφm (t) = E eitXm = ∞−∞eitx fm (x) dx(3.12)(where Xm is a random variable with density fm ), the density is regained by the
relation ∞1
fm (x) = φm (x) =e−itx φm (t) dt.
(3.13)
2π −∞Taking the Fourier transform of the characteristic function φm (t), and interchanging
the sum and the integral, we get
1
fm (x) =
2π
=−

 2
t2
m 
1
−t
e− 2m  ml (l − 1)! m
−∞ m

 ∞

l−1

e−itx dt

l=1

1
2π

m 


 ∞

l=1

−∞

m
1
(−m)−ll (l − 1)!

t2

t 2(l−1) e− 2m e−itx dt

m 
1
1  m
=−
(−m)−l Im .
l (l − 1)!
2π(3.14)

l=1

Completing the square in the integrand of Im , we obtainmx 2

Im = e − 2



√
t
1
t 2(l−1) exp −√ + i mx
2
m
−∞

 ∞

2

dt.

√
Changing variables by y = √1m t + i mx, dy = √1m dt, we find Im equals(3.15)

1040

J Theor Probab (2013) 26:1020–1060
mx 2

Im = e − 2

mx 2

 ∞
−∞
1

= e− 2 ml− 2

y2 √
√
√
(y − i mx)2(l−1) ( m)2(l−1) e− 2 m dy2(l−1) 
s=0√2(l − 1)(−i mx)2(l−1)−s
s

 ∞
−∞

y2

y s e− 2 dy. (3.16)√
The integral above is the sth moment of the Gaussian, and is 2π (s − 1)!! for even s
and 0 for odd s. Since the odd s terms vanish, we replace the variable s with 2s andsum over 0 ≤ s ≤ (l − 1). We find
l−1 

2
√
l−1−s2(l − 1) 
− mx2
l− 12
Im = 2π em(2s − 1)!!.
−mx 2
2s

(3.17)

s=0

Substituting this expression for Im into (3.14) and making the change of variablesr = l − 1 − s, we find that the density ism−r 
mx 2 m−1m(2r + 2s)!
1e− 2  1−
fm (x) = √22πm r=0 (2r)! s=0 r + s + 1 (r + s)!s!

s 2 rmx . (3.18)
This completes the proof of Theorem 1.4(1).
3.2 The m → ∞ Limit and the Semi-circle

Before proving Theorem 1.4(2), we first derive expressions for the limits of the average moments of the symmetric m-block Toeplitz ensemble. We sketch the argument.
Though the analysis is similar to its circulant cousin, it presents more difficult combinatorics. Because diagonals do not “wrap around”, certain diagonals are better tobe on than others. Consequently, the Diophantine obstructions of [18] are present.
The problems are the matchings with “crossings”, or, in topological language, thosematchings which give rise to tori with genus g ≥ 1 as opposed to spheres with g = 0.
For a detailed analysis of the Diophantine obstructions and how the added circulant
structure fixes them, see [18] and [29]. Fortunately, it is easy to show that the contributions to the 2kth moment of the symmetric m-block Toeplitz distribution fromthe non-crossing (i.e, the spherical matchings or, in the language of [5], the Catalan
words) are unhindered by Diophantine obstructions and thus contribute fully.
The

1 2k
number of these matchings is Ck , which is the kth Catalan number k+1
as
well
k
as the 2kth moment of the Wigner density
fWig (x) =1π0

1 − ( x2 )2

if |x| ≤ 2,

(3.19)

otherwise.

Note that with this, normalization we have a semi-ellipse √and not a semi-circle;
to√obtain the semi-circle, we normalize the eigenvalues by 2 N and not N . As theother matchings contribute zero in the limit, we obtain convergence to the Wigner
semi-circle as m → ∞. We now prove the above assertions.

J Theor Probab (2013) 26:1020–1060

1041

Lemma 3.1 The limit of the average of the 2kth moment of the symmetric m-block
Toeplitz ensemble equals2kM2k;m = Ck +d(k, g)m−2g ,(3.20)

g=1

where Ck is the kth Catalan number and d(k, g) ∈ [0, 1] are constants corresponding
to the total contributions from the genus g pairings for the 2kth moment.
Proof For the symmetric m-block Toeplitz ensemble, the analysis in Sect. 2 applies
almost exactly. In the condition for aij = ai j , equality replaces congruence modulo N :• j − i = j − i and i ≡ i (mod m), or• j − i = −(j − i ) and i ≡ j (mod m).
These constraints are more restrictive, so we again obtain 2n−l N l+1 as an upperbound on the number of solutions. Following the previous argument, the odd moments are M2k+1;m (N ) = Ok ( √1 ), and the even moments areN

M2k;m (N ) =



1
N k+1


η(σ ) + Ok

σ

1
,
N

(3.21)

where η(σ ) is the number of solutions to the Diophantine equations arising from thepairings σ on {(1, 2), (2, 3), . . . , (2k, 1)} of the indices. Thus the odd moments vanishin the limit. Moreover, the only matchings that contribute are the ones with negative
signs. To see this fact, one can follow the proof of Lemma 2.3, except working in Z
instead of Z/NZ.
While it is known that most matchings for the real symmetric Toeplitz ensemble
do not contribute fully, a general expression for the size of the contributions is unknown, though there are expressions for these in terms of volumes of Eulerian solids(see [10]) or obstructions to Diophantine equations (see [18]). These expressions imply that each matching contributes at most 1. We introduce constants to denote theircontribution (this corresponds to the m = 1 case). This allows us to handle the real
symmetric m-block Toeplitz ensemble, and (arguing as in the proof of Lemma 2.4),
write the limit of the average of the 2kth moments as2k

M2k;m =d(k, g)m−2g .

(3.22)

g=0

Here d(k, g) is the constant corresponding to the contributions of the genus g matchings. All that is left is to show that d(k, 0), the contributions from the non-crossingor spherical matchings, is the Catalan number Ck .
We know that the number of non-crossing matchings of 2k objects into k pairs is
the Catalan number Ck . This is well known in the literature. Alternatively, we know
the number of non-crossing matchings is ε0 (k), as these are the ones that give the1042

J Theor Probab (2013) 26:1020–1060

genus 0 sphere. The claim follows immediately from (3.2) by taking the constant3
term (as g = 0) and noting tanh( x2 ) = x2 − x24 + · · · . We are thus reduced to proving
that, even with the mod m periodicity, each of these pairings still contributes 1.
One way of doing this is by induction on matchings. Consider a non-crossing
configuration of contributing matchings for the 2kth moment. Consider an arbitrary
matching in the configuration, and denote the matching by α1 . The matching corresponds to an equation is − is+1 = it+1 − it . If the matching is adjacent, meanings = t + 1, then it+1 is free and it = it+2 , and there is no “penalty” (i.e., a decreasein the contribution) from the (mod m) condition. We call this having the ends ofa matching “tied” (note that adjacent matchings always tie their ends). Otherwise,note that since we are looking at even moments, there are an even number of indices. Thus, to either side of the matching α1 there can only be an even number ofindices matched between themselves, since otherwise some matching would be crossing over α1 . Thus, to either side, we are reduced to the non-crossing configurations
for a lesser moment. By induction, these two sub-configurations are tied, and thentrivially tie with our initial matched pair. As at each step there were no obstructions
on the indices, this matching contributes fully, completing the proof.

Our claims about convergence to semi-circular behavior now follow immediately.
Proof of Theorem 1.4(2) It is trivial to show that the symmetric m-block circulant
ensemble has its limiting spectral distribution converge to the semi-ellipse as m → ∞because we have an explicit formula for its moments. From Lemma (2.4), we see thatlim M2k;m (N ) = lim

m→∞

m→∞

 εg (k)
g≤ k2

m2g

= ε0 (k),(3.23)

which in the proof of Lemma 3.1 we saw equals the Catalan number Ck .
We now turn to the symmetric m-block Toeplitz case. The proof proceeds similarly. From Lemma 3.1 we have d(k, g)
Ck +
m→∞
m2g
k

lim M2k;m = limm→∞= Ck ,(3.24)g≤ 2completing the proof.



4 Convergence of the Limiting Spectral Measures
We investigate several types of convergence.
(1) (Almost Sure Convergence) For each k, Xk;m,N → Xk,m almost surely if
Pm A ∈ Ωm : Xk;m,N (A) → Xk,m (A) as N → ∞ = 1;

(4.1)

J Theor Probab (2013) 26:1020–1060

1043(2) (Convergence in Probability) For each k, Xk;m,N → Xk,m in probability if for all
> 0,



(4.2)
lim Pm Xk;m,N (A) − Xk,m (A) > = 0;
N →∞(3) (Weak Convergence) For each k, Xk;m,N → Xk,m weakly if
Pm Xk;m,N (A) ≤ x → P Xk,m (A) ≤ x(4.3)

as N → ∞ for all x at which FXk,m (x) := P(Xk,m (A) ≤ x) is continuous.
Alternate notations are to say either with probability 1 or strongly for almost sureconvergence and in distribution for weak convergence; both almost sure convergenceand convergence in probability imply weak convergence. For our purposes we take
Xk,m as the random variable which is identically Mk,m , the limit of the average mth
moment (i.e., limN →∞ Mk,m;N ), which we show below exist and uniquely determine
a probability distribution for our ensembles.
We have proved the first two parts of Theorem 1.4, which tells us that the limiting
spectral measures exist and giving us, for the symmetric m-block circulant ensemble,
a closed form expression for the density. We now prove the rest of the theorem, anddetermine the various types of convergence we have. We first prove the claimed uniform convergence of part (3), and then discuss the weak, in probability, and almost
sure convergence of part (4).
We use characteristic functions and Fourier analysis to show uniform (and thus
pointwise) convergence of the limiting spectral distribution of the symmetric m-block
circulant ensemble to the semi-ellipse distribution (remember it is an semi-ellipse andnot a semi-circle due to our normalization). We note that this implies Lp convergencefor every p. The proof follows by showing the characteristic functions are close, andthen the Fourier transform gives the densities are close.
Proof of Theorem 1.4(3) The density fm is the Fourier transform of φm (equivalently,
φm is the characteristic function associated with the density fm , where we have tobe slightly careful to keep track of the normalization of the Fourier transform; see(3.12)); similarly the Wigner distribution fWig (x) is the Fourier transform of φ, where
the Wigner distribution (a semi-ellipse in our case due to our normalizations) is
fWig (x) =1π

1 − ( x2 )20

if |x| ≤ 2,

(4.4)

otherwise.

As our densities are nice, we may use the Fourier inversion formula to evaluate
the difference. We find for any > 0 that


 ∞

 

 −itx 
φ̂m (x) − φ̂(x) =  1
φm (t) − φ(t) e
dt 
 2π
−∞
 ∞


φm (t) − φ(t) dt≤−∞
2

m− 9 + ,

(4.5)

1044

J Theor Probab (2013) 26:1020–1060

where the bound for this integral is proved in Lemma A.1 and follows from standard
properties of Laguerre polynomials and Bessel functions. Thus, as m → ∞, fm (x) =φ̂m (x) converges to fWig (x) = φ̂(x) for all x ∈ R. As the bound on the difference
depends only on m and not on x, the convergence is uniform.
We now show Lp convergence. We have L∞ convergence because it is equivalent
to a.e. uniform convergence. For 1 ≤ p < ∞, we automatically have Lp convergence
as we have both L1 convergence and the L∞ norm is bounded.
Proof of Theorem 1.4(4) The proofs of these statements follow almost immediatelyfrom the arguments in [18, 22, 29], as those proofs relied on degree of freedom arguments. The additional structure imposed by the (mod m) relations does not substantially affect those proofs (as can seen in the generalizations of the arguments from[18] to [29] to [22]).

5 Future Research
We discuss some natural, additional questions which we hope to study in future work.
5.1 Representation Theory
The N × N m-block circulant matrices form a semisimple algebra over R. This algebra may be decomposed into N simple subalgebras of dimension m2 , all but one
or two of which are isomorphic to Mm (C). One can show that, up to first order, thisdecomposition sends our measure on symmetric m-block circulant matrices to them × m Gaussian Unitary Ensemble. One may then give a more algebraic proof of
our results and circumvent the combinatorics of pairings; combining the two proofs
gives a new proof of the results of [19]. This approach will appear in a more general setting in an upcoming paper of Kopp. The general result may be regarded as aCentral Limit Theorem for Artin–Wedderburn decomposition of finite-dimensional
semisimple algebras
5.2 Spacings
Another interesting topic to explore is the normalized spacings between adjacenteigenvalues. For many years, one of the biggest conjectures in random matrix theory was that if the entries of a full, N × N real symmetric matrix were chosen from anice density p (say mean 0, variance 1, and finite higher moments), then as N → ∞the spacing between normalized eigenvalues converges to the scaling limit of theGOE, the Gaussian Orthogonal Ensemble (these matrices have entries chosen fromGaussians, with different variances depending on whether or not the element is on themain diagonal or not). After resisting attacks for decades, this conjecture was finallyproved; see the work of Erdős, Ramirez, Schlein, and Yau [13, 14] and Tao and Vu[37, 38].
While this universality of behavior for differences seems to hold, not just for thesefull ensembles, but also for thin ensembles such as d-regular graphs (see the numerical observations of Jakobson, (S. D.) Miller, Rivin and Rudnick [23]), we clearly doJ Theor Probab (2013) 26:1020–1060

1045

Fig. 8 Density of nonzero
spacings of the 10 central
eigenvalues of 100 1024 × 1024
symmetric circulant matrices,with independent entries picked
i.i.d.r.v. from a Gaussian,normalized to have mean
spacing 1. Compared toexponential and GOE densities

Fig. 9 Density of nonzero spacings of the 10 central eigenvalues of 100 1024 × 1024 symmetric m-block
circulant matrices, with independent entries picked i.i.d.r.v. from a Gaussian, normalized to have mean
spacing 1, with m = 2, 16, 128, 256, 512, 1024, respectively. Compared to exponential and GOE densities

not expect to see GOE behavior for all thin families. A simple counterexample are diagonal matrices; as N → ∞ the density of normalized eigenvalues will be whateverdensity the entries are drawn from, and the spacings between normalized eigenvalues will converge to the exponential. We also see this exponential behavior in other

1046

J Theor Probab (2013) 26:1020–1060

Fig. 10 Density of spacings of the 10 central eigenvalues of 100 1024 × 1024 symmetric m-block Toeplitz
matrices, with independent entries picked i.i.d.r.v. from a Gaussian, normalized to have mean spacing 1,
with m = 1, 2, 4, 16, 128, 1024, respectively. Compared to exponential and GOE densities

ensembles. It has numerically been observed in various Toeplitz ensembles (see [18,29]).
For the ensemble of symmetric circulant matrices, we cannot have strictly exponential behavior because all but 1 or 2 (depending on the parity of Nm ) of the eigenvalues occur with multiplicity two. This can be seen from the explicit formula forthe eigenvalues of a circulant matrix. Thus, the limiting spacing density has a pointof mass 12 at 0. Nonetheless, the nonzero spacings appear to be distributed exponentially; see Fig. 8.
Similarly, for a symmetric m-block circulant matrix, all but N − m or N − m − 1 ofthe eigenvalues occur with multiplicity two. The nonzero spacings appear to have thesame exponential distribution (see Fig. 9). This is somewhat surprising, given that the
eigenvalue density varies with m and converges to the semi-circle as m → ∞. While
we see new eigenvalue densities for m constant, numerics suggest that we’ll see new
spacing densities for N
m constant.

J Theor Probab (2013) 26:1020–1060

1047

However, for symmetric m-block Toeplitz matrices, we see different behavior (seeFig. 10). The spacings look exponentially distributed for m = 1 and appear to converge to the GOE distribution as we increase m. In the Toeplitz case, but not in thecirculant, we see the spacings behaving as the spectral densities do.
The representation theoretic approach will be used to solve the spacings problem
for symmetric m-block circulant matrices in an upcoming paper of Kopp. The spacing
problem for block Toeplitz matrices will require some new innovation.
Acknowledgements M. Koloğlu and G.S. Kopp were partially supported by Williams College and
NSF Grants DMS0855257 and DMS0850577, and S.J. Miller was partly supported by NSF Grant
DMS0970067. It is a pleasure to thank our colleagues from the Williams College 2010 SMALL REU
program as well as the participants of the ICM Satellite Meeting in Probability & Stochastic Processes(Bangalore, 2010) for many helpful conversations, especially Arup Bose and Rajat Hazra. We would also
like to thank Elizabeth Townsend Beazley for comments on Wentao Xiong’s senior thesis, which is thebasis of Appendix B.

Appendix A: Pointwise Convergence as m → ∞This appendix by Gene Kopp, Steven J. Miller and Frederick Strauch.5
The characteristic function for the spectral measures of the period m-block circulant matrices is 2 −1m 
1−t
1 − t2  m
φm (t) = e 2m
,
(A.1)
m
( − 1)! m=1

which solves the differential equationttφm (t) + 3φm (t) + t 4 −m2φm (t) = 0(A.2)

with initial condition φm (0) = 1; letting m → ∞ gives tφ (t) + 3φ (t) + 4tφ(t) = 0,
with initial condition φ(0) = 1. The solution to the finite m equation is a Laguerre
polynomial, and the m = ∞ limit is J1 (2t)with J1 the Bessel function of order 1.
t
To see this, recall that the generalized Laguerre polynomial (see [1]) has the explicit representation
n 

n+α 1
(−x)i .
L(α)
(x)
=
(A.3)
n
n − i i!
i=0

To compare (A.1) with (A.3), we first shift the summation index by one ( → + 1)
to find

m−1 
t2 
m
1 −t 2
1
φm (t) = e− 2m.
(A.4)+1 ! mm=0

5 Department of Physics, Williams College, fws1@williams.edu.

1048

J Theor Probab (2013) 26:1020–1060

Using the identity




m
m
=
+1
m−1−

(A.5)

we see that n = m − 1, α = 1, and thus the characteristic function can be written interms of the Laguerre polynomial:
1 − t 2 (1) t 22m,
φm (t) = e
Lm−1
m
m

(A.6)

or equivalently in terms of the confluent hypergeometric functiont2
t2
φm (t) = e− 2m M m + 1, 2, −
.
m

(A.7)

From 13.2.2 of [1] we have limm→∞ φm (t) = φ(t); however, we need some control on the rate of convergence.
Lemma A.1 Let r > 13 and β = 23 (1 − r). For all m and all t we havem−(1−r)φm (t) − φ(t)

r

t

− 32

if |t| ≤ mβ ,
− 54

+m

t2

exp(− 2m )otherwise,(A.8)

where the implied constant is independent of m but may depend on r. This implies
 ∞
−∞



φm (t) − φ(t) dt

1−r

m− 3 .

(A.9)
2

Letting > 0 and taking r = 13 + 3 implies the integral is O(m− 9 + ).
Proof We first consider small t: |t| ≤ mβ with β = 23 (1 − r). Using 13.3.7 of [1] with2

a = m + 1, b = 2 and z = − tm to bound the confluent hypergeometric function M,
we findt2
t2
φm (t) = e− 2m M m + 1, 2, −m∞=

J1 (2t) +An (2m)−n (−1)n t n−1 Jn+1 (2t),t(A.10)

n=12m
where A0 = 1, A1 = 0, A2 = 1 and An+1 = An−1 + n+1
An−2 for n ≥ 2.
1
For any r > 3 and m sufficiently large we have An ≤ mrn (we cannot do better
than r > 13 as A3 = 23 m). This follows by induction. It is clear for n ≤ 2, and forlarger n we have by the inductive assumption that

J Theor Probab (2013) 26:1020–1060

1049

2m
An−2 ≤ mr(n−1) + m · mr(n−2)
n+1= mr(n+1) · m−2r + m1−3r ;An+1 = An−1 +(A.11)

as r > 13 the above is less than mr(n+1) for m large. If we desire a bound to hold forall m, we instead use An ≤ cr mrn for cr sufficiently large. Substituting this bound for
An into (A.10), noting J1 (2t)= φ(t) and using |Jn (x)| ≤ 1 (see 9.1.60 of [1]) yields,t1−rfor |t| ≤ m ,
φm (t) − φ(t) ≤

∞ 
cr 
t
2m1−r
2m1−r

n−1

−(1−r).
r m(A.12)

n=1

We now turn to t large: |t| ≥ mβ . Using

 
 

φm (t) − φ(t) ≤ φm (t) + φ(t)

(A.13)

to trivially bound the difference, the claim follows the decay of the Bessel and La1
guerre functions. Specifically (see 8.451(1) of [17]), we have J1 (x) x − 2 and thusφ(t) =J1 (2t)t3

t− 2 .

(A.14)For φm (t), we use 8.978(3) of [17], which states

√
π
απ
(α)
− 12 x2 − α2 − 14 α2 − 14
Ln (x) = π e x−ncos 2 nx −24

 α 3
+ O n2−4 ,(A.15)

1

2

so long as Im(α) = 0 and x > 0. Letting x = tm with |t| ≥ 13 log 2 m, α = 1 andn = m − 1 we find
 2
t2
t
(1)
−1 − 2m
φm (t) = m e
Lm−1
m
3



t2
t2
t2 − 4 1−1 − 2m
− 14
2m
4
e
m e
m +m
m
3

t2

5

t − 2 + m− 4 e− 2m .

(A.16)
∞−∞ |φm (t) − φ(t)| dt. The
(1−r)
mβ
β
contribution from |t| ≤ m is easily seen to be Or ( m1−r ) = Or (m− 3 ) with our
choice of β. For |t| ≥ mβ , we have a contribution bounded by

All that remains is to prove the claimed bound for

 ∞
2
mβ

 −3
5
t2 
t 2 + m− 4 e− 2m dt

− β2

m

m−

− 34

+m

(1−r)
3


t2
exp −
dt
√
2m
2πm
−∞

 ∞
3

+ m− 4 ,1(A.17)

1050

J Theor Probab (2013) 26:1020–1060

as the last integral is that of a Gaussian with mean zero and variance m and hence
is 1. (We chose β = 23 (1 − r) to equalize the bounds for the two integrals.)
Appendix B: Generalized m-Block Circulant Matrices
This appendix by Steven J. Miller and Wentao Xiong.6
As the proofs are similar to the proof for m-block circulant matrices, we just highlight the differences. The trace expansion from before holds, as do the arguments thatthe odd moments vanish.
We first explore the modulo condition to compute some low moments, and showthat the difference in the modulo condition between the m-block circulant matrices
and the generalized m-block circulant matrices leads to different values for moments,and hence limiting spectral distributions. Thus the limiting spectral distribution depends on the frequency of each element, as well as the way the elements are arranged,
in an m-pattern.
B.1 Zone-Wise Locations and Pairing Conditions
Since we have restricted the computation of moments to even moments, and haveshown that the only configurations that contribute to the 2kth moment are thosein which the 2k matrix entries are matched in k pairs in opposite orientation, weare ready to compute the moments explicitly. We start by calculating the 2nd moment, which by (2.10) is N12 1≤i,j ≤N aij aj i . As long as the matrix is symmetric,
aij = aj i and the 2nd moment is 1. We now describe the conditions for two entries
ais is+1 , ait it+1 to be paired, denoted as ais is+1 = ait it+1 ⇐⇒ (s, s + 1) ∼ (t, t + 1),
which we need to consider in detail for the computation of higher moments. To facilitate the practice of checking pairing conditions, we divide an N × N symmetricm-block circulant matrix into 4 zones (see Fig. 11), and then reduce an entry ais is+1
in the matrix to its “basic form”. Write i = mη + , where η ∈ {1, 2, . . . , Nm } and∈ {0, 1, . . . , m − 1}, we have(1) 0 ≤ is+1 − is ≤ N2 − 1 ⇒ ais is+1 ∈ zone 1 and ais is+1 = a s ,m(ηs+1 −ηs )+ s+1 ;(2) N2 ≤ is+1 − is ≤ N − 1 ⇒ ais is+1 ∈ zone 2 and ais is+1 = a s+1 ,m(ηs + N −ηs+1 )+ s ;m(3) N2 ≤ is − is+1 ≤ N − 1 ⇒ ais is+1 ∈ zone 3 and ais is+1 = a s ,m(ηs+1 + N −ηs )+ s+1 ;m(4) 0 ≤ is − is+1 ≤ N2 − 1 ⇒ ais is+1 ∈ zone 4 and ais is+1 = a s+1 ,m(ηs −ηs+1 )+ s .
In short, (is+1 − is ) determines which diagonal ais is+1 is on. If ais is+1 is in zone 1 or
3 (Area I), s determines the slot of ais is+1 in an m-pattern; if ais is+1 is in zone 2 or 4
(Area II), s+1 determines the slot of ais is+1 in an m-pattern.
Recall the two basic pairing conditions, the diagonal condition that we have explored before, and the modulo condition, for which we will define an equivalence
relation R. For a real symmetric m-block circulant matrix following a generalized
m-pattern and any two entries ais is+1 , ait it+1 in the matrix, suppose that is and it+1
6 Department of Mathematics and Statistics, Williams College, xx1@williams.edu.

J Theor Probab (2013) 26:1020–1060

1051

Fig. 11 The four zones for
m-block circulant matrices

are the indices that determine the slot of the respective entries, then is Rit+1 if andonly if ais is+1 , ait it+1 are in certain slots in an m-pattern such that these two entries
can be equal. For example, for the {a, b} pattern, is Rit+1 ⇐⇒ is ≡ it+1 (mod 2);
for the {a, a, b, b} pattern, is Rit+1 ⇐⇒ mod (is , 4), mod (it+1 , 4) ∈ {1, 2} ormod (is , 4), mod (it+1 , 4) ∈ {3, 0}.
We now formally define the two pairing conditions.
(1) (diagonal condition) is − is+1 ≡ −(it − it+1 ) (mod N ).
(2) (modulo condition) is Rit+1 or is+1 Rit , depending on which zone(s) ais is+1 , ait it+1
are located in.
Since the diagonal condition implies a Diophantine equation for each of the k pairsof matrix entries, we only need to choose k + 1 out of 2k i ’s, and the remaining i ’s
are determined. This shows that, trivially, the number of non-trivial configurations
is bounded above by N k+1 . In addition, the diagonal condition always ensure that
ais is+1 and ait it+1 are located in different areas. For instance, if ais is+1 ∈ zone 1 andis − is+1 = −(it − it+1 ), then ais is+1 ∈ zone 4; if ais is+1 ∈ zone 1 and is − is+1 =−(it − it+1 ) − N , then ais is+1 ∈ zone 2, etc. Thus, if is determines the slot for ais is+1
in an m pattern, then it+1 determines for ait it+1 ; if is+1 determines the slot for ais is+1 ,then it determines for ait it+1 , and vice versa.
Considering the “basic” form of the entries, the two conditions above are equivalent to(1) (diagonal condition) (mηs + s ) − (mηs+1 + s+1 ) ≡ −(mηt + t ) + (mηt+1 +t+1 )(mod N) ⇒ m(ηs − ηs+1 + ηt − ηt+1 ) + ( s − s+1 + t − t+1 ) = 0 or ±N .
(2) (modulo condition) s R t+1 or s+1 R t .
Since m|N , this requires m|( s − s+1 + t − t+1 ). Given the range of the η ’s and’s, we have s − s+1 + t − t+1 = 0 or ± m, which indicates thatηs − ηs+1 + ηt − ηt+1 = 0, ±1,

N N
NN, ± 1, − , or − ± 1.
m m
m
m

(B.1)

As discussed before, if we allow repeated elements in an m-pattern, the equivalence relation R no longer necessitates a congruence relation as in pattern where each

1052

J Theor Probab (2013) 26:1020–1060

element is distinct. While the computation of high moments for general m-patterns
appears intractable, fortunately we are able to illustrate how the difference in the modulo condition affects moment values by comparing the low moments for two simple
patterns {a, b, a, b} and {a, a, b, b}.
B.2 The Fourth Moment
Although we can show that the higher moments differ by the way the elements arearranged in an m-pattern, the 4th moment is in fact independent of the arrangementof elements. We show that the 4th moment for any m-pattern is determined solely by
the frequency at which each element appears, and refer the reader to Appendix B.3
of [25] (or [45]) for the computation that the 6th moment depends on not just thefrequencies but also the pattern; we omit the proof as it is similar to the computationof the 4th moment, although significantly more book-keeping is required. Briefly,
for the higher moments for patterns with repeated elements, there exist “obstructions
to modulo equations” that make trivial some non-trivial configurations for patterns
without repeated elements. Due to the obstructions to modulo equations, some configurations that are non-trivial for all-distinct patterns become trivial for patterns withrepeated elements, making the higher moments for repeated patterns smaller.
Lemma B.1 For an ensemble of real symmetric period m-block circulant matrices ofsize N , if within each m-pattern we have n i.i.d.r.v. {αr }nr=1 , each of which has a fixed
number of occurrences νr such that nr=1 νr = m, the 4th moment of the limiting
spectral distribution is 2 + nr=1 ( νmr )3 .
By (2.10), we calculate

1
4 +1

N2

1≤i,j,k,l≤N aij aj k akl ali for the 4th moment. Thereare 2 ways of matching the 4 entries in 2 pairs:(1) (adjacent, 2 variations) aij = aj k and akl = ali (or equivalently aij = ali andaj k = akl );(2) (diagonal, 1 variation) aij = akl and aj k = ali .
There are 3 matchings, with the two adjacent matchings contributing the same to the
4th moment. We first consider one of the adjacent matchings, aij = aj k and akl = ali .
The pairing conditions (B.1) in this case are:(1) (diagonal condition) i − j ≡ k − j (mod N ), k − l ≡ i − l(mod N );(2) (modulo condition) iRk or j Rj , kRi or lRl.
Since 1 ≤ i, j, k, l ≤ N , the diagonal condition requires i = k, and then the modulo condition follows trivially, regardless of the m-pattern we study. Hence, we canchoose j and l freely, each with N choices, i freely with N choices, and then k is3
fixed. This matching then contributes N4 +1 = 1 (fully) to the 4th moment, so doesN2

the other adjacent matching.
We proceed to the diagonal matching, aij = akl and aj k = ali . The pairing conditions (B.1) in this case are:(1) (diagonal condition) i − j ≡ l − k(mod N ), j − k ≡ i − l(mod N );

J Theor Probab (2013) 26:1020–1060

1053(2) (modulo condition) iRl or j Rk, j Ri or kRl.
The diagonal condition j − k ≡ i − l(mod N ) is equivalent to i − j ≡ l − k(mod N ),which entails(1) i + k = j + l, or(2) i + k = j + l + N , or
(3) i + k = j + l − N .
In any case, we only need to choose 3 indices out of i, j, l, k, and then the last one
is fixed. In the following argument, without loss of generality, we choose (i, j, l) andthus fix k.
For a general m-pattern, we write i = 4η1 + 1 , j = 4η2 + 2 , k = 4η3 + 3 , l =4η4 + 4 , where η1 , η2 , η3 , η4 ∈ {0, 1, . . . , Nm } and 1 , 2 , 3 , 4 ∈ {0, 1, . . . , m − 1}.
Before we consider the ’s, we note that there exist Diophantine constraints. For
example, if i + k = j + l, given that 1 ≤ i, j, l ≤ N , k = j + l − i also needs tosatisfy 1 ≤ k ≤ N . As a result, we need 0 ≤ η2 + η4 − η1 ≤ N4 . Note that, due tothe ’s, sometimes we may have 0 ≤ η2 + η4 − η1 ≤ N4 + ε, where the error termε ∈ (− m2 , m2 ) and only trivially affects the number of choices of (η2 , η4 , η1 ) for a
fixed m as N → ∞.
We now explore the Diophantine constraints for each variation of the diagonalcondition (B.1). The i + k = j + l case is similar to that in [18], where, in a Toeplitz
matrix, the diagonal condition only entails i + k = j + l, and there are obstructions
to the system of Diophantine equations following the diagonal condition. However,the circulant structure that adds i + k = j + l + N and i + k = j + l − N to the diagonal condition fully makes up the Diophantine obstructions. This explains why thelimiting spectral distribution for ensembles of circulant matrices has the moments ofa Gaussian, while that for ensembles of Toeplitz matrices has smaller even moments.
We now study the 3 possibilities of the diagonal condition for the circulant structure.
(1) Consider i + k = j + l. We use Lemma 2.5 from [18] to handle the obstructions
to Diophantine equations, which says: Let IN = {1, . . . , N}. Then #{x, y, z ∈ IN :1 ≤ x + y − z ≤ N} = 23 N 3 + 13 N .
In our case, let M = N
m . The number of possible combinations of (η2 , η4 , η1 )Nthat allow 0 ≤ η3 ≤ 4 is 23 M 3 + 13 M.7 For each of η2 , η4 , η1 , we have m freechoices of , and thus the number of (i, j, l) is m3 ( 23 M 3 + 13 M) = 23 N 3 + O(N ).
(2) Consider i + k = j + l + N . Note 1 ≤ k ≤ N requires 0 ≤ η2 + η4 − η1 + N
m ≤
N
N
N
⇒
−
≤
η
+
η
−
η
≤
0.
Similar
to
the
i
+
k
=
j
+
l
case,
we
write
M
=
2
4
1
m
m
m
and S = η2 + η4 , and then − N
m ≤ S − η1 ≤ 0 ⇒ S ≤ η1 ≤ M + S where obviously
S ≤ M. We have S + 1 ways to choose (η2 , η4 ) s.t. η2 + η4 = S, and M − S + 1
choices of η1 . The number of (i, j, l) is thus
m3

M

S=0


(S + 1)(M − S + 1) = m3

 
M3
N3
5
+ M2 + M =+ O N 2 . (B.2)
666

7 In [18], the related lemma is proven for η , η , η ∈ N , i.e., no cases where η η η = 0. Thus we are
+
2 4 1
2 4 1

supposed to start from S = 0; however, as N → ∞, the error from this becomes negligible.

1054

J Theor Probab (2013) 26:1020–1060(3) Consider i + k = j + l − N . Now 1 ≤ k ≤ N requires 0 ≤ η2 + η4 − η1 − N
m ≤
N
N
2N
N
m ⇒ m ≤ η2 + η4 − η1 ≤ m . Again, we write M = m and S = η1 + η4 , andthen M ≤ S − η1 ≤ 2M ⇒ S − 2M ≤ η1 ≤ S − M where obviously S ≥ M. We
have 2M − S + 1 ways to choose (η2 , η4 ) s.t. η2 + η4 = S, and S − M + 1 choicesof η1 . The number of (i, j, l) is thus
m3

2M



(2M − S + 1)(S − M + 1) = m3

S=M

=

M3
5
+ M2 + M
6
6

 
N3
+ O N2 .
6(B.3)

Therefore, with the additional diagonal conditions i + k = j + l + N and i + k =j + l − N induced by the circulant structure, the number of (i, j, l) is of the order ( 23 +1
1
3
3
6 + 6 )N = N , i.e. the circulant structure makes up the obstructions to Diophantine
equations in the Toeplitz case. Since the η ’s do not matter for the modulo condition,
to make a non-trivial configuration, we may choose three η ’s freely, each with Nmchoices, and then choose some ’s that satisfy the modulo condition, which we will
study below.
For the modulo condition, it is necessary to figure out which zones the four entries
are located in. Recall that the diagonal condition will always ensure that two paired
entries are located in different areas. For the 4th moment, each of the 3 variations of
the diagonal condition is sufficient to ensure that any pair of entries involved are located in the right zones. We may check this rigorously by enumerating all possibilitiesof the zone-wise locations of the 4 entries, e.g. if i + k = j + l + N , if aij ∈ zone 1,
then akl ∈ zone 2.8 As a result, for a pair of matrix elements in the diagonal matching, say aij = akl , if i determines the slot in an m-pattern for aij and thus mattersfor the modulo condition, then l determines for akl ; if j determines for aij , then kdetermines for akl , and vice versa.
With the zone-wise issues settled, we study how to obtain a non-trivial configuration for the 4th moment. Recall the modulo condition for the diagonal matching:iRl or j Rk, j Ri or kRl. This entails 22 = 4 sets of equivalence relations,
iRlRj ; iRlRk, j RkRi, j RkRl.

(B.4)

Each set of equivalence relations appears with a certain probability, depending on
the zone-wise locations of the 4 entries. For example, iRlRj follows from iRl andj Ri, which requires both aij and aj k ∈ Area I. Regardless of the probability withwhich each set occurs, we choose one free index with N choices, and then anothertwo indices such that these 3 indices are related to each other under R. The numberof choices of the two indices after the free one is determined solely by the number ofoccurrences of the elements in an m-pattern.
8 This enumeration is complicated since the zone where an entry a is located imposes restrictions on theijchoice of i, j , e.g. when ai,j ∈ zone 2, we have i ≥ N2 and j ≤ N2 .

J Theor Probab (2013) 26:1020–1060

1055

We give a specific example of making a non-trivial configuration for the 4th for
two simple patterns {a, b, a, b} and {a, a, b, b}. Under the condition i + k = j + l,
if aij ∈ zone 1 and aj k ∈ zone 3, then akl ∈ zone 4 and ali ∈ zone 2. We first selectη1 , η2 , η4 such that i, j, l and k = j + l − i satisfy the zone-wise locations.9 In thiscase, based on pairing conditions (B.1), pairing aij = akl and aj k = ali will require1 R 4 and 2 R 1 , or equivalently 1 R 2 R 4 . Without loss of generality, we can startwith a free 1 with 4 choices, then there are 2 free choices for each of 2 and 4 , andthen we have a non-trivial configuration. We have similar stories under the other two
variations of the diagonal condition and with other zone-wise locations of aij andakl . Therefore, we can choose three out of four η ’s freely, each with N4 choices,then one with 4 choices, then another two ’s each with 2 choices, and finally thelast index is determined under the diagonal condition. As discussed before, such a
choice of indices will always satisfy the zone-wise requirements and thus the -based
3
pairing conditions. Thus there are ( N4 )3 · 4 · 2 · 2 = N4 choices of (i, j, k, l) that willproduce a non-trivial configuration. It follows that the contribution from the diagonal
3
matching to the 4th moment is N13 ( 23 + 16 + 16 ) N4 = 14 .
The computation of the 4th moment for the simple patterns {a, b, a, b} and{a, a, b, b} can be immediately generalized to the 4th moment for other patterns.
As emphasized before, both adjacent matchings contribute fully to the 4th moment
regardless of the m-pattern. For diagonal matching, the system of Diophantine equations induced by the diagonal condition are also independent of the m-pattern inquestion, and the way we count possible configurations can be easily generalized toan arbitrary m-pattern. We have thus proved Lemma B.1.
Note that Lemma B.1 implies that the 4th moment for any pattern depends
solely on the frequency at which each element appears in an m-period. Besides the{a, a, b, b} pattern that we have studied in depth, we may easily test two extreme
cases. One case where n = m, i.e. each random variable appears only once, represents
the m-block circulant matrices from Theorem 1.4 for which the 4th moment is 2 + m12(and m = 1 represents the circulant matrices for which the 4th moment is 3). Numerical simulations for numerous patterns including {a, a, b}, {a, b, b}, {a, b, b, a},{a, b, c, a, b, c}, {a, b, c, d, e, e, d, c, b, a} et cetera support Lemma B.1 as well; we
present results of some simulations in Tables 1, 2 and 3.
B.3 Existence and Convergence of High Moments
Although it is impractical to find every moment for a general m-block circulant pattern using brute-force computation, we are still able to prove that, for any m-block
circulant pattern, every moment exists, is finite (and satisfies certain bounds), and that
there exists a limiting spectral distribution. In addition, the empirical spectral measure of a typical real symmetric m-block circulant matrix converge to this limiting
measure, and we have convergence in probability and almost sure convergence.
We have shown that all the odd moments vanish as N → ∞, and thus we focus on
the even moments. We need to prove the following theorem.
9 It is noteworthy that the specific location of an element still depends on the’s, but as N → ∞, the probability that the η ’s alone determine the zone-wise locations of elements approaches 1, i.e. the probability
that adding the ’s changes the zone-wise location of an element approaches 0.

1056

J Theor Probab (2013) 26:1020–1060

Table 1 Comparison of moments for various patterns involving a and b. The first column are the theoretical values for the moments of the pattern a, b, and the final are the moments of the standard normal. The
middle three columns are 200 simulations of 4000 × 4000 matrices
abab (theory)kabab (observed)

aabb (observed)

abba (observed)

N (0, 1)2

1.00001.00161.0014

0.997242.25002.25832.25412.24051
3

67.50007.55777.32127.293815

832.8125

33.2506

30.482230.5631105

10177.1880

180.8270

153.9530

155.6930

945

Table 2 Comparison of moments for various patterns involving a and b. The first column are the theoretical values for the moments of the pattern a, b. The remaining columns are 200 simulations of 3600 × 3600
matriceskabababaaabbbaaaabbbb

aaaaabbbbb

aababb2

1.00001.00081.0001

0.99840.999642.25002.25412.24412.24492.250267.50007.30117.20987.25517.2319832.812530.374429.5004

30.012729.537810

177.1880

155.0380

145.8240

150.7220145.4910

Table 3 Comparison of moments for various patterns involving a and b. The first column are the theoretical values for the moments of the pattern a, b, c. The remaining columns are 200 simulations of3600 × 3600 matriceskabcabcabccbaaabbccabbccaaabcbc21.00001.00051.0006

0.99831.00134

2.1111

2.11222.1153

2.10472.116166.1111

6.02486.05406.00836.0235822.0370

20.9398

21.2004

20.9908

20.841110

94.629685.024187.0857

85.990284.2097

Theorem B.2 For any patterned
limN →∞ M2k (N ) exists and is finite.

m-block

circulant

matrixensemble,

Proof It is trivial that M2k (N ) is finite. As discussed before, it is bounded below
by the 2kth moment for the ensemble of m-block circulant matrices where, in them-pattern, each element is distinct, and more importantly it is bounded above by the
2kth moment for the ensemble of circulant matrices, and we know that the limiting
spectral distribution for this matrix ensemble is a Gaussian.
We now show that limN →∞ M2k (N ) exists. To calculate M2k (N ), we match 2k
elements from the matrix, {ai1 i2 , ai2 i3 , . . . , ai2k i1 }, in k pairs, where i ∈ {1, 2, . . . , N}
and this will give (2k − 1)!! matchings. For each matching, there are a certain number

J Theor Probab (2013) 26:1020–1060

1057

of configurations, and most of such configurations do not contribute to the moments
as N → ∞.
For the m-block circulant pattern, the equivalence relation R implies thats R t+1 ⇔ s = t+1 , and since m|( s − s+1 + t − t+1 ), we have s+1 = t as
well (see (B.1)).10 Thus ηs − ηs+1 + ηt − ηt+1 = 0 or ± N
m , three equations that have
3 + O(( N )2 ) solutions in total, as we have shown in the 4th moment computation.
)(Nmm
However, if there are repeated elements in an m-period, then s R t+1 no longer
necessitates s = t+1 , and it is possible that ( s − s+1 + t − t+1 ) = ±m. Thus, thezone-wise locations of elements matter in making non-trivial configurations. Recall
that the zone-wise location (see (B.1)) of an element ais is+1 is determined by (is+1 −is ): if ais is+1 is in zone 1 or 3 (Area I), s determines the slot of ais is+1 in an m-period;
if ais is+1 is in zone 2 or 4 (Area II), s+1 determines the slot of ais is+1 in an m-period.
In addition, the diagonal condition will always ensure that two paired entries ais is+1
and ait it+1 are located in different areas.
Recall that for any matching M, the k pairs of matrix elements, each pair in theform of ais is+1 = ait it+1 , are fixed. For any M, to make a non-trivial configuration,
we first choose an vector of length 2k. If we choose all the ’s freely, there are m2k
possible choices for an vector, most of which do not meet the modulo condition,and trivially, m2k is an upper bound for the number of valid vectors. It is noteworthy that out of the 2k ’s of an vector, only some of the ’s will matter for themodulo condition. Which ’s in fact matter depends on how we pair the 2k matrix
entries ais is+1 ’s and the zone-wise locations of the paired ais is+1 ’s, which we cannot
determine without fixing the η ’s (and thus the i ’s).
However, for any matching, the way we pair the 2k matrix entries into k pairs isfixed, and for each fixed pair ais is+1 = ait it+1 , two ’s will matter for the modulo
condition: either s R t+1 or s+1 R t . Thus there are 2k ways to choose k pairs of’s for each matching. For each way of fixing the k pairs of ’s, we examine eachpair, say ( 1 , 2 ), and there are a certain number of choices of ( 1 , 2 ) suchthat 1 R 2 . Continuing in this way, for each pair, we choose two ’s that satisfy
the equivalence relation R. Note that an
may matter twice, once, or never forthe modulo condition depending on the zone-wise locations of the ais is+1 ’s. We thenchoose the other ’s that do not matter for the modulo condition such that for eachpair of ais is+1 = ait it+1 , we have s − s+1 + t − t+1 = 0 or ± m, and finally wehave a valid vector. The number of valid vectors will be determined by m, k,
and the pattern of an m-period, but will be independent of N since the system of kequivalence relations for the modulo condition does not involve N .
With a valid vector, we have fixed the zone-wise locations of the 2k matrix
elements by fixing the ’s that matter for the modulo condition. We now turn to the
diagonal condition and study the η ’s. With k equations in the form ofm(ηs − ηs+1 + ηt − ηt+1 ) + ( s − s+1 + t − t+1 ) = 0 or ±N,(B.5)

10 This explains why, for an m-pattern without repeated elements, the zone-wise locations of matrix entries

do not matter in making a non-trivial configuration.

1058

J Theor Probab (2013) 26:1020–1060

and ( s − s+1 + t − t+1 ) known in each of the k equations, we in fact have kequations in the form ofηs − ηs+1 + ηt − ηt+1 = γ ,

(B.6)

N
N
N
where γ ∈ {0, ±1, N
m , m ± 1, − m , − m ± 1}. This gives us k + 1 degrees of freedom
k+1 vectors of η ’s. Since
in choosing the η ’s, and trivially, we can have at most ( Nm)the vector is fixed, for one equation ηs − ηs+1 + ηt − ηt+1 = γ , there are only
3 choices of γ . With k equations in this form, we have at most 3k systems of η
equations. Note that not all of the η vectors satisfying an η equation system derived
from the diagonal condition will help make a non-trivial configuration, since the η ’sneed to be chosen such that the resulted ais is+1 ’s will satisfy the zone-wise locations
in order to be coherent with the pre-determined vector. For example, if in a pair ofmatrix entries ais is+1 = ait it+1 where s R t+1 , even though the η ’s are chosen suchthat ηs − ηs+1 + ηt − ηt+1 = γ , it is possible that ais is+1 , ait it+1 are located in certain
zones such that we need s+1 R t to ensure a non-trivial configuration.
The following steps mirror those in [18]. Denote an η equation system by S. For
ηany S we have k equations with η1 , η2 , . . . , η2k ∈ {1, 2, . . . , Nm }. Let z = N/m ∈m 2m{N, N , . . . , 1}. Without the zone-wise concerns discussed before, the system of kequations would have k + 1 degrees of freedom and determine a nice region in the(k + 1)-dimensional unit cube. Taking into account the zone-wise concerns, however,
we will still have k + 1 degrees of freedom. For example, for a pair of matrix elements ais is+1 = ait it+1 , the system S requires ηs − ηs+1 + ηt − ηt+1 = γ . If we needs R t+1 to make a non-trivial configuration, say ais is+1 ∈ zone 1, then we will obtainan additional equation 0 ≤ is+1 − is ≤ N2 − 1 ⇒ 0 ≤ (ηs+1 − ηs ) + s+1 − s ≤ N2 − 1with ( s+1 − s ) ∈ {−m + 1, −m + 2, . . . , 0, 1, . . . , m − 2, m − 1}. Based on the region determined by ηs − ηs+1 + ηt − ηt+1 = γ , this additional zone-related restriction
will only allow a slice of the region for us to choose valid η ’s. With k zone-wise restrictions, only a proportion of the original region in the unit cube will be preserved
for the choice of the η vector. Nevertheless, the “width” of each slice is of order N2 ,and we still have k + 1 degrees of freedom.
Therefore, with m fixed and as N → ∞, we obtain to first order the volume of
k+1 +this region, which is finite. Unfolding back to the η ’s, we obtain M2k (S)( Nm)N kOk (( m ) ), where M2k (S) is the volume associated with this η system. Summing overall η systems, we obtain the number of non-trivial configurations for the 2kth momentfrom this particular vector. Next, within a given matching M, we sum over all valid
vectors, the number of which is independent of N as we have shown before. In theend, we sum over the (2k − 1)!! matchings to obtain M2k N k+1 + Ok (N k ), and thek+1 +O (N k )k2kth moment is simply M2k N N k+1= M2k + O( N1 ).


The above proves the existence of the moments. The convergence proof follows
with only minor changes to the convergence proofs from [18, 29].

J Theor Probab (2013) 26:1020–1060

1059

References
1. Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions. Dover, New York (1965). Online at http://people.math.sfu.ca/~cbm/aands/
2. Baik, J., Borodin, A., Deift, P., Suidan, T.: A model for the bus system in Cuernevaca (Mexico). Math.
Phys. (2005), 1–9. Online available at http://arxiv.org/abs/math/0510414
3. Basak, A., Bose, A.: Limiting spectral distribution of some band matrices. Periodica Math. Hungarica
63(1), 113–150 (2011)
4. Basak, A., Bose, A.: Balanced random Toeplitz and Hankel matrices. Electron. Comm. Probab. 15,
134–148
5. Banerjee, S., Bose, A.: Noncrossing partitions, Catalan words and the semicircle law. J. Theor. Probab.
doi:10.1007/s10959-011-0365-4
6. Beckwith, O., Miller, S.J., Shen, K.: Distribution of eigenvalues of weighted, structured matrix ensembles, preprint
7. Bose, A., Chatterjee, S., Gangopadhyay, S.: Limiting spectral distributions of large dimensional random matrices. J. Indian Stat. Assoc. 41, 221–259 (2003)
8. Bose, A., Hazra, R.S., Saha, K.: Patterned random matrices and notions of independence, Technical Report R3/2010 (2010), Stat-Math Unit, Kolkata. Available online at http://www.isical.
ac.in/~statmath
9. Bose, A., Mitra, J.: Limiting spectral distribution of a special circulant. Stat. Probab. Lett. 60(1),111–120 (2002)
10. Bryc, W., Dembo, A., Jiang, T.: Spectral measure of large random Hankel, Markov, and Toeplitz
matrices. Ann. Probab. 34(1), 1–38 (2006)
11. Dyson, F.: Statistical theory of the energy levels of complex systems: I, II, III. J. Math. Phys. 3,
140–156 (1962), 157–165, 166–175
12. Dyson, F.: The threefold way. Algebraic structure of symmetry groups and ensembles in quantum
mechanics. J. Math. Phys. 3, 1199–1215 (1962)
13. Erdős, L., Ramirez, J.A., Schlein, B., Yau, H.-T.: Bulk Universality for Wigner Matrices, preprint.
http://arxiv.org/abs/0905.4176
14. Erdős, L., Schlein, B., Yau, H.-T.: Wegner estimate and level repulsion for Wigner random matrices,
preprint. http://arxiv.org/abs/0905.4176
15. Firk, F.W.K., Miller, S.J.: Nuclei, primes and the random matrix connection. Symmetry 1, 64–105(2009). doi:10.3390/sym1010064
16. Forrester, P.J.: Log-Gases and Random Matrices. London Mathematical Society Monographs, vol. 34.
Princeton University Press, Princeton (2010)
17. Gradshteyn, I., Ryzhik, I.: Tables of Integrals, Series, and Products. Academic Press, New York(1965)
18. Hammond, C., Miller, S.J.: Eigenvalue spacing distribution for the ensemble of real symmetric
Toeplitz matrices. J. Theor. Probab. 18(3), 537–566 (2005)
19. Harer, J., Zagier, D.: The Euler characteristic of the moduli space of curves. Invent. Math. 85, 457–485(1986)
20. Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)
21. Hayes, B.: The spectrum of Riemannium. Am. Sci. 91(4), 296–300 (2003)
22. Jackson, S., Miller, S.J., Pham, V.: Distribution of eigenvalues of highly palindromic Toeplitz matrices. http://arxiv.org/abs/1003.2010
23. Jakobson, D., Miller, S.D., Rivin, I., Rudnick, Z.: Eigenvalue spacings for regular graphs. In: Emerging Applications of Number Theory, Minneapolis, 1996. The IMA Volumes in Mathematics and its
Applications, vol. 109, pp. 317–327. Springer, New York (1999)
24. Kargin, V.: Spectrum of random Toeplitz matrices with band structure. Electron. Commun. Probab.
14, 412–421 (2009)
25. Kopp, G.S., Koloğlu, M., Miller, S.J., Strauch, F., Xiong, W.: The limiting spectral measure for ensembles of symmetric block circulant matrices. arXiv version. http://arxiv.org/abs/1008.4812
26. Krbalek, M., Seba, P.: The statistical properties of the city transport in Cuernavaca (Mexico) andRandom matrix ensembles. J. Phys. A, Math. Gen. 33, L229–L234 (2000)
27. Ledoux, M.: A recursion formula for the moments of the Gaussian orthogonal ensemble. Ann. IHP
45(3), 754–769 (2009)
28. Liu, D.-Z., Wang, Z.-D.: Limit distribution of eigenvalues for random Hankel and Toeplitz band matrices, to appear in J Theor Probab. http://arxiv.org/abs/0904.2958

1060

J Theor Probab (2013) 26:1020–1060

29. Massey, A., Miller, S.J., Sinsheimer, J.: Distribution of eigenvalues of real symmetric palindromic
Toeplitz matrices and circulant matrices. J. Theor. Probab. 20(3), 637–662 (2007)
30. Meckes, M.: The spectra of random abelian G-circulant matrices, preprint. http://arxiv.org/PS_cache/arxiv/pdf/1109/1109.5675v1.pdf
31. Miller, S.J., Novikoff, T., Sabelli, A.: The distribution of the second largest eigenvalue in families ofrandom regular graphs. Exp. Math. 17(2), 231–244 (2008)
32. McKay, B.: The expected eigenvalue distribution of a large regular graph. Linear Algebra Appl. 40,
203–216 (1981)
33. Montgomery, H.: The pair correlation of zeros of the zeta function. In: Analytic Number Theory.
Proceedings of Symposia in Pure Mathematics, vol. 24, pp. 181–193. AMS, Providence (1973)
34. Stein, E., Shakarchi, R.: Fourier Analysis: An Introduction. Princeton University Press, Princeton(2003)
35. Stein, E., Shakarchi, R.: Complex Analysis. Princeton University Press, Princeton (2003)
36. Takacs, L.: A moment convergence theorem. Am. Math. Mon. 98(8), 742–746 (1991)
37. Tao, T., Vu, V.: From the Littlewood–Offord problem to the circular law: Universality of the spectral
distribution of random matrices. Bull. Am. Math. Soc. 46, 377–396 (2009)
38. Tao, T., Vu, V.: Random matrices: Universality of local eigenvalue statistics up to the edge, preprint.
http://arxiv.org/PS_cache/arxiv/pdf/0908/0908.1982v1.pdf
39. Wigner, E.: On the statistical distribution of the widths and spacings of nuclear resonance levels. Proc.
Camb. Philol. Soc. 47, 790–798 (1951)
40. Wigner, E.: Characteristic vectors of bordered matrices with infinite dimensions. Ann. Math. 2(62),548–564 (1955)
41. Wigner, E.: Statistical properties of real symmetric matrices. In: Canadian Mathematical Congress
Proceedings, pp. 174–184. University of Toronto Press, Toronto (1957)
42. Wigner, E.: Characteristic vectors of bordered matrices with infinite dimensions. II. Ann. Math. Ser.
2 65, 203–207 (1957)
43. Wigner, E.: On the distribution of the roots of certain symmetric matrices. Ann. Math. Ser. 2 67,
325–327 (1958)
44. Wishart, J.: The generalized product moment distribution in samples from a normal multivariate population. Biometrika A 20, 32–52 (1928)
45. Xiong, W.: The limiting spectral measure for the ensemble of generalized real symmetric period mcirculant matrices, senior thesis (advisor S.J. Miller), Williams College (2011)
46. Zvonkin, A.: Matrix integrals and map enumeration: An accessible introduction. Math. Comput.
Model. 26(8–10), 281–304 (1997)