Press "Enter" to skip to content

Journées X-UPS 2013

Centre de Mathématiques Laurent Schwartz - École Polytechnique

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) \]

\[ \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.

4 Comments

  1. christophe 2013-04-18

    Je confirme que c’étaient des journées enthousiasmantes!
    S’il fallait le refaire, je resignerais.

    Et bravo pour le tour de force de rendre accessibles les matrices aléatoires aux non-initiés
    ch

  2. Igor Carron 2013-05-11

    Djalil,

    Merci pour la lecon.

    Je trouve etonnant la question “Combien de temps prend le calcul sur ordinateur du spectre d’une matrice 600×600?” comme si le spectre d’une matrice aleteoires etait foncierement plus difficile.

    Un autre element a peut-etre dire est que les matrices aleatoires sont notoirement utilisees pour tout les calculs de sensibilite des spectres d’autre matrices (en particulier les matrices non normales qui sont issues de la modelisation de certain phenomenes physiques importants – linearisation de Navier Stokes, etc..-) Cette propriete de facilite de calcul du spectre est un atout quand on etudie un operateur “tres” non normale.

    Igor.

  3. Djalil Chafaï 2013-05-11

    Hello Igor. Je crois que c’était la dimension (600) qui a étonné la personne, sans doute habituée aux matrices de petite dimension, et non pas le caractère aléatoire des matrices. Les gens ne se rendent pas compte que l’algèbre linéaire de grande dimension est utilisée des milliards de fois par seconde partout dans le monde pour faire toutes sortes de choses…

  4. Igor Carron 2013-05-12

    En fait c’est cela qui m’a etonne venant de quelqu’un qui est loin dans le cursus universitaire/ingenieur. Mes enfants commencent a regarder les systemes d’equations lineaires a une/deux variables et je pense qu’il n’y pas plus grande source de debat que de leur dire que l’on a des problemes avec des millions ou des centaines de millions d’inconnues et en plus les systemes sont sous determines et que l’on cherche vraiment des aiguilles dans des bottes de foins 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *