1 Introduction↩︎

For an \(N\times N\) matrix \(A\) with complex entries and complex eigenvalues \(\lambda_1(A),\cdots,\lambda_N(A)\), its empirical spectral distribution (ESD) is defined as the following probability measure \[\mu_A:=\frac{1}{N}\sum_{j=1}^N\delta_{\lambda_j(A)}.\] A central problem in random matrix theory is to study, for a sequence of \(N\times N\) matrices \((A^N)_{N\geq 1}\), the convergence of its ESD \(\mu_{A^N}\) to some deterministic probability measure \(\mu\). When \(A_N\) is a real symmetric or Hermitian matrix, its eigenvalues are real and the convergence of \(\mu_{A^N}\) can be addressed via the method of moments. For matrices with i.i.d. entries above the diagonal, [2] established the celebrated Wigner semicircle law; and for the Gram matrix of i.i.d. rectangular matrices, [3] established the celebrated Marchenko–Pastur law.

The convergence of ESDs for non-Hermitian matrix ensembles is significantly harder to establish. For the i.i.d. ensemble \(X^N\) where the entries are i.i.d. without imposing symmetry, the convergence of \(\mu_{\frac{1}{\sqrt{N}}X^N}\) to the circular law \(\mu_{\text{circ}}\) was established in [4], [5] and [6]. A key component among these papers is that we need to derive quantitative least singular value estimates for \(\frac{1}{\sqrt{N}}X^N-zI\) over \(z\in\mathbb{C}\) in order to rigorously apply Girko’s Hermitization trick [7] (see Section 1.3), which is a new requirement not demanded by Hermitian random matrices. We refer to the survey [8] for more discussion.

Since then, the circular law has also been proven for sparse random matrices [9] and sparse random directed graphs [9], and the limiting ESD for sparse random graphs with constant average degree was established in [10]. The circular law was also recently proven for many inhomogeneous non-Hermitian random matrices, see [11], [12], [13], [14], [15], [16]. However, in these works, the assumption that the entries are (mostly) independent plays a crucial role for establishing least singular value lower bounds for \(\frac{1}{\sqrt{N}}A_N-z\), and thus for establishing the circular law limit.

In this paper, we are specifically interested in random matrices that arise from evaluating a non-commutative polynomial at independent Ginibre matrices. The entries of these matrices are highly dependent. Then for any polynomial \(\mathfrak{p}\) with complex coefficients and \(n\) non-commuting variables, and \(n\) i.i.d. random matrices \(X_1^N,\cdots,X_n^N\), we study the spectrum of \(P^N=\mathfrak{p}(X_1^N,\cdots,X_n^N)\). Prior to this work, the convergence of the ESD of \(P^N\) was only established in several special classes of polynomial \(\mathfrak{p}\). The very special case of product of i.i.d. matrices was studied in much depth in [17], [18], [19], and see also [20]. For more general polynomials \(\mathfrak{p}\), the convergence of ESD of \(P^N\) was only established in [1] when the polynomial \(\mathfrak{p}\) has maximal degree 2. Before the present work, no general theory was known when \(\deg\mathfrak{p}\geq 3\). A series of works [21], [22], [23] have shown that for a sequence of non-normal matrices converging in \(*\)-moments (this covers the case of \(P^N\) here, see the next paragraph), it is often sufficient to add a vanishing noisy perturbation to regularize the ESD and guarantee convergence of ESD to the perceived limiting measure. However, as a perturbation is needed, this does not constitute a general theory of ESDs for \(P^N\) themselves.

Polynomials in random matrices are also central topics in the theory of free probability and operator algebra, stemming from Voiculescu’s work [24]. Voiculescu showed that free probability theory describes the limiting measures for ESDs of polynomials in Wigner matrices. Indeed, let \(\mathfrak{p}\) be a non-commuting and self-adjoint polynomial, and let \(W_1^N,\cdots,W_n^N\) be independent \(N\times N\) GUE matrices, then the ESD of \(\mathfrak{p}(W_1^N,\cdots,W_n^N)\) converges to the spectral distribution of \(\mathfrak{p}(s_1,\cdots,s_n)\) where \(s_1,\cdots,s_n\) are freely independent semi-circular elements in a \(C^*\)-algebra. A later notion of strong convergence introduced by Haagerup and Thorbjørnsen [25] further characterized the convergence of the operator norm of the matrix polynomial to the operator norm of the free probability limit. Some more recent progress on this topic can be found in [26], [27], and see also the survey [28]. However, all these works concern self-adjoint polynomials in Wigner matrices, and the non-normal case is completely untouched. For instance, [28], Section 6.9 asked whether an analogous theory of asymptotic freeness (namely, convergence of the ESD to the Brown measure limit, see Section 1.3) can be derived for polynomials \(\mathfrak{p}\) evaluated in non-Hermitian random matrices. The main contribution of this paper is to make a significant step in this problem, proving convergence of ESDs for \(\mathfrak{p}\) evaluated in Ginibre matrices with arbitrary \(\deg\mathfrak{p}\), and the convergence goes beyond Gaussians covering a class of generic distributions with bounded density. The main results of this paper are stated as follows.

We write \(\mathbb{C}\langle x_1,\cdots,x_n\rangle\) for the class of polynomials with complex coefficients in \(n\) non-commuting indeterminate variables \(x_1,\cdots,x_n\).

The main step in proving Theorem 2 is to lower bound the least singular value of shifted versions of \(P^N\), which is stated in the following second main result of the paper:

Here \(\sigma_{min}(\cdot)\) is the least singular value of a square matrix and \(\mathfrak{p}(0)\) is the constant term in \(\mathfrak{p}\), which is obtained from setting all Ginibre matrices \(X_i^N\) equal to zero. This least singular value estimate excludes the single point \(z=\mathfrak{p}(0)\) and is not uniform in \(z\), but is still sufficient for proving the Brown measure convergence in Theorem 2. We remark that when \(\mathfrak{p}\) has degree two, [1], Theorem 1.3 proved a least singular value estimate uniformly for all \(z\in\mathbb{C}\), but higher degree polynomials are not covered. It is possible to track the exact values of \(c_0\) and \(c\), and they should depend only on the dimension of the linearization matrix associated with \(\mathfrak{p}\), see Section 2, but the exact dimension dependence is very complicated so we do not determine the exact value here.

Interestingly, the main results of this paper do not rely on the strict Gaussian structure of Ginibre matrices, and we generalize them to a wide class of non-Gaussian distributions:

The moment assumption 2 on \(\xi\) can be weakened to requiring only finiteness up to \(Q_\mathfrak{p}\)-th moment, for some constant \(Q_\mathfrak{p}>0\) depending only on the polynomial \(\mathfrak{p}\). We still require in 1 that \(\xi\) has a bounded density on \(\mathbb{C}\), and this covers many non-Gaussian distributions such as the uniform distribution over several disjoint disks in the complex plane, or the convolution of a Gaussian distribution with another subgaussian distribution.

1.1 Main ideas of the proof↩︎

The matrix \(P^N\) is not Hermitian, and to prove the convergence of its empirical spectral law, the standard method by now is to use Girko’s idea [7] to do integration by parts by Green’s formula and transfer the problem to the convergence of the integral of \(\log(x)\) with respect to the empirical singular value distribution of \(P^N-zI\). See Section [section5462for] for details. The main technical step in justifying the latter convergence is to prove that, for almost every \(z\in\mathbb{C}\) with respect to the Lebesgue measure, the least singular value of \(P^N-z\) is at least \(N^{-C_z}\) for some constant \(C_z\). Indeed, aside from this least singular value estimate, all the other steps needed in the proof of Brown measure convergence are relatively standard by now, by combining available technical toolboxes.

For a non-Hermitian square matrix, most existing methods for establishing a least singular value lower bound require independent entries. This is clearly not the case for \(P^N\) as it involves a complicated polynomial \(\mathfrak{p}\). A well-known method to handle this is to find a linearization matrix \(\mathcal{T}_N\), which is a matrix of a larger dimension, such that its least singular value is no larger than the least singular value of \(P^N-z\), and such that the least singular value of \(\mathcal{T}_N\) is much easier to analyze. There are several different ways to find a linearization matrix for \(P^N-z\) and there is no clear consensus which linearization is the best when \(\deg\mathfrak{p}\geq 3\). In Section 2 we introduce one such linearization, and the resulting linearization matrix is written as \[\mathcal{L}_z(X)=K_z\otimes I_N+\sum_{\ell=1}^n H_\ell\otimes X_\ell,\]where \(K_z,H_\ell\) are square matrices of dimension \(m\) and the dimension \(m\) depends only on \(\mathfrak{p}\).

