Mines Maths 1 MP 2008

Thème de l'épreuve Inégalité d'Alexandrov
Principaux outils utilisés algèbre linéaire, topologie, déterminants, formes quadratiques
Mots clefs permanents, inégalité d'Alexandrov, espaces de Lorentz

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 2008 MATH. I MP ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES. ÉCOLES NATIONALES SUPÉRIEURES DE L'AÉRONAUTIQUE ET DE L'ESPACE, DE TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT-ÉTIENNE, DES MINES DE NANCY, DES TÉLÉCOMMUNICATIONS DE BRETAGNE. ÉCOLE POLYTECHNIQUE (Filière TSI). CONCOURS D'ADMISSION 2008 PREMIÈRE ÉPREUVE DE MATHÉMATIQUES Filière MP (Durée de l'épreuve : 3 heures) L'usage d'ordinateur ou de calculette est interdit. Sujet mis à la disposition des concours : ENSAE ParisTech, ENSTIM, TELECOM SudParis (ex TELECOM INT), TPE-EIVP, 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. Inégalité d'Alexandrov Dans tout ce problème, n est un entier au moins égal à 1. On note Sn le groupe des permutations de In = {1, · · · , n}. On note Mn, p (R) l'espace vectoriel des matrices à n lignes et p colonnes, à coefficients réels. Pour une matrice M Mn, n (R) de coefficients mij , on notera mj le j-ème vecteur colonne de M , celui dont les composantes sont (mij , i = 1, · · · , n). On écrira ainsi M = (m1 , · · · , mn ). On remarquera que mij est indifféremment le coefficient en ligne i et colonne j de M ainsi que la i-ième composante de mj . On identifiera une matrice colonne m et le vecteur de Rn dont les composantes dans la base canonique de Rn sont les coefficients de m. On note k k la norme euclidienne de Rn et x.y représente le produit scalaire euclidien de deux vecteurs de Rn . On note S la sphère unité de Rn , c'est-à-dire S = {x / kxk = 1}. Pour une matrice M Mn, n (R), pour i et j éléments de {1, · · · , n}, on note M (i|j) la matrice obtenue en supprimant de M la i-ème ligne et la j-ième colonne. Pour un vecteur colonne m, m(j) représente le vecteur colonne m duquel on a ôté la j-ième composante. Soit Q une matrice symétrique réelle de Mn,n (R). On note BQ la forme bilinéaire associée : pour tout x et y de Rn , BQ (x, y) = Qx.y, et on note Q la forme quadratique associée : Q (x) = BQ (x, x). Définition 1. Soit V un sous-espace vectoriel de Rn , on dira que Q est définie positive (respectivement positive, respectivement définie négative) sur V lorsque Q (x) > 0 pour tout x appartenant à V S (respectivement Q (x) > 0, respectivement Q (x) < 0). On notera V+ (respectivement - V+ 0 , respectivement V ) l'ensemble des sous-espaces vectoriels sur lesquels Q est définie positive (respectivement positive, respectivement définie négative). On pose r(Q ) = max+ (dim V ) et s(Q ) = max- (dim V ), V V V V avec la convention que maxV dim V = 0. 2 I Permanents Définition 2. Pour M = (m1 , . . . , mn ) Mn, n (R), on définit son permanent, noté per, par per : n Mn, 1 (R) - R 7 (m1 , . . . , mn ) - X m1(1) m2(2) . . . mn(n) . Sn On tiendra pour acquis que la forme per est multilinéaire et symétrique, c'est-à-dire invariante par permutation des vecteurs. 1. Établir pour tous m1 , m2 , · · · , mn éléments de Mn, 1 (R), l'inégalité | per(m1 , · · · , mn )| 6 n! n Y kmj k. j=1 n 2. Pour (m1 , · · · , mn ) et (r1 , r2 · · · , rn ) éléments de Mn, 1 (R) suivante : , établir l'inégalité | per(m1 , · · · , mn ) - per(r1 , · · · , rn )| 6 n! n X km1 k . . . kmj-1 k kmj - rj k krj+1 k . . . krn k, j=1 où l'on convient que km1 k . . . kmj-1 k = 1 pour j = 1 et krj+1 k . . . krn k = 1 pour j = n. 3. Montrer la propriété suivante : pour tout j In , per M = n X i=1 II mij per M (i|j) . (1) Formes quadratiques Dans toute cette partie, Q est une matrice symétrique réelle inversible. On note sp(Q) = (1 , · · · , n ) la suite de ses valeurs propres répétées selon leur multiplicité, n+ (Q) le nombre de termes strictement positifs dans sp(Q) et n- (Q) le nombre de termes strictement négatifs dans sp(Q). 3 - 4. Soit H V+ 0 et G V , montrer que H et G sont en somme directe et que r(Q ) + s(Q ) 6 n. 5. Montrer que r(Q ) > n+ (Q). On a alors de même s(Q ) > n- (Q). 6. Montrer que r(Q ) = n+ (Q) et que s(Q ) = n- (Q). Soit R une autre matrice symétrique réelle inversible de taille n telle qu'il existe une constante satisfaisant la propriété suivante : pour tout x et y de Rn , |BQ (x, y) - BR (x, y)| 6 kxk kyk. 7. Montrer qu'il existe > 0 tel que r(Q ) = r(R ) si 6 . III Espaces de Lorentz Définition 3. Soit Q Mn,n (R), une matrice symétrique et Q la forme quadratique associée. On dit que (Rn , Q) est un espace de Lorentz lorsque les propriétés suivantes sont vérifiées : i) Q est inversible, ii) r(Q ) = 1 et s(Q ) = n - 1. On suppose dans cette partie que Q Mn,n (R) est telle que (Rn , Q) soit un espace de Lorentz. Soit a un vecteur tel que Q (a) > 0 et b Rn . Soit l'application définie par : R - R - 7 Q (b + a). 8. On suppose, dans cette question, que a et b sont linéairement indépendants. Montrer qu'il existe au moins une valeur de telle que () < 0. 9. Établir la propriété : BQ (a, b)2 > Q (a)Q (b), avec égalité si et seulement si a et b sont colinéaires. On pourra s'inspirer de la preuve de l'inégalité de Cauchy-Schwarz. 4 (2) IV Inégalité d'Alexandrov On veut maintenant établir le théorème suivant. On note (e1 , · · · , en ) la base canonique de Rn . Théorème 1. Soit n un entier supérieur à 2. Soit m1 , · · · , mn des éléments de Rn à composantes strictement positives. Soit Q la matrice symétrique dont les coefficients sont définis par qij = per(m1 , m2 , · · · , mn-2 , ei , ej ), i In , j In Soit BQ et Q les formes bilinéaires et quadratiques associées à Q respectivement. L'espace (Rn , Q) est un espace de Lorentz. 10. Calculer r(Q ) et s(Q ) pour n = 2, c'est-à-dire pour 0 1 Q= . 1 0 ! On suppose le théorème 1 établi pour tout k 6 n - 1. 11. Établir pour tout j de In l'inégalité : 2 per(m1 , · · · , mn-3 , mn-2 , c, ej ) > per(m1 , · · · , mn-3 , mn-2 , mn-2 , ej ) × per(m1 , · · · , mn-3 , c, c, ej ), (3) avec égalité si et seulement si c(j) et mn-2 (j) sont colinéaires. Dans les questions 12 et 13, c est un élément de Rn tel que Qc = 0. 12. Établir l'identité : 0 = Qc.c = n X mj,n-2 per(m1 , · · · , mn-3 , c, c, ej ) j=1 13. Montrer que pour tout j In , per(m1 , · · · , mn-2 , c, ej ) = 0 et per(m1 , · · · , mn-2 , mn-2 , ej ) > 0. 5 14. En déduire Qc = 0 si et seulement si c = 0. Soit e = Pn i=1 ei , pour tout appartenant à [0, 1], on pose B (x, y) = per(m1 + (1 - )e, · · · , mn-2 + (1 - )e, x, y). On note Q et la matrice symétrique et la forme quadratique associées à la forme bilinéaire symétrique B . 15. Expliciter Q0 . Montrer que ses valeurs propres sont (n - 1)! et -(n - 2)! et que r(Q0 ) = 1 ainsi que s(Q0 ) = n - 1. 16. Soit et deux éléments distincts de [0, 1]. Montrer que, pour tout x et tout y de Rn , |B (x, y) - B (x, y)| 6 n n!| - | kxkkyk n-2 Y j=1 (kmj k + n). 17. Établir que r(Q1 ) = 1 et s(Q1 ) = n - 1. On pourra raisonner par l'absurde et considérer = sup[0,1] { / r(Q ) = 1}. 18. Établir l'inégalité d'Alexandrov qui stipule que pour m1 , · · · , mn-1 vecteurs de Rn à coordonnées strictement positives et b vecteur quelconque de Rn , 2 per(m1 , · · · , mn-1 , b) > per(m1 , · · · , mn-1 , mn-1 ) per(m1 , · · · , b, b). Fin du problème 6

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


 Mines Maths 1 MP 2008 -- Corrigé Ce corrigé est proposé par Gilbert Monna (Professeur en CPGE) ; il a été relu par Tristan Poullaouec (ENS Cachan) et Sophie Rainero (Professeur en CPGE). Ce problème porte sur le permanent d'une matrice carrée à coefficients réels. On peut définir le permanent de manière très simple : on prend la formule donnant le déterminant de la matrice M = (aij )16i,j6n P det M = ()a1(1) . . . an(n) Sn et on supprime le terme (), signature de la permutation . Autrement dit, on fait la somme de tous les produits possibles de coefficients de la matrice en prenant un terme et un seul par ligne et par colonne. Les mêmes causes produisant les mêmes effets, on obtient une forme multilinéaire par rapport aux lignes et aux colonnes, et en supprimant la cause on a supprimé l'effet : sans le terme (), la forme n'est plus antisymétrique mais symétrique. Ce problème se subdivise en quatre parties : · La première consiste en des majorations assez simples du permanent. La question 2 est un peu technique et la dernière donne un développement analogue à celui des déterminants. Il est évidemment préférable d'avoir les idées claires sur les déterminants, au programme de première année. · La deuxième partie porte sur des propriétés plus ou moins classiques des matrices symétriques réelles, la dernière question comprenant un intermède topologique assez délicat. · On passe ensuite aux espaces de Lorentz, pour établir deux propriétés qui seront utiles pour la suite, avant d'aborder, dans la quatrième partie, la démonstration du résultat principal du problème : une inégalité portant sur les permanents. C'est un problème difficile. On peut dire que c'est de la « haute algèbre », mais il est certainement très formateur. Le rapport du jury confirme la difficulté de ce problème en signalant qu'« un petit nombre de candidats a maîtrisé une partie importante du sujet ». Indications Partie I 1 Penser au cardinal du groupe symétrique. 2 Le déterminant d'une matrice est égal à celui de la matrice transposée : qu'en est-il pour le permanent ? Introduire les termes m(1)1 . . . m(j-1)(j-1) r(j)j . . . r(n)n sous forme d'une somme télescopique. 3 Utiliser la linéarité du permanent par rapport à chaque colonne comme vous l'avez vu faire pour établir les formules de développement d'un déterminant (au bon vieux temps, quand vous étiez en MPSI). Partie II 5 Se servir du théorème de réduction des matrices symétriques réelles. 6 Utiliser les questions 4 et 5. 7 La majoration d'une valeur absolue donne deux inégalités : choisir la bonne ! Dans un espace vectoriel normé de dimension finie la sphère unité est compacte. Partie III 8 Montrer l'existence d'une droite D de Vect (a, b) telle que la restriction de Q à D soit définie négative. 9 L'indication est fournie par l'énoncé : la suivre. Partie IV 11 Définir une structure de Lorentz sur Rn-1 de façon à faire une récurrence en utilisant le développement du permanent. 12 Traduire l'égalité Qc · c = 0 en utilisant les permanents, puis utiliser les propriétés de ces derniers. 13 Ne pas s'étonner de trouver dans cette question un résultat déjà démontré à la question 11. 14 Il faut montrer qu'on est dans le cas d'égalité de l'inégalité (3) et en tirer les conséquences. 15 Déterminer les coefficients de la matrice A = Q0 /(n - 2)! et étudier les propriétés de la matrice A + In . 16 Utiliser la question 2. 17 Utiliser la question 7. Les conseils du jury Le jury regrette à de nombreuses reprises les « tentatives de bluff » et insiste sur le fait qu'« en aucun cas, le correcteur ne peut attribuer de points s'il n'a pas la certitude absolue que la réponse donnée est parfaitement correcte d'autant plus qu'il n'est absolument pas question de pénaliser ceux des candidats qui ont pris le temps de bien rédiger. » Le jury conseille également aux candidats qui ne savent pas traiter une question et qui en admettent le résultat pour continuer de le dire clairement : « tout acte d'honnêteté est très apprécié ; en revanche, toute tentative de dissimulation ou de tricherie indispose les correcteurs et peut être très pénalisante. » I. Permanents 1 Par définition, per(m1 , m2 , . . . , mn ) = P m1(1) m2(2) . . . mn(n) Sn Le groupe Sn est de cardinal n!, par suite per(m1 , m2 , . . . , mn ) est la somme de n! nombres réels. D'après l'inégalité triangulaire, P |per(m1 , m2 , . . . , mn )| 6 |m1(1) m2(2) . . . mn(n) | Sn 6 P |m1(1) ||m2(2) | . . . |mn(n) | Sn Soit |m1(1) ||m2(2) | . . . |mn(n) | l'un des termes de la somme précédente. Le réel m1(1) est la première composante du vecteur colonne m(1) , de ce fait |m1(1) | 6 km(1) k Il en est de même pour tous les facteurs |mi(i) |, ainsi |m1(1) ||m2(2) | . . . |mn(n) | 6 km(1) kkm(2) k . . . km(n) k L'application est une permutation et par conséquent elle est bijective. Il s'ensuit km(1) kkm(2) k . . . km(n) k = km1 kkm2 k . . . kmn k Chacun des n! termes de la somme étant majoré par le même terme km1 k . . . kmn k, on peut majorer la somme elle-même par n! fois ce terme : |per(m1 , m2 , . . . , mn )| 6 n! n Q kmj k j=1 2 Le permanent est la somme de tous les produits possibles de n facteurs en choisissant un et un seul facteur par ligne et par colonne. Avec cette définition, il est facile de voir que le permanent d'une matrice est égal au permanent de sa transposée, c'est-à-dire P P m1(1) m2(2) . . . mn(n) = m(1)1 m(2)2 . . . m(n)n Sn Sn Le recours à cet artifice est nécessaire pour pouvoir facilement se débarrasser des permutations. En effet, par la suite, on va ordonner les termes : il est plus facile de manipuler m(1)1 la (1)e composante du vecteur m1 , dont on va majorer la valeur absolue par km1 k, plutôt que m1(1) la première composante du vecteur m(1) qu'il faudrait majorer par km(1) k. Ainsi, on peut écrire |per(m1 , m2 , . . . , mn ) - per(r1 , r2 , . . . , rn )| P P = m(1)1 m(2)2 . . . m(n)n - r(1)1 r(2)2 . . . r(n)n Sn = P Sn m(1)1 m(2)2 . . . m(n)n - r(1)1 r(2)2 . . . r(n)n Sn 6 P |m(1)1 m(2)2 . . . m(n)n - r(1)1 r(2)2 . . . r(n)n | Sn On a, comme dans la question précédente, une somme de n! termes. On va montrer que chacun d'eux est majoré par n P km1 k . . . kmj-1 kkmj - rj kkrj+1 k . . . krn k j=1 Soit un élément de Sn . Introduisons « de force » les termes de cette somme qui se simplifient sous forme d'une suite télescopique : |m(1)1 . . . m(n)n - r(1)1 . . . r(n)n | = m(1)1 . . . m(n)n + n-1 P m(1)1 . . . m(j)j r(j+1)(j+1) . . . r(n)n j=1 - r(1)1 . . . r(n)n - n P m(1)1 . . . m(j-1)(j-1) r(j)j . . . r(n)n j=2 = n P m(1)1 . . . m(j-1)(j-1) m(j)j r(j+1)(j+1) . . . r(n)n j=1 - n P m(1)1 . . . m(j-1)(j-1) r(j)j r(j+1)(j+1) . . . r(n)n j=1 = 6 n P m(1)1 . . . m(j-1)(j-1) (m(j)j - r(j)j ) r(j+1)(j+1) . . . r(n)n j=1 n P |m(1)1 . . . m(j-1)(j-1) (m(j)j - r(j)j ) r(j+1)(j+1) . . . r(n)n | j=1 Rappelons que, suivant la convention posée par l'énoncé, les termes en j - 1 pour j = 1 et j + 1 pour j = n sont égaux à 1 pour que les sommations aient toujours du sens. Par le même argument qu'à la question précédente, on en déduit que n P |m(1)1 . . . m(n)n - r(1)1 . . . r(n)n | 6 km1 k . . . kmj-1 kkmj - rj kkrj+1 k . . . krn k j=1 Au final, après sommation sur Sn , on obtient bien la relation cherchée, à savoir |per(m1 , . . . , mn ) - per(r1 , . . . , rn )| 6 n! n P km1 k . . . kmj-1 kkmj - rj kkrj+1 k . . . krn k j=1 Cette question était très technique et, comme pour toutes les questions du problème, le résultat était donné. Le rapport du jury signale « beaucoup de tentatives de bluff ». C'est une attitude dangereuse, surtout ici : si l'argument incontournable de série télescopique n'est pas mentionné, il est à peu près certain que la démonstration est une escroquerie, et le correcteur considérera dans la suite tout raisonnement vague comme du bluff. 3 On a admis que l'application per est symétrique par rapport aux colonnes : il suffit donc de faire la démonstration par rapport à la première. Décomposons-la en 0 m11 m11 0 0 0 .. 0 0 m21 0 m21 . .. . . . + · · ·+ ... . m m1 = + = .. + .. + · · · + i1 . . . m(n-1)1 0 0 . m 0 . (n-1)1 mn1 0 0 0 m n1 0