Fixed-degree covariance trace moments and independent edge witnesses

First replace $\xi$ by any bounded centered real iid entry $\eta$, of variance $v\ge 0$. For a fixed integer $k\ge 1$, set $T_{n,k}=\frac{1}{n}\mathrm{Tr}{\left(\frac{Y_n{Y}_n^T}{n}\right)}^k=\frac{1}{n^{k+1}}{\sum }_{i_1,\dots ,i_k\le n}{\sum }_{j_1,\dots ,j_k\le p_n}{\prod }_{\mathrm{\ell }=1}^k{\eta }_{i_{\mathrm{\ell }}{j}_{\mathrm{\ell }}}{\eta }_{i_{\mathrm{\ell }+1}{j}_{\mathrm{\ell }}},i_{k+1}=i_1\mathrm{.}$

Each summand is a length-$2k$ closed alternating walk on a bipartite graph: row labels and column labels are disjoint vertex types, and each distinct pair $(i,j)$ is an edge. Its graph is connected. An edge occurring once makes its expectation zero, by centering and independence. Every surviving walk therefore has at most $k$ distinct edges and at most $k+1$ vertices. There are finitely many equality patterns of the $2k$ vertex positions, with a bound depending only on $k$. A pattern with $r$ row and $s$ column vertices has exactly $(n{)}_r(p_n{)}_s$ injective labelings, and its summand expectations are uniformly bounded. Consequently, every pattern with $r+s\le k$ contributes $O(n^{-1})$ after normalization.

A pattern with $k+1$ vertices has exactly $k$ edges, its graph is a tree, and every edge is traversed exactly twice. The closed walk traverses each tree edge once in each direction. The order in which it first enters the children of each vertex makes this tree a rooted ordered tree, rooted at a row vertex. Conversely the contour walk of every such ordered tree supplies exactly one canonical equality pattern. This is a bijection: on a tree an edge cannot be left behind before its whole descendant excursion is completed, since that would force a third traversal. If the tree has $s$ odd-depth (column) vertices, its limiting labeling weight is ${\gamma }^s$, and its expectation is $v^k$.

For completeness, the tree count can be extracted without any random-matrix theorem. Let $R(z)$ count ordered trees rooted at a row, with an edge contributing $z$ and each column vertex contributing $\gamma$. Let $C(z)$ count column-rooted trees with the same weights, including the root-column weight. The ordered list of subtrees gives, as formal power series, $R=\frac{1}{1-zC},C=\frac{\gamma }{1-zR}\mathrm{.}$

Writing $H=R-1$, these equations give $C=\gamma +H$ and $H=z(1+H)(\gamma +H)\mathrm{.}$

The formal coefficient identity for $H=z\mathrm{\Phi }(H)$ is $[z^k]H=\frac{1}{k}[u^{k-1}]\mathrm{\Phi }(u{)}^k\mathrm{.}$

One direct verification uses formal residues: substitute $z=u\mathrm{/}\mathrm{\Phi }(u)$ into $\mathrm{Res}H(z)z^{-k-1}dz$. The resulting residue is $\mathrm{Res}(u^{-k}{\mathrm{\Phi }}^k-u^{-k+1}{\mathrm{\Phi }}^{k-1}{\mathrm{\Phi }}^{\mathrm{\prime }})du$; the second coefficient is $(k-1)\mathrm{/}k$ times the first, by differentiating ${\mathrm{\Phi }}^k$. This proves the identity, including $k=1$. Applying it gives ${\mu }_k(\gamma )=[z^k]H={\sum }_{s=1}^k\frac{1}{k}\left(\genfrac{}{}{0px}{}{k}{s}\right)\left(\genfrac{}{}{0px}{}{k}{s-1}\right){\gamma }^s\mathrm{.}$

Thus $E{T}_{n,k}⟶v^k{\mu }_k(\gamma )\mathrm{.}$ This explicitly counts all leading patterns, and the argument above bounds all nonleading patterns. It does not assume a spectral limit.

For a label assignment $w$, let $M_w$ be its walk monomial and $Z_w=M_w-E{M}_w$. Expand the fourth centered moment as a sum of $E(Z_{w_1}{Z}_{w_2}{Z}_{w_3}{Z}_{w_4})$, with normalization $n^{-4k-4}$.

Join two of the four walks when their sets of matrix entries share an edge. A walk isolated in this graph is independent of the other three monomials, so its centered factor makes the expectation zero. Therefore every surviving configuration has at most two clusters of walks. Each cluster has a connected union graph because its walks are individually connected and consecutive walks in the cluster share an edge.

Moreover, no matrix-entry edge can occur just once in the total $8k$ factors. Indeed, if that edge occurs in $M_{w_t}$, then $E{M}_{w_t}=0$, so $Z_{w_t}=M_{w_t}$, and conditioning on all other entries makes the expectation zero. Thus a surviving configuration has at most $4k$ distinct edges. Its number of distinct vertices is at most the sum over its clusters of (edges plus one), hence at most $4k+2$. Sharing vertices between different edge-clusters only reduces this bound.

There are finitely many patterns at this fixed $k$. Bounded entries bound every centered product expectation by a constant depending only on $k$ and the entry bound. With $p_n=O(n)$, the count of labelings is $O(n^{4k+2})$. Therefore $E\mathrm{\mid }{T}_{n,k}-E{T}_{n,k}{\mathrm{\mid }}^4=O(n^{-2})\mathrm{.}$

Markov's inequality and the first Borel–Cantelli lemma show $T_{n,k}-E{T}_{n,k}\to 0$ almost surely. Intersecting over all integer $k\ge 1$ proves simultaneous fixed-degree trace convergence for bounded entries. Neither independence between different $n$ nor a monotone sequence $p_n$ was assumed.

Rectangular strong law. For every integrable iid nonnegative array $Z_{ij}$, $\frac{1}{n^2}{\sum }_{i\le n,j\le p_n}{Z}_{ij}⟶\gamma EZ\text{almost surely}\mathrm{.}$

To prove this, for each positive rational $t$ enumerate the cells of the nested rectangles $[m]\times [\lfloor tm\rfloor ]$ in their successive increments. This is an enumeration of the whole quadrant, so the ordinary one-dimensional iid strong law applies at the rectangle cardinalities. It gives the limit $tEZ$ after division by $m^2$. Intersect these probability-one events over rational $t$. Bracket $p_n\mathrm{/}n$ between rationals $t_{-}<\gamma <t_{+}$ and use nonnegativity, then let $t_{\pm }\to \gamma$. This proof accommodates arbitrary $p_n\mathrm{/}n\to \gamma$.

Singular-value comparison. For two real rectangular matrices $A,B$ of the same dimensions, pad their ordered singular-value lists with zeros to length $n$ when forming $A{A}^T,B{B}^T$. Then ${\sum }_{i=1}^n(s_i(A)-s_i(B){)}^2\le \mathrm{\parallel }A-B{\mathrm{\parallel }}_F^2\mathrm{.}$ Here is an elementary proof of the underlying comparison. For symmetric matrices $U,V$ of dimension $d$ with ordered eigenvalues $\alpha ,\beta$, orthogonal diagonalization expresses $\mathrm{Tr}(UV)$ as ${\sum }_{ij}{\alpha }_i{\beta }_j{d}_{ij}$, where $d_{ij}$ is the square of an orthogonal overlap and its row and column sums are one. For descending real sequences, this sum is at most ${\sum }_i{\alpha }_i{\beta }_i$: set $c_i={\sum }_j{d}_{ij}{\beta }_j$; the sum of its first $r$ entries is at most the sum of the first $r$ entries of $\beta$, because the associated column weights lie in $[0,1]$ and sum to $r$. Summation by parts against descending $\alpha$, with equal total sums, proves the assertion. Expanding $\mathrm{Tr}(U-V{)}^2$ now bounds it below by ${\sum }_i({\alpha }_i-{\beta }_i{)}^2$. Apply this result to the symmetric dilations $\left(\begin{array}{cc}0& A\\ A^T& 0\end{array}\right),\left(\begin{array}{cc}0& B\\ B^T& 0\end{array}\right)\mathrm{.}$

Their eigenvalues are the singular values, their negatives, and the required zeros. Both sides acquire a factor two, proving the comparison.

For $k\ge 1$, the scalar factorization and Cauchy–Schwarz consequently give $\mid \frac{1}{n}{\sum }_i{s}_i^{2k}-\frac{1}{n}{\sum }_i{t}_i^{2k}\mid \le 2k{\left(\frac{\mathrm{\parallel }A-B{\mathrm{\parallel }}_F^2}{n}\right)}^{1\mathrm{/}2}{[\frac{2}{n}{\sum }_i(s_i^{4k-2}+t_i^{4k-2})]}^{1\mathrm{/}2}\mathrm{.}$ Indeed $\mathrm{\mid }{s}^{2k}-t^{2k}\mathrm{\mid }\le 2k\mathrm{\mid }s-t\mathrm{\mid }(s^{2k-1}+t^{2k-1})$ for nonnegative $s,t$; squaring the last parenthesis is bounded by twice the sum of the squares. This inequality needs no operator-norm bound on $B$.

For integer $K\ge 1$, put $m_K=E[\xi {\mathbf{1}}_{\mathrm{\mid }\xi \mathrm{\mid }\le K}],{\eta }^{(K)}=\xi {\mathbf{1}}_{\mathrm{\mid }\xi \mathrm{\mid }\le K}-m_K,v_K=E({\eta }^{(K)}{)}^2\mathrm{.}$

Then $0\le v_K\le 1$ and $v_K\to 1$. The residual $r_K=\xi -{\eta }^{(K)}$ has second moment ${\delta }_K^2=E{r}_K^2=E[{\xi }^2{\mathbf{1}}_{\mathrm{\mid }\xi \mathrm{\mid }>K}]-m_K^2⟶0.$

Let $B_n^{(K)}$ be the normalized matrix of these bounded centered entries, constructed from the same original array. On one probability-one event, phases 1–2 give for every integer $K$ and every integer $j\ge 1$ $\frac{1}{n}\mathrm{Tr}(B_n^{(K)}{B}_n^{(K)T}{)}^j⟶v_K^j{\mu }_j(\gamma )\mathrm{.}$

The rectangular strong law, applied to $r_K^2$, also gives simultaneously in $K$ $\frac{1}{n}\mathrm{\parallel }{A}_n-B_n^{(K)}{\mathrm{\parallel }}_F^2⟶\gamma {\delta }_K^2\mathrm{.}$

Intersect this event with the original coarse-norm event. For each outcome in the intersection there is a finite $C$ such that $\mathrm{\parallel }{A}_n\mathrm{\parallel }\le C$ eventually. Thus the $s_i^{4k-2}$ average in the comparison inequality is at most $C^{4k-2}$. The $t_i^{4k-2}$ average converges to $v_K^{2k-1}{\mu }_{2k-1}(\gamma )\le {\mu }_{2k-1}(\gamma )$. Consequently ${\mathrm{lim\hspace{0.17em}sup}}_n\mid \frac{1}{n}\mathrm{Tr}{S}_n^k-v_K^k{\mu }_k(\gamma )\mid \le 2k\sqrt{\gamma }{\delta }_K\sqrt{2(C^{4k-2}+{\mu }_{2k-1}(\gamma ))}\mathrm{.}$

Let $K\to \mathrm{\infty }$. This proves, simultaneously for every fixed positive integer $k$, $\frac{1}{n}\mathrm{Tr}{S}_n^k⟶{\mu }_k(\gamma )\text{almost surely}\mathrm{.}$

In particular $n^{-1}\mathrm{Tr}{S}_n\to \gamma >0$, so eventually there is at least one positive eigenvalue. Every fixed polynomial with zero constant term has its normalized trace limit by linearity. There is no triangular truncation, hidden high-moment assumption, or appeal to an empirical-distribution limit.

Set $c=1+\gamma$, $d=2\sqrt{\gamma }$, so $a=c-d$, $b=c+d$, and define on $(a,b)$ $w(x)=\frac{1}{2\pi }\sqrt{(b-x)(x-a)}\mathrm{.}$

We prove the exact positive-moment identity ${\mu }_k(\gamma )={\int }_a^b{x}^{k-1}w(x)dx(k\ge 1)\mathrm{.}$ This is only an identity for explicit numbers and integrals. No probability measure or spectral support theorem is asserted or used.

For real $z>0$ sufficiently small, substitute $x=c+d\cos \theta$. The generating function of the right-hand side is $z{\int }_a^b\frac{w(x)}{1-zx}dx=\frac{z{d}^2}{2\pi }{\int }_0^{\pi }\frac{{\sin }^2\theta }{1-cz-dz\cos \theta }d\theta \mathrm{.}$

