Limiting spectral distribution of a special circulant matrix with dependent entries

LIMITING SPECTRAL DISTRIBUTION OF CIRCULANT MATRIX WITH DEPENDENT ENTRIES

ARUP BOSE AND KOUSHIK SAHA^∗

This article is subsumed in the Technical Report R6/2009, Stat-Math Unit.

Abstract. In this article, we derive the limiting spectral distribution of thecirculant matrix when the input sequence is a stationary infinite order two sided moving average process.

Keywords: Large dimensional random matrix, eigenvalues, circulant matrix, empirical spectral distribution, limiting spectral distribution, moving average process, convergence in distribution, convergence in probability, normal approximation.

AMS 2000 Subject Classification. 60F99, 62E20, 60G57.

1. Introduction and Main result

Suppose λ₁, λ₂, ..., λ_n are all the eigenvalues of a square matrix A_n of order n. Then the empirical spectral distribution function (ESDF) of A_n is defined as

F_n(x, y) =n⁻¹ Xn

i=1

I{Reλ_i ≤x, Imλ_i≤y}.

Let {A_n}^∞_n=1 be a sequence of square matrices with the corresponding ESDF {F_n}^∞_n=1. The Limiting Spectral Distribution (or measure) (LSD) of the sequence is defined as the weak limit of the sequence {F_n}^∞_n=1, if it exists.

If{A_n}are random, the limit is understood to be in some probabilistic sense, such as “almost surely” or “in probability”. Suppose elements of {A_n} are defined on some probability space (Ω,F, P), that is {A_n} are random. Let F be a nonrandom distribution function. We say the ESD of A_n converges to thelimiting spectral distribution (LSD)F inL₂ if at all continuty points (x, y) ofF,

Z

ω

¡F_n(x, y)−F(x, y)¢₂

dP(ω)→0 as n→ ∞

and converges in probability toF if for every² >0 and at all continuty points (x, y) ofF, P¡

|F_n(x, y)−F(x, y)|> ²¢

→0 as n→ ∞.

∗Research supported by CSIR Fellowship, Dept. of Science and Technology, Govt. of India.

1

For detailed information on limiting spectral distributions of large dimensional random matrices see [Bai(1999)] and also [Bose and Sen(2008)].

In this article we focus on obtaining the LSD of thecirculant matrix (C_n) given by

C_n = ^√1_n









x₀ x₁ x₂ . . . x_n−2 x_n−1 x_n−1 x₀ x₁ . . . x_n−3 x_n−2 x_n−2 x_n−1 x₀ . . . x_n−4 x_n−3

...

x₁ x₂ x₃ . . . x_n−1 x₀







 .

So, the (i, j)th element of the matrix is x(j−i+n)mod n. The eigenvalues are given by (see for example [Brockwell and Davis(2002)]),

λ_k = 1

√n

n−1X

l=0

x_le^iωkl=b_k+ic_k ∀k= 1,2,· · ·, n, where

ω_k = 2πk

n , b_k= 1

√n

n−1X

l=0

x_lcos(ω_kl), c_k= 1

√n

n−1X

l=0

x_lsin(ω_kl).

The existence of the LSD ofC_n is given by the following theorem of [Bose and Mitra(2002)].

Theorem 1.1. Let{x_i}be a sequence of independent random variables with mean 0 and variance 1 and sup_iE |x_i |³<∞. Then the ESD ofC_n converges in L₂ to the two-dimensional normal distribution given by N₂(0, D) whereDis a diagonal matrix with diagonal entries 1/2.

We investigate the existence of LSD ofC_n under a dependent situation. Let{x_n;n≥0} be a two sided moving average process,

x_n= X∞

i=−∞

a_i²_n−i

where {a_n;n ∈Z} ∈ l₁, that is P

n|a_n| <∞, are nonrandom and {²_i;i ∈Z} are iid random variables with mean zero and variance one. We show that the LSD ofC_n continues to exist in this dependent situation. Defineγ_h =Cov(x_t+h, x_t). Then it is easy to see thatP

j∈Z|γ_j|<∞ and thespectral density function of{x_n} is given by

f(ω) = 1 2π

X

k∈Z

γ_kexp(ikω) = 1 2π

£γ₀+ 2X

k≥1

γ_kcos(kω)¤

for ω∈[0,2π].

Letf^∗ = inf_ω∈[0,2π]f(ω) and C₀ ={ω∈[0,2π];f(ω) = 0}. Fork= 1,2,· · ·, n, define ξ_2k−1= 1

