negationslash ? 18.338J/16.394J: The Mathematics of In?nite Random Matrices The Stieltjes transform based approach Raj Rao Handout #4, Thursday, September 16, 2004. 1 The eigenvalue distribution function For an N ×N matrix A N , the eigenvalue distribution function 1 (e.d.f.) F A N (x) is de?ned as F A N (x) = Number of eigenvalues of A N ≤ x . (1) N As de?ned, the e.d.f. is right continuous and possibly atomic i.e. with step discontinuities at discrete points. In practical terms, the derivative of (1), referred to as the (eigenvalue) level density, is simply the appropriately normalized histogram of the eigenvalues of A N . The MATLAB code histn we distributed earlier approximates this density. A surprising result in in?nite RMT is that for some matrix ensembles, the expectation E[F A N (x)] has a well de?ned i.e. not zero and not in?nite limit. We drop the notational dependence on N in (1) by de?ning the limiting e.d.f. as F A (x) = lim E[F A N (x)]. (2) N→∞ This limiting e.d.f. 2 is also sometimes referred to in literature as the integrated density of states [2, 3]. Its derivative is referred to as the level density in physics literature [4]. The region of support associated with this limiting density is simply the region where dF A (x) = 0. When discussing the limiting e.d.f. we shall often distinguish between, its atomic and non-atomic components. 2 The Stieltjes transform representation One step removed from the e.d.f. is the Stieltjes transform which has proved to be an e?cient tool for determining this limiting density. For all non-real z the Stieltjes (or Cauchy) transform of the probability measure F A (x) is given by 1 m A (z) = x ?z dF A (x) Im z negationslash= 0. (3) The integral above is over the whole 3 or some subset of the real axis since for the matrices of interest, such as the Hermitian or real symmetric matrices, the eigenvalues are real. When we refer to the “Stieltjes transform of A” in this paper, we are referring to m A (z) de?ned as in (3) expressed in terms of the limiting density dF A (x) of the random matrix ensemble A. 1 This is also referred to in literature as the empirical distribution function [1]. 2 Unless we state otherwise any reference to an e.d.f. or the level density. in this paper will refer to the corresponding limiting e.d.f. or density respectively. 3 While the Stieltjes integral is over the positive real axis, the Cauchy integral is more general [5] and can include complex contours as well. This distinction is irrelevant for several practical classes of matrices, such as the sample covariance matrices, where all of the eigenvalues are non-negative. Nonetheless, throughout this paper, (3) will be referred to as the Stieltjes transform with the implicit assumption that the integral is over the entire real axis. ? ? ? ? The Stieltjes transform in (3) can also be interpreted as an expectation with respect to the measure F A (x) such that 1 m A (z) = E X . (4) zx ? Since there is a one-to-one correspondence between the probability measure F A (x) and the Stieltjes transform, convergence of the Stieltjes transform can be used to show the convergence of the probability measure F A (x). Once this convergence has been established, the Stieltjes transform can be used to yield the density using the so-called Stieltjes-Perron inversion formula [6] dF A (x) 1 = lim Im m A (x + iξ). (5) dx π ξ→0 When studying the limiting distribution of large random matrices, the Stieltjes transform has proved to be particularly relevant because of its correspondence with the matrix resolvent. The trace of the matrix resolvent, M A (z), de?ned as M A (z) = (A N ?zI) ?1 can be written as N ? 1 tr[M A (z)] = (6) zλ i ? i=1 where λ i for i = 1, 2,. . . , N are the eigenvalues of A N . For any A N , M A (z) is a non-random quantity. However, when A N is a large random matrix, 1 m A (z) = lim tr[M A (z)]. (7) N→∞ N The Stieltjes transform and its resolvent form in (7) are intimately linked to the classical moment problem [6]. This connection can be observed by noting that the integral in (3) can be expressed as an analytic “multipole” series expansion about z = ∞ such that ? ∞ k ∞ ? k m A (z) = z k+1 dF A (x) = ? x dF A (x) ? x z k+1 ? ? k=0 k=0 ∞ (8) 1 ? M k A = . z k+1 ? z ? k=1 where M k A = x k dF A (x) is the k th moment of x on the probability measure dF A (x). The analyticity of the Stieltjes transform about z = ∞ expressed in (8) is a consequence of our implicit assumption that the region of support for the limiting density dF A (x) is bounded i.e. lim x→∞ dF A (x) = 0. Incidentally, the η-transform introduced by Tulino and Verd`u in [7] can be expressed in terms of m(z) and permits a series expansion about z = 0. Given the relationship in (7), it is worth noting that the matrix moment M A is simply k M A = lim 1 tr[A k N ] = x k dF A (x). (9) k N→∞ N Equation (8), written as a multipole series, suggests that a way of computing the density would be to determine the moments of the random matrix as in (9), and then invert the Stieltjes transform using (5). For the famous semi-circular law, Wigner actually used a moment based approach in [8] to determine the density for the standard Wigner matrix though he did not explicitly invert the Stieltjes transform as we suggested above, As the reader may imagine, such a moment based approach is not particularly useful for more general classes of random matrices. We discuss a more relevant and practically useful Stieltjes transform based approach next. ? ? ? ? 3 Stieltjes transform based approach Instead of obtaining the Stieltjes transform directly, the so-called Stieltjes transform approach relies instead on ?nding a canonical equation that the Stieltjes transform satis?es. The Marˇcenko-Pastur theorem [9] was the ?rst and remains most famous example of such an approach. We include a statement of its theorem in the form found in literature. We encourage you to write this theorem, as an exericse, in a simpler manner. Theorem 1 (The Marˇcenko-Pastur Theorem ). Consider an N ×N matrix, B N . Assume that 1. X n is an n×N matrix such that the matrix elements X n ij are independent identically distributed (i.i.d.) complex random variables with mean zero and variance 1 i.e. X n ij ] = 0 and E[bardblX n = 1. ij ∈ C, E[X n ij bardbl 2 ] 2. n = n(N) with n/N → c > 0 .as N →∞ 3. T n = diag(τ 1 n ,τ 2 n ,...,τ n n } converges almost surely in n ) where τ i n ∈ R, and the e.d.f. of {τ 1 n ,...,τ n distribution to a probability distribution function H(τ) as N →∞. 1 4. B N = A N + N X ? T n X n , where A N is a Hermitian N×N matrix for which F A N converges vaguely to A n almost surely, A being a possibly defective (i.e. with discontinuities) nonrandom distribution function. 5. X n , T n , and A N are independent. Then, almost surely, F B N converges vaguely, almost surely, as N → ∞ to a nonrandom d.f. F B whose Stieltjes transform m(z), z ∈C, satis?es the canonical equation τ dH(τ) m(z) = m A z ?c (10) 1 + τ m(z) We now illustrate the use of this theorem with a representative example. This example will help us highlight issues that will be of pedagogical interest throughout this semester. 1 Suppose A N = 0 i.e. B N = N X ? T n X n . The Stieltjes transform of A N , by the de?nition in (3), is then n simply 1 1 m A (z) = = . (11) 0 ?z ? z Hence, using the Marˇcenko-Pastur theorem as expressed in (10), the Stieltjes transform m(z) of B N is given by 1 . (12) m(z) = ? τdH(τ) ? z ?c 1+τm(z) Rearranging the terms in this equation and using m instead of m(z) for notational convenience, we get 1 τdH(τ) z = + c . (13) ? m 1 + τm Equation (13) expresses the dependence between the Stieltjes transform variable m and probability space variable z. Such a dependence, expressed explicitly in terms of dH(τ), will be referred to throughout this paper as a canonical equation. Equation (13) can also be interpreted as the expression for the functional inverse of m(z). To determine the density of B N by using the inversion formula in (5) we need to ?rst solve (13) for m(z). In order to obtain an equation in m and z we need to ?rst know dH(τ) in (13). In theory, dH(τ) could be any density that satis?es the conditions of the Marˇcenko-Pastur theorem. However, as we shall shortly recognize, for an arbitrary distribution, it might not be possible to obtain an analytical or even an easy numerical solution for the density On the other hand, for some speci?c distributions of dH(τ), it will indeed be possible to analytically obtain the density We consider one such distribution below. Suppose T n = I i.e. the diagonal elements of T n are non-random with d.f. dH(τ) = δ(τ ?1). Equation (13) then becomes 1 c z = + . (14) ? m 1 + m ? ? ? Rearranging the terms in the above equation we get zm(1 + m) = ?(1 + m) + cm (15) which, with a bit of algebra, can be written as 2 m z + m(1 ?c + z)+ 1 = 0. (16) Equation (16) is a polynomial equation in m whose coe?cients are polynomials in z. We will refer to such polynomials, often derived from canonical equations as Stieltjes (transform) polynomials for the remainder of this paper. As discussed, to obtain the density using (5) we need to ?rst solve (16) for m in terms of z. Since, from (16), we have a second degree polynomial in m it is indeed possible to analytically solve for its roots and obtain the density. dF B /dx 0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 ?1 0 1 2 3 4 5 6 7 x Figure 1: Level density for B N = (1/N)X ? X n with c = 2. n This level density, sometimes referred to in the literature as the Marˇcenko-Pastur distribution, is given by dF B (x) = max 0, 1 ?c δ(x) + (x ?b ? )(b + ?x) I [ b ? ,b + ] (17) dx 2πx where b ± = (1± √ c) 2 and I [b ,b + ] is the indicator function that is equal to 1 for b ? < z < b + and 0 elsewhere. ? 1 Figure 1 compares the histogram of the eigenvalues of 1000 realizations of the matrix B N = N X ? X n with n N = 100 and n = 200 with the solid line indicating the theoretical density given by (17) for c = n/N = 2. We now consider a modi?cation to the Marˇcenko-Pastur theorem that is motivated by the sample covari ance matrices that appear often in array processing applications. 3.1 The Sample Covariance Matrix In the previous section we used the Marˇcenko-Pastur theorem to examine the density of a class of random 1 ? 1/2 matrices B N = N X ? T n X n . Suppose we de?ned the N ×n matrix, Y N = X n T n , then B N may be written n as 1 ? B N = Y N Y N . (18) N 1/2 Recall that T n was assumed to be diagonal and non-negative de?nite so T n can be constructed uniquely up to the sign. If Y N were to be interpreted as a matrix of observations, then B N written as (18) is reminiscent ? ? ? ? ? ? ? ? 1 n n X ? n n N n N n T 1/2 n n T 1/2 n X n n N n n n n N n X ? n T 1/2 n X n T 1/2 n 1 On nN N YN × Y N ?× O ? = = C n B N Figure 2: The matrices B n and C N when n > N. of sample covariance matrices that appear in many engineering and statistical applications. However, among ? other things, it is subtly di?erent because of the normalization of the Y N Y N by the number of rows N of Y N rather than by the number of columns n. Hence, we need to come up with a de?nition of a sample covariance matrix that mirrors the manner in which it is used in practical applications. With engineering, particularly signal processing applications in mind, we introduce the n×N matrix, 1/2 O n = T n X n and de?ne 1 ? C n = O n O n (19) N to be the sample covariance matrix (SCM). By comparing (18) and (19) while recalling the de?nitions of Y N and O n , it is clear that the eigenvalues of B n are related to the eigenvalues of C n . For B N of the form in (18), the Marˇcenko-Pastur theorem can be used to obtain the canonical equation for m B (z) given by (13). Recall, that by m B (z) we mean the Stieltjes transform associated with the limiting e.d.f. F B (x) of B N as N →∞. There is however, an exact relationship between the non-limiting e.d.f.’s F B N (x) and the F C n (x) and hence the corresponding Stieltjes transforms m B N (z) and m C n (z) respectively. We exploit this relationship below to derive the canonical equation for C n from the canonical equation for B N given in (13). Figure 2 schematically depicts C n and B N when n > N i.e. when c > 1. In this case, C n , as denoted in the ?gure, will have n?N zero eigenvalues. The other N eigenvalues of C n will, however, be identically equal to the N eigenvalues of B N . Hence, the e.d.f. of C n can be exactly expressed in terms of the e.d.f. of B N as n F C n (x) = n?N I (0,∞] + F B N (x) (20) N N = (c?1)I (0,∞] + cF B N (x). (21) Recalling the de?nition of the Stieltjes transform in (3), this implies that the Stieltjes transform m C n (z) of C n is related to the Stieltjes transform m B N (z) of B N by the expression m C n (z) = ? c?1 + cm B N (z). (22) z Similarly, Figure 3 schematically depicts C n and B N when n < N i.e. c < 1. In this case, B N , as denoted in the ?gure, will have N ?n zero eigenvalues. The other n eigenvalues of B N will, however, be identically equal to the n eigenvalues of C n . Hence, as before, the e.d.f. of B N can be exactly expressed in terms of the e.d.f. of C n as N F B N (x) = N ?n I (0,∞] + F C n (x) (23) n n 1 1 = c ?1 I (0,∞] + F C n (x) (24) c Once again, recalling the de?nition of the Stieltjes transform in (3), this implies that the Stieltjes transform m C n (z) of C n is related to the Stieltjes transform m B N (z) of B N by the expression 1 1 1 m B N (z) = ? c ?1 z + c m C n (z). (25) ? ? ? n N n n nnn T 1/2 n X n T 1/2 n X ? n N n n nn n n N X ? n N T 1/2 n T 1/2 n X n 1 1 N O n n N Y N × Y N ? × O ? = = C n B N Figure 3: The matrices B n and C N when n < N. Multiplying both sides of (25) by c, we get 1 cm B N (z) = ?(1 ?c) + m C n (z) (26) z which upon rearranging the terms is precisely (22). Equation (22) is an exact expression relating the Stieltjes transforms of C n and B N for all n and N. As N → ∞, the Marˇcenko-Pastur theorem states that m B N (z) → m B (z) which implies that the limiting Stieltjes transform m C (z), for C n can be written in terms of m B (z) using (22) as m C (z) = c?1 + cm B (z). (27) ? z For our purpose of getting the canonical equation for m C (z) using the canonical equation for m B (z), it is more useful to rearrange the terms in (27) and express m B (z) can be written in terms of m C (z). This relationship is simply 1 1 1 m B (z) = ? c ?1 z + m C (z). (28) c Hence, to obtain the canonical equation for m C (z) we simply have to substitute the expression for m B (z) in (28) into (13). With some fairly straightforward algebra, that we shall omit here, it can be veri?ed that m C (z) is the solution to the canonical equation dH(τ) m C (z) = . (29) {(1 ?c?czm C (z)}τ ?z 1/2 ? 1/2 Incidentally, (29)was ?rst derived by Silverstein in [10]. He noted that the eigenvalues of 1 T n X n X n T n N ? were the same as those of 1 X n X n T n so that (29) was the canonical equation for this class of matrices as N well. Additionally, in their proof of the Marˇcenko-Pastur theorem in [11], Bai and Silverstein dropped the restriction on T n being diagonal so that T n could be any matrix whose e.d.f. F T n H. As the reader may → appreciate, this broadens the class of matrices for which this theorem may be applied. 3.2 The (generalized) Wishart matrix 1 ? Revisiting the previous example, when T n = I, C n = N X n X . This matrix C n is the generalized version of n the famous Wishart matrix ensemble ?rst studied by Wishart in 1928 [12]. In physics literature, the Wishart matrix is also referred to as the Laguerre Ensemble [13]. Strictly speaking, C n is referred to as a Wishart matrix only when the elements of X n are i.i.d. Gaussian random variables. The canonical equation for C n in (29) becomes 1 m = (30) (1 ?c?czm)?z which upon rearranging yields the Stieltjes polynomial 2 czm ?(1 ?c?z)m+ 1 = 0. (31) 1 2 3 ? ? ? ? ?? ? ? ? 0 0.5 1 1.5 2 2.5 3 3.5 4 0 0.5 1.5 2.5 3.5 dF C /dx c=1 c=0.5 c=0.1 c=0.01 x Figure 4: The density of the (generalized) Wishart matrix {W n (c)} for di?erent values of c. Once again, (31) is a second degree polynomial in m whose coe?cients are polynomials in z. Hence, as before, (31) can be solved analytically to yield a solution for m in terms of z. The inversion formula in (5) can then be used to obtain the limiting density for C n . This is simply dF C (x) 1 = max 0, 1 ? δ(x) + (x ?b ? )(b + ?x) I [ b ? ,b + ] (32) dx c 2πxc where, as before, b ± = (1± √ c) 2 . As (32) suggests, the limiting density for C n depends only on the parameter c. Hence, for the remainder of this paper, we will use the notation {W(c)}to denote the (generalized)Wishart 1 ? matrix ensemble 4 de?ned as W(c) = N X n X with c = n/N > 0. n Figure 4 plots the density in (32) for di?erent values of c. From (32) the reader may notice that as c → i.e. for a ?xed n as N →∞, both the largest and the smallest eigenvalue, b + and b ? respectively, approach 1. This validates our intuition about the behavior of W(c) for a ?xed n as N → ∞. Additionally, from Figure 4, the reader may notice that the density gets increasingly more symmetrical about x = 1 as the value of c decreases. For c = 0.01, the density is almost perfectly symmetrical about x = 1. The reader may note that with an appropriate scaling and translation, the density of {W(c)} as c 0 could be made to resemble → the semi-circular distribution. In fact, in [14] Jonsson used this observation and the correspondence between the distribution in (32) and the generalized β-distribution to infer the moments of W n (c) from the even moments of the Wigner matrix which are incidentally the Catalan numbers denoted by C k for an integer k. More recently, Dumitriu recognized [15] that these moments could be written in terms of the (k, r) Narayana numbers [16] de?ned as N k,r = 1 k k ?1 (33) r + 1 r r so that the individual moments may be obtained from the moment generating function k?1 ? ?? ? k?1 r M k W (c) = c r N k,r = c k k ?1 (34) r r r=0 r=0 for which, it may be noted that M k W (1) = C k = M 2 S k are also the even moments of the standard Wigner matrix. 4 For notational convenience, when discussing in?nite (generalized) Wishart matrices we will simply refer to {W (c)} as the Wishart matrix even when the elements of X n are i.i.d. but not Gaussian. We will occasionally add a subscript such as W 1 (c) to di?erentiate between di?erent realizations of the ensemble {W (c)}. When discussing ?nite Wishart matrices, we will implicitly assume that the elements of X n are i.i.d. Gaussian. Its use in either manner will be obvious from the context. 0 ? 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 dF C /dx 0.1 0 ?1 0 1 2 3 4 5 6 x Figure 5: The density of C n with c = n/N = 0.1 and dH(τ) = 0.6δ(τ ?1)+ 0.4δ(τ ?3). The Wishart matrix {W(c)} has been studied exhaustively by statisticians and engineers. For in?nite Wishart matrices, (32) captures the limiting density and the extreme eigenvalues i.e. the region of support. The limiting moments are given by (34). As it was for the asymptotic Wigner matrix, the limiting density of the asymptotic Wishartmatrix did not depend on whether the elements of X n were real or complex. Similarly, as it was for the Gaussian ensembles, the analytical behavior of the ?nite Wishart matrices did indeed depend on whether the elements were real or complex. Nonetheless, the limiting moment and eigenvalue behavior could be inferred from the behavior of the ?nite (real or complex) Wishart matrix counterpart. The reader is directed towards some of the representative literature and the references therein on the distribution of the smallest [17], largest [18, 19, 20, 21], sorted [19, 22, 23], unsorted eigenvalues [19, 22, 23], and condition numbers [22, 23] of the Wishart matrix that invoke this link between the ?nite and in?nite Wishart matrix ensembles. We will now discuss sample covariance matrices for which the behavior of the limiting density can be best, if not solely, analyzed analytically using the Marˇcenko-Pastur theorem. 3.3 Additional examples of sample covariance matrices Suppose dH(τ) = pδ(τ ?λ 1 ) + (1 ?p)δ(τ ?λ 2 ) i.e. T n has an atomic mass of weight p at λ 1 and another atomic mass of weight (1 ?p) at λ 2 . The canonical equation in (29) becomes p 1 ?p m = + (35) λ 1 (1 ? cmz)?z λ 2 (1 ? cmz)?zc ? c ? which upon rearranging yields the Stieltjes polynomial 2 ? 2 λ 1 c 2 m 3 z 2 λ 2 + ? ?2λ 1 λ 2 cz + λ 1 cz 2 + 2λ 1 c 2 λ 2 z + λ 2 cz m 2 + λ 1 λ 2 + λ 2 cz + pλ 2 cz ?λ 1 z + λ 1 c 2 λ 2 + z ?λ 2 z + 2λ 1 cz ?pλ 1 cz ?2λ 1 λ 2 c ? m ?(pλ 2 + z ?pλ 1 c + λ 1 c ?λ 1 + pλ 2 c + pλ 1 ) = 0. (36) 1 1/2 ? 1/2 It can be readily veri?ed that if p = 1 and λ 1 = 1, then C n = N T n X n X n T n is simply the Wishart matrix we discussed above. Though it might not seem so from a cursory look, for p = 1 and λ 1 = 1, (36) can be shown after some elementary factorization to simplify to (31). Since (36) is a third degree polynomial in m it can conceivably be solved analytically using Cardano’s formula. For general c, p, λ 1 and λ 2 this is cumbersome and cannot be solved analytically as a function of z and c for arbitrary values of p, λ 1 , and λ 2 . However, for speci?c values of c, p, λ 1 , and λ 2 we can numerically solve 1 2 ? ? ? ? the resulting Stieltjes polynomial in (36). For example, when p = 0.6, λ 1 = 1 and λ 2 = 3, (36) simpli?es to 2 ? 11 11 3 2 2 2 2 3c 2 m z + ? 4cz 2 ?6cz + 6c z m + (3 ?4z ?6c + 31 cz + 3c + z )m + c + z ? = 0. (37) 5 5 5 For c = 0.1, (37) becomes 27 2 243 169 99 2 3 m 3 z 2 + ? 50 z + 2/5z 2 m + 100 ? 50 z + z m ? + z = 0 (38) 100 50 To determine the density from (38) we need to determine the roots of the polynomial in m and use the inversion formula in (5). Since we do not know the region of support for this density we would conjecture such a region and basically solve the polynomial above for every value of z. Using numerical tools such as the roots command in MATLAB this is not very di?cult. Figure 5 shows the excellent agreement between the theoretical density (solid line) obtained from numer ically solving (38) and the histogram of the eigenvalues of 1000 realizations of the matrix C n with n = 100 and N = n/c = 1000. Figure 6 shows the behavior of the density for a range of values of c. This ?gure captures our intuition that as c → 0, the eigenvalues of the sample covariance matrix C n will be increasingly localized about λ 1 = 1 and λ 2 = 3. By contrast, capturing this very same analytic behavior using ?nite RMT is not as straightforward. 0 1 2 3 4 5 6 7 8 9 10 0 0.5 1.5 2.5 x dF C /dx c=0.2 c=0.05 c=0.01 Figure 6: The density of C n with dH(τ) = 0.6δ(τ ?1)+ 0.4δ(τ ?3) for di?erent values of c Unlike the Wishart matrix, the distribution function (or level density) of ?nite dimensional covariance matrices, such as the C n we considered in this example, can only be expressed in terms of zonal or other multivariate orthogonal polynomials that appear frequently in texts such as [19]. Though these polynomials have been studied extensively by multivariate statisticians [24, 25, 26, 27, 28, 29, 30, 31] and more recently by combinatorists [32, 33, 34, 35, 36, 37] the prevailing consensus is that they are unwieldy and not particularly intuitive to work with. This is partly because of their de?nition as in?nite series expansions which makes their numerical evaluation a non-trivial task when dealing with matrices of moderate dimensions. More importantly, from an engineering point of view, the Stieltjes transform based approaches allows us to generate plots of the form in Figure 6 with the implicit assumption that the matrix in question is in?nite and yet, predict the behavior of the eigenvalues for the practical ?nite matrix counterpart with remarkable accuracy, as Figure 5 corroborates. This is the primary motivation for this course’s focus on developing in?nite random matrix theory. In the lectures that follow we will discuss other techniques that allow us to characterize a very broad class of in?nite random matrices that cannot be characterized using ?nite RMT. We will often be intrigued by and speculate on the link between these in?nite matrix ensembles and their ?nite matrix counterparts. We encourage you to ask us questions on this or to explore them further. 4 Exericses 1. Veri?ed that Silverstein’s sample covariance matrix theorem can be inferred directly from the Marˇcenko- Pastur theorem. Note: You will have to do some substitution tricks to get the parameter “c” to refer to the same quantity. 2. Derive the moments of the Wishart matrix from the observation that as c → 0, the density becomes “approximately” semi-circular. Hint: you will have to make an approximation for the region of support while remembering that for any a < 1, a 2 < a. There will also be a shifting and rescaling in this problem to get the terms to match up correctly. Recall that the moments of the Wishart matrix are expressed in terms of the Narayana polynomials in (34). 3. Come up with numerical code to compute the theoretical density when dH(τ) has three atomic masses (e.g. dH(τ) = 0.4δ(τ ?1)+ 0.4δ(τ ?3)+ 0.2δ(τ ?7)). Plot the limiting density as a function of x for a range of values of c. 4. Do the same when there are four atomic masses in dH(τ) (e.g. dH(τ) = 0.3δ(τ ?1)+ 0.25δ(τ ?3)+ 0.25δ(τ ? 7) + 0.25δ(τ ? 10)) . Verify that the solution obtained matches up with the simulations. Hints: Do all the roots match up? 5. What happens if there are atomic masses of negative weight in dH(τ) (e.g. dH(τ) = 0.5δ(τ + 1) + 0.5δ(τ ?1)). Does the limiting theoretical density line up with the experimental results? Check the assumptions of the Marˇcenko-Pastur theorem! Is this “allowed”? References [1] Sang II Choi and Jack W. Silverstein. Analysis of the limiting spectral distribution of large dimensional random matrices. volume 54(2), pages 295–309. 1995. [2] Boris A. Khoruzenkho, A.M. Khorunzhy, and L.A. Pastur. Asymptotic properties of large random matrices with independent entries. Journal of Mathematical Physics, 37:1–28, 1996. [3] L. Pastur. A simple approach to global regime of random matrix theory. In Mathematical results in statistical mechanics, Marseilles, 1998, pages 429–454. World Sci. Publishing, River Edge, NJ, 1999. [4] Madan Lal Mehta. Random Matrices. Academic Press, Boston, second edition, 1991. [5] M. Abramowitz and I.A. Stegun, editors. Handbook of Mathematical Functions. Dover Publications, New York, 1970. [6] N. I. Akhiezer. The classical moment problem and some related questions in analysis. Hafner Publishing Co., New York, New York, 1965. Translated by N. Kemmer. [7] A. M. Tulino and S. Verd′u. Random matrices and wireless communications. Foundations and Trends in Communications and Information Theory, 1(1), June 2004. [8] Eugene P. Wigner. Characteristic vectors of bordered matrices with in?nite dimensions. Annals of Math., 62:548–564, 1955. [9] V.A. Marˇcenko and L.A. Pastur. Distribution of eigenvalues for some sets of random matrices. Math USSR Sbornik, 1:457–483, 1967. [10] Jack W. Silverstein. Strong convergence of the empirical distribution of eigenvalues of large dimensional random matrices. Journal of Multivariate Analysis, 55(2):331–339, 1995. [11] Z. D. Bai and J. W. Silverstein. On the empirical distribution of eigenvalues of a class of large dimensional random matices. Journal of Multivariate Analysis, 54(2):175–192, 1995. [12] J. Wishart. The generalized product moment distribution in samples from a normal multivariate pop ulation. Biometrika, 20 A:32–52, 1928. [13] Ioana Dumitriu and Alan Edelman. Matrix Models for Beta Ensembles. Journal of Mathematical Physics, (11):5830–5847, November 2002. [14] Dag Jonsson. Some limit theorems for the eigenvalues of a sample covariance matrix. J. of Multivar. Anal., 12:1–38, 1982. [15] Ioana Dumitriu and Etienne Rassart. Path counting and random matrix theory. Electronic Journal of Combinatorics, 7(7), 2003. R-43. [16] Robert A. Sulanke. Re?nements of the Narayana numbers. Bull. Inst. Combin. Appl., 7:60–66, 1993. [17] Alan Edelman. The distribution and moments of the smallest eigenvalue of a random matrix of Wishart type. Lin. Alg. Appl., 159:55–80, 1991. [18] T. Sugiyama. On the distribution of the largest latent root of the covariance matrix. Annals of Math. Statistics, 38:1148–1151, 1967. [19] Robb J. Muirhead. Aspects of Multivariate Statistical Theory. John Wiley & Sons, New York, 1982. [20] Craig A. Tracy and Harold Widom. The Distribution of the Largest Eigenvalue in the Gaussian En sembles. In J.F. van Diejen and L.Vinet, editors, Calogero-Moser-Sutherland Models, CRM Series in Mathematical Physics, volume 4, pages 461–472. Springer-Verlag, Berlin, 2000. [21] Iain M. Johnstone. On the distribution of the largest eigenvalue in principal components analysis. Annals of Statistics, 29(2):295–327, 2001. [22] Alan Edelman. Eigenvalues and condition numbers of random matrices. SIAM J. on Matrix Analysis and Applications, 1988:543–560, 1988. [23] Alan Edelman. Eigenvalues and Condition Numbers of Random Matrices. PhD thesis, Massachusetts Institute of Technology, 1989. [24] Henry Jack. A class of symmetric polynomials with a parameter. Proc. R. Soc. Edinburgh, 69:1–18, 1970. [25] Zhimin Yan. Generalized hypergeometric functions and Laguerre polynomials in two variables. Contemp. Math., 138:239–259, 1992. [26] Zhimin Yan. A class of generalized hypergeometric functions in several variables. Canad. J. Math, 44:1317–1338, 1992. [27] P. Bleher and Alexander Its. Semiclassical asymptotics of orthogonal polynomials, Riemann-Hilbert problem, and the universality in the matrix model. Ann. of Math., 150:185–266, 1999. [28] Percy Deift, T. Kriecherbauer, K. McLaughlin, S. Venakides, and Xin Zhou. Uniform asymptotics for polynomials orthogonal with respect to varying exponential weights and applications to universality questions in random matrix theory. Comm. Pure Appl. Math., 52, 1999. [29] I.G. Macdonald. Symmetric Functions and Hall Polynomials. Oxford Mathematical Monographs. Oxford University Press, 2nd edition, 1998. [30] Kenneth I. Gross and Donald St. P. Richards. Special functions of matrix argument In: algebraic induction, zonal polynomials, and hypergeometric functions. Trans. American Math. Society, 301:781– 811, 1987. [31] Kenneth I. Gross and Donald St. P. Richards. Total positivity, spherical series, and hypergeometric functions of matrix argument. J. Approx. Theory, 59, no. 2:224–246, 1989. [32] Andrei Okounkov and Grigori Olshanski. Asymptotics of Jack polynomials as the number of variables goes to in?nity. IMRN, 13:641–682, 1998. [33] Luc Lapointe and Luc Vinet. A Rodrigues formula for the Jack polynomials and the Macdonald-Stanley conjecture. [34] F. Knop and S. Sahi. A recursion and a combinatorial formula for the Jack polynomials. Invent. Math., 128:9–22, 1997. [35] Friedrich Knop and Siddhartha Sahi. A recursion and a combinatorial formula for Jack polynomials. Inventiones Mathematicae, 128:9–22, 1997. [36] Richard P. Stanley. Some combinatorial properties of Jack symmetric functions. Adv. in Math., 77:76– 115, 1989. [37] Philip J. Hanlon, Richard P. Stanley, and John R. Stembridge. Some combinatorial aspects of the spectra of normally distributed random matrices. In Hypergeometric functions on domains of positivity, Jack polynomials, and applications (Tampa, FL, 1991), volume 138 of Contemp. Math., pages 151–174. Amer. Math. Soc., Providence, RI, 1992.