Press "Enter" to skip to content

20 search results for "circular law"

Three convex and compact sets of matrices

Matrix

This post is devoted to few convex and compact sets of matrices that I like.

The set \( {\mathcal{C}_n} \) of correlation matrices. A real \( {n\times n} \) matrix \( {C} \) is a correlation matrix when \( {C} \) is symmetric, semidefinite positive, with unit diagonal. This means that

\[ C_{ii}=1, \quad C_{ji}=C_{ji},\quad \left<x,Cx\right>\geq0 \]

for every \( {1\leq i,j\leq n} \) and for every \( {x\in\mathbb{R}^n} \). In particular, we have \( {C_{ij}=C_{ji}\in[-1,1]} \) for every \( {1\leq i,j\leq n} \). The set \( {\mathcal{C}_n} \) of all correlation matrices is convex and compact. It contains the identity matrix \( {I_n} \) but is not stable by the matrix product. However, it is stable by the Schur-Hadamard entrywise product! It is the intersection of the cone of symmetric positive semidefinite matrices \( {\mathcal{S}_n^+} \) with the affine subspace of equations \( {S_{11}=\cdots=S_{nn}=1} \). A closer look at \( {\mathcal{C}_3} \) gives, by simply computing the principal minors,

\[ \begin{pmatrix} 1 & a & c \\ a & 1 & b \\ c & b & 1 \end{pmatrix} \in\mathcal{C}_3 \quad\text{iff}\quad a,b,c\in[-1,1] \quad\text{and}\quad a^2+b^2+c^2\leq 1+2abc. \]

This shows the ellipsoidal geometry of \( {\mathcal{C}_n} \), coming from the spectral constraint, and related to the Schur complement. The set \( {\mathcal{C}_n} \) is not a polytope of \( {\mathbb{R}^{n\times n}} \) (i.e. is not the intersection of a finite collection of half spaces). Some authors use the name elliptope, an example of spectrahedron (set of matrices defined by linear matrix inequalities). The extremal points of \( {\mathcal{C}_n} \) were studied by Ycart while the facial structure was explored by Laurent and Poljak. A useful parameterization of \( {\mathcal{C}_n} \) using covariance graphs was developed by Kurowicka and Cooke.

The uniform probability measure on \( {\mathcal{C}_n} \) is the normalized trace of the Lebesgue measure. Its simulation was studied by many people, and one can take a look at the works of Joe and of Lewandowski, Kurowicka, and Joe, where the volume of \( {\mathcal{C}_n} \) is also computed in \( {\mathbb{R}^{n(n-1)/2}} \):

\[ \mathrm{Volume}(\mathcal{C}_n) = \pi^{(n^2-1)/4}\frac{\prod_{k=1}^{(n-1)/2}\Gamma(2k)}{2^{(n-1)^2/4}\Gamma^{n-1}((n+1)/2)} \]

if \( {n} \) is odd, while if \( {n} \) is even:

\[ \mathrm{Volume}(\mathcal{C}_n) = \pi^{n(n-2)/4}\frac{2^{(3n^2-4n)/4}\Gamma^n(n/2)\prod_{k=1}^{(n-2)/2}\Gamma(2k)}{\Gamma^{n-1}(n)}. \]

If \( {S} \) is a symmetric \( {n\times n} \) positive semidefinite matrix then the matrix \( {C} \) defined by

\[ C_{ij}=\frac{S_{ij}}{\sqrt{S_{ii}S_{jj}}} \]

for every \( {1\leq i,j\leq n} \) belongs to \( {\mathcal{C}_n} \). If \( {C} \) is a random element of \( {\mathcal{C}_n} \) following the uniform law, then it is known that the off-diagonal entries of \( {C} \), which are correlated, follow the same law, namely the Beta law of parameter \( {(n/2,n/2)} \) on \( {[-1,1]} \) (the density of the law of \( {C} \) is also computable using a covariance graph representation, leading to the volumetric formulas above). This allows to show that if \( {S} \) is the empirical covariance matrix of a standard Gaussian sample in \( {\mathbb{R}^n} \) then the random correlation matrix constructed from \( {S} \) (which is the empirical correlation matrix) does not follow the uniform law on \( {\mathcal{C}_n} \). One may ask whether or not the asymptotic spectral properties of a uniform random element of \( {\mathcal{C}_n} \), as \( {n\rightarrow\infty} \), are identical to the ones of Gaussian empirical covariance matrices (Marchenko-Pastur quarter circular law). I have not tested this numerically by simulation.

The set \( {\mathcal{M}_n} \) of stochastic matrices. A real \( {n\times n} \) matrix \( {M} \) is a stochastic matrix (we say also a Markov matrix) when all its entries are non-negative and all rows sum up to one. This means that \( {M_{ij}\geq0} \) and \( {M_{i1}+\cdots+M_{in}=1} \) for every \( {1\leq i,j\leq n} \). In particular, \( {M_{ij}\in[0,1]} \) for all \( {1\leq i,j\leq n} \), and every row belongs to the non-negative portion of the \( {\ell^1_n} \) unit sphere. The name Markov comes from the fact that such matrices are exactly the transition matrices of finite Markov chains on a state space of cardinal \( {n} \). The set \( {\mathcal{M}_n} \) of all \( {n\times n} \) Markov matrices is convex and compact. It is a polytope of \( {\mathbb{R}^{n\times n}} \) (i.e. intersection of half spaces) with \( {n(n-1)} \) degrees of freedom. The set \( {\mathcal{M}_n} \) contains the identity matrix \( {I_n} \) and is stable by matrix product (it is thus a semigroup for this product).

