  Consider 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 goes to infinity, these permutations viewed as
operators on the (n-1) dimensional vector space orthogonal to the vector with
all coordinates equal to 1, 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.
