The distribution of eigenvalues of randomized permutation matrices
Annales de l'Institut Fourier, Volume 63 (2013) no. 3, p. 773-838

In this article we study in detail a family of random matrix ensembles which are obtained from random permutations matrices (chosen at random according to the Ewens measure of parameter θ>0) by replacing the entries equal to one by more general non-vanishing complex random variables. For these ensembles, in contrast with more classical models as the Gaussian Unitary Ensemble, or the Circular Unitary Ensemble, the eigenvalues can be very explicitly computed by using the cycle structure of the permutations. Moreover, by using the so-called virtual permutations, first introduced by Kerov, Olshanski and Vershik, and studied with a probabilistic point of view by Tsilevich, we are able to define, on the same probability space, a model for each dimension greater than or equal to one, which gives a meaning to the notion of almost sure convergence when the dimension tends to infinity. In the present paper, depending on the precise model which is considered, we obtain a number of different results of convergence for the point measure of the eigenvalues, some of these results giving a strong convergence, which is not common in random matrix theory.

Dans cet article, nous étudions en détail une famille d’ensembles de matrices aléatoires qui sont obtenues à partir de matrices de permutation aléatoires en remplaçant les coefficients égaux à un par des variables aléatoires complexes non nulles plus générales. Pour ces ensembles, les valeurs propres peuvent être calculées très explicitement en utilisant la structure en cycles des permutations. De plus, en utilisant les permutations virtuelles, étudiées par Kerov, Olshanski, Vershik et Tsilevich, nous sommes capables de définir, sur le même espace de probabilité, un modèle pour chaque dimension supérieure ou égale à un, ce qui donne un sens à la notion de convergence presque sûre quand la dimension tend vers l’infini. Dans le présent article, selon le modèle précis qui est étudié, nous obtenons différents résultats de convergence pour la mesure ponctuelle des valeurs propres, certains de ces résultats donnant une convergence forte.

Received : 2010-12-06
Accepted : 2012-03-15
Classification:  15A18,  15A52,  20B30
Keywords: Random matrix, permutation matrix, virtual permutation, convergence of eigenvalues
     author = {Najnudel, Joseph and Nikeghbali, Ashkan},
     title = {The distribution of eigenvalues of randomized permutation matrices},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {63},
     number = {3},
     year = {2013},
     pages = {773-838},
     doi = {10.5802/aif.2777},
     zbl = {1278.15010},
     mrnumber = {3137473},
     language = {en},
     url = {}
Najnudel, Joseph; Nikeghbali, Ashkan. The distribution of eigenvalues of randomized permutation matrices. Annales de l'Institut Fourier, Volume 63 (2013) no. 3, pp. 773-838. doi : 10.5802/aif.2777.

[1] Anderson, Greg W.; Guionnet, Alice; Zeitouni, Ofer An introduction to random matrices, Cambridge Studies in Advanced Mathematics, Tome 118, Cambridge University Press, Cambridge, 2010 | MR 2760897 | Zbl 1184.15023

[2] Arratia, Richard; Barbour, A. D.; Tavaré, Simon Logarithmic combinatorial structures: a probabilistic approach, EMS Monographs in Mathematics, European Mathematical Society (EMS), Zürich, 2003 | MR 2032426 | Zbl 1040.60001

[3] Billingsley, Patrick Convergence of probability measures, Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons Inc., New York, 1999 (A Wiley-Interscience Publication) | MR 1700749 | Zbl 0172.21201

[4] Dehaye, P-O.; Zeindler, D. On averages of randomized class functions on the symmetric group and their asymptotics (2009) (

[5] Diaconis, Persi Patterns in eigenvalues: the 70th Josiah Willard Gibbs lecture, Bull. Amer. Math. Soc. (N.S.), Tome 40 (2003) no. 2, pp. 155-178 | Article | MR 1962294 | Zbl 1161.15302

[6] Diaconis, Persi; Shahshahani, Mehrdad On the eigenvalues of random matrices, J. Appl. Probab., Tome 31A (1994), pp. 49-62 (Studies in applied probability) | Article | MR 1274717 | Zbl 0807.15015

[7] Evans, Steven N. Eigenvalues of random wreath products, Electron. J. Probab., Tome 7 (2002), pp. 1-15 | Article | MR 1902842 | Zbl 1013.15006

[8] Hambly, B. M.; Keevash, P.; O’Connell, N.; Stark, D. The characteristic polynomial of a random permutation matrix, Stochastic Process. Appl., Tome 90 (2000) no. 2, pp. 335-346 | Article | MR 1794543 | Zbl 1047.60013

[9] Kerov, Serguei; Olshanski, Grigori; Vershik, Anatoli Harmonic analysis on the infinite symmetric group. A deformation of the regular representation, C. R. Acad. Sci. Paris Sér. I Math., Tome 316 (1993) no. 8, pp. 773-778 | MR 1218259 | Zbl 0796.43005

[10] Mehta, Madan Lal Random matrices, Pure and Applied Mathematics (Amsterdam), Tome 142, Elsevier/Academic Press, Amsterdam, 2004 | MR 2129906 | Zbl 1107.15019

[11] Mezzadri, F.; Snaith, N.-C. (eds.) Recent perspectives in random matrix theory and number theory, London Mathematical Society Lecture Note Series, Tome 322, Cambridge University Press, 2005 | MR 2145172 | Zbl 1065.11002

[12] Olshanski, G. Asymptotic combinatorics with applications to mathematical physics, Lecture Notes in Mathematics, Tome 1815, Springer, 2003 | MR 2009838

[13] Pitman, J. Combinatorial stochastic processes, Lecture Notes in Mathematics, Tome 1875, Springer-Verlag, Berlin, 2006 (Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002, With a foreword by Jean Picard) | MR 2245368 | Zbl 1103.60004

[14] Tsilevich, N. V. Distribution of cycle lengths of infinite permutations, J. Math. Sci., Tome 87 (1997) no. 6, pp. 4072-4081 | Article | MR 1374318 | Zbl 0909.60011

[15] Tsilevich, N. V. Stationary measures on the space of virtual permutations for an action of the infinite symmetric group (1998) (PDMI Preprint)

[16] Wieand, Kelly Eigenvalue distributions of random permutation matrices, Ann. Probab., Tome 28 (2000) no. 4, pp. 1563-1587 | Article | MR 1813834 | Zbl 1044.15017

[17] Wieand, Kelly Permutation matrices, wreath products, and the distribution of eigenvalues, J. Theoret. Probab., Tome 16 (2003) no. 3, pp. 599-623 | Article | MR 2009195 | Zbl 1043.60007

[18] Zeindler, Dirk Permutation matrices and the moments of their characteristic polynomial, Electron. J. Probab., Tome 15 (2010) no. 34, pp. 1092-1118 | MR 2659758 | Zbl 1225.15038