{'fraction_non_alphanumeric': 0.041384429804212676, 'fraction_numerical': 0.013454579196436856, 'mean_word_length': 4.103219696969697, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Spectral gap of doubly stochastic matrices generated from equidistributed unitary matrices

To a unitary matrix U we associate a doubly stochastic matrix M by taking the modulus squared of each element of U. To study the connection between onset of quantum chaos on graphs and ergodicity of the underlying Markov chain, specified by M, we study the limiting distribution of the spectral gap of M when U is taken from the Circular Unitary Ensemble and the dimension N of U is taken to infinity. We prove that the limiting distribution is degenerate: the gap tends to its maximal value 1. The shape of the gap distribution for finite N is also discussed.


Introduction
Recently it was proposed by Kottos and Smilansky [1,2] that quantum graphs can serve as a good "toy" model for quantum chaos. Numerical simulations confirmed that for some classes of graphs, including the fully connected graphs, the Bohigas-Giannoni-Schmit Conjecture [3] holds true. By this we mean that various statistical functions of the spectrum of the graphs converge to the corresponding functions obtained in Random Matrix Theory (RMT) [4] in the limit as the number of vertices is taken to infinity.
On the graphs, the quantum evolution operator assumes the form of a finite unitary matrix U. In [1,2] it was argued that the classical counterpart of the quantum system is the Markov chain on the directed bonds of the graph with the matrix M of the transition probabilities given by It was conjectured that there is a link between ergodicity of the Markov chain and the convergence of the quantum statistics to RMT results. However, in [5] it was shown that the statistics for a special family of graphs, the quantum star graphs, converge to a non-RMT limit as the size of the graphs increases. However "classically" the star graphs have nice properties: the corresponding Markov chain possesses a unique attracting equilibrium distribution which corresponds to the eigenvalue 1 of M. Thus ergodicity of each graph does not immediately imply RMT-like behaviour.
It is well-known that a good quantitative measure of ergodicity of a Markov chain is its spectral gap. Given the spectrum {1, λ 2 , λ 3 , . . . λ N } of M, the spectral gap is defined as The spectral gap indicates the speed of convergence of any initial distribution to the equilibrium one: the greater g is, the faster is the convergence. Tanner [6,7] suggested that if for a sequence of graphs the spectral gap of the corresponding Markov chains is uniformly bounded away from zero, then the spectral statistics will converge to their RMT form. This seems to be a good indicator of the conformance to RMT: while for each star graph the gap is non-zero, it decreases to zero as we increase the size of the graph. And in the numerically verified cases of RMT-like behaviour the gap stays bounded away from zero. To investigate the connection between random unitary matrices and the ergodicity of their "classical" analogues, we ask the following question: given a large random unitary matrix, find the probability distribution of the spectral gap of the corresponding Markov chain.

Preliminaries
Since the most natural ensemble of the unitary matrices is the Circular Unitary Ensemble (CUE), we shall restrict our attention to it, although the generalisation of the problem to other ensembles is straightforward.
where V and W are any two N × N unitary matrices.
The set of all such N × N matrices we denote by DS(N).
If U is unitary then the matrix M defined by (1) is doubly stochastic. For a Markov chain it means that the uniform measure is invariant, that is (1/N, . . . , 1/N) is a left eigenvector of M with the eigenvalue 1. We denote the gap probability density function by f N (g) and the corresponding cumulative distribution by For convenience we also denote by λ 2 (M) the second largest (by modulus) eigenvalue of the doubly stochastic matrix M, and, as a consequence, g = 1 − |λ 2 (M)|.

Numerics and a conjecture
First of all we are going to present the results of some numerical simulations. The algorithm we used is simple: random matrices from CUE(N) are generated using the Hurwitz parametrisation [8] (see also [9]), the spectrum of the corresponding doubly stochastic matrix M is computed and the gap is calculated according to the definition (2).
The cumulative distribution functions obtained for N = 2, 3, 5, 10, 20, 40, 80 for sample sizes of 10 5 are shown on Figure 1. From the plot we can see that the typical gap tends to 1 as we increase N. Thus it is natural to conjecture that the gap probability density function f N (g) converges to δ(g − 1) in the sense of distributions as N → ∞ or, in other words, Further evidence in support of this guess is presented by Figure 2, where the mean E|λ 2 | and the standard deviation σ of the second largest eigenvalue are plotted as functions of N. A good fit to the mean is given by E|λ 2 | ∝ 1/ √ N (which is supported by heuristic observations presented in Section 4). Note that since 0 ≤ |λ 2 | ≤ 1 and (7) to verify (6) it is enough to show that E|λ 2 | → 0 as N → ∞.

N = 2 case
In the case of N = 2 it is easy to calculate the gap probability explicitly. For completeness we include the derivation although it is obvious from Figure 1 that the distribution for N = 2 is not typical. A 2 × 2 unitary matrix can be parametrized as The Haar (uniform) measure on the CUE(2) can be expressed in terms of the parameters α, χ, ψ and φ as (2π) −3 dα dχ dψ d sin 2 φ. The corresponding doubly stochastic matrix is with eigenvalues 1 and cos 2 φ − sin 2 φ. Thus the gap is equal to 2 min(1 − sin 2 φ, sin 2 φ) and its distribution is uniform on the interval [0, 1] (which agrees with Figure 1).

Mean of the second largest eigenvalue
As a consequence, the gap distribution f N (g) converges to δ(g − 1) in the sense of distributions as N → ∞.
Proof. The eigenvalues of M ∈ DS(N) are, in general, complex. It would be more convenient to deal with nonnegative real eigenvalues. The trick is to consider the matrix A = M T M which, due to the semigroup property is also doubly stochastic. In addition, it is symmetric (all eigenvalues are real) and positive definite (i.e. all eigenvalues are nonnegative). To relate the eigenvalues of the matrices A and M we write for the second largest eigenvalue of A, where e = (1, . . . , 1) T is the eigenvector of both A and M with the eigenvalue 1, and y is the eigenvector of M corresponding to λ 2 (M). From (12) and the inequality (Eξ) 2 < E(ξ 2 ) we infer that to prove the Theorem it is enough to show that the mean of |λ 2 (A)| converges to zero as N → ∞.
The simplest way to estimate the second largest eigenvalue of A is to compute its trace. Since A is positively defined, we have Thus if we can find such n that E(Tr A n ) → 1, it will imply that E(λ 2 (A)) → 0. It turns out that it is enough to take n = 2. However let us consider n = 1 too.
And calculating the mean where due to the invariance of measure of CUE(N) the means of the different matrix elements are equal. To calculate E|U 1,1 | 4 one can either integrate over the measure of CUE(N), as was done in [10], or apply various invariance considerations [11]. The result is E|U 1,1 | 4 = 2/(N 2 + N) and therefore E(Tr A) → 2 as N → ∞. This agrees with the numerical observation that E|λ 2 (M)| ∝ 1/ √ N : the eigenvalues of A are then of order 1/N and there are N − 1 of them (not counting the 1).
In the case n = 2 we have Applying the averaging we again find that due to the invariance of the measure all contributions from the first sum are the same and there are (N 2 − N) 2 of them; there are 2N 2 (N − 1) contributions from the second and the third sum (the contributions are equal) and N 2 contributions from the last. Counting the number of terms in each sum, we write where the averages can be calculated using [11], .
Bringing everything together, we obtain which effectively finishes the proof.

Shape of the distribution of |λ 2 (M)|
It is now clear that the distributions f N (|λ 2 |) have singular limit. The natural question to ask, then, is what is the shape of f N (|λ 2 |) for finite, but large, N and whether there are sequences of normalizing coefficients a N and b N such that the random variables (|λ 2 | − a N )/b N have continuous limiting distribution. While we are unable to give a definite answer, we can make a guess. Since |λ 2 | = max j=2,...,N |λ j |, it is not unnatural to conjecture that for large N the distribution of the second largest eigenvalue |λ 2 | is well approximated by the Generalized Extreme Value distribution (GEV) [12,13], specified by its cumulative distribution function for some (N-dependent) ξ, a and b: the GEV distribution is used to model maxima of sequences of random variables.
To check our conjecture we fit the numerical data for N = 80 to the form (22) using an Splus routine by Coles [13]. The routine minimizes the log-likelihood function where x i is the sequence of observations of |λ 2 |. The result of the routine is plotted as the probability density function G ′ (x) for fitted ξ = −0.07, a and b against the histogram of the numerical data for |λ 2 |. One can see that the agreement is very good. The probability and quantile plots, which we do not present here, also show good agreement. As N is taken to infinity, the values of a and b decay to zero, so that the limit of the distribution is the step function, and ξ saturates at a nonzero value.

Conclusions
We have shown that if we take element-wise modulus squared of a large unitary matrix U, the resulting doubly stochastic matrix M will have large spectral gap: with high probability all N − 1 "free" eigenvalues will have small modulus. In particular, it means that the Markov chain corresponding to M will quickly relax from any initial distribution into the uniform stationary state. While our observation is by no means a proof of Tanner's [7] conjecture that the families of graphs with large gap in their "classical" spectrum will adhere to RMT predictions, it is another powerful argument in its favour. We also note that the unitary evolution matrix of a general graph is sparse due to the topological restrictions [1,2]. Thus, although arbitrary U can be considered as the scattering matrix for an N-star graph, the generalisation of the gap distribution to graphs with less trivial topology still remains to be studied.
The results for the mean of the traces of M T M and (M T M) 2 , obtained in the course of our proof, completely agree with the numerical observation that the mean gap increases with N like 1 − O N −1/2 . We also presented numerical evidence in favour of the claim that for finite N the distribution of the second largest eigenvalue is well approximated by the generalized extreme value distribution.