X/ENS Maths A MP 2016

Thème de l'épreuve Étude de simplexes en dimension n
Principaux outils utilisés matrices, déterminant, géométrie affine, convexité, pgcd
Mots clefs GL(n, Z), matrices de transvection, barycentres, ensembles convexes, simplexes

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


ÉCOLE POLYTECHNIQUE -- ECOLES NORMALES SUPÉRIEURES CONCOURS D'ADMISSION 2016 FILIÈRE MP COMPOSITION DE MATHÉMATIQUES -- A -- (XLCR) (Durée : 4 heures) L'utilisation des calculatrices n'est pas autorisée pour cette épreuve. *** Toute afiirmation doit être clairement et complètement justifiée. Soit n> 1 un entier. On appelle point entier de R" un point dont toutes les coordonnées sont entières, c 'est-- a--dire un point de Z". Si IC est une partie de R", on note IC son intérieur. On appelle points entiers de IC (resp. points entiers intérieurs) les points de IC fi Z" (resp. les points de IC fi Z"). On note respectivement Card(IC @ Z") et Card(IC 0 Z"), le nombre (éventuellement infini) de points entiers de IC et de son intérieur IC. Soit h5 l'homothétie de rapport O E R (centrée en 0), on note BIC : h3(IC) l'image de IC par h5. Si Tæ est la translation de vecteur &: E R'", on note IC --- a: : T_oe(IC) l'image de IC par T_oe. Si M : (mig-) est une matrice de M...,(R), m,;j est le coefficient de la i--ème ligne et de la j--ème colonne. On note (æ1| -- - - la,) la matrice de M,,(R) dont les colonnes sont les vecteurs æ1, . . . ,oen E R". On note I,, la matrice identité de M,,(R) et E,;j la matrice de M,, (R) dont tous les coefficients sont nuls sauf celui de la 7Z--ème ligne et j--ème colonne qui vaut 1. On note Mn (Z) l'ensemble des matrices de M,,(R) dont tous les coefficients sont entiers. On note LaJ la partie entière d'un réel & : c'est le plus grand entier inférieur ou égal à a; et {a} = a---- La) E [O, 1[ la partie fractionnaire de a.. On note )aL le plus grand entier strictement inférieur à a. On rappelle que des entiers al, . . . , ak, non tous nuls sont dits premiers entre eux dans leur ensemble si pgcd(a1, . . . ,ak) = 1. Première partie 1. Soit M EUR M,,(R) une matrice inversible et à coefficients entiers. la. Montrer que M _1 est à coefficients rationnels. 1b. Montrer l'équivalence des pr0positions suivantes : i) M "1 est à coefficients entiers. ii) detM vaut 1 ou --1. Dans la suite, on note GLn(Z) l'ensemble des matrices carrées de taille n à coefficients entiers et de déterminant il. C'est un sous--groupe de GLn(R). On remarque que pour t' # j et e E Z, la matrice I,, + CE,-j appartient a GLn (Z). 2. Soit M = (:... . . -- p.,) EUR GL,,(R). 2a. Montrer que M EUR GLn(Z) si et seulement si M (Zn) : Z". 2b. Montrer l'équivalence des propositions suivantes : i) M & GLn(Z). 'ÏL ii) Les points entiers du parallélépipède ? = {thoez ! Vi EUR {1,. . . ,n}, t.; E [0,1]} sont 73=1 TL exactement les 2" points Eat-wi, où ei EUR {0,1} pour tout i E {1,. . . ,n}. i=1 3. Pour tout oz dans R et pour tous entiers i et j distincts compris entre 1 et n, décrire l'effet sur une matrice carrée M de taille n de la multiplication a gauche par In +Oinj. Même question pour la multiplication à droite. 4. Soient al, . . . ,an des entiers non tous nuls. Le but de cette question est de montrer qu'il existe une matrice de Mn (Z) dont la première colonne est (al, . . . ,a") et de déterminant pgcd(a1, . . . ,un). Pour cela on raisonne par récurrence sur n. Soit N E Mn_1(Z) une matrice dont la première colonne est (dg, . . . ,on). Étant donnés u, U EUR @, on considère la matrice 4a. Exprimer det M en fonction de det N , u et @. 4b. On suppose que les @, . . . ,an sont non tous nuls et que detN = pgcd(a2, . . . ,on). Montrer que l'on peut choisir u, v de sorte que M réponde à. la question. Oonclure. 5. Soit M EUR Mn(Z), de déterminant non nul. On souhaite montrer qu'il existe une matrice A dans GLn(Z) telle que MA soit triangulaire supérieure et en notant MA = (cz-j), on ait l'inégalité 0 < cij < Cii pour tous z',j EUR {1, . . . ,n} tels que i < j. 5a. On note M : (oe1| -- - - |oen). Soient oe'1, . . . ,oeÇ. les éléments de Z"_1 obtenus en prenant les (n ---- 1) dernières coordonnées de 331, . . . ,a:n. n Montrer qu'il existe a1, . . . ,an dans @, non tous nuls, tels que E ai 332 = 0. Montrer que l'on i=1 peut choisir les 0..- entiers et premiers entre eux dans leur ensemble. 5.,b' Montrer qu'il existe une matrice A1 dans GLñ(Z) telle que la première colonne de C = M A1 ait tout ses coefficients êi1 nuls sauf le premier 611 que l'on peut prendre strictement positif. 5c. En considérant pour tout j = 2, . . . ,n la division euclidienne 61j = qj511 +73, 0 < 73 < 611, montrer que l'on peut supposer 611 > E1j, quitte à changer A1. 5d. Oonclure par récurrence. 6. Soit M EUR Mn(Z), de déterminant non nul. Montrer qu'il existe une matrice A dans GLn(Z) telle que AM soit triangulaire inférieure et en notant AM = (cz-j), on ait l'inégalité 0 < cij < 011 pour tous i,j EUR {1,...,n} tels quej < 75. Deuxième partie Soient 30,31, . . . 7sn des points de R" tels que les vecteurs 31 -- sg, 52 -- so, . . . ,sn -- so soient linéairement indépendants. On appelle simpleæe de sommets 30,31, . . . ,sn l'ensemble : 'ÏL TL S= {thslei=1,....,n, t. 20, Zt.=} i=0 i=0 'n n ={SO+ZÉz(Sz--SO)IVZ= , ,n,tz>O,th<1} i=1 Z=1 Si de plus les si sont tous des points entiers, on dit que S est un simplexe entier. On définit le volume du simplexe 8 de sommets 80,81, . . . , sn par 1 Vol(8) := 7--1--'| det(31 -- so, 32 -- so, . . . ,sn ---- S())l. 7. Soit 8 le simplexe de sommets 30,31, . . . ,sn. 7 a. Montrer S est un compact convexe de R'". . " n 71). Montrer que 8 = {ztfit |Vi = 1,...,n, tz-- > O, Zti = 1}. i=0 i=0 En déduire que si 0 E 8, alors, pour tout À E [0,1[, ÀS C 8 . 7c. Pour i = O, . . . ,n, on note 5. = (1,si) le point de Rn+1 dont les coordonnées sont 1 suivi des coordonnées de si. Exprimer | det(â07 sl, . . . ,à")! en fonction de Vol(8 ) En déduire que le volume d'un simplexe ne dépend pas de l'ordre des sommets. 8. Soit V > 0 un réel. 8a. Donner un exemple de simplexe entier de R2, de volume supérieur ou égal à. V, et n'ayant aucun point intérieur entier. 8b. Donner un exemple de simplexe entier de R3, de volume supérieur ou égal à V, et dont les seuls points entiers sont les sommets. 9. Soit IC un compact convexe de R" tel que 0 EUR IC. 9a. Montrer que l'ensemble des À 2 0 tels que --ÀIC C IC est un intervalle. On note a(IC) = sup{À ; OI ---- ÀIC C IC}. 9b. Montrer que a(IC) < 00 et que a(IC) = max{À > O] --ÀIC C IC}. 9c. _ Montrer que 0 < a(IC) < 1. En déduire que a(IC) = 1 si et seulement si IC est symétrique par rapport a 0. On admettra le résultat suivant que l'on pourra utiliser sans démonstration pour la suite du problème. Théorème 1. Soit 8 un simpleæe de R" et le un entier. Si Vol(S) ; k, il eæiste Ic + 1 points distincts oO, . . . ,vk de 8 tels que o.; -- Uj EUR Z" quels que soient i et j entre 0 et k. 10. Dans toute cette question, 8 est un simplexe de R" tel que 0 EUR 8 . On veut montrer c...@...Zn).2J...(Æpÿp. On pose alors a = a(S), et k = JVOI(S) (@ î 1)n { 103. Exprimer, pour fl E R et oe E R'", Vol(fi5) et Vol(S -- 33). Montrer que pour A E [0,1] suffisamment proche de 1, Vol ( Au 8) > le. a + 1 . . . . Àa , . 10b. Soeent u0, . . . ,uk les le + 1 pomts d1stmcts dans + 18 ver1fiant ui -- uj EUR Z" pour a . . , - ; / \ ' ('Ui _ vj)a tous i, 3, dont lex1stence est assuree par le Theoreme 1. Montrer que les pomts ----+--1-- @ Àa .. sont dans + 18 . En déduire que les v.- ---- uj sont dans S . a. 10EUR. Montrer qu'il existe un indice j E {O, . . . ,le} tels que les (27EUR + 1) points 0, i(ui -- uj), pour i E {O, . . . ,k} \ {j} soient distincts. En déduire l'énoncé de la question 10, puis que 2 Troisième partie Oard(Ë o Z") ; v01(5) ("(S) ) n . On dit que deux simplexes 8 et S' de R" sont équivalents s'il existe un ordre d'énumération des sommets 30,31, . . . , sn de S, et 36, s'1, . . . ,s.'n de S', et une matrice A de GLn(Z) tels que A(si -- so) = 3,2- -- 56 pour tout i = 1,...,n. 11. Montrer que deux simplexes entiers S et S' sont équivalents si et seulement s'il existe une matrice A E GLn(Z) et un vecteur I) E Z" tels que S' = A(8 ) -- b. 12. Montrer que le volume, le nombre de points entiers et le nombre de points intérieurs entiers sont les mêmes pour deux simplexes entiers équivalents. 13. Soit 8 un simplexe entier. Montrer qu'il existe des entiers ci > 0 pour i = 1, . . . ,n, et un simplexe S' équivalent à 8, tels que 5' C HÎ=1[O,C1] et que TL H c.-- = n! Vol(S). i=1 On pourra utiliser la. question 6 pour une matrice M bien choisie. 14. Montrer qu'un simplexe entier 8 est équivalent à. un simplexe contenu dans le cube [O, n! Vol(S)]". On admet le résultat suivant que l'on pourra utiliser sans démonstration. Théorème 2. Pour tout entier strictement positif le, il existe une constante strictement positive C(n, le) telle que pour tout simpleoee entier 8 de R" possédant eæactement le points intérieurs entiers, Vol(S) < C(n, k:). 15. Déduire du Théorème 2 que pour tout entier strictement positif le, il n'existe a équiva-- lence près qu'un nombre fini de simplexes entiers de R." ayant exactement le points intérieurs. * >I< *

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


 X/ENS Maths A MP 2016 -- Corrigé Ce corrigé est proposé par Tristan Poullaouec (Professeur en CPGE) ; il a été relu par Émilie Liboz (Professeur en CPGE) et Benjamin Monmege (Enseignantchercheur à l'université). Ce problème étudie les simplexes à coordonnées entières de Rn , qui généralisent les triangles et tétraèdres en dimension supérieure. Ces objets géométriques sont notamment utilisés en optimisation linéaire. L'énoncé est constitué de trois parties mêlant algèbre linéaire et géométrie affine ; les deux premières sont indépendantes. · La première partie porte sur les matrices à coefficients entiers. On prouve que l'on peut, après multiplication par une matrice de GLn (Z), transformer toute matrice inversible à coefficients entiers positifs en une matrice triangulaire inférieure à coefficients entiers positifs telle que, dans chaque colonne, le terme diagonal soit le plus grand coefficient. La démarche employée n'est pas sans rappeler l'algorithme du pivot de Gauss. · La deuxième partie se consacre à l'étude des simplexes entiers de Rn . Ce sont les polyèdres de Rn engendrés par n + 1 points entiers tels que les n vecteurs reliant l'un des points aux autres soient linéairement indépendants. Après avoir établi quelques propriétés générales, on minore le nombre de points entiers à l'intérieur d'un tel simplexe à l'aide de son volume. · Dans la troisième partie, on démontre qu'il n'existe, à une bijection près, qu'un nombre fini de simplexes entiers ayant un nombre fixé de points entiers dans son intérieur. Le problème est d'une longueur raisonnable et ne manque pas d'intérêt. Hormis une ou deux propriétés géométriquement évidentes mais délicates à justifier proprement, il ne présente pas de difficulté technique ou conceptuelle majeure. Notons que l'on admet deux théorèmes assez puissants pour démontrer les résultats essentiels, ce qui rend la démarche quelque peu frustrante. Enfin, l'énoncé n'est pas exempt de défauts : il comporte plusieurs fautes d'orthographe, des imprécisions et manques de rigueur ; surtout, deux erreurs grossières ont certainement déstabilisé les candidats. Indications Première partie 1.a Penser à faire intervenir la comatrice de M. 2.a Utiliser la question 1.b. Pour montrer que M GLn (Z), on pourra considérer l'image de la base canonique de Rn par M et M-1 . 2.b Il est plus simple de montrer que la propriété ii) équivaut à M(Zn ) = Zn . 4.b Exprimer pgcd (a1 , . . . , an ) en fonction de a1 et de pgcd (a2 , . . . , an ), puis utiliser le résultat de la question précédente. 5.b Prendre une des matrices dont l'existence est assurée par la question 4. 5.c Se servir du résultat de la question 3. 6 L'énoncé comporte une erreur : la condition sur les coefficients cij est en fait 0 6 cij < cjj pour 1 6 j < i 6 n. Deuxième partie 7.a Pour la compacité, il suffit de vérifier que S est l'image d'un compact de Rn par une application continue. 7.b Il est plus simple de montrer que S est égal à n n P P S = s0 + ti (si - s0 ) i [[ 1 ; n ]], ti > 0 et ti < 1 i=1 8.a 8.b 9.a 9.b 9.c 10.a 10.b 10.c i=1 Commencer par établir que cet ensemble est ouvert, en utilisant la réciproque de l'application rencontrée dans la question 7.a. Vérifier ensuite que les points de S\S ne sont pas des points intérieurs de S. Prendre un triangle rectangle compris entre les droites d'équations respectives x = 0 et x = 1, par exemple. On peut chercher un tétraèdre compris entre les plans d'équations respectives z = 0, z = 1, x = 0 et x = 1. Ne pas oublier que les intervalles sont les parties convexes de R. Comme 0 K, l'ensemble K contient une boule ouverte B(0, ) pour un > 0. En particulier, K contient un élément non nul. Considérer un élément de K de norme maximale. Pour la seconde partie de la question, on pourra s'intéresser à la limite de la a quantité Vol S lorsque tend vers 1. a+1 (vi - vj )a Exprimer comme barycentre de vi et -avj . a+1 Montrer que la négation de la propriété conduit à l'alignement de trois points de même norme. Troisième partie 12 Montrer que l'application : x 7- Ax - b est bijective et que (Zn ) = Zn en utilisant la question 2.a. 13 L'énoncé comporte une erreur, il faut seulement prouver que S [ 0 ; cmax ] n , où cmax = max {c1 , . . . , cn }. Pour cela, appliquer le résultat de la question 6 à la matrice (s1 - s0 | · · · |sn - s0 ) et considérer le simplexe S = A(S) - As0 . Première partie 1.a Notons Com(M) la comatrice de M ; comme M est inversible, son déterminant est non nul et l'on a M-1 = t Com(M) / det(M) Le déterminant des matrices carrées d'ordre n est un polynôme à n2 indéterminées sur Z. Puisque la matrice M est à coefficients entiers, det(M) est aussi un entier. De même, tous les déterminants extraits de M sont des entiers, donc Com(M) est à coefficients entiers. Ceci entraîne que Les coefficients de la matrice M-1 sont rationnels. 1.b Procédons par double implication. · Supposons que la propriété i) est vraie. La matrice M-1 possède des coefficients entiers, donc det(M-1 ) Z en utilisant l'argument de la question 1.a. Pour la même raison, det(M) Z. Or, det(M) × det(M-1 ) = det M M-1 = det(In ) = 1 donc les deux entiers det(M) et det(M-1 ) ont pour produit 1. Ceci signifie qu'ils sont simultanément égaux à 1 ou à -1. Ainsi, la propriété ii) est vraie. En effet, les seuls entiers admettant un inverse entier sont 1 et -1. · Réciproquement, supposons que la propriété ii) est vraie. Comme det(M) = + - 1, t la matrice M-1 = + - Com(M) est alors à coefficients entiers. Ainsi, M-1 Mn (Z) det(M) {-1; 1} 2.a Prouvons dans un premier temps que si la matrice M appartient à GLn (Z), alors M(Zn ) = Zn . Dans cette question, M(Zn ) désigne implicitement {MX | X Zn }. Supposons donc que la matrice M appartient à GLn (Z). En particulier, elle est à coefficients entiers d'où X Zn MX Zn Ceci prouve que M(Zn ) Zn . De même, M-1 est à coefficients entiers d'après la question 1.b, donc Y Zn X = M-1 Y Zn soit Y Zn X Zn Y = MX Ceci montre que Z M(Z ). De ce fait, M(Z ) = Zn . Prouvons maintenant l'implication réciproque. Supposons donc que M(Zn ) = Zn . Notons (e1 , e2 , . . . , en ) la base canonique de Rn : comme ei Zn , on a Mei Zn pour tout i [[ 1 ; n ]]. Autrement dit, les colonnes de la matrice M appartiennent toutes à Zn , si bien que M est à coefficients entiers. La matrice M étant de plus inversible, la relation M(Zn ) = Zn conduit alors à M-1 (Zn ) = Zn . Le même raisonnement permet ainsi d'établir que M-1 est à coefficients entiers. On déduit enfin de la question 1.b que det(M) = + - 1, ce qui entraîne que M GLn (Z). Par conséquent, n n M GLn (Z) n M(Zn ) = Zn 2.b Grâce à la question 2.a, montrer l'équivalence des propriétés i) et ii) revient à montrer que la propriété ii) équivaut à M(Zn ) = Zn . Supposons que M(Zn ) = Zn . Pour tout vecteur colonne T = (t1 , t2 , . . . , tn ) de Rn , n P on a ti xi = MT car les xi sont les vecteurs colonne de la matrice M. De ce fait, i=1 P = {MT | T [[ 0 ; 1 ]]n }. Pour un tel vecteur T [[ 0 ; 1 ]]n , on a MT Zn MT Zn MT M(Zn ) MT = MX avec X Zn T = X Zn car M est inversible n T {0, 1} Les seuls points entiers de P sont donc les n P i xi , avec i {0, 1} pour tout i=1 i [[ 1 ; n ]]. Ceci signifie que la propriété ii) est vraie. Supposons maintenant que la propriété ii) est vraie. Par conséquent, les n P i xi , i=1 où i {0, 1} pour tout i [[ 1 ; n ]], sont des points entiers. En particulier, xi Zn pour tout i [[ 1 ; n ]]. Les vecteurs colonne de la matrice M sont ainsi à coefficients entiers, ce qui prouve que M Mn (Z). Il s'ensuit que M(Zn ) Zn . Pour montrer l'inclusion réciproque, raisonnons par l'absurde et supposons qu'il existe un vecteur Y Zn tel que Y / M(Zn ). La matrice M étant inversible, on -1 peut définir le vecteur X = M Y, qui vérifie alors Y = MX et X / Zn . Notons X1 le vecteur obtenu en prenant les parties entières des coordonnées du vecteur X et X2 = X - X1 . On a ainsi X1 Zn et X2 [ 0 ; 1 [ n . · Si X2 Zn , on a X = X1 + X2 Zn . Comme X / Zn , on en déduit par n contraposée que X2 /Z . · De plus, comme M est dans Mn (Z), on a MX2 = M(X - X1 ) = MX - MX1 = Y - MX1 Zn Ceci contredit la propriété ii) puisque MX2 est un point entier de P tandis que X2 n'est pas entier. On a ainsi prouvé par l'absurde l'inclusion réciproque Zn M(Zn ). En conclusion, M GLn (Z) si, et seulement si, les points entiers du parallén P lépipède P = i xi | i [[ 1 ; n ]], ti [ 0 ; 1 ] sont exactei=1 ment les 2n points n P i xi , où i {0, 1} pour tout i [[ 1 ; n ]]. i=1 3 D'après le cours, La multiplication à gauche d'une matrice par la matrice de transvection Tij () = In + Eij remplace sa ligne Li par Li + Lj et laisse les autres lignes inchangées. La multiplication à droite remplace sa colonne Cj par Cj + Ci et laisse les autres colonnes inchangées. Ce résultat de première année se retrouve aisément à l'aide de la définition du produit matriciel. Notons M = (mk ) et Tij () = (tk ) Mn (R). On a tk = k + ik j en utilisant le symbole de Kronecker. Posons alors