Abstract
Independent Haar-unitary random matrices and independent Haar-orthogonal random matrices are known to be asymptotically liberating ensembles, and they give rise to asymptotic free independence when used for conjugation of constant matrices. G. Anderson and B. Farrel showed that a certain family of discrete random unitary matrices can actually be used to the same end. In this paper, we investigate fluctuation moments and higher-order moments induced on constant matrices by conjugation with asymptotically liberating ensembles. We show for the first time that the fluctuation moments associated with second-order free independence can be obtained from conjugation with an ensemble consisting of signed permutation matrices and the discrete Fourier transform matrix. We also determine fluctuation moments induced by various related ensembles where we do not get known expressions but others related to traffic free independence.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
1.1 Background
Random matrices are matrix-valued random variables that were first investigated in mathematical statistics [29] and then in nuclear physics [28]. Over the years, its study has evolved into a theory with applications to pure and applied sciences such as numerical analysis [6], analytic number theory [10], and wireless communications [24].
One of the main topics in random matrix theory is the study of limiting, or asymptotic, properties of random matrix ensembles. The term random matrix ensemble is used in the literature to refer to a sequence of random matrices \(\{X_{N}\}_{N=1}^{\infty }\), or a sequence of families of random matrices \(\{\{X_{N,i}\}_{i \in I}\}_{N=1}^{\infty }\), where the considered random matrices increase in size with respect to N. Their limiting properties are those arising from letting N go to infinity. Joint eigenvalue distributions, eigenvalues spacing, concentration inequalities, large deviation principles, maximal eigenvalues, and central limit theorems are some examples of limiting properties, for an introduction on these subjects one can consult [2].
Now, introduced by D. Voiculescu in his research on von Neumann algebras in [25], free probability theory has played a key role in the study of random matrices when multiple ensembles need to be considered. A main notion from free probability is that of asymptotic free independence.
Definition 1
Let I be a non-empty set. Suppose \(\{X_{N,i}\}_{N=1}^{\infty }\) is a random matrix ensemble for each \(i\in I\) where each \(X_{N,i}\) is a N-by-N random matrix. We say that \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i\in I\) are asymptotically freely independent if the following two conditions hold:
-
(AF.1)
for each index \(i \in I \) and every integer \(m\ge 1\) the limit
$$\begin{aligned} \displaystyle \lim _{N\rightarrow \infty } {\mathbb {E}}\left[ \textrm{tr} \left( {X_{N,i}^m} \right) \right] , \end{aligned}$$where \(\textrm{tr} \left( {\cdot } \right) \) denotes the normalized trace \(\frac{1}{N}\textrm{Tr} \left( {\cdot } \right) \), exists and
-
(AF.2)
for all integers \(m\ge 1\), all indexes \(i_1, i_2, \ldots , i_m \in I\) satisfying \(i_{1} \ne i_{2}, i_{2} \ne i_{3}, \ldots , i_{m-2} \ne i_{m-1}, i_{m-1} \ne i_{m}\), and \(i_{m} \ne i_{1}\) and all polynomials \(\textrm{p}_{1}, \textrm{p}_{2}, \ldots ,\textrm{p}_{m}\) in the algebra \({\mathbb {C}}[\textrm{x}]\), we have
$$\begin{aligned} \lim _{N\rightarrow \infty } {\mathbb {E}} \left[ {\textrm{tr} \left( {Y_{N,1} Y_{N,2} \cdots Y_{N,m}} \right) }\right] = 0 \end{aligned}$$where \(Y_{N,k} = \textrm{p}_{k} \left( X_{N,i_k} \right) - {\mathbb {E}} \left[ {\textrm{tr} \left( {\textrm{p}_{k} \left( X_{N,i_k} \right) } \right) }\right] I_{N}\).
The first connection between free probability and random matrices was established by D. Voiculescu when he showed in [26] that independent Gaussian unitary ensembles converge to free semicircular random variables, a result which generalizes Wigner’s semicircular law and entails the asymptotic free independence of independent Gaussian unitary ensembles. The list of random matrix ensembles exhibiting asymptotic free independence has been extended since then, and it now includes: independent Wishart ensembles, independent Gaussian orthogonal ensembles, independent Haar-unitary distributed ensembles, independent Haar-orthogonal distributed ensembles, among others. The monograph [27] and the book [20] are standard introductions to free probability, and the recent monograph [18] is an excellent source presenting multiples directions in which the relation between free probability and random matrices has been extended.
Another result due to D. Voiculescu in [26], and subsequently generalized by other authors, states that conjugation by independent Haar-unitary distributed random matrices gives rise to asymptotic free independence. More concretely, assume \(D_{N,i}\) is a self-adjoint N-by-N deterministic matrix for each index \(i \in I\) and each integer \(N\ge 1\) and suppose that
for all \(i \in I \) and \(m\ge 1\); the random matrix ensembles \(\{ D^{}_{N,i} \}_{N=1}^{\infty }\) with \(i \in I\) might or might not be asymptotically freely independent; however, if \(\{U_{N,i}\}_{i \in I}\) is a family of independent N-by-N Haar-unitary distributed random matrices for each \(N\ge 1\), then \(\{ U^{}_{N,i} D^{}_{N,i} U^{*}_{N,i} \}_{N=1}^{\infty }\) with \(i \in I\) are asymptotically freely independent. The same conclusion holds if each \(U_{N,i}\) is Haar-orthogonal distributed, see [13].
Aiming to enclose all of those unitary random matrix ensembles that give rise to asymptotic free independence when used for conjugation, B. Farrell and G. Anderson introduced in [1] the notion of asymptotically liberating random matrix ensembles.
Definition 2
Suppose \( U_{N,i} \) is an N-by-N unitary random matrix for each index \(i \in I\) and each integer \(N\ge 1\). The unitary random matrix ensemble \(\left\{ \left\{ U_{N,i} \right\} _{i\in I}\right\} _{N=1}^{\infty }\) is asymptotically liberating if for all indexes \(i_{1},i_{2},\ldots ,i_{m} \in I\) with \(i_1 \ne i_2, i_2 \ne i_3, \ldots , i_{m-1}\ne i_m\), and \(i_m \ne i_1\) there exists a constant \(C > 0\) depending only on the indexes \(i_{1},i_{2},\ldots ,i_{m}\) such that
for all integers \(N \ge 1\) and all matrices \(A_{N,1}, A_{N,2}, \ldots , A_{N,m} \in \text {Mat}_N ({\mathbb {C}})\) each of trace zero.
It follows immediately from the above definition that asymptotically liberating ensembles gives rise to asymptotic free independence when used for conjugation. Indeed, suppose \(\{ \{ U_{N,i} \}_{i\in I}\}_{N=1}^{\infty }\) is an asymptotically liberating ensemble and assume \(\{ D^{}_{N,i} \}_{N=1}^{\infty }\) with \(i \in I\) satisfy (1.1). Letting \(X_{N,i} = U^{}_{N,i} D^{}_{N,i} U^{*}_{N,i}\), we have (1.1) implies (AF.1) from Definition 1; moreover, if each \(Y_{N,k}\) is as in (AF.2) from Definition 1, then
where \(A_{N,k}\) denotes the matrix of trace zero \(\textrm{p}_{k} ( D^{}_{N,i_k}) - \textrm{tr} ( \textrm{p}_{k} ( D^{}_{N,i_k} )) I_{N} \), but (1.1) also implies that \(\sup _{N} \left\| {A^{}_{N,k}} \right\| < \infty \), and hence, (AF.2) holds. As it was intended, independent Haar-unitary random matrix ensembles and independent Haar-orthogonal random matrix ensembles are among those unitary random matrix ensembles shown to be asymptotically liberating, see Theorem 2.8 in [1] or Lemma 3.
A key feature of asymptotic free independence is that it provides us with universal rules to compute limiting mixed moments out of individual ones. A limiting mixed moment of the ensembles \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i\in I\) is a limit of the form
where at least two of the indexes \(i_1, i_2,\ldots ,i_m \in I\) are distinct and none of them depend on N. For instance, if \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i\in I\) are asymptotically free independent and \(i_{1}, i_{2} \in I\) are distinct, one can show that
where \( \alpha _{m}^{(i)}\) denotes \(\lim _{N\rightarrow \infty } {\mathbb {E}}[\textrm{tr}(X_{N,i}^m) ]\) and is called the m-th limiting individual moment of \(\{X_{N,i}\}_{N=1}^{\infty }\). The relation above, and any other derived from asymptotic free independence to compute mixed moments, is called universal since it does not depend on any particular choice of \(i_{1}\) and \(i_{2}\) and it only requires \(\{X_{N,i_{1}}\}_{N=1}^{\infty }\) and \(\{X_{N,i_{2}}\}_{N=1}^{\infty }\) to be asymptotically freely independent.
At this point, one might wonder if there are universal rules for computing limiting mixed moments of higher order out of individual ones. A limiting moment of n-th order of the ensembles \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i \in I\) is defined to be a limit of the form
where \({\mathfrak {c}}_{n}[\cdot , \ldots , \cdot ]\) denotes the n-th classical cumulant and each \({\widetilde{X}}_{N,k}\) is of the form
for some integer \(m_{k}\ge 1\) and some indexes \(i^{(k)}_{1},i^{(k)}_{2},\ldots ,i^{(k)}_{m_{k}} \in I\) not depending on N. The choice of the normalization factor \(N^{n-2}\) appearing in (1.3) is due to what has been observed for the behavior of (1.3) when each \(X_{N,i}\) is a Gaussian unitary ensemble. Since the limiting moment (1.3) is just a generalization of (1.2), we call it mixed if at least two of the indexes \(i^{(1)}_{1},\ldots ,i^{(1)}_{m_{1}},i^{(2)}_{1},\ldots ,\) \(i^{(2)}_{m_{2}},\ldots ,i^{(n)}_{1},\ldots , i^{(n)}_{m_{n}}\) are distinct, and individual, otherwise.
The most studied moments of higher order are moments of second order, also known as fluctuation moments. A fluctuation moment of the ensembles \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i \in I\) is then a limit of the form
for some integers \(m_{1},m_{2}\ge 1\) and indexes \(i_{1},i_{2},\ldots ,i_{m_{1}},i_{m_{1}+1},i_{m_{1}+2},\ldots ,i_{m_{1}+m_{2}} \in I\). A common practice in free probability theory to determine combinatorially (1.3), or (1.4), is that of calculating limiting moments of products of cyclically alternating and centered random matrices, as in (AF.2) from Definition 1. For fluctuation moments, this means one must consider limits of the form
where \( Y_{N,k}\) and \(Z_{N,l}\) are given by
for all polynomials \(\textrm{p}_{1}, \textrm{p}_{2},\ldots , \textrm{p}_{m_{1}}, \textrm{q}_{1},\textrm{q}_{2}, \ldots , \textrm{q}_{m_{2}} \in {\mathbb {C}}[\textrm{x}]\) and all indexes \(i_1, i_2, \ldots , i_{m_{_1}}, j_{1},j_{2}, \ldots , j_{m_{_2}} \in I\) satisfying the condition
Analyzing the fluctuation moments of complex Gaussian and complex Wishart random matrix ensembles, J. Mingo and R. Speicher found a relation between individual and mixed moments of first and second order and introduced in [16] the notion of asymptotic free independence of second order.
Definition 3
We say that the random matrix ensembles \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i\in I\) are asymptotically freely independent of second order if they are asymptotically freely independent and the following three conditions are satisfied:
-
(ASOF.1)
for each index \(i \in I\) and all integers \(m,n \ge 1\) the limit
$$\begin{aligned} \displaystyle \lim _{N\rightarrow \infty } \textrm{Cov} \left[ \textrm{Tr} ( {X_{N,i}^m} ), \textrm{Tr} ( {X_{N,i}^n} ) \right] \end{aligned}$$exists,
-
(ASOF.2)
for all integers \(m_{1},m_{2} \ge 1\), all indexes \(i_1, i_2, \ldots , i_{m_{_1}}, j_{1},j_{2},\ldots ,j_{m_{_2}} \in I\) satisfying (1.6), and all polynomials \(\textrm{p}_{1}, \textrm{p}_{2},\ldots , \textrm{p}_{m_{1}}, \textrm{q}_{1},\textrm{q}_{2}, \ldots , \textrm{q}_{m_{2}}\) in the algebra \({\mathbb {C}}[\textrm{x}]\), if we take
$$\begin{aligned} Y_{N}=Y_{N,1} Y_{N,2} \cdots Y_{N,m_{1}} \quad \text { and } \quad Z_{N} = Z_{N,1} Z_{N,2} \cdots Z_{N,m_{2}} \end{aligned}$$with \(Y_{N,k}\) and \(Z_{N,l}\) given by (1.5) for \(1 \le k \le m_{1}\) and \(1 \le l \le m_{2}\), we have
$$\begin{aligned} \lim _{N\rightarrow \infty } \textrm{Cov} \left[ \textrm{Tr} ( { Y_{N} } ), \textrm{Tr} ( { Z_{N} } ) \right] = \delta _{m_{1},m_{2}} \lim _{N\rightarrow \infty } \sum ^{m_{1}}_{l=1}\prod ^{m_{2}}_{k=1} {\mathbb {E}} \left[ {\textrm{tr} \left( {Y_{N,k}Z_{N,l-k}} \right) }\right] \end{aligned}$$(1.7)where \(l-k\) is taken modulo \(m_{2}\), and
-
(ASOF.3)
for every integer \(n\ge 3\), all polynomials \(\textrm{p}_{1}, \textrm{p}_{2},\ldots , \textrm{p}_{n}\) in the algebra of non-commutative polynomials \({\mathbb {C}} \left\langle \textrm{x}_{i} \mid i \in I \right\rangle \), letting \(Y_{N,k} = \textrm{p}_{k} \left( \{X_{N,i}\}_{i\in I} \right) \), we have
$$\begin{aligned} \lim _{N\rightarrow \infty } {\mathfrak {c}}_{n} \left[ \textrm{Tr} \left( {Y_{N,1}} \right) , \textrm{Tr} \left( {Y_{N,2}} \right) ,\ldots ,\textrm{Tr} \left( {Y_{N,n}} \right) \right] = 0 \end{aligned}$$
Similar to asymptotic free independence, asymptotic free independence of second order provides us with universal rules, via the conditions (ASOF.1) and (ASOF.2) above, to calculate limiting mixed fluctuation moments out of individual ones. Moreover, independent Gaussian unitary ensembles are asymptotically freely independent of second order and conjugation by independent Haar-unitary random matrix ensembles leads to asymptotic free independence of second order, see [16] and [15], respectively.
However, in contrast to moments of first order, fluctuation moments induced by Haar-unitary random matrix ensembles and those induced by Haar-orthogonal random matrix ensembles differ. Investigating fluctuation moments of independent Gaussian orthogonal ensembles, E. Redelmeier proved in [21] that if each \(\{X_{N,i}\}_{i \in I}\) forms a family of independent Gaussian orthogonal ensembles for every \(N\ge 1\), then the ensembles \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i\in I\) satisfy (ASOF.1) and (ASOF.3) from Definition 3 but (ASOF.2) has to be replaced by the following:
- (ASOF.2’):
-
for all integers \(m_{1},m_{2} \ge 1\), all indexes \(i_1, i_2, \ldots , i_{m_{_1}}, j_{1},j_{2},\ldots ,j_{m_{_2}} \in I\) satisfying (1.6), and all polynomials \(\textrm{p}_{1}, \textrm{p}_{2},\ldots , \textrm{p}_{m_{1}}, \textrm{q}_{1},\textrm{q}_{2}, \ldots , \textrm{q}_{m_{2}}\) in the algebra \({\mathbb {C}}[\textrm{x}]\), if we take
$$\begin{aligned} Y_{N}=Y_{N,1} Y_{N,2} \cdots Y_{N,m_{1}} \quad \text { and } \quad Z_{N} = Z_{N,1} Z_{N,2} \cdots Z_{N,m_{2}} \end{aligned}$$with \(Y_{N,k}\) and \(Z_{N,l}\) given by (1.5) for \(1 \le k \le m_{1}\) and \(1 \le l \le m_{2}\), we then have
$$\begin{aligned} \lim _{N\rightarrow \infty } \textrm{Cov} \left[ \textrm{Tr} ( {Y_{N}} ), \textrm{Tr} ( {Z_{N} } ) \right]&= \delta _{m_{1},m_{2}} \lim _{N\rightarrow \infty } \sum ^{m_{1}}_{l=1} \left( \prod ^{m_{2}}_{k=1} {\mathbb {E}} [ {\textrm{tr} ( {Y_{N,k}Z_{N,l-k}} ) } ] \right. \nonumber \\&\quad \left. + \prod ^{m_{2}}_{k=1} {\mathbb {E}} [ {\textrm{tr} ( {Y^{}_{N,k}Z^{T}_{N,l+k}} ) } ] \right) \end{aligned}$$(1.8)where \(l-k\) and \(l+k\) are taken modulo \(m_{2}\).
Asymptotically freely independent ensembles satisfying (ASOF.1), (ASOF.2’), and (ASOF.3) are called asymptotically freely independent of second order in the real sense. Generalizing the findings of E. Redelmeier in [21], it was shown by J. Mingo and M. Popa in [13] that independent orthogonally invariant ensembles are asymptotically freely independent of second order in the real sense, and therefore, the fluctuation moments induced by Haar-orthogonal ensembles are not described by (1.7) but (1.8) instead.
1.2 Objectives and Main Results
The aim of this paper is to investigate the behavior of the fluctuation moments, and higher-order moments, resulting from conjugation by asymptotically liberating ensembles. Since independent Haar-unitary and independent Haar-orthogonal are both asymptotically liberating but the fluctuation moments each of them induces are distinct, we already know that the induced fluctuation moments depend on the specific liberating ensemble used for conjugation. However, it might well be the case that the relations in (1.7) and (1.8) cover all possible behaviors for fluctuation moments induced by liberating ensembles; our first result shows that this is actually not the case, adding even more evidence that fluctuation moments are more intricate than its first-order counterpart.
It is illustrative and good for comparison to restate what the relations in (1.7) and in (1.8) yield when Haar-unitary ensembles and Haar-orthogonal ensembles are used of conjugation. So, let us assume \(X_{N,1} = U^{}_{N,1} D^{}_{N,1} U^{*}_{N,1}\) and \(X_{N,2} = U^{}_{N,2} D^{}_{N,2} U^{*}_{N,2}\) for each integer \(N \ge 1\) where each sequence \(\{ D^{}_{N,i} \}_{N=1}^{\infty }\) satisfies (1.1) and \(\{ U_{N,1}, U_{N,2} \}_{N=1}^{\infty }\) is an asymptotically liberating ensemble. Note that if the random matrices \(Y_{N}\) and \(Z_{N}\) are as in (ASOF.2) from Definition 3, then we can write
and
where \(A^{}_{N,k}\) and \(B^{}_{N,l}\) are deterministic matrices of trace zero given by
for \(1 \le k \le 2m_{1}\) and \(1 \le l \le 2m_{2}\). For simplicity, and without loss of generality, let us assume \(i_{1} = j_{1}\). Now, if \(U_{N,1}\) and \(U_{N,2}\) are independent Haar-unitary ensembles, it follows from (AF.2) in Definition 1 and the relation in (1.7) that the covariance \( \textrm{Cov} \left[ \textrm{Tr} ( { Y_{N} } ), \textrm{Tr} ( { Z_{N} } ) \right] \) converges to
as N goes to infinity. On the other hand, if \(U_{N,1}\) and \(U_{N,2}\) are independent Haar-orthogonal ensembles, then (AF.2) and (1.8) imply that \( \textrm{Cov} \left[ \textrm{Tr} ( { Y_{N} } ), \textrm{Tr} ( { Z_{N} } ) \right] \) converges to
as N goes to infinity. Note that (1.1) alone guarantees the existence of each of the limits above if each matrix \(D_{N,i}\) equals its transpose, regardless of what \(U_{N,1}\) and \(U_{N,2}\) are.
Another ensemble shown to be asymptotically liberating, see Corollary 3.2 in [1], and a main focus in this paper, is the unitary random matrix ensemble \(\{W_{N}, H_{N}W_{N} /\sqrt{N}, X_{N}H_{N}W_{N}/\sqrt{N} \}\) where \(W_{N}\) is a random N-by-N signed permutation matrix, \(X_{N}\) is a random N-by-N signature matrix independent from \(W_{N}\), and \(H_{N}\) is the N-by-N discrete Fourier transform matrix. Our first result shows that if we take pairs of distinct unitary matrices \(U_{N,1}\) and \(U_{N,2}\) from \(\{W_{N}, H_{N}W_{N} /\sqrt{N}, X_{N}H_{N}W_{N}/\sqrt{N} \}\) and use them for conjugation, then the resulting fluctuation moments vary with each pair and differ from those in (1.12) and in (1.13).
Theorem 1
Let \(D_{N,1}\) and \(D_{N,2}\) be N-by-N self-adjoint matrices for each integer \(N\ge 1\) so that each \(\{ D^{}_{N,i} \}_{N=1}^{\infty }\) satisfies (1.1).
Suppose \(X_{N,1} = U^{}_{N,1} D^{}_{N,2} U^{*}_{N,1} \) and \(X_{N,2} = U^{}_{N,2} D^{}_{N,2} U^{*}_{N,2} \) where \(U_{N,1}\) and \(U_{N,2}\) are distinct matrices from \(\{W_{N}, H_{N}W_{N} /\sqrt{N}, X_{N}H_{N}W_{N}/\sqrt{N} \}\).
If \(Y_{N}\) and \(Z_{N}\) are given by \(Y_{N}=Y_{N,1} Y_{N,2} \cdots Y_{N,2m_{1}}\) and \(Z_{N} = Z_{N,1} Z_{N,2} \cdots Z_{N,2m_{2}}\) where \(Y_{N,k}\) and \(Z_{N,l}\) are defined as in (1.5) for some polynomials \(\textrm{p}_{1}, \textrm{p}_{2},\ldots , \textrm{p}_{2m_{1}}, \textrm{q}_{1}, \textrm{q}_{2}, \ldots , \textrm{q}_{2m_{2}}\in {\mathbb {C}}[\textrm{x}]\) and some indexes \(i_1, i_2, \ldots , i_{2m_{_1}}, j_{1},j_{2},\ldots ,j_{2m_{_2}} \in \{1,2\}\) satisfying (1.6) and \(i_{1}=j_{1}\), then the following holds:
-
(1)
\(U_{N,1} = W_{N} \) and \(U_{N,2}= H_{N}W_{N}/\sqrt{N}\) implies
$$\begin{aligned}&\textrm{Cov} \left[ \textrm{Tr} ( { Y_{N} } ), \textrm{Tr} ( { Z_{N} } ) \right] \\&\quad = \delta _{m_{1},m_{2}} \sum _{l=1}^{m_{1}} \left( \prod _{k=1}^{2m_{1}} \textrm{tr} \left( {A_{N,k} B_{N,2l-k}} \right) + \prod _{k=1}^{2m_{1}} \textrm{tr} \left( {A^{}_{N,k} B_{N,2l+k-1}^{T}} \right) \right) \\ {}&\qquad + O \left( N^{-\frac{1}{2 }}\right) \end{aligned}$$ -
(2)
\(U_{N,1} = W_{N} \) and \(U_{N,2}= X_{N}H_{N}W_{N}/\sqrt{N}\) implies
$$\begin{aligned}&\textrm{Cov} \left[ \textrm{Tr} ( { Y_{N} } ), \textrm{Tr} ( { Z_{N} } ) \right] \\&\quad = \delta _{m_{1},m_{2}} \sum _{l=1}^{m_{1}} \left( \prod _{k=1}^{2m_{1}} \textrm{tr} \left( {A_{N,k} B_{N,2l-k}} \right) + \prod _{k=1}^{2m_{1}} \textrm{tr} \left( {A_{N,k} \circ B_{N,2l+k-1}} \right) \right) \\ {}&\qquad + O \left( N^{-\frac{1}{2 }}\right) \end{aligned}$$ -
(3)
\(U_{N,1} = H_{N}W_{N}/\sqrt{N} \) and \(U_{N,2}= X_{N}H_{N}W_{N}/\sqrt{N}\) implies
$$\begin{aligned} \textrm{Cov} \left[ \textrm{Tr} ( { Y_{N} } ), \textrm{Tr} ( { Z_{N} } ) \right]= & {} \sum _{l_{1}=1}^{2m_{1}} \sum _{l_{2}=1}^{2m_{2}} \prod _{k_{1}=1}^{m_{1}} \textrm{tr} \left( {A_{N,l_{1}+k_{1}-1} A_{N,l_{1}-k_{1}}} \right) \cdot \\{} & {} \prod _{k_{2}=1}^{m_{2}} \textrm{tr} \left( {B_{N,l_{2}+k_{2}-1} B_{N,l_{2}-k_{2}}} \right) \\{} & {} + \delta _{m_{1},m_{2}} \sum _{l=1}^{2m_{1}} \left( \prod _{k=1}^{2m_{1}} \textrm{tr} \left( {A_{N,k}B_{N,l-k}} \right) \right) + O \left( N^{-\frac{1}{2 }}\right) \end{aligned}$$
with \(A_{N,k}\) and \(B_{N,l}\) defined as in (1.11), \(2l-k\), \(2l+k-1\), \(l_{1}+k_{1}-1\), \(l_{1}-k_{1}\), and \(l-k\) interpreted modulo \(2m_{1}\), and \(l_{2}+k_{2}-1\) and \(l_{2}+k_{2}\) interpreted module \(2m_{2}\).
The discovery of second-order behaviors deviating from second-order free independence, and second-order free independence in the real sense, is not new. From a more algebraic setting, the authors of [8] and [9] analyze fluctuation moments of matrices with entries from a possibly non-commutative unital algebra and obtain different relations from those mentioned above. Additionally, the fluctuation moments of symplectically invariant random matrices have been fully determined in [22]. In particular, the relations (1.12) and (1.13) must be replaced by
when considering conjugation by independent Haar-symplectic random matrix ensembles. We recap in Table 1 the fluctuation moments induced by conjugation with matrices uniformly distributed on classical compact groups and in Table 2 the fluctuation moments induced by conjugation with the matrices considered in this paper.
Notice (1.1) alone is not enough to guarantee the existence of limiting second-order behaviors in Theorem 1, in contrast to (1.12) and (1.13). For instance, if we want to take the limit as N goes to infinity in (3) from Theorem 1, we need \(\{D_{N,1}\}_{N=1}^{\infty }\) and \(\{D_{N,2}\}_{N=1}^{\infty }\) to have a joint limiting distribution, i.e., we need that the limit \(\lim _{N \rightarrow \infty } \textrm{tr}(D_{N,i_{1}}^{} D_{N,i_{2}}^{} \cdots D_{N,i_{m}}^{} ) \) exists for all integers \(m\ge 1\) and all indexes \(i_{1},i_{2},\ldots ,i_{m} \in \{1,2\}\). This shows we cannot expect a classification for universal products of second order, in the spirit of [19] or [23], encompassing all of the second-order behaviors exhibited by random matrices.
It would be desirable to have a master theorem encompassing all three cases in Theorem 1. However, in our analysis of fluctuation moments, we arrive to combinatorics that seem already too intricate when we consider each case separately. On this regard, although we make no explicit use of the theory of traffic free independence of C. Male, see [11], it is likely that our results will find a nice expression in terms of traffic algebras. Tools from traffic algebras have been already used in [12] to describe joint fluctuation moments of Wigner random matrices and deterministic matrices and their lack of second-order independence. Finally, it is pointed out in [7] that traffic algebras are closely related to \({\mathcal {A}}\)-tracial algebras, with both notions generalizing classical and free independence. We hope to describe the results in this paper in terms of traffic or \({\mathcal {A}}\)-tracial algebras in a future work.
Despite the fact that no pair of distinct unitary matrices \(U_{N,1}\) and \(U_{N,2}\) from the ensemble \(\{W_{N}, H_{N}W_{N} /\sqrt{N}, X_{N}H_{N}W_{N}/\sqrt{N} \}_{N=1}^{\infty }\) leads to asymptotic free independence of second order when used for conjugation, it turns out not much more is needed to achieve this end, at least, partially. More concretely, if \(U_{N,1}=W_{N,1}\) and \(U_{N,2}=H_{N}W_{N,2}/\sqrt{N}\) where \(W_{N,1}\) and \(W_{N,2}\) are independent N-by-N uniformly distributed signed permutation matrices, then the fluctuation moments induced by \(\{U_{N,1},U_{N,2}\}_{N=1}^{\infty }\) are the same as if \(U_{N,1}\) and \(U_{N,2}\) were independent Haar-unitary, i.e., the induced fluctuation moments are described by (1.12). Thus, we can think of \(\{W_{N,1},H_{N}W_{N,2} /\sqrt{N} \}_{N=1}^{\infty }\) as an asymptotically liberating ensemble of second order.
Theorem 2
Let \(D_{N,1}\) and \(D_{N,2}\) be N-by-N self-adjoint matrices for each integer \(N\ge 1\) so that each \(\{ D^{}_{N,i} \}_{N=1}^{\infty }\) satisfies (1.1). Suppose \(X_{N,1} = U^{}_{N,1} D^{}_{N,2} U^{*}_{N,1} \) and \(X_{N,2} = U^{}_{N,2} D^{}_{N,2} U^{*}_{N,2} \) where \(U_{N,1}=W_{N,1}\) and \(U_{N,2}=H_{N}W_{N,2}/\sqrt{N}\). Then, \(\{X_{N,1}\}_{N=1}^{\infty }\) and \(\{X_{N,2}\}_{N=1}^{\infty }\) are asymptotically freely independent and they satisfy (ASOF.1) and (ASOF.2) from Definition 3. In particular, if \(Y_{N}\), \(Z_{N}\), \(A_{N,k}\), and \(B_{N,l}\) are given as in the previous theorem, then
The main result in [1] gives sufficient conditions on a unitary random matrix ensemble to be asymptotically liberating. Using a different approach than the one of [1], we have been able to prove that, under the same conditions, a unitary random matrix ensemble not only is asymptotically liberating but also satisfies a natural generalization of the boundedness condition in Definition 2 to cumulants of any order. More concretely, we have the following lemma.
Lemma 3
Let \( U_{N,i} \) be an N-by-N unitary random matrix for each index \(i \in I\) and each integer \(N\ge 1\).
Suppose the unitary random matrix ensemble \({\mathcal {U}}=\{\{U_{N,{i}}\}_{{i} \in I}\}_{N=1}^{\infty }\) satisfies the following two conditions:
-
(I)
the families of random matrices \( \{ U^{*}_{N,i_{1}}U^{}_{N,i_{2}} \}_{i_{1}, i_{2} \in I} \) and \( \{ \textrm{W}^{*} U^{*}_{N,i_{1}}U^{}_{N,i_{2}} \textrm{W} \}_{i_{1}, i_{2} \in I} \) are equal in distribution for every N-by-N signed permutation matrix \(\textrm{W}\), and
-
(II)
for each positive integer m and indexes \(i_{1}, i_{2} \in I\) with \(i_{1} \ne i_{2} \) there is a constant \(C_m(i_1,i_2)\) independent from N such that
$$\begin{aligned} \Bigg \Vert \left( U^{*}_{N,i_{1}}U^{}_{N,i_{2}} \right) (j_{1},j_{2})\Bigg \Vert _{m} \le C_m(i_1,i_2) N^{-1/2} \end{aligned}$$for all integers \( j_{1},j_{2} \in \{1,2,\ldots , N\}\).
Now, given positive integers \(m_1, m_2, \ldots , m_n\), take \(m'_{k}=m'_{k-1}+m^{}_{k-1}\) for \(k=2,3,\ldots ,n\) with \(m'_{1}=0\) and consider the permutation \(\gamma = (1,2,\ldots , m'_{1}+ m_{1})(m'_{2}+1,m'_{2}+2, \ldots , m'_{2}+ m_{2}) \cdots (m'_{n}+1, \ldots , m'_{n}+ m_{n})\). If some indexes \({i}_1,{i}_2, \ldots , {i}_m \in I\) are such that \({i}_{k} \ne {i}_{\gamma (k)}\) for \(k=1, 2, \ldots , m\) where \(m = m_1 + m_2 + \cdots + m_n\), then there exists a constant \(C({i}_1, {i}_2, \ldots , {i}_m)\) such that for
with \(A_{1},A_{2},\ldots ,A_{m} \in \textrm{M}_N({\mathbb {C}})\) each of trace zero, we have
The fact that a unitary random matrix ensemble \( \{ \{ U_{N,i} \}_{i\in I} \}_{N=1}^{\infty }\) satisfying (I) and (II) above is asymptotically liberating can now be seen as a particular case of the previous lemma. Moreover, if \(U_{N,i_{1}}\) and \(U_{N,i_{2}}\) are independent Haar-unitary (resp. Haar-orthogonal), then \(U^{*}_{N,i_{1}}U^{}_{N,i_{2}}\) is also Haar-unitary (resp. Haar-orthogonal), and hence, \(U^{*}_{N,i_{1}}U^{}_{N,i_{2}}\) satisfies (I) and (II) above. Therefore, independent Haar-unitary (Haar-orthogonal) random matrix ensembles are asymptotically liberating.
The customary definition of asymptotic free independence for random matrix ensembles involves the convergence of a sequence of linear functionals on non-commutative polynomials, see Proposition 14 and the comment right after its proof. In a similar way, multi-linear functionals on non-commutative polynomials can be used to analyze the behavior of moments of higher order, allowing us to show that unitary random matrix ensembles satisfying (I) and (II) above induce the bounded cumulants property when used for conjugation.
Theorem 4
Let \(D_{N,i}\) be a self-adjoint N-by-N deterministic matrix, and let \( U_{N,i} \) be an N-by-N unitary random matrix for each index \(i \in I\) and each integer \(N\ge 1\). Suppose the unitary random matrix ensemble \( \{ \{ U_{N,i} \}_{i\in I} \}_{N=1}^{\infty }\) satisfies (I) and (II) from the previous lemma and (1.1) holds. Then, the ensemble \( \{ \{ U^{}_{N,i}D^{}_{N,i}U_{N,i}^{*} \}_{i \in I} \}_{N=1}^{\infty }\) has the bounded cumulants property; namely, for all polynomials \(\textrm{p}_{1}, \textrm{p}_{2}, \textrm{p}_{3}, \ldots \) in the algebra of non-commutative polynomials \({\mathbb {C}}\left\langle \textrm{x}_{i} \mid {i \in I} \right\rangle \) taking \(Y_{N,k}= \textrm{p}_{k} (\{U^{}_{N,i}D^{}_{N,i}U^{*}_{N,i} \}_{i \in I} )\) we have
for every integer \(n \ge 1\).
The term bounded cumulants property is borrowed from [14] where it is used to prove several results concerning the limiting behavior of unitarily invariant random matrix ensembles and some other random matrix ensemble with this property.
A few technical comments are worth before we present the organization of the paper. Bounds of graph sums of square matrices, see [17] or Sect. 3, and the relations (4.4) and (5.3) are some key components to our results. In particular, (4.4) reveals the n-th cumulant from Lemma 3 can be written a sum where each term is a product of a cumulant \({\mathfrak {c}}_n \left[ \pi \right] \) of the random variables \(( U^{*}_{N,i_{1}}U^{}_{N,i_{2}} ) (j_{1},j_{2})\) and a graph sum of the deterministic matrices \(A_{l}\). Sharp bounds for graph sums are provided in Theorem 5, so the behavior and existence of higher-order moments depend largely on the cumulants \({\mathfrak {c}}_n \left[ \pi \right] \), at least, in our approach. Estimates of \({\mathfrak {c}}_2 \left[ \pi \right] \) up to terms of order \(N^{-m-1/2}\) are enough for Theorems 1 and 2 and constitute some of our main technical results, see Proposition 17. The sharpness of our estimates for \({\mathfrak {c}}_2 \left[ \pi \right] \)—and, consequently, of the terms of order \(N^{-1/2}\) appearing in Theorems 1 and 2—is addressed in the last section. For higher-order moments with \(n\ge 3\), a finer description of \({\mathfrak {c}}_n \left[ \pi \right] \) than the one given here is required. A full description of \({\mathfrak {c}}_n \left[ \pi \right] \) for the unitary matrices from Theorems 1 and 2 would mean to write graph sums of the discrete Fourier transform as a power series in \(N^{1/2}\), such expression for arbitrary \(\pi \) and arbitrary N is unknown to us at the moment. For Haar-unitary and Haar-orthogonal ensembles, a full description of \({\mathfrak {c}}_n \left[ \pi \right] \) as a power series in \(N^{-2}\) is already available via the Weingarten Calculus from [4] and [5], so higher-order moments might be computed using (4.4) in this case.
1.3 Organization of this Paper
The rest of this paper is organized as follows. In Sect. 2, we introduce the main definitions and the main notation for partitions, classical cumulants, matrices, and non-commutative polynomials; we also establish the distribution of random signed permutation matrices and random signature matrices. In Sect. 3, we review and prove multiple results on graph sums of square matrices. Roughly speaking, a graph sum of square matrices is a sum of products of entries of square matrices with the constraint that some of the entries from distinct matrices are indexed by the same summation variable. Then, Sects. 4 and 5 are devoted to the proofs of our main results; concretely, Lemma 3 and Theorem 4 are proved in Sect. 4, whereas Theorems 1 and 2 are proved in Sect. 5. Finally, in Sect. 6, we give some concluding remarks including open questions and further research projects.
2 Preliminaries
2.1 Set Partitions, the Möbius Inversion Function, and Classical Cumulants
A partition of a non-empty set S is a set of non-empty and pair-wise disjoint subsets of S whose union is S, i.e., a set \(\pi \) is a partition of S if \(B \subset S\) and \(B \ne \emptyset \) for every \(B \in \pi \), \(B\cap B' \ne \emptyset \) implies \(B=B'\) for all \(B,B'\in \pi \), and \(\cup _{B \in \pi } B = S\). The elements of a partition are called blocks, a block is said to be even if it has even cardinality, and similarly, a block is said to be odd if it has odd cardinality. A partition containing only even blocks is called even, but if all of its blocks have exactly two elements, we refer to it as a pairing. The total number of block in partition \(\pi \) is denoted by \(\#(\pi )\) and we let P(S), \(P_{\text {even}}(S)\), and \(P_{2}(S)\) denote the set of all partitions of S, the set of all even partitions of S, and the set of all pairing partitions of S, respectively.
Example
The sets \(\theta _{1} = \{\{-1,-3,-2,2\},\{1,3\}\}\), \(\theta _{2} = \{\{-1,-2\},\{2\},\{1,-3,3\}\}\), and \(\theta _{3} = \{\{-1,-3\},\{1,3\},\{-2,2\}\}\) are all partitions of \(\{-1,1,2,-2,-3,3\}\). The partitions \(\theta _{1}\) and \(\theta _{3}\) are both even, but while \(\theta _{3}\) is a pairing, \(\theta _{1}\) is not. The partition \(\theta _{2}\) is neither even nor odd since it contains two odd blocks, \(\{2\}\) and \(\{1,-3,3\}\), and one even block, \(\{-1,2\}\).
We let [m] and \([\pm m ]\) denote the sets of integers \(\{1,2,\ldots , m\}\) and \(\{-1,1,-2,2,\ldots , -m, m \}\), respectively. The sets [m] and \([\pm m ]\) are used extensively in this paper, so we will omit the square brackets when referring to any of their sets of partitions. Thus, for instance, we write \(P_{\text {even}}(\pm m)\) instead of \(P_{\text {even}}([\pm m])\). Having fixed integers \(m_1, m_2 \ge 1\) and a partition \(\pi \in P(\pm (m_1 + m_2))\), we denote by \({\pi }_1\) and \({\pi }_2\) the restrictions of \({\pi }\) to \([\pm m_1]\) and \([\pm (m_1 + m_2) ] {\setminus } [\pm m_1]\), respectively.
Every partition \(\pi \in P(S)\) defines an equivalence relation, denoted by \(\sim _{\pi }\), that has the blocks of \(\pi \) as equivalence classes. Thus, given elements \(k,l \in S\), we write \(k \sim _{\pi } l\) only if k and l belong to the same block of \(\pi \). With this notation in mind, a partition \(\pi \in P( \pm m )\) is called symmetric if \(k \sim _{\pi } l\) implies \(-k \sim _{\pi } -l\).
The set of partitions P(S) becomes a partially ordered set with the partial order \(\le \) defined as follows: given partitions \(\pi \) and \(\theta \) in P(S), we write \(\pi \le \theta \), and say that \(\pi \) is a refinement of \(\theta \), if every block of \(\pi \) is contained in some block of \(\theta \). Note that \(\pi \le \theta \) if and only if \(k \sim _{\pi } l\) implies \(k \sim _{\theta } l \) for all \(k,l \in S\). In the previous example, the partition \(\pi _{3}\) is a refinement of \(\pi _{1}\), and there is no other refinement between \(\pi _{1}\), \(\pi _{2}\), and \(\pi _{3}\).
Consider now the function \(\zeta : P(S) \times P(S) \rightarrow \{1,0\}\) defined by
This function is called the zeta function of P(S). It turns out that if S is a finite set, then the system of equations
determines a function \(\mu : P(S) \times P(S) \rightarrow {\mathbb {Z}}\) called the Möbius function of P(S) which can be explicitly computed, but first, let us establish the convention that whenever we write \(\eta =\{B_{i_1},B_{i_2},\ldots ,B_{i_r}\}\) for a partition \(\eta \), it is always assumed that blocks \(B_{i_k}\) and \(B_{i_l}\) are the same only if \(i_k=i_l\). Suppose now we are given partitions \(\pi \) and \(\theta \) in P(S). If \(\pi \le \theta \), we can write \(\theta = \{B_1, B_2,\ldots , B_{r}\}\) and \(\pi =\{B_{1,1},B_{1,2}, \ldots , B_{1,m_1},\ldots , B_{n,m_r} \}\) with \(B_{k} = \cup _{l=1}^{m_k}B_{k,l}\) for each k, and, in this case, we have
On the other hand, if \(\pi \) is not a refinement of \(\theta \), we have \(\mu (\pi ,\theta ) = 0\). The Möbius inversion formula states that given arbitrary functions \(f,g:P(S) \rightarrow {\mathbb {C}}\), we have the relation
The computation of Möbius function, Eq. (2.2), and the Möbius inversion formula, Eq. (2.3), is well known, and their proofs can be found in [20, Lecture 10].
Let \((\Omega ,{\mathcal {F}},P)\) be a classical probability space, and let \(L^{-\infty }(\Omega ,{\mathcal {F}},P)\) denote the set of complex-valued random variables on \((\Omega ,{\mathcal {F}},P)\) with finite moments of all orders. The classical n-th cumulant on \(L^{-\infty }(\Omega ,{\mathcal {F}},P)\) is the n-linear functional \({\mathfrak {c}}_{n}: L^{-\infty }(\Omega ,{\mathcal {F}},P) \times \cdots \times L^{-\infty }(\Omega ,{\mathcal {F}},P) \rightarrow {\mathbb {C}} \) defined by
for random variables \(x_1, x_2, x_3,\ldots , x_n \in L^{-\infty }(\Omega ,{\mathcal {F}},P)\) and where \({\mathbb {E}}[ \cdot ]\) denotes the corresponding expected value. Note that if \(x_{k}\) is a constant for some \(k \in [n]\) and \(n \ge 2\), then \( {\mathfrak {c}}_{n}[x_1, x_2,\ldots , x_n] = 0 \).
2.2 The Kernel Notation, Tuples, and Permutations
Let \(S_{1}\) and \(S_{2}\) be non-empty sets. We make the convention that for a function \({\textbf{j}}: S_{1} \rightarrow S_{2}\), we put \(j_{k} = {\textbf{j}}(k)\) for every \(k \in S_{1}\); additionally, if \(S_{1} = [\pm m] \) for some integer \(m \ge 1\), we identify the function \({\textbf{j}}: S_{1} \rightarrow S_{2}\) with the tuple \((j_{-1},j_{1},j_{-2},\ldots ,j_{-m},j_{m})\). Moreover, the kernel of a function \({\textbf{j}}: S_{1} \rightarrow S_{2}\), denoted by \( \textrm{ker} \left( {{\textbf{j}}} \right) \), is defined as the partition of \(S_{1}\) whose blocks are all of the non-empty pre-images of \({\textbf{j}}\), i.e.,
The group of all permutations on a non-empty set S is denoted by \(\textrm{Sym}(S)\); however, if \(S=[m]\) or \(S = [\pm m]\) for some positive integer m, we simply write \(\textrm{Sym}(m)\) and \(\textrm{Sym}(\pm m)\), respectively. Given permutations \(\sigma _{l} \in \textrm{Sym}(S_l)\) for \(l=1,2\), we let \({\textbf{j}} \circ \varvec{\sigma }_{1}: S_{1} \rightarrow S_{2}\) and \( \varvec{\sigma }_{2} \circ {\textbf{j}}: S_{1} \rightarrow S_{2}\) denote the usual composition of functions, so we have
Example
The function \({\textbf{j}}:[\pm 3] \rightarrow [4]\) given by
or, equivalently, \( (j_{-1},j_{1},j_{-2},j_{2},j_{-3},j_{3}) = (4,1,3,4,1,4)\), has kernel
Additionally, if \(\sigma _{1} \in \textrm{Sym}(\pm 3)\) is given \(\sigma _{1} (k)=-k\) for every \(k \in [\pm 3]\) and \(\sigma _{2} \in \textrm{Sym}(4)\) is the cyclic permutation (1, 2, 3, 4), then \( {\textbf{j}} \circ \varvec{\sigma }_{1} = (1,4,4,3,4,1) \) and \( \varvec{\sigma }_{2} \circ {\textbf{j}} = (1,2,4,1,2,1) \).
Given a permutation \(\sigma \in \textrm{Sym}(S)\) and a partition \(\pi \in P(S)\), we let \(\sigma \circ \pi \) be the partition in P(S) given by
The map \(\pi \mapsto \sigma \circ \pi \) is a poset automorphism; in particular, it is order-preserving, so for all partitions \(\pi , \theta \in P(S_{})\) we get
Remark
Note that a partition \(\pi \in P(S_{1})\) and a function \({\textbf{j}}: S_{1} \rightarrow S_{2}\) satisfy \(\pi \le \textrm{ker} \left( {{\textbf{j}}} \right) \) if only if the function \({\textbf{j}}\) is constant when restricted to each of the blocks of \(\pi \), i.e., \(j_{k} = j_{l}\) whenever \(k,l \in B\) for some block \(B \in \pi \).
Moreover, for any permutations \(\sigma _{l} \in \textrm{Sym}(S_{l})\) with \(l=1,2\), we have that \( \textrm{ker} \left( { {\textbf{j}} \circ \varvec{\sigma }_{1} } \right) = \sigma ^{-1}_{1} \circ \textrm{ker} \left( {{\textbf{j}}} \right) \) and \( \textrm{ker} \left( {{\textbf{j}}} \right) = \textrm{ker} \left( {\varvec{\sigma }_{2} \circ {\textbf{j}}} \right) \).
2.3 Some Random Matrices and the Joint Distribution of their Entries
Let I be a non-empty set. Suppose \(\{X_{i}\}_{i \in I}\) and \(\{Y_{i}\}_{i \in I}\) are two families of N-by-N random matrices defined on the same probability space. We say that \(\{X_{i}\}_{i \in I}\) and \(\{Y_{i}\}_{i \in I}\) are equal in distribution if we have
for all integers \(m\ge 1\), indexes \(i_{1},i_{2}, \ldots , i_{m} \in I\), and functions \({\textbf{j}}: [\pm m] \rightarrow [N]\).
A matrix \(\textrm{X} \in \textrm{Mat}_{N}({\mathbb {C}})\) is a signature matrix if there exist signs \(\epsilon _{1},\ldots ,\epsilon _{N} \in \{-1,1\}\) such that
An N-by-N random matrix X is a uniformly distributed signature matrix if it is uniformly distributed on the set of N-by-N signature matrices; in this case, for all functions \(\textbf{i,j}: S \rightarrow [N]\) we have
A matrix \( \textrm{W} \in \textrm{Mat}_{N}({\mathbb {C}})\) is a signed permutation matrix if there exist signs \(\epsilon _{1},\ldots ,\epsilon _{N} \in \{-1,1\}\) and a permutation \(\sigma \in \textrm{Sym}(N) \) such that
An N-by-N random matrix W is a uniformly distributed signed permutation matrix if it is uniformly distributed on the set of N-by-N signed permutation matrices; if that is the case, for all functions \(\textbf{i,j}: S \rightarrow [N]\) we get
Remark
Suppose \(\{V_{i}\}_{i \in I}\) is a family of N-by-N random matrices distribution-invariant under conjugation by signed permutation matrices, i.e., the families \(\{V_{i}\}_{i \in I}\) and \(\{W^{*} V_{i} W \}_{i \in I}\) are equal in distribution for every signed permutation matrix W. Then, for all integers \(m\ge 1\), indexes \(i_{1},i_{2}, \ldots , i_{m} \in I\), and functions \({\textbf{j}}: [\pm m] \rightarrow [N]\), we have
for all signs \(\epsilon _{1},\ldots ,\epsilon _{N} \in \{-1,1\}\) and permutations \(\sigma \in \textrm{Sym}(N)\).
2.4 Non-commutative Polynomials and their Evaluation on Families of Random Matrices
Let I be a non-empty set. We denote by \({\mathbb {C}}\left\langle \textrm{x}_{i} \mid i \in I \right\rangle \) the algebra of non-commutative polynomials on the family of variables \(\{\textrm{x}_{i} \mid i \in I\}\). Let us recall that \({\mathbb {C}}\left\langle \textrm{x}_{i} \mid i \in I \right\rangle \) is the algebra over \({\mathbb {C}}\) with a basis consisting of all the words in the alphabet \(\{\textrm{x}_{i} \mid i \in I\}\), including the empty word which acts as multiplicative identity, and the product of two basis elements is given by concatenation. Thus, a basis element is a word of the form
for some integer \(r\ge 0\) and some indexes \(i_{1},i_{2},\ldots , i_{r} \in I\), and if \(\textrm{x}_{j_{1}}\textrm{x}_{j_{2}}\cdots \textrm{x}_{j_{r}}\) is another basis element, we have
Given polynomials \(\textrm{p}_{1},\textrm{p}_{2}, \ldots , \textrm{p}_{m}\) in the algebra \({\mathbb {C}}\left\langle \textrm{x}_{i} \mid i \in I \right\rangle \) and a set \(S=\{ k_{1}< k_{2}< \cdots < k_{n} \} \subset [m]\), we let
Suppose we are given random matrix ensembles \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i\in I\) where each \(X_{N,i}\) is a N-by-N random matrix. For each non-commutative polynomial \(\textrm{p} \in {\mathbb {C}}\left\langle \textrm{x}_{i} \mid i \in I \right\rangle \), we denote by
the random matrix obtained from replacing each \(\textrm{x}_{i}\) appearing in the polynomial \(\textrm{p}\) with the random matrix \(X_{N,i}\) for every \(i\in I\) and the constant term of \(\textrm{p}\), say \(\alpha \), with the scalar multiple of the identity matrix \(\alpha I_{N}\). For instance, if \(\textrm{p}(\textrm{x}_{1},\textrm{x}_{2}) = \textrm{x}_{1} \textrm{x}_{2} - \textrm{x}^{2}_{2} + 4 \), then
3 Graph Sums of Square Matrices
In this section, we review and prove some useful results on graph sums of square matrices. A graph sum of given matrices \(A_{1},A_{2},\ldots ,A_{m} \in \textrm{Mat}_N({\mathbb {C}})\) is a sum of the form
for some partition \(\pi \in P(\pm m)\). Note that the condition \( \textrm{ker} \left( {{\textbf{j}}} \right) \ge \pi \) in the sum above is simply a restatement of a set of equalities between the indexes \(j_{\pm k}\). For example, if we let \(\pi = \{\{1,-2\},\{2,-3\},\ldots ,\{m-1,-m\},\{m,-1\}\}\), then \( \textrm{ker} \left( {{\textbf{j}}} \right) \ge \pi \) only if \(j_{1} = j_{-2},j_{2}=j_{-3},\ldots , j_{m-1}=j_{-m}\), and \(j_{m}=j_{-1}\), and thus, we get
It is worth mentioning that although the labeling of the entries of \(A_{k}\) in (3.1) is not customary, it has proven to be suitable for many of our calculations; moreover, for a bijection \(\sigma : [\pm m ] \rightarrow S \), the relation
provides the link between the labeling of the entries of \(A_{k}\) in (3.1) and any other labeling. For instance, if \(\sigma : [\pm m ] \rightarrow [2m] \) is given by \(\sigma (-k)=2k-1\) and \(\sigma (k)=2k\) for \(1 \le k \le m\), then
where \({{\hat{\pi }}} = \{\{1,2\},\{3,4\},\ldots ,\{2\,m-1,2\,m\}\}\) and \(\pi = \sigma ^{-1}\circ {{\hat{\pi }}} = \{\{-1,1\},\{-2,2\},\ldots ,\{-m,m\}\}\). The type of sums above are named graph sums because they can be associated with certain graphs that, as we will see next, help us analyze the corresponding sums.
3.1 Bounds of Graph Sums of General Square Matrices
The main result in [17] concerns more general graph sums, allowing the matrices \(A_{k}\) in (3.1) to be rectangular and not necessarily square. For graph sums of square matrices, however, the result takes the following form.
Theorem 5
Suppose \(\pi \) is a partition in \(P(\pm m)\). Then, there exists a rational number \(\tau _{\pi } \in \{ 1, \frac{3}{2}, 2,\ldots \}\) depending only on the partition \(\pi \) such that for every integer \(N\ge 1\) the following two conditions hold:
-
(a)
for all matrices \( A_{1}, A_{2}, \ldots ,A_{m}\in \textrm{Mat}_N({\mathbb {C}}) \), we have
$$\begin{aligned} \left| \sum _{\begin{array}{c} {\textbf{j}} :[\pm m]\rightarrow [N] \\ \textrm{ker} \left( {{\textbf{j}}} \right) \ge \pi \end{array} } \prod _{k=1}^{m} A_{k}( j_{-k},j_{k}) \right| \le N^{\tau _{\pi }} \prod _{k=1}^{m} \left\| {A_{k}} \right\| \end{aligned}$$ -
(b)
there are some nonzero matrices \(B_{1}, B_{2}, \ldots ,B_{m} \in \textrm{Mat}_N({\mathbb {C}}) \) satisfying
$$\begin{aligned} \left| \sum _{\begin{array}{c} {\textbf{j}} :[\pm m]\rightarrow [N] \\ \textrm{ker} \left( {{\textbf{j}}} \right) \ge \pi \end{array} } \prod _{k=1}^{m} B_{k}( j_{-k},j_{k}) \right| = N^{\tau _{\pi }} \prod _{k=1}^{m} \left\| {B_{k}} \right\| \end{aligned}$$
Note that \(\tau _{\pi }\) is uniquely determined by (a) and (b). We call \(\tau _{\pi }\) the graph sum exponent of \(\pi \).
It is also shown in [17] that the graph sum exponent \(\tau _{\pi }\) can be algorithmically computed analyzing the two-edge connectedness of a graph associated with \(\pi \). For the reader’s convenience, we recount such algorithm next.
- Step 1.:
-
Given a partition \(\pi \in P(\pm m)\), consider the undirected graph \({\mathcal {G}}_{\pi }\) resulting from, first, taking edges \(E_{1}, E_{2},\ldots ,E_{m}\) with endpoints \(-1,+1,-2,+2,\ldots ,-m,+m\), respectively, and, then, identifying endpoints when they belong to the same block of \(\pi \).
- Step 2.:
-
Identify the cutting edges and the two-edge connected components of \({\mathcal {G}}_{\pi }\). Recall that a cutting edge of a graph, also known as a bridge, is an edge whose removal increases the number of connected components.
Moreover, a graph is two-edge connected if it is connected and has no cutting edges, and, consequently, a two-edge connected component of a graph is a subgraph that is maximal, under the usual graph inclusion, in the set of all two-edge connected subgraphs
- Step 3.:
-
Letting \({\mathcal {F}}_{\pi }\) denote the graph with vertex set given by the set of all two-edge connected components of \({\mathcal {G}}_{\pi }\) and edge set given by the set of all cutting edges of \({\mathcal {G}}_{\pi }\), the graph sum exponent \(\tau _{\pi }\) is given by
$$\begin{aligned} \tau _{\pi } = \sum _{v \text { vertex in } {\mathcal {F}}_{\pi } } {\mathfrak {l}}(v) \quad \text {where} \quad {\mathfrak {l}}(v) := \left\{ \begin{array}{cl} \frac{1}{2} &{} \text { if } \deg (v) = 1, \\ 1 &{} \text { if } \deg (v) = 0, \\ 0 &{} \text {otherwise}. \end{array}\right. \end{aligned}$$(3.3)and \(\deg (v)\) denotes the degree of the vertex v in the graph \({\mathcal {F}}_{\pi }\).
Example
The undirected graph \({\mathcal {G}}_{\pi }\) associated with the partition
can be represented as
Hence, the cutting edges of \({\mathcal {G}}_{\pi }\) are \(E_{3}\), \(E_{5}\), \(E_{6}\), \(E_{7}\), \(E_{8}\), and \(E_{9}\); moreover, the two-edge connected components of \({\mathcal {G}}_{\pi }\) are exactly what remains of \({\mathcal {G}}_{\pi }\) after removing all of its cutting edges. The graph \({\mathcal {F}}_{\pi }\) can be obtained from \({\mathcal {G}}_{\pi }\) by shrinking each of the two-edge connected components of \({\mathcal {G}}_{\pi }\) to a vertex, and thus, if we represent the cutting edges of \({\mathcal {G}}_{\pi }\) with dashed lines, we obtain
where \({\mathcal {F}}_{\pi }\) is the graph on the right and next to each of its vertices we have placed the corresponding contribution \({\mathfrak {l}}(v)\) to the graph sum exponent \(\tau _{\pi }\). Therefore, we have \(\tau _{\pi } = 4\).
Having described the algorithm to compute \(\tau _{\pi }\), we can now show that graph sum exponents of even partitions can be easily calculated.
Proposition 6
If \(\pi \in P( \pm m) \) is an even partition, then the graph sum exponent \(\tau _{\pi }\) equals the number of connected components of \({\mathcal {G}}_{\pi }\).
Proof
By Equation (3.3), it suffices to show that the graph \({\mathcal {G}}_{\pi }\) has no cutting edges. Suppose \({\mathcal {G}}_{\pi }\) has a cutting edge. If we remove such cutting edge, we get two disjoint graphs, each of which has one single vertex of odd degree and the other vertices of even degree. But, this contradicts the handshaking lemma that in any graph the sum of degrees over all its vertices must be even. Thus, \({\mathcal {G}}_{\pi }\) has no cutting edges, and hence, all its connected components are two-edge connected. \(\square \)
Now, resulting from endowing each edge \(E_{k}\) in the graph \({\mathcal {G}}_{\pi }\) with the direction that goes from \(+k\) to \(-k\), the directed graph \(\vec {{\mathcal {G}}}_{\pi }\) can sometimes be used to describe the corresponding graph sum. In particular, a graph sum factors as a product of traces of matrices when all connected components of \({\mathcal {G}}_{\pi }\) are bouquets, to which we refer as multiple loops, or cycles, each connected component gives rise to a trace. For example, for the partition
and given matrices \(A_{1},A_{2},\ldots ,A_{7} \in \textrm{Mat}_N({\mathbb {C}})\), we have the graph sum
where the right-hand side can be deduced from analyzing the directed graph \(\vec {{\mathcal {G}}}_{\pi }\) as follows:
-
(1)
The corresponding directed graph \(\vec {{\mathcal {G}}}_{\pi }\) has exactly three connected components, two cycles and one double-loop, and can be represented as
Each cycle and each one multiple-loop gives rise to a trace in the right-hand side of (3.4).
-
(2)
If a connected component of \(\vec {{\mathcal {G}}}_{\pi }\) is a cycle, we unfold it to obtain a horizontal line and replace each edge \(E_{k}\) by the matrix \(A_{k}\) if the direction of \(E_{k}\) goes from right to left in the horizontal line; otherwise, we replace \(E_{k}\) by \(A^{T}_{k}\), the transpose of \(A_{k}\).
We then put the matrices \(A_k\) or \(A_{k}^{T}\) in a trace \(\textrm{Tr} \left( {\cdot } \right) \) as they appear when we read the resulting horizontal line from left to right. For instance, the longest cycle of \(\vec {{\mathcal {G}}}_{\pi }\) gives
And so, we obtain the trace \(\textrm{Tr} \left( { A_{7}^{T} A_{1}^{} A_{6}^{} A_{5}^{T} } \right) \) in (3.4). Note that \(\textrm{Tr} \left( { A_{1}^{} A_{6}^{} A_{5}^{T} A_{7}^{T} } \right) \) and \(\textrm{Tr} \left( { A_{2}^{} A_{3}^{} } \right) \) do not depend on how the cycles in \(\vec {{\mathcal {G}}}_{\pi }\) are unfolded since for any matrices \(A,B \in \textrm{Mat}_N({\mathbb {C}})\) we have \(\textrm{Tr} \left( {AB} \right) = \textrm{Tr} \left( {BA} \right) \), \(\textrm{Tr} \left( {A} \right) = \textrm{Tr} \left( {A^{T}} \right) \), and \((AB)^{T} = B^{T}A^{T}\).
-
(3)
On the other hand, a multiple-loop in \(\vec {{\mathcal {G}}}_{\pi }\) with edges \(E_{k_{1}},E_{k_{2}},\ldots ,E_{k_{n}}\) yields the trace of the Hadamard product of \(A_{k_{1}},A_{k_{2}},\ldots ,A_{k_{n}}\). This way, we get \(\textrm{Tr} \left( {A_{4} \circ A_{8}} \right) \) in (3.4).
Thus, if \(\pi \) is now given by
the corresponding directed graph \(\vec {{\mathcal {G}}}_{\pi }\) can be represented as
and hence, we obtain
3.2 Bounds of Graph Sums of The Discrete Fourier Transform Matrix
Although the bound for graph sums given by Theorem 5 is optimal in the set of all square matrices, it might not be optimal for some graph sums involving the discrete Fourier transform matrix. Let us recall that the N-by-N discrete Fourier transform matrix is the symmetric matrix H with entries given by
where \(\omega = \exp (-\frac{2 \pi }{N} \sqrt{-1} ) \) is a primitive N-th root of unity. Now, letting \({\textbf{h}}({\textbf{j}})\) be given by
for each function \({\textbf{j}}: [\pm 2m] \rightarrow [N]\), Theorem 5 gives us that
for any partition \(\pi \in P(\pm 2m)\); on the other hand, since \( {\textbf{h}}({\textbf{j}})\) has absolute value 1, we also obtain
Thus, if \(\pi \) is the partition \(\{\{2k-1,-2k+1,2k,-2k\} \mid k = 1,2,\ldots , m\}\), then the graph sum exponent \(\tau _{\pi }\) equals m, and hence, \(\tau _{\pi } + m = 2m\), but also \(\#(\pi ) = m\), so (3.8) is a sharper bound than (3.7) in this case. In general, we prefer (3.8) over (3.7) since (3.8) is invariant under re-labeling of the entries of H and \(H^{*}\) in (3.6); namely, given a permutation \(\sigma \in \textrm{Sym}( \pm 2m )\) and letting
for any function \({\textbf{j}}: [\pm 2m] \rightarrow [N]\), the inequality in (3.8) implies
since we have the relation
Moreover, in the proof of Theorem 1, we will need to consider sums of the form
where \(m=m_{1}+m_{2}\) for some integers \(m_{1},m_{2} \ge 1\) and \(\sigma \in \textrm{Sym}(\pm 2m)\) is the permutation with cycle decomposition given by
Although the sum in (3.10) is not a graph sum, it can be determined up to a term of order \(N^{\#{\pi }-1}\) analyzing (3.9) since for every partition \( \pi \in P(\pm 2m)\) we have
The rest of this section is devoted to find and classify partitions \(\pi \) such that (3.8) becomes an equality. To do that, let us first associate a polynomial to each partition \(\pi \in P (\pm 2m)\).
The polynomial \(\varvec{\textrm{p}_{\pi }}\). Given a partition \(\pi =\{B_{1},B_{2},\ldots ,B_{r}\} \in P(\pm 2m)\), we let \(\textrm{p}_{\pi }(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r})\), or simply \(\textrm{p}_{\pi }\), be the polynomial obtained from the expression
after replacing each variable \(\textrm{x}_{k}\) by \(\textrm{x}_{l}\) whenever k belongs to the block \(B_{l}\). For instance, if \(\pi =\{B_{1}=\{-1,3\},B_{2}=\{-3,1\},B_{3}=\{-2,2\},B_{4}=\{-4,4\}\}\), then
Equivalently, the polynomial \(\textrm{p}_{\pi }(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r})\) is the image of (3.13) under the unique homomorphism from \({\mathbb {Z}}\left[ \textrm{x}_{-1},\textrm{x}_{1},\ldots ,\textrm{x}_{-2m},\textrm{x}_{2m}\right] \) to \({\mathbb {Z}}[\textrm{x}_{1}, \textrm{x}_{2}, \ldots , \textrm{x}_{r}]\) such that \(\textrm{x}_{k} \mapsto \textrm{x}_{l} \) whenever \(k \in B_{l}\). Note that \(\textrm{p}_{\pi }(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r})\) has degree either 0 or 2 and can also be explicitly defined as
where
moreover, \(\textrm{p}_{\pi }(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r})\) satisfies the relation
Therefore, (3.8) becomes an equality precisely when \(\textrm{p}_{\pi }(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r})\) is the zero polynomial. On the other hand, if \(\textrm{p}_{\pi }(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r})\) is a nonzero polynomial, we can then find a sharper bound than (3.8) via the reciprocity theorem for generalized Gauss sums, see [3, Section 1.2] for a proof of this theorem.
The reciprocity theorem for generalized Gauss sums Suppose a, b, c are integers with \(a, c\ne 0\) and \(ac+b\) even. Then,
Proposition 7
If \(\textrm{p}(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r})\) is a nonzero polynomial of degree at most 2 in \({\mathbb {Z}} \left[ \textrm{x}_1, \textrm{x}_2, \ldots , \textrm{x}_r \right] \), then there exists a constant \(C_{\textrm{p}}\) independent of N such that
Proof
Suppose \(\textrm{p}(\textrm{x}_{1},\ldots ,\textrm{x}_{r}) \in {\mathbb {Z}} \left[ \textrm{x}_1, \ldots , \textrm{x}_r \right] \) is a nonzero polynomial of degree at most 2. Without loss of generality, we can assume that there is a nonzero linear polynomial \(\textrm{q}_{1}(\textrm{x}_{1},\ldots ,\textrm{x}_{r}) = \alpha _{1} \textrm{x}_{1} + \alpha _{2} \textrm{x}_{2} +\cdots + \alpha _{r} \textrm{x}_{r} \in {\mathbb {Z}} \left[ \textrm{x}_{1}, \textrm{x}_{2}, \ldots , \textrm{x}_{r} \right] \) and a polynomial \(\textrm{q}_{2}(\textrm{x}_{2},\ldots ,\textrm{x}_{r}) \in {\mathbb {Z}} \left[ \textrm{x}_{2}, \textrm{x}_{3}, \ldots , \textrm{x}_{r} \right] \) of degree at most 2 such that
Since we have the inequality
we only need to show that there is a constant \(C_{\textrm{p}}\) independent from N such that
Suppose \(\alpha _{1} \ne 0\). Then, we have that
where S(a, b, c) denotes the generalized Gauss quadratic sum as in (3.17). Thus, by the reciprocity theorem for generalized Gauss sums, we get
and therefore, we obtain
Now, suppose \(\alpha _{1} = 0\). Recall that
So, we have
But, since the polynomial \(\textrm{q}_{1}(\textrm{x}_{1},\ldots ,\textrm{x}_{r}) = \alpha _{1} \textrm{x}_{1} +\cdots + \alpha _{r} \textrm{x}_{r}\) is nonzero, we must have \(\alpha _{k} \ne 0\) for some \(k \ne 1\), and hence, the equation
has at most \(\left| {\alpha _{k}} \right| \) solutions in the set \(\{0,1,\ldots ,N-1\}\) for any given integer \(\beta \). Thus, we have
and therefore, we get
\(\square \)
As an immediate consequence from (3.12), (3.16), and Proposition 7, we have the following.
Corollary 8
If \(\textrm{p}_{\pi }(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r})\) is a nonzero polynomial for some partition \(\pi = \{B_{1},B_{2},\ldots ,B_{r}\} \in P(\pm 2\,m)\), then there is a constant \(C_{}\) independent from N so that
The next two propositions establish necessary and sufficient conditions for \(\textrm{p}_{\pi }(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r})\) to be the zero polynomial. Roughly speaking, the polynomial \(\textrm{p}_{\pi }(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r})\) is zero if only and if the blocks of the partition \(\pi \) group the elements of the set \([\pm 2m]\) in such a way that the positive and negative signs appearing in (3.13) cancel each other out.
Proposition 9
Suppose \(\pi = \{B_{1}, B_{2}, \ldots , B_{2m}\}\) is a pairing partition in \(P( \pm 2 m )\). Then the polynomial \(\textrm{p}_{\pi } (\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{2\,m})\) is zero if and only if \(\pi \) is a symmetric partition such that \(k \sim _\pi l\) implies \(k + l\) odd for all integers \(k,l \in [\pm 2 m]\).
Proof
Suppose \(\textrm{p}_{\pi } (\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{2\,m})\) is the zero polynomial and take \(a_{t,s}\) as (3.15) for \(1 \le t \le s \le 2\,m\). To prove \(\pi \) is a symmetric partition such that \(k \sim _\pi l\) implies \(k + l\) odd for all integers \(k,l \in [\pm 2 m]\), it suffices to show that for every integer \(k \in [2m]\) there exists an integer \(l \in [2\,m]\) such that \(k+l\) is odd and either \(k \sim _\pi l\) and \(-k \sim _\pi -l\) or \(k \sim _\pi - l\) and \(-k \sim _\pi l\). Fix \(k \in [2m]\) and let \(t',s' \in [2\,m]\) such that \(k \in B_{t'}\) and \(-k \in B_{s'}\). Since \(\textrm{p}_{\pi } (\textrm{x}_1, \ldots , \textrm{x}_{2\,m}) = \sum _{1 \le t \le s \le r} a_{t,s} \textrm{x}_{t} \textrm{x}_{s}\) is the zero polynomial, we must have \(a_{t',s'}= 0 \). Now, if \(t' \ne s'\), from (3.15) we get that
which implies there exists \(l \in [2\,m] \) such that \( (-1)^{k} + (-1)^{l}\) is zero and either \(l \in B_{t'}\) and \(-l \in B_{s'}\) or \(-l \in B_{t'}\) and \(l \in B_{s'}\). But this is equivalent to the desired conclusion. A similar argument works for the case \(s=t\).
Now, if the partition \(\pi \) is a symmetric pairing in \(P(\pm 2m)\) such that \(k \sim _\pi l\) implies \(k + l\) odd for all integers \(k,l \in [\pm 2\,m]\), we can write \(\pi =\{B_{1},B_{2},\ldots ,B_{2\,m}\}\) with \(B_{1}=\{-k_{1},-l_{1}\},B_{2}=\{k_{1},l_{1}\}, B_{3}=\{-k_{2},-l_{2}\},B_{2}=\{k_{2},l_{2}\},\ldots ,B_{2\,m}=\{k_{m},l_{2\,m}\}\) and \(k_{1},l_{1},k_{2},l_{2},\ldots ,l_{m} \in [\pm 2m]\) satisfying \(k_{i}+l_{i}\) odd for \(i=1,2,\ldots , m\). Moreover, since \(\bigcup _{i=1}^{2\,m} B_{i}= [\pm 2\,m]\) and \((-1)^{k} = (-1)^{-k}\) for \(k \in [\pm 2m]\), we have
Therefore, from the definition of \(\textrm{p}_{\pi }(\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{2m})\) and the fact that \(k_{i}+l_{i}\) is odd for \(i=1,2,\ldots , m\), we get
\(\square \)
Proposition 10
Let \(\pi = \{B_1, B_2, \ldots , B_n\}\) be a partition in \(P( \pm 2\,m )\). If there is a partition \(\theta \in P( \pm 2\,m )\) such that \(\theta \le \pi \) and \(\textrm{p}_{\theta }\) is the zero polynomial, then \(\textrm{p}_{\pi }\) is also the zero polynomial. Conversely, if \(\textrm{p}_{\pi }\) is the zero polynomial, then there is a symmetric pairing partition \(\theta \le \pi \) such that \(\textrm{p}_{\theta }\) is the zero polynomial.
Proof
Suppose \(\theta \le \pi \) and \(\textrm{p}_{\theta }\) is the zero polynomial. Write \(\theta =\{B_{1,1},B_{1,2}, \ldots , B_{1,m_1},\ldots , B_{n,m_n} \}\) with \(B_{i} = \cup _{j=1}^{m_i}B_{i,j}\) for \(i=1,2,\ldots , n\). Take \({\mathcal {A}} = {\mathbb {Z}}\Big [\textrm{x}_{1},\textrm{x}_{-1},\ldots ,\textrm{x}_{2\,m},\textrm{x}_{-2\,m}\Big ]\), \({\mathcal {B}}={\mathbb {Z}}[\textrm{x}_{1,1}, \textrm{x}_{1,2}, \ldots , \textrm{x}_{1,m_1}, \ldots , \textrm{x}_{n,m_n}]\), and \({\mathcal {C}} = {\mathbb {Z}}[\textrm{x}_{1}, \textrm{x}_{2}, \ldots , \textrm{x}_{n}]\) and let \(\Phi : {\mathcal {A}} \rightarrow {\mathcal {B}}\) and \(\Psi : {\mathcal {B}} \rightarrow {\mathcal {C}}\) be the unique homomorphisms such that \( \Phi (\textrm{x}_{k})= \textrm{x}_{i,j}\) if \(k \in B_{i,j}\) and \(\Psi (\textrm{x}_{i,j}) = \textrm{x}_{i}\). Note that \((\Psi \circ \Phi ) (\textrm{x}_{k}) = \textrm{x}_{l}\) only if \(k \in B_{l}\), and thus, by definition of \(\textrm{p}_{\pi }\) and \(\textrm{p}_{\theta }\), we have that
Hence, if \(\textrm{p}_{\theta }\) is the zero polynomial, so is \(\textrm{p}_{\pi }\).
Suppose now \(\textrm{p}_{\pi }\) is the zero polynomial and let \(\theta \) be a minimal element of the set \( \{ {\widehat{\pi }} \in P(\pm 2\,m): {\widehat{\pi }} \le \pi \text{ and } \textrm{p}_{ {\widehat{\pi }}} = 0 \} \) endowed with the partial order inherited from \(P(\pm 2 m)\). Since \(\textrm{p}_{\theta }\) is the zero polynomial, it follows from the first part of Proposition 9’s proof that for every integer \(k \in [2m]\) there exists an integer \(l \in [2m]\) such that \(k+l\) is odd and either \(k \sim _\theta l\) and \(-k \sim _\theta -l\) or \(k \sim _\theta - l\) and \(-k \sim _\theta l\). Therefore, \(\theta \) lacks singletons and either \(\theta \) is a pairing partition or \(\theta \) has a block with at least three elements. Let us assume \(\theta = \{C_1, C_2, \ldots , C_n\}\) has a block with at least three elements, say \(C_{n}\). The previous property of \(\theta \)—borrowed from the first part of Proposition 9’s proof—implies there are integers \(k, l \in [2\,m]\) such that \(k+l\) is odd and at least one of the following conditions holds:
-
(1)
\(+k, +l \in C_{n}\) and \(-k \sim _\theta -l\)
-
(2)
\(+k, - l \in C_{n}\) and \(-k \sim _\theta +l\)
-
(3)
\(-k, -l \in C_{n}\) and \(+k \sim _\theta +l\)
-
(4)
\(-k, +l \in C_{n}\) and \(+k \sim _\theta -l\)
Assume (1) holds. Then, \( C_{n} {\setminus }\{k,l\}\) is not empty, and hence, letting \({\widehat{C}}_{i} = C_{i}\) for \(i=1,2,\ldots n-1\), \({\widehat{C}}_{n} = C_{n} \setminus \{k,l\}\), and \({\widehat{C}}_{n+1}= \{k,l\}\), we have \({{\widehat{\theta }}} = \{{\widehat{C}}_{1}, {\widehat{C}}_{2}, \ldots , {\widehat{C}}_{n+1} \}\) is a partition of \([\pm 2\,m ]\) such that \({{\widehat{\theta }}} \lneq \theta \), i.e., \(\theta \ge {{\widehat{\theta }}}\) but \(\theta \ne {{\widehat{\theta }}}\). Let us show that \(\textrm{p}_{{{\widehat{\theta }}}}\) must be the zero polynomial, contradicting the minimality of \(\theta \). Take \({\mathcal {A}} = {\mathbb {Z}}\left[ \textrm{x}_{1},\textrm{x}_{-1},\ldots ,\textrm{x}_{m},\textrm{x}_{-m}\right] \), \({\mathcal {B}}={\mathbb {Z}}[\textrm{x}_{1}, \textrm{x}_{2}, \ldots , \textrm{x}_{n}]\), and \(\widehat{{\mathcal {B}}} = {\mathbb {Z}}[\textrm{x}_{1}, \textrm{x}_{2}, \ldots , \textrm{x}_{n+1}]\) and let \(\Phi : {\mathcal {A}} \rightarrow {\mathcal {B}}\) and \({{\widehat{\Phi }}}: {\mathcal {A}} \rightarrow \widehat{{\mathcal {B}}}\) be the unique homomorphisms such that \( \Phi (\textrm{x}_{i})= \textrm{x}_{j}\) if \(i \in {C}_{j}\) and \({{\widehat{\Phi }}}(\textrm{x}_{i}) = \textrm{x}_{j}\) if \(i \in {\widehat{C}}_{j}\). Since \({\Phi }(\textrm{x}_{i}) = {\widehat{\Phi }}(\textrm{x}_{i})\) for \(i \in [\pm 2\,m] {\setminus } \{k,l\}\), we have
Moreover, since \(-k \sim _\theta -l\), we have \(\Phi ( \textrm{x}_{-k} ) = \Phi ( \textrm{x}_{-l} ) = {{\widehat{\Phi }}}( \textrm{x}_{-k} ) = {{\widehat{\Phi }}}( \textrm{x}_{-l} ) \), so we get
since \(k+l\) is odd, \(\Phi (\textrm{x}_{k}) = \Phi (\textrm{x}_{l}) = \textrm{x}_{n}\), and \({{\widehat{\Phi }}}(\textrm{x}_{k}) = {{\widehat{\Phi }}}(\textrm{x}_{l}) = \textrm{x}_{n+1}\). Thus, we obtain
But then, \(\theta \) is not minimal, and therefore, (1) does not hold. Similar arguments show that neither (2), nor (3), nor (4) hold. Therefore, the partition \(\theta \) must be a pairing, and, in fact, a symmetric pairing by Proposition 9. \(\square \)
As mentioned earlier, in proving Theorem 1, we need to consider sums as in (3.10). Note that if \(\textrm{p}_{\sigma ^{-1} \circ \pi }\) is the zero polynomial for some permutation \(\sigma \in \textrm{Sym}(\pm 2m)\), then \({\textbf{h}}({\textbf{j}}) = 1\) for any function \({\textbf{j}}:[\pm 2\,m]\rightarrow [N] \) satisfying \( \textrm{ker} \left( {{\textbf{j}}} \right) \ge \sigma ^{-1} \circ \pi \), and hence, we would get
On the other hand, if the polynomial \(\textrm{p}_{\sigma ^{-1} \circ \pi }\) is nonzero, we have that (3.10) is of order \(N^{\#(\pi ) - 1/2}\) by Corollary 8. We will now use the previous results to classify all symmetric pairing partitions so that \(\textrm{p}_{\sigma ^{-1} \circ \pi }\) is the zero polynomial.
Lemma 11
Let \(m=m_{1} + m_{2}\) for some integers \(m_{1}, m_{2}\ge 1\), and let \(\sigma \) be the permutation given by (3.11). Suppose k and l are integers in \([2\,m]\) and \(\pi \) is a symmetric pairing partition in \(P(\pm 2\,m)\) such that \(\textrm{p}_{\sigma ^{-1} \circ \pi }\) is the zero polynomial. If \(-k \sim _\pi l\), then \(\sigma ^{-t}(-k) \sim _\pi \sigma ^{t}(l)\) for every integer \(t \ge 0\). On the other hand, if \(-k \sim _\pi -l\), then \(\sigma ^{t}(-k) \sim _\pi \sigma ^{t}(-l)\) for every integer \(t \ge 0\).
Proof
Note that \({\hat{k}} \sim _{\pi } {\hat{l}} \) implies \(\sigma (- \sigma ^{-1} ({\hat{k}}) ) \sim _{\pi } \sigma (- \sigma ^{-1} ({\hat{l}}) )\). Indeed, by Proposition 10, the partition \(\sigma ^{-1} \circ \pi \) is symmetric since \(\textrm{p}_{\sigma ^{-1} \circ \pi }\) is the zero polynomial, and hence, \(- \sigma ^{-1} ({\hat{k}}) \sim _{\sigma ^{-1} \circ \pi } - \sigma ^{-1} ({\hat{l}}) \) provided \({\hat{k}} \sim _{\pi } {\hat{l}} \), but in that case we must have \(\sigma (- \sigma ^{-1} ({\hat{k}}) ) \sim _{\pi } \sigma (- \sigma ^{-1} ({\hat{l}}) )\). Note also that for every integer \({\hat{k}} \in [\pm 2m]\) we have
since for \(1 \le k \le 2\,m \) we have \(\sigma ^{-1}(k)=-k\), \(-\sigma ^{-1}(-k)<0\), and \(\sigma (-k)=k\).
Now, suppose \(\sigma ^{-t}(-k) \sim _{\pi } \sigma ^{t}(l)\) for some integer \(t \ge 0\). If t is even, then \({\hat{k}}=\sigma ^{-t}(-k)< 0 < \sigma ^{t}(l)={\hat{l}}\), and hence \( \sigma ^{-t-1}(-k) = \sigma (- \sigma ^{-1} ({\hat{k}}) ) \sim _{\pi } \sigma (- \sigma ^{-1} ({\hat{l}}) ) = \sigma ^{t+1}(l)\). On the other hand, if t is odd, we have \(\sigma ^{-t}(-k)> 0 > \sigma ^{t}(l)\), and hence \( \sigma ^{-t-1}(-k) = - \sigma ^{-t}(-k) \sim _{\pi } - \sigma ^{t}(l) = \sigma ^{t+1}(l)\) since \(\pi \) is symmetric. Thus, \(-k \sim _{\pi } l\) implies \(\sigma ^{-t}(-k) \sim _\pi \sigma ^{t}(l)\) for every integer \(t \ge 0\) by induction on t. Similarly, assuming \(-k \sim _{\pi } -l\), we get \(\sigma ^{t}(-k) \sim _{\pi } \sigma ^{t}(-l)\) for all \(t\ge 0\). \(\square \)
Remark 12
The results regarding the polynomials \(\textrm{p}_{\pi }\) and \(\textrm{p}_{\sigma ^{-1} \circ {\pi }}\) being zero can be restated in terms of the graphs \({\mathcal {G}}_{\pi }\) and \(\vec {{\mathcal {G}}}_{\pi }\) from Sect. 3.1. For instance, in the following proposition we show that the polynomial \(\textrm{p}_{\sigma ^{-1} \circ {\pi }}\) is zero for a given symmetric partition \(\pi \in P(\pm 2m)\) with \(m=m_1 + m_2\) if and only if one of the following conditions for the directed graph \(\vec {{\mathcal {G}}}_{\pi }\), where \(F_{t}\) denotes the edge \(E_{2m_{1}+t}\) for \(t=1,2,\ldots ,2m_{2}\), holds:
-
(1)
\(m_{1}=m_{2}\) and there is an integer \(1 \le l \le m_{2}\) so that the graph \(\vec {{\mathcal {G}}}_{\pi }\) can be represented as
-
(2)
\(m_{1}=m_{2}\) and there is an integer \(1 \le l \le m_{2}\) so that the graph \(\vec {{\mathcal {G}}}_{\pi }\) can be represented as
-
(3)
\(\vec {{\mathcal {G}}}_{\pi }\) is the disjoint union of \(\vec {{\mathcal {G}}}_{\pi _{1}}\) and \(\vec {{\mathcal {G}}}_{\pi _{2}}\), there is an integer \(1 \le k \le 2m_{1}\) so that \(\vec {{\mathcal {G}}}_{\pi _{1}}\) can be represented as
and there is an integer \(2m_{1}+1 \le l \le 2m_{1} + 2m_{2}\) so that \(\vec {{\mathcal {G}}}_{\pi _{2}}\) can be represented as
-
(4)
\(m_{1}\) and \(m_{2}\) are odd integers, the graph \(\vec {{\mathcal {G}}}_{\pi }\) is the disjoint union of \(\vec {{\mathcal {G}}}_{\pi _{1}}\) and \(\vec {{\mathcal {G}}}_{\pi _{2}}\), the graph \(\vec {{\mathcal {G}}}_{\pi _{1}}\) can be represented as
and the graph \(\vec {{\mathcal {G}}}_{\pi _{2}}\) can be represented as
-
(5)
\(m_{2}\) is odd, \(\vec {{\mathcal {G}}}_{\pi }\) is the disjoint union of \(\vec {{\mathcal {G}}}_{\pi _{1}}\) and \(\vec {{\mathcal {G}}}_{\pi _{2}}\), there is an integer \(1 \le k \le 2m_{1}\) so that \(\vec {{\mathcal {G}}}_{\pi _{1}}\) can be represented as
and the graph \(\vec {{\mathcal {G}}}_{\pi _{2}}\) can be represented as
-
(6)
\(m_{1}\) is odd, the graph \(\vec {{\mathcal {G}}}_{\pi }\) is the disjoint union of \(\vec {{\mathcal {G}}}_{\pi _{1}}\) and \(\vec {{\mathcal {G}}}_{\pi _{2}}\), the graph \(\vec {{\mathcal {G}}}_{\pi _{1}}\) can be represented as
and there is an integer \(1 \le l \le 2m_{1}\) so that \(\vec {{\mathcal {G}}}_{\pi _{2}}\) can be represented as
In the graphs above, \(2\,l-t\), \(2\,l+t-1\), and \(k \pm t \) are taken modulo \(2m_{1}\) for \(t=1,2,\ldots ,2m_{1}\) and \(l \pm t \) is taken modulo \(2m_{2}\) for \(t=1,2,\ldots ,2m_{2}\).
Proposition 13
Let \(m=m_{1} + m_{2}\) for some integers \(m_{1}, m_{2}\ge 1\), and let \(\sigma \) be the permutation given by (3.11). Suppose \({\pi }\) is a symmetric pairing partition of \([\pm 2m ]\) and denote by \({\pi }_1\) and \({\pi }_2\) the restrictions of \({\pi }\) to \([\pm 2m_1]\) and \([\pm 2\,m ] {\setminus } [\pm 2m_1]\), respectively. Then, \(\textrm{p}_{\sigma ^{-1} \circ {\pi }}\) is the zero polynomial if and only if one of the following conditions holds:
-
(1)
\({\pi } \ne {\pi }_1 \sqcup {\pi }_2\), \(m_{1}=m_{2}\), and there are integers \(1 \le k \le 2m_{2}\) and \(2m_{1}+1 \le l \le 2m_{1}+2m_{2}\) such that \(k+l\) is even and
$$\begin{aligned} {\pi } = \left\{ \{\sigma ^{t}(-k),\sigma ^{-t}(l)\} \mid t=1,2,\ldots , 4m_{1} \right\} . \end{aligned}$$ -
(2)
\({\pi } \ne {\pi }_1 \sqcup {\pi }_2\), \(m_{1}=m_{2}\), and there are integers \(1 \le k \le 2m_{2}\) and \(2m_{1}+1 \le l \le 2m_{1}+2m_{2}\) such that \(k+l\) is odd and
$$\begin{aligned} {\pi } = \left\{ \{\sigma ^{t}(-k),\sigma ^{t}(-l)\} \mid t=1,2,\ldots , 4m_{1} \right\} . \end{aligned}$$ -
(3)
\({\pi } = {\pi }_1 \sqcup {\pi }_2\) and there are integers \(1 \le k \le 2m_{1}\) and \(2m_{1}+1 \le l \le 2m_{1}+2m_{2}\) such that
$$\begin{aligned} {\pi }_{1} = \left\{ \{\sigma ^{t_{1}}(-k),\sigma ^{-t_{1}}(k) \} \mid t_{1}=1,2,\ldots , 2m_{1} \right\} \end{aligned}$$and
$$\begin{aligned} {\pi }_{2} = \left\{ \{\sigma ^{t_{2}}(-l),\sigma ^{-t_{2}}(l) \} \mid t_{2}=1,2,\ldots , 2m_{2} \right\} . \end{aligned}$$ -
(4)
\({\pi } = {\pi }_1 \sqcup {\pi }_2\), \(m_{1}\) and \(m_{2}\) are odd integers,
$$\begin{aligned} {\pi }_{1} = \left\{ \{\sigma ^{t_{1}}(-1),\sigma ^{t_{1}}(-m_1-1)\} \mid t_{1}=1,\ldots , 2m_{1} \right\} , \end{aligned}$$and
$$\begin{aligned}{\pi }_{2} = \left\{ \{\sigma ^{t_{2}}(-2m_1-1),\sigma ^{t_{2}}(-2m_1-m_2-1)\} \mid t_{2}=1,\ldots , 2m_{2} \right\} . \end{aligned}$$ -
(5)
\({\pi } = {\pi }_1 \sqcup {\pi }_2\), \(m_{2}\) is odd, there is an integer \(1 \le k \le 2m_{1}\) such that
$$\begin{aligned} {\pi }_{1} = \left\{ \{\sigma ^{t_{1}}(-k),\sigma ^{-t_{1}}(k) \} \mid t_{1}=1,2,\ldots , 2m_{1} \right\} , \end{aligned}$$and
$$\begin{aligned} {\pi }_{2} = \left\{ \{\sigma ^{t_{2}}(-2m_1-1),\sigma ^{t_{2}}(-2m_1-m_2-1)\} \mid t_{2}=1,\ldots , 2m_{2}. \right\} \end{aligned}$$ -
(6)
\({\pi } = {\pi }_1 \sqcup {\pi }_2\), \(m_{1}\) is odd,
$$\begin{aligned} {\pi }_{1} = \left\{ \{\sigma ^{t_{1}}(-1),\sigma ^{t_{1}}(-m_1-1)\} \mid t_{1}=1,\ldots , 2m_{1} \right\} , \end{aligned}$$and there is an integer \(2m_{1}+1 \le l \le 2m_{1}+2m_{2}\) such that
$$\begin{aligned} {\pi }_{2} = \left\{ \{\sigma ^{t_{2}}(-l),\sigma ^{-t_{2}}(l) \} \mid t_{2}=1,2,\ldots , 2m_{2} \right\} . \end{aligned}$$
Proof
Put \({{{\hat{\pi }}}} = \sigma ^{-1} \circ \pi \). Suppose \({{{\hat{\pi }}}} = \{B_{1}, B_{2},\ldots , B_{r}\}\) and let \(\Phi \) be the unique homomorphism from \({\mathbb {Z}}[\textrm{x}_{-1},\textrm{x}_{1},\ldots ,\textrm{x}_{-2m},\textrm{x}_{2m}]\) to \({\mathbb {Z}}[\textrm{x}_{1},\textrm{x}_{2},\ldots ,\textrm{x}_{r}]\) such that \(\Phi (\textrm{x}_{i}) = \textrm{x}_{j}\) if \(i \in B_{j}\). If condition (1) holds, then \({{{\hat{\pi }}}} = \left\{ \{\sigma ^{t}(-k),\sigma ^{-t-2}(l)\} \mid t = 1,2,\ldots , 4m_{1} \right\} \) and \(\sigma ^{t}(-k) + \sigma ^{-t-2}(l)\) is odd for \(t=1,2,\ldots , 4m_{1}\). Thus, since we can write
we get \( \textrm{p}_{{{{\hat{\pi }}}}} = \Phi ( \sum _{i=1}^{2\,m} (-1)^{i} \textrm{x}_{-i} \textrm{x}_{i} ) = 0. \) It follows from similar arguments that \(\textrm{p}_{{{{\hat{\pi }}}}}\) is the zero polynomial if (2) holds. Now, if (4) holds and we take \(l=2m_{1}+1\), we have that \(\sigma ^{t}(-k) + \sigma ^{-t-2}(k)\) and \(\sigma ^{t}(-l) + \sigma ^{t}(-m_{2}-l)\) are odd and \({{{\hat{\pi }}}} = \left\{ \{\sigma ^{t}(-k),\sigma ^{-t-2}(k)\}, \{\sigma ^{t}(-l),\sigma ^{t}(-m_{2}-l)\}\mid t \ge 0 \right\} \). Thus, since we can write
,
we get \(\displaystyle \textrm{p}_{{{\hat{\pi }}}}= 0\). Similar arguments show that if either (3), (5), or (6) holds, then \(\textrm{p}_{{{\hat{\pi }}}}\) is the zero polynomial.
Suppose now \(\textrm{p}_{{{{\hat{\pi }}}}}\) is the zero polynomial and let \({{{\hat{\pi }}}}_1\) and \({{{\hat{\pi }}}}_2\) be the restrictions of \({{{\hat{\pi }}}}\) to \([\pm 2m_1]\) and \([\pm (2m_1 + 2m_2)] {\setminus } [\pm 2m_1]\), respectively. We will consider two cases \({{{\hat{\pi }}}} \ne {{{\hat{\pi }}}}_{1} \sqcup {{{\hat{\pi }}}}_{2}\) and \({{{\hat{\pi }}}} = {{{\hat{\pi }}}}_{1} \sqcup {{{\hat{\pi }}}}_{2}\). Assume first \({{{\hat{\pi }}}} \ne {{{\hat{\pi }}}}_{1} \sqcup {{{\hat{\pi }}}}_{2}\). By Proposition 9, there are integers \(1 \le k \le 2m_{1}\) and \(2m_{1}+1 \le l \le 2m_{1}+2m_{2}\) such that \(k+l\) is odd and one of the following holds:
-
(1’)
\(k \sim _{{{\hat{\pi }}}} - l\) and \(-k \sim _{{{\hat{\pi }}}} l\).
-
(2’)
\(k \sim _{{{\hat{\pi }}}} l\) and \(-k \sim _{{{\hat{\pi }}}} -l\).
Suppose (2’) holds. Then, \(-k=-\sigma (-k) \sim _{\pi } -\sigma (-l) = -l\), and by Lemma 11, we have that \(\sigma ^{t}(-k) \sim _{\pi } \sigma ^{t}(-l)\) for every integer \(t \ge 0\). Moreover, since \(-k=\sigma ^{4m_1}(-k)\), \(\sigma ^{4m_1}(-k) \sim _{\pi } \sigma ^{4m_1}(-l)\), and \({\pi }\) is a pairing, we must have \(-l=\sigma ^{4m_1}(-l)\). But, the equation \(-l = \sigma ^{t}(-l)\) holds only if t is an integer multiple of \(4m_2\), and hence, \(4m_1\) is a multiple of \(4m_2\). Similarly, \(4m_2\) is a multiple of \(4m_1\), and therefore, \(4m_1 = 4m_2\), and the partition \({{{\hat{\pi }}}}\) satisfies condition (2). A similar argument shows that \({{{\hat{\pi }}}}\) satisfies condition (1) if we suppose (1’) holds. Assume now \({{{\hat{\pi }}}} = {{{\hat{\pi }}}}_{1} \sqcup {{{\hat{\pi }}}}_{2}\). By Proposition 9, there is an integer \(1 < {\hat{k}} \le 2m_{1}\) satisfying one of the following:
-
(a)
\(1 \sim _{{{\hat{\pi }}}} {\hat{k}}\), \(-1 \sim _{{{\hat{\pi }}}} -{\hat{k}}\), and \(1+{\hat{k}}\) is odd.
-
(b)
\(1 \sim _{{{\hat{\pi }}}} - {\hat{k}}\), \(-1 \sim _{{{\hat{\pi }}}} {\hat{k}}\), and \(1+{\hat{k}}\) is odd.
and there is an integer \(2m_1+1 < {\hat{l}} \le 2m_{1} + 2m_2 \) satisfying one of the following:
-
(A)
\(2m_1 +1 \sim _{{{\hat{\pi }}}} {\hat{l}}\), \(-2m_1 -1 \sim _{{{\hat{\pi }}}} -{\hat{l}}\), and \(2m_1 +1+{\hat{l}}\) is odd.
-
(B)
\(2m_1 +1 \sim _{{{\hat{\pi }}}} -{\hat{l}}\), \(-2m_1 -1 \sim _{{{\hat{\pi }}}} {\hat{l}}\), and \(2m_1 +1+{\hat{l}}\) is odd.
If (a) holds, we know that \(\sigma ^{t}(-1) \sim _{\pi } \sigma ^{t}(-{\hat{k}})\) for every integer \(t \ge 0\) by Lemma 11. But then, since \(-{\hat{k}} = \sigma ^{2{\hat{k}}-2}(-1)\), \(\sigma ^{2{\hat{k}}-2}(-1) \sim _{{\pi }} \sigma ^{2{\hat{k}}-2}(-{\hat{k}})\), and \({\pi }\) is a pairing, we must have \(\sigma ^{2{\hat{k}}-2}(-{\hat{k}}) = -1\), or, equivalently, \(4{\hat{k}} - 4\) is a multiple of \(4m_{1}\). Therefore, \(m_{1}={\hat{k}}-1\) is odd, and \( \sigma ^{t_1}(-1) \sim _{{{\hat{\pi }}}} \sigma ^{t_1}(-m_1 - 1)\), and hence,
On the other hand, if (b) holds, it follows from Lemma 11 that \(\sigma ^{t}(1) \sim _{\pi } \sigma ^{-t}(-{\hat{k}}')\) for every integer \(t \ge 0\). Moreover, since \({\hat{k}}'\) has the same parity as \( 1+ {\hat{k}}\), we have \({\hat{k}}'=2k-1\) for some integer \(k \ge 1\). But then, since \(k = \sigma ^{2k-2}(1) = -\sigma ^{2-2k}(2k-1)\) and \(\sigma ^{2k-2}(1) \sim _{{\pi }} \sigma ^{2-2k}(2k-1)\), we have \(k \sim _{\pi } -k\), and therefore,
Similar arguments show that if (A) holds, then \(m_{2}\) is odd and
and if (B) holds, then there is an integer l such that
This completes the proof that if \(\textrm{p}_{{{{\hat{\pi }}}}}\) is the zero polynomial, then \({{{\hat{\pi }}}}\) must satisfy either (1), (2), (3), (4), (5), or (6). \(\square \)
4 The Bounded Cumulants Property
In this section, we first prove Lemma 3, and then, before we can apply it to get the conclusion in Theorem 4, we need to establish the relations between the notion of asymptotic free independence, the bounded cumulants property, and linear functionals on an algebra of non-commutative polynomials.
Proof of Lemma 3
Put \(V_k= U^{*}_{N,{i}_k} U_{N,{i}_{\gamma (k)}}\) for \(k=1,2, \ldots , m\) and note that
Now, letting \(\mathbf {a(j)}, {\textbf{v}}_1({\textbf{j}}), {\textbf{v}}_2({\textbf{j}}), \ldots , {\textbf{v}}_n({\textbf{j}})\) be given by
for each function \({\textbf{j}}:[\pm m] \rightarrow [N]\), we have that
since the matrices \(A_k\) are deterministic and the classical cumulants are multi-linear. By hypothesis, the family of random matrices \(\left\{ V_{l}\right\} _{l=1}^{m}\) is distribution-invariant under conjugation by signed permutation matrices, thus given a function \({\textbf{j}}:[\pm m] \rightarrow [N]\) we have
for all signs \(\epsilon _{1},\epsilon _{2},\ldots ,\epsilon _{N} \in \{\pm 1 \}\) and permutations \(\sigma \in \textrm{Sym}(N)\). This implies that
whenever \( \textrm{ker} \left( {{\textbf{j}}} \right) \) contains at least one block of odd size, and
provided a function \(\mathbf {j'}:[\pm m] \rightarrow [N]\) satisfies \( \textrm{ker} \left( {\mathbf {j'}} \right) = \textrm{ker} \left( {{\textbf{j}}} \right) \). Thus, letting \({\mathfrak {c}}_n \left[ \pi \right] \) denote the common value \({\mathfrak {c}}_{n} \left[ {\textbf{v}}_{1}({\textbf{j}}),\ldots ,{\textbf{v}}_{n}({\textbf{j}})\right] \) among all those functions \({\textbf{j}}:[\pm m] \rightarrow [N]\) satisfying \( \textrm{ker} \left( {{\textbf{j}}} \right) =\pi \), Equation (4.1) becomes
Moreover, the Möbius inversion formula in (2.3) implies
since for all partitions \(\theta \in P(\pm m)\) we have the relation
Hence, we get
Note that if a partition \(\theta \in P(\pm m)\) has a block of the form \(\{k,-k\}\), then
where \( (\star ) \) is a sum excluding the entries of \(A_{k}\). Therefore, since each \(A_{k}\) is assumed to be of trace zero, we have
where \(P_{\chi }(\pm m )\) denotes the set of all partitions in \(P_{\text {even}}( \pm m)\) with no blocks of the form \(\{k,-k\}\).
Now, for a partition \(\theta \in P_{\chi }(\pm m)\), each connected component of the graph \({\mathcal {G}}_{\theta }\), constructed as in Sect. 3.1, has at least two edges, and hence, \({\mathcal {G}}_{\theta }\) has at most \(\frac{m}{2}\) connected components. Thus, from Theorem 5, Proposition 6, and the equality in (4.4), we get
Since the sums above are over the finite sets \(P_{\text {even}}(\pm m)\) and \(P_{\chi }(\pm m)\), our proof will be complete if we show that there is a constant \(C_{n}\) independent from N such that
for all functions \({\textbf{j}}:[\pm m] \rightarrow [N]\). Let \({\textbf{j}}:[\pm m] \rightarrow [N]\) be arbitrary. By Hölder’s inequality, letting \(m_B:= \sum _{k \in B} m_k \) for any given subset B of [n], we have
But, by hypothesis, the p-norms of the entries of \( \sqrt{N} V_{l}\) are uniformly bounded, i.e., there are constants \(C_p = \max _{k=1}^{m}C_{p}(i_k,i_{\gamma (k)})\) with \(p=1,2,\ldots , m\) such that
for all integers \(1 \le j_{l},j_{-\gamma (l)} \le N\) and \(l=1,2,\ldots , m\), and hence, we get
Now, the moment–cumulants relation in (2.4) implies
so it follows that
And the proof of Lemma 3 is now complete. \(\square \)
Now, asymptotic free independence and the bounded cumulants property can be stated in terms of some linear functionals, and, by doing so, we can show the bounded cumulants property is actually equivalent to a condition that is a consequence of Lemma 3, see Proposition 15 and Corollary 16. Thus, to prove Theorem 4, we first examine the relations between the notion of asymptotic free independence, the bounded cumulants property, and linear functionals on an algebra of non-commutative polynomials first.
4.1 Multi-linear Functionals on Non-commutative Polynomials and Notions from Free Probability
Let I be a non-empty set. Let \({\mathcal {A}}\) denote the algebra of non-commutative polynomials \({\mathbb {C}}\left\langle \textrm{x}_{i} \mid i \in I \right\rangle \), and let \({\mathcal {A}}_{i} \subset {\mathcal {A}}\) denote the algebra of polynomials \({\mathbb {C}}\left[ x_{i} \right] \) for each index \(i \in I\). Suppose we are given random matrix ensembles \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i\in I\) where each \(X_{N,i}\) is a N-by-N random matrix and consider the sequence of unital linear functional \(\{\varphi _{N}: {\mathcal {A}}\rightarrow {\mathbb {C}}\}_{N=1}^{\infty }\) where each \(\varphi _{N}\) is defined by
Note that the two conditions necessary for the random matrix ensembles \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i\in I\) to be asymptotically freely independent, namely (AF.1) and (AF.2) from Definition 1, can be stated in terms of the linear functionals \(\varphi _{N}\) as
-
(AF.1)
\(\displaystyle \lim _{N\rightarrow \infty }\varphi _{N} \left[ \textrm{p}_{}\right] \) exists for every \(\textrm{p}_{} \in {\mathcal {A}}_{i}\) and every \(i\in I\), and
-
(AF.2)
\(\displaystyle \lim _{N \rightarrow \infty } \varphi _{N}\left[ (\textrm{p}_{1} - \varphi _{N}\left[ \textrm{p}_{1}\right] ) (\textrm{p}_{2} - \varphi _{N}\left[ \textrm{p}_{2}\right] ) \cdots (\textrm{p}_{m} - \varphi _{N}\left[ \textrm{p}_{m}\right] ) \right] = 0 \) whenever \(\textrm{p}_{k} \in {\mathcal {A}}_{i_{k}} \) with \(i_{1}\ne i_{2}, i_{2} \ne i_{3}, \ldots , i_{m-1} \ne i_{m}\)
Moreover, assuming that (AF.1) holds, we can replace each \(\varphi _{N}\left[ \textrm{p}_{k}\right] \) appearing in (AF.2) by \(\varphi _{}\left[ \textrm{p}_{k}\right] :=\lim _{N\rightarrow \infty }\varphi _{N} \left[ \textrm{p}_{k}\right] \); more concretely, we have the following.
Proposition 14
Suppose each ensemble \(\{X_{N,i}\}_{N=1}^{\infty }\) has a limiting distribution, namely \(\varphi _{}\left[ \textrm{p}_{}\right] :=\lim _{N\rightarrow \infty }\varphi _{N} \left[ \textrm{p}_{}\right] \) exists for every \(\textrm{p}_{} \in {\mathcal {A}}_{i}\) and every \(i\in I\). Then the ensembles \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i\in I\) are asymptotically freely independent if and only if the following holds:
-
(AF.2’)
\(\displaystyle \lim _{N \rightarrow \infty } \varphi _{N}\left[ (\textrm{p}_{1} - \varphi _{}\left[ \textrm{p}_{1}\right] ) (\textrm{p}_{2} - \varphi _{}\left[ \textrm{p}_{2}\right] ) \cdots (\textrm{p}_{m} - \varphi _{}\left[ \textrm{p}_{m}\right] ) \right] = 0 \) whenever \(\textrm{p}_{k} \in {\mathcal {A}}_{i_{k}} \) with \(i_{1}\ne i_{2}, i_{2} \ne i_{3}, \ldots , i_{m-1} \ne i_{m}\)
Moreover, if either (AF.2) or (AF.2’) holds, then \(\lim _{N\rightarrow \infty }\varphi _{N} \left[ \textrm{p}_{}\right] \) exists for every \( \textrm{p}_{} \in {\mathcal {A}}\).
Proof
Let J be the set of all positive integers m satisfying the following property: if \(\textrm{p}^{}_{1} \in {\mathcal {A}}_{i^{}_{1}}\), \(\textrm{p}^{}_{2} \in {\mathcal {A}}_{i^{}_{2}}\), \(\ldots \), \(\textrm{p}^{}_{m} \in {\mathcal {A}}_{i^{}_{m}}\) with \(i_{1},i_{2},\ldots ,i_{m}\in I\) and \(i^{}_{1} \ne i^{}_{2}, i^{}_{2} \ne i^{}_{3}, \ldots , i^{}_{m_{}-1} \ne i^{}_{m_{}} \), then \(\lim _{N \rightarrow \infty } \varphi _{N} \left[ \textrm{p}_{1} \textrm{p}_{2} \cdots \textrm{p}_{m} \right] \) exists. Since the algebras \({\mathcal {A}}_{i}\) with \(i \in I\) generate \({\mathcal {A}}\) and each \(\varphi _{N}\) is linear, \(\lim _{N\rightarrow \infty }\varphi _{N} \left[ \textrm{p}_{}\right] \) exists for every \( \textrm{p}_{} \in {\mathcal {A}}\) if the set J contains every positive integer. Now, by hypothesis, 1 belongs to J, so let us assume \(1, 2, \ldots , m-1\) belong to J and suppose \(\textrm{p}^{}_{1}, \textrm{p}^{}_{2}, \ldots , \textrm{p}^{}_{m}\) are as above. Thus, if \(S=\{ k_{1}< k_{2}< \cdots < k_{\left| {S} \right| } \}\) is a strict subset of [m], the limits
where \(S^{c}\) denotes the complement of S in the set [m] and \({\vert S^{c} \vert }\) denotes the cardinality of \(S^{c}\), exist. Moreover, if (AF.2) holds, the equality
implies \(\lim _{N\rightarrow \infty }\varphi _N \left[ \textrm{p}_{1} \cdots \textrm{p}_{m} \right] \) exists. And therefore, J contains every positive integer by induction on m. Similarly, if (AF.2’) holds, then \(\lim _{N\rightarrow \infty }\varphi _N \left[ \textrm{p}_{1} \cdots \textrm{p}_{m} \right] \) exists, and hence J contains every positive integer, since each \(\varphi _{N}\left[ \textrm{p}_{k} \right] \) in the equality above can be replaced by \(\varphi _{}\left[ \textrm{p}_{k} \right] \).
Let us now show that (AF.2) and (AF.2’) are equivalent. Suppose \(\textrm{p}^{}_{1} \in {\mathcal {A}}_{i^{}_{1}}, \textrm{p}^{}_{2} \in {\mathcal {A}}_{i^{}_{2}}, \ldots , \textrm{p}^{}_{m} \in {\mathcal {A}}_{i^{}_{m}}\) with \(i_{1},i_{2},\ldots ,i_{m}\in I\) and \(i^{}_{1} \ne i^{}_{2}, i^{}_{2} \ne i^{}_{3}, \ldots , i^{}_{m_{}-1} \ne i^{}_{m_{}} \) and take \(\textrm{q}_k=\textrm{p}_k-\varphi \left[ \textrm{p}_k \right] \) for \(k=1,2,\ldots , m\). We then have \(\lim _{N\rightarrow \infty } \varphi _{N}\left[ \textrm{q}_{k} \right] = 0 \) and the equality
Thus, if condition (AF.2’) holds, then \(\lim _{N\rightarrow \infty }\varphi _{N} \left[ \textrm{p}_{}\right] \) exists for every \( \textrm{p}_{} \in {\mathcal {A}}\), and hence,
additionally, we have \( \lim _{N\rightarrow \infty } \varphi _N \left[ (\textrm{p}_{1}-\varphi \left[ \textrm{p}_{1} \right] ) \cdots (\textrm{p}_{m}-\varphi \left[ \textrm{p}_{m} \right] ) \right] = \lim _{N\rightarrow \infty }\varphi _{N} \left[ \textrm{q}_{1} \cdots \textrm{q}_{m} \right] = 0 \), and thus
This shows that (AF.2’) implies (AF.2). Similarly, (AF.2) implies (AF.2’). \(\square \)
In the literature, however, the most common definition of asymptotic free independence for random matrix ensembles in terms of the linear functionals \(\varphi _{N}\) defined by (4.5) goes as follows: \(\{X_{N,i}\}_{N=1}^{\infty }\) with \(i\in I\) are asymptotically freely independent if they have a joint limiting (algebraic) distribution, i.e., \( \lim _{N \rightarrow \infty } \varphi _{N}\left[ \textrm{p} \right] \) exist for every polynomial \(\textrm{p}\in {\mathcal {A}}\), and letting \(\varphi _{}:= \lim _{N \rightarrow \infty } \varphi _{N}\), we have
whenever \(\textrm{p}_{k} \in {\mathcal {A}}_{i_{k}} \) with \(i_{1}\ne i_{2}, i_{2} \ne i_{3}, \ldots , i_{m-1} \ne i_{m}\). The previous proposition shows equivalence between the common definition of asymptotic free independence and the one given in the introduction of this paper.
Now, the bounded cumulants property for the random matrix ensemble \(\{ \{X_{N,i}\}_{i\in I}\}_{N=1}^{\infty }\) can also be established in terms of multi-linear functionals. If for each integer \(n\ge 1\), we consider the n-linear map \(\rho _{N}: {\mathcal {A}}\times \cdots \times {\mathcal {A}} \rightarrow {\mathbb {C}}\) defined by
for all \(\textrm{p}_{1}, \textrm{p}_{2},\ldots , \textrm{p}_{n} \in {\mathcal {A}}\) and where \({\mathfrak {c}}_{n}[\cdot ,\ldots ,\cdot ]\) denotes the classical cumulant, from Sect. 2.1, the random matrix ensemble \(\{ \{ X^{}_{N,i} \}_{i \in I} \}_{N=1}^{\infty }\) has then the bounded cumulants property if only if
for all \(\textrm{p}_{1}, \textrm{p}_{2},\ldots , \textrm{p}_{n} \in {\mathcal {A}}\) and all integers \(n\ge 1\). Moreover, under some mild assumptions, each polynomial \(\textrm{p}_{k}\) appearing in (4.7) can be replaced by
for some polynomials \(\textrm{p}^{(k)}_{1} \in {\mathcal {A}}_{i^{(k)}_{1}}, \textrm{p}^{(k)}_{2} \in {\mathcal {A}}_{i^{(k)}_{2}}, \ldots ,\textrm{p}^{(k)}_{m_{k}} \in {\mathcal {A}}_{i^{(k)}_{m_{k}}}\) and still get the bounded cumulants property.
Proposition 15
Suppose \(\varphi _N: {\mathcal {A}} \rightarrow {\mathbb {C}}\) is a unital linear functional and \(\rho _N: {\mathcal {A}}\times \cdots \times {\mathcal {A}} \rightarrow {\mathbb {C}}\) is an n-linear functional for each integer \(N \ge 1\). If the limits \( \lim _{N \rightarrow \infty }\varphi _N\left[ \textrm{p}\right] \) and \(\lim _{N \rightarrow \infty }\rho _N\left[ \textrm{p}_1,\textrm{p}_2,\ldots ,\textrm{p}_n\right] \) exist for all \(\textrm{p} \in {\mathcal {A}}, \textrm{p}_1 \in {\mathcal {A}}_{{i}_1},\textrm{p}_2 \in {\mathcal {A}}_{{i}_2},\ldots , \textrm{p}_n \in {\mathcal {A}}_{{i}_n} \) with \({i}_{1},{i}_{2},\ldots ,{i}_{n} \in I\), then the following are equivalent:
-
(1)
\( \displaystyle \sup _{N} \left| { \rho _N\left[ \textrm{p}_1,\textrm{p}_2,\ldots ,\textrm{p}_n\right] } \right| < \infty \) for all \(\textrm{p}_1,\textrm{p}_2,\ldots ,\textrm{p}_n \in {\mathcal {A}}\)
-
(2)
\(\displaystyle \sup _{N} \left| { \rho _N\left[ \textrm{q}_1,\textrm{q}_2,\ldots ,\textrm{q}_n\right] } \right| < \infty \) if each \(\textrm{q}_k\) is of the form
$$\begin{aligned}\textrm{q}_k=\textrm{p}^{(k)}_1 \textrm{p}^{(k)}_2 \cdots \textrm{p}^{(k)}_{m_k}\end{aligned}$$with \(\textrm{p}^{(k)}_{j} \in {\mathcal {A}}_{i^{(k)}_{j}}\) and \(i^{(k)}_{1} \ne i^{(k)}_{2}, i^{(k)}_{2} \ne i^{(k)}_{3}, \ldots , i^{(k)}_{m_{k}-1} \ne i^{(k)}_{m_{k}} \)
-
(3)
\(\displaystyle \sup _{N} \left| { \rho _N \left[ \textrm{q}_{N,1}, \textrm{q}_{N,2}, \ldots , \textrm{q}_{N,n} \right] } \right| < \infty \) if each \(\textrm{q}_{N,k}\) is of the form
$$\begin{aligned}\textrm{q}_{N,k}= ( \textrm{p}^{(k)}_1 - \varphi _N[\textrm{p}^{(k)}_1] ) ( \textrm{p}^{(k)}_2 - \varphi _N[\textrm{p}^{(k)}_2] ) \cdots ( \textrm{p}^{(k)}_{m_k}-\varphi _N [\textrm{p}^{(k)}_{m_{k}} ] ) \end{aligned}$$with \(\textrm{p}^{(k)}_{j} \in {\mathcal {A}}_{i^{(k)}_{j}}\) and \(i^{(k)}_{1} \ne i^{(k)}_{2}, i^{(k)}_{2} \ne i^{(k)}_{3}, \ldots , i^{(k)}_{m_{k}-1} \ne i^{(k)}_{m_{k}} \)
Proof
Conditions (1) and (2) are equivalent since each \(\rho _{N}\) is n-linear and the algebra \({\mathcal {A}}\) is generated by the sub-algebras \(\{{\mathcal {A}}_{i}\}_{i \in I}\). We only need to prove that (1) implies (3) and (3) implies (2).
Suppose (1) holds and let \(\textrm{q}_{N,k}\) is as in (3) for \(k=1,2,\ldots ,n\). Then, by multi-linearity, we have
The sum above is a finite sum, and, by hypothesis, each of its elements is uniformly bounded with respect to N. Hence, (3) follows.
Let us assume now (3) holds, and let J be the set of all positive integers m satisfying the following property: If \(m=m_{1}+m_{2}+\cdots + m_{n}\) for some positive integers \(m_{1},m_{2},\ldots ,m_{n}\), and \(\textrm{p}^{(k)}_{j} \in {\mathcal {A}}_{i^{(k)}_{j}}\) for \(j=1,2,\ldots ,m_k\) and \(i^{(k)}_{1} \ne i^{(k)}_{2}, i^{(k)}_{2} \ne i^{(k)}_{3}, \ldots , i^{(k)}_{m_{k}-1} \ne i^{(k)}_{m_{k}} \) for \(k=1,2,\ldots ,n\), then \(\displaystyle { \sup _{N} \left| { \rho _N (\textrm{q}_{1}, \textrm{q}_{2}, \ldots , \textrm{q}_{n} ) } \right| } < \infty \) where each \(\textrm{q}_k\) is given by \(\textrm{q}_{k}=\textrm{p}^{(k)}_1 \textrm{p}^{(k)}_2 \cdots \textrm{p}^{(k)}_{m_k}\). Note that we are done if we show that \(J=\{n,n+1,n+2,\ldots \}\). By hypothesis, n belongs to J, so let us assume \(n, n+1, \ldots , m-1\) belong to J and let \(\textrm{p}^{(k)}_j\), \(\textrm{q}_{N,k}\) and \(\textrm{q}_k\) as above. Consider the equality
given by n-linearity of \(\rho _N\). Now, since (3) holds, \(\rho _N ( \textrm{q}_{N,1}, \ldots , \textrm{q}_{N,n} )\) is uniformly bounded with respect to N and, by induction hypothesis, so is \(\rho _N [\vec {\prod _{j \in J_{1} }} \textrm{p}^{(k)}_{j}, \ldots , \vec {\prod _{j \in J_{n} }} \textrm{p}^{(k)}_{j}] \) if at least one \(J_{k}\) is not \([m_{k}]\). Thus, \( \rho _N ( \textrm{q}_{1}, \ldots , \textrm{q}_{n} )\) is also uniformly bounded with respect to N, and hence, m belongs to J. \(\square \)
The multi-linear functionals \(\rho _{N}: {\mathcal {A}}\times \cdots \times {\mathcal {A}} \rightarrow {\mathbb {C}}\) given by (4.6) are tracial in each entry, i.e., for ever integer \(k \in [n]\) and polynomials \(\textrm{q}_{0},\textrm{q}_{1},\ldots ,\textrm{q}_{n} \in {\mathcal {A}}\), we have
This traciality allows us to impose the condition that \(i^{(k)}_{m_{k}} \ne i^{(k)}_{1}\) in (2) and (3) from Proposition 15 and still get uniform boundedness of \(\rho _N\left[ \textrm{p}_1,\textrm{p}_2,\ldots ,\textrm{p}_n\right] \) with respect to N.
Corollary 16
Suppose \({\mathcal {A}}\), \({\mathcal {A}}_{i}\), \(\varphi _{N}\), and \(\rho _{N}\) are as in Proposition 15. If \(\rho _{N}\) is tracial in each entry, then condition (1) from Proposition 15 is equivalent to any of the following:
-
(2’)
\(\displaystyle \sup _{N} \left| {\left[ \textrm{q}_1,\textrm{q}_2,\ldots ,\textrm{q}_n\right] } \right| < \infty \) if each \(\textrm{q}_k\) is of the form \(\textrm{q}_k=\textrm{p}^{(k)}_1 \textrm{p}^{(k)}_2 \cdots \textrm{p}^{(k)}_{m_k}\) with \(\textrm{p}^{(k)}_{j} \in {\mathcal {A}}_{i^{(k)}_{j}}\) and \(i^{(k)}_{1} \ne i^{(k)}_{2}, i^{(k)}_{2} \ne i^{(k)}_{3}, \ldots , i^{(k)}_{m_{k}-1} \ne i^{(k)}_{m_{k}}\), and \(i^{(k)}_{m_{k}} \ne i^{(k)}_{1} \)
-
(3’)
\(\displaystyle \sup _{N} \left| {\rho _N \left[ \textrm{q}_{N,1}, \textrm{q}_{N,2}, \ldots , \textrm{q}_{N,n} \right] } \right| < \infty \) if each \(\textrm{q}_{N,k}\) is of the form
$$\begin{aligned}\textrm{q}_{N,k}= ( \textrm{p}^{(k)}_1 - \varphi _N[\textrm{p}^{(k)}_1] ) ( \textrm{p}^{(k)}_2 - \varphi _N[\textrm{p}^{(k)}_2] ) \cdots ( \textrm{p}^{(k)}_{m_k}-\varphi _N [\textrm{p}^{(k)}_{m_{k}} ] ) \end{aligned}$$with \(\textrm{p}^{(k)}_{j} \in {\mathcal {A}}_{i^{(k)}_{j}}\) and \(i^{(k)}_{1} \ne i^{(k)}_{2}, i^{(k)}_{2} \ne i^{(k)}_{3}, \ldots , i^{(k)}_{m_{k}-1} \ne i^{(k)}_{m_{k}}\), and \(i^{(k)}_{m_{k}} \ne i^{(k)}_{1}\)
Proof
Note that while condition (2) from Proposition 15 allows the indexes \(i^{k}_{1}\) and \(i^{k}_{m_{k}}\) to be possibly the same, condition (2’) above explicitly prohibits this. Thus, by traciality of \(\rho _{N}\) in each entry, we have that (2’) and (2) are equivalent, and hence, it only remains to show that (3’) above implies (3) from Proposition 15.
Assume (3’) holds and let J be the set of all positive integers m satisfying the following property: if \(m=m_{1}+m_{2}+\cdots + m_{n}\) for some positive integers \(m_{1},m_{2},\ldots ,m_{n}\), and \(\textrm{p}^{(k)}_{j} \in {\mathcal {A}}_{i^{(k)}_{j}}\) for \(j=1,2,\ldots ,m_k\) and \(i^{(k)}_{1} \ne i^{(k)}_{2}, i^{(k)}_{2} \ne i^{(k)}_{3}, \ldots , i^{(k)}_{m_{k}-1} \ne i^{(k)}_{m_{k}} \) for \(k=1,2,\ldots ,n\), then
where each \(\textrm{q}_{N,k}\) as above. By hypothesis, n belongs to J, so let us assume \(n, n+1, \ldots , m-1\) belong to J and let \(\textrm{p}^{(k)}_j\), \(\textrm{q}_{N,k}\) and \(\textrm{q}_k\) as above. Thus, if \(i^{(k)}_{m_{k}} \ne i^{(k)}_{1}\) for \(k=1,2,\ldots ,n\), Inequality (4.8) holds. On the other hand, if \(i^{(k)}_{m_{k}} = i^{(k)}_{1}\) for some \(k \in \{1,2,\ldots ,n\}\), let us consider polynomials \(\widetilde{\textrm{p}}^{}_{N,k}\) and \(\widetilde{\textrm{r}}_{N,k}\) given by
By traciality of \(\rho _{N}\) in the k-th entry, we have
moreover, from the relation
we get the equality
by linearity of \(\rho _{N}\) in the k-th entry. But then, by induction hypothesis, every element in the right-hand side of the equality above is uniformly bounded with respect to N, and therefore, so is \(\rho _N [ \textrm{q}_{N,1}, \ldots , \textrm{q}_{N,n} ]\). \(\square \)
Having proved Proposition 14 and Corollary 16, we can now show that, under the hypothesis of Theorem 4, the family of random matrix ensembles \(\{ \{ U^{}_{N,i} D^{}_{N,i} U^{*}_{N,i} \}_{N=1}^{\infty } \}_{i \in I}\) has the bounded cumulants property.
Proof of Theorem 4
Let \({\mathcal {A}}\) denote the algebra of non-commutative polynomials \({\mathbb {C}}\left\langle \textrm{x}_{i} \mid i \in I \right\rangle \), and let \({\mathcal {A}}_{i} \subset {\mathcal {A}} \) denote the algebra \({\mathbb {C}}\left[ x_{i} \right] \) for each index \(i \in I\). For each integer \(N\ge 1\), take \(X_{N,i} = U^{}_{N,i} D^{}_{N,i} U^{*}_{N,i} \) for every index \(i \in I\) and let \(\varphi _{N}: {\mathcal {A}}\rightarrow {\mathbb {C}}\) be the unital linear map defined by (4.5). Note that if \(\textrm{p} \in {\mathcal {A}}_{j}\) for some \(j \in I\), then \(\textrm{p}\left( \{X_{N,i}\}_{i \in I} \right) = U^{}_{N,j} \textrm{p}( D^{}_{N,j} ) U^{*}_{N,j} \), and hence, the limit \(\lim _{N\rightarrow \infty } \varphi _{N}[\textrm{p}]\) exists for every \(\textrm{p} \in {\mathcal {A}}_{i}\) and every \(i \in I\). Now, suppose we are given polynomials \(\textrm{p}^{}_{1} \in {\mathcal {A}}_{i^{}_{1}}, \textrm{p}^{}_{2} \in {\mathcal {A}}_{i^{}_{2}}, \ldots , \textrm{p}^{}_{m} \in {\mathcal {A}}_{i^{}_{m}}\) with \(i_{1},i_{2},\ldots ,i_{m}\in I\) and \(i^{}_{1} \ne i^{}_{2}, i^{}_{2} \ne i^{}_{3}, \ldots , i^{}_{m_{}-1} \ne i^{}_{m_{}} \), and \(i^{}_{m} \ne i^{}_{1}\). Note that
where
and each \(A^{}_{N,i^{}_{j}}\) is of trace zero and given by
Thus, by Lemma 3, there is a constant C depending only on the indexes \(i^{}_{j}\) such that
But then, since \(\sup _{N} \left\| {D_{N,i}} \right\| < \infty \) and \(\lim _{N\rightarrow \infty }\textrm{tr}( D^{k}_{N,i} )\) exists for every \(k\ge 1\) and any \(i \in I\), we have \(\sup _{N} \left\| {A^{}_{N,i^{}_{j}}} \right\| < \infty \), and therefore,
Each linear functional \(\varphi _{N}\) is tracial, i.e., \(\varphi _{N}[pq] = \varphi _{N}[qp]\) for all \(p,q \in {\mathcal {A}}\), and thus, following similar arguments to those in the proof of Corollary 16, we can remove the condition \(i_{m} \ne i_{1}\) and still get (4.9). Therefore, by Proposition 14, the random matrix ensembles \(\{ U^{}_{N,i} D^{}_{N,i} U^{*}_{N,i} \}_{N=1}^{\infty }\) with \(i \in I\) are asymptotically free, \( \lim _{N\rightarrow \infty } \varphi _{N}[ \textrm{p} ] \) exists for every \(\textrm{p} \in {\mathcal {A}} \), and (1.15) holds for \(n = 1\).
Fix now an arbitrary integer \(n\ge 2\) and let \(\rho _{N}: {\mathcal {A}}\times \cdots \times {\mathcal {A}} \rightarrow {\mathbb {C}}\) be the n-linear map given by (4.6) for every integer \(N \ge 1\). Note that
if \(\textrm{p}_{1} \in {\mathcal {A}}_{i_{1}}, \textrm{p}_{2} \in {\mathcal {A}}_{i_{2}}, \ldots , \textrm{p}_{n} \in {\mathcal {A}}_{i_{n}}\) for some \(i_{1},i_{2},\ldots ,i_{n} \in I\). Thus, since n is arbitrary, the family of ensembles \(\{ \{ U^{}_{N,i} D^{}_{N,i} U^{*}_{N,i} \}_{N=1}^{\infty } \}_{i \in I}\) has the bounded cumulants property if the multi-linear functional \(\rho _{N}\) satisfies (3’) from Corollary 16, namely
whenever each \(\textrm{q}_{N,k}\) is of the form
with \(\textrm{p}^{(k)}_{j} \in {\mathcal {A}}_{i^{(k)}_{j}}\) and \(i^{(k)}_{1} \ne i^{(k)}_{2}, i^{(k)}_{2} \ne i^{(k)}_{3}, \ldots , i^{(k)}_{m_{k}-1} \ne i^{(k)}_{m_{k}}\), and \(i^{(k)}_{m_{k}} \ne i^{(k)}_{1}\). Suppose \(i^{(k)}_{j}\), \(\textrm{p}^{(k)}_{j}\), and \(\textrm{q}_{N,k}\) are as above and take \(Y_{N,k}=\textrm{q}_{N,k}\left( \{X_{N,i}\}_{i \in I} \right) \) for \(k=1,2,\ldots , n\). Then, we have
Moreover, letting \(A_{N,i^{(k)}_{j}} = \textrm{p}^{(k)}_{j} ( D_{N,i^{(k)}_{j}} ) - \textrm{tr} ( \textrm{p}^{(k)}_{j} ( D_{N,i^{(k)}_{j}} ) ) I_{N} \) for each \(i^{(k)}_{j}\) and every \(N \ge 1\), we get \(A_{N,i^{(k)}_{j}}\) is of trace zero, \(\sup _{N} \left\| {A^{}_{N,i^{(k)}_{j}}} \right\| < \infty \), and
Therefore, by Lemma 3, there is a constant C depending only on the indexes \(i^{(k)}_{j}\) such that
\(\square \)
5 Fluctuation Moments
The proofs of Theorems 1 and 2 are very similar, and thus, in order to avoid redundancies, this section is devoted to prove only Theorem 1; nonetheless, what has to be modified to obtain the conclusions from Theorem 2 is pointed out in the next section.
Let \(X_{N,1}\) and \(X_{N,2}\) be as in Theorem 1. Assume \(Y_{N}=Y_{N,1} Y_{N,2} \cdots Y_{N,2m_{1}}\) and \(Z_{N} = Z_{N,1} Z_{N,2} \cdots Z_{N,2m_{2}}\) where \(Y_{N,k}\) and \(Z_{N,l}\) are given by (1.5) for some polynomials \(\textrm{p}_{1}, \textrm{p}_{2},\ldots , \textrm{p}_{2m_{1}}, \textrm{q}_{1}, \textrm{q}_{2}, \ldots , \textrm{q}_{2m_{2}}\in {\mathbb {C}}[\textrm{x}]\) and some indexes \(i_1, i_2, \ldots , i_{2m_{_1}}, j_{1},j_{2},\ldots ,j_{2m_{_2}} \in \{1,2\}\) satisfying \(i_{1}=j_{1}\) and (1.6). Note that
and
with \(A_{N,k}\) and \(B_{N,l}\) defined as in (1.11); moreover, we have \( i_{2k-1} = j_{2\,l-1} = i_{1} \ne i_{2} = i_{2k} = j_{2\,l}\). Thus, following similar arguments to those in the proof of Lemma 3, we obtain
where \(P_{\chi }(\pm {2m})\) denotes the set of all even partitions of \([\pm {2m}]\) with no blocks of the form \(\{k,-k\}\), \(\mu :P(\pm {2\,m} ) \times P( \pm {2\,m})\rightarrow {\mathbb {C}}\) is the Möbius inversion function, \(\mathbf {a(j)}\) is given by
for function each \({\textbf{j}}: [\pm {2m} ] \rightarrow [N]\), and if \({\textbf{j}}: [\pm {2m} ] \rightarrow [N]\) satisfies \( \textrm{ker} \left( {{\textbf{j}}} \right) = \pi \), then
with \(V^{}_{2k-1} = V^{*}_{2k} = U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} \) for \(k = 1,2,\ldots , m\) and \(\sigma \in \textrm{Sym}(\pm 2\,m)\) is the cyclic permutation given by
It turns out that (5.1) becomes
where \(P_{\chi \chi }(\pm {2m})\) denotes the set of all partitions \(\theta \in P_{\chi }(\pm {2m})\) such that the graph sum exponent \(\tau _{\theta }\), defined in Sect. 3.1, equals m. Indeed, if we are given partitions \(\pi \in P_{\text {even}}(\pm {2\,m})\) and \(\theta \in P_{\chi }(\pm {2\,m}) \) satisfying \(\theta \ge \pi \), then Theorem 5 and Proposition 6 imply
where \(\tau _{\theta }\) is the number of connected components of the graph \({\mathcal {G}}_{\theta }\). Now, by hypothesis, \(\sup _{N} \left\| {D_{N,i}} \right\| < \infty \) and \(\lim _{N\rightarrow \infty }\textrm{tr}( D^{k}_{N,i} )\) exists for every \(k\ge 1\) and any \(i \in \{1,2\}\), so we have
Moreover, every connected component of \({\mathcal {G}}_{\theta }\) contains at least two edges since \(\theta \) is even and has no blocks of the form \(\{-k,k\}\), and hence, the graph sum exponent \(\tau _{\theta }\) satisfies
Additionally, since the unitary ensemble \(\{\{U_{N,1},U_{N,2}\}\}_{N=1}^{\infty }\) satisfies (II) from Lemma 3, it follows from the proof of Lemma 3 that there is a constant \(C_{2}\) independent from N satisfying
Therefore, from (5.4) we obtain
unless the graph sum exponent \(\tau _{\theta } = m\), and, consequently, we get (5.3).
Note that the condition \(\tau _{\theta } = m\), for an even partition \(\theta \in P(\pm 2m)\) with no blocks of the form \(\{+k,-k\}\), forces each component of the undirected graph \({{\mathcal {G}}}_{\theta }\) to have exactly two edges. Thus, for any partition \(\theta \in P_{\chi \chi }(\pm {2\,m})\), each component of the directed graph \(\vec {{\mathcal {G}}}_{\theta }\) has one of the following forms:
And therefore, as illustrated at the end of Sect. 3.1, each graph sum \(\sum _{\begin{array}{c} \textrm{ker}({\textbf{j}}) \ge \theta \end{array}}{\textbf{a}}({\textbf{j}})\) appearing in (5.3) can be written as a product of traces of matrices where each trace is of the following forms: \(\textrm{Tr} ( {C_{N,k}C_{N,l}} ) \), \(\textrm{Tr} ( {C^{}_{N,k}C^{T}_{N,l}} ) \), or \(\textrm{Tr} ( {C_{N,k} \circ C_{N,l}} ) \) where \(C_{N,k}\) and \(C_{N,l}\) belong to the set \(\{A_{N,1}, \ldots , A_{N,2m_{1}},B_{N,1},\ldots , B_{N,2m_{2}}\}\). Hence, letting \({\mathfrak {c}}[\pi ]\) be given by (5.2) for each partition \(\pi \in P(\pm 2\,m)\), the conclusions in Theorem 1 will follow from (5.3) once we determine the order of
Now, recall the values of Möbius inversion function are determined by (2.1), and given explicitly by (2.2). Thus, to determine the order of (5.6), it is enough to compute \({\mathfrak {c}}_{2}[\pi ]\) for even partitions \(\pi \in P(\pm 2m)\) satisfying \(\pi \le \theta \) for some other partition \(\theta \) in the set \(P_{\chi \chi }(\pm {2m} )\).
Proposition 17
Suppose \(\theta \) is a partition in \(P_{\chi \chi }(\pm {2m} )\). If \(\pi \) is an even partition such that \(\pi \le \theta \) and \({\mathfrak {c}}_{2}[\pi ]\) is given by (5.2), then the following holds:
-
(1)
for \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = \frac{1}{\sqrt{N}} W^{*} H^{} W\), we have
$$\begin{aligned} N^{m}{\mathfrak {c}}_{2}[ \pi ]&= \left\{ \begin{array}{cl} 1 + O\left( N^{-1}\right) &{} \text {if there is a symmetric pairing partition }\\ &{} {{\hat{\theta }}} \le \pi \text { satisfying either (1) or }\\ &{} (2) \text { from Proposition 13} \\ O\left( N^{-1/2}\right) &{} \text {otherwise. } \end{array} \right. \end{aligned}$$ -
(2)
for \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = \frac{1}{\sqrt{N}} W^{*} X H^{} W\), we obtain
-
(3)
for \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = \frac{1}{N} W^{*} H^{*}X H^{} W\), we get
The proof of Proposition 17 is based on the expected value of products of entries from X and W, see relations (2.5) and (2.6), and the results on graph sums of the discrete Fourier transform from Sect. 3.2; however, it requires some technical intermediate steps, so we will omit it for now and leave it to the end of this section. Nonetheless, the computation of (5.6) up to a term of order \(N^{-m-1/2}\) is quite simple assuming that Proposition 17 holds.
Lemma 18
Suppose \(\theta \) is a partition in \(P_{\chi \chi }(\pm {2m} )\) and let \({\mathfrak {c}}[\pi ]\) be given by (5.2) for each partition \(\pi \in P(\pm 2\,m)\). Then, the following holds:
-
(1)
for \( U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = \frac{1}{\sqrt{N}} W^{*} H W\), we have
-
(2)
for \( U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = \frac{1}{\sqrt{N}} W^{*} XH W^{*}\), we obtain
-
(3)
for \( U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = \frac{1}{N} W^{*} H^{*}XH W^{}\), we get
Proof
Suppose \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}}=W^{*}XHW/\sqrt{N}\). Propositions 13 and 17 imply that
unless there are integers \( 1\le k \le 2m_{1} < l \le 2m_{1} + 2m_{2}\) satisfying one of the following:
-
(i)
\(k+l\) is even and \(\sigma ^{t}(-k) \sim _{\theta } \sigma ^{-t}(l)\) for all integers \(t \ge 0\) or
-
(ii)
\(k+l\) is odd, \(\sigma ^{t}(-k) \sim _{\theta } \sigma ^{t}(-l)\) for all integers \(t \ge 0\) and \({\mathcal {G}}_{\theta }\) has only double loops as components
Assuming that (i) above holds, consider the pairing partition \({{\hat{\theta }}} = \{ \{ \sigma ^{t}(-k), \sigma ^{-t}(l) \}\mid t \ge 0\}\) and note that Proposition 17 implies that
Moreover, since \(N^{m}{\mathfrak {c}}_{2} \left[ \pi \right] = 1 + O(N^{-1})\) for any partition \(\pi \) satisfying \({{\hat{\theta }}} \le \pi \le \theta \), we get
from equations in (2.1) defining the Möbius inversion function. On the other hand, if (ii) above holds, consider \({{\hat{\theta }}} = \{ \{ \sigma ^{t}(-k), \sigma ^{t}(-l) \}\mid t \ge 0\}\) instead and note that (5.7) above holds also in this case. Hence, since \(N^{m}{\mathfrak {c}}_{2} \left[ \theta \right] = 1 + O(N^{-1})\) and \(N^{m}{\mathfrak {c}}_{2} \left[ \pi \right] = O(N^{-1/2})\) for any partition \({{\hat{\theta }}} \le \pi < \theta \), we obtain
The other cases, namely \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*}HW /\sqrt{N} \) and \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*} H^{*}XH W/N\), are proved in the same way, one chooses a suitable pairing partition \({{\hat{\theta }}}\) such that (5.7) holds, and then the corresponding conclusion follows from Proposition 17 and the equations in (2.1) defining the Möbius function. \(\square \)
As mentioned earlier, the proof of Theorem 1 is complete once we apply Lemma 18 to the relation (5.3). For instance, suppose \( U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*} H^{*}XH W^{} / N\). Then, Theorem 5, Lemma 18, and (5.3) imply that
where \({\mathcal {P}}_{1}\) and \({\mathcal {P}}_{2}\) are subsets of \(P_{\chi \chi }(\pm {2m})\) given by
and
Now, note the set \({\mathcal {P}}_{1}\) has cardinality \(2m_{1}\) provided \(m_{1} = m_{2}\). Moreover, \(m_{1} = m_{2}\) implies that a partition \(\theta \in P(\pm 2m)\) belongs to the set \({\mathcal {P}}_{1}\) if and only if for some integer \(1\le l \le 2m_{1}\) the directed graph \(\vec {{\mathcal {G}}}_{\theta }\) can be represented as
where \(F_{k}\) denotes the edge \( E_{2m_{1}+k}\) and \(l-k\) is taken module \(2m_{1}\) for \(k=1,2,\ldots , 2m_{1}\). Thus, for each integer \(1\le l \le 2m_{1}\), there exists a unique \(\theta \in {\mathcal {P}}_{1}\) so that
and hence, we obtain
On the other hand, the set \({\mathcal {P}}_{2}\) has cardinality \(m_{1} \cdot m_{2}\) since
and
for \(l_{1}=1,2,\ldots , m_{1}\) and \(l_{2}=1,2,\ldots , m_{2}\). Moreover, a partition \(\theta \in P(\pm 2m)\) belongs to the set \({\mathcal {P}}_{2}\) if and only if for some integers \(1\le l \le m_{1}\) and \(1\le l_{2} \le m_{2}\) the directed graph \(\vec {{\mathcal {G}}}_{\theta }\) can be represented as
where \(l_{1}-k_{1}\) and \(l_{2}-k_{2}\) are taken modulo \(2m_{1}\) and \(2m_{2}\), respectively, for \(k_{1}=1,2,\ldots ,m_{1}\) and \(k_{2} = 1,2,\ldots ,m_{2}\). Thus, for each partition \(\theta \in {\mathcal {P}}_{2}\) there are integers \(1 \le l_{1} \le m_{1}\) and \(1 \le l_{2} \le m_{2}\) satisfying
Therefore, we have
The other cases, namely \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*}HW /\sqrt{N} \) and \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*} XH W/N\), are proved in the same way, applying Lemma 18 to the relation (5.3) we obtain similar relations to that in (5.8) that lead to (1) and (2) in Theorem 1.
The remaining of this section is devoted to the proof of Proposition 17. For clarity, we have considered two cases: \( U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*} H^{*} X H^{} W / N \) and \( U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*} Y H^{} W /\sqrt{N} \) where Y is either the identity matrix \(I_{N}\) or an N-by-N uniformly distributed signature matrix X. But first, let us introduce some more notation for partitions.
Given a partition \(\pi \in P(\pm 2\,m)\), we let \(\pi _{\text {even}}\) and \(\pi _{\text {odd}}\) denote the restriction of \(\pi \) to the sets \(\{ k \in [\pm 2\,m] \mid k \text { is even} \}\) and \(\{ k \in [\pm 2\,m] \mid k \text { is odd} \}\), respectively. Moreover, we let \(\pi ^{\text {even}}\) and \(\pi ^{\text {odd}}\) denote the partitions of \(\{ k \in [\pm 4\,m] \mid k \text { is even } \} \) and \(\{ k \in [\pm 4\,m] \mid k \text { is odd} \}\), respectively, given by \(\pi ^{\text {even}} = \{\{ 2k \mid k \in B \} \mid B \in \pi \}\) and \(\pi ^{\text {odd}} = \{\{ 2k-\textrm{sign}{(k)} \mid k \in B \} \mid B \in \pi \}\) where \(\textrm{sign}(k) = 1\), if k is positive, and \(\textrm{sign}(k) = -1\), otherwise. For instance, if \(\pi \) is the partition in \(P(\pm 6)\) given by
then
5.1 Case \(\varvec{ U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}}=\frac{1}{\sqrt{N}} W^{*} Y H^{} W}\)
Let Y be an N-by-N diagonal random matrix independent from W. Given a function \({\textbf{i}}: [\pm 2m] \rightarrow [N]\), we let
where \(\mathbf {h_{1}}({\textbf{i}})\), \(\mathbf {h_{2}}({\textbf{i}})\), \(\mathbf {y_{1}}({\textbf{i}})\), and \(\mathbf {y_{2}}({\textbf{i}})\) are given by
additionally, if we are given a function \({\textbf{j}}: [\pm 2\,m] \rightarrow [N]\), we put
where \({\textbf{w}}_{1}(\textbf{i,j})\) and \({\textbf{w}}_{2}(\textbf{i,j})\) are given by
Now, for every partition \(\pi \in P_{}(\pm {2m})\) and any function \({\textbf{j}}:[\pm {2\,m}] \rightarrow [N]\) satisfying \( \textrm{ker} \left( {{\textbf{j}}} \right) = \pi \), we define \({\mathfrak {C}}_{2} \left[ \pi \right] \) by
where \({\pi }_1\) and \({\pi }_2\) denote the restrictions of \({\pi }\) to \([\pm 2m_1]\) and \([\pm 2\,m ] {\setminus } [\pm 2m_1]\), respectively, and \(\sigma \in \textrm{Sym}(\pm 2m)\) is the cycle permutation given by
Proposition 19
Let \(\pi \) be an even partition in \(P(\pm {2m})\). Suppose \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*} Y H^{} W / \sqrt{N}\) where Y is an N-by-N diagonal matrix independent from W so that each entry Y(i, i) takes values in the set \(\{-1,1\}\). If \({\mathfrak {c}}_{2}[\pi ]\) and \({\mathfrak {C}}_{2} \left[ \pi \right] \) are given by (5.2) and (5.9), respectively, then
Proof
Fix a function \({\textbf{j}}:[\pm {2m}] \rightarrow [N]\) satisfying \( \textrm{ker} \left( {{\textbf{j}}} \right) = \pi \). Note that the \((j_{-2k+1},j_{2k-1})\)-entry of \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}}\) and the \((j_{-2k},j_{2k})\)-entry of \(U^{*}_{N,{i}_{2}} U^{}_{N,{i}_{1}}\) are given by
and
respectively. Thus, from (5.2) and the linearity of the covariance, we have that
where \({{\textbf{h}}}({\textbf{i}})\), \({{\textbf{w}}}_{1}\mathbf {(i,j)}\), \({{\textbf{w}}}_{2}\mathbf {(i,j)}\), \({\textbf{y}}_{1}\mathbf {(i)}\), \({\textbf{y}}_{2}\mathbf {(i)}\), and \(\varvec{\sigma }\) are defined as above. But, for every function \({\textbf{i}}:[\pm {2\,m}]\rightarrow [N]\), we have that
so we obtain
Moreover, from (2.6) we get that
provided \( \textrm{ker} \left( {{\textbf{i}}} \right) \ne \pi \) and \( \textrm{ker} \left( {{\textbf{i}}} \right) \not \ge \pi _{1} \sqcup \pi _{2} \), respectively. And hence, equality in (5.11) becomes
To obtain (5.10), it only remains to show that for \({\theta } \gneq \pi _{1} \sqcup \pi _{2} \), i.e., \(\theta \ge \pi _{1} \sqcup \pi _{2}\) but \(\theta \ne \pi _{1} \sqcup \pi _{2}\), implies
Suppose \({\theta } \in P(\pm {2m})\) satisfies \({\theta } \gneq \pi _{1} \sqcup \pi _{2} \). Then, we must have \(\#(\theta ) < \#(\pi _{1} \sqcup \pi _{2}) = \#(\pi _{1}) + \#(\pi _{2})\), or, equivalently,
Now, \({\textbf{h}}({\textbf{i}}\circ \varvec{{\sigma }})\) has absolute value 1 for any function \({\textbf{i}}:[\pm {2m}]\rightarrow [N]\) and \(\left| { {\mathbb {E}} \left[ {{{\textbf{y}}}_{1}({\textbf{i}})}\right] {\mathbb {E}} \left[ {{{\textbf{y}}}_{2}({\textbf{i}})}\right] } \right| \le 1\), so (2.6) implies
\(\square \)
Proof of (1) from Proposition 17
Let Y be the identity matrix \(I_{N}\). By Proposition 19, we only need to show that
where \({\mathfrak {C}}_{2} \left[ \pi \right] \) is given by (5.9). Note that from (2.6) and (5.9) we obtain the inequality
But then, if \(\textrm{p}_{\sigma ^{-1} \circ \pi }\) is a nonzero polynomial, so is \(\textrm{p}_{\sigma ^{-1} \circ \pi _{1} \sqcup \pi _{2} }\) by Proposition 10, and therefore, the last inequality and Corollary 8 would imply \( {\mathfrak {C}}_{2} \left[ \pi \right] = O(N^{-1/2}). \text { } \) And so, we can assume \(\textrm{p}_{\sigma ^{-1} \circ \pi }\) is the zero polynomial without loss of generality.
Now, for every function \({\textbf{i}}:[\pm {2m} ] \rightarrow [N]\) satisfying \( \textrm{ker} \left( {{\textbf{i}}} \right) =\pi \) we have \({\textbf{h}}({\textbf{i}}\circ \varvec{\sigma }) = 1\) since \(\textrm{p}_{\sigma ^{-1} \circ \pi }\) is the zero polynomial; additionally, (2.6) gives \( {\mathbb {E}} \left[ {{\textbf{w}}(\textbf{i,j})}\right] = \frac{(N-\#(\pi _{}))!}{N!} \) since \(\pi \) is an even partition. Thus, from (5.9) we obtain
Moreover, by Proposition 10, there is a symmetric pairing partition \({{\hat{\theta }}} \le \pi \) such that \(\textrm{p}_{\sigma ^{-1} \circ {{\hat{\theta }}}}\) is also the zero polynomial, and hence, the partition \({{\hat{\theta }}}\) must satisfy one of the conditions (1)-(6) from Proposition 13. Notice \({{\hat{\theta }}} = {\hat{\theta }}_{1} \sqcup {\hat{\theta }}_{2}\), where \({\hat{\theta }}_1\) and \({\hat{\theta }}_2\) denote the restrictions of \({{\hat{\theta }}}\) to \([\pm 2m_1]\) and \([\pm 2\,m ] {\setminus } [\pm 2m_1]\), respectively, implies
Indeed, if \({{\hat{\theta }}} = {\hat{\theta }}_{1} \sqcup {\hat{\theta }}_{2}\), then \({\hat{\theta }}_{1}\) and \({\hat{\theta }}_{2}\) must be even partitions, and so are \(\pi _{1}\) and \(\pi _{2}\) since \({{\hat{\theta }}} \le \pi \) implies \({\hat{\theta }}_{1} \le \pi _{1}\) and \({\hat{\theta }}_{2} \le \pi _{2}\), so (2.6) gives
for every function \({\textbf{i}}:[\pm {2m} ] \rightarrow [N]\) satisfying \( \textrm{ker} \left( {{\textbf{i}}} \right) =\pi _{1} \sqcup \pi _{2}\); moreover, Proposition 10 implies the polynomial \(\textrm{p}_{\sigma ^{-1} \circ \pi _1 \sqcup \pi _2}\) is also zero since \({{\hat{\theta }}} = {\hat{\theta }}_{1} \sqcup {\hat{\theta }}_{2} \le \pi _1 \sqcup \pi _2\), and thus, we obtain
Hence, (5.13) follows from (5.12) provided \({{\hat{\theta }}}\) satisfies either (3), (4), (5), or (6) from Proposition 13.
Assume now \({{\hat{\theta }}}\) satisfies either (1) or (2) from Proposition 13. Then, either \(\pi _1 \sqcup \pi _2\) contains some singletons, if \(\{k,l\} \in \pi \) or \(\{k,-l\} \in \pi \) for some integers \(1\le k \le 2m_{1} < l \le 2m_{1}+2m_{2}\), or \(\pi _1 \sqcup \pi _2 = \{\{-k,k\} \mid k \in [\pm 2\,m ]\}\), otherwise. In any case, the graph \(\vec {{\mathcal {G}}}_{\pi _1 \sqcup \pi _2}\) satisfies none of the conditions (1)-(6) from Remark 12 since \(m_{1}+m_{2} > 2\), and hence, the polynomial \(\textrm{p}_{\sigma ^{-1} \circ \pi _1 \sqcup \pi _2}\) is nonzero. Thus, by (2.6) and Corollary 8, we have
for some constant \(C > 0\) independent from N. Therefore, from (5.12) we get that
\(\square \)
Proof of (2) from Proposition 17
Let Y be a random N-by-N signature matrix independent from W. Similar to the previous case, \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*} H^{} W / \sqrt{N}\), we can assume \(\textrm{p}_{\sigma ^{-1} \circ \pi }\) is the zero polynomial and it suffices to show that
Let \(\pi _{\text {odd},1}\) and \(\pi _{\text {odd},2}\) denote the restrictions of \(\pi _{\text {odd}}\) to \([\pm 2m_1]\) and \([\pm 2\,m ] {\setminus } [\pm 2m_1]\), respectively. Note that if \(\pi _{\text {odd}}\) is not an even partition, then either \(\pi _{\text {odd},1}\) or \(\pi _{\text {odd},2}\) is not even, and hence, we obtain \({\mathfrak {C}}_{2}[\pi ]=0\) since (2.5) would imply \( {\mathbb {E}} \left[ {{\textbf{y}}_1({\textbf{i}})}\right] {\mathbb {E}} \left[ {{\textbf{y}}_2({\textbf{i}})}\right] = {\mathbb {E}} \left[ {{\textbf{y}}({\textbf{i}})}\right] =0 \) for every function \({\textbf{i}}:[\pm {2m} ] \rightarrow [N]\) satisfying \( \textrm{ker} \left( {{\textbf{i}}} \right) =\pi \). Thus, we can further assume \(\pi _{\text {odd}}\) is even. It then follows from (2.5) and (2.6) that
for \({\textbf{i}}:[\pm {2m} ] \rightarrow [N]\) satisfying \( \textrm{ker} \left( {{\textbf{i}}} \right) =\pi \), and hence, we obtain
By Proposition 10, there is a symmetric pairing partition \({{\hat{\theta }}} \le \pi \) such that \(\textrm{p}_{\sigma ^{-1} \circ {{\hat{\theta }}}}\) is also the zero polynomial, and thus, the partition \({\hat{\theta }}\) must satisfy one of the conditions (1)-(6) from Proposition 13. However, if \({\hat{\theta }}\) satisfies either (3), (4), (5), or (6), then
Indeed, suppose \({\hat{\theta }}\) satisfies either (3), (4), (5), or (6) from Proposition 13, let \({\hat{\theta }}_1\) and \({\hat{\theta }}_2\) denote the restrictions of \({\hat{\theta }}\) to \([\pm 2m_1]\) and \([\pm 2\,m ] {\setminus } [\pm 2m_1]\), respectively, and let \({\textbf{i}}:[\pm {2\,m} ] \rightarrow [N]\) be a function satisfying \( \textrm{ker} \left( {{\textbf{i}}} \right) =\pi _{1} \sqcup \pi _{2}\). Note that \({\hat{\theta }} = {\hat{\theta }}_1 \sqcup {\hat{\theta }}_2 \le \pi _{1} \sqcup \pi _{2}\) since \({\hat{\theta }} \le \pi \) implies \({\hat{\theta }}_{1} \le \pi _{1}\) and \({\hat{\theta }}_{2} \le \pi _{2}\), and thus, by Proposition 10, the polynomial \(\textrm{p}_{\sigma ^{-1} \circ \pi _{1} \sqcup \pi _{2}}\) is zero, and hence, we get
Moreover, \(\pi _{1}\) and \(\pi _{2}\) are even partitions since \({\hat{\theta }}\) is even and \({\hat{\theta }} = {\hat{\theta }}_1 \sqcup {\hat{\theta }}_2 \le \pi \), so, from (2.6), we get
The partitions \(\pi _{\text {odd},1}\) and \(\pi _{\text {odd},2}\) are also even since \({\hat{\theta }}_{\text {odd}}\) is even and \({\hat{\theta }} = {\hat{\theta }}_1 \sqcup {\hat{\theta }}_2 \le \pi \) implies \({\hat{\theta }}_{\text {odd}} = {\hat{\theta }}_{\text {odd},1} \sqcup {\hat{\theta }}_{\text {odd},2}\), \({\hat{\theta }}_{\text {odd},1} \le \pi _{\text {odd},1}\), and \({\hat{\theta }}_{\text {odd},2} \le \pi _{\text {odd},2}\) where \({\hat{\theta }}_{\text {odd},1}\) and \({\hat{\theta }}_{\text {odd},2}\) denote the restrictions of \({\hat{\theta }}_{\text {odd}}\) to \([\pm 2m_1]\) and \([\pm 2\,m ] {\setminus } [\pm 2m_1]\), respectively. Thus, from (2.5), we have
Consequently, we obtain (5.16) from (5.15). Now, similar to the case \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*} H^{} W / \sqrt{N}\), if \({\hat{\theta }}\) satisfies either (1) or (2) from Proposition 13, then \(\textrm{p}_{\sigma ^{-1} \circ \pi _1 \sqcup \pi _2}\) is a nonzero polynomial and (5.14) holds, so, from (5.15), we obtain
since we have \(\left| { {\mathbb {E}} \left[ {{\textbf{y}}_1({\textbf{i}})}\right] {\mathbb {E}} \left[ {{\textbf{y}}_2({\textbf{i}})}\right] = 1 } \right| \le 1\) for any function \({\textbf{i}}:[\pm {2m} ] \rightarrow [N]\).
It only remains to show that the undirected graph \({\mathcal {G}}_{\pi }\) must have only double loops as connected components if \({\hat{\theta }}\) satisfies (2) from Proposition 13. So, suppose \({\hat{\theta }}\) satisfies (2) from Proposition 13. Note that if \(\pi \) has a block of the form \(\{k,l\}\), then \(k+l\) is odd, and hence, we must have either \(\{k\}\) or \(\{l\}\) is a block of \(\pi _{\text {odd}}\), contradicting the assumption that \(\pi _{\text {odd}}\) is an even partition. Thus, \(\pi \) has only blocks of the form \(\{k,l,-k,-l\}\), or, equivalently, the undirected graph \({\mathcal {G}}_{\pi }\) has only double loops as connected components. \(\square \)
5.2 Case \(\varvec{ U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} =\frac{1}{N} W^{*} H^{*} X H^{} W}\)
For each function \({\textbf{i}}:[\pm {4m}] \rightarrow [N]\), we let \(\widehat{{\textbf{h}}}_{}({\textbf{i}})\), \(\widehat{{\textbf{g}}}_{}({\textbf{i}})\), \(\widehat{{\textbf{x}}}_{1}({\textbf{i}})\), and \(\widehat{{\textbf{x}}}_{2}({\textbf{i}})\) be given by
additionally, if we are given a function \({\textbf{j}}:[\pm {2\,m}] \rightarrow [N]\), we take
and let \(\widehat{{\textbf{w}}}_{1}(\textbf{i,t})\) and \(\widehat{{\textbf{w}}}_{2}(\textbf{i,t})\), also denoted \(\widehat{{\textbf{w}}}_{1}({\textbf{i}})\) and \(\widehat{{\textbf{w}}}_{2}({\textbf{i}})\), respectively, be defined by
Now, given partitions \(\pi \in P(\pm 2\,m)\) and \({\alpha } \in P_{2}(2\,m)\) and a function \({\textbf{j}}:[\pm {2m}] \rightarrow [N]\) satisfying \( \textrm{ker} \left( {{\textbf{j}}} \right) = \pi \), we define \({\mathfrak {C}}_{2} \left[ \pi , {\alpha } \right] \) by
where \(\pi ^{\text {odd}}_{1}\) and \(\pi ^{\text {odd}}_{2}\) denote the restrictions of \(\pi ^{\text {odd}}\) to the sets \([\pm 4m_{1}]\) and \([\pm (4m_{1}+4m_{2}) ] \setminus [\pm 4m_{1}]\), respectively, \({{\widehat{\alpha }}}\) is the partition given by \({{\widehat{\alpha }}}=\{\{-2k,2k,-2l,2l\} \mid \{k,l\} \in \alpha \}\), and \({\widehat{\sigma }} \in \textrm{Sym}(\pm 4m)\) is the permutation with cycle decomposition
Proposition 20
Let \(\pi \) be an even partition in \(P(\pm {2m})\). Suppose \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = W^{*} H^{*}X H^{} W / N\). If \({\mathfrak {c}}_{2} \left[ \pi \right] \) is given by (5.2) and \({\mathfrak {C}}_{2} \left[ \pi , {\alpha } \right] \) is given by (5.18) for every pairing partition \({\alpha } \in P_{2}(2m)\), then
Proof
Fix a function \({\textbf{j}}:[\pm {2m}] \rightarrow [N]\) satisfying \( \textrm{ker} \left( {{\textbf{j}}} \right) = \pi \) and let \({\textbf{t}}\) be as in (5.17). The \((j_{-k},j_{k})\)-entry of \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}}\) is then given by the sum
and hence, by Equation (5.2) and the linearity of the covariance, we get
where \(\widehat{{\textbf{g}}}({\textbf{i}})\), \(\widehat{{\textbf{w}}}_{1}\mathbf {(i,t)}\), \(\widehat{{\textbf{w}}}_{2}\mathbf {(i,t)}\), \(\widehat{{\textbf{x}}}_{1}\mathbf {(i)}\), and \(\widehat{{\textbf{x}}}_{2}\mathbf {(i)}\) are defined as above and \({{\widetilde{\sigma }}} \in \textrm{Sym}(\pm 4m)\) is the permutation with cycle decomposition
Note that for every function \({\textbf{i}}:[\pm {4m}]\rightarrow [N]\) we have
for \(k=1,2\), so we get
Now, suppose \(\theta = \textrm{ker} \left( {{\textbf{i}}} \right) \) for a function \({\textbf{i}}:[\pm {4\,m}]\rightarrow [N]\). Since \(\pi ^{\text {odd}} = \textrm{ker} \left( {{\textbf{t}}} \right) \), from (2.6) we have that
provided \({\theta }_{\text {odd}} \ne \pi ^{\text {odd}}\) and \({\theta }_{\text {odd}} \not \ge (\pi _{1} \sqcup \pi _{2})^{\text {odd}} = \pi _{1} ^{\text {odd}} \sqcup \pi _{2}^{\text {odd}} \), respectively; moreover, (2.5) implies that
if \({\theta }_{\text {even}}\) is not an even partition, \({\theta }_{\text {even}}\) has a block of the form \(\{ 2k, -2k\}\), or \(2k \not \sim _{{\theta }} -2k\) for some \(k \in [2m]\). Thus, we obtain
where \({\widetilde{P}}_{\beta }(\pm 4m)\) denotes the set of all partitions \({\theta } \in P(\pm 4\,m)\) such that \({\theta }_{\text {odd}} \ge \beta ^{\text {odd}}\) and for every integer \(k \in [2m]\) there exists \(l \in [2\,m]{\setminus }\{k\}\) such that \(2k \sim _{{\theta }} -2k \sim _{{\theta }} -2\,l \sim _{{\theta }} 2\,l\).
Now, letting \({\widehat{P}}_{\beta }(\pm 4m)\) denote the set of partitions \({\theta } \in {\widetilde{P}}_{\beta }(\pm 4m)\) so that \({\theta } = {\theta }_{\text {even}} \sqcup {\theta }_{\text {odd}}\), \({\theta }_{\text {odd}} = \beta ^{\text {odd}}\), and every block of \({\theta }_{\text {even}}\) is of the form \(\{2k,-2k,2l,-2l\}\) with \(k,l \in [2\,m]\) and \(k\ne l\), note the mapping
with \(\widehat{{\alpha }} = \left\{ \{2k,-2k,2\,l,-2\,l\} \mid \{k,l\} \in {\alpha } \right\} \) gives a bijection between the set of pairing partitions \(P_{2}(2m)\) and the set \({\widehat{P}}_{\beta }(\pm 4m)\) for any partition \(\beta \in P(\pm 2m)\). Thus, to get (5.19), it only remains to show that
Suppose \({\theta } \in {\widetilde{P}}_{\pi _{1} \sqcup \pi _{2}}( \pm 4\,m )\). Then, since \({\theta }_{\text {odd}} \ge (\pi _{1} \sqcup \pi _{2})^{\text {odd}} = \pi _{1}^{\text {odd}} \sqcup \pi _{2}^{\text {odd}}\) and each block of \({\theta }_{\text {even}}\) has at least 4 elements, we get the inequality
with equality only if \({\theta } = {\theta }_{\text {even}} \sqcup {\theta }_{\text {odd}}\), \({\theta }_{\text {odd}} = \pi _{1}^{\text {odd}} \sqcup \pi _{2}^{\text {odd}}\), and each block of \({\theta }_{\text {even}}\) has exactly 4 elements, i.e., \({\theta } \in {\widehat{P}}_{\pi _{1} \sqcup \pi _{2} }( \pm 4\,m )\); moreover, (2.5) and (2.6) imply that
Hence, if \({\theta } \in {\widetilde{P}}_{\pi _{1} \sqcup \pi _{2}}( \pm 4\,m ) {\setminus } {\widehat{P}}_{\pi _{1} \sqcup \pi _{2} }( \pm 4\,m )\), we have
Similar arguments show that \( \#({\theta }) \le m + \#(\pi _{})\) for every partition \({\theta } \in {\widetilde{P}}_{\pi _{}}( \pm 4m )\) with equality only if \({\theta } \in {\widehat{P}}_{\pi }( \pm 4m )\), and hence, we get
for any \({\theta } \in {\widetilde{P}}_{\pi _{}}( \pm 4\,m ) {\setminus } {\widehat{P}}_{\pi }( \pm 4\,m )\). \(\square \)
Proposition 21
Suppose \(\pi \in P_{\text {}}(\pm 2\,m )\) and \({\alpha } \in P_{2}(2\,m)\) and let \({\alpha }_{1}\) and \({\alpha }_{2}\) denote the restrictions of \({\alpha }\) to the sets \([2m_{1}]\) and \([ 2m_{1} + 2m_{2} ] {\setminus } [2m_{1}]\), respectively. If \({\mathfrak {C}}_{2}[\pi ,{\alpha }] \) is given by (5.18), then
Proof
Note that if the polynomial \(\textrm{p}_{{{\widehat{\sigma }}}^{-1} \circ ({\widehat{\alpha }} \sqcup \pi ^{\text {odd}})}\) is nonzero, then \({\mathfrak {C}}_{2}[\pi ,{\alpha }] = O(N^{-1/2})\). Indeed, if \(\textrm{p}_{{{\widehat{\sigma }}}^{-1} \circ ({\widehat{\alpha }} \sqcup \pi ^{\text {odd}})}\) is a nonzero polynomial, so is \(\textrm{p}_{{{\widehat{\sigma }}}^{-1} \circ ({\widehat{\alpha }} \sqcup \pi _{1}^{\text {odd}} \sqcup \pi _{2}^{\text {odd}} ) }\) by Proposition 10, and thus, Corollary 8 implies there is a constant C independent from N such that
for \(\beta = \pi \) and \(\beta =\pi _{1} \sqcup \pi _{2}\). But then, we get that \({\mathfrak {C}}_{2}[\pi ,{\alpha }] = O(N^{-1/2})\) since from (2.5), (2.6), and (5.18) we have
Assume \(\textrm{p}_{{{\widehat{\sigma }}}^{-1} \circ ({\widehat{\alpha }} \sqcup \pi ^{\text {odd}})}\) is the zero polynomial. Then, by Proposition 10, there is a symmetric pairing partition \(\eta \le {\widehat{\alpha }} \sqcup \pi ^{\text {odd}}\) such that \(\textrm{p}_{{{\widehat{\sigma }}}^{-1} \circ \eta }\) is also the zero polynomial, and hence, the partition \(\eta \) must satisfy one of the conditions (1)-(6) from Proposition 13. However, we have \(\eta =\eta _{\text {odd}} \sqcup \eta _{\text {even}}\), since \(\eta \le {\widehat{\alpha }} \sqcup \pi ^{\text {odd}}\), and neither \(2m_1\) or \(2m_2\) is odd, so conditions (2) and (4)-(6) cannot hold. Now, note that if \(\textrm{p}_{{{\widehat{\sigma }}}^{-1} \circ ({\widehat{\alpha }} \sqcup \beta ^{\text {odd}})}\) is zero polynomial for some partition \(\beta \in P(\pm 2m)\), then
since we would have \(\widehat{{\textbf{h}}}({\textbf{i}} \circ \varvec{{\widehat{\sigma }}} ) =1\) for any function \( {\textbf{i}}:[\pm {4\,m} ] \rightarrow [N]\) satisfying \( \textrm{ker} \left( {{\textbf{i}}} \right) = {\widehat{\alpha }} \sqcup \beta ^{\text {odd}}\). Hence, if \({\alpha }_{1}\), \({\alpha }_{2}\), \(\pi _{1}\), and \(\pi _{2} \) are all even partitions and the polynomial \(\textrm{p}_{\sigma ^{-1} \circ {\hat{\alpha }} \sqcup \pi ^{\text {odd}}_{1} \sqcup \pi ^{\text {odd}}_{2} }\) is zero, from (2.5), (2.6), and (5.18), we obtain
On the other hand, if either \({\alpha }_{1}\) or \({\alpha }_{2}\) is not an even partition, from (2.5) and (5.18), we get
Suppose \({\eta }\) satisfies (3) from Proposition 13 and let \(1\le k \le 4m_{1}\) and \(4m_{1}+1 \le l \le 4m_{1}+4m_{2}\) such that \( \eta = \left\{ \{{{\widehat{\sigma }}}^{t_{1}}(-k),{{\widehat{\sigma }}}^{-t_{1}}(k)\}, \{{{\widehat{\sigma }}}^{t_{2}}(-l),{{\widehat{\sigma }}}^{-t_{2}}(l)\} \mid t_{2}, t_{2} \ge 0 \right\} . \) We need to consider three cases: k and l are both odd, \(k+l\) is odd, and k and l are both even. First, if k and l are both odd, then \(\textrm{p}_{\sigma ^{-1} \circ {\hat{\alpha }} \sqcup \pi ^{\text {odd}}_{1} \sqcup \pi ^{\text {odd}}_{2} }\) is also the zero polynomial, \(\pi _{1}\) and \(\pi _{2} \) are both even partitions, and \({\alpha } = {\alpha }_{1} \sqcup {\alpha }_{2}\), so (5.21) holds. Second, if \(k+l\) is odd, then \({\alpha } = {\alpha }_{1} \sqcup {\alpha }_{2}\) and \(\pi = \pi _{1} \sqcup \pi _{2} \), but then (5.21) holds too. Third, if k and l are both even, then \(\pi = \pi _{1} \sqcup \pi _{2} \) and either \({\alpha } = {\alpha }_{1} \sqcup {\alpha }_{2}\) or \({\alpha } \ne {\alpha }_{1} \sqcup {\alpha }_{2}\). However, if \({\alpha } = {\alpha }_{1} \sqcup {\alpha }_{2}\), we already know that \({\mathfrak {C}}_{2}[\pi ,{\alpha }]= O(N^{-1})\) from (5.21), and if \({\alpha } \ne {\alpha }_{1} \sqcup {\alpha }_{2}\), then \({\alpha }_{1}\) and \({\alpha }_{2}\) are not even partitions, so (5.22) holds. Finally, if \({\eta }\) satisfies (1) from Proposition 13, we must have \({\alpha } \ne {\alpha }_{1}\sqcup {\alpha }_{2}\), so we obtain \({\mathfrak {C}}_{2}[\pi ,{\alpha }] = 1 + O\left( N^{-1}\right) \). \(\square \)
Proof of (3) from Proposition 17
Fix an even partition \(\pi \in P(\pm 2m)\) such that \(\pi \le \theta \) for some partition \(\theta \in P_{\chi \chi }(\pm 2\,m)\) and let \({\mathfrak {C}}_{2}[\pi ,\alpha ] \) be given by (5.18) for each pairing partition \(\alpha \in P_{2}(2m)\). By Proposition 21, we have that
where \(E_{\pi }\) and \(F_{\pi }\) are the subsets of \(P_{2}(2m)\) given by
and
Thus, by Proposition 20, we only need to show that \(E_{\pi } \ne \emptyset \) implies \(\left| {E_{\pi }} \right| =1\), \(F_{\pi } \ne \emptyset \) implies \(\left| {F_{\pi }} \right| = 2\), and \(E_{\pi } \cap F_{\pi }\) is empty.
Let \(\alpha \) and \(\beta \) be pairing partitions in \(P_{2}(2m)\) and suppose there are symmetric pairings \(\eta _{\alpha }, \eta _{\beta } \in P(\pm {4\,m})\) satisfying (1) from Proposition 13, \(\eta _{\alpha } \le {\widehat{\alpha }} \sqcup \pi ^{\text {odd}}\), and \(\eta _{\beta } \le {\widehat{\beta }} \sqcup \pi ^{\text {odd}}\). Then, there are integers \( 2m_{1} + 1 \le l_{\alpha }, l_{\beta } \le 2m_{1} + 2m_{2}\) so that
where \({\widehat{\sigma }}\) is the permutation given by
But then, we must have
since \(\eta _{\alpha } \le {\widehat{\alpha }} \sqcup \pi ^{\text {odd}}\) and \(\eta _{\beta } \le {\widehat{\beta }} \sqcup \pi ^{\text {odd}}\), and thus, we get that
where \({\sigma }\) is the permutation given by
In particular, for \(t=0\), we obtain \(l_{\alpha } \sim _{ \pi } -1 \sim _{ \pi } l_{\beta }\), and thus, we have \(l_{\alpha }=l_{\beta }\) since \(\pi \) is an even partition with only blocks of the form \(\{-k,+k,-l,l\}\) and \(\{+k,-l\}\). Therefore, it follows from (5.23) that \({\widehat{\alpha }}={\widehat{\beta }}\), or, equivalently, \({\alpha }={\beta }\). This shows that \(E_{\pi } \ne \emptyset \) implies \(\left| {E_{\pi }} \right| =1\).
Suppose now there are symmetric pairings \(\eta _{\alpha }, \eta _{\beta } \in P(\pm {4\,m})\) satisfying (3) from Proposition 13 with k and l even, \(\eta _{\alpha } \le {\widehat{\alpha }} \sqcup \pi ^{\text {odd}}\), and \(\eta _{\beta } \le {\widehat{\beta }} \sqcup \pi ^{\text {odd}}\). Then, there exist integers \( 1 \le k_{\alpha } \le k_{\beta } \le 2m_{1}\) so that
and hence, we get
since \(\eta _{\alpha } \le {\widehat{\alpha }} \sqcup \pi ^{\text {odd}}\) and \(\eta _{\beta } \le {\widehat{\beta }} \sqcup \pi ^{\text {odd}}\); in particular, we must have
Now, since \({\alpha }\) and \({\beta }\) are pairing partitions of \([2m_{1}+2m_{2}]\), \({\widehat{\alpha }} = \{\{+2k,-2k,+2\,l,-2\,l\} \mid \{k,l\} \in \alpha \} \), and \({\widehat{\beta }} = \{\{+2k,-2k,+2\,l,-2\,l\} \mid \{k,l\} \in \beta \} \), we get
where \({\sigma }\) is the permutation defined above; hence, we obtain
and
where \(\alpha _{1}\) and \(\beta _{1}\) denote the restrictions of \(\alpha \) and \(\beta \), respectively, to the set \([\pm 2m_{1}]\). Let us show that \(\alpha _{1}=\beta _{1}\). From (5.24), we also have that
for every integer \(t \ge 0\), and thus, since \(\pi ^{\text {odd}} = \{\{ 2k-\textrm{sign}{(k)} \mid k \in B \} \mid B \in \pi \}\}\), we obtain
Let \(t=k_{\beta }-k_{\alpha }\) and note that
since
moreover, since \({\sigma }^{2t}(k_{\alpha } ) > 0\), \({\sigma }^{-2t+1}( k_{\alpha } ), {\sigma }^{2t+1}( k_{\alpha } ) < 0\), and \(\pi \) is a partition with only blocks of the form \(\{-k,+k,-l,l\}\) and \(\{+k,-l\}\) with \(k,l > 0\), we must have
or, equivalently,
But the equality \({\sigma }^{s}(k_{\alpha }) = k_{\alpha }\) holds if only if \(s \equiv 0 \mod 4m_{1}\), so only \({\sigma }^{-4t}( k_{\alpha } ) = k_{\alpha }\) can hold, and thus, we get \(k_{\alpha } = k_{\beta }\) or \(k_{\beta } = k_{\alpha } + m_{1}\) since \(0 \le t = k_{\beta } - k_{\alpha } \le 2m_{1}-1\). Therefore, \(\alpha _{1} = \beta _{1}\) and there is an integer \(1\le k=k_{\alpha } \le 2m_{1}\) so that
Similarly, letting \(\alpha _{2}\) and \(\beta _{2}\) denote the restrictions of \(\alpha \) and \(\beta \), respectively, to the set \([\pm (2m_{1}+2m_{2})] {\setminus } [\pm 2m_{1}]\), we have \(\alpha _{2} = \beta _{2}\) and there is an integer \(2m_{1}+1 \le l_{} \le 2m_{1}+2m_{2}\) so that
This shows that \(\left| {F_{\pi }} \right| = 2\) provided \(F_{\pi } \ne \emptyset \) since \(\gamma \in F_{\pi }\) implies
where \({\widetilde{\alpha }} =\{\{ \sigma ^{2t}(k),\sigma ^{-2t}(k) \} \mid 1 \le t \le m_{1}-1 \} \cup \{\{ \sigma ^{2t}(l),\sigma ^{-2t}(l) \} \mid 1 \le t \le m_{2}-1 \} \).
Finally, \(E_{\pi } \cap F_{\pi }\) is empty since \(E_{\pi } \ne \emptyset \) implies \(\pi \ne \pi _{1} \sqcup \pi _{2}\), and, on the other hand, \( F_{\pi } \ne \emptyset \) implies \(\pi =\pi _{1} \sqcup \pi _{2}\). \(\square \)
6 Concluding Remarks
-
(1)
The exponent \(-1/2\) in the remainder terms \(O(N^{-1/2})\) essentially comes from the \(-1/2\) in Proposition 7 and can be upgraded to \(-1\) as follows. One first shows that for all partitions \(\pi = \{B_1, \ldots , B_r\}\) appearing in (5.3) and having at least one through block—i.e., a block intersecting both \([\pm 2m_1]\) and \([\pm 2\,m ] {\setminus } [\pm 2m_1]\)- the polynomial \(\textrm{p}_{\sigma ^{-1} \circ \pi } (\textrm{x}_1,\ldots , \textrm{x}_r)= \sum _{1 \le t \le s \le r} a_{t,s} \textrm{x}_{t} \textrm{x}_{s}\) satisfies exactly one of the following:
-
(a)
\(\textrm{p}_{\sigma ^{-1} \circ \pi }\) is the zero polynomial, or
-
(b)
there exists \(t \in [r]\) so that \(a_{t,t}=0\) and \(a_{t,s} \ne 0\) or \(a_{s,t} \ne 0\) for some \(s \in [r]\).
For polynomials \(\textrm{p}_{\sigma ^{-1} \circ \pi }\) satisfying (b) above, the last part of Proposition 7’s proof shows that
$$\begin{aligned} \left| { \sum _{j_1,j_2,\ldots ,j_r=0}^{N-1} e^{-\frac{2 \pi \sqrt{-1}}{N} \textrm{p}_{\sigma ^{-1} \circ \pi }(j_1,j_2,\ldots ,j_r) } } \right| \le C_{\textrm{p}_{\sigma ^{-1} \circ \pi }} N^{r-1} \end{aligned}$$(6.1)for some constant \(C_{\textrm{p}_{\sigma ^{-1} \circ \pi }}\) independent of N. Then, carefully carrying the \(-1\) from (6.1) through the computations of \({\mathfrak {C}}_{2}[\pi ]\) and \({\mathfrak {C}}_{2}[\pi ,{\alpha }] \), one can replace \(-1/2\) by \(-1\) in the remainder terms \(O(N^{-1/2})\), first in Proposition 17 and Lemma 18, and then in Theorems 1 and 2.
-
(a)
-
(2)
The random matrix ensemble \(\{W_{N,1},H_{N}W_{N,2}\}_{N=1}^{\infty }\) satisfies the hypothesis in Lemma 3, and hence, Theorem 2 is proved once we show (1.14) holds. To that end, we first define appropriate versions of the functions \({\textbf{w}}_{}(\textbf{i,j})\), \({\textbf{w}}_{1}(\textbf{i,j})\), \({\textbf{w}}_{2}(\textbf{i,j})\) and show that (5.10) still holds in this case. Then, following similar steps to those in the proof of Proposition 17 and Lemma 18 and letting \(U^{*}_{N,{i}_{1}} U^{}_{N,{i}_{2}} = \frac{1}{\sqrt{N}} W_{N,1}^{*} H^{}_{N} W_{N,2}\), we conclude
$$\begin{aligned}&\sum _{\begin{array}{c} \pi \in P_{\text {even}}(\pm {2m}) \\ \pi \le \theta \end{array}} N^{m} {\mathfrak {c}}_{2} \left[ \pi \right] \mu (\pi , \theta ) \\&\quad = \left\{ \begin{array}{cl} 1 + O\left( N^{-1/2} \right) &{} \text {if } \theta \text { is a pairing partition satisfying (1)} \\ &{} \text {from Proposition 13}, \\ O\left( N^{-1/2}\right) &{} \text {otherwise.} \end{array}\right. \end{aligned}$$ -
(3)
One can replace the discrete Fourier transform \(H_{N}\) in the unitary random matrix ensemble \(\{W_{N}, H_{N}W_{N} /\sqrt{N}, X_{N}H_{N}W_{N}/\sqrt{N} \}_{N=1}^{\infty }\) by any Hadamard matrix \(H'_{N}\) and still get an asymptotically liberating ensemble, see [1]. Moreover, key equations in this paper involving \(H_{N}\) still hold when we replace \(H_{N}\) by a general Hadamard matrix \(H'_{N}\), for instance, (3.8), (3.10), and (3.12). Thus, to determine the corresponding induced fluctuations moments, one needs to compute graph sums of \(H'_{N}\) and obtain similar results to those from Sect. 3.2. However, the results for graph sums of \(H_{N}\) were possible thanks to the reciprocity theorem for generalized Gauss sums and it is not immediate what tools could be used for a general \(H'_{N}\).
-
(4)
Although Proposition 15 and Corollary 16 give equivalent conditions only for point-wise uniform boundedness, similar statements and proofs provide us with corresponding conditions for the point-wise convergence of a sequence of multi-linear functionals. These conditions together with bounds for graph sums can be exploited to study higher-order moments. In particular, the relations (4.4) and (5.3) can be used to determine the higher-order moments induced by Haar-unitary and Haar-orthogonal via the Weingarten Calculus from [4] and [5].
Data Availability
Data sharing is not applicable to this article as no datasets were generated or analyzed during the current study.
References
Anderson, G.W., Farrell, B.: Asymptotically liberating sequences of random unitary matrices. Adv. Math. 255, 381–413 (2014)
Anderson, G.W., Guionnet, A., Zeitouni, O.: An Introduction to Random Matrices. Cambridge University Press, Cambridge (2010)
Berndt, B.C., Evans, R.J., Williams, K.S.: Gauss and Jacobi Sums. Wiley, New York (1998)
Collins, B.: Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability. Int. Math. Res. Not. 8, 953–982 (2003)
Collins, B., Śniady, P.: Integration with respect to the Haar measure on unitary, orthogonal and symplectic group. Commun. Math. Phys. 264, 773–795 (2006)
Edelman, A., Rao, N.R.: Random matrix theory. Acta Numer. 14, 233–297 (2005)
Gabriel, F.: Combinatorial theory of permutation-invariant random matrices I: Partitions, geometry and renormalization, (2015). Prepint at arXiv:1503.02792
Hao, Z., Popa, M.: A combinatorial result on asymptotic independence relations for random matrices with non-commutative entries. J. Oper. Theory 80, 47–76 (2018)
Jiao, Y., Popa, M.: On fluctuations of traces of large matrices over a non-commutative algebra. J. Oper. Theory 73, 71–90 (2015)
Keating, J.: The Riemann zeta-function and quantum chaology. In: Casati, G., Guarneri, I., Smilansky, U. (eds.) Quantum Chaos, pp. 145–185. North-Holland Publishing Co., Amsterdam (1993)
Male, C.: Traffic distributions and independence: permutation invariant random matrices and the three notions of independence. Mem. Am. Math. Soc. 267, 850 (2020)
Male, C., Mingo, J.A., Péché, S., Speicher, R.: Joint global fluctuations of complex wigner and deterministic matrices. Random Matrices Theory Appl. 11, 2250015 (2022)
Mingo, J.A., Popa, M.: Real second order freeness and Haar orthogonal matrices. J. Math. Phys. 54, 051701 (2013)
Mingo, J.A., Popa, M.: Freeness and the transposes of unitarily invariant random matrices. J. Funct. Anal. 271, 883–921 (2016)
Mingo, J.A., Śniady, P., Speicher, R.: Second order freeness and fluctuations of random matrices. II. Unitary random matrices. Adv. Math. 209, 212–240 (2007)
Mingo, J.A., Speicher, R.: Second order freeness and fluctuations of random matrices. I. Gaussian and Wishart matrices and cyclic Fock spaces. J. Funct. Anal. 235, 226–270 (2006)
Mingo, J.A., Speicher, R.: Sharp bounds for sums associated to graphs of matrices. J. Funct. Anal. 262, 2272–2288 (2012)
Mingo, J.A., Speicher, R.: Free Probability and Random Matrices. Springer, New York (2017)
Muraki, N.: The five independences as natural products. Infin. Dimens. Anal. Quantum Probab. Relat. Top. 6, 337–371 (2003)
Nica, A., Speicher, R.: Lectures on the Combinatorics of Free Probability. Cambridge University Press, Cambridge (2006)
Redelmeier, C.E.I.: Real second-order freeness and the asymptotic real second-order freeness of several real matrix models. Int. Math. Res. Not. IMRN 3353–3395, 2012 (2014)
Redelmeier, C.E.I.: Quaternionic second-order freeness and the fluctuations of large symplectically invariant random matrices. Random Matrices Theory Appl. 10, 2150017 (2021)
Speicher, R.: On universal products. In: Voiculescu, D.-V. (ed.) Free probability theory, pp. 257–266. Amer. Math. Soc, Providence, RI (1997)
Tulino, A.M., Verdú, S.: Random matrix theory and wireless communications. Commun. Inf. Theory 1, 1–182 (2004)
Voiculescu, D.: Symmetries of some reduced free product \(C^\ast \)-algebras. In H. Araki, C. C. Moore, Ş. V. Stratila, and D. V. Voiculescu, editors, Operator Algebras and their Connections with Topology and Ergodic Theory, vol. 1132, pp. 556–588 (1985). Springer Berlin
Voiculescu, D.: Limit laws for random matrices and free products. Invent. Math. 104, 201–220 (1991)
Voiculescu, D.V., Dykema, K.J., Nica, A.: Free Random Variables. American Mathematical Society, Providence (1992)
Wigner, E.P.: Characteristic vectors of bordered matrices with infinite dimensions. Ann. Math. 2(62), 548–564 (1955)
Wishart, J.: The generalised product moment distribution in samples from a normal multivariate population. Biometrika 20A(1/2), 32–52 (1928)
Acknowledgements
The author would like to thank James A. Mingo for invaluable discussions during the preparatiion of this paper. The author also thanks the anonymous referees for their insightful suggestions and comments, all of which improved the presentation of this material. Research was partially supported by The Mexican National Council of Science and Technology (CONACYT) ref. 579659/410386.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
Research was partially supported by The Mexican National Council of Science and Technology (CONACYT) ref. 579659/410386.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Vazquez-Becerra, J. Fluctuation Moments Induced by Conjugation with Asymptotically Liberating Random Matrix Ensembles. J Theor Probab 36, 1972–2039 (2023). https://doi.org/10.1007/s10959-023-01246-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10959-023-01246-9