Mines Maths 1 MP 2016

Thème de l'épreuve Autour de l'inégalité de Hoffman-Wielandt
Principaux outils utilisés convexité, réduction, permutations, matrices symétriques, lois de probabilité
Mots clefs matrices circulantes, théorème spectral, inégalité de réarrangement, inégalité de Hoffman-Wielandt, théorème de Birkhoff-Von Neumann, matrice bistochastique, matrice extrémale

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


A 2016 - MATH. I MP. École des PONTS ParisTech, ISAE-SUPAERO, ENSTA ParisTech, TÉLÉCOM ParisTech, MINES ParisTech, MINES Saint-Étienne, MINES Nancy, TÉLÉCOM Bretagne, ENSAE ParisTech (Filière MP). CONCOURS 2016 PREMIÈRE ÉPREUVE DE MATHÉMATIQUES (Durée de l'épreuve : 3 heures) L'usage de l'ordinateur ou de la calculatrice est interdit. Sujet mis à la disposition des concours : Concours Commun TPE/EIVP, Concours Mines-Télécom, Concours Centrale-Supélec (Cycle international). Les candidats sont priés de mentionner de façon apparente sur la première page de la copie : MATHÉMATIQUES I - MP L'énoncé de cette épreuve comporte 6 pages de texte. Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre. Autour de l'inégalité de Hoffman-Wielandt Dans tout le problème n désigne un entier supérieur ou égal à 2. Soit Mn (R) l'ensemble des matrices carrées d'ordre n à coefficients réels et A un sous ensemble de Mn (R). On dit qu'une matrice A Mn (R) est extrémale dans A si pour tous M, N dans A et tout ]0, 1[, on a l'implication : A = M + (1 - )N = A = M = N. On note Bn l'ensemble des matrices bistochastiques de Mn (R), c'est-à-dire l'ensemble des matrices A = (Ai,j )16i,j6n dont tous les coefficients sont positifs ou nuls et tels que n Ø j=1 Ai,j = n Ø Aj,i = 1 pour tout i {1, 2, . . . , n}. j=1 On note enfin Pn l'ensemble des matrices de permutation M Mn (R) dont les coefficients sont de la forme : (M )i,j = 1 0 si i = (j) sinon, pour tous i, j dans {1, 2, . . . , n}, où est une permutation de {1, 2, . . . , n}. La partie A n'est pas indispensable à la résolution des parties suivantes. A Un exemple Soit J la matrice de Mn (C) définie par 0 1 0 0 0 1 . . . . . J = . . .. ... 0 1 0 ... ... .. . ... ... 0 0 .. . 0 1 0 c'est-à-dire par Ji,j = 1 si j - i = 1 ou i - j = n - 1, et Ji,j = 0 sinon. 1. Montrer que J est une matrice de permutation. Calculer les valeurs propres réelles et complexes de J, et en déduire que J est diagonalisable sur C. 2. Déterminer une base de Cn de vecteurs propres de J. 2 Dans les trois questions suivantes n désigne un entier naturel impair > 3. Pour tout m N, on note Xm une variable aléatoire à valeurs dans {0, 1, . . . , n - 1} telle que · X0 = 0 avec probabilité 1 ; · si Xm = k, alors ou bien Xm+1 = k - 1 modulo n, ou bien Xm+1 = k + 1 modulo n, ceci avec équiprobabilité. On note Um = P (Xm = 0) P (Xm = 1) . .. . P (Xm = n - 1) 3. Déterminer U0 et une matrice A de Mn (R) telle que pour tout m N, Um+1 = AUm . On exprimera A à l'aide de la matrice J. 4. Déterminer les valeurs propres de la matrice A et un vecteur propre de Rn unitaire associé à la valeur propre de module maximal. 5. En déduire la limite de Um lorsque m +. B Théorème de Birkhoff-Von Neumann 6. Montrer que l'ensemble Bn est convexe et compact. Est-il un sous espace vectoriel de Mn (R) ? 7. Montrer que Pn Bn et que Pn est un sous-groupe multiplicatif de GLn (R). Tout élément de Pn est-il diagonalisable sur C ? L'ensemble Pn est-il convexe ? 8. Montrer que toute matrice de Pn est extrémale dans Bn . Dans toute la suite de cette partie, on considère une matrice bistochastique A = (Ai,j )16i,j6n qui n'est pas une matrice de permutation. 9. Montrer qu'il existe un entier r > 0 et deux familles i1 , i2 , . . . , ir et j1 , j2 , . . . , jr 3 TSVP d'indices distincts dans {1, 2, . . . , n} tels que pour tous k {1, 2, . . . , r}, Aik ,jk ]0, 1[ et Aik ,jk+1 ]0, 1[ avec jr+1 = j1 . 10. En considérant la matrice B = (Bi,j )16i,j6n de Mn (R) définie par : Bik ,jk =1 k {1, 2, . . . , r} Bik ,jk+1 = -1 k {1, 2, . . . , r} dans les autres cas, Bi,j = 0 montrer que A n'est pas un élément extrémal de Bn . En déduire l'ensemble des éléments extrémaux de Bn . On dit qu'une matrice M = (Mi,j )16i,j6n de Mn (R+ ), à coefficients positifs ou nuls, admet un chemin strictement positif s'il existe une permutation de {1, 2, . . . , n} telle que M(1),1 M(2),2 · · · M(n),n > 0. On démontre par récurrence sur n, et on admet le résultat suivant : si M est à coefficients positifs ou nuls et si toute matrice extraite de M ayant p lignes et q colonnes avec p + q = n + 1 n'est pas la matrice nulle, alors M admet un chemin strictement positif. 11. Montrer que A admet un chemin strictement positif. On note une permutation de {1, 2, . . . , n} telle que A(1),1 A(2),2 · · · A(n),n > 0 1 et on pose 0 = min(A(j),j ) et A0 = (A - 0 M ) où M est la matrice de j 1 - 0 permutation associée à . 12. Montrer que A0 est bien définie, et que c'est une matrice bistochastique contenant au moins un élément nul de plus que A. 13. En raisonnant par récurrence, démontrer que A s'écrit comme une combinaison linéaire d'un nombre fini de matrices de permutation M0 , M1 , . . . , Ms : A = 0 M 0 + 1 M 1 + · · · + s M s où les coefficients i sont tous strictement positifs et de somme 4 qs i=0 i = 1. 14. Soit une forme linéaire de Mn (R). Montrer que inf (M ) existe. En M Pn déduire que inf (M ) existe et est atteint en une matrice de permutation. M Bn C Inégalité de Hoffman-Wielandt Dans cette partie, on munit Mn (R) de la norme euclidienne ë · ë associée au produit scalaire défini par éA, Bê = tr(tA · B). On note Sn (R) le sous-ensemble de Mn (R) des matrices symétriques et On (R) celui des matrices orthogonales. 15. Montrer que pour tous A Mn (R) et P, Q dans On (R), on a ëPAQë = ëAë. Dans la suite de cette partie, A et B désignent deux matrices symétriques réelles. 16. Montrer qu'il existe deux matrices diagonales réelles DA ,DB , et une matrice orthogonale P = (Pi,j )16i,j6n telles que ëA - Bë2 = ëDA P - P DB ë2 . 17. Montrer que la matrice R définie par Ri,j = (Pi,j )2 pour tous i, j dans {1, 2, . . . , n} est bistochastique et que ëA - Bë2 = Ø Ri,j |i (A) - j (B)|2 16i,j6n où 1 (A), . . . , n (A) désignent les valeurs propres de A et 1 (B), . . . , n (B) celles de B. 18. En déduire que min n Ø |(j) (A) - j (B)|2 6 ëA - Bë2 j=1 où le minimum porte sur l'ensemble de toutes les permutations de {1, 2, . . . , n}. Soit (, A, P ) un espace probabilisé et V l'ensemble des variables aléatoires définies sur cet espace admettant un moment d'ordre 2. Pour tout X de V , on 5 TSVP note X PX si X suit la loi PX . Pour tout couple (P1 , P2 ) de lois, on pose d2 (P1 , P2 ) = inf X,Y V XP1 ,Y P2 E(|X - Y |2 ). Soit (a1 , . . . , an ) et (b1 , . . . , bn ) deux familles de réels. On note P1 la loi uniforme sur {a1 , . . . , an } et P2 la loi uniforme sur {b1 , . . . , bn }. 19. Montrer que d2 (P1 , P2 ) = n 1Ø |a(i) - b(i) |2 n i=1 où l'on a noté a(1) 6 · · · 6 a(n) et b(1) 6 · · · 6 b(n) les suites (a1 , . . . , an ) et (b1 , . . . , bn ) ré-ordonnées par ordre croissant. En déduire que pour toutes matrices symétriques réelles A, B de valeurs propres respectives (a1 , . . . , an ) et (b1 , . . . , bn ), on a l'inégalité : n d2 (P1 , P2 ) 6 ëA - Bë2 . Fin du problème 6

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Mines Maths 1 MP 2016 -- Corrigé Ce corrigé est proposé par Denis Conduché (Professeur en CPGE) ; il a été relu par Antoine Sihrener (Professeur en CPGE) et Benoît Chevalier (ENS Ulm). Ce sujet porte sur l'inégalité de Hoffman-Wielandt, les valeurs propres des matrices symétriques, et les matrices bistochastiques. Une matrice stochastique est une matrice carrée à coefficients réels positifs dont les sommes des éléments de chaque ligne valent 1. Les matrices bistochastiques sont les matrices stochastiques dont la transposée est aussi stochastique. L'ensemble des matrices bistochastiques est l'enveloppe convexe des matrices de permutation : c'est le théorème de Birkhoff-Von Neumann, montré dans la partie B. Le sujet est découpé en trois parties, la première servant d'introduction et les deux autres étant assez indépendantes. · La partie A s'intéresse à la matrice associée à la permutation circulaire, dite matrice circulante. Cette partie fait intervenir de la réduction sur C, des racines n-ièmes de l'unité et des probabilités liées aux chaînes de Markov, tout en restant très élémentaire. Les méthodes mises en oeuvre et les résultats obtenus sont classiques. · La partie B étudie la géométrie de l'ensemble Bn des matrices bistochastiques dans Mn (R). Bn est un convexe compact, et ses points extrémaux sont exactement les matrices de permutation. Les raisonnements sont souvent algorithmiques, et se formalisent par des récurrences. · La partie C s'intéresse aux matrices symétriques et à l'inégalité de HoffmanWielandt, qui permet de majorer la distance entre les valeurs propres de deux matrices symétriques. La dernière question introduit la distance de Wasserstein, ou earth mover's distance (EMD) entre deux mesures de probabilité. Choisir une distance pertinente est un problème clé de l'apprentissage statistique, ou machine learning, et l'EMD convient. Un des enjeux de la recherche actuelle est de baisser le coût machine ­ prohibitif ­ du calcul de cette distance. Le sujet est difficile : malgré quelques questions plus abordables, il contient peu d'algèbre linéaire classique et obligeait les candidats à manipuler des outils dont ils avaient, en principe, peu l'habitude. Indications Partie A 2 Résoudre les systèmes associés aux sous-espaces propres. Poser = e alléger les notations. 2i n pour 3 Utiliser la formule des probabilités totales. 4 Se ramener à l'étude de J, et diagonaliser A dans Cn . 5 Calculer la limite de Am en passant par la forme diagonale calculée en répondant à la question précédente. Partie B 6 Compacité : montrer que l'espace est fermé comme intersection d'images réciproques de fermés. 7 Diagonalisation : chercher un polynôme annulateur à racines simples. 8 Étudier les coefficients nuls de la matrice de Pn . 9 Tester sur un exemple, pour r petit. Une matrice a forcément un nombre fini de coefficients. 10 Placer A sur un segment d'intérieur non vide inclus dans Bn . La matrice B est un vecteur directeur de la droite sous-jacente. 11 Raisonner par l'absurde, en sommant les lignes liées au mineur nul. 12 Raisonner par l'absurde pour l'existence de A0 , et faire un calcul direct pour montrer qu'elle est bistochastique. 13 Raisonner par récurrence sur le nombre de coefficients non nuls. 14 Procéder par double inégalité pour montrer que Inf (M) = Inf (M). MPn MBn Partie C 16 Utiliser le fait qu'une matrice symétrique réelle est diagonalisable. n P n P t 17 Se rappeler que Tr ( A B) = Aij Bij . i=1j=1 18 Utiliser le résultat de la question 14. 19 Considérer des variables aléatoires X et Y de lois respectives P1 et P2 , puis la matrice bistochastique Mij = nP(X = ai , Y = bj ). A. Un exemple 1 · J est une matrice de permutation : Soit la permutation circulaire définie par (1) = n et i {2, . . . , n} (i) = i - 1 La matrice de permutation associée est J = M . Ainsi, J est une matrice de permutation. · Valeurs propres de J : Soit J (x) le polynôme caractéristique de J. J (x) = det(xIn - J) = x -1 0 .. . x .. . 0 -1 0 0 ··· 0 .. . -1 . . . .. .. . . 0 .. .. . . -1 ··· 0 x En développant par rapport à la première colonne, on obtient x -1 .. . 0 J (x) = x . .. . . . 0 ··· (0) .. .. . . 0 -1 x + (-1)n+1 (-1) -1 x (0) 0 ··· 0 .. . -1 . . . .. .. . . 0 x -1 Les deux matrices carrées de taille n - 1 étant triangulaires, il vient J (x) = xn + (-1)n+2+n-1 = xn - 1 L'ensemble des valeurs propres est donc l'ensemble des racines n-ièmes de l'unité, noté n 2ik o Un = e n k {0, . . . , n - 1} Finalement, Les valeurs propres réelles de J sont -1 et 1 si n est pair, et 1 si n est impair. Les valeurs propres complexes de J sont les racines n-ième de l'unité. · Diagonalisabilité : Le polynôme caractéristique de J est scindé à racines simples sur C, par conséquent J est diagonalisable sur C. 2i 2 Il reste à déterminer une base de chaque espace propre. Soit = e n Un . Soit k [[ 0 ; n - 1 ]]. Notons Ek = Ker ( k In - J) le sous-espace propre de J associé à la t valeur propre k . Soit X = x1 · · · xn Cn . Comme x2 x1 .. JX = J ... = . xn xn x1 1 x2 = k x1 k .. . il vient X Ek X Vect .. k . x = x n n-1 x1 = k xn (n-1)k La dernière égalité du système étant vérifiée car elle s'écrit x1 = nk x1 , ce qui est toujours vrai puisque n = 1. En notant 1 k Xk = .. . (n-1)k il vient Ek = Vect (Xk ). Comme J est diagonalisable d'après la question 1, l'espace L est la somme directe des sous-espaces propres de J, d'où Cn = n-1 k=0 Ek . Ainsi, (X0 , X1 , . . . , Xn-1 ) forme une base de Cn de vecteurs propre de J. La réduction de la matrice J permet de réduire toutes les matrices circulantes a0 a1 an-2 an-1 an-1 a0 a1 an-2 . . . . . . Mn (C) . . . A = an-2 .. .. .. . . . a1 a1 an-2 an-1 a0 On constate qu'une matrice circulante est un polynôme en J : A = n-1 P a J . =0 Par conséquent elle a les mêmes sous-espaces propres Ek = Vect (Xk ) que J, n-1 P pour les valeurs propres a k . =0 3 Dans cette question et les deux suivantes, comme le suggère l'énoncé, toutes les égalités de variables aléatoires seront notées modulo n, pour éviter d'avoir à distinguer les cas i = 0 lorsqu'on parle de i - 1, et i = n lorsqu'on parle de i + 1. Puisque l'événement (X0 = 0) est de probabilité 1 et que la somme des probabilités des (X0 = k) vaut 1, les événements (X0 = k) sont de probabilité nulle pour k 6= 0 : t U0 = 1 0 · · · 0 Soit m N fixé et i Xm+1 () = {0, . . . , n - 1}. La famille (Xm = k)k forme un système complet d'événements, ainsi P(Xm+1 = i) = n-1 P P((Xm+1 = i) (Xm = k)) k=0 Or P((Xm+1 = i) (Xm = k)) = 0 si k / {i - 1, i + 1} donc P(Xm+1 = i) = P((Xm+1 = i) (Xm = i - 1)) + P((Xm+1 = i) (Xm = i + 1)) = P(Xm+1 = i | Xm = i - 1)P(Xm = i - 1) + P(Xm+1 = i | Xm = i + 1)P(Xm = i + 1) De plus, d'où P(Xm+1 = k - 1 | Xm = k) = P(Xm+1 = k + 1 | Xm = k) = 1/2 P(Xm+1 = i) = 1 1 P(Xm = i - 1) + P(Xm = i + 1) 2 2 Ainsi, Um+1 = AUm avec