√n

n−1X

t=0

²_tcos(ω_kt), ξ_2k= 1

√n

n−1X

t=0

²_tsin(ω_kt).

Define

B(ω) =

µ a₁(e^iω) −a₂(e^iω) a₂(e^iω) a₁(e^iω)

¶ ,

wherea₁(e^iω) =R[a(e^iω)], a₂(e^iω) =I[a(e^iω)], a(e^iω) is same as defined in Lemma 1.3 and for z∈C,R(z),I(z) denote the real and imaginary part of zrespectively. It is easy to see that

|a(e^iω)|² =a₁(e^iω)²+a₂(e^iω)² = 2πf(ω).

Define for (x, y)∈R² and ω∈[0,2π], H(ω, x, y) =

½ P¡

B(ω)(N₁, N₂)⁰≤√

2(x, y)⁰¢

if f(ω)6= 0, I(x≥0, y ≥0) if f(ω) = 0.

Since a(e^iω) is continuous on [0,2π], it is easy to verify that for fixed (x, y), H is bounded continuous function inω. Hence we may define

F(x, y) = Z ₁

0

H(2πs, x, y)ds.

F is a proper distribution function.

For any Borel set B, let λ(B) denote the corresponding Lebesgue measure. It is easy to see that

(i) if λ(C₀) = 0 thenF is continuous everywhere and,

(ii) ifλ(C₀)6= 0 thenF is discontinuous only on D₁={(x, y) :xy = 0}.

Theorem 1.2. Suppose {²_i} are iid with E|²_i|^(2+δ) <∞. Then the ESD of C_n converges in L₂ to the LSD

F(x, y) = Z ₁

0

H(2πs, x, y)ds, and if λ(C₀) = 0 we have

F(x, y) = Z Z

I_{{(v1,v2)≤(x,y)}}

h Z 1 0

I_{f(2πs)6=0} 1

2π²f(2πs)e⁻

v2 1 +v2 2πf(2πs)2 ds

i

dv₁dv₂.

Remark 1.1. If inf_ω∈[0,2π]f(ω)>0, we can write F_g in the following form F(x, y) =

Z Z

I_{{(v1,v2)≤(x,y)}}

h Z 1 0

1

2π²f(2πs)e⁻

v2 1 +v2

2 2πf(2πs)ds

i

dv₁dv₂.

Remark 1.2. If {x_i} are i.i.d, then f(ω) = 1/2π for all ω ∈ [0,2π] and the LSD is standard complex normal distribution. This agrees with Theorem 1.1.

Proof of the theorem mainly depends on following two lemmas. Lemma 1.3 follows from [Fan and Yao(2003)] (Theorem 2.14(ii), page 63). For completeness, we have provided a proof.

The proof of Lemma 1.4 follows easily from [Bhattacharya and Ranga Rao(1976)] (Corollary 18.3, page 184). We omit the details.

Lemma 1.3. Letx_t=P_∞

j=−∞a_t²_t−j fort≥0, where{²_t} are i.i.d random variables with mean 0, variance 1 and P_∞

j=−∞|a_j|<∞. Then for k= 1,2,· · ·, n, λ_k=a(e^iωk)[ξ_2k−1+iξ_2k] +Y_n(ω_k), wherea(e^iωk) =P_∞

j=−∞a_je^iωkj and max_0≤k<nE|Y_n(ω_k)|² →0 asn→ ∞.

Proof.

λ_k = 1

√n

n−1X

t=0

x_te^iωkt

= 1

√n X∞

j=−∞

a_je^iωkj

n−1X

t=0

²_t−je^iωk(t−j)

= 1

√n X∞

j=−∞

a_je^iωkj Ãn−1X

t=0

²_te^iωkt+U_nj

!

= a(e^iωk)[ξ_2k−1+iξ_2k] +Y_n(ω_k),

where a(e^iωk) =

X∞

j=−∞

a_je^iωkj, U_nj=

n−1−jX

t=−j

²_te^iωkt−

n−1X

t=0

²_te^iωkt, Y_n(ω_k) =n^−1/2 X∞

j=−∞

a_je^iωkjU_nj.

Note that if|j|< n,U_nj is a sum of 2|j|independent random variables, whereas if|j| ≥n,U_nj is a sum of 2nindependent random variables. ThusE|U_nj|²≤2 min(|j|, n). Therefore, for any fixed positive integerl and n > l,

E|Y_n(ω_k)|² ≤ 1 n



 X^∞

