Journées X-UPS 2013

J’ai le plaisir cette année d’intervenir lors des journées mathématiques X-UPS, aux côtés de Christophe Giraud et de Sylvie Méléard. Ma mission est de proposer une introduction aux matrices aléatoires (documents électroniques: notes de cours et planches d’exposés).

Voici les réponses à quelques questions posées pendants les exposés:

Question. Comment montrer que la mesure de comptage normalisée des valeurs propres d’une matrice de permutation aléatoire de loi uniforme sur le groupe symétrique converge vers la loi uniforme sur cercle unité quand la dimension tend vers l’infini?

Réponse. il suffit de montrer que tous les moments convergent vers zéro:

\[ \forall r\in\mathbb{N}^*, \lim_{n\rightarrow\infty}\mathbb{E}\frac{1}{n}\mathrm{Tr}(P_\sigma^r)=0 \]

Ils sont liés aux points fixes de \( {\sigma^r} \) (cycles de longueur \( {r} \) de \( {\sigma} \)) comme évoqué ici.

Question. Combien de temps prend le calcul sur ordinateur du spectre d’une matrice 600×600?

Réponse. De l’ordre de la seconde avec Scilab sur un ordinateur portable ordinaire. Par ailleurs, sur mon ordinateur portable, la plus grande dimension praticable est de l’ordre de 1500, pour des raisons de mémoire vive essentiellement.

Question. Les calculs numériques de spectres sont-il précis ?

Réponse. Pas toujours. Il est possible de construire des exemples pathologiques (nilpotence, mauvais conditionnement) qui produisent des résultats numériques pathologiques. Cependant, les matrices à coefficient i.i.d. ne sont pas pathologiques avec grande probabilité. Les méthodes itératives de l’analyse numérique matricielle (comme l’algorithme QR par exemple) sont détaillées dans le livre de Golub et van Loan.

Question. D’accord \( {\mu_n(I):=\mu_{\frac{1}{\sqrt{n}}H}(I)} \) converge vers \( {\mu(I)} \), mais à quelle vitesse? Peut-on quantifier cette convergence?

Réponse. Oui, pour GUE par exemple, Gustavsson a montré que pour tout \( {I=]-\infty,x]} \) avec \( {-2<x<2} \), le théorème central limite suivant a lieu:

\[ \frac{\mu_n(I)-\mathbb{E}(\mu_n(I))}{\sqrt{\mathrm{Var}(\mu_n(I))}} \overset{\text{loi}}{\longrightarrow}\mathrm{Normale}(0,1). \]

De plus, \( {\mathbb{E}(\mu_n(I))=\mu(I)+O(\ln(n)/n^2)} \) et \( {2\pi^2\mathrm{Var}(\mu_n(I))\sim c\ln(n)} \) ce qui donne

\[ \frac{\sqrt{2}\pi n}{\sqrt{\ln(n)}} (\mu_n(I)-\mu(I)) \overset{\text{loi}}{\longrightarrow}\mathrm{Normale}(0,1). \]

La vitesse est différente pour \( {x=\pm2} \). La vitesse dépend également de la régularité de la fonction test (ci-dessus \( {f=\mathbf{1}_I} \)). D’après Pastur et Lytova, elle ne dépend pas de \( {n} \) lorsque \( {f} \) est continue bornée dérivable et à dérivée bornée:

\[ \frac{1}{\sigma_f}\left(\int\!f\,d\mu_n-\int\!f\,d\mu\right) \overset{\text{loi}}{\longrightarrow}\mathrm{Normale}(0,1) \]

où

\[ \sigma_f^2:=\frac{1}{4\pi^2}\int_{-2}^2\int_{-2}^2\! \left(\frac{f(x)-f(y)}{x-y}\right)^2 \frac{4-xy}{\sqrt{4-x^2}\sqrt{4-y^2}}\,dxdy. \]

On peut également, pour une classe de fonctions \( {\mathcal{F}} \), chercher à contrôler la quantité

\[ \sup_{f\in\mathcal{F}}\left|\int\!f\,d\mu_n-\int\!f\,d\mu\right|. \]

Lorsque par exemple \( {\mathcal{F}} \) est constituée par les fonctions lipschitziennes, on obtient la distance de couplage de Wasserstein W1, qui revient à contrôler le premier moment (sa vitesse est de l’ordre de \( {1/\sqrt{n}} \)). Pour en savoir plus, notamment au delà du cas GUE, on pourra consulter la thèse de Sandrine Dallaporta (2012).

Question. Faut-il dire inégalité de concentration de Azuma-Hoeffding ou de McDiarmid?

Réponse. La seconde est une version spéciale de la première, comme expliqué ici.

Question. Est-ce qu’on peut prouver le théorème de Wigner en se ramenant au cas gaussien?

Réponse. Oui, il existe des preuves spécifiques pour le cas gaussien GUE, qui tirent partie de la densité explicite des valeurs propres. Ensuite, il existe des stratégies de réduction au cas GUE, en remplaçant une à une les coefficients de la matrice par un coefficient gaussien. Cela nécessite l’utilisation de formules de Hadamard donnant la dérivée du spectre par rapport aux coefficients. Contrairement au cas du théorème central limite habituel, nous avons ici \( {n^2} \) variables, ce qui nécessite le contrôle de quatre moments des coefficients. Cette stratégie est au coeur de la preuve du théorème des quatre moments de Tao et Vu.

Question. Comment simuler des matrices orthogonales de loi uniforme?

Réponse. Il s’agit de simuler la mesure de Haar sur le groupe orthogonal. Il est possible d’utiliser l’algorithme d’orthonormalisation de Gram-Schmidt à partir de vecteurs aléatoires i.i.d. gaussiens (algorithme QR). Cela revient par exemple à effectuer un produit de \( {n} \) matrices de Householder aléatoires indépendantes spéciales, cf. Generation of random orthogonal matrices, par Anderson, Olkin, et Underhill. Pour le groupe unitaire, cf. How to generate random unitary matrices, par Ozols. Plus généralement, on pourra consulter How to Generate Random Matrices from the Classical Compact Groups, par Mezzadri. Cela fait penser à l’algorithme de Fisher-Yates-Knuth pour la mesure de Haar sur les matrices de permutations (groupe symétrique) qui consiste en un produit de \( {n} \) transpositions aléatoires indépendantes spéciales.