To prove a least singular value lower bound for \(\mathcal{L}_z\), a first attempt would be to construct a net for vectors in \(\mathbb{C}^{N\times m}\) and show that the Gaussian randomness beats the cardinality of the net. But a major problem arises here: do we know that the coefficients \(H_\ell\) span the whole matrix space, or otherwise the covariance matrix of the Gaussian entries lives at a much lower dimension so that we do not have enough randomness at all to beat the net size? Unfortunately, we do not have sufficient structural information about the linearization matrices \(H_\ell\) particularly when \(\deg\mathfrak{p}\geq 3\), and in most interesting cases, the matrices \(H_\ell\) do not span the whole space \(M_m(\mathbb{C})\) and a naive net argument via Gaussian anti-concentration is insufficient.

To simplify the problem, we note that \(K_z\) is invertible when \(z\neq \mathfrak{p}(0)\), so we multiply by \(K_z^{-1}\) to turn \(H_\ell\) into \(H_\ell K_z^{-1}\) and turn \(K_z\) to \(I_m\). This transform is legitimate since \(K_z\) is singular only at \(z=\mathfrak{p}(0)\), and we simply ignore this value of \(z\) by proving the estimate at all other \(z\in\mathbb{C}\). The benefit is immediate: suppose that on some linear subspace of \(\mathbb{C}^m\), each \(H_\ell K_z^{-1}\) acts by 0, then the \(I_m\) term preserves invertibility; whereas if \(H_\ell K_z^{-1}\) acts non-trivially, we may use Gaussian anti-concentration from \(H_\ell K_z^{-1}\). The intuition is mostly clear in 1-d, where \(I_N+rX^N\), \(X^N\) a Ginibre matrix, has nontrivial least singular value lower bound for any \(r\in\mathbb{C}\). At this point one may guess that perhaps the exact structure of \(H_\ell\) and \(K_z^{-1}\) does not matter, and can one prove a least singular value lower bound for arbitrary coefficient matrices? This idea is stated in the following theorem (see Theorem 27 for the non-Gaussian generalization):

Theorem 5 may appear plausibly true although we still do not know how to handle high dimensional matrix coefficients. The first idea is that we can do an algebraic reduction: we may suppose that \(R_1,\cdots,R_n\) have no common nontrivial invariant subspace, which corresponds to assuming that \(\mathbb{C}^m\) is a simple module under left \(R_1,\cdots,R_n\) action. If this is not true, we can find a composition series, such that each quotient module is a simple left \(R_1,\cdots,R_n\)-module. See Section 3.1 for details. In this filtration, the matrix \(\mathcal{T}_N\) is directly put into a block upper triangular form, and by simple linear algebra (Fact 11) we know that we only need to get a least singular value lower bound for each diagonal block where the induced action of \(R_1,\cdots,R_n\) acts irreducibly.

To handle each irreducible block, we will use the negative second moment identity (Lemma 2) to lower bound the least singular value. The idea of the method is to find the normal vector to all columns except the \(a\)-th big column, and test the inner product of this \(a\)-th column against this normal vector. In our setting, any big column is spanned by coefficients \(R_\ell\) multiplied by a Gaussian, therefore denoting \(A=(A_1,\cdots,A_N)\) the unit normal to all columns except the \(a\)-th, we need to test the inner product of \(A\) with these coefficients \(R_\ell\). For fixed \((R_\ell)\) which are not all zero, the Gram matrix is non-degenerate, so this can be transferred to measuring the size of each component \(A_i\) in the linear subspace spanned by \(R_1,\cdots,R_n\). Therefore, if the final inner product is small in expectation, this would almost force each component \(A_i\) to lie almost entirely in the orthogonal complement of \(R_1,\cdots,R_n\) in \(M_m(\mathbb{C})\). Let \(B\) be the entry-wise projection of \(A\) onto the orthogonal complement of \(R_1,\cdots,R_n\), this implies that \(B\) should approximately solve the following equation \[B_k+\sum_{i,\ell}\overline{X_\ell(i,k)}R_\ell^*B_i\to 0,\quad \forall k\neq a.\] We prove in Theorem 13 that this is impossible with very high probability.