j=−∞

|a_j|(EU_nj² )^1/2





2 ¡

∵ X∞

−∞

|a_j|<∞¢

≤ 2 n



 X^∞

j=−∞

|a_j|{min(|j|, n)}^1/2





2

≤ 2



 1

√n X

|j|≤l

|a_j||j|^1/2+X

|j|>l

|a_j|





2

.

Note that the right-hand side of the above expression is independent of k and as n → ∞, it can be made smaller than any given positive constant by choosing l large enough. Hence,

max_1≤k≤nE|Y_n(ω_k)|² →0. ¤

Lemma 1.4. Let X₁, . . . , X_k be independent random vectors with values in R^d, having zero means and an average positive-definite covariance matrix V_k = k⁻¹P_k

j=1CovX_j. Let G_k

denote the distribution of k^−1/2T_k(X₁+. . .+X_k), whereT_k is the symmetric, positive-definite matrix satisfyingT_k² =V_k⁻¹,n≥1. If for someδ >0,E kX_j k^(2+δ)<∞, then

sup

C∈C

|G_k(C)−Φ_0,I(C)| ≤ ck^−δ/2£ k⁻¹

Xk

j=1

E kT_kX_j k^(2+δ)¤

≤ ck^−δ/2(λ_min(V_k))^−(2+δ)£ k⁻¹

Xk

j=1

E kX_j k^(2+δ)¤

where Φ_0,I is the normal probability function with mean zero and identity covariance matrix, C, the class of all Borel-measurable convex subsets of R^d and c is a constant, depending only on d.

Proof of Theorem 1.2: We first assume λ(C₀) = 0. To prove the theorem it suffices to show that for eachx, y∈R,

(1.1) E(F_n(x, y))→F(x, y) and V(F_n(x, y))→0.

Note that we may ignore the eigenvalueλ_nand alsoλ_n/2whenevernis even since they contribute atmost 2/nto the ESD F_n(x, y). So forx, y∈R,

E[F_n(x, y)] ∼ n⁻¹

n−1X

k=1,(k6=n/2)

P(b_k ≤x, c_k≤y).

Define for k= 1,2,· · · , n,

η_k= (ξ_2k−1, ξ_2k)⁰, Y_1n(ω_k) =R[Y_n(ω_k)], Y_2n(ω_k) =I[Y_n(ω_k)],

A_k=

µ a₁(e^iωk) −a₂(e^iωk) a₂(e^iωk) a₁(e^iωk)

¶ ,

where a(e^iωk), Y_n(ω_k) are same as defined in Lemma 1.3. Then (b_k, c_k)⁰ = A_kη_k + (Y_1n(ω_k), Y_2n(ω_k))⁰.From Lemma 1.3, it is intutively clear that for largen, λ_k∼a(e^iωk)[ξ_2k−1+ iξ_2k]. So first we show that for largen

1 n

n−1X

k=1,(k6=n/2)

P(b_k≤x, c_k≤y)∼ 1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k ≤(x, y)⁰).

Note

¯¯

¯1 n

n−1X

k=1,(k6=n/2)

P(b_k≤x, c_k≤y)− 1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k ≤(x, y)⁰)

¯¯

¯

=

¯¯

¯1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k+ (Y_1n(ω_k), Y_2n(ω_k))⁰ ≤(x, y)⁰)−P(A_kη_k≤(x, y)⁰)

¯¯

¯

≤ 1 n

n−1X

k=1,(k6=n/2)

P((|Y_1n(ω_k)|,|Y_2n(ω_k)|)>(², ²))

+

¯¯

¯1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k≤(x, y)⁰,(|Y_1n(ω_k)|,|Y_2n(ω_k)|)≤(², ²))−P(A_kη_k ≤(x, y)⁰)

¯¯

¯

= T₁+T₂, say.

Now using Lemma 1.3, as n→ ∞ T₁≤ 1

n

n−1X

k=1,(k6=n/2)

P(|Y_n(ω_k)|² >2²²)≤ 1 2²²sup

k

E|Y_n(ω_k)|² →0.

T₂ ≤ max n¯¯

¯1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k ≤(x+², y+²)⁰−P(A_kη_k≤(x, y)⁰)

¯¯

¯,

¯¯

¯1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k ≤(x−², y−²)⁰−P(A_kη_k ≤(x, y)⁰)

¯¯

¯ o

and ¯

¯¯1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k≤(x+², y+²)⁰−P(A_kη_k ≤(x, y)⁰)

¯¯