If \( {E} \) is a \( {n\times n} \) matrix with non-negative entries then the \( {n\times n} \) matrix \( {M} \), defined by

\[ M_{ij}=\frac{E_{ij}}{E_{i1}+\cdots+E_{in}} \]

for every \( {1\leq i,j\leq n} \), belongs to \( {\mathcal{M}_n} \). If the entries of \( {E} \) are i.i.d. exponential random variables then the Markov matrix \( {M} \) constructed from \( {E} \) follows the uniform law on \( {\mathcal{M}_n} \) which is the normalized trace of the Lebesgue measure. This kind of random matrices is called the Dirichlet Markov Ensemble since the rows of such random matrices are i.i.d. and follow the Dirichlet distribution with parameter \( {(1,\ldots,1)} \). Note that the entries of this matrix are identically distributed and follow a Beta law, and are correlated on each row and independent across rows. The law of large numbers gives \( {E_{i1}+\cdots+E_{in}=n(1+o(1))} \) and this suggests that the asymptotic spectral properties of such a random \( {M} \) as \( {n\rightarrow\infty} \) are identical to the ones of \( {E} \) (Marchenko-Pastur quarter circular law and Girko circular law), see cb-pc-dc.

Stochastic group. Let us consider the set of all \( {n\times n} \) real matrices such that \( {M} \) is invertible and \( {M_{i1}+\cdots+M_{in}=1} \) for all \( {1\leq i\leq n} \) (note that the entries of \( {M} \) are allowed to take negative values). This set is actually a group for the matrix product, sometimes called the stochastic group, and we refer to Poole for more details. This set is neither convex nor compact and I ignore what are its asymptotic spectral properties if equipped with a probability measure (notion of uniform law via constrained maximum entropy?).

The set \( {\mathcal{B}_n} \) of doubly stochastic matrices. A real \( {n\times n} \) matrix \( {B} \) is doubly stochastic (we say also bistochastic) if \( {B} \) and \( {B^\top} \) are both stochastic matrices. This means that \( {B_{i1}+\cdots+B_{in}=B_{i1}+\cdots+B_{in}=1} \) for any \( {1\leq i\leq n} \). In particular, \( {B_{ij}\in[0,1]} \) for every \( {1\leq i,j\leq n} \). The set \( {\mathcal{B}_n} \) is convex and compact, and forms a polytope of \( {\mathbb{R}^{n\times n}} \) with \( {(n-1)^2} \) degrees of freedom. It was shown by Canfield and McKay that in \( {\mathbb{R}^{(n-1)\times(n-1)}} \),

\[ \mathrm{Volume}(\mathcal{B}_n) =\frac{\exp\left(\frac{1}{3}+n^2+o(1)\right)}{(2\pi)^{n-1/2}n^{(n-1)^2}n^{n-1}}. \]

The Birkhoff polytope was remarkably studied by Barvinok, and a discrete version (contingency tables) by Barvinok and Hartigan.

The set \( {\mathcal{B}_n} \) contains the identity matrix and is stable by the matrix product (semigroup!). The matrix with all entries equal to \( {1/n} \) belongs to \( {\mathcal{B}_n} \) and is called sometimes the Wedderburn matrix. The van der Waerden conjecture, solved by Falikman, states that the Wedderburn matrix achieves the minimum of the permanent on \( {\mathcal{B}_n} \). The set \( {\mathcal{B}_n} \) is referred to as the Birkhoff polytope (that is why we use the notation \( {\mathcal{B}_n} \)). A celebrated theorem of Birkhoff and von Neumann states that \( {\mathcal{B}_n} \) is the convex envelope of permutation matrices. It can be shown, using the Minkowski-Carathéodory theorem, that each element of \( {\mathcal{B}_n} \) is the convex combination of at most \( {(n-1)^2+1} \) permutation matrices (which depend on the particular element). The set \( {\mathcal{B}_n} \) is also known as the assignment polytope or as the transportation polytope, since each element corresponds to a transportation map between \( {n} \) unit sources and \( {n} \) unit targets. One should not confuse \( {\mathcal{B}_n} \) with the permutahedron. The set \( {\mathcal{B}_n} \) plays a role in diverse areas and can be used for instance for the proof of the Hoffman-Wielandt inequality in matrix analysis.

The uniform law \( {\mathcal{L}_n} \) on \( {\mathcal{B}_n} \) is the normalized trace of the Lebesgue measure. The law \( {\mathcal{L}_n} \) has identical marginal laws, and is invariant by permutation of rows and of columns but is not exchangeable (i.e. invariant by any permutation of the entries). Let us consider the random walk on \( {\mathcal{B}_n} \) obtained at each step by selecting randomly two rows and two columns and transferring a random amount of mass between the corresponding four entries. This is a Markov chain which admits \( {\mathcal{L}_n} \) as an invariant law. Its speed of convergence was studied by Diaconis. More recently, Chatterjee, Diaconis, and Sly have shown that many asymptotic properties of random matrices drawn from \( {\mathcal{L}_n} \) are identical to the ones of random matrices with i.i.d. exponential entries. In particular, the entries are close to the exponential distribution of mean \( {1/n} \) and the Marchenko-Pastur quarter circular law holds true. It is conjectured that the Girko circular law is also true (we ignore how to adapt the Tao and Vu proof).

