Abstract
The celebrated elliptic law describes the distribution of eigenvalues of random matrices with correlations between off-diagonal pairs of elements, having applications to a wide range of physical and biological systems. Here, we investigate the generalization of this law to random matrices exhibiting higher-order cyclic correlations between k tuples of matrix entries. We show that the eigenvalue spectrum in this ensemble is bounded by a hypotrochoid curve with k-fold rotational symmetry. This hypotrochoid law applies to full matrices as well as sparse ones, and thereby holds with remarkable universality. We further extend our analysis to matrices and graphs with competing cycle motifs, which are described more generally by polytrochoid spectral boundaries.
| Original language | English |
|---|---|
| Article number | 010302 |
| Pages (from-to) | 1-5 |
| Number of pages | 5 |
| Journal | Physical Review E |
| Volume | 100 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 16 Jul 2019 |
Funding
Aceituno Pau Vilimelis * Max Planck Institute for Mathematics in the Sciences , 04103 Leipzig, Germany Rogers Tim † Centre for Networks and Collective Behaviour, Department of Mathematical Sciences, University of Bath , Bath BA27AY, United Kingdom Schomerus Henning ‡ Department of Physics, Lancaster University , Lancaster LA1 4YB, United Kingdom * [email protected] † [email protected] ‡ [email protected] 16 July 2019 July 2019 100 1 010302 21 December 2018 11 February 2019 ©2019 American Physical Society 2019 American Physical Society The celebrated elliptic law describes the distribution of eigenvalues of random matrices with correlations between off-diagonal pairs of elements, having applications to a wide range of physical and biological systems. Here, we investigate the generalization of this law to random matrices exhibiting higher-order cyclic correlations between k tuples of matrix entries. We show that the eigenvalue spectrum in this ensemble is bounded by a hypotrochoid curve with k -fold rotational symmetry. This hypotrochoid law applies to full matrices as well as sparse ones, and thereby holds with remarkable universality. We further extend our analysis to matrices and graphs with competing cycle motifs, which are described more generally by polytrochoid spectral boundaries. Royal Society 10.13039/501100000288 Engineering and Physical Sciences Research Council 10.13039/501100000266 EP/P010180/1 Determining the eigenvalue spectra of large random matrices is a rich theoretical problem [1] with many applications in fields as diverse as telecommunications [2] , quantum physics [3] , ecology [4,5] , and economics [6] . A key result in this field is the elliptic law [7] , which states that in the limit of large matrix size the eigenvalues for random matrices with correlations between symmetric pairs of entries are confined within an ellipse in the complex plane. This result originating from over 30 years ago still drives scientific developments today, in both mathematical theory [8–12] as well as applications [5,13] . As the applications of random matrix theory have diversified, so too have the ensembles under study. Existing generalizations of the elliptic law fall broadly into three categories. There is a large body of theoretical work concerning random matrix ensembles defined by potential functions, where the quadratic case recovers the elliptic law, but more complicated potentials produce interesting spectral distributions (see, e.g., [14,15] ). Alternatively, for some applications it is necessary to impose a system-level structure such as modularity (see, e.g., [16] ), often by addition or multiplication with another matrix (see [17,18] for methods and rigorous mathematical results). Lastly, growing interest in the study of complex networks has led many authors to consider sparse ensembles containing many zero matrix elements, where the location of the nonzero elements encodes the adjacency matrix of some directed graph (or digraph ), and can have striking eigenvalue distributions [19,20] (see [21] for a recent topical review). In none of these directions of work has the problem of high-order correlations been fully and directly addressed. This is not for lack of interest. Multiparty interactions in dense systems are important in biological applications such as ecology [22] , stabilization of microbial communities [23] , or gene-gene interactions [24] and can provide valuable engineering insights into machine learning [25,26] and control theory [27] . Moreover, most of the sparse random matrix literature hinges on the assumption of a treelike interaction structure; it remains a long-standing and important problem to allow the relaxation of this assumption, inducing higher-order correlations. Here, we investigate the generalization of the elliptic law to ensembles, both dense and sparse, featuring higher-order correlations. In the case that there is a single dominant correlation order k , we find that the spectrum is bounded by a hypotrochoid curve (i.e., the path of a point located on a small wheel that rolls inside a larger wheel) with k -fold rotational symmetry (see Fig. 1 for an illustration). Surprisingly, we thereby recover the spectral boundary of a highly structured system, a sparse regular digraph [19,20] , but in a much more general and universal context. Extending this result further to the case where more than one correlation order is present, we find a more general family of polytrochoid boundary curves described by multiple linked gears [28] . 10.1103/PhysRevE.100.010302.f1 1 FIG. 1. Hypotrochoid curves (black lines) bounding the eigenvalue spectra (blue dots) of random matrices with higher-order correlations. Left: a dense N × N random matrix M with Tr M 5 ¯ / N = 0.075 and other correlations negligible. Right: a random digraph in which each node appears in exactly two directed cycles of length three, with no other edges. In both cases N = 1000 . The large and small red circles respectively show the fixed and rotating wheels describing the hypotrochoid curve. Dense matrices . We study N × N -dimensional non-Hermitian matrices with real or complex entries independently drawn from a distribution with zero mean and bounded variance. For any of such matrix M , the density μ ( z ) of complex eigenvalues z can be obtained from a Green's function of the form [17,29,30] (1) G ( z , z * ) = z 1 − M i λ 1 i λ 1 z * 1 − M † − 1 ≡ G 11 G 12 G 21 G 22 , where z * denotes complex conjugation and M † the adjoint; for a real matrix this is just the transpose. Thereby (2) μ ( z ) = 1 π ∂ g 11 ∂ z * , g ( z , z * ) = lim λ → 0 + Tr G 11 Tr G 12 Tr G 21 Tr G 22 ≡ g 11 g 12 g 21 g 22 . For a random matrix M , the ensemble-averaged density μ ¯ ( z ) therefore follows from g ¯ ( z , z * ) . This can be used to derive the elliptic law of random matrices in the large N limit, which serves as useful preparation. Let us expand (3) G = Z − 1 ∑ ℓ = 0 ∞ ( M Z − 1 ) ℓ into a geometric series, where (4) Z = Z ⊗ 1 , Z = z i λ i λ z * , M = M 0 0 M † . When we perform the averaging, only certain products of matrix elements M n m survive. These can be organized into groups of terms whose number scales differently in the matrix dimension N . In particular, there will be many terms where we can pair M n m with ( M † ) m n to yield a finite average. If no further correlations are present the leading order is (5) where the lines denote a pair of matrices that are averaged. This factorization of the average is called the noncrossing or planar approximation. It enjoys a large degree of universality based on combinatorial arguments, going much beyond the case of Gaussian statistics where the indicated pairings represent Wick contractions, which are embodied in the framework of free probability [30] . The elliptic law is derived straightforwardly from the expression above. Carrying out the average of the M matrices, taking the partial trace on both sides, and rearranging for Z , one obtains (6) Z = N / g ¯ + τ 2 2 g ¯ 11 σ 2 g ¯ 12 σ 2 g ¯ 21 τ 2 2 g ¯ 22 . Comparing terms in the off-diagonal in this equation (and noting the constraints g ¯ 11 = g ¯ 22 * and g 12 = g 21 > 0 ), we find two possible solutions: (i) either g 12 = 0 , or (ii) | g ¯ 11 | 2 − g ¯ 12 2 = N / σ 2 . The first of these yields g ¯ 11 proportional to z and therefore holds only outside of the support of the spectrum. Examining the diagonal elements of (6) in the case (ii) we obtain (7) z = σ 2 g ¯ 11 * + τ 2 2 g ¯ 11 , which must be solved together with the constraint that | g ¯ 11 | 2 − N / σ 2 > 0 . The boundary of the spectrum is therefore found by determining the values of z for which | g ¯ 11 | 2 = N / σ 2 ; in the present case one finds an ellipse with foci ± 2 τ 2 N . Inside the support, one can solve (7) to determine g ¯ 11 and apply (2) to find that the spectral density μ ( z ) is uniform. To generalize these results to ensembles with high-order correlations where Tr M k ¯ / N is a fixed parameter, we reinterpret the Hermitian contributions of weight τ 2 in the elliptic law as correlations of order k = 2 . Introducing correlations of general order k , we pick up additional contributions corresponding to contractions (8) where k matrices are combined by the indicated lines. Our results will show that these contributions give rise to a notable departure from the universal elliptic law, and therefore constitute the relevant perturbations beyond established theory. We assume for now that there is just a single extra term of these, of fixed k and with weight τ k . This gives (9) Z = N / g ¯ + τ k k g ¯ 11 k − 1 σ 2 g ¯ 12 σ 2 g ¯ 21 τ k k g ¯ 22 k − 1 and results, inside the spectrum, in the equations (10) z = σ 2 g ¯ 11 * + τ k k g ¯ 11 k − 1 , g ¯ 12 2 = | g ¯ 11 | 2 − N / σ 2 . The boundary of the support is therefore determined by the condition | g ¯ 11 | 2 = N / σ 2 . In the large N limit we choose the scalings σ 2 = N − 1 , τ k k = ρ k N 1 − k to balance the contribution of terms in Eq. (10) . With the parametrization g ¯ 11 = N e i φ , which we insert into Eq. (10) , the boundary curve then becomes (11) z b ( φ ) = e − i φ + ρ k e i ( k − 1 ) φ . This equation is precisely the complex parametrization of a hypotrochoid curve in which the small and large wheels have radii in a ratio of 1 : ( k − 1 ) . In Fig. 2 we illustrate this result numerically for various values of k and ρ k ; see [31] for the matrix generation algorithm. 10.1103/PhysRevE.100.010302.f2 2 FIG. 2. Hypotrochoid curves (black lines) bounding the eigenvalue spectra (blue dots) of random matrices with correlations Tr M k ¯ = N ρ k . Note that (although hard to determine from Fig. 2 ), for k > 2 the density of eigenvalues inside the hypotrochoid support is in fact not uniform; in general, solutions to Eq. (10) do not have the property that ∂ g ¯ 11 / ∂ z * is constant. This distribution is, however, universal in the sense that it is determined entirely by the parameters σ 2 and ρ k , and other properties of the distribution of matrix elements are unimportant. We will now explore to what extent this universality extends to sparse matrices. Sparse digraphs . Square matrices can be seen as an alternative representation of weighted digraphs, where the entry M n m corresponds to the weight of the edge going from node n to node m . This implies that for large dense graphs with random weights we can obtain the eigenvalues of their adjacency matrix by the previous methods. However, it is well known that sparsity can change the eigenvalue distribution substantially [32–34] . Surprisingly, the hypotrochoidic law (11) also applies to highly structured sparse systems. Randomly generated digraphs in which each node belongs to exactly d directed cycles of length k were studied in [19,20] , where it was shown that the adjacency matrices of these graphs have hypotrochoidic spectra in the limit of large network size. This result extends further to disordered directed random graph ensembles. In the Supplemental Material [31] we apply effective medium approximation (EMA) [35] to derive the following hypotrochoidic law for the spectral boundary of cyclic random digraphs: (12) z b ( φ ) = 1 t e − i φ + d ̂ t k − 1 e i ( k − 1 ) φ , where k is the length of cycles, d ̂ is the (degree biased) number of cycles per node [31] , and t is the unique positive real solution of ( d ̂ − 1 ) t 2 k − d ̂ t 2 + 1 = 0 . The EMA is technically valid in the case 1 ≪ d ̂ ≪ N ; however, numerical simulations show excellent agreement down to relatively small values of d ̂ (see Fig. 3 ). For fixed node degrees it is exact. 10.1103/PhysRevE.100.010302.f3 3 FIG. 3. Hypotrochoid curves (black lines) bounding the eigenvalue spectra (blue dots) of sparse random digraphs composed of k cycles. In (a) the networks were generated to have nodes with fixed in-degree and out-degree, here d = 2 ; in (b) nodes are assigned to cycles uniformly randomly, resulting in Poisson distributions for both in-degree and out-degree, with the mean degree being 〈 d 〉 = 8 in this case (for Poisson graphs d ̂ = 〈 d 〉 ). Note the similarity of (b) with the plots presented in Fig. 2 . To understand how both sparse and dense cyclic ensembles share the same universal behavior, we explore the asymptotic behavior of Eq. (12) as d ̂ → ∞ . For a direct comparison we rescale the adjacency matrix of the graph by d ̂ − 1 / 2 , which corresponds to the factor σ = N − 1 / 2 that we used before and that normalizes rows and columns. The previous result (12) for k = 3 then reads (13) z b ( φ ) = d ̂ − 1 / 2 t − 1 e − i φ − ( d ̂ 1 / 2 − d ̂ − 1 / 2 ) t 2 e 2 i φ with t being the same as in Eq. (12) . We note that for large d ̂ , t ∼ d ̂ − 1 / 2 , so that we recover the support (11) for full matrices with an effective parameter ρ 3 ∼ d ̂ − 1 / 2 . The same connection indeed appears when we compare the definition of the quantities σ 2 and ρ τ from the traces of M . By applying the noncrossing approximation to the full matrix we find (14) lim N → ∞ 1 N Tr M 3 l ¯ = 1 2 n + 1 3 l l ρ 3 l , (15) lim N → ∞ 1 N Tr ( M M † ) l ¯ = 1 l 2 l l , while carrying out the corresponding combinatorics for the graphs gives (16) lim N → ∞ 1 N Tr M 3 l ¯ = A ( 3 ) ( l , d ̂ ) d ̂ − 3 l / 2 , (17) lim N → ∞ 1 N Tr ( M M † ) l ¯ = A ( 2 ) ( l , d ̂ ) d ̂ − l , which we express in terms of the number of self-returning walks of length 2 l from the root of an infinite k -regular tree: (18) A ( m ) ( l , d ̂ ) = d ̂ l ∑ j = 0 l − 1 m l j ( l − j ) ( d ̂ − 1 ) j . Asymptotically for large d ̂ , A ( m ) ( l , d ̂ ) = d ̂ l l m l l − 1 = d ̂ l m l − l + 1 m l l , so that both expressions again match up for ρ 3 ∼ d ̂ − 1 / 2 . It is worth mentioning that the traces of M , which can be computed explicitly, relate to asymptotic spectral statistics in the so-called “trace formulas” which are relevant in random matrix theory [36] as well as in semiclassical physics [37,38] . These observations lend further support to our conclusion that the cycle structure captures the essential universal features of the eigenvalue distribution beyond the elliptic law. Polytrochoid spectra . Starting from Eq. (8) , our approach generalizes to matrices with correlations of multiple orders, leading to a boundary curve (19) z b ( φ ) = e − i φ + ∑ k ρ k e i ( k − 1 ) φ . The curve described by this equation is an example of the very general polytrochoid family. For the particular case of two competing correlation orders, the curve is described by tracing the path of a point in a wheel rotating around a larger wheel, which itself is rotating in the opposite direction around the origin. Adding further correlation orders would correspond to the addition of more linked wheels with the same drawing procedure. Polytrochoid spectral boundaries are also found in digraphs with mixed cycle lengths, where each vertex connects to d k k cycles of weight w k (see [31] for a derivation in the case of two competing cycle motifs). In the limit of large degrees, we obtain the explicit formula (20) z d ¯ = e − i φ + d 1 w 1 d ¯ k 1 e i ( k 1 − 1 ) φ + d 2 w 2 d ¯ k 2 e i ( k 2 − 1 ) φ , where d ¯ = d 1 w 1 2 + d 2 w 2 2 0 . Figure 4 shows a numerical illustration of this result, which is in excellent agreement with our derivations for relatively large degrees. 10.1103/PhysRevE.100.010302.f4 4 FIG. 4. Polytrochoid curve (black line) bounding the eigenvalue spectrum (blue dots) of a sparse regular random digraph composed of 3-cycles and 4-cycles, with each node appearing in four of each. In this case the curve is traced by the dot marked on the smaller wheel, which makes three turns around the larger wheel while the larger wheel makes one turn around the origin, in the opposite direction. Discussion . We have shown that high-order correlations in the entries of a random matrix give a surprising and even beautiful shape to its eigenvalues, with the boundary given by a hypotrochoid, generalizing the classical result from Girko [7] . Furthermore, we have uncovered a remarkable degree of universality of this result by connecting it to the known case of regular graphs with cyclic motifs [19] , and studied the relationship between both cases. Our derivations are in excellent agreement with numerical results. Our results have a simple interpretation in terms of systems theory. A feedback loop is a classical control theory tool to enhance or dampen certain frequencies. A cycle of length k where the product of the edge weights is w is a feedback loop with delay k and weight w , therefore a graph with abundance of cycles of length k with positive feedback would resonate at a frequency 1 k . On the spectral side, the presence of large positive correlations of order k leads to dominant eigenvalues (or poles, in control theory terms) with phases 2 π j k for j < k . This interpretation can also be used in the other direction. Matrices and graphs are useful models to represent the interactions between elements, and our results show that random matrix theory can account for intricate multielement interactions. That is, the stability and resonance properties of complex systems with interconnected feedback loops can be studied by converting the loops into graph cycles and then applying our results in random matrix theory. For example, designing large networked systems such as the Internet or power grids is a challenging problem due to the amount of feedback loops present [39,40] . Likewise, biological regulatory systems [41–43] include many intertwined feedback loops that render their analysis difficult. In all those examples, their stability and dynamical properties can be studied through the spectrum of their adjacency matrix, which can be difficult to estimate. However, finding frequent cycles and their corresponding delays is typically easier [44–46] , meaning that we can leverage the simplicity of finding cycles to obtain rigorous results on the stability of those systems. We hope that the techniques and results presented here may inspire new developments in these fields. Finally, the system theory interpretation also provides relevant theoretical insights and questions. For instance, the effects of negative correlations, which in systems theory corresponds to a rotation of the poles, is also explained by Eqs. (11) and (12) . On the other hand, the combination of cycles with positive and negative feedbacks for the same length is not fully covered by our method: in the case of a full matrix or a dense digraph, the positive and negative feedbacks appear in a single connected graph and thus cancel each other—meaning that Eqs. (11) and (12) remain valid—but in very sparse digraphs the presence of many finite-size isolated subgraphs implies that there are components dominated by either positive or negative feedback, and thus the effective medium approximation does not hold. Acknowledgments. This work was supported by the Royal Society (T.R.) and EPSRC (H.S.) via Grant No. EP/P010180/1. The authors are grateful to Izaak Neri for highlighting important prior work on sparse networks with cycles.
ASJC Scopus subject areas
- Statistical and Nonlinear Physics
- Statistics and Probability
- Condensed Matter Physics