¯≤T₃+T₄+T₅. where

T₃=

¯¯

¯1 n

n−1X

k=1,(k6=n/2)

P(A_kξ_k≤(x, y)⁰)−P(A_k(N₁ N₂)⁰≤(√ 2x,√

2y)⁰)

¯¯

¯,

T₄=

¯¯

¯1 n

n−1X

k=1,(k6=n/2)

P(A_kξ_k≤(x+², y+²)⁰)−P(A_k(N₁ N₂)⁰ ≤(√

2x+√ 2²,√

2y+√ 2²)⁰)

¯¯

¯,

T₅=

¯¯

¯1 n

n−1X

k=1,(k6=n/2)

P(A_k(N₁N₂)⁰ ≤(√ 2x+√

2²,√ 2y+√

2²)⁰)−P(A_k(N₁N₂)⁰ ≤(√ 2x,√

2y)⁰)

¯¯

¯.

To showT₃, T₄→0 define fork= 1,2,· · · , n−1,(except fork=n/2) andl= 0,1,2,· · ·, n−1, X_l,k = (√

2²_lcos(ω_kl), √

2²_lsin(ω_kl))⁰. Note that

E(X_l,k) = 0 ∀ l, k, n.

(1.2)

n⁻¹

n−1X

l=0

Cov(X_l,k) =I ∀ k, n.

(1.3)

Note that fork6=n/2

{A_kη_k ≤(x, y)⁰}={A_k(n^−1/2

n−1X

l=0

X_l,k)≤(√ 2x,√

2y)⁰}.

Since {(r, s) :A_k(r, s)⁰ ≤(√ 2x,√

2y)⁰} is a convex set in R² and {X_l,k, l= 0,1, . . .(n−1)}

satisfies (1.2) and (1.3), we can apply Lemma 1.4 for k6=n/2 to get

¯¯P(A_k(n^−1/2

n−1X

l=0

X_l,k)≤(√ 2x,√

2y)⁰)−P(A_k(N₁, N₂)⁰ ≤(√ 2x,√

2y)⁰)¯¯≤cn^−δ/2[n⁻¹

n−1X

l=0

E kX_lkk^(2+δ)], whereN₁, N₂ are independent standard normal variates. Note that

sup

1≤k≤n

[n⁻¹

n−1X

l=0

EkX_lk k^(2+δ)]≤M <∞ and, asn→ ∞

1 n

n−1X

k=1,(k6=n/2)

¯¯P(A_k(n^−1/2

n−1X

l=0

X_l,k)≤(√ 2x,√

2y)⁰)−P(A_k(N₁, N₂)⁰ ≤(√ 2x,√

2y)⁰)¯

¯≤cM n^−δ/2→0.

Hence T₃ →0 and similarlyT₄→0. and also

n→∞lim 1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k ≤(x, y)⁰) = lim

n→∞

1 n

n−1X

k=1,(k6=n/2)

H(2πk n , x, y)

= Z ₁

0

H(2πs, x, y)ds.

Therefore

n→∞lim T₅ =

¯¯

¯ Z ₁

0

H(2πs, x+², y+²)ds− Z ₁

0

H(2πs, x, y)ds

¯¯

¯

≤ Z ₁

0

¯¯H(2πs, x+², y+²)ds−H(2πs, x, y)¯

¯ds.

Note that

¯¯H(2πs, x+², y+²)ds−H(2πs, x, y)¯¯≤2 and for fixed (x, y)∈R² as²→0,

(1.4) ¯

¯H(2πs, x+², y+²)ds−H(2πs, x, y)¯

¯→0.

Hence by DCT lim_²→0lim_n→∞T₅ = 0 and

²→0lim lim

n→∞

¯¯

¯1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k ≤(x+², y+²)⁰−P(A_kη_k≤(x, y)⁰)

¯¯

¯= 0.

Also note that for fixed (x, y) as ²→0,

(1.5) ¯

¯H(2πs, x−², y−²)ds−H(2πs, x, y)¯

¯→0,

outside the measure zero set C₀. Using this fact, proceeding as above we can show that

²→0lim lim

n→∞

¯¯

¯1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k ≤(x−², y−²)⁰−P(A_kη_k≤(x, y)⁰)

¯¯

¯= 0, and hence lim_²→0lim_n→∞T₂= 0. Therefore as n→ ∞,

E[F_n(x, y)]∼ 1 n

n−1X

k=1,(k6=n/2)

P(A_kη_k≤(x, y)⁰)→ Z ₁