Unistochastic matrices. If \( {U} \) is \( {n\times n} \) unitary then the matrix \( {(|U_{ij}|^2)_{1\leq i,j\leq n}} \) belongs to \( {\mathcal{B}_n} \). Such matrices are sometimes called unistochastic by some physicists. However, it turns out that many elements of \( {\mathcal{B}_n} \) are not unistochastic.

Tridiagonal doubly stochastic matrices. The subset of tridiagonal elements of \( {\mathcal{B}_n} \) corresponds to birth and death processes on a finite state space of cardinal \( {n} \) which are symmetric with respect to the uniform law. The uniform distribution on this remarkable subset was studied by Diaconis and Wood.

Permutation matrices. Recall that \( {P} \) is an \( {n\times n} \) permutation matrix when there exists a permutation \( {\sigma} \) of \( {\{1,\ldots,n\}} \) such that \( {P_{ij}=\mathbf{1}_{i=\sigma(j)}} \) for every \( {1\leq i,j\leq n} \). The set \( {\mathcal{P}_n} \) of \( {n\times n} \) permutation matrices is the set of extremal points of the convex polytope \( {\mathcal{B}_n} \). The set \( {\mathcal{P}_n} \) is a finite sub-group of \( {\mathrm{GL}_n} \) homomorphic to the permutation group \( {\Sigma_n} \). The spectrum of a permutation matrix \( {P} \) associated to \( {\sigma\in\Sigma_n} \) is actually a very nice object which is related to its cycles decomposition. Namely, if \( {\sigma} \) has exactly \( {1\leq r\leq n} \) cycles, with lengths \( {\ell_1,\ldots,\ell_r} \), then \( {P} \) has the spectrum of the bloc diagonal matrix

\[ B_1\oplus\cdots\oplus B_r \]

where \( {B_k} \) is \( {\ell_k\times\ell_k} \) of the form (the cycle is a right shift on \( {\mathbb{Z}/\ell_k\mathbb{Z}} \))

\[ \begin{pmatrix} 0 & 1 & 0 & 0 & \cdots & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 1 \\ 1 & 0 & 0 & 0 & \cdots & 0 \end{pmatrix}. \]

The spectrum of \( {B_k} \) is given by the solutions of the equation \( {\lambda^{\ell(k)}=(-1)^{\ell(k)}} \) (roots of \( {\pm} \) unity). The spectrum of \( {P} \) is the union of the spectra of \( {B_1,\ldots,B_r} \). In particular, the spectrum of \( {P} \) is included in the unit circle \( {\{z\in\mathbb{C};|z|=1\}} \) and depends only on \( {c_1,\ldots,c_n} \) where \( {c_k} \) is the number of cycles of length \( {k} \) of \( {\sigma} \). Note that \( {c_1} \) is the number of fixed points of \( {\sigma} \), and \( {c_1+2c_2+\cdots+nc_n=n} \). Now if \( {P} \) is uniformly distributed on \( {\mathcal{P}_n} \) then \( {\sigma} \) is uniformly distributed on \( {\Sigma_n} \) and this allows to describe the spectrum of \( {P} \) via an Ewens distribution with parameter \( {\theta=1} \), which gives rise as \( {n\rightarrow\infty} \) to a Poisson-Dirichlet distribution. The spectrum of uniform permutation matrices was studied for instance by Wieand, by Hambly, Keevash, O’Connell, and Stark, and more recently by Ben Arous and Dang. We ignore how to exploit these results in order to study the spectrum of the element of \( {\mathcal{B}_n} \).

Note. I have learned the existence of the set of correlation matrices from Gérard Letac, an eclectic mind who was one of my teachers years ago.

5 Comments

Roots of random polynomials

Mark Kac

The Girko circular law theorem states that if \( {X} \) is a \( {n\times n} \) random matrix with independent and identically distributed entries (i.i.d) of variance \( {1/n} \) then the empirical measure

\[ \frac{1}{n}\sum_{i=1}^n\delta_{\lambda_i(X)} \]

made with the eigenvalues of \( {X} \), converges, as the dimension \( {n} \) tends to infinity, to the uniform law on the unit disk \( {\{z\in\mathbb{C}:|z|\leq1\}} \). This is to me the most beautiful spectral theorem in random matrix theory (well, I also like the Voiculescu asymptotic freeness theorem).

The random matrix \( {X} \) has i.i.d. entries and its eigenvalues are the roots of its characteristic polynomial. The coefficients of this random polynomial are neither independent nor identically distributed. Beyond random matrices, let us consider a random polynomial

\[ P(z)=a_0+a_1z+\cdots+a_nz^n \]

where \( {a_0,\ldots,a_n} \) are independent random variables. By analogy with random matrices, one may ask about the behavior as \( {n\rightarrow\infty} \) of the roots

\[ \lambda_1(P),\ldots,\lambda_n(P) \]

of \( {P} \) in \( {\mathbb{C}} \) and in particular the behavior of their empirical measure

\[ \frac{1}{n}\sum_{i=1}^n\delta_{\lambda_i(P)}. \]