For $u>\mathrm{\mid }v\mathrm{\mid }$, substitution $t=\tan (\theta \mathrm{/}2)$ directly gives ${\int }_0^{\pi }(u-v\cos \theta {)}^{-1}d\theta =\pi \mathrm{/}\sqrt{u^2-v^2}$. Polynomial division in $\cos \theta$ then gives ${\int }_0^{\pi }\frac{{\sin }^2\theta }{u-v\cos \theta }d\theta =\frac{\pi }{v^2}(u-\sqrt{u^2-v^2}),$ with its continuous value when $v=0$. Hence the generating function above equals $\frac{1-cz-\sqrt{(1-cz{)}^2-4\gamma z^2}}{2z}\mathrm{.}$

It is analytic near zero, vanishes there, and solves $H=z(1+H)(\gamma +H)$. The formal equation uniquely determines the coefficients recursively, so these coefficients equal the tree counts of phase 1. Expansion under the integral is justified by the uniformly convergent geometric series on $[a,b]$ for small $z$. This proves the identity, also when $a=0$.

Consequently, for every polynomial $P$ with $P(0)=0$, $\frac{1}{n}\mathrm{Tr}P(S_n)⟶{\int }_a^b\frac{P(x)}{x}w(x)dx\mathrm{.}$

At $a=0$, the quotient is the polynomial obtained by canceling the factor $x$, so there is no singularity to interpret.

Fix $L$ with $0<L<b$. For an integer $q\ge 0$ use $P_q(x)=x^{q+1}(x-L)$. Its trace limit is $I_q={\int }_a^b{x}^q(x-L)w(x)dx\mathrm{.}$

Choose $\max (a,L)<t<u<b$. The positive contribution from $[t,u]$ is at least $t^q(t-L){\int }_t^{u}w(x)dx$. The absolute negative contribution, supported in $[a,L]$ when that interval is nonempty, is at most $L^{q}L{\int }_a^{b}w(x)dx$. Since $t>L$ and $w>0$ on $(a,b)$, $I_q>0$ for some finite integer $q$ (and for all sufficiently large $q$). If $L\le a$, positivity follows directly.

If all eigenvalues of $S_n$ were at most $L$, every summand $P_q(\lambda )$ would be nonpositive, contradicting the eventually positive normalized trace. Thus ${\lambda }_{\max }(S_n)>L$ for all sufficiently large $n$. Intersecting over a countable sequence $L\uparrow b$ gives $\mathrm{lim\hspace{0.17em}inf}{\lambda }_{\max }\ge b$.

Fix $U>a$. If desired replace $U$ by a smaller number in $(a,b)$; proving the stronger bound for that smaller threshold proves the original bound. Thus assume $a<U<b$. Choose a fixed $B>b$ and use the polynomial $Q_q(x)=x(U-x)(B-x{)}^{2q},q\ge 0.$

For every $x\ge 0$, it vanishes at $0$, is nonpositive for $x\ge U$, and is positive for $0<x<U$ except at the irrelevant zero of the even factor. Its trace limit is $J_q={\int }_a^b(U-x)(B-x{)}^{2q}w(x)dx\mathrm{.}$

Choose $a<t<u<U$. The positive contribution on $[t,u]$ is at least $(U-u)(B-u{)}^{2q}{\int }_t^{u}w(x)dx\mathrm{.}$

The absolute negative contribution on $[U,b]$ is at most $(b-U)(B-U{)}^{2q}{\int }_a^{b}w(x)dx\mathrm{.}$

Because $B-u>B-U>0$ and the positive interval has positive integral, $J_q>0$ for some finite integer $q$. If $S_n$ had no positive eigenvalue below $U$, all its eigenvalues would be either $0$ or at least $U$, and therefore $\mathrm{Tr}{Q}_q(S_n)\le 0$. The positive limiting trace excludes this for every sufficiently large $n$. Hence ${\lambda }_{\min }^{}(S_n)<U$ eventually. Let $U\downarrow a$ through a countable sequence to obtain $\mathrm{lim\hspace{0.17em}sup}{\lambda }_{\min }^{}\le a$.

For $\gamma =1$, $a=0$. The same argument chooses $0<t<u<U$ and proves an eventually positive eigenvalue below every prescribed $U>0$. The factor $x$ removes every exact zero eigenvalue, including arbitrary extra rank defects, so no rank theorem or lower-rank estimate is concealed in this case. Since eigenvalues are nonnegative, this also proves ${\lambda }_{\min }^{}\to 0$ in the square-aspect-ratio case.