Suppose that \(B_1,\cdots,B_N\) span a subspace \(E\), and denote \(Y(E):=\operatorname{span}_{\ell=1}^n R_\ell^*E\). Then this means each \(B_i\) should approximately lie in \(E\cap Y(E)\) yet the Gaussian randomness has effective dimension \(\dim Y(E)\). Temporarily ignoring very small coefficients, this means that if we know \(\dim Y(E)\geq\dim (E\cap Y(E))+1\), then the Gaussian anti-concentration has one more effective dimension than the net size needed to cover the \(B_i's\), and this net argument wins. This should imply that the components of \(B\) should not all be nearly orthogonal to \(\operatorname{span}(R_1,\cdots,R_n)\), completing the proof of Theorem 13.

So why do we have \(\dim (E\cap Y(E))<\dim Y(E)\)? This follows from our algebraic assumption that \(R_i\) now acts irreducibly, and we can turn this into irreducibility of the action of \(R_i^*\), ruling out the possibility that \(Y(E)\subset E\) by irreducibility. This is the content of Proposition 12. In the above we have temporarily regarded inequalities with small error as equalities, and we ignored all possibilities of small but nonzero coefficients. In Section 4 we turn this into a rigorous proof allowing all margins, approximations and nearly degenerate coefficients. This gives a full proof of Theorem 5.

To the best of the author’s knowledge, the use of simple algebraic ideas such as irreducible modules, composition series and irreducible dual actions in proving least singular value estimates appears to be new. Meanwhile, Theorem 5 may be useful beyond the current setting of polynomials in Ginibre matrices: the theorem covers what may be called patterned Ginibre matrices of finite type and is further very flexible with respect to taking tensor products. The freedom in the choice of \(R_i\) opens many possibilities for investigating many other structured Ginibre matrices via Theorem 5, which are not accessible otherwise.

1.1.1 The non-Gaussian case↩︎

Generalizing the Gaussian result to the non-Gaussian setting further demands some hard work. The lack of Carbery-Wright inequality for non-log-concave measures requires us to prove a substitute estimate (Proposition 29), and we develop moment comparisons to transfer the proven Gaussian case analysis to the general case. The free probability part (Lemma 8) also relies on some recent advances in strong convergence from [27], see also [28].

1.2 Some future directions↩︎

We list here some future directions that are worth further pursuing, and they can be seen as natural next steps of this work.

1.3 The Brown measure limit↩︎

This section reviews the definition of the Brown measure limit, while the main contents are referenced from [1]. A more comprehensive introduction to free probability can be found in [30] or [31].

We recall that a tracial \(W*\)-probability space \((\mathcal{A},\tau)\) consists of a von Neumann algebra \(\mathcal{A}\) and a tracial faithful normal state \(\tau\) on \(\mathcal{A}\). By Voiculescu’s result [24], we have the convergence of the non-commutative distribution of \((X_1^N,\cdots,X_n^N)\) in \(*\)-moments to the non-commutative distribution for \(n\) free circular elements \((c_1,\cdots,c_n)\in\mathcal{A}\). The convergence is in the sense that for any polynomial \(\mathfrak{p}\in\mathbb{C}\langle x_1,\cdots,x_n,x_1^*,\cdots,x_n^*\rangle\) we have \[\lim_{N\to\infty}\frac{1}{N}\operatorname{Tr}(\mathfrak{p}(X_1^N,\cdots,X_n^N,(X_1^N)^*,\cdots,(X_n^N)^*))=\tau(\mathfrak{p}(c_1,\cdots,c_n,c_1^*,\cdots,c_n^*)).\] where the right-hand side is a linear map on the set of polynomials, and is uniquely defined by its values on monomials. For any monomial where we choose \(i_1,\cdots,i_k\in[1,n]\) and any \(\epsilon_1,\cdots,\epsilon_k\in\{1,*\}\), \(\tau(c_{i_1}^{\epsilon_1}\cdots c_{i_k}^{\epsilon_k})\) equals the number of non-crossing pair partitions of \(\{1,\cdots,k\}\) where each block \(b=(b_1,b_2)\) satisfies that \(i_{b_1}=i_{b_2}\) and furthermore \((\epsilon_{b_1},\epsilon_{b_2})=(1,*)\text{ or }(*,1)\). Since polynomial functions are dense among the set of continuous functions, using the fact that Ginibre matrices are bounded with exponentially high probability, the latter implies that for any bounded continuous function \(f\) and self-adjoint polynomial \(\mathfrak{p}\), \[\lim_{N\to\infty}\frac{1}{N}\operatorname{Tr}(f(\mathfrak{p}(X_1^N,\cdots,X_n^N,(X_1^N)^*,\cdots,(X_n^N)^*)))=\tau(f(\mathfrak{p}(c_1,\cdots,c_n,c_1^*,\cdots,c_n^*)))\quad a.s.\]For self-adjoint \(\mathfrak{p}\), this immediately guarantees convergence of empirical spectral law of \(\mathfrak{p}(X_1^N,\cdots,X_n^N,(X_1^N)^*,\cdots,(X_n^N)^*)\) toward the distribution of \(\mathfrak{p}(c_1,\cdots,c_n,c_1^*,\cdots,c_n^*)\). For non-self-adjoint \(\mathfrak{p}\), the convergence is no longer justified so easily. Girko’s idea [7] of integration by parts via Green’s formula suggests that the empirical measure for eigenvalues of \(\mathfrak{p}(X_1^N,\cdots,X_n^N,(X_1^N)^*,\cdots,(X_n^N)^*)\) should converge to the Brown measure defined below, which is given for any twice continuously differentiable function \(\psi\) with bounded support on \(\mathbb{C}\) via \[\label{righthandsideof} \int_\mathbb{C}\psi(\lambda)d\nu_{\mathfrak{p}(c_1,\cdots,c_n,c_1^*,\cdots,c_n^*)}(\lambda):=\frac{1}{4\pi}\int \Delta\psi(z)\tau(\log|z-\mathfrak{p}(c_1,\cdots,c_n,c_1^*,\cdots,c_n^*)|^2)dz.\tag{3}\] To see why this limit is anticipated, note that for any twice continuously differentiable function \(\psi\) with bounded support and complex numbers \(\lambda_i,1\leq i\leq N\), integration by parts yields \[\frac{1}{N}\sum_{i=1}^N\psi(\lambda_i)=\frac{1}{2\pi}\int\Delta\psi(z)\frac{1}{N}\sum_{i=1}^N\log|z-\lambda_i|dz,\]and \(dz\) is integration over Lebesgue measure on \(\mathbb{C}\). Taking the \(\lambda_i,1\leq i\leq N\) as eigenvalues of \(\mathfrak{p}(X_1^N,\cdots,X_n^N,(X_1^N)^*,\cdots,(X_n^N)^*)\) the above implies that \[\frac{1}{N}\sum_{i=1}^N\psi(\lambda_i)=\frac{1}{4\pi}\int\Delta\psi(z)\frac{1}{N}\operatorname{Tr}\left(\log|z-\mathfrak{p}(X_1^N,\cdots,X_n^N,(X_1^N)^*,\cdots,(X_n^N)^*)|^2\right)dz.\]Observe that the function \(|z-\mathfrak{p}(X_1^N,\cdots,X_n^N,(X_1^N)^*,\cdots,(X_n^N)^*)|^2\) is self-adjoint in the entries, and ignoring the singularity and unboundedness of the logarithm we can heuristically take the limit and obtain the right-hand side of 3 .

In this paper we restrict ourselves to holomorphic polynomials \(\mathfrak{p}\) so that \(\mathfrak{p}\) only depends on \(X_1^N,\cdots,X_n^N\) but not their adjoints. Theorem 2 proves that, for this class of holomorphic polynomials \(\mathfrak{p}\) of any degree, the spectrum of \(\mathfrak{p}(X_1^N,\cdots,X_n^N)\) converges to the Brown measure when evaluated at complex Ginibre matrices.

1.4 Notation and list of symbols↩︎

Throughout the paper, \(M_m(\mathbb{C})\) denotes the linear space of complex-valued square matrices of dimension \(m\). More generally, \(M_{m_1,m_2}(\mathbb{C})\) consists of complex matrices of dimension \(m_1\times m_2\). The latter space is equipped with the Hilbert-Schmidt norm: for each \(A\in M_{m_1,m_2}(\mathbb{C})\), \[\|A\|_{\text{HS}}=\left(\sum_{s=1}^{m_1}\sum_{t=1}^{m_2}|A_{s,t}|^2\right)^\frac{1}{2}.\] Then \(M_m(\mathbb{C})\) is a Hilbert space with respect to the inner product \(\langle A,B\rangle=\operatorname{Tr}(AB^*)\).

Let \(\mathcal{H}\) be a complex Hilbert space of complex dimension \(d\). Then the complex Grassmannian \(\operatorname{Gr}_\mathbb{C}(k,\mathcal{H})\) consists of linear subspaces of \(\mathcal{H}\) of complex dimension \(k\). The Grassmannian has real dimension \(2k(\dim \mathcal{H}-k)\) and is equipped with the following projection metric \[\rho(E,E'):=\|P_E-P_{E'}\|_{\text{op}},\]where \(P_E,P_{E'}\) are orthogonal projections from \(\mathcal{H}\) onto \(E\) and \(E'\) respectively. We can find a \(\delta\)-net \(\mathcal{G}_\delta\) in this Grassmannian with cardinality \[|\mathcal{G}_\delta|\leq(\frac{C}{\delta})^{2k(d-k)}\]for some universal constant \(C>0\).

2 First reductions↩︎

This section defines a linearization matrix for \(P^N-zI\), and reduces the least singular value proof of Theorem 3 to the proof of Theorem 5. Linearization of matrix polynomials has seen many applications in random matrix theory and computations, see for instance [32], [33].

2.1 Tensor train decomposition of the polynomial↩︎

We introduce a linearization for the polynomial \(\mathfrak{p}\). Indeed, there are many different ways to find such a linearization, and our main proof mechanisms are not specific to one particular linearization matrix. We use the tensor train decomposition introduced in [34].

First write \(\mathfrak{p}\) in the following form: \[\mathfrak{p}(x)=a_\emptyset+\sum_{\ell=1}^n b_\ell x_\ell+\sum_{q=2}^d\mathfrak{p}_q(x),\]where \(d\) is the maximal degree of \(\mathfrak{p}\) and \(\mathfrak{p}_q(x)\) is the homogeneous degree-q part of \(\mathfrak{p}(x)\). We can further write each \(\mathfrak{p}_q(x)\) as \[\mathfrak{p}_q(x)=\sum_{i_1,\cdots,i_q}a_{i_1,\cdots,i_q}^{(q)}x_{i_1}\cdots x_{i_q} .\]

For each nonzero \(\mathfrak{p}_q\), we choose a minimal Tensor Train/Hankel factorization as follows. Specifically, define the Tensor Train ranks \[r_{q,s}:=\operatorname{rank}[a^{(q)}_{i_1\cdots i_s;i_{s+1}\cdots i_q}],\quad s=1,\cdots,q-1.\]That is, we flatten the degree-\(q\) coefficient tensor across the split \[(i_1,\cdots,i_s)\mid (i_{s+1},\cdots,i_q).\] Then we define the intermediate state spaces \[E_{q,s}\eqsim \mathbb{C}^{r_{q,s}},\quad s=1,\cdots,q-1.\] These homogeneous components share the same scalar root space \(E_\star=\mathbb{C}\). Then for this polynomial \(\mathfrak{p}\), we consider the following bouquet linearization space \[E=E(\mathfrak{p})=E_\star\oplus \oplus_{2\leq q\leq d,\mathfrak{p}_q\neq 0} \oplus_{s=1}^{q-1}E_{q,s} .\] The subspace \(E\) has dimension \[m=m(\mathfrak{p})=1+\sum_{2\leq q\leq d:\mathfrak{p}_q\neq 0}\sum_{s=1}^{q-1}r_{q,s}.\] For this degree-q part \(\mathfrak{p}_q\) we define a family of maps \(G_{q,1}(\cdot),\cdots,G_{q,q}(\cdot)\) such that the argument of each function takes values in \([1,n]\) and \[G_{q,s}(i):E_{q,s}\to E_{q,s-1},\quad 1\leq s\leq q\] is a linear map for each \(1\leq i\leq n\), with \(E_{q,0}=E_{q,q}=\mathbb{C}\), and the coefficient tensor can be written in the following tensor train form: \[\label{tensortrainforms} a_{i_1\cdots i_q}^{(q)}=G_{q,1}(i_1)G_{q,2}(i_2)\cdots G_{q,q}(i_q) .\tag{4}\]

The maps \(G_{q,1}(\cdot),\cdots,G_{q,q}(\cdot)\) can be constructed as follows (the construction is not unique).

Start with the flattening \[M_1(i_1;i_2,\cdots,i_q)=a^{(q)}_{i_1\cdots i_q}.\]Then factor it with rank \(r_{q,1}\): \[M_1=U_1V_1.\]Then define \[\operatorname{G_{q,1}}(i_1):=\operatorname{row } i_1\text{ of }U_1\] so that \(G_{q,1}(i_1)\in M_{1,r_{q,1}}\). The remaining tensor is \(V_1(\alpha_1;i_2,\cdots,i_q)\). Next we flatten \(V_1\) via \[(\alpha_1,i_2)\mid (i_3,\cdots,i_q).\]Factor it with rank \(r_{q,2}\) so we write \[V_1(\alpha_1,i_2;i_3,\cdots,i_q)=U_2V_2\] and define \[G_{q,2}(i_2)_{\alpha_1}:=\text{ the (\alpha_1,i_2)-th row of }U_2\]so that \(G_{q,2}(i_2)\in M_{r_{q,1},r_{q,2}}\). Proceed in this way, for each \(1\leq s\leq q-2\) and each \(V_s(\alpha_s,i_{s+1},\cdots,i_q)\) we write \[V_s(\alpha_s,i_{s+1};i_{s+2},\cdots,i_q)=U_{s+1}V_{s+1}\] and take \(G_{q,s+1}(i_{s+1})_{\alpha_s}\) as the \((\alpha_s,i_{s+1})\)-th row of \(U_{s+1}\). And finally we define \[G_{q,q}(i_q)_{\alpha_{q-1},1}=V_{q-1}(\alpha_{q-1};i_q).\] This defines \(G_{q,3},\cdots,G_{q,q}\).

Then equation 4 is directly fulfilled by the above definitions. This can be verified inductively: \[\begin{align} a_{i_1\cdots i_q}^{(q)}&=\sum_{\alpha_1=1}^{r_{q,1}}U_1(i_1,\alpha_1)V_1(\alpha_1,i_2,\cdots,i_q)\\&=\sum_{\alpha_1=1}^{r_{q,1}}G_{q,1}(i_1)\sum_{\alpha_2=1}^{r_{q,2}}U_2(\alpha_1,i_2;\alpha_2)V_2(\alpha_2,i_3,\cdots,i_q)=\cdots. \end{align}\]

2.2 Linearization step and generated subalgebra↩︎

We will define the linearization matrix in a specific way tailor-made for our goal. For a compact \(z\)-region, say \(|z|\leq R\), consider the root scalar \(\theta_*(z)=a_\emptyset-z\). Then basically any choice of nonzero constants \[\eta_{q,s}\in\mathbb{C}\setminus\{0\},\quad 2\leq q\leq d,1\leq s\leq q-1\] can generate a valid linearization. For future applications, when \(z\neq a_\emptyset\), we fix one choice \[\label{equalitys} \eta_{q,s}=a_\emptyset -z,\quad 2\leq q\leq d,1\leq s\leq q-1,\tag{5}\] and when \(z=a_\emptyset\) we simply take \(\eta_{q,s}=1\) for all \(q,s\).

Denote by \(d_\mathfrak{p}:=\deg\mathfrak{p}\) the maximal degree of the polynomial \(\mathfrak{p}\). Then we define a deterministic diagonal matrix \(K_z\) via \[K_z=(a_\emptyset-z)P_\star+\sum_{2\leq q\leq d_\mathfrak{p},\mathfrak{p}_q\neq 0}\sum_{s=1}^{q-1}\eta_{q,s}P_{q,s},\] where \(P_\star\) and \(P_{q,s}\) are orthogonal projections onto \(E_\star\) and \(E_{q,s}\). For \(z\neq a_\emptyset\), by our definition, \[K_z=(a_\emptyset-z)I_E.\] so \(K_z\) acts as a scalar multiple on the whole space \(E\).

Next, we define the edge matrices \(H_\ell\). For each letter \(\ell\in\{1,\cdots,n\}\), we define \(H_\ell\in M_m(\mathbb{C})\) via the following steps.

First include the linear part of \(\mathfrak{p}\) by setting \[(H_\ell)_{\star,\star}=b_\ell.\] Then for each homogeneous chain \(\mathfrak{p}_q,q\geq 2\) we define the following chain scaling constant \[\mu_q:=(-1)^{q-1}\prod_{s=1}^{q-1}\eta_{q,s}.\]Then we enter the following blocks in \(H_\ell\): \[(H_\ell)_{E_\star,E_{q,1}}=\mu_q G_{q,1}(\ell),\]

\[(H_\ell)_{E_{q,s-1},E_{q,s}}=G_{q,s}(\ell),\quad 2\leq s\leq q-1,\]and finally set \[(H_\ell)_{E_{q,q-1},E_\star}=G_{q,q}(\ell),\]as we identify \(E_*\simeq E_{q,q}\simeq \mathbb{C}\). We finally set all other blocks to be zero except those already defined. Then we define the following linearization

\[\label{equation325} \mathcal{L}_z(X)=K_z\otimes I_N+\sum_{\ell=1}^n H_\ell\otimes X_\ell.\tag{6}\]

We now check that this is the correct Schur complement formula:

We illustrate our construction for polynomials of degree 3:

2.3 Operator norm upper bound↩︎

Since the Ginibre matrices \(X_i^N\) have bounded operator norm with high probability, we will work on this event throughout the article:

Meanwhile, we can take the inverse of \(K_z\) when \(z\neq \mathfrak{p}(0)\):

Then Theorem 3 can be deduced from Theorem 5:

3 Least singular value for the general tensor product model↩︎

This section is devoted to the proof of Theorem 5, a quantitative least singular value lower bound for the following general tensor product matrices \[\mathcal{T}_N= I_m\otimes I_N+\sum_{\ell=1}^n R_\ell\otimes X_\ell,\]where \(R_1,\cdots,R_n\) are fixed in \(M_m(\mathbb{C})\) and \(X_1,\cdots,X_n\) are i.i.d. complex Ginibre matrices.

3.1 Filtration spanning and irreducible modules↩︎

The first step of the proof is to decompose the space \(\mathbb{C}^m\) into invariant subspaces for left \(R_1,\cdots,R_n\) action, and then to form irreducible quotients for the action. The decompositions stated here will be used throughout this section.

Consider the algebra \[\mathcal{A}:=\operatorname{alg}(I_m,R_1,\cdots,R_n)\subset M_m(\mathbb{C})\] and we regard \(\mathbb{C}^m\) as a left \(\mathcal{A}\)-module where \(\mathcal{A}\) acts from the left by left multiplication. (Note: in general, the algebra \(\mathcal{A}\) does not generate the whole matrix algebra \(M_m(\mathbb{C})\), so we need a filtration here.)

We fix an \(\mathcal{A}\)-invariant composition filtration of \(\mathbb{C}^m:\)

\[\label{filtrationgaps} 0=Z_0\subsetneq Z_1\subsetneq\cdots\subsetneq Z_s=\mathbb{C}_m,\tag{8}\] where each \(Z_a\) is invariant for all left \(R_\ell\) actions, and each quotient \[\label{dimsib} S_{I(b)}:=Z_b/Z_{b-1}\tag{9}\] is a simple left \(\mathcal{A}\)-module. We use the subscript \(I(b),1\leq b\leq s\) to stress that this labels irreducible quotient modules instead of columns. Then we define \(S_{I(1)},\cdots,S_{I(s)}\).

A natural question is how we choose the filtration 8 , as the choice of composition filtration is in general not unique and not canonical. Indeed, the exact choice does not matter: we will choose an arbitrary composition filtration 8 and fix it throughout the paper. Although the numerical constants in the least singular value estimate will depend on the choice of filtration, any choice of filtration is enough to complete the proof.

Next, we assign a norm on each \(S_{I(b)}\) via the Hilbert space quotient norm. Equivalently, we choose an orthogonal splitting \[\mathbb{C}^m=E_1\oplus\cdots E_s,\quad E_a=Z_a\cap Z_{a-1}^\perp.\] Under this orthogonal decomposition, each \(R_i\) is placed in a block upper triangular form, and each block map is the following induced map \[\label{inducedactions} R_\ell^{(I(b))}:S_{I(b)}\to S_{I(b)}.\tag{10}\] Therefore, each \(\mathcal{T}_N\) is also of block upper triangular form, where its diagonal blocks are \[\label{label526} \mathcal{T}_{N,I(b)}= I_{S_I(b)}\otimes I_N+\sum_{\ell=1}^n R_\ell^{(I(b))}\otimes X_\ell,\quad 1\leq b\leq s.\tag{11}\] Therefore, we only need to prove least singular value lower bound on each simple factor, and the overall LSV lower bound can be retrieved via the following triangular reconstruction mechanism:

3.2 Consequence of a simple module↩︎

In this algebraic subsection, we show why passing to irreducible \(\mathcal{A}\)-modules \(Z\) is particularly useful for our goal. The main idea is that if \(Z\) is irreducible for the left multiplication of \(R_i\), then a subset of \(\operatorname{End}(Z)\) will also be irreducible for the left multiplication of dual atoms \(R_1^*,\cdots,R_n^*\). This will be very useful when we characterize the structure of a normal vector to column subspaces.

We again use a fully abstract formulation. Let \(Z\) be a fixed finite-dimensional Hilbert space with given coefficient maps \[R_1,\cdots,R_n\in\operatorname{End}(Z).\] Denote the linear subspace they generate by \[\Sigma_R:=\operatorname{span}\{R_1,\cdots,R_n\}\subset\operatorname{End}(Z)\]and also denote by \(\mathcal{D}_R\) its orthogonal complement in the Hilbert-Schmidt norm: \[\mathcal{D}_R:=\Sigma_R^\perp\subset\operatorname{End}(Z).\] Then for any nonzero linear subspace \[0\neq E\subset \mathcal{D}_R,\] we define the subspace generated by \(R_\ell^*\) from \(E\) by \[\label{yyyeee}Y(E):=\operatorname{span}_{\ell=1}^n R_\ell^*E .\tag{12}\] Note that the case \(E=\mathcal{D}_R\) is also contained in this definition.

3.3 Least singular value for dual operators with a dimensional surplus↩︎

We introduce a crucial least singular value estimate which is a consequence of Proposition 12.

Let \(Z\) be an irreducible left \(\mathcal{A}\)-module, and recall that \(\mathcal{D}_R\subset \operatorname{End}(Z)\) is the orthogonal subspace to \(\Sigma_R=\operatorname{span}(R_1,\cdots,R_n)\). Let \(a\) be any index where \(1\leq a\leq N\), and define the following random operator \[\mathfrak{D}_a:\mathcal{D}_R^N\to\operatorname{End}(Z)^{N-1}\]via \[(\mathfrak{D}_aB)_k=B_k+\sum_{i,\ell}\overline{X_\ell(i,k)}R_\ell^*B_i,\quad k\neq a.\] Here we simply use \(R_\ell\) to denote the induced action of \(R_\ell\) on \(Z\) (see 10 for the more precise notation of induced action, but we omit the induced subscript \(I(b)\) here for simplicity), and \(R_\ell^*\) is simply the adjoint matrix of this induced action \(R_\ell\).

Indeed, by definition the law of \(\mathfrak{D}_a\) does not depend on the choice of \(a\). The mapping \(\mathfrak{D}_a\) arises as we consider the normal vector to the span of all columns of \(\mathcal{T}_{N,I(s)}\) with the \(a\)-th column removed (for any block \(s\)), and the input vector \(B\) ranges from all normal vectors taking value in \(\mathcal{D}_R\). We have the following lower bound for the least singular value of \(\mathfrak{D}_a\):

Here \(R_1,\cdots,R_n\) act trivially means that they act by zero on \(Z\) and in particular \(Z\) is one dimensional. Except this degenerate case, we always have \(\dim \Sigma_R>0\) so that \(\dim \mathcal{D}_R<\dim \operatorname{End}(Z)\). Thus the output dimension of \(\mathfrak{D}_a\) is larger than the input dimension when \(N\) is large enough, and therefore a good least singular value lower bound is expected to hold for \(\mathfrak{D}_a\). The proof of Theorem 13 is deferred to Section 4. The proof is highly technical and is one of the main contributions of this paper. We now complete the rest assuming Theorem 13 holds.

3.4 Proving square LSV for a single factor via exposed columns↩︎

To bound the least singular value of \(\mathcal{T}_N\) which is a square matrix, we will use the following negative second moment identity. The proof is presented in Appendix 7.

We now apply Lemma 2 to the matrix \(\mathcal{T}_N\). We fix an exposed block column \(a\) (which means all the columns indexed by \(\{1,\cdots,m\}\otimes e_a\) where \(e_a\) is the \(a\)-th column for an \(N\)-column matrix). After removing the \(a\)-th block column, denote by \(\mathcal{T}_{-a}\) the resulting matrix. Denote by \[W_a:=\ker (\mathcal{T}_{-a}^*)\subset Z^N.\]Then almost surely, \(\dim W_a=\dim Z.\) Indeed, the following fact is proven in Appendix 7:

The \(a\)-th exposed column of \(\mathcal{T}_N\) has the following form \[C_a(\xi):Z\to Z^N,\] \[C_a(\xi)u=e_au+\sum_{i=1}^N\sum_{\ell=1}^n\xi_i^\ell e_iR_\ell u,\]where \(e_1,\cdots,e_N\) are standard basis vectors and where \(\xi_i^\ell\) are i.i.d. copies of complex Gaussian random variables with variance \(\frac{1}{N}\). Then we project onto \(W_a\) and denote by \[D_a(\xi):=P_{W_a}C_a(\xi):Z\to W_a.\]

Our goal is to prove that, with very high probability over the non-exposed columns in \(\mathcal{T}_{-a}\), we can find some fixed constant \(B_Z>0\) such that \[\label{testvectors} \|\det D_a(\xi)\|_{L_\xi^2}\geq N^{-B_Z}.\tag{13}\] This is because a lower bound on \(\det D_a(\xi)\) can easily yield a lower bound on \(\sigma_{\text{min}}(D_a(\xi))\) which we then feed in Lemma 2, since it has a fixed size and bounded operator norm.

3.5 Exposed coefficient frame lower bound↩︎

To prove 13 , we regard \(D_a(\xi)\) as a Gaussian vector (conditional on \(\mathcal{T}_{-a}\)) and compute its variance by testing it against other test vectors. We take any unit test vector \[A:Z\to W_a\subset Z^N.\]We write the coordinates of \(A\) in terms of the coordinate structure on \(Z^N\) as \[A=(A_i)_{i=1}^N,\quad A_i\in\operatorname{End}(Z).\]Then we can write the inner product as \[\langle A,D_a(\xi)\rangle=\langle A_a,I_Z\rangle+\sum_{i,\ell}\xi_i^\ell\langle A_i,R_\ell\rangle.\]Then \(\mathbb{E}[\langle A,D_a(\xi)\rangle]=\langle A_a,I_Z\rangle.\)

At this point, we divide into two different situations:

1. Either on \(Z\), all the actions \(R_\ell\) act by 0. Then \(Z\) is simply one dimensional and the matrix \(\mathcal{T}_N\) is simply the \(N\)-dimensional identity matrix. Then its least singular value lower bound is immediate.

2. The left actions \(R_\ell\) do not act by 0 on \(Z\). We will then use anti-concentration of the Gaussian vectors. The rest of the proof will focus only on this situation.

We prove the following characterization of the structure of \(A\):

3.6 Frame lower bound↩︎

The following is a direct consequence of Proposition 15:

3.7 Carbery-Wright and block negative second moment↩︎

To convert the estimate in expectation in 18 to a small ball estimate, we shall need the following anti-concentration result of Carbery and Wright:

Now we can complete the proof of Theorem 5.

3.7.1 Constant dependence↩︎

4 Dual least singular value estimate with dimensional surplus↩︎

This section is devoted to the proof of Theorem 13. Recall that we consider the random mapping \(\mathfrak{D}_a\) defined via \[(\mathfrak{D}_aB)_k=B_k+\sum_{i,\ell}\overline{X_\ell(i,k)}R_\ell^*B_i,\quad k\neq a.\]

Let \(E\subset \mathcal{D}_R:=\Sigma_R^\perp\subset \operatorname{End}(Z)\) be any linear subspace, and define the following coefficient maps \[\Psi_E:E\otimes\mathbb{C}^n\to \operatorname{End}(Z),\quad \Psi_E((x_\ell)_\ell)=\sum_{\ell=1}^n R_\ell^*x_\ell.\] Then, by definition in 12 , \(Y(E)=\operatorname{Ran}\Psi_E\). However, the smallest singular value of this map can become very small and make later small-ball estimates infeasible. To remedy this, take a scale \(\sigma\geq 0\) (whose value will be determined later), and we define the following subset of \(Y(E)\):

\[\label{scaleysigmae} Y_\sigma(E):=\text{span}\{\text{left singular vectors of }\Psi_E\text{ with singular value }\geq\sigma\}.\tag{23}\] We call this the active image, which is the part of \(Y(E)\) such that the Gaussian random term has variance at least \(\sigma^2/N\). The dimensions in \(Y(E)\cap( Y_\sigma(E))^\perp\) are discarded and not counted for small ball dimensions.

Then we define the following quotient map \[P_{E,\sigma}:E\to \operatorname{End}(Z)/Y_\sigma(E),\quad P_{E,\sigma}x=[x] .\]

Take another threshold \(\tau>0\) which will be fixed later, and we define \[\label{scaletausigmae} C_{\tau,\sigma}(E) :=\text{span}\{\text{right singular vectors of }P_{E,\sigma}\text{ with singular value }\leq\tau\}.\tag{24}\] Informally, \(C_{\tau,\sigma}(E)\) is the part of \(E\) which is within an angle \(\tau\) to the active image \(Y_\sigma(E)\).

Throughout the section we work under the following good operator norm event: there exists some constant \(M_{\text{op}}>0\) such that \[\label{goodoperatornorm} \Omega_{\text{good}}:=\{ \|\Psi_E\|\leq M_{\text{op}}\quad \forall E,\quad \|X_\ell\|\leq 8\quad \forall 1\leq \ell\leq n\}.\tag{25}\] Since \(\|\Psi_E\|\leq\sum_{\ell=1}^n\|R_\ell^*\|\), \(M_{\text{op}}\) always exists and we fix such a choice. By standard properties of operator norm bounds for Ginibre, we have \[\mathbb{P}(\Omega_{\text{good}})\geq 1-\exp(-\Omega(N)),\] where the multiplicative constant in \(\Omega(N)\) depends only on \(n\).

4.1 Preliminaries for a net argument↩︎

In this section, we list all technical preparations that we will need to prove Theorem 13.

4.1.1 A robust lemma for dimension surplus↩︎

We shall first need the following quantitative strengthening for Proposition 12:

For two linear subspaces \(Y,C\subset F\) in a Hilbert space \(F\), and \(t>0\), we use the following notation \(Y\subset_t C\) to mean that \[Y\subset_t C\Rightarrow \operatorname{dist}(y,C)\leq t\|y\|\quad\forall y\in Y.\] We shall need the following simple linear algebra lemma (proof see Appendix 7)

4.1.2 Geometric intersections and solution to kernel equation↩︎

We will use the following abstract tube covering lemma for the kernel equation satisfied by a unit normal vector \(A\).

Observe that if we take \(Y=Y_\sigma(E)\) for some \(\sigma>0\) as defined in 23 , then \(C_\tau(E,Y)\) coincides with the space \(C_{\tau,\sigma}(E)\) defined in 24 .

We explain how Lemma 4 is used for the kernel equation of normal vectors \(A\). If \(\|(\mathcal{D}A)_k\|\leq\rho\), then we have \[A_k\in E\cap (Y(E)+\rho B_\mathcal{H})\]for each \(k\). Then each \(A_k\) is contained in \(T_\rho(E,Y(E))\), so we apply Lemma 4 with \(Y=Y(E)\). Then by 28 , the entries \(A_k\) are covered by the product of the net of the unit ball in \(C_\tau(E,Y)\) and by the other net in its orthogonal complement with a much smaller net size. In practice, we always take \(\epsilon=C_{op}\rho\) for a constant \(C_{op}\) depending only on the operator norm, and \(\epsilon,\rho\) will be polynomially small in \(N\). The constant \(\tau\) will be set sufficiently small (so we can use Proposition 18) but fixed and independent of \(N\). Therefore, the net size on \(E\cap(C_\tau(E,Y))^\perp\) used for approximating 29 is fixed no matter how small \(\epsilon,\rho\) really are, and does not contribute in magnitude to the net entropy.

4.1.3 Covariance operator and active subspace extraction↩︎

We describe a standard procedure to project a PSD matrix onto subspaces where the least singular value is positively bounded from below. Let \(E\) be a finite-dimensional Hilbert space with complex dimension \(n\), and let \[\mathcal{S}:=\sum_{i=1}^se_ie_i^*.\]Then \(\mathcal{S}\geq 0\). Let its eigenvalues be \(\lambda_1,\cdots,\lambda_n\geq 0\), having the corresponding orthonormal eigenvectors \(u_1,\cdots,u_n\).

Fix a threshold \(\tau>0\). At the first layer, we test if \(\lambda_n(\mathcal{S})\geq \tau\). If yes, we take \(W=E\) and \(e_i'=e_i\). If not, we remove the eigenvector \(u_n\) and pass to \(W_{n-1}:=\operatorname{span}\{u_1,\cdots,u_{n-1}\}\) and denote by \(e_i^{(n-1)}:=P_{W_{n-1}}e_i\) and denote by \[\label{stratification} \mathcal{S}_{n-1}:=\sum_{i=1}^se_i^{(n-1)}(e_i^{(n-1)})^*=P_{W_{n-1}}\mathcal{S}P_{W_{n-1}}.\tag{31}\] Moreover, we have the approximation error \[\label{approximationerror} \sum_{i=1}^s|e_i-e_i'|^2=\sum_{i=1}^s|(I-P_{W_{n-1}})e_i|^2=\operatorname{tr}((I-P_{W_{n-1}})\mathcal{S}(I-P_{W_{n-1}}))\leq \tau.\tag{32}\] In our applications, we will take \(T_1,\cdots,T_s\) to be elements of \(\operatorname{End}(E)\) and let \(\Gamma_\mathcal{S}\) be the covariance operator of the Gaussian sum \(\sum_{i=1}^sg_iT_i\): \(\Gamma_\mathcal{S}=\operatorname{Cov}(\sum_{i=1}^sg_iT_i)\). In this case, the covariance is given by the following operator \[\Gamma_\mathcal{S}:M_d(\mathbb{C})\to M_d(\mathbb{C}),\]where \[\label{equations8770} \Gamma_\mathcal{S}:=\sum_{i=1}^s T_i\otimes T_i^*.\tag{33}\] The same subspace stratification 31 as above can be applied to the PSD matrix \(\Gamma_\mathcal{S}\).

Then we consider a more general Gaussian with product matrices \[X=\sum_{i=1}^m\sum_{j=1}^n g_{ij}T_iB_j\]where \(g_{ij}\) are i.i.d. standard complex Gaussians. Let \(\mathcal{H}\) be a linear subspace of \(M_d\mathbb{(}C)\) invariant under left \(T_i\) action. For each \(T_i\), the left multiplication operator is defined as \[L_i:\mathcal{H}\to\mathcal{H},\quad L_i(B)=T_iB.\]Then its Hilbert-Schmidt adjoint is \(L_i^*(A)=T_i^*A\).

Denote by the covariance operator of \(B_j\) as \[\label{equations877} \Gamma_B:=\sum_{j=1}^n B_j\otimes B_j^*,\tag{34}\] then one can verify that the covariance operator of \(X\) is \[\Gamma_X:=\sum_{i=1}^m L_i\Gamma_B L_i^*.\]Furthermore, suppose that \(B\) gives a linear subspace \(V\) such that \(\Gamma_B\geq\mu P_V\), then denote by \[S_{T,V}:=\sum_{i=1}^m L_iP_VL_i^*,\]one must have \[\label{composedvariance} \Gamma_X\geq\mu S_{T,V}.\tag{35}\]

4.2 LSV via the net argument: active profile case↩︎

When we apply a net argument to the kernel equation \[(\mathfrak{D}_aB)_k=B_k+\sum_{i,\ell}\overline{X_\ell(i,k)}R_\ell^*B_i\]we need to take into account two degeneracies:

1. The covariance operator defined by \(B_i\) is positively definite on the linear subspace spanned by \(B_i\), but some eigenvalues are too small so that the operator is almost degenerate in some directions;

2. The operator \(\Psi_E\) on the subspace spanned by \(E\) has enough nonzero singular directions, but some singular values are too small and some directions are nearly degenerate.

We will first handle the second degeneracy by considering \(Y_\sigma(E)\) for certain nonzero threshold values of \(\sigma\) in this section. We first assume that the first degeneracy does not occur up to a threshold, see the following definition. The degenerate \(B_i\)-profile case will be settled in the next section via approximation.

We shall use the following notation: for any measurable event \(L\subset\Omega\), \[\mathbb{P}^{\Omega_{\text{good}}}(L)=\mathbb{P}(L\cap\Omega_{\text{good}}).\]

Now we carry out the net argument for LSV, assuming \(Y(E)=Y_\sigma(E)\) for some \(\sigma>0\):

The restriction to \(\mathcal{W}(d,\sigma)\) means that we assume all nonzero singular values of \(\Psi_E\) are larger than \(\sigma\). We will remove this restriction later.

We now remove the restriction to \(\mathcal{W}(d,\sigma)\) in Proposition 20. The idea is as follows:

The proof of this fact is evident. Since the iteration ?? is only done finitely many times, we must be able to find the finite constant \(\operatorname{Mag_d(D_d)}\), which is essentially a function of \(D_d\) (save for the fixed parameter \(m,d\).) We take a dyadic decomposition for the range:

When there is a large gap in the singular values, we arrive at the following similar conclusion as in Proposition 20:

Combining all the above cases, we conclude with the following Proposition:

4.3 Non-regular profiles and proof completion↩︎

We shall use the following simple approximation result for a profile \(B\) by a regular profile \(B'\) living in a vector space of smaller dimension:

Now we can complete the proof of Theorem 13. The idea is to use Lemma 5 and choose the constants \(D_1,D_2,\cdots\) inductively such that \(D_i\) is much larger than \(D_{i-1}\) and thus the approximation error does not ruin the established least singular value estimate.

5 Brown measure limit and convergence to Brown measure↩︎

In this section we complete the proof of Theorem 2. This part of the argument is essentially the same as in [1], Section 8. While [1] only considered quadratic polynomials in Ginibre because their least singular value estimates are only proven for quadratics, the resulting convergence to Brown measure conditioned on a known least singular value estimate holds for polynomials of any degree. We still present the main steps here not only for the sake of completeness, but also for two more reasons: (1) our least singular value estimate does not hold for \(z=\mathfrak{p}(0)\) and is not uniform for \(z\), but we show that this does not prevent us from using the same convergence argument; and (2) when we adapt the proof to non-Gaussian cases in Section 6, several technical steps need to be reworked.

For any \(z\in\mathbb{C}\) we set \[\nu_N^z:=\mu_{(zI_N-P^N)(zI_N-P^N)^*}\]where we denote \(P^N=\mathfrak{p}(X_1^N,\cdots,X_n^N)\). Applying Green’s formula we have \[\label{thiswillverify}\int_\mathbb{C}\psi(z)d\mu_{P^N}(z)=\frac{1}{4\pi}\int_\mathbb{C}\Delta\psi(z)\int_0^\infty\log(x)d\nu_N^z(x)dz.\tag{45}\] Then to justify the convergence, we prove in the following three steps:

1. For each fixed \(z\in\mathbb{C}\) the measure \(\nu_N^z\) converges weakly almost surely to a probability measure \(\nu^z\) on \(\mathbb{R}_+\) which can be identified.

2. For almost every \(z\in\mathbb{C}\), we have that the integral \(\int_{\mathbb{R}_+}\log (x)d\nu_N^z(x)\) converges to \(\int_{\mathbb{R}_+}\log(x)d\nu^z(x)\) in probability. This step uses Theorem 3.

3. In probability, the function \(z\mapsto \int_{\mathbb{R}_+}\log(x)d\nu_N^z(x)\) converges in \(L^1\) to the function \(z\mapsto \int_{\mathbb{R}_+}\log(x)d\nu^z(x)\) so that \(\mu_{P^N}\) converges in distribution to the limit that is identified as \(\nu_{\mathfrak{p}}(c_1,\cdots,c_n)\).

For non-Gaussian distributions, the proof in Step [step33] does not need any change, but the proof of Step [step11] and Step [step22] will be modified in Section 6.

Proof of Step [step11]. Since \((zI-P^N)(zI-P^N)^*\) is self-adjoint in independent Ginibre matrices and their adjoints, this part directly follows from Voiculescu’s theorem [24]. The limiting measure \(\nu^z\) is the law of \(|z-\mathfrak{p}(c_1,\cdots,c_n)|^2\) in the sense of \(*\)-moments. Moreover, \(\nu^z\) is compactly supported for any fixed \(z\in\mathbb{C}\).

Proof of Step [step22]. Denote the event \[\mathcal{G}_N(z):=\{\|P^N\|\leq C_\mathfrak{p},\quad\sigma_{\text{min}}(z-P^N)\geq N^{-\beta/2}\}.\]Then by Theorem 3 and Fact 9, we can choose \(\beta\) large enough so that for any \(z\in\mathbb{C}:z\neq \mathfrak{p}(0)\), \(\mathbb{P}(\mathcal{G}_N(z))\) tends to one (although the rate may not be uniform in \(z\)).

For any smooth nonnegative function \(\chi_\epsilon\) vanishing on \([0,\epsilon/2]\) and equaling one on \([\epsilon,\infty)\), since we have that \[\limsup_{N\to\infty}\|P^N\|\leq C_\mathfrak{p}\quad a.s.,\]then Step [step11] tells us that we have convergence \[\lim_{N\to\infty}\int _0^\infty \chi_\epsilon(x)\log(x)d\nu_N^z(x)=\int_0^\infty\chi_\epsilon(x)\log(x) d\nu^z(x)\quad a.s.\] Therefore, we only need to prove that for any \(\delta,\delta'>0\) we can find an \(\epsilon\in(0,1)\) satisfying that \[\limsup_{N\to\infty}\mathbb{P}\left\{\mathbf{1}_{\mathcal{G}_N(z)}\left| \int_0^\epsilon\log x d\nu_N^z(x) \right|\geq\delta\right\} \leq\delta',\] which further boils down to proving, for each \(z\neq \mathfrak{p}(0)\), \[\lim_{\epsilon\to 0}\limsup_{N\to\infty}\mathbb{E}\left|\int_{N^{-\beta}}^\epsilon\log xd\nu_N^z(x)\right|=0,\] since there are no singular values in \([0,N^{-\beta}]\) on the event \(\mathcal{G}_N(z)\).

We define the Stieltjes transform of \(\nu^z\) and \(\mathbb{E}[\nu_N^z]\) as follows: for any \(\zeta\in\mathbb{C}\), \[g^z(\zeta)=\int_0^\infty\frac{1}{\zeta-x}d\nu^z(x),\quad g_N^z(\zeta)=\mathbb{E}[\int_0^\infty \frac{1}{\zeta-x}d\nu_N^z(x)] .\] We only consider a polynomial \(\mathfrak{p}\) of degree at least 1. By [1], Lemma 8.1 (the proof actually works for \(\mathfrak{p}\) of all degrees, see Appendix 7 for a proof recall), for any fixed \(z\in\mathbb{C}\) we can find \(C,N_0>0\) and \(c_1,c_2\in(0,1)\) satisfying that for any \(\eta\in[N^{-c_1},1]\) and \(N\geq N_0\), we have \[\label{thisisfromref3} |\Im (g_N^z(i\eta))|\leq C\eta^{-c_2}.\tag{46}\] This estimate implies that for any \(x\in[N^{-c_1},1]\), we have \[\label{bythegaussianmodel} F_N^z(x):=\mathbb{E}[\nu_N^z([0,x])]\leq 2x|\Im(g_N^z(ix))|\leq 2Cx^{1-c_2}.\tag{47}\] Therefore, for some \(\alpha<c_1\) and any \(\epsilon<1\), \[\begin{align} &\mathbb{E}|\int_{N^{-\beta}}^\epsilon\log xd\nu_N^z(x)|\\&\leq -\int_{N^{-\beta}}^{N^{-\alpha}}\log xd\mathbb{E}[\nu_N^z(x)]-\int_{N^{-\alpha}}^{\epsilon}\log xd\mathbb{E}[\nu_N^z(x)]\\&\leq 2C\beta(\log N)N^{-\alpha(1-c_2)}+2C\frac{\epsilon^{1-c_2}}{1-c_2}-2C(\log\epsilon)\epsilon^{1-c_2}, \end{align}\] which tends to 0 as \(\epsilon\) is small enough. This completes Step [step22].

Proof of Step [step33]. Define the following two functions \[h_N(z):=\int_0^\infty\log xd\nu_N^z(x),\quad h(z)=\int_0^\infty\log xd\nu^z(x).\]We have proven \(h_N(z)\) converges to \(h(z)\) in probability for any \(z\neq\mathfrak{p}(0)\). For any compact subset \(K\), since the operator norm event \(\mathcal{A}_N:=\{\|P^N\|\leq C_\mathfrak{p}\}\) has probability \(1-o(1)\), we only need to verify the \(L^1\) convergence \[\lim_{N\to\infty}\mathbb{E}\left(\mathbf{1}_{\mathcal{A}_N}\int_{z\in K}|h_N(z)-h(z)|dz \right)=0,\] and this will verify 45 for twice continuously differentiable functions of bounded support. The bounded support condition is again removed since eigenvalues are almost surely bounded. To verify the convergence we check that they are uniformly bounded in \(L^2\): by definition, \[h_N(z)=\frac{2}{N}\sum_{j=1}^N\log|z-\lambda_j(P^N)|,\] then by Jensen, \[\label{ell2integrability} \mathbb{E}\left[\mathbf{1}_{\mathcal{A}_N}\int_K|h_N(z)|^2dz\right]\leq 4\sup_{|\lambda|\leq C_\mathfrak{p}}\int_K|\log|z-\lambda||^2dz,\tag{48}\] and the same \(L^2\) norm upper bound holds for \(h\). Then \(\mathbf{1}_{\mathcal{A}_N}h_N\) converges to \(\mathbf{1}_{\mathcal{A}_N}h\) in \(L^1(\Omega\times K)\). Thus \(h_N\) converges in probability to \(h\) in \(L^1(K)\), so \(\mu_{P^N}\) converges to \(\nu_{\mathfrak{p}(c_1,\cdots,c_n)}\) in probability in the sense of distributions on \(K\). Enlarging \(K\) to contain all spectrum of \(\mathfrak{p}(c_1,\cdots,c_n)\) completes the proof of Theorem 2.

6 Extension to non-Gaussian cases↩︎

This section proves the non-Gaussian entry convergence result: Theorem 4. We only need to show that each specific Gaussian computation in this paper can be generalized to the non-Gaussian case, possibly with a weakened exponent.

We begin with an operator norm control:

6.1 Least singular value estimates↩︎

We first prove analogous least singular value estimates. We can generalize the proof of Theorem 13:

Then we can generalize Theorem 5 to the non-Gaussian case:

We can then generalize Theorem 3 to non-Gaussian entries via linearization:

The proof is immediate by combining Theorem 27 with Lemma 1 and Fact 10.

We have used the following comparison lemma for polynomial moments:

The proof of Lemma 6 is deferred to Appendix 7. The positive definiteness of \(M^\mu_{(d)}\) is equivalent to the fact that there does not exist a nonzero holomorphic polynomial \(q\in\mathbb{C}[z],\deg q\leq d\) such that \(q(\xi)=0\) a.s. Indeed, take any polynomial \(q(z)=\sum_{a=0}^d c_az_a\), then \[\mathbb{E}|q(\xi)|^2=c^*M^\mu_{(d)}c.\] So \(q(\xi)=0\) a.s. if and only if \(c^*M^\mu_{(d)}c=0\). When \(\mu\) has a density with respect to planar Lebesgue measure, then clearly such \(q\) does not exist, and thus \(M^\mu_{(d)}\) is positive definite.

We have also used the following (weaker) substitute for Carbery-Wright (Theorem 16), as the latter holds for all log-concave distributions but we do not assume log concavity here:

We also need the following estimate, which is a complex version of [37], Theorem 1.1.

Proposition 29, Lemma 7, Corollary 2 and Fact 30 are proven in Appendix 7.

6.2 Proof of Brown measure convergence: non-Gaussian case↩︎

In this final section we generalize the argument in Section 5 to the non-Gaussian case, thus completing the proof of Theorem 4. We again split the proof into Steps [step11], [step22] and [step33].

For Step [step11], since the \(X_i^N\) have i.i.d. entries of law \(\frac{1}{\sqrt{N}}\xi\) where \(\xi\) has mean 0, variance 1 and finite moments of all orders, the family \((X_1^N,\cdots,X_n^N)\) converges in \(*\)-moments in probability to the free circular family \((c_1,\cdots,c_n)\). This can be checked via the standard trace moment expansion since the only leading index configurations are given by the tree pairings which match each entry to its conjugate, and the contributions involving \(\mathbb{E}\xi^2\) have a lower order. This implies, for any \(k\geq 1\), \[\operatorname{tr}_N[(zI_N-P_N)(zI_N-P_N)^*]^k\to\tau(|z-\mathfrak{p}(c_1,\cdots,c_n)|^{2k})\] and thus by moment tightness, \(\nu_N^z\) converges weakly in probability towards a measure \(\nu^z=\operatorname{Law}(|z-\mathfrak{p}(c_1,\cdots,c_n)|^2)\).

For the proof of Step [step33], we only use (a) uniform \(L^2\) integrability 48 ; (b) pointwise convergence by Step [step22]; and (c) boundedness of \(\|P^N\|\) which holds on \(\Omega_{\text{high-prob}}\). Thus all the steps follow once Step [step22] is proved.

For Step [step22], we import estimate 47 in the Gaussian case from [1], Lemma 8.1, and the remaining arguments do not depend on the entry law. Thus, the only missing component is a non-Gaussian version of 47 , which is stated as the following Lemma 8. Having proven this, the Brown measure convergence in Theorem 4 is fully proven.

We have used the following perturbative estimate, see Appendix 7 for the proof.

7 Proofs of auxiliary results↩︎

This appendix contains the proofs of some technical results that are left unproven in the main text.

Acknowledgment↩︎

The author thanks Charles Bordenave and Ping Zhong for introducing the author to this very interesting problem.

Funding↩︎

The author is supported by a fellowship from IAS provided by the S.S. Chern Foundation for Mathematical Research Fund and the Fund for Mathematics.

References↩︎

---

1. By definition of Grassmannian distance, \(d_{\operatorname{Gr}}(E,E')=\|P_E-P_{E'}\|_{\text{op}}\).↩︎

2. [27], Theorem 2.10 considers a general random matrix of the form \(X=\sum_i Z_i\) where the \(Z_i\) are mutually independent, and associates to \(X\) a Gaussian random matrix \(G\) such that \(\mathbb{E}[X]=\mathbb{E}[G],\mathbb{E}[XX^*]=\mathbb{E}[GG^*]\). The comparison of resolvents of \(X\) and \(G\) in Theorem 2.10 involves two parameters: one is \(\mathbb{E}[(X-\mathbb{E}X)^2]\) which is \(O(1)\) in our case, and the other is \(\max_i\|Z_i\|\) which is at most \(N^{-0.1}\) by our truncation.↩︎