The literature on this subject is quite rich and can be traced back to the works of Littlewood and Offord, Rice, and Kac. We refer to Shub and Smale, Azaïs and Wschebor, and Edelman and Kostlan (see also this paper) for (partial) reviews. As for random matrices, the case where the coefficients are real is more subtle due to the presence of real roots. Regarding the complex case, the zeros of Gaussian analytic functions is the subject of a recent monograph in connection with determinantal processes. Various cases are considered in the literature, including the following three families:

  • Kac polynomials, for which \( {(a_i)_{0\leq i\leq n}} \) are i.i.d.
  • Binomial polynomials, for which \( {a_i=\sqrt{\binom{n}{i}}b_i} \) for all \( {i} \) and \( {{(b_i)}_{0\leq i\leq n}} \) are i.i.d.
  • Weyl polynomials, for which \( {a_i=\frac{1}{\sqrt{i!}}b_i} \) for all \( {i} \) and \( {{(b_i)}_{0\leq i\leq n}} \) are i.i.d.

Geometrically, the complex number \( {z} \) is a root of \( {P} \) if and only if the vectors

\[ (1,z,\ldots,z^n) \quad\mbox{and}\quad (\overline{a_0},\overline{a_1},\ldots,\overline{a_n}) \]

are orthogonal in \( {\mathbb{C}^{n+1}} \), and this connects the problem to Littlewood-Offord type problems and small balls probabilities estimates, see this 1943 paper for instance.

Regarding Kac polynomials, Kac (see also the errata) has shown in the real Gaussian case that the asymptotic number of real roots is about \( {\frac{2}{\pi}\log(n)} \) as \( {n\rightarrow\infty} \). Kac obtained the same result when the coefficients are uniformly distributed. Hammersley derived an explicit formula for the \( {k} \)-point correlation of the roots of Kac polynomials. Shparo and Shur have shown that the empirical measure of the roots of Kac polynomials with light tailed coefficients tends as \( {n\rightarrow\infty} \) to the uniform law one the unit circle \( {\{z\in\mathbb{C}:|z|=1\}} \) (the arc law). If the coefficients are heavy tailed then the limiting law concentrates on the union of two centered circles, see Götze and Zaporozhets and references therein.

Regarding Weyl polynomials, various simulations and conjectures have been made, see e.g. Galligo and Emiris, Galligo, and Tsigaridas. For instance, if \( {(b_i)_{0\leq i\leq n}} \) are i.i.d. standard Gaussian, it was conjectured that the asymptotic behavior of the roots of the Weyl polynomials is analogous to the Ginibre Ensemble. Namely, the empirical distribution of the roots tends as \( {n\rightarrow\infty} \) to the uniform law on the centered disc of the complex plane (circular law), and moreover, in the real Gaussian case, there are about \( {\frac{2}{\pi}\sqrt{n}} \) real roots as \( {n\rightarrow\infty} \) and their empirical distribution tends as \( {n\rightarrow\infty} \) to a uniform law on an interval, as for the real Ginibre Ensemble. The complex Gaussian case was considered by Leboeuf and by Peres and Virág, while the real roots of the real Gaussian case were studied by Schehr and Majumdar. Beyond the Gaussian case, it is tempting to try the logarithmic potential approach with the companion matrix of \( {P} \). Recall that the companion matrix of the monic polynomial

\[ Q(z):=c_0+c_1z+\cdots+c_{n-1}z^{n-1}+z^n \]

is the \( {n\times n} \) matrix

