Semicircular law with a few independent entries in a random matrix

Technical Summary: Semicircular Law with a Few Independent Entries in a Random Matrix

Problem Statement
In random matrix theory, a fundamental distinction has traditionally been drawn between Wigner matrices and other "patterned" matrices (such as Toeplitz, Hankel, symmetric circulant, and reverse circulant matrices). Wigner matrices, constructed from $O(n^2)$ independent random variables, are known to have a limiting spectral distribution (LSD) that converges to the semicircular law. Conversely, patterned matrices, which rely on only $O(n)$ independent random variables, typically exhibit limiting spectral distributions with unbounded supports.

The central question motivating this work, originally posed by Prof. Arup Bose, is whether the unbounded support of the LSD is an intrinsic consequence of having only $O(n)$ independent entries, or if it arises specifically from the repetitive structural patterns (e.g., variables repeating along diagonals or cross-diagonals) inherent in Toeplitz and Hankel matrices. The authors investigate whether it is possible to construct matrices with only $O(n)$ independent random variables that nonetheless converge to the semicircular law.

Methodology and Model Construction
The authors propose a novel random matrix model, $X_n$, designed to utilize $O(n)$ independent random variables while disrupting the repetitive structures found in traditional patterned matrices.

1. Underlying Variables: Let $\xi_1, \dots, \xi_n$ be $n$ independent random variables with mean 0, variance 1, and finite moments of all orders.
2. Permutation Mechanism: Let $S_n$ be the set of bijections (permutations) on $[n]$. The authors introduce $n$ independent and identically distributed (i.i.d.) random permutations $\Phi_1, \dots, \Phi_n$, each sampled uniformly from $S_n$.
3. Matrix Entry Definition: The entries of an intermediate matrix $Y$ are defined by permuting the underlying variables: $Y_{ij} = \xi_{\Phi_i(j)}$.
4. Symmetrization: The final $n \times n$ symmetric random matrix $X_n$ is constructed as:
   $$X_{ij} = \frac{1}{\sqrt{2}}(Y_{ij} + Y_{ji}) = \frac{1}{\sqrt{2}}(\xi_{\Phi_i(j)} + \xi_{\Phi_j(i)})$$
5. Scaling: To analyze the spectrum, the matrix is rescaled by $\sqrt{n}$ to form $\tilde{X}_n = \frac{1}{\sqrt{n}}X_n$.

The authors verify that the entries of $X_n$ are centered and calculate their covariances. Notably, the variance of the diagonal entries is approximately 2, while off-diagonal entries have variance approximately $1 + 1/n$. The trace of the squared matrix scales such that $\lim_{n \to \infty} \frac{1}{n^2} \mathbb{E}[\text{Tr}(X_n^2)] = 1$, consistent with the normalization required for the standard semicircular law.

Key Results
The primary result, stated in Theorem 4.1, establishes that if the underlying variables $\xi_i$ have finite moments of all orders, the empirical spectral distribution (ESD) of $\tilde{X}_n$ converges weakly in probability to the standard semicircular law.

• Convergence Metric: The convergence is measured using the bounded-Lipschitz distance ($d_{BL}$), which metrizes the topology of weak convergence.
• Conditional Convergence (Corollary 4.1): The authors further demonstrate that this convergence holds conditionally for "most" realizations of the permutations. Specifically, for any $\epsilon, \delta, \eta > 0$, there exists a set of permutation sequences $A_n \subseteq S_n^{\otimes n}$ with measure greater than $(1-\eta)(n!)^n$ such that, conditioned on the permutations belonging to $A_n$, the distance between the ESD and the semicircular law is less than $\epsilon$ with probability at least $1-\delta$.

Proof Strategy
The proof relies on the method of moments, specifically invoking Theorem 5 from a prior work by [WHW16]. The authors must verify two conditions for the moments of the matrix entries:

1. Moment Bounds: For distinct indices, the expectation of products of matrix entries must be bounded by $C_{pq} n^{-p/2}$. This is achieved by analyzing the probability that the indices of the underlying permutations form a "matched" partition (where every element appears at least twice). The randomness of the permutations ensures that the probability of such matches decays sufficiently fast as $n \to \infty$.
2. Limit of Moments: The expectation of the product of squared entries must converge to 1. The authors show that the probability of "collisions" (where distinct indices map to the same underlying variable) is $O(1/n)$, which vanishes in the limit, leaving the dominant term to converge to the required value.

Significance and Claims
The paper claims to resolve the question of whether $O(n)$ independent entries inherently prevent the emergence of the semicircular law. The authors conclude that the unbounded support observed in Toeplitz and Hankel matrices is not a consequence of the low number of independent variables ($O(n)$), but rather a result of the intrinsic repetitive patterns of those matrices (where the same random variables appear along parallel diagonals).

By destroying these repetitive structures through random permutations while maintaining the $O(n)$ count of independent variables, the authors demonstrate that the empirical spectral distribution can be made arbitrarily close to the semicircular law. This finding suggests that the "few independent entries" constraint is not the fundamental barrier to semicircularity; rather, the specific algebraic structure of the repetition is the critical factor.

Empirical Validation
The theoretical results are supported by simulations (Section 5) where the authors generate the matrix $\tilde{X}_n$ for $n=2000$ using standard normal variables. The resulting histogram of eigenvalues aligns perfectly with the density of the standard semicircular law, visually confirming the theoretical convergence.