Eigenvalues of random lifts and polynomial of random permutation matrices

Abstract

Let $(\sigma_{1}, \ldots, \sigma_d)$ be a finite sequence of independent random permutations, chosen uniformly either among all permutations or among all matchings on $n$ points. We show that, in probability, as $n\to\infty$, these permutations viewed as operators on the $n-1$ dimensional vector space $\{(x_1,\ldots, x_n)\in \mathbb{C}^n, \sum x_i=0\}$, are asymptotically strongly free. Our proof relies on the development of a matrix version of the non-backtracking operator theory and a refined trace method.

As a byproduct, we show that the non-trivial eigenvalues of random $n$-lifts of a fixed based graphs approximately achieve the Alon-Boppana bound with high probability in the large $n$ limit. This result generalizes Friedman’s Theorem stating that with high probability, the Schreier graph generated by a finite number of independent random permutations is close to Ramanujan.

Finally, we extend our results to tensor products of random permutation matrices. This extension is especially relevant in the context of quantum expanders.

Authors

Charles Bordenave

Institut Mathématiques de Marseille, 39 rue Frédéric Joliot Curie, 13013 Marseille, France

Benoît Collins

Department of Mathematics, Graduate School of Science, Kyoto University, Kyoto 606-8502, Japan