Noncrossing partitions, Catalan words, and the semicircle law (Q354756)

The authors study the distribution of eigenvalues of random patterned matrices of the following type. For every \(n\in \mathbb N\) let \(L_n:\{1,\ldots,n\}^2 \to \mathbb N_0^d\) be a function (called a link function) such that \(L_{n+1}(i,j) = L_n(i,j)\) whenever \(1\leq i,j \leq n\). Let \(\{x_k: k\in \mathbb N_0^d\}\) be independent random variables (called the input variables). The authors study random matrices of the form \[ A_n = (x_{L_n(i,j)})_{i,j=1}^n. \] For example, taking \(L_n(i,j) = (\text{min} (i,j), \text{max}(i,j))\), one obtains random symmetric matrices (that is, Wigner matrices). This framework includes also random Toeplitz, Hankel, reverse and symmetric circulant matrices as special cases. To study the limiting distribution of the eigenvalues of \(n^{-1/2} A_n\) it is natural to use the method of moments, that is to compute the large \(n\) limit of \(n^{-d/2}\text{Tr} (A_n^d)\), for every \(d\in\mathbb N\). This amounts to taking sums over certain combinatorial structures, called words. In the Wigner case it is known that only so-called Catalan words contribute to the moments of the limit (and each Catalan word contributes exactly \(1\)). Hence, the moments of the limiting eigenvalue distribution coincide with the number of Catalan words of length \(d\). This leads to the Wigner semicircle law. The paper studies the general framework of patterned random matrices and the main questions addressed in the paper are: 1) Under what conditions non-Catalan words do not contribute to the moments? 2) When does each Catalan word contributes at least \(1\) (with possible contributions from non-Catalan words)? 3) When does each Catalan word contributes exactly \(1\)? One of the results of the paper shows that under some general conditions the Wigner semicircle law serves as a ``lower bound'' in the sense that all moments of the limiting eigenvalue distribution are larger than the moments of the Wigner law.