Eigenvalues of random lifts and polynomials 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.