In this paper
AbstractIntroductionComments about the use of AIThe model, normalization, and spectral measuresThe random graph and its Hermitian matrixThe mean and variance of matrix entriesEmpirical and expected spectral measuresOur main theoremsIngredients of the proofsExact diagonalization of the deterministic biasThe centered semicircle law by closed walksSpectral comparison and a norm estimateProofs of the main theoremsProof of Theorem 1Proof of Theorem 2Special cases and interpretationHow the familiar families fit into the modelExpected counts and the scale of the bulkThe spectrum of the mean is a different distributionWhy uncentered second moments need not be semicircularFurther questionsThe bulk and the large exceptional eigenvaluesReferencesWorksMathematics
Spectral distribution for biased orientations of random graphs
Abstract
We study the Hermitian adjacency matrix of the second kind for biased orientations of Erdos-Renyi random graphs. In the model , an edge is present with probability and, conditional on its presence, is directed from its smaller to its larger endpoint with probability . Both parameters may depend on , and biased tournaments are the special case . We prove a global semicircle law whenever , for both the centered and the uncentered matrix, and also for the expected empirical spectral measure. Our second theorem gives the exact spectrum of the mean matrix and the limits of the extreme eigenvalues on the scale , under a sufficient density assumption. The main difference from the unbiased random orientations (where ) is emergence of multiple large eigenvalues. The proofs include the closed-walk counting, control of the moment variances, an explicit diagonalization of the deterministic bias, and the passage from centered to uncentered spectral measures.
Introduction
Let be the Erdős–Rényi random graph on the ordered vertex set . We obtain a random oriented graph by independently directing every present edge from its smaller to its larger endpoint with probability , and in the opposite direction with probability . We denote the resulting model by . The parameters have distinct roles: controls edge presence, whereas controls orientation bias. Throughout, both and may vary with .
Biased tournament models have some history. Probably the earliest paper is by Frank [6]. Łuczak, Ruciński, and Gruszka [16] studied the evolution of biased tournaments, and, more recently, Gishboliner, Krivelevich, and Kronenberg [8] considered the chromatic number of biased tournaments. However, their eigenvalues were not studied before. The same holds for biased orientations of random graphs.
We use the sixth-root Hermitian adjacency matrix introduced by the author [17], also called the Hermitian adjacency matrix of the second kind. There are several reasons why this specific choice is the most natural one, see [17] and [2]. An arc has weight in its direction and weight in the reverse direction. The earlier Hermitian adjacency matrix, introduced independently by Guo and Mohar [10] and Liu and Li [15], uses weights and . Further properties of the second-kind matrix are studied by Li and Yu [14]. The main distinction between the two conventions is that the real part creates a nonzero mean even when .
Our results use Wigner’s semicircle law [20] and the standard spectral comparison methods described for example in Bai and Silverstein [3] and in other textbooks about eigenvalues of random matrices, a popular example being a recent manuscript of Tao [18]. Related results for random oriented graphs and random mixed graphs include the work of Chen, Li and Lian [5], Hu, Li, Liu and Zhang [13], and Guan et al. [9]. Separation of the leading eigenvalue for first-kind Hermitian matrices of random mixed graphs is studied by Hu, Broersma, Hou and Zhang [11]. The same authors give bounds on skew spectral radii of general random oriented graphs in [12]. These results provide context, but the mean and variance computation for the present matrix and model bear notable differences.
We give two main theorems for the family . The first describes the bulk spectrum and its expected empirical measure. The second describes the deterministic mean spectrum and the extreme eigenvalues on the scale . Uniformly oriented random graphs and biased tournaments are particular special cases, obtained by setting and , respectively.
The bulk theorem is a model-specific application of the classical moment method. Its main additional ingredient is the treatment of the mean matrix. Under a nonzero bias, the imaginary part of the mean has large rank and norm of order . Nevertheless, after bulk normalization it can be decomposed into a matrix of rank and a matrix of norm . We derive this decomposition from an explicit cotangent formula for its eigenvalues. Details are included to explain both the parameter assumptions and the different roles of bulk and extreme eigenvalues.
Comments about the use of AI
I have known the results collected in this paper since the original work in [10] and [17]. I have popularized it in several talks since I like the shift used to deal with the skew-symmetric part. This shift gives the eigenvalues at the complex line , which is reminiscent to the location of zeros of the Riemann zeta function. I also like the appearance of multiple large eigenvalues in the biased orientation models.
I was saving the final technicalities and subsequent paper submission for a graduate student. However, since the recent AI work in mathematics, I have realized that this is no longer a good Master Thesis problem and have decided to write it myself. I have used help from ChatGPT (the current model GPT-6.1 Sol) which has enhanced my original draft manuscript to my satisfaction. The model did not go much beyond my current understanding, but it was an extremely useful tool that saved me a lot of technical work and also provided some more generality. For example, § 6.3–§ 6.6 and several comments scattered around have been the work of ChatGPT.
My original results started with the unbiased case, but since that case has been more or less covered by Hu et al. [13, 11] and by Guan et al. [9], I decided to stick with biased orientations, the case of which provides a novel outcome, where several large eigenvalues appear in addition to the bulk of eigenvalues following the semicircle distribution.
The model, normalization, and spectral measures
The random graph and its Hermitian matrix
All graphs considered here have no loops, and there is at most one arc between any unordered pair of vertices. More explicitly, for each , independently of all other unordered pairs, the model makes the choices
| Outcome on | Probability |
| No edge | |
| The arc | |
| The arc |
caption:
:::
This is exactly the two-stage construction of first sampling a random undirected graph and then orienting its present edges with bias . In particular,
is the biased tournament on the ordered vertex set , with forward orientation probability . At or every present edge is directed consistently with one of the two vertex orders. Such an orientation is deterministic conditional on the underlying graph; the graph remains random when .
For an oriented graph , its Hermitian adjacency matrix is , with
where
Thus , so is Hermitian and has real eigenvalues. We count multiplicities and order them as
If is the adjacency matrix of the underlying undirected graph and is the real skew-adjacency matrix, whose -entry is for , for , and otherwise, then
The two summands use the same edge choices and are generally dependent. Our proofs work with the entries of directly. Reversing every arc replaces by , which has the same real eigenvalues. Consequently the spectral distributions for parameters and are identical.
As mentioned before, several results work for more general gain graphs, where each edge has an arbitrary complex weight with and the symmetric matrix entry has . The gain may even be different for different pairs . In particular, Theorem 1 extends to gain graphs.
The mean and variance of matrix entries
For the remainder of the article, write
We will first determine the mean and variance of the entries of , viewed as a random matrix corresponding to our model . Since , the following expressions are nonnegative.
For , direct calculation gives
For a complex random variable, variance here means , not . Notice that . It vanishes precisely when , or when and .
Let be the all-ones matrix, the identity, and the deterministic skew-symmetric matrix with entries above the diagonal, below it, and on the diagonal. Then the mean matrix and the corresponding centered matrix are defined as
The entries of above the diagonal are independent, centered, and have common variance . They satisfy the uniform bound
We also define the normalization factor
Let us observe that we allow and to depend on . Therefore, also the constants in (4) and (7) depend on in general. When necessary we write to emphasize dependence on . A normalization by is used only when .
Empirical and expected spectral measures
For a Hermitian matrix of order , we define its spectral measure and its cumulative distribution function as
Here is unit mass at . For a random matrix , its expected empirical spectral measure is the deterministic measure that satisfies
for every Borel set . It is generally different from , the spectral measure of the mean matrix. The standard semicircle distribution has density
Its odd moments vanish and its -th moment is .
For convergence of (random) probability measures, we write if, for every bounded continuous real function , . That is, for every ,
Thus each integral against a fixed test function converges in probability to its prescribed limit. The notation denotes ordinary weak convergence of deterministic probability measures. We refer the reader to [4] for further details.
For a Hermitian matrix, is its operator norm (also called the spectral radius of ). We write when is bounded in probability, and when .
Our main theorems
We will prove two theorems. The first one establishes the weak convergence of spectral measures.
Theorem 1 (The semicircle bulk and its expectation). Let have distribution , and let be as in (2.7)–(2.10). If
then
In particular, for any fixed , we have
and
This is a global spectral statement. A proportion tending to 1 of the eigenvalues lies in any fixed enlargement of , but eigenvalues can be distributed differently and some individual eigenvalues can be much larger. The next theorem describes such eigenvalues on the scale .
Theorem 2 (The mean spectrum and the extreme eigenvalues). Let have distribution , and put .
If , set . The eigenvalues of , in decreasing order, are exactly
If , they are once and with multiplicity . If , all eigenvalues are zero.
Let . For all parameter sequences, we have
Suppose and . If , define and . For every fixed integer ,
If , then
It is worth noting that Theorem 2 does not require (14), although its part (iii) uses a related assumption that . The condition is sufficient (but not necessary) for the stated extreme-eigenvalue limits; no optimal threshold is asserted. The scale permits . If instead , the limits on the scale are obtained by multiplying the right-hand sides of (20)–(22) by . For a fixed nonzero limiting bias, each fixed index from either end has a nonzero limit on the scale . This does not mean that a positive proportion of the eigenvalues has that scale.
Ingredients of the proofs
Exact diagonalization of the deterministic bias
Lemma 1. For and , let and . Then
In particular,
Replacing by leaves the spectrum unchanged.
Proof. Add and write . Any eigenvalue of is real, and its eigenvector satisfies
In the difference between row and row , the first sum cancels and the second expression changes by . Thus
Since , is nonzero. If , this recurrence would force every coordinate to vanish, which is impossible since eigenvector is non-zero. We may therefore normalize and write
Here and . The first row of (25) becomes
Since , cancellation gives
The roots are , where . Solving (26) for gives
Conversely, these values and their geometric-coordinate vectors determined by (26) satisfy the first row and every consecutive row difference; hence they satisfy all rows. The values are distinct and decreasing because cotangent is strictly decreasing on . They give the full spectrum of . Subtracting proves (23).
Taking and gives and yields (24). Finally, . Conjugating an eigenvector preserves its real eigenvalue. This proves the last assertion.
The centered semicircle law by closed walks
The next lemma uses standard trace formula to express spectral moments via counting of closed walks in the complete graph with edges weighted by the matrix entries. The convenient assumption is that the random matrix has centered entries .
The lemma allows the entry distribution and its variance to depend on . The entries need not have a rotationally symmetric complex distribution, and no condition on is needed. In particular, they can arise by “centering” any gain values in , not necessarily restricted to the sixth roots of unity.
Lemma 2. Let be Hermitian with zero diagonal and independent entries above the diagonal. Suppose that for every , we have
where is a fixed constant. Let . If , then
Proof. We give the moment argument in five steps.
Step 1: Expand the trace as a sum of walks. For a fixed positive integer ,
Each term corresponds to a closed walk . Since the diagonal of is zero, we may assume that any consecutive vertices are distinct. If an unordered edge occurs just once, its associated centered entry is independent of all other factors, so this term also vanishes in the expectation.
For any remaining walk, let be its number of distinct unordered edges and its number of distinct vertices. Every edge is used at least twice, hence . The graph traced by the walk is connected, so .
Step 2: Bound on nonleading walk patterns. A walk pattern records the walk after relabeling vertices in their order of first appearance. In other words, the pattern is obtained from by omitting the repeated appearances of vertices and keeping only the first one. There are only finitely many such patterns for fixed , and a pattern with vertices has at most assignments of actual vertex labels. If an edge occurs times, in either direction, its factor in the expectation has absolute value at most
Independence across unordered edges now bounds the expectation for the walk by . Thus a fixed pattern contributes at most a constant depending on , multiplied by
If , the second factor tends to zero and the first is at most one. If but , the first factor is at most and hence (29) also tends to 0. Therefore only the case , , can have a nonzero limit. The underlying graph of any such pattern is a tree, and the walk traverses each of its edges exactly twice. Such patterns are called tree patterns.
Step 3: Count the leading tree walks. For a tree pattern, each of its edges is traversed exactly twice. Deleting any tree edge separates the support into two parts. A closed walk crosses this cut equally often in both directions, so the two traversals must be one in each direction. Each edge consequently contributes . This is why the complex phases do not affect the limiting law. Note also that the value in (29) is equal to 1 for every tree walk. Therefore, it suffices to count the number of tree patterns and tree walks.
For clarity, the number of tree walk patterns is the Catalan number . Mark the first traversal of each edge as an up-step and the return traversal as a down-step. On a tree with each edge used twice, a return is to the parent of the current vertex, and an up-step discovers a new vertex. The result is a path with up-steps and down-steps, never below its starting height. Conversely, such a path reconstructs a unique tree walk by introducing the next unused vertex at every up-step and returning to the parent at every down-step. The reflection argument counts these paths as
Each pattern has distinct label assignments. Its normalization in (28) is , and its entry expectation is . We obtain
Step 4: The spectral moments concentrate. We have determined the limit of expectation of () for every fixed . Now, we need to analyse its variance. Write for the product of entries associated with a walk . The variance of is a normalized sum of over pairs of closed walks of length . If their unordered edge-sets are disjoint, the products are independent and the covariance is zero, even if the walks share a vertex. Otherwise their union is connected. If some union edge occurs just once among the factors, centering kills both terms of the covariance. We therefore only need unions with edges, each used at least twice, and vertices.
The joint expectation is bounded by (see Step 2). The product of the separate expectations satisfies the same bound whenever it is nonzero: every shared edge supplies an extra factor , which can be bounded by . For each union pattern, the normalization is and there are at most labelings. Its absolute contribution is at most a constant times
where we used that for all sufficiently large . There are finitely many pairs of patterns for fixed , so
Chebyshev’s inequality and (30) show that each moment converges in probability to its semicircle value.
Step 5: Pass from moments to measures. We give the details because weak convergence does not, by itself, imply convergence of moments of unbounded functions. Write
The preceding steps show that for every integer ; for both sides are identically one.
First take an arbitrary subsequence of matrix orders. By further extraction, choose orders within the subsequence such that
This is possible because each maximum involves only finitely many moments, all converging in probability. The probabilities in (32) are summable. The first Borel–Cantelli lemma therefore gives an event of probability 1 on which simultaneously for every integer . Independence between different matrix orders is not needed.
Fix an outcome in that event and set . We now have a deterministic sequence of probability measures. Since , there is a finite constant such that, for every ,
Thus the measures are tight. Every subsequence consequently has a further subsequence converging weakly to a probability measure on .
We next show that any such limit has the required moments. To simplify the notation, we may assume that the originally chosen sequence converges weakly to . For a fixed , choose an even integer . Convergence of the -th moments gives , and hence
The weak limit also satisfies . To see this, we consider the function that is bounded and continuous, so the weak convergence implies
Letting and applying monotone convergence proves the stated bound.
Let be a continuous function equal to one on , zero outside , and taking values in . Weak convergence applies to the bounded continuous function . The above tail estimates allow us first to pass to the weak limit for fixed and then let . It follows that for every $k.
These moments identify uniquely. Indeed, for and every positive integer ,
Letting shows that is supported on . It has the same integrals of all polynomials as the semicircle distribution . Uniform polynomial approximation of continuous functions on then implies that . Thus, every weakly convergent subsequence of has the same limit, and tightness gives .
We have proved that every original subsequence admits a further subsequence along which weak convergence holds almost surely. This implies weak convergence in probability. More explicitly, if convergence failed for some bounded continuous test function, there would be a subsequence along which the probability of a fixed positive deviation stayed bounded away from zero. Its almost surely convergent further subsequence would contradict that property.
Finally, for bounded continuous , put and . Then and . For any ,
Taking limits and then letting proves convergence of the expectations, which is the weak convergence .
Spectral comparison and a norm estimate
For two Hermitian matrices of order , the rank inequality and Weyl’s inequality state that
See Bai and Silverstein [3]. Suppose , with and . The norm estimate moves each ordered eigenvalue by at most , and the rank estimate changes a distribution function by at most . Combining them gives
In particular, if , , and converges to a measure with continuous distribution function, then has the same weak limit. The assertion also holds for convergence in probability, by applying the displayed bounds at fixed points and using continuity of the limiting function.
We will use the concentration inequality in the general form used below. It is the two-sided consequence of Tropp [19], Theorem 6.1(ii) of that paper, pp. 421–422; the one-sided estimate is also stated as Theorem 1.4 of that paper.
Two-sided matrix Bernstein inequality. Let be independent random Hermitian matrices of order , with and almost surely, where is fixed. Put
For every ,
If , then almost surely.
Proof. Tropp’s Theorem 6.1(ii) in [19] bounds by the right-hand side of (38) with prefactor . Apply it to both and . The norm bound gives , and the variance parameter is unchanged. Since , a union bound supplies the factor 2.
If , positivity of implies almost surely for each .
To estimate the norm of , write it as a sum of rank-1 matrices:
Here is the -th coordinate vector. The summands are independent centered Hermitian matrices. The only nonzero block of a summand has eigenvalues , so its norm is at most 2 by (9). Squaring that block gives
Apply (38) with , , and . For and , this gives
For example, take . The exponent has absolute value at least : in general, satisfies , and here , , . Thus the probability is at most . In particular,
When , almost surely, and the same conclusion holds. This estimate is intended for separation on the scale ; it does not locate the sharp bulk edge.
Proofs of the main theorems
Proof of Theorem 1
Proof. By the assumption (14), we have that . The entries of satisfy the assumptions of Lemma 2 with . Consequently .
To prove the convergence of spectral measures of , we will need to control the spectrum of the imaginary mean , where . We will use Lemma 1 with and . We may assume that , so we have . By (24), the multiset of eigenvalues of consists of values , where . For and , if and only if or , where . The angles are equally spaced by . An interval of length contains at most of them, so
If , the left-hand side is zero and the bound is still valid.
Next, we split the mean into two “small” perturbations. Take the spectral decomposition of and retain in only eigenvalues of absolute value greater than and the corresponding projections into their eigenspaces. Let contain the part of the spectral decomposition corresponding to the remaining eigenvalues. Then , and by (42),
because and . Using the full mean in (8), we have the exact decomposition
The middle term has rank at most . The norm of the last term is at most . The comparison (37) and continuity of the semicircle distribution function now give . This argument is needed because the norm of the entire mean divided by need not tend to zero.
Finally, we take expectations and interval counts. For every bounded continuous test function, convergence of its integral in probability implies convergence of the expectation by the boundedness argument at the end of Lemma 2. This proves the last assertion of (15). The endpoints of have zero semicircle mass. Weak convergence therefore gives (16). Its left-hand side lies in , so its expectation also converges, proving (17). □
Proof of Theorem 2
Proof. (i) First, we identify the exact mean spectrum. For , (8) gives
If , complex conjugation allows us to replace it by without changing the eigenvalues. Apply Lemma 1 with and . Its angle is , which proves (18). If , the all-ones vector is an eigenvector of with eigenvalue , and its orthogonal complement has eigenvalue . This gives the stated spectrum. The case is immediate.
(ii) For part (ii), we pass from the mean to the random matrix. Weyl’s inequality applied to , followed by (41), proves (19).
(iii) If , then eventually, and gives
Consequently, the eigenvalues of and differ uniformly by . It remains to compute deterministic limits.
We can now evaluate the extreme deterministic eigenvalues. Suppose first that . Then , , and for fixed ,
since as . At the other end, the angle for is . The identity gives
Together with the above, this gives (20) and (21).
If instead , then . The norm formula in (24) and for give
The comparison matrix has eigenvalues once and otherwise. Further application of Weyl’s inequality and the above comparison of eigenvalues of and proves (22).
Special cases and interpretation
How the familiar families fit into the model
The following table records the bulk variance and the sufficient bulk condition used in the proof of Theorem 1.
| Special case | Entry variance | Bulk condition |
Table 1.
Both parameters in this table may still vary with , subject to the indicated restriction. In the first row, the equivalence of the displayed condition with follows from .
For unbiased orientations, Theorem 2 gives the more explicit estimates
since the mean has only one eigenvalue outside its scalar part. Thus ensures a single leading eigenvalue asymptotic to , with every other eigenvalue .
For tournaments, set throughout. The model is , the scale in the bulk theorem is , and the scale in the extreme theorem is . Its density assumption holds automatically. At , this agrees with the unbiased orientation of , and both descriptions give variance and a leading eigenvalue asymptotic to .
If and , there is no randomness. The tournament is transitive, up to reversing all arcs. Now and , so its entire spectrum is
In particular, and . This recovers the computation in [1]. The extreme-eigenvalue formulas still apply, while the bulk theorem has no variance normalization in this deterministic case.
More generally, if for a fixed , then , regardless of . The bulk condition is then equivalent to . If instead with , then , and the same equivalence holds.
Expected counts and the scale of the bulk
Theorem 1 answers the question of the expected eigenvalue distribution through the expected empirical measure. For fixed , it gives
On the original eigenvalue scale, a convenient bulk density approximation is therefore
where . Its meaning is the global interval-count statement above. Since is finite, the actual expected spectral measure is discrete; no exact density or local eigenvalue-spacing law is asserted. The scalar shift in the mean is negligible relative to .
Under the extreme theorem’s density assumption, we have and . Whenever the bulk theorem also applies,
Thus eigenvalues with a nonzero limit on the scale are well beyond the bulk scale. Their number need not be bounded, but their proportion tends to zero by the bulk law.
The spectrum of the mean is a different distribution
For fixed and fixed , let . The angles in (18) become uniformly distributed on . It follows that the unscaled mean matrix has the weak limit
Indeed, this is the distribution of , with uniform on . For any bounded continuous test function, restrict first to , where ordinary Riemann sums apply; the two omitted end intervals have total probability . Letting proves the weak convergence. Changing variables gives the displayed density. It is a Cauchy law with location and scale .
For , the mean instead has limiting measure , since its exceptional leading eigenvalue has mass only . In the deterministic transitive case , , (50) is also the limiting unscaled spectral measure of itself. For fixed parameters with , random fluctuations create the growing bulk scale . Consequently the measure in (50) must be distinguished from .
Why uncentered second moments need not be semicircular
Weak convergence controls bounded continuous test functions, and the function is unbounded. Large eigenvalues can therefore contribute to second moments without changing the weak bulk limit. For every oriented graph with arcs,
In our model, , so, when ,
For fixed and fixed with , the limit is
whereas the semicircle second moment is 1. The extra term comes from the mean. To see this, observe that , and
because the cross term has expectation zero. Dividing by explains both the semicircle contribution and the excess. This is why the moment proof is applied to , followed by a separate comparison for .
Further questions
The theorems describe global spectral measures and coarse extreme-eigenvalue limits. Natural next questions are the limiting laws when stays bounded, sharp separation thresholds for small , and fluctuations of the extreme eigenvalues. When , the smaller bias eigenvalues may interact with the bulk on intermediate scales. Comparing the norm of with suggests examining of order ; for fixed this is the usual order of magnitude . The present results do not determine that transition or its local statistics.
The bulk and the large exceptional eigenvalues
We finish by stating together what the two main theorems say about the different parts of the spectrum. Here the global bulk means the eigenvalues described by the limiting empirical measure on the scale . For a fixed , we use the window to make the assertion that this part contains asymptotically almost all eigenvalues precise. This window includes the spectral edges. In the narrower terminology used for local spectral statistics, bulk locations are normalized points in compact subintervals of ; neighborhoods of and are the edges.
Corollary 1 (Semicircle bulk with an unbounded exceptional part). Suppose that
Let , , and .
(i) For every fixed $\varepsilon > 0,
Within this scale, the eigenvalue counts follow the semicircle law: for every ,
In particular, every such interval contains a number of eigenvalues proportional to with probability tending to one.
(ii) For every fixed positive integer ,
where
Thus any fixed number of eigenvalues from each end has scale , which is asymptotically larger than the bulk scale.
(iii) For fixed , define
For every fixed integer ,
The exceptional counts therefore tend to infinity in probability on both sides, while their total proportion tends to zero.
Proof. Theorem 1 gives the interval-count limit and (53), since the semicircle law assigns mass one to and has no atoms. The constants in part (ii) are those of Theorem 2(iii). Moreover, implies
For each fixed , part (ii) consequently yields and . By the ordering of the eigenvalues, with probability tending to , at least eigenvalues lie above the positive threshold and at least lie below the negative threshold. This proves the first assertion of (55). The second one is precisely the complement of (53). □
The corollary distinguishes two types of conclusions. The bulk is a statement about proportions and the empirical distribution. The explicit exceptional limits concern fixed indices from either end. They do not assert that every eigenvalue outside the bulk window has order . Indices growing with can occur on intermediate scales. Nor do they specify a canonical boundary between the bulk and its edges.
For comparison, consider the ordinary adjacency matrix of with fixed . Its mean is , which, after a scalar shift, has rank one. The classical result of Füredi and Komlós [7 Theorem 1] gives and, for every fixed ,
Thus, with probability tending to one, there is exactly one eigenvalue beyond any fixed enlargement of the ordinary semicircle range. Under a nonzero limiting orientation bias, Corollary 1 instead gives unbounded exceptional counts on both sides. The additional deterministic term is responsible for this behavior: it has a whole sequence of positive and negative eigenvalues of order at fixed indices. At this imaginary mean vanishes, and Theorem 2 recovers single exceptional eigenvalue on the scale .
References
References
- [1]Sajeed Akbari, Jonathan Aloni, Maxwell Levit, Bojan Mohar, and S. Ahmad Mojallal. Hermitian spectra of tournaments. submitted for publication.
- [2]Sajeed Akbari, Jonathan Aloni, Maxwell Levit, Bojan Mohar, and Steven Xia. Spectrally symmetric orientations of graphs. arXiv: 2512.08049.
- [3]Z. Bai and J. W. Silverstein. Spectral Analysis of Large Dimensional Random Matrices. Springer Series in Statistics. Springer, New York, second edition, 2010. doi:10.1007/978-1-4419-0661-8.DOI
- [4]Patrick Billingsley. Convergence of Probability Measures. Wiley Series in Probability and Statistics. John Wiley & Sons, New York, second edition, 1999.
- [5]X. Chen, X. Li, and H. Lian. The skew energy of random oriented graphs. Linear Algebra Appl., 438:4547–4556, 2013. doi:10.1016/j.laa.2013.02.007.DOI
- [6]Ove Frank. Stochastic competition graphs. Review of the International Statistical Institute, 36(3):319–326, 1968.DOI
- [7]Z. Füredi and J. Komlós. The eigenvalues of random symmetric matrices. Combinatorica, 1(3):233–241, 1981. doi:10.1007/BF02579329.DOI
- [8]Lior Gishboliner, Michael Krivelevich, and Gal Kronenberg. On MAXCUT in strictly super-critical random graphs, and coloring of random graphs and random tournaments. Random Structures & Algorithms, 52(4):545–559, 2018.
- [9]Y. Guan, B. Cheng, M. Chen, M. Liang, J. Liu, J. Wang, C. Yang, and L. Zeng. The spectral distribution of random mixed graphs. Axioms, 11(3):126, 2022. doi:10.3390/axioms11030126.DOI
- [10]K. Guo and B. Mohar. Hermitian adjacency matrix of digraphs and mixed graphs. J. Graph Theory, 85:217–248, 2017. doi:10.1002/jgt.22057.DOI
- [11]D. Hu, H. Broersma, J. Hou, and S. Zhang. The spectra of random mixed graphs. Linear Algebra Appl., 653:320–338, 2022. doi:10.1016/j.laa.2022.08.019.DOI
- [12]D. Hu, H. Broersma, J. Hou, and S. Zhang. The skew spectral radius and skew Randić spectral radius of general random oriented graphs. Linear Algebra Appl., 685:125–137, 2024. doi:10.1016/j.laa.2024.01.003.DOI
- [13]D. Hu, X. Li, X. Liu, and S. Zhang. The spectral distribution of random mixed graphs. Linear Algebra Appl., 519:343–365, 2017. doi:10.1016/j.laa.2017.01.011.DOI
- [14]S. Li and Y. Yu. Hermitian adjacency matrix of the second kind for mixed graphs. Discrete Math., 345(5):112798, 2022. doi:10.1016/j.disc.2022.112798.DOI
- [15]J. Liu and X. Li. Hermitian-adjacency matrices and Hermitian energies of mixed graphs. Linear Algebra Appl., 466:182–207, 2015. doi:10.1016/j.laa.2014.10.028.DOI
- [16]Tomasz Łuczak, Andrzej Ruciński, and Jacek Gruszka. On the evolution of a random tournament. Discrete Mathematics, 148(1–3):311–316, 1996.DOI
- [17]B. Mohar. A new kind of Hermitian matrices for digraphs. Linear Algebra Appl., 584:343–352, 2020. doi:10.1016/j.laa.2019.09.024.DOI
- [18]Terence Tao. Topics in Random Matrix Theory, volume 132 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2012.DOI
- [19]J. A. Tropp. User-friendly tail bounds for sums of random matrices. Found. Comput. Math., 12:389–434, 2012. doi:10.1007/s10208-011-9099-z.DOI
- [20]E. P. Wigner. On the distribution of the roots of certain symmetric matrices. Ann. of Math. (2), 67:325–327, 1958. doi:10.2307/1970008.DOI