0

H(2πs, x, y)ds,

and since λ(C₀) = 0, we have Z ₁

0

H(2πs, x, y)ds = Z ₁

0

I{f(2πs)6=0}H(2πs, x, y)ds

= Z ₁

0

I{f(2πs)6=0}

h Z Z

I_{{B(2πs)(u1,u2)}⁰_≤(x,y)⁰_} 1 2πe^−u

21+u2

2 2du₁du₂ i

ds

= Z ₁

0

I{f(2πs)6=0}

h Z Z

I_{{(v1,v2)≤(x,y)}} 1

2π²f(2πs)e⁻

v2 1 +v2

2πf(2πs)2 dv₁dv₂ i

ds

= Z Z

I_{{(v1,v2)≤(x,y)}}

h Z 1 0

I{f(2πs)6=0}

1

2π²f(2πs)e⁻

v2 1 +v2 2πf(2πs)2 ds

i dv₁dv₂

= F(x, y).

Now, to showV[F_n(x, y)]→0, it is enough to show that 1

n²

Xn

k6=k⁰;k,k⁰=1

Cov(J_k, J_k⁰)→0.

(1.6)

where for 1≤k≤n,J_k is the indicator that{b_k≤x, c_k≤y}. Observe that 1

n²

Xn

k6=k⁰;k,k⁰=1

Cov(J_k, J_k⁰) = 1 n²

Xn

k6=k⁰;k,k⁰=1

[E(J_k, J_k⁰)−E(J_k)E(J_k⁰)]. Now asn→ ∞,

1 n²

Xn

k6=k⁰;k,k⁰=1

E(J_k)E(J_k⁰) =¡1 n

Xn

k=1

E(J_k)¢₂

− 1 n²

Xn

k=1

(E(J_k))²→H(x, y)². So to show (1.6), it is enough to show as n→ ∞,

1 n²

Xn

k6=k⁰;k,k⁰=1

E(J_k, J_k⁰)→H(x, y)². Along the lines of the proof used to show _n¹P_n

k=1P(A_k(N₁ N₂)⁰ ≤ (√ 2x,√

2y)⁰) → F(x, y), one may now extend the vectors of two coordinates defined above to ones with four coordinates and proceed exactly as above to verify this. We omit the routine details.

When λ(C₀)6= 0, we have to show (1.1) only at continuty points ofF and it is continuous on complement of D₂. All the above steps except (1.4),(1.5) in the proof will go through for all (x, y), but on complement ofD(1.4),(1.5) also holds. Hence if λ(C₀)6= 0, we have our required

LSD. This proves the Theorem. ¤

References

[Bai(1999)] Z. D. Bai. Methodologies in spectral analysis of large-dimensional random matrices, a review.Statist.

Sinica, 9(3):611–677, 1999. ISSN 1017-0405. With comments by G. J. Rodgers and Jack W. Silverstein; and a rejoinder by the author.

[Bhattacharya and Ranga Rao(1976)] R. N. Bhattacharya and R. Ranga Rao.Normal approximation and as- ymptotic expansions. John Wiley & Sons, New York-London-Sydney, 1976. Wiley Series in Probability and Mathematical Statistics.

[Bose and Mitra(2002)] Arup Bose and Joydip Mitra. Limiting spectral distribution of a special circulant.Statist.

Probab. Lett., 60(1):111–120, 2002. ISSN 0167-7152.

[Bose and Sen(2008)] Arup Bose and Arnab Sen. Another look at the moment method for large dimensional random matrices.Electron. J. Probab., 13:no. 21, 588–628, 2008. ISSN 1083-6489.

[Brockwell and Davis(2002)] Peter J. Brockwell and Richard A. Davis.Introduction to time series and forecasting.

Springer Texts in Statistics. Springer-Verlag, New York, second edition, 2002. ISBN 0-387-95351-5. With 1 CD-ROM (Windows).

[Fan and Yao(2003)] Jianqing Fan and Qiwei Yao.Nonlinear time series. Springer Series in Statistics. Springer- Verlag, New York, 2003. ISBN 0-387-95170-9. Nonparametric and parametric methods.

(Arup Bose)Stat-Math Unit, Indian Statistical Institute, 203 B. T. Rd., Calcutta 700108, India, E-mail: abose@isical.ac.in, bosearu@gmail.com

(Koushik Saha) Stat-Math Unit, Indian Statistical Institute, 203 B. T. Rd., Calcutta 700108, India, E-mail: koushik r@isical.ac.in