\[ \begin{pmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1\\ -c_0 & -c_1 & -c_2 & \cdots & -c_{n-1}\\ \end{pmatrix}. \]

Its characteristic polynomial is \( {Q} \). Numerical simulations reveal strange phenomena depending on the law of the coefficients but we ignore it they are purely numerical. Note for instance that if the coefficients of \( {P} \) are all real positive then the roots cannot be real positive. The heavy tailed case is also of interest (rings?).

5 Comments

Changchun – Jilin province – China

Changchun
Changchun, Jilin province, People Republic of China

It is time for me to leave Changchun, after three very interesting weeks. I participated to a French-Chinese summer school on Random matrix theory and high dimensional statistics (July 10-30) organized by Zhidong Bai, Alice Guionnet, and Jianfeng Yao. The summer school took place in the campus of the Northeast Normal University (NENU). Most participants were French or Chinese speakers, except Jack W. Silverstein (so unique). My colleague Philippe Biane from Marne-la-Vallée was also there. It was the occasion to interact with Wembo Li, X.-D. Li, Tiefeng Jiang, Guangming Pan, and a bunch of young mathematicians. I gave with great pleasure a course around the circular law together with Charles Bordenave. Zhidong Bai worked on the circular law theorem during 13 years, see his interview by Atanu Biswas in 2006.

Dinner in Changchun during the France-China summer school 2011

There are very few tourists in Changchun, and the local people were happy to interact with foreigners, these so strange long-nose. The hospitality of the local organizers was also wonderful. Beyond slight cultural differences, I enjoyed very much my time, including in particular the food and the drinks, a bit less the incredible road traffic. I will also remember forever our visit to Changbaishan at the North Korean borders. Despite numerous problems China remains an impressive country with great vitality and potentialities.

Changchun - School of Marxism
Photo taken in the NENU campus by Hayat Cheballah

Related reading: rubrique Chine du Monde Diplomatique & Monde Diplomatique in Chinese.

Do you know these movies and writings? (ones of my favorites among others about China)

您好

Leave a Comment

Aspects of the Complex Ginibre Ensemble

Ginibre Ensemble 1000 x 1000
Ginibre Ensemble of size 1000 x 1000. GNU-R simulation courtesy of A. Hardy.

This post is devoted to the Complex Ginibre Ensemble, the subject of an expository talk that I gave few months ago. Let \( {(G_{i,j})_{i,j\geq1}} \) be an infinite table of i.i.d. random variables on \( {\mathbb{C}\equiv\mathbb{R}^2} \) with \( {G_{11}\sim\mathcal{N}(0,\frac{1}{2}I_2)} \). The Lebesgue density of the \( {n\times n} \) random matrix \( {\mathbf{G}=(G_{i,j})_{1\leq i,j\leq n}} \) in \( {\mathcal{M}_n(\mathbb{C})\equiv\mathbb{C}^{n\times n}} \) is

\[ \mathbf{A}\in\mathcal{M}_n(\mathbb{C}) \mapsto \pi^{-n^2}e^{-\sum_{i,j=1}^n|\mathbf{A}_{ij}|^2} = \pi^{-n^2}e^{-\mathrm{Tr}(\mathbf{A}\mathbf{A}^*)} \ \ \ \ \ (1) \]

where \( {\mathbf{A}^*} \) the conjugate-transpose of \( {\mathbf{A}} \). We say that \( {\mathbf{G}} \) belong to the Complex Ginibre Ensemble. This law is unitary invariant, in the sense that if \( {\mathbf{U}} \) and \( {\mathbf{V}} \) are \( {n\times n} \) unitary matrices then \( {\mathbf{U}\mathbf{G}\mathbf{V}} \) and \( {\mathbf{G}} \) are equally distributed. The entry-wise and matrix-wise real and imaginary parts of \( {\mathbf{G}} \) are independent and belong to the Gaussian Unitary Ensemble (GUE) of Gaussian random Hermitian matrices (the converse is also true).

The eigenvalues \( {\lambda_1(\mathbf{A}),\ldots,\lambda_n(\mathbf{A})} \) of a matrix \( {\mathbf{A}\in\mathcal{M}_n(\mathbb{C})} \) are the roots in \( {\mathbb{C}} \) of its characteristic polynomial \( {P_\mathbf{A}(z)=\det(\mathbf{A}-z\mathbf{I})} \), labeled so that \( {|\lambda_1(\mathbf{A})|\geq\cdots\geq|\lambda_n(\mathbf{A})|} \) with growing phases.

Lemma 1 (Diagonalizability) For every \( {n\geq1} \), the set of elements of \( {\mathcal{M}_n(\mathbb{C})} \) with multiple eigenvalues has zero Lebesgue measure in \( {\mathbb{C}^{n\times n}} \). In particular, the set of nondiagonalizable elements of \( {\mathcal{M}_n(\mathbb{C})} \) has zero Lebesgue measure in \( {\mathbb{C}^{n\times n}} \).

Proof: If \( {\mathbf{A}\in\mathcal{M}_n(\mathbb{C})} \) has characteristic polynomial

\[ P_\mathbf{A}(z)=z^n+a_{n-1}z^{n-1}+\cdots+a_0, \]

then \( {a_0,\ldots,a_{n-1}} \) are polynomials functions of \( {\mathbf{A}} \). The resultant \( {R(P_\mathbf{A},P’_\mathbf{A})} \) of \( {P_\mathbf{A},P’_\mathbf{A}} \), called the discriminant of \( {P_\mathbf{A}} \), is the determinant of the \( {(2n-1)\times(2n-1)} \) Sylvester matrix of \( {P_\mathbf{A},P’_\mathbf{A}} \). It is a polynomial in \( {a_0,\ldots,a_{n-1}} \). We have also the Vandermonde formula

\[ |R(P_\mathbf{A},P’_\mathbf{A})|=\prod_{i{<}j}|\lambda_i(\mathbf{A})-\lambda_j(\mathbf{A})|^2. \]

Consequently, \( {\mathbf{A}} \) has all eigenvalues distinct if and only if \( {\mathbf{A}} \) lies outside the polynomial hyper-surface \( {\{\mathbf{A}\in\mathbb{C}^{n\times n}:R(P_\mathbf{A},P’_\mathbf{A})=0\}} \). ☐

Since the law of \( {\mathbf{G}} \) is absolutely continuous, from lemma 1, we get that a.s. \( {\mathbf{G}\mathbf{G}^*\neq \mathbf{G}^*\mathbf{G}} \) (nonnormality) but \( {\mathbf{G}} \) is diagonalizable with distinct eigenvalues. Note that if \( {\mathbf{G}=\mathbf{U}\mathbf{T}\mathbf{U}^*} \) is the Schur unitary decomposition where \( {\mathbf{U}} \) is unitary and \( {\mathbf{T}} \) is upper triangular, then \( {\mathbf{T}=\mathbf{D}+\mathbf{N}} \) with \( {\mathbf{D}=\mathrm{diag}(\lambda_1(\mathbf{G}),\ldots,\lambda_n(\mathbf{G}))} \) and

\[ \mathrm{Tr}(\mathbf{G}\mathbf{G}^*) =\mathrm{Tr}(\mathbf{D}\mathbf{D}^*) +\mathrm{Tr}(\mathbf{N}\mathbf{N}^*). \]

Following Ginibre, one may compute the joint density of the eigenvalues by integrating (1) over the non spectral variables \( {\mathbf{U}} \) and \( {\mathbf{N}} \). The result is stated in Theorem 2 below. The law of \( {\mathbf{G}} \) is invariant by the multiplication of the entries with a common phase, and thus the law spectrum of \( {\mathbf{G}} \) is rotationally invariant in \( {\mathbb{C}^n} \). In the sequel we set

\[ \Delta_n:=\{(z_1,\ldots,z_n)\in\mathbb{C}^n:|z_1|\geq\cdots\geq|z_n|\}. \]

Theorem 2 (Spectrum law) \( {(\lambda_1(\mathbf{G}),\ldots,\lambda_n(\mathbf{G}))} \) has density \( {n!\varphi_n\mathbf{1}_{\Delta_n}} \) where

\[ \varphi_n(z_1,\ldots,z_n)=\frac{\pi^{-n}}{\prod_{k=1}^nk!} \exp\left(-\sum_{k=1}^n|z_k|^2\right)\prod_{1\leq i{<}j\leq n}|z_i-z_j|^2. \]

In particular, for every symmetric Borel function \( {F:\mathbb{C}^n\rightarrow\mathbb{R}} \),

\[ \mathbb{E}[F(\lambda_1(\mathbf{G}),\ldots,\lambda_n(\mathbf{G}))] =\int_{\mathbb{C}^n}\!F(z_1,\ldots,z_n)\varphi_n(z_1,\ldots,z_n)\,dz_1\cdots dz_n. \]

We will use Theorem 2 with symmetric functions of the form

\[ F(z_1,\ldots,z_n) =\sum_{i_1,\ldots,i_k \text{ distinct}}f(z_{i_1})\cdots f(z_{i_k}). \]

The Vandermonde determinant comes from the Jacobian of the diagonalization, and can be interpreted as an electrostatic repulsion. The spectrum is a Gaussian determinantal process. One may also take a look at the fourth chapter of the book by Hough, Krishnapur, Peres, and Virag for a generalization to zeros of Gaussian analytic functions. Theorem 2 is reported in chapter 15 of Mehta’s book. Ginibre considered additionally the case where \( {\mathbb{C}} \) is replaced by \( {\mathbb{R}} \) or by the quaternions. These two cases are less studied than the complex case, due to their peculiarities. For instance, for the real Gaussian case, and following Edelman (Corollary 7.2), the probability that the \( {n\times n} \) matrix has all its eigenvalues real is \( {2^{-n(n-1)/4}} \), see also Akemann and Kanzieper. The whole spectrum does not have a density in \( {\mathbb{C}^n} \) in this case!

Theorem 3 (\( {k} \)-points correlations) Let \( {z\in\mathbb{C}\mapsto\gamma(z)=\pi^{-1}e^{-|z|^2}} \) be the density of the standard Gaussian law \( {\mathcal{N}(0,\frac{1}{2}I_2)} \) on \( {\mathbb{C}} \). Then for every \( {1\leq k\leq n} \), the “\( {k} \)-point correlation”

\[ \varphi_{n,k}(z_1,\ldots,z_k) := \int_{\mathbb{C}^{n-k}}\!\varphi_n(z_1,\ldots,z_k)\,dz_{k+1}\cdots dz_n \]

satisfies to

\[ \varphi_{n,k}(z_1,\ldots,z_k) = \frac{(n-k)!}{n!}\gamma(z_1)\cdots\gamma(z_k) \det\left[K(z_i,z_j)\right]_{1\leq i,j\leq k} \]

where

\[ K(z_i,z_j) :=\sum_{\ell=0}^{n-1}\frac{(z_iz_j^*)^\ell}{\ell!} =\sum_{\ell=0}^{n-1}H_\ell(z_i)H_\ell(z_j)^* \quad\text{with}\quad H_\ell(z):=\frac{1}{\sqrt{\ell!}}z^\ell. \]

In particular, by taking \( {k=n} \) we get

\[ \varphi_{n,n}(z_1,\ldots,z_n) =\varphi_n(z_1,\ldots,z_n) =\frac{1}{n!}\gamma(z_1)\cdots\gamma(z_n)\det\left[K(z_i,z_j)\right]_{1\leq i,j\leq n}. \]

Proof: Calculations made by Mehta (chapter 15 page 271 equation 15.1.29) using

\[ \prod_{1\leq i{<}j\leq n}|z_i-z_j|^2 =\prod_{1\leq i{<}j\leq n}(z_i-z_j)\prod_{1\leq i{<}j\leq n}(z_i-z_j)^* \]

and

\[ \det\left[z_j^{i-1}\right]_{1\leq i,j\leq k}\det\left[(z_j^*)^{i-1}\right]_{1\leq i,j\leq k} =\frac{\prod_{j=1}^kj!}{n!}\det\left[K(z_i,z_j)\right]_{1\leq i,j\leq k}. \]

Recall that the empirical spectral distribution of an \( {n\times n} \) matrix \( {A} \) is given by

\[ \mu_\mathbf{A}:=\frac{1}{n}\sum_{k=1}^n\delta_{\lambda_k(\mathbf{A})}. \]

Theorem 4 (Mean Circular Law) For every continuous bounded function \( {f:\mathbb{C}\rightarrow\mathbb{R}} \),

\[ \lim_{n\rightarrow\infty}\mathbb{E}\left[\int\!f\,d\mu_{\frac{1}{\sqrt{n}}\mathbf{G}}\right] =\pi^{-1}\int_{|z|\leq 1}\!f(z)\,dxdy. \]

Proof: From Theorem 3, with \( {k=1} \), we get that the density of \( {\mathbb{E}\mu_{\mathbf{G}}} \) is

\[ \varphi_{n,1}: z\mapsto \gamma(z)\left(\frac{1}{n}\sum_{\ell=0}^{n-1}|H_\ell|^2(z)\right) =\frac{1}{n\pi}e^{-|z|^2}\sum_{\ell=0}^{n-1}\frac{|z|^{2\ell}}{\ell!}. \]

Following Mehta (chapter 15 page 272), by elementary calculus, for every compact \( {C\subset\mathbb{C}} \),

\[ \lim_{n\rightarrow\infty}\sup_{z\in C} \left|n\varphi_{n,1}(\sqrt{n}z)-\pi^{-1}\mathbf{1}_{[0,1]}(|z|)\right|=0. \]

The \( {n} \) in front of \( {\varphi_{n,1}} \) is due to the fact that we are on the complex plane \( {\mathbb{C}=\mathbb{R}^2} \) and thus \( {d\sqrt{n}xd\sqrt{n}y=ndxdy} \). Here is the start of the elementary calculus: for \( {r^2<n} \),

\[ e^{r^2}-\sum_{\ell=0}^{n-1}\frac{r^{2\ell}}{\ell!} =\sum_{\ell=n}^\infty\frac{r^{2\ell}}{\ell!} \leq \frac{r^{2n}}{n!}\sum_{\ell=0}^\infty\frac{r^{2\ell}}{(n+1)^\ell} =\frac{r^{2n}}{n!}\frac{n+1}{n+1-r^2} \]

while for \( {r^2>n} \),

\[ \sum_{\ell=0}^{n-1}\frac{r^{2\ell}}{\ell!} \leq\frac{r^{2(n-1)}}{(n-1)!}\sum_{\ell=0}^{n-1}\left(\frac{n-1}{r^2}\right)^\ell \leq \frac{r^{2(n-1)}}{(n-1)!}\frac{r^2}{r^2-n+1}. \]

This leads to the result by taking \( {r^2:=|\sqrt{n}z|^2} \). ☐

The real Gaussian version of Theorem 4 was established by Edelman (theorem 6.3). The sequence \( {(H_k)_{k\in\mathbb{N}}} \) forms an orthonormal basis of square integrable analytic functions on \( {\mathbb{C}} \) for the standard Gaussian on \( {\mathbb{C}} \). The uniform law on the unit disc (known as the circular law) is the law of \( {\sqrt{V}e^{2i\pi W}} \) where \( {V} \) and \( {W} \) are i.i.d. uniform random variables on the \( {[0,1]} \). Ledoux makes use of this point of view for his interpolation between complex Ginibre and GUE via the Girko elliptic laws (see also Johansson).

Theorem 5 (Strong Circular Law) Almost surely, for all continuous bounded \( {f:\mathbb{C}\rightarrow\mathbb{R}} \),

\[ \lim_{n\rightarrow\infty}\int\!f\,d\mu_{\frac{1}{\sqrt{n}}\mathbf{G}} = \pi^{-1}\int_{|z|\leq 1}\!f(z)\,dxdy. \]

Proof: We reproduce Silverstein’s argument, published by Hwang. The argument is similar to the proof of the strong law of large numbers for i.i.d. random variables with finite fourth moment. It suffices to establish the result for compactly supported continuous bounded functions. Let us pick such a function \( {f} \) and set

\[ S_n:=\int_{\mathbb{C}}\!f\,d\mu_{\frac{1}{\sqrt{n}}\mathbf{G}} \quad\text{and}\quad S_\infty:=\pi^{-1}\int_{|z|\leq 1}\!f(z)\,dxdy. \]

Suppose for now that we have

\[ \mathbb{E}[\left(S_n-\mathbb{E} S_n\right)^4]=O(n^{-2}). \ \ \ \ \ (2) \]

By monotone convergence,

\[ \mathbb{E}\sum_{n=1}^\infty\left(S_n-\mathbb{E} S_n\right)^4 =\sum_{n=1}^\infty\mathbb{E}[\left(S_n-\mathbb{E} S_n\right)^4]<\infty \]

and consequently \( {\sum_{n=1}^\infty\left(S_n-\mathbb{E} S_n\right)^4<\infty} \) a.s. which implies \( {\lim_{n\rightarrow\infty}S_n-\mathbb{E} S_n=0} \) a.s. Since \( {\lim_{n\rightarrow\infty}\mathbb{E} S_n=S_\infty} \) by theorem 4, we get \( {\lim_{n\rightarrow\infty}S_n=S_\infty} \) a.s. Finally, one can swap the universal quantifiers on \( {\omega} \) and \( {f} \) thanks to the separability of \( {\mathcal{C}_c(\mathbb{C},\mathbb{R})} \). To establish (2), we set

\[ S_n-\mathbb{E} S_n=\frac{1}{n}\sum_{i=1}^nZ_i \quad\text{with}\quad Z_i:=f\left(\lambda_i\left(\frac{1}{\sqrt{n}}\mathbf{G}\right)\right). \]

Next, we obtain, with \( {\sum_{i_1,\ldots}} \) running over distinct indices in \( {1,\ldots,n} \),

\[ \mathbb{E}\left[\left(S_n-\mathbb{E} S_n\right)^4\right] =\frac{1}{n^4}\sum_{i_1}\mathbb{E}[Z_{i_1}^4] \]

\[ +\frac{4}{n^4}\sum_{i_1,i_2}\mathbb{E}[Z_{i_1}Z_{i_2}^3] \]

\[ +\frac{3}{n^4}\sum_{i_1,i_2}\mathbb{E}[Z_{i_1}^2Z_{i_2}^2] \]

\[ +\frac{6}{n^4}\sum_{i_1,i_2,i_3}\mathbb{E}[Z_{i_1}Z_{i_2}Z_{i_3}^2] \]

\[ +\frac{1}{n^4}\sum_{i_1,i_2,i_3,i_3,i_4}\!\!\!\!\!\!\mathbb{E}[Z_{i_1}Z_{i_3}Z_{i_3}Z_{i_4}]. \]

The first three terms of the right hand side are \( {O(n^{-2})} \) since \( {\max_{1\leq i\leq n}|Z_i|\leq\Vert f\Vert_\infty} \). Finally, some calculus using the expressions of \( {\varphi_{n,3}} \) and \( {\varphi_{n,4}} \) provided by Theorem 3 allows to show that the remaining two terms are also \( {O(n^{-2})} \). See Hwang (page 151). ☐

Following Kostlan, the integration of the phases in the joint density of the spectrum given by Theorem 2 leads to theorem 6 below. See also Rider and the book by Hough, Krishnapur, Peres, and Virag for a generalization to determinental processes.

Theorem 6 (Layers) If \( {Z_{1},\ldots,Z_{n}} \) are independent with \( {Z_k^2\sim\Gamma(k,1)} \) for every \( {k} \), then

\[ \left\{|\lambda_1(\mathbf{G})|,\ldots,|\lambda_n(\mathbf{G})|\right\} \overset{d}{=} \left\{Z_{1},\ldots,Z_{n}\right\}. \]

Note that \( {(\sqrt{2}Z_k)^2\sim\chi^2(2k)} \) which is useful for \( {\sqrt{2}\mathbf{G}} \). Since \( {Z_k^2\overset{d}{=}E_1+\cdots+E_k} \) where \( {E_1,\ldots,E_k} \) are i.i.d. exponential random variables of unit mean, we get, for every \( {r>0} \),

\[ \mathbb{P}\left(\rho(\mathbf{G})\leq \sqrt{n}r\right) =\prod_{1\leq k\leq n}\mathbb{P}\left(\frac{E_1+\cdots+E_k}{n}\leq r^2\right) \]

where \( {\rho(\mathbf{G})=\max_{1\leq i\leq n}|\lambda_i(\mathbf{G})|=|\lambda_1(\mathbf{G})|} \) is the spectral radius of \( {\mathbf{G}} \).

The law of large numbers suggests that \( {r=1} \) is a critical value. The central limit theorem suggests that \( {n^{-1/2}\rho(\mathbf{G})} \) behaves when \( {n\gg1} \) as the maximum of a standard Gaussian i.i.d sample, for which the fluctuations follow the Gumbel law. A quantitative central limit theorem and the Borel-Cantelli lemma provides the follow result. The full proof is in Rider.

Theorem 7 (Convergence and fluctuation of the spectral radius)

\[ \mathbb{P}\left(\lim_{n\rightarrow\infty}\frac{1}{\sqrt{n}}\rho(\mathbf{G})=1\right)=1. \]

Moreover, if \( {\gamma_n:=\log(n/2\pi)-2\log(\log(n))} \) then

\[ \sqrt{4n\gamma_n} \left(\frac{1}{\sqrt{n}}\rho(\mathbf{G})-1-\sqrt{\frac{\gamma_n}{4n}}\right) \overset{d}{\underset{n\rightarrow\infty}{\longrightarrow}} \mathcal{G}. \]

where \( {\mathcal{G}} \) is the Gumbel law with cumulative distribution function \( {x\mapsto e^{-e^{-x}}} \) on \( {\mathbb{R}} \).

The convergence of the spectral radius was obtained by Mehta (chapter 15 page 271 equation 15.1.27) by integrating the joint density of the spectrum of Theorem 2 over the set \( {\bigcap_{1\leq i\leq n}\{|\lambda_i|>r\}} \). The same argument is reproduced by Hwang (pages 149-150). Let us give now an alternative derivation of Theorem 4. From Theorem 7, the sequence \( {(\mathbb{E}\mu_{n^{-1/2}\mathbf{G}})_{n\geq1}} \) is tight and every adherence value \( {\mu} \) is supported in the unit disc. From Theorem 2, such a \( {\mu} \) is rotationally invariant, and from Theorem 6, the image of \( {\mu} \) by \( {z\in\mathbb{C}\mapsto|z|} \) has density \( {r\mapsto 2r\mathbf{1}_{[0,1]}(r)} \) (use moments!). Theorem 4 follows immediately.

Note that the recent book of Forrester contains many computations for the Ginibre Ensemble. See also the chapter by Khoruzhenko and Sommers in the Oxford Handbook of Random Matrices.

Photo of Jean Ginibre
Jean Ginibre – Mathematical physicist
5 Comments

Can't find what you're looking for? Try refining your search:

Syntax · Style · .