betaFeedback

WorksMathematics

Spectral distribution for biased orientations of random graphs

Abstract

We study the Hermitian adjacency matrix of the second kind for biased orientations of Erdos-Renyi random graphs. In the model D(n,p,p′)D(n,p,p'), an edge is present with probability pp and, conditional on its presence, is directed from its smaller to its larger endpoint with probability p′p'. Both parameters may depend on nn, and biased tournaments are the special case D(n,1,p′)D(n,1,p'). We prove a global semicircle law whenever n(p(1−p)+3p2p′(1−p′))→∞n(p(1-p)+3p^2p'(1-p')) \to \infty, for both the centered and the uncentered matrix, and also for the expected empirical spectral measure. Our second theorem gives the exact spectrum of the mean matrix and the limits of the extreme eigenvalues on the scale npnp, under a sufficient density assumption. The main difference from the unbiased random orientations (where p′=1/2p'=1/2) is emergence of multiple large eigenvalues. The proofs include the closed-walk counting, control of the moment variances, an explicit diagonalization of the deterministic bias, and the passage from centered to uncentered spectral measures.

Introduction

Let G(n,p)G(n,p) be the Erdős–Rényi random graph on the ordered vertex set [n]={1,…,n}[n]=\{1,\ldots,n\}. We obtain a random oriented graph by independently directing every present edge from its smaller to its larger endpoint with probability p′p', and in the opposite direction with probability 1−p′1-p'. We denote the resulting model by D(n,p,p′)D(n,p,p'). The parameters have distinct roles: pp controls edge presence, whereas p′p' controls orientation bias. Throughout, both p=p(n)p=p(n) and p′=p′(n)p'=p'(n) may vary with nn.

Biased tournament models have some history. Probably the earliest paper is by Frank [6]. Łuczak, Ruciński, and Gruszka [16] studied the evolution of biased tournaments, and, more recently, Gishboliner, Krivelevich, and Kronenberg [8] considered the chromatic number of biased tournaments. However, their eigenvalues were not studied before. The same holds for biased orientations of random graphs.

We use the sixth-root Hermitian adjacency matrix introduced by the author [17], also called the Hermitian adjacency matrix of the second kind. There are several reasons why this specific choice is the most natural one, see [17] and [2]. An arc has weight ω=(1+i3)/2\omega=(1+i\sqrt{3})/2 in its direction and weight ω‾\overline{\omega} in the reverse direction. The earlier Hermitian adjacency matrix, introduced independently by Guo and Mohar [10] and Liu and Li [15], uses weights ii and −i-i. Further properties of the second-kind matrix are studied by Li and Yu [14]. The main distinction between the two conventions is that the real part Re⁡(ω)=1/2\operatorname{Re}(\omega) = 1/2 creates a nonzero mean even when p′=1/2p' = 1/2.

Our results use Wigner’s semicircle law [20] and the standard spectral comparison methods described for example in Bai and Silverstein [3] and in other textbooks about eigenvalues of random matrices, a popular example being a recent manuscript of Tao [18]. Related results for random oriented graphs and random mixed graphs include the work of Chen, Li and Lian [5], Hu, Li, Liu and Zhang [13], and Guan et al. [9]. Separation of the leading eigenvalue for first-kind Hermitian matrices of random mixed graphs is studied by Hu, Broersma, Hou and Zhang [11]. The same authors give bounds on skew spectral radii of general random oriented graphs in [12]. These results provide context, but the mean and variance computation for the present matrix and model bear notable differences.

We give two main theorems for the family D(n,p,p′)\mathcal{D}(n,p,p'). The first describes the bulk spectrum and its expected empirical measure. The second describes the deterministic mean spectrum and the extreme eigenvalues on the scale npnp. Uniformly oriented random graphs and biased tournaments are particular special cases, obtained by setting p′=1/2p' = 1/2 and p=1p = 1, respectively.

The bulk theorem is a model-specific application of the classical moment method. Its main additional ingredient is the treatment of the mean matrix. Under a nonzero bias, the imaginary part of the mean has large rank and norm of order npnp. Nevertheless, after bulk normalization it can be decomposed into a matrix of rank o(n)o(n) and a matrix of norm o(1)o(1). We derive this decomposition from an explicit cotangent formula for its eigenvalues. Details are included to explain both the parameter assumptions and the different roles of bulk and extreme eigenvalues.

Comments about the use of AI

I have known the results collected in this paper since the original work in [10] and [17]. I have popularized it in several talks since I like the 12\frac{1}{2} shift used to deal with the skew-symmetric part. This shift gives the eigenvalues at the complex line Im⁡(z)=−12\operatorname{Im}(z) = -\frac{1}{2}, which is reminiscent to the location of zeros of the Riemann zeta function. I also like the appearance of multiple large eigenvalues in the biased orientation models.

I was saving the final technicalities and subsequent paper submission for a graduate student. However, since the recent AI work in mathematics, I have realized that this is no longer a good Master Thesis problem and have decided to write it myself. I have used help from ChatGPT (the current model GPT-6.1 Sol) which has enhanced my original draft manuscript to my satisfaction. The model did not go much beyond my current understanding, but it was an extremely useful tool that saved me a lot of technical work and also provided some more generality. For example, § 6.3–§ 6.6 and several comments scattered around have been the work of ChatGPT.

My original results started with the unbiased case, but since that case has been more or less covered by Hu et al. [13, 11] and by Guan et al. [9], I decided to stick with biased orientations, the case of which provides a novel outcome, where several large eigenvalues appear in addition to the bulk of eigenvalues following the semicircle distribution.

The model, normalization, and spectral measures

The random graph and its Hermitian matrix

All graphs considered here have no loops, and there is at most one arc between any unordered pair of vertices. More explicitly, for each u<vu < v, independently of all other unordered pairs, the model D(n,p,p′)\mathcal{D}(n,p,p') makes the choices

Outcome on uvuvProbability
No edge1−p1-p
The arc u→vu \to vpp′pp'
The arc v→uv \to up(1−p′)p(1-p')

caption:

:::

This is exactly the two-stage construction of first sampling a random undirected graph G(n,p)G(n,p) and then orienting its present edges with bias p′p'. In particular,

T(n,p′):=D(n,1,p′)(1)\mathcal{T}(n,p') := \mathcal{D}(n,1,p') \tag*{(1)}

is the biased tournament on the ordered vertex set [n][n], with forward orientation probability p′p'. At p′=0p'=0 or 11 every present edge is directed consistently with one of the two vertex orders. Such an orientation is deterministic conditional on the underlying graph; the graph remains random when 0<p<10 < p < 1.

For an oriented graph DD, its Hermitian adjacency matrix is H=H(D)∈CV(D)×V(D)H = H(D) \in\mathbb{C}^{V(D)\times V(D)}, with

Huv={ω,u→v is an arc,ω‾,v→u is an arc,0,u=v or u,v are nonadjacent,(2)H_{uv} = \begin{cases} \omega, & u \to v\text{ is an arc},\\ \overline{\omega}, & v \to u\text{ is an arc},\\ 0, & u=v\text{ or }u,v\text{ are nonadjacent}, \end{cases} \tag*{(2)}

where

ω=1+i32.\omega= \frac{1+i\sqrt{3}}{2}.

Thus Hvu‾=Huv\overline{H_{vu}}=H_{uv}, so H=H∗H=H^* is Hermitian and has nn real eigenvalues. We count multiplicities and order them as

λ1(H)≥λ2(H)≥⋯≥λn(H).\lambda_1(H) \ge\lambda_2(H) \ge\cdots\ge\lambda_n(H).

If A=A(D)A=A(D) is the adjacency matrix of the underlying undirected graph and S=S(D)S=S(D) is the real skew-adjacency matrix, whose uvuv-entry is 11 for u→vu\to v, −1-1 for v→uv\to u, and 00 otherwise, then

H(D)=12A(D)+i32S(D).(3)H(D)=\frac{1}{2}A(D)+i\frac{\sqrt{3}}{2}S(D). \tag*{(3)}

The two summands use the same edge choices and are generally dependent. Our proofs work with the entries of HH directly. Reversing every arc replaces HH by H‾\overline{H}, which has the same real eigenvalues. Consequently the spectral distributions for parameters p′p' and 1−p′1-p' are identical.

As mentioned before, several results work for more general gain graphs, where each edge u→vu\to v has an arbitrary complex weight ζ\zeta with ∣ζ∣=1|\zeta|=1 and the symmetric matrix entry has ζ‾\overline{\zeta}. The gain ζ\zeta may even be different for different pairs u,vu,v. In particular, Theorem 1 extends to gain graphs.

The mean and variance of matrix entries

For the remainder of the article, write

β=2p′−1,a=32β,α=12+ia,τ=∣α∣2=14+a2=1−3p′(1−p′).(4)\beta=2p'-1,\qquad a=\frac{\sqrt{3}}{2}\beta,\qquad\alpha=\frac{1}{2}+ia,\qquad\tau=|\alpha|^2=\frac{1}{4}+a^2=1-3p'(1-p'). \tag*{(4)}

We will first determine the mean and variance of the entries of HH, viewed as a random matrix corresponding to our model D(n,p,p′)\mathcal{D}(n,p,p'). Since 14≤τ≤1\frac{1}{4}\le\tau\le1, the following expressions are nonnegative.

For u<vu<v, direct calculation gives

EHuv=pp′ω+p(1−p′)ω‾=pα,(5)\mathbb{E}H_{uv}=pp^{\prime}\omega+p(1-p^{\prime})\overline{\omega}=p\alpha, \tag*{(5)}
E∣Huv∣2=p,(6)\mathbb{E}|H_{uv}|^2=p, \tag*{(6)}
ν:=Var⁡Huv=E∣Huv−pα∣2=p−p2∣α∣2=p(1−p)+3p2p′(1−p′).(7)\nu:=\operatorname{Var}H_{uv}=\mathbb{E}|H_{uv}-p\alpha|^2=p-p^2|\alpha|^2=p(1-p)+3p^2p^{\prime}(1-p^{\prime}). \tag*{(7)}

For a complex random variable, variance here means Var⁡Z=E∣Z−EZ∣2\operatorname{Var} Z=\mathbb{E}|Z-\mathbb{E}Z|^2, not E(Z−EZ)2\mathbb{E}(Z-\mathbb{E}Z)^2. Notice that 0≤ν≤p0\leq\nu\leq p. It vanishes precisely when p=0p=0, or when p=1p=1 and p′∈{0,1}p^{\prime}\in\{0,1\}.

Let JnJ_n be the all-ones matrix, InI_n the identity, and SnS_n the deterministic skew-symmetric matrix with entries 11 above the diagonal, −1-1 below it, and 00 on the diagonal. Then the mean matrix MnM_n and the corresponding centered matrix WnW_n are defined as

Mn:=EHn=p2(Jn−In)+ipαSn,Wn:=Hn−Mn.(8)M_n:=\mathbb{E}H_n=\frac{p}{2}(J_n-I_n)+ip\alpha S_n,\qquad W_n:=H_n-M_n. \tag*{(8)}

The entries of WnW_n above the diagonal are independent, centered, and have common variance ν\nu. They satisfy the uniform bound

∣(Wn)uv∣≤1+p∣α∣≤2.(9)|(W_n)_{uv}|\leq1+p|\alpha|\leq2. \tag*{(9)}

We also define the normalization factor

sn:=nν.(10)s_n:=\sqrt{n\nu}. \tag*{(10)}

Let us observe that we allow p=pnp=p_n and p′=pn′p^{\prime}=p_n^{\prime} to depend on nn. Therefore, also the constants in (4) and (7) depend on nn in general. When necessary we write νn,αn,pn,pn′\nu_n,\alpha_n,p_n,p_n^{\prime} to emphasize dependence on nn. A normalization by sns_n is used only when νn>0\nu_n>0.

Empirical and expected spectral measures

For a Hermitian matrix BB of order nn, we define its spectral measure μB\mu_B and its cumulative distribution function FBF_B as

μB=1n∑j=1nδλj(B),FB(x)=μB((−∞,x]).(11)\mu_B=\frac{1}{n}\sum_{j=1}^{n}\delta_{\lambda_j(B)},\qquad F_B(x)=\mu_B((-\infty,x]). \tag*{(11)}

Here δt\delta_t is unit mass at tt. For a random matrix BB, its expected empirical spectral measure is the deterministic measure μ‾B\overline{\mu}_B that satisfies

μ‾B(U)=EμB(U)=1nE#{j:λj(B)∈U}(12)\overline{\mu}_B(U)=\mathbb{E}\mu_B(U)=\frac{1}{n}\mathbb{E}\#\{j:\lambda_j(B)\in U\} \tag*{(12)}

for every Borel set UU. It is generally different from μEB\mu_{\mathbb{E}B}, the spectral measure of the mean matrix. The standard semicircle distribution μsc\mu_{\mathrm{sc}} has density

ρsc(x)=12π4−x2 1[−2,2](x).(13)\rho_{\mathrm{sc}}(x)=\frac{1}{2\pi}\sqrt{4-x^2}\,1_{[-2,2]}(x). \tag*{(13)}

Its odd moments vanish and its 2m2m-th moment is Cm=(m+1)−1(2mm)C_m=(m+1)^{-1}\binom{2m}{m}.

For convergence of (random) probability measures, we write μBn→w,Pμ\mu_{B_n}\xrightarrow{w,\mathbb{P}}\mu if, for every bounded continuous real function ff, ∫f dμBn→P∫f dμ\int f\,d\mu_{B_n}\xrightarrow{\mathbb{P}}\int f\,d\mu. That is, for every ε>0\varepsilon>0,

P(∣∫f dμn−∫f dμ∣>ε)⟶0.\mathbb{P}\left(\left|\int f\,d\mu_n-\int f\,d\mu\right|>\varepsilon\right)\longrightarrow0.

Thus each integral against a fixed test function converges in probability to its prescribed limit. The notation →w\xrightarrow{\mathrm{w}} denotes ordinary weak convergence of deterministic probability measures. We refer the reader to [4] for further details.

For a Hermitian matrix, ∥B∥op=max⁡j∣λj(B)∣\lVert B\rVert_{\mathrm{op}}=\max_j\lvert\lambda_j(B)\rvert is its operator norm (also called the spectral radius of BB). We write Zn=OP(rn)Z_n=O_{\mathbb{P}}(r_n) when Zn/rnZ_n/r_n is bounded in probability, and Zn=oP(rn)Z_n=o_{\mathbb{P}}(r_n) when Zn/rn→P0Z_n/r_n\xrightarrow{\mathbb{P}}0.

Our main theorems

We will prove two theorems. The first one establishes the weak convergence of spectral measures.

Theorem 1 (The semicircle bulk and its expectation). Let DnD_n have distribution D(n,pn,pn′)\mathcal{D}(n,p_n,p'_n), and let Hn,Wn,νn,snH_n,W_n,\nu_n,s_n be as in (2.7)–(2.10). If

nνn=n[pn(1−pn)+3pn′2(1−pn′)]⟶∞(14)n\nu_n=n\left[p_n(1-p_n)+3p_n'^2(1-p'_n)\right]\longrightarrow\infty \tag*{(14)}

then

μWn/sn→w,Pμsc,μHn/sn→w,Pμsc,μ‾Hn/sn→wμsc.(15)\mu_{W_n/s_n}\xrightarrow{\mathrm{w},\mathbb{P}}\mu_{\mathrm{sc}},\qquad \mu_{H_n/s_n}\xrightarrow{\mathrm{w},\mathbb{P}}\mu_{\mathrm{sc}},\qquad \overline{\mu}_{H_n/s_n}\xrightarrow{\mathrm{w}}\mu_{\mathrm{sc}}. \tag*{(15)}

In particular, for any fixed x<yx<y, we have

1n#{j:xsn<λj(Hn)≤ysn}→P∫xyρsc(t) dt(16)\frac{1}{n}\#\{j:x s_n<\lambda_j(H_n)\leq y s_n\}\xrightarrow{\mathbb{P}}\int_x^y\rho_{\mathrm{sc}}(t)\,\mathrm{d}t \tag*{(16)}

and

1nE#{j:xsn<λj(Hn)≤ysn}⟶∫xyρsc(t) dt.(17)\frac{1}{n}\mathbb{E}\#\{j:x s_n<\lambda_j(H_n)\leq y s_n\}\longrightarrow\int_x^y\rho_{\mathrm{sc}}(t)\,\mathrm{d}t. \tag*{(17)}

This is a global spectral statement. A proportion tending to 1 of the eigenvalues lies in any fixed enlargement of [−2sn,2sn][-2s_n,2s_n], but o(n)o(n) eigenvalues can be distributed differently and some individual eigenvalues can be much larger. The next theorem describes such eigenvalues on the scale npnnp_n.

Theorem 2 (The mean spectrum and the extreme eigenvalues). Let DnD_n have distribution D(n,pn,pn′)\mathcal{D}(n,p_n,p'_n), and put cn=∣an∣=(3/2)∣2pn′−1∣c_n=\lvert a_n\rvert=(\sqrt{3}/2)\lvert2p'_n-1\rvert.

  1. If cn>0c_n>0, set θn=arctan⁡(2cn)\theta_n=\arctan(2c_n). The eigenvalues of Mn=EHnM_n=\mathbb{E}H_n, in decreasing order, are exactly

λj(Mn)=pn[cncot⁡(θn+(j−1)πn)−12],1≤j≤n.(18)\lambda_j(M_n)=p_n\left[c_n\cot\left(\frac{\theta_n+(j-1)\pi}{n}\right)-\frac{1}{2}\right],\qquad1\leq j\leq n. \tag*{(18)}

If cn=0c_n=0, they are (n−1)pn/2(n-1)p_n/2 once and −pn/2-p_n/2 with multiplicity n−1n-1. If pn=0p_n=0, all eigenvalues are zero.

  1. Let Δn=nνnlog⁡n+log⁡n\Delta_n=\sqrt{n\nu_n\log n}+\log n. For all parameter sequences, we have

max⁡1≤j≤n∣λj(Hn)−λj(Mn)∣=OP(Δn).(19)\max_{1\leq j\leq n}\lvert\lambda_j(H_n)-\lambda_j(M_n)\rvert=O_{\mathbb{P}}(\Delta_n). \tag*{(19)}
  1. Suppose npn/log⁡n→∞np_n/\log n\to\infty and pn′→r∈[0,1]p'_n\to r\in[0,1]. If r≠12r\neq\frac{1}{2}, define c∗=(3/2)∣2r−1∣c_*=(\sqrt{3}/2)\lvert2r-1\rvert and θ∗=arctan⁡(2c∗)\theta_*=\arctan(2c_*). For every fixed integer k≥1k\geq1,

λk(Hn)npn→Pc∗θ∗+(k−1)π,(20)\frac{\lambda_k(H_n)}{np_n}\xrightarrow{\mathbb{P}}\frac{c_*}{\theta_*+(k-1)\pi}, \tag*{(20)}
λn+1−k(Hn)npn→P−c∗kπ−θ∗.(21)\frac{\lambda_{n+1-k}(H_n)}{np_n}\xrightarrow{\mathbb{P}}-\frac{c_*}{k\pi-\theta_*}. \tag*{(21)}

If r=12r=\frac{1}{2}, then

λ1(Hn)npn→P12andmax⁡2≤j≤n∣λj(Hn)∣npn→P0.(22)\frac{\lambda_1(H_n)}{np_n}\xrightarrow{\mathbb{P}}\frac{1}{2} \qquad\text{and}\qquad \frac{\max_{2\le j\le n}|\lambda_j(H_n)|}{np_n}\xrightarrow{\mathbb{P}}0. \tag*{(22)}

It is worth noting that Theorem 2 does not require (14), although its part (iii) uses a related assumption that npn/log⁡n→∞np_n/\log n\to\infty. The condition npn/log⁡n→∞np_n/\log n\to\infty is sufficient (but not necessary) for the stated extreme-eigenvalue limits; no optimal threshold is asserted. The scale npnnp_n permits pn→0p_n\to0. If instead pn→p∗>0p_n\to p_*>0, the limits on the scale nn are obtained by multiplying the right-hand sides of (20)–(22) by p∗p_*. For a fixed nonzero limiting bias, each fixed index from either end has a nonzero limit on the scale npnnp_n. This does not mean that a positive proportion of the eigenvalues has that scale.

Ingredients of the proofs

Exact diagonalization of the deterministic bias

Lemma 1. For b≥0b\ge0 and c>0c>0, let Kn(b,c)=b(Jn−In)+icSnK_n(b,c)=b(J_n-I_n)+icS_n and θ=arg⁡(b+ic)∈(0,π/2]\theta=\arg(b+ic)\in(0,\pi/2]. Then

λj(Kn(b,c))=ccot⁡(θ+(j−1)πn)−b,1≤j≤n.(23)\lambda_j(K_n(b,c))=c\cot\left(\frac{\theta+(j-1)\pi}{n}\right)-b,\qquad1\le j\le n. \tag*{(23)}

In particular,

λj(iSn)=cot⁡((2j−1)π2n),∥iSn∥op=cot⁡π2n.(24)\lambda_j(iS_n)=\cot\left(\frac{(2j-1)\pi}{2n}\right),\qquad\lVert iS_n\rVert_{\mathrm{op}}=\cot\frac{\pi}{2n}. \tag*{(24)}

Replacing cc by −c-c leaves the spectrum unchanged.

Proof. Add bInbI_n and write A=bJn+icSnA=bJ_n+icS_n. Any eigenvalue γ\gamma of AA is real, and its eigenvector z=(z1,…,zn)z=(z_1,\ldots,z_n) satisfies

γzu=b∑v=1nzv+ic(∑v>uzv−∑v<uzv).(25)\gamma z_u=b\sum_{v=1}^{n}z_v+ic\left(\sum_{v>u}z_v-\sum_{v<u}z_v\right). \tag*{(25)}

In the difference between row u+1u+1 and row uu, the first sum cancels and the second expression changes by −ic(zu+1+zu-ic(z_{u+1}+z_u. Thus

(γ+ic)zu+1=(γ−ic)zu.(\gamma+ic)z_{u+1}=(\gamma-ic)z_u.

Since c≠0c\ne0, γ+ic\gamma+ic is nonzero. If z1=0z_1=0, this recurrence would force every coordinate to vanish, which is impossible since eigenvector is non-zero. We may therefore normalize z1=1z_1=1 and write

zu=ru−1,r=γ−icγ+ic.(26)z_u=r^{u-1},\qquad r=\frac{\gamma-ic}{\gamma+ic}. \tag*{(26)}

Here ∣r∣=1|r|=1 and r≠1r\ne1. The first row of (25) becomes

γ+ic=(b+ic)∑u=1nru−1=(b+ic)1−rn1−r.\gamma+ic=(b+ic)\sum_{u=1}^{n}r^{u-1}=(b+ic)\frac{1-r^n}{1-r}.

Since 1−r=2ic/(γ+ic)1-r=2ic/(\gamma+ic), cancellation gives

rn=b−icb+ic=e−2iθ.(27)r^n=\frac{b-ic}{b+ic}=e^{-2i\theta}. \tag*{(27)}

The nn roots are rj=e−2itjr_j=e^{-2it_j}, where tj=(θ+(j−1)π)/n∈(0,π)t_j=(\theta+(j-1)\pi)/n\in(0,\pi). Solving (26) for γ\gamma gives

γ=ic1+rj1−rj=ccot⁡tj.\gamma=ic\frac{1+r_j}{1-r_j}=c\cot t_j.

Conversely, these values and their geometric-coordinate vectors determined by (26) satisfy the first row and every consecutive row difference; hence they satisfy all rows. The nn values are distinct and decreasing because cotangent is strictly decreasing on (0,π)(0,\pi). They give the full spectrum of AA. Subtracting bb proves (23).

Taking b=0b=0 and c=1c=1 gives θ=π/2\theta=\pi/2 and yields (24). Finally, Kn(b,−c)=Kn(b,c)‾K_n(b,-c)=\overline{K_n(b,c)}. Conjugating an eigenvector preserves its real eigenvalue. This proves the last assertion.

The centered semicircle law by closed walks

The next lemma uses standard trace formula to express spectral moments ∑j=1nλjk=Tr⁡(Xk)\sum_{j=1}^{n}\lambda_j^k=\operatorname{Tr}(X^k) via counting of closed walks in the complete graph with edges weighted by the matrix entries. The convenient assumption is that the random matrix XX has centered entries XuvX_{uv}.

The lemma allows the entry distribution and its variance to depend on nn. The entries need not have a rotationally symmetric complex distribution, and no condition on EXuv2\mathbb{E}X_{uv}^{2} is needed. In particular, they can arise by “centering” any gain values in HH, not necessarily restricted to the sixth roots of unity.

Lemma 2. Let Xn=(Xuv)X_n=(X_{uv}) be Hermitian with zero diagonal and independent entries above the diagonal. Suppose that for every u<vu<v, we have

EXuv=0,E∣Xuv∣2=νn>0,and∣Xuv∣≤L,\mathbb{E}X_{uv}=0,\qquad\mathbb{E}|X_{uv}|^2=\nu_n>0,\qquad\text{and}\qquad|X_{uv}|\le L,

where LL is a fixed constant. Let Bn=Xn/nνnB_n=X_n/\sqrt{n\nu_n}. If nνn→∞n\nu_n\to\infty, then

μBn→w,Pμscandμ‾Bn→wμsc.\mu_{B_n}\xrightarrow{\mathrm{w},\mathbb{P}}\mu_{\mathrm{sc}} \qquad\text{and}\qquad \overline{\mu}_{B_n}\xrightarrow{\mathrm{w}}\mu_{\mathrm{sc}}.

Proof. We give the moment argument in five steps.

Step 1: Expand the trace as a sum of walks. For a fixed positive integer kk,

E1nTr⁡Bnk=1n(nνn)k/2∑u1,…,uk=1nE[Xu1u2⋯Xuku1].(28)\mathbb{E}\frac{1}{n}\operatorname{Tr}B_n^k = \frac{1}{n(n\nu_n)^{k/2}} \sum_{u_1,\ldots,u_k=1}^{n} \mathbb{E}\left[X_{u_1u_2}\cdots X_{u_ku_1}\right]. \tag*{(28)}

Each term corresponds to a closed walk u1u2⋯uku1u_1u_2\cdots u_ku_1. Since the diagonal of BnB_n is zero, we may assume that any consecutive vertices uj,uj+1u_j,u_{j+1} are distinct. If an unordered edge uvuv occurs just once, its associated centered entry is independent of all other factors, so this term also vanishes in the expectation.

For any remaining walk, let ee be its number of distinct unordered edges and tt its number of distinct vertices. Every edge is used at least twice, hence e≤k/2e\le k/2. The graph traced by the walk is connected, so t≤e+1t\le e+1.

Step 2: Bound on nonleading walk patterns. A walk pattern records the walk after relabeling vertices in their order of first appearance. In other words, the pattern is obtained from u1u2⋯uku_1u_2\cdots u_k by omitting the repeated appearances of vertices and keeping only the first one. There are only finitely many such patterns for fixed kk, and a pattern with tt vertices has at most ntn^t assignments of actual vertex labels. If an edge occurs m≥2m \ge2 times, in either direction, its factor in the expectation has absolute value at most

E∣Xuv∣m≤Lm−2E∣Xuv∣2=Lm−2νn.\mathbb{E}|X_{uv}|^m \le L^{m-2}\mathbb{E}|X_{uv}|^2 = L^{m-2}\nu_n.

Independence across unordered edges now bounds the expectation for the walk by Lk−2eνneL^{k-2e}\nu_n^e. Thus a fixed pattern contributes at most a constant depending on kk, LL multiplied by

ntνnen(nνn)k/2=nt−e−1(nνn)e−k/2.(29)\frac{n^t\nu_n^e}{n(n\nu_n)^{k/2}}=n^{t-e-1}(n\nu_n)^{e-k/2}. \tag*{(29)}

If e<k/2e < k/2, the second factor tends to zero and the first is at most one. If e=k/2e = k/2 but t<e+1t < e+1, the first factor is at most n−1n^{-1} and hence (29) also tends to 0. Therefore only the case k=2mk = 2m, e=me = m, t=m+1t = m + 1 can have a nonzero limit. The underlying graph of any such pattern is a tree, and the walk traverses each of its edges exactly twice. Such patterns are called tree patterns.

Step 3: Count the leading tree walks. For a tree pattern, each of its edges is traversed exactly twice. Deleting any tree edge separates the support into two parts. A closed walk crosses this cut equally often in both directions, so the two traversals must be one in each direction. Each edge consequently contributes E(XuvXvu)=E∣Xuv∣2=νn\mathbb{E}(X_{uv}X_{vu})=\mathbb{E}|X_{uv}|^2=\nu_n. This is why the complex phases do not affect the limiting law. Note also that the value in (29) is equal to 1 for every tree walk. Therefore, it suffices to count the number of tree patterns and tree walks.

For clarity, the number of tree walk patterns is the Catalan number CmC_m. Mark the first traversal of each edge as an up-step and the return traversal as a down-step. On a tree with each edge used twice, a return is to the parent of the current vertex, and an up-step discovers a new vertex. The result is a path with mm up-steps and mm down-steps, never below its starting height. Conversely, such a path reconstructs a unique tree walk by introducing the next unused vertex at every up-step and returning to the parent at every down-step. The reflection argument counts these paths as

(2mm)−(2mm+1)=1m+1(2mm)=Cm.\binom{2m}{m}-\binom{2m}{m+1}=\frac{1}{m+1}\binom{2m}{m}=C_m.

Each pattern has n(n−1)⋯(n−m)n(n-1)\cdots(n-m) distinct label assignments. Its normalization in (28) is nm+1νnmn^{m+1}\nu_n^m, and its entry expectation is νnm\nu_n^m. We obtain

1nETr⁡Bnk⟶{0,k odd,Cm,k=2m.(30)\frac{1}{n}\mathbb{E}\operatorname{Tr} B_n^k \longrightarrow \begin{cases} 0, & k\text{ odd},\\ C_m, & k=2m. \end{cases} \tag*{(30)}

Step 4: The spectral moments concentrate. We have determined the limit of expectation of n−1Tr⁡Bnkn^{-1}\operatorname{Tr} B_n^k (n→∞n \to\infty) for every fixed kk. Now, we need to analyse its variance. Write PwP_w for the product of entries associated with a walk ww. The variance of n−1Tr⁡Bnkn^{-1}\operatorname{Tr} B_n^k is a normalized sum of E(PwPw′)−EPwEPw′\mathbb{E}(P_wP_{w'})-\mathbb{E}P_w\mathbb{E}P_{w'} over pairs w,w′w,w' of closed walks of length kk. If their unordered edge-sets are disjoint, the products are independent and the covariance is zero, even if the walks share a vertex. Otherwise their union is connected. If some union edge occurs just once among the 2k2k factors, centering kills both terms of the covariance. We therefore only need unions with e≤ke \le k edges, each used at least twice, and t≤e+1t \le e+1 vertices.

The joint expectation is bounded by L2k−2eνneL^{2k-2e}\nu_n^e (see Step 2). The product of the separate expectations satisfies the same bound whenever it is nonzero: every shared edge supplies an extra factor νn\nu_n, which can be bounded by L2L^2. For each union pattern, the normalization is n2(nνn)kn^2(n\nu_n)^k and there are at most ntn^t labelings. Its absolute contribution is at most a constant times

nt−e−2(nνn)e−k≤n−1,n^{t-e-2}(n\nu_n)^{e-k}\le n^{-1},

where we used that nνn≥1n\nu_n \ge1 for all sufficiently large nn. There are finitely many pairs of patterns for fixed kk, so

Var⁡(1nTr⁡Bnk)=Ok,L(n−1).(31)\operatorname{Var}\left(\frac{1}{n}\operatorname{Tr} B_n^k\right)=O_{k,L}(n^{-1}). \tag*{(31)}

Chebyshev’s inequality and (30) show that each moment converges in probability to its semicircle value.

Step 5: Pass from moments to measures. We give the details because weak convergence does not, by itself, imply convergence of moments of unbounded functions. Write

mk(Bn)=∫xk dμBn(x)=1nTr⁡Bnk,mk=∫xk dμsc(x).m_k(B_n)=\int x^k\,d\mu_{B_n}(x)=\frac{1}{n}\operatorname{Tr} B_n^k,\qquad m_k=\int x^k\,d\mu_{\mathrm{sc}}(x).

The preceding steps show that mk(Bn)→Pmkm_k(B_n)\xrightarrow{\mathbb{P}}m_k for every integer k≥0k\ge0; for k=0k=0 both sides are identically one.

First take an arbitrary subsequence of matrix orders. By further extraction, choose orders njn_j within the subsequence such that

P{max⁡0≤k≤j∣mk(Bnj)−mk∣>1/j}≤2−j.(32)\mathbb{P}\left\{\max_{0\le k\le j}\left|m_k(B_{n_j})-m_k\right|>1/j\right\}\le2^{-j}. \tag*{(32)}

This is possible because each maximum involves only finitely many moments, all converging in probability. The probabilities in (32) are summable. The first Borel–Cantelli lemma therefore gives an event of probability 1 on which mk(Bnj)→mkm_k(B_{n_j})\to m_k simultaneously for every integer k≥0k\ge0. Independence between different matrix orders is not needed.

Fix an outcome in that event and set ηj=μBnj\eta_j=\mu_{B_{n_j}}. We now have a deterministic sequence of probability measures. Since ∫x2 dηj→m2=1\int x^2\,d\eta_j\to m_2=1, there is a finite constant CC such that, for every R>0R>0,

sup⁡jηj({∣x∣>R})≤1R2sup⁡j∫x2 dηj(x)≤CR2.(33)\sup_j\eta_j(\{|x|>R\})\le\frac{1}{R^2}\sup_j\int x^2\,d\eta_j(x)\le\frac{C}{R^2}. \tag*{(33)}

Thus the measures are tight. Every subsequence consequently has a further subsequence converging weakly to a probability measure η\eta on R\mathbb{R}.

We next show that any such limit η\eta has the required moments. To simplify the notation, we may assume that the originally chosen sequence converges weakly to η\eta. For a fixed kk, choose an even integer 2q>k2q>k. Convergence of the 2q2q-th moments gives K2q:=sup⁡j∫∣x∣2q dηj(x)<∞K_{2q}:=\sup_j\int|x|^{2q}\,d\eta_j(x)<\infty, and hence

sup⁡j∫∣x∣>R∣x∣k dηj(x)≤K2qR2q−k⟶0as R→∞.(34)\sup_j\int_{|x|>R}|x|^k\,d\eta_j(x)\le\frac{K_{2q}}{R^{2q-k}}\longrightarrow0\quad\text{as }R\to\infty. \tag*{(34)}

The weak limit η\eta also satisfies ∫∣x∣2q dη≤K2q\int|x|^{2q}\,d\eta\le K_{2q}. To see this, we consider the function fM(x):=min⁡{∣x∣2q,M}f_M(x):=\min\{|x|^{2q},M\} that is bounded and continuous, so the weak convergence ηj→wη\eta_j\xrightarrow{w}\eta implies

∫fM dη=lim⁡j→∞∫fM dηj≤K2q.\int f_M\,d\eta=\lim_{j\to\infty}\int f_M\,d\eta_j\le K_{2q}.

Letting M→∞M\to\infty and applying monotone convergence proves the stated bound.

Let χR\chi_R be a continuous function equal to one on [−R,R][-R,R], zero outside [−2R,2R][-2R,2R], and taking values in [0,1][0,1]. Weak convergence applies to the bounded continuous function xkχR(x)x^k\chi_R(x). The above tail estimates allow us first to pass to the weak limit for fixed RR and then let R→∞R\to\infty. It follows that ∫xk dη=mk\int x^k\,d\eta=m_k for every $k.

These moments identify η\eta uniquely. Indeed, for R>2R>2 and every positive integer qq,

η({∣x∣>R})≤m2qR2q=CqR2q≤(4R2)q.\eta(\{|x|>R\}) \le\frac{m_{2q}}{R^{2q}} = \frac{C_q}{R^{2q}} \le\left(\frac{4}{R^2}\right)^q.

Letting q→∞q \to\infty shows that η\eta is supported on [−2,2][-2,2]. It has the same integrals of all polynomials as the semicircle distribution μsc\mu_{\mathrm{sc}}. Uniform polynomial approximation of continuous functions on [−2,2][-2,2] then implies that η=μsc\eta=\mu_{\mathrm{sc}}. Thus, every weakly convergent subsequence of (ηj)(\eta_j) has the same limit, and tightness gives ηj⟶wμsc\eta_j \mathrel{\mathop{\longrightarrow}\limits^{\mathrm{w}}} \mu_{\mathrm{sc}}.

We have proved that every original subsequence admits a further subsequence along which weak convergence holds almost surely. This implies weak convergence in probability. More explicitly, if convergence failed for some bounded continuous test function, there would be a subsequence along which the probability of a fixed positive deviation stayed bounded away from zero. Its almost surely convergent further subsequence would contradict that property.

Finally, for bounded continuous ff, put Yn=∫f dμBnY_n=\int f\,\mathrm{d}\mu_{B_n} and y=∫f dμscy=\int f\,\mathrm{d}\mu_{\mathrm{sc}}. Then Yn⟶PyY_n \mathrel{\mathop{\longrightarrow}\limits^{\mathrm{P}}} y and ∣Yn∣,∣y∣≤∥f∥∞|Y_n|,|y|\le\|f\|_\infty. For any ε>0\varepsilon>0,

E∣Yn−y∣≤ε+2∥f∥∞P{∣Yn−y∣>ε}.\mathbb{E}|Y_n-y| \le\varepsilon+2\|f\|_\infty\mathbb{P}\{|Y_n-y|>\varepsilon\}.

Taking limits and then letting ε↓0\varepsilon\downarrow0 proves convergence of the expectations, which is the weak convergence μ‾Bn⟶wμsc\overline{\mu}_{B_n} \mathrel{\mathop{\longrightarrow}\limits^{\mathrm{w}}} \mu_{\mathrm{sc}}.

Spectral comparison and a norm estimate

For two Hermitian matrices A,BA,B of order nn, the rank inequality and Weyl’s inequality state that

sup⁡x∣FA(x)−FB(x)∣≤rank⁡(A−B)n,(35)\sup_x |F_A(x)-F_B(x)| \le\frac{\operatorname{rank}(A-B)}{n}, \tag*{(35)}
max⁡j∣λj(A)−λj(B)∣≤∥A−B∥op.(36)\max_j |\lambda_j(A)-\lambda_j(B)| \le\|A-B\|_{\mathrm{op}}. \tag*{(36)}

See Bai and Silverstein [3]. Suppose A=B+R+EA=B+R+E, with rank⁡R≤r\operatorname{rank}R\le r and ∥E∥op≤ε\|E\|_{\mathrm{op}}\le\varepsilon. The norm estimate moves each ordered eigenvalue by at most ε\varepsilon, and the rank estimate changes a distribution function by at most r/nr/n. Combining them gives

FB(x−ε)−rn≤FA(x)≤FB(x+ε)+rn.(37)F_B(x-\varepsilon)-\frac{r}{n}\le F_A(x)\le F_B(x+\varepsilon)+\frac{r}{n}. \tag*{(37)}

In particular, if r/n→0r/n\to0, ε→0\varepsilon\to0, and μB\mu_B converges to a measure with continuous distribution function, then μA\mu_A has the same weak limit. The assertion also holds for convergence in probability, by applying the displayed bounds at fixed points and using continuity of the limiting function.

We will use the concentration inequality in the general form used below. It is the two-sided consequence of Tropp [19], Theorem 6.1(ii) of that paper, pp. 421–422; the one-sided estimate is also stated as Theorem 1.4 of that paper.

Two-sided matrix Bernstein inequality. Let Y1,…,YNY_1,\ldots,Y_N be independent random Hermitian matrices of order dd, with EYk=0\mathbb{E}Y_k=0 and ∥Yk∥op≤L\|Y_k\|_{\mathrm{op}}\le L almost surely, where L>0L>0 is fixed. Put

Z=∑k=1NYk,σ2=∥∑k=1NE(Yk2)∥op.Z=\sum_{k=1}^{N}Y_k,\qquad\sigma^2=\left\|\sum_{k=1}^{N}\mathbb{E}(Y_k^2)\right\|_{\mathrm{op}}.

For every t>0t>0,

P{∥Z∥op≥t}≤2dexp⁡(−t22(σ2+Lt/3)).(38)\mathbb{P}\{\|Z\|_{\mathrm{op}}\ge t\}\le2d\exp\left(-\frac{t^2}{2(\sigma^2+Lt/3)}\right). \tag*{(38)}

If σ2=0\sigma^2=0, then Z=0Z=0 almost surely.

Proof. Tropp’s Theorem 6.1(ii) in [19] bounds P{λmax⁡(Z)≥t}\mathbb{P}\{\lambda_{\max}(Z) \ge t\} by the right-hand side of (38) with prefactor dd. Apply it to both (Yk)(Y_k) and (−Yk)(-Y_k). The norm bound gives λmax⁡(±Yk)≤L\lambda_{\max}(\pm Y_k) \le L, and the variance parameter is unchanged. Since ∥Z∥op=max⁡{λmax⁡(Z),λmax⁡(−Z)}\lVert Z\rVert_{\mathrm{op}} = \max\{\lambda_{\max}(Z),\lambda_{\max}(-Z)\}, a union bound supplies the factor 2.

If σ2=0\sigma^2=0, positivity of E(Yk2)\mathbb{E}(Y_k^2) implies Yk=0Y_k=0 almost surely for each kk.

To estimate the norm of WnW_n, write it as a sum of rank-1 matrices:

Wn=∑u<vY(uv),Y(uv)=(Wn)uveuev∗+(Wn)uv‾eveu∗.(39)W_n=\sum_{u<v}Y^{(uv)},\qquad Y^{(uv)}=(W_n)_{uv}e_ue_v^*+\overline{(W_n)_{uv}}e_ve_u^*. \tag*{(39)}

Here eue_u is the uu-th coordinate vector. The summands are independent centered Hermitian matrices. The only nonzero block of a summand has eigenvalues ±∣(Wn)uv∣\pm|(W_n)_{uv}|, so its norm is at most 2 by (9). Squaring that block gives

E[(Y(uv))2]=νn(eueu∗+evev∗),∑u<vE[(Y(uv))2]=(n−1)νnIn.\mathbb{E}\left[(Y^{(uv)})^2\right]=\nu_n(e_ue_u^*+e_ve_v^*),\qquad\sum_{u<v}\mathbb{E}\left[(Y^{(uv)})^2\right]=(n-1)\nu_n I_n.

Apply (38) with d=nd=n, L=2L=2, and σ2=(n−1)νn\sigma^2=(n-1)\nu_n. For t>0t>0 and n≥2n\ge2, this gives

P{∥Wn∥op≥t}≤2nexp⁡(−t22((n−1)νn+2t/3)).(40)\mathbb{P}\{\lVert W_n\rVert_{\mathrm{op}}\ge t\}\le2n\exp\left(-\frac{t^2}{2((n-1)\nu_n+2t/3)}\right). \tag*{(40)}

For example, take t=6(n−1)νnlog⁡n+4log⁡nt=\sqrt{6(n-1)\nu_n\log n}+4\log n. The exponent has absolute value at least 3log⁡n3\log n: in general, t=2σ2u+2Lu/3t=\sqrt{2\sigma^2u}+2Lu/3 satisfies t2≥2u(σ2+Lt/3)t^2\ge2u(\sigma^2+Lt/3), and here σ2=(n−1)νn\sigma^2=(n-1)\nu_n, L=2L=2, u=3log⁡nu=3\log n. Thus the probability is at most 2n−22n^{-2}. In particular,

∥Wn∥op=OP(nνnlog⁡n+log⁡n).(41)\lVert W_n\rVert_{\mathrm{op}}=O_{\mathbb{P}}\left(\sqrt{n\nu_n\log n}+\log n\right). \tag*{(41)}

When νn=0\nu_n=0, Wn=0W_n=0 almost surely, and the same conclusion holds. This estimate is intended for separation on the scale npnnp_n; it does not locate the sharp bulk edge.

Proofs of the main theorems

Proof of Theorem 1

Proof. By the assumption (14), we have that sn=nνn→∞s_n=\sqrt{n\nu_n}\to\infty. The entries of WnW_n satisfy the assumptions of Lemma 2 with L=2L=2. Consequently μWn/sn→w,Pμsc\mu_{W_n/s_n}\xrightarrow{\mathrm{w},\mathbb{P}}\mu_{\mathrm{sc}}.

To prove the convergence of spectral measures of Hn/snH_n/s_n, we will need to control the spectrum of the imaginary mean Qn=idnSnQ_n=i d_nS_n, where dn=pnand_n=p_na_n. We will use Lemma 1 with b=0b=0 and c=dnc=d_n. We may assume that p′>12p'>\frac{1}{2}, so we have c>0c>0. By (24), the multiset of eigenvalues of QnQ_n consists of values dncot⁡ϑjd_n\cot\vartheta_j, where ϑj=(j−12)π/n\vartheta_j=(j-\frac{1}{2})\pi/n. For t>0t>0 and dn≠0d_n\ne0, ∣dncot⁡ϑj∣>t|d_n\cot\vartheta_j|>t if and only if ϑj<ϕ\vartheta_j<\phi or ϑj>π−ϕ\vartheta_j>\pi-\phi, where ϕ=arctan⁡(∣dn∣/t)\phi=\arctan(|d_n|/t). The angles ϑj\vartheta_j are equally spaced by π/n\pi/n. An interval of length ϕ\phi contains at most nϕ/π+1n\phi/\pi+1 of them, so

#{j:∣λj(Qn)∣>t}≤2nπarctan⁡∣dn∣t+2≤2n∣dn∣πt+2.(42)\#\{j:|\lambda_j(Q_n)|>t\}\le\frac{2n}{\pi}\arctan\frac{|d_n|}{t}+2\le\frac{2n|d_n|}{\pi t}+2. \tag*{(42)}

If dn=0d_n=0, the left-hand side is zero and the bound is still valid.

Next, we split the mean into two “small” perturbations. Take the spectral decomposition of QnQ_n and retain in RnR_n only eigenvalues of absolute value greater than sn\sqrt{s_n} and the corresponding projections into their eigenspaces. Let En=Qn−RnE_n=Q_n-R_n contain the part of the spectral decomposition corresponding to the remaining eigenvalues. Then Qn=Rn+EnQ_n=R_n+E_n, and by (42),

rank⁡Rnn≤2∣dn∣πsn+2n→0,and∥En∥op⁡≤sn.\frac{\operatorname{rank} R_n}{n}\leq\frac{2|d_n|}{\pi\sqrt{s_n}}+\frac{2}{n}\to0,\qquad\text{and}\qquad\lVert E_n\rVert_{\operatorname{op}}\leq\sqrt{s_n}.

because ∣dn∣≤3/2|d_n|\leq\sqrt{3}/2 and sn→∞s_n\to\infty. Using the full mean in (8), we have the exact decomposition

Hnsn=Wnsn+Rn+(pn/2)Jnsn+En−(pn/2)Insn.(43)\frac{H_n}{s_n}=\frac{W_n}{s_n}+\frac{R_n+(p_n/2)J_n}{s_n}+\frac{E_n-(p_n/2)I_n}{s_n}. \tag*{(43)}

The middle term has rank at most rank⁡Rn+1=o(n)\operatorname{rank} R_n+1=o(n). The norm of the last term is at most sn−1/2+pn/(2sn)→0s_n^{-1/2}+p_n/(2s_n)\to0. The comparison (37) and continuity of the semicircle distribution function now give μHn/sn⟶w,Pμsc\mu_{H_n/s_n}\mathrel{\mathop{\longrightarrow}\limits^{\mathrm{w},\mathbb{P}}}\mu_{\mathrm{sc}}. This argument is needed because the norm of the entire mean divided by sns_n need not tend to zero.

Finally, we take expectations and interval counts. For every bounded continuous test function, convergence of its integral in probability implies convergence of the expectation by the boundedness argument at the end of Lemma 2. This proves the last assertion of (15). The endpoints of (x,y](x,y] have zero semicircle mass. Weak convergence therefore gives (16). Its left-hand side lies in [0,1][0,1], so its expectation also converges, proving (17). □

Proof of Theorem 2

Proof. (i) First, we identify the exact mean spectrum. For pn>0p_n>0, (8) gives

Mn=pn[12(Jn−In)+i anSn].M_n=p_n\left[\frac{1}{2}(J_n-I_n)+\mathrm{i}\,a_nS_n\right].

If an<0a_n<0, complex conjugation allows us to replace it by cn=∣an∣c_n=|a_n| without changing the eigenvalues. Apply Lemma 1 with b=1/2b=1/2 and c=cnc=c_n. Its angle is arg⁡(1/2+icn)=arctan⁡(2cn)\arg(1/2+\mathrm{i}c_n)=\arctan(2c_n), which proves (18). If an=0a_n=0, the all-ones vector is an eigenvector of Jn−InJ_n-I_n with eigenvalue n−1n-1, and its orthogonal complement has eigenvalue −1-1. This gives the stated spectrum. The case pn=0p_n=0 is immediate.

(ii) For part (ii), we pass from the mean to the random matrix. Weyl’s inequality applied to Hn=Mn+WnH_n=M_n+W_n, followed by (41), proves (19).

(iii) If npn/log⁡n→∞np_n/\log n\to\infty, then pn>0p_n>0 eventually, and νn≤pn\nu_n\leq p_n gives

Δnnpn≤log⁡nnpn+log⁡nnpn⟶0.(44)\frac{\Delta_n}{np_n}\leq\sqrt{\frac{\log n}{np_n}}+\frac{\log n}{np_n}\longrightarrow0. \tag*{(44)}

Consequently, the eigenvalues of Hn/(npn)H_n/(np_n) and Mn/(npn)M_n/(np_n) differ uniformly by oP(1)o_{\mathbb{P}}(1). It remains to compute deterministic limits.

We can now evaluate the extreme deterministic eigenvalues. Suppose first that pn′→r≠12p_n'\to r\neq\frac{1}{2}. Then cn→c∗>0c_n\to c_\ast>0, θn→θ∗>0\theta_n\to\theta_\ast>0, and for fixed kk,

λk(Mn)npn=cnncot⁡θn+(k−1)πn−12n⟶c∗θ∗+(k−1)π,\frac{\lambda_k(M_n)}{np_n}=\frac{c_n}{n}\cot\frac{\theta_n+(k-1)\pi}{n}-\frac{1}{2n}\longrightarrow\frac{c_\ast}{\theta_\ast+(k-1)\pi},

since xcot⁡x→1x\cot x\to1 as x→0x\to0. At the other end, the angle for j=n+1−kj=n+1-k is π−(kπ−θn)/n\pi-(k\pi-\theta_n)/n. The identity cot⁡(π−x)=−cot⁡x\cot(\pi-x)=-\cot x gives

λn+1−k(Mn)npn=−cnncot⁡kπ−θnn−12n⟶−c∗kπ−θ∗.\frac{\lambda_{n+1-k}(M_n)}{np_n}=-\frac{c_n}{n}\cot\frac{k\pi-\theta_n}{n}-\frac{1}{2n}\longrightarrow-\frac{c_\ast}{k\pi-\theta_\ast}.

Together with the above, this gives (20) and (21).

If instead pn′→1/2p_n' \to1/2, then an→0a_n \to0. The norm formula in (24) and cot⁡x≤1/x\cot x \le1/x for 0<x≤π/20 < x \le\pi/2 give

∥Mnnpn−Jn−In2n∥op=∣an∣ncot⁡π2n≤2∣an∣π⟶0.\left\| \frac{M_n}{np_n} - \frac{J_n-I_n}{2n} \right\|_{\mathrm{op}} = \frac{|a_n|}{n}\cot\frac{\pi}{2n} \le\frac{2|a_n|}{\pi} \longrightarrow0.

The comparison matrix has eigenvalues (n−1)/(2n)(n-1)/(2n) once and −1/(2n)-1/(2n) otherwise. Further application of Weyl’s inequality and the above comparison of eigenvalues of HnH_n and MnM_n proves (22).

Special cases and interpretation

How the familiar families fit into the model

The following table records the bulk variance and the sufficient bulk condition used in the proof of Theorem 1.

Special caseEntry variance ν\nuBulk condition
p′=1/2p' = 1/2p−p2/4p - p^2/4np→∞np \to\infty
p=1p = 13p′(1−p′)3p'(1-p')np′(1−p′)→∞np'(1-p') \to\infty
p′∈{0,1}p' \in\{0,1\}p(1−p)p(1-p)np(1−p)→∞np(1-p) \to\infty

Table 1.

Both parameters in this table may still vary with nn, subject to the indicated restriction. In the first row, the equivalence of the displayed condition with nν→∞n\nu\to\infty follows from 3p/4≤p−p2/4≤p3p/4 \le p-p^2/4 \le p.

For unbiased orientations, Theorem 2 gives the more explicit estimates

λ1(Hn)=(n−1)pn2+OP(Δn),(45)\lambda_1(H_n) = \frac{(n-1)p_n}{2} + O_{\mathrm{P}}(\Delta_n), \tag*{(45)}
max⁡j≥2∣λj(Hn)+pn/2∣=OP(Δn),(46)\max_{j\ge2}|\lambda_j(H_n) + p_n/2| = O_{\mathrm{P}}(\Delta_n), \tag*{(46)}

since the mean has only one eigenvalue outside its scalar part. Thus npn/log⁡n→∞np_n/\log n \to\infty ensures a single leading eigenvalue asymptotic to npn/2np_n/2, with every other eigenvalue oP(npn)o_{\mathrm{P}}(np_n).

For tournaments, set pn=1p_n=1 throughout. The model is T(n,pn′)=D(n,1,pn′)\mathcal{T}(n,p_n')=\mathcal{D}(n,1,p_n'), the scale in the bulk theorem is 3npn′(1−pn′)\sqrt{3np_n'(1-p_n')}, and the scale in the extreme theorem is nn. Its density assumption holds automatically. At p′=1/2p'=1/2, this agrees with the unbiased orientation of G(n,1)G(n,1), and both descriptions give variance 3/43/4 and a leading eigenvalue asymptotic to n/2n/2.

If p=1p=1 and p′∈{0,1}p'\in\{0,1\}, there is no randomness. The tournament is transitive, up to reversing all arcs. Now c=3/2c=\sqrt{3}/2 and θ=π/3\theta=\pi/3, so its entire spectrum is

λj(Hn)=32cot⁡(π/3+(j−1)πn)−12.(47)\lambda_j(H_n)=\frac{\sqrt{3}}{2}\cot\left(\frac{\pi/3+(j-1)\pi}{n}\right)-\frac{1}{2}. \tag*{(47)}

In particular, λ1(Hn)/n→33/(2π)\lambda_1(H_n)/n \to3\sqrt{3}/(2\pi) and λn(Hn)/n→−33/(4π)\lambda_n(H_n)/n \to-3\sqrt{3}/(4\pi). This recovers the computation in [1]. The extreme-eigenvalue formulas still apply, while the bulk theorem has no variance normalization in this deterministic case.

More generally, if pn≤1−δp_n\le1-\delta for a fixed δ>0\delta>0, then δpn≤νn≤pn\delta p_n\le\nu_n\le p_n, regardless of pn′p_n'. The bulk condition is then equivalent to npn→∞np_n\to\infty. If instead pn′∈[δ,1−δ]p_n'\in[\delta,1-\delta] with 0<δ≤1/20<\delta\le1/2, then νn≥3δ(1−δ)pn\nu_n\ge3\delta(1-\delta)p_n, and the same equivalence holds.

Expected counts and the scale of the bulk

Theorem 1 answers the question of the expected eigenvalue distribution through the expected empirical measure. For fixed x<yx<y, it gives

E#{j:xsn<λj(Hn)≤ysn}=n∫xyρsc(t) dt+o(n).(48)\mathbb{E}\#\{j:x s_n<\lambda_j(H_n)\le y s_n\}=n\int_x^y\rho_{\mathrm{sc}}(t)\,\mathrm{d}t+o(n). \tag*{(48)}

On the original eigenvalue scale, a convenient bulk density approximation is therefore

fnbulk(x)=12πsn2(4sn2−x2)+(49)f_n^{\mathrm{bulk}}(x)=\frac{1}{2\pi s_n^2}\sqrt{(4s_n^2-x^2)_+} \tag*{(49)}

where y+=max⁡{y,0}y_+=\max\{y,0\}. Its meaning is the global interval-count statement above. Since nn is finite, the actual expected spectral measure is discrete; no exact density or local eigenvalue-spacing law is asserted. The scalar shift −pn/2-p_n/2 in the mean is negligible relative to sn→∞s_n\to\infty.

Under the extreme theorem’s density assumption, we have npn→∞np_n\to\infty and sn≤npns_n\le\sqrt{np_n}. Whenever the bulk theorem also applies,

npnsn≥npn→∞.\frac{np_n}{s_n}\ge\sqrt{np_n}\to\infty.

Thus eigenvalues with a nonzero limit on the scale npnnp_n are well beyond the bulk scale. Their number need not be bounded, but their proportion tends to zero by the bulk law.

The spectrum of the mean is a different distribution

For fixed p>0p>0 and fixed p′≠12p'\ne\frac{1}{2}, let c=∣a∣>0c=|a|>0. The angles in (18) become uniformly distributed on (0,π)(0,\pi). It follows that the unscaled mean matrix has the weak limit

μMn⟶wCp,c,wheredCp,cdx(x)=pcπ((x+p/2)2+p2c2).(50)\mu_{M_n}\mathrel{\mathop{\longrightarrow}^{\mathrm{w}}}C_{p,c},\qquad\text{where}\qquad\frac{\mathrm{d}C_{p,c}}{\mathrm{d}x}(x)=\frac{pc}{\pi\left((x+p/2)^2+p^2c^2\right)}. \tag*{(50)}

Indeed, this is the distribution of pccot⁡U−p/2pc\cot U-p/2, with UU uniform on (0,π)(0,\pi). For any bounded continuous test function, restrict first to U∈[ε,π−ε]U\in[\varepsilon,\pi-\varepsilon], where ordinary Riemann sums apply; the two omitted end intervals have total probability 2ε/π2\varepsilon/\pi. Letting ε↓0\varepsilon\downarrow0 proves the weak convergence. Changing variables x=pccot⁡u−p/2x=pc\cot u-p/2 gives the displayed density. It is a Cauchy law with location −p/2-p/2 and scale pcpc.

For p′=12p'=\frac{1}{2}, the mean instead has limiting measure δ−p/2\delta_{-p/2}, since its exceptional leading eigenvalue has mass only 1/n1/n. In the deterministic transitive case p=1p=1, p′∈{0,1}p'\in\{0,1\}, (50) is also the limiting unscaled spectral measure of HnH_n itself. For fixed parameters with ν>0\nu>0, random fluctuations create the growing bulk scale nν\sqrt{n\nu}. Consequently the measure in (50) must be distinguished from μHn\mu_{H_n}.

Why uncentered second moments need not be semicircular

Weak convergence controls bounded continuous test functions, and the function x2x^2 is unbounded. Large eigenvalues can therefore contribute to second moments without changing the weak bulk limit. For every oriented graph with mm arcs,

Tr⁡H2=∑u,vHuvHvu=∑u,v∣Huv∣2=2m.\operatorname{Tr}H^2=\sum_{u,v}H_{uv}H_{vu}=\sum_{u,v}|H_{uv}|^2=2m.

In our model, Em=(n2)pn\mathbb{E}m=\binom{n}{2}p_n, so, when νn>0\nu_n>0,

E∫x2 dμHn/sn(x)=n−1n⋅pnνn.(51)\mathbb{E}\int x^2\,\mathrm{d}\mu_{H_n/s_n}(x)=\frac{n-1}{n}\cdot\frac{p_n}{\nu_n}. \tag*{(51)}

For fixed p>0p > 0 and fixed p′p' with ν>0\nu> 0, the limit is

pν=11−pτ=1+p2τν>1,(52)\frac{p}{\nu} = \frac{1}{1-p\tau} = 1 + \frac{p^2\tau}{\nu} > 1, \tag*{(52)}

whereas the semicircle second moment is 1. The extra term comes from the mean. To see this, observe that Tr⁡Mn2=n(n−1)pn′2τn\operatorname{Tr} M_n^2 = n(n-1)p_n^{\prime2}\tau_n, and

ETr⁡Hn2=ETr⁡Wn2+Tr⁡Mn2,\mathbb{E}\operatorname{Tr} H_n^2 = \mathbb{E}\operatorname{Tr} W_n^2 + \operatorname{Tr} M_n^2,

because the cross term has expectation zero. Dividing by n2νnn^2\nu_n explains both the semicircle contribution and the excess. This is why the moment proof is applied to WnW_n, followed by a separate comparison for HnH_n.

Further questions

The theorems describe global spectral measures and coarse extreme-eigenvalue limits. Natural next questions are the limiting laws when nνnn\nu_n stays bounded, sharp separation thresholds for small pnp_n, and fluctuations of the extreme eigenvalues. When pn′→1/2p'_n \to1/2, the smaller bias eigenvalues may interact with the bulk on intermediate scales. Comparing the norm of ipnanSnip_na_nS_n with sns_n suggests examining ∣pn′−1/2∣|p'_n-1/2| of order sn/(npn)s_n/(np_n); for fixed p>0p > 0 this is the usual order of magnitude n−1/2n^{-1/2}. The present results do not determine that transition or its local statistics.

The bulk and the large exceptional eigenvalues

We finish by stating together what the two main theorems say about the different parts of the spectrum. Here the global bulk means the eigenvalues described by the limiting empirical measure on the scale sn=nνns_n = \sqrt{n\nu_n}. For a fixed ε>0\varepsilon> 0, we use the window [−(2+ε)sn,(2+ε)sn][-(2+\varepsilon)s_n,(2+\varepsilon)s_n] to make the assertion that this part contains asymptotically almost all eigenvalues precise. This window includes the spectral edges. In the narrower terminology used for local spectral statistics, bulk locations are normalized points in compact subintervals of (−2,2)(-2,2); neighborhoods of −2-2 and 22 are the edges.

Corollary 1 (Semicircle bulk with an unbounded exceptional part). Suppose that

nνn→∞,npnlog⁡n→∞,andpn′→r∈[0,1]∖{12}.n\nu_n \to\infty,\qquad\frac{np_n}{\log n} \to\infty,\qquad\text{and}\qquad p'_n \to r \in[0,1]\setminus\left\{\frac{1}{2}\right\}.

Let sn=nνns_n = \sqrt{n\nu_n}, c∗=(3/2)∣2r−1∣c_* = (\sqrt{3}/2)|2r-1|, and θ∗=arctan⁡(2c∗)\theta_* = \arctan(2c_*).

(i) For every fixed $\varepsilon > 0,

#{j:∣λj(Hn)∣≤(2+ε)sn}=n−oP(n).(53)\#\{j : |\lambda_j(H_n)| \le(2+\varepsilon)s_n\} = n-o_P(n). \tag*{(53)}

Within this scale, the eigenvalue counts follow the semicircle law: for every −2<x<y<2-2 < x < y < 2,

1n#{j:xsn<λj(Hn)≤ysn}→P∫xyρsc(t) dt.\frac{1}{n}\#\{j : xs_n < \lambda_j(H_n) \le ys_n\} \xrightarrow{\mathbb{P}} \int_x^y \rho_{\mathrm{sc}}(t)\,dt.

In particular, every such interval contains a number of eigenvalues proportional to nn with probability tending to one.

(ii) For every fixed positive integer kk,

λk(Hn)npn→PΛk,λn+1−k(Hn)npn→P−Λk′,(54)\frac{\lambda_k(H_n)}{np_n} \xrightarrow{\mathbb{P}} \Lambda_k,\qquad\frac{\lambda_{n+1-k}(H_n)}{np_n} \xrightarrow{\mathbb{P}} -\Lambda'_k, \tag*{(54)}

where

Λk=c∗θ∗+(k−1)π>0,Λk′=c∗kπ−θ∗>0.\Lambda_k=\frac{c_*}{\theta_*+(k-1)\pi}>0,\qquad\Lambda'_k=\frac{c_*}{k\pi-\theta_*}>0.

Thus any fixed number of eigenvalues from each end has scale npnnp_n, which is asymptotically larger than the bulk scale.

(iii) For fixed ε>0\varepsilon>0, define

Nn+(ε)=#{j:λj(Hn)>(2+ε)sn},Nn−(ε)=#{j:λj(Hn)<−(2+ε)sn}.N_n^+(\varepsilon)=\#\{j:\lambda_j(H_n)>(2+\varepsilon)s_n\}, \qquad N_n^-(\varepsilon)=\#\{j:\lambda_j(H_n)<-(2+\varepsilon)s_n\}.

For every fixed integer K≥1K\ge1,

P{Nn+(ε)≥K, Nn−(ε)≥K}⟶1,Nn+(ε)+Nn−(ε)n→P0.(55)\mathbb{P}\{N_n^+(\varepsilon)\ge K,\ N_n^-(\varepsilon)\ge K\}\longrightarrow1, \qquad \frac{N_n^+(\varepsilon)+N_n^-(\varepsilon)}{n}\xrightarrow{\mathbb{P}}0. \tag*{(55)}

The exceptional counts therefore tend to infinity in probability on both sides, while their total proportion tends to zero.

Proof. Theorem 1 gives the interval-count limit and (53), since the semicircle law assigns mass one to [−2,2][-2,2] and has no atoms. The constants in part (ii) are those of Theorem 2(iii). Moreover, νn≤pn\nu_n\le p_n implies

npnsn≥npn⟶∞.\frac{np_n}{s_n}\ge\sqrt{np_n}\longrightarrow\infty.

For each fixed KK, part (ii) consequently yields λK(Hn)/sn→P+∞\lambda_K(H_n)/s_n\xrightarrow{\mathbb{P}}+\infty and λn+1−K(Hn)/sn→P−∞\lambda_{n+1-K}(H_n)/s_n\xrightarrow{\mathbb{P}}-\infty. By the ordering of the eigenvalues, with probability tending to 11, at least KK eigenvalues lie above the positive threshold and at least KK lie below the negative threshold. This proves the first assertion of (55). The second one is precisely the complement of (53). □

The corollary distinguishes two types of conclusions. The bulk is a statement about proportions and the empirical distribution. The explicit exceptional limits concern fixed indices from either end. They do not assert that every eigenvalue outside the bulk window has order npnnp_n. Indices growing with nn can occur on intermediate scales. Nor do they specify a canonical boundary between the bulk and its edges.

For comparison, consider the ordinary adjacency matrix AnA_n of G(n,p)G(n,p) with fixed p∈(0,1)p\in(0,1). Its mean is p(Jn−In)p(J_n-I_n), which, after a scalar shift, has rank one. The classical result of Füredi and Komlós [7 Theorem 1] gives λ1(An)/(np)→P1\lambda_1(A_n)/(np)\xrightarrow{\mathbb{P}}1 and, for every fixed ε>0\varepsilon>0,

P{max⁡2≤j≤n∣λj(An)∣≤(2+ε)np(1−p)}⟶1.(56)\mathbb{P}\left\{\max_{2\le j\le n}|\lambda_j(A_n)|\le(2+\varepsilon)\sqrt{np(1-p)}\right\}\longrightarrow1. \tag*{(56)}

Thus, with probability tending to one, there is exactly one eigenvalue beyond any fixed enlargement of the ordinary semicircle range. Under a nonzero limiting orientation bias, Corollary 1 instead gives unbounded exceptional counts on both sides. The additional deterministic term ipnanSnip_na_nS_n is responsible for this behavior: it has a whole sequence of positive and negative eigenvalues of order npnnp_n at fixed indices. At pn′=1/2p_n'=1/2 this imaginary mean vanishes, and Theorem 2 recovers single exceptional eigenvalue on the scale npnnp_n.

References

References

  1. [1]Sajeed Akbari, Jonathan Aloni, Maxwell Levit, Bojan Mohar, and S. Ahmad Mojallal. Hermitian spectra of tournaments. submitted for publication.
  2. [2]Sajeed Akbari, Jonathan Aloni, Maxwell Levit, Bojan Mohar, and Steven Xia. Spectrally symmetric orientations of graphs. arXiv: 2512.08049.
  3. [3]Z. Bai and J. W. Silverstein. Spectral Analysis of Large Dimensional Random Matrices. Springer Series in Statistics. Springer, New York, second edition, 2010. doi:10.1007/978-1-4419-0661-8.DOI
  4. [4]Patrick Billingsley. Convergence of Probability Measures. Wiley Series in Probability and Statistics. John Wiley & Sons, New York, second edition, 1999.
  5. [5]X. Chen, X. Li, and H. Lian. The skew energy of random oriented graphs. Linear Algebra Appl., 438:4547–4556, 2013. doi:10.1016/j.laa.2013.02.007.DOI
  6. [6]Ove Frank. Stochastic competition graphs. Review of the International Statistical Institute, 36(3):319–326, 1968.DOI
  7. [7]Z. Füredi and J. Komlós. The eigenvalues of random symmetric matrices. Combinatorica, 1(3):233–241, 1981. doi:10.1007/BF02579329.DOI
  8. [8]Lior Gishboliner, Michael Krivelevich, and Gal Kronenberg. On MAXCUT in strictly super-critical random graphs, and coloring of random graphs and random tournaments. Random Structures & Algorithms, 52(4):545–559, 2018.
  9. [9]Y. Guan, B. Cheng, M. Chen, M. Liang, J. Liu, J. Wang, C. Yang, and L. Zeng. The spectral distribution of random mixed graphs. Axioms, 11(3):126, 2022. doi:10.3390/axioms11030126.DOI
  10. [10]K. Guo and B. Mohar. Hermitian adjacency matrix of digraphs and mixed graphs. J. Graph Theory, 85:217–248, 2017. doi:10.1002/jgt.22057.DOI
  11. [11]D. Hu, H. Broersma, J. Hou, and S. Zhang. The spectra of random mixed graphs. Linear Algebra Appl., 653:320–338, 2022. doi:10.1016/j.laa.2022.08.019.DOI
  12. [12]D. Hu, H. Broersma, J. Hou, and S. Zhang. The skew spectral radius and skew Randić spectral radius of general random oriented graphs. Linear Algebra Appl., 685:125–137, 2024. doi:10.1016/j.laa.2024.01.003.DOI
  13. [13]D. Hu, X. Li, X. Liu, and S. Zhang. The spectral distribution of random mixed graphs. Linear Algebra Appl., 519:343–365, 2017. doi:10.1016/j.laa.2017.01.011.DOI
  14. [14]S. Li and Y. Yu. Hermitian adjacency matrix of the second kind for mixed graphs. Discrete Math., 345(5):112798, 2022. doi:10.1016/j.disc.2022.112798.DOI
  15. [15]J. Liu and X. Li. Hermitian-adjacency matrices and Hermitian energies of mixed graphs. Linear Algebra Appl., 466:182–207, 2015. doi:10.1016/j.laa.2014.10.028.DOI
  16. [16]Tomasz Łuczak, Andrzej Ruciński, and Jacek Gruszka. On the evolution of a random tournament. Discrete Mathematics, 148(1–3):311–316, 1996.DOI
  17. [17]B. Mohar. A new kind of Hermitian matrices for digraphs. Linear Algebra Appl., 584:343–352, 2020. doi:10.1016/j.laa.2019.09.024.DOI
  18. [18]Terence Tao. Topics in Random Matrix Theory, volume 132 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2012.DOI
  19. [19]J. A. Tropp. User-friendly tail bounds for sums of random matrices. Found. Comput. Math., 12:389–434, 2012. doi:10.1007/s10208-011-9099-z.DOI
  20. [20]E. P. Wigner. On the distribution of the roots of certain symmetric matrices. Ann. of Math. (2), 67:325–327, 1958. doi:10.2307/1970008.DOI

Paper details

vlnc:W_uj96fceg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents