X Maths 2 MP 2000

Thème de l'épreuve Étude des combinaisons linéaires à coefficients positifs
Principaux outils utilisés algèbre linéaire, espaces euclidiens, topologie

Corrigé

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

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE FILIÈRE MP CONCOURS D'ADMISSION 2000 DEUXIÈME COMPOSITION DE MATHÉMATIQUES (Durée : 4 heures) L'utilisation des calculatrices n'est pas autorisée pour cette épreuve. *** On attache... la plus grande importance à la clarté, a la précision et a la conciston de la rédaction. *** Ce problème a pour objet l'étude de certains cônes dans des espaces euclidiens. On désigne par E l'espace euclidien R"(n Z 1), par (.l.) son produit scalaire usuel, et par H." la norme associée. Pour toute partie X de E , on note X * (resp. X +) l'ensemble des éléments 3: de E satisfaisant (m'y) : O (resp. (Æ|y) Z 0) pour tout y de X. Une partie C' de E sera appelée cône à faces s'il existe une famille finie d'éléments T c17... ,cT (r > O) de E telle que C soit l'ensemble des combinaisons linéaires ZÀici avec i=1 /\1, . .. ,/\T 2 0. On supposera toujours les ci non nuls, et on dira qu'ils engendrent C. Enfin on appelle face de C toute partie de C de la forme C' 0 {w}l avec M EUR C+. La première partie est indépendante des suivantes. Première partie 1. Vérifier que tout sous-espace vectoriel non nul de E est un cône à faces. 2. Supposant n = 7" = 2, décrire (sans démonstration mais avec des figures) les ensembles C, C+ et donner sous chaque figure la liste des faces de C suivant les diverses positions relatives de c1 et 02. 3. Supposant que n = 7" = 3 et que (c1,c2,03) est une base orthogonale de E7 décrire sans démonstration C7 C+ et les faces de C . Deuxième partie On se propose, dans cette partie, de démontrer que tout cône à faces est fermé dans E. 4.a) Soit K une partie compacte de E ne contenant pas 0. Montrer que l'ensemble des éléments de la forme Àoe, où A G R+ et 117 E K , est fermé dans E. b) Ce résultat subsiste-t--il si l'on suppose K seulement fermé, ou si K, compact, contient 0 ? 5. On considère maintenant un cône à faces C engendré par des éléments c1, . .. ,cT. &) Montrer que C' est fermé lorsqu'il ne contient aucune droite vectorielle. [On pourra T' T' introduire l'ensemble K des éléments 2 /\iCi avec Ài EUR R+ et z Ài : l.] i:1 i=1 b) Soit V un sous--espace vectoriel de E (éventuellement réduit à 0) contenu dans C et distinct de C . On note P le projecteur orthogonal de E sur VL. Vérifier que P(C) est un cône à faces contenu dans C. c) Supposant que P(C) contient une droite vectorielle, construire un sous--espace vectoriel de E contenu dans C et contenant strictement V. d) Montrer que C est fermé dans E. Troisième partie 6. On se propose ici de démontrer que tout cône à faces C vérifie (C+)+ : C. &) Soit (L un élément de E. Montrer que la fonction réelle définie sur C par c »--> ||c -- a|| atteint sa borne inférieure en un point unique de C . On le notera p(a). b) Déterminer le signe de (p(a) -- ale) lorsque 0 E C, ainsi que la valeur de (p(a) -- a|p(a)). c) Conclure. Quatrième partie On souhaite maintenant démontrer que tout cône à faces est l'intersection d'une famille finie de demi--espaces fermés (on appelle demi-espace fermé tout sous--ensemble de E de la forme {a}+ avecaEUR E, a;£0). 7. Démontrer l'équivalence des conditions suivantes relatives à un cône à faces C : (a) le sous-espace vectoriel de E engendré par C est égal à E; (B) l'intérieur de C est non vide. 8. On suppose dans cette question les conditions de la question 7. satisfaites pour un cône à faces C . a) Démontrer l'équivalence des conditions suivantes relatives à un élément a: de C : (ON) x est un point frontière de C; (fi') ac appartient à une face de C distincte de C . b) Que subsisterait--il de ce résultat si l'on ne supposait pas satisfaites les conditions de la question 7. ? EUR) Soit &: un point de E n'appartenant pas à C . Construire une face F de C, distincte de C et ayant la propriété suivante : pour tout 11) EUR C'+ tel que F = C D {w}l, on a (æ|w) < 0. [On pourra considérer le segment de droite joignant a: a un point mo de l'intérieur de C]. 9.3) Montrer que l'ensemble des faces d'un cône à faces est fini. b) Montrer que tout cône à faces est l'intersection d'une famille finie de demi--espaces fermés. 10. Déduire de ce qui précède que, si C est un cône à faces, il en est de même de C+.

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


 X Maths 2 MP 2000 -- Corrigé Ce corrigé est proposé par Francesco Colonna-Romano (ENS Ulm) et Sébastien Desreux (ENS Ulm) ; il a été relu par Serge Bellaïche (ENS Ulm) et Éric Ricard (ENS Ulm). Ce sujet s'intéresse aux combinaisons linéaires d'une famille finie de vecteurs lorsqu'on impose aux coefficients d'être positifs. Les ensembles obtenus ressemblent à des « cônes » présentant des faces (et appelés pour cette raison « cônes à faces »), dont on étudie certaines propriétés géométriques et topologiques. Les connaissances requises sont assez élémentaires ; elles concernent les espaces euclidiens et la topologie des espaces vectoriels normés. Une bonne connaissance de la géométrie permettra une approche intuitive des questions difficiles, mais la rédaction doit être très rigoureuse, en particulier dans les questions de topologie. La difficulté du sujet est nettement progressive. Si les deux premières parties sont relativement simples, la fin se révèle plutôt ardue, avec des questions délicates dont la rédaction est de surcroît longue. Le problème se compose de quatre parties, qui ne sont pas indépendantes, mais dont on peut sans peine admettre le résultat final qui, seul, servira dans les parties suivantes. La première partie traite simplement quelques exemples afin de se familiariser avec les définitions ; la deuxième montre qu'un cône à faces est fermé ; la troisième associe à chaque cône un ensemble dual C+ (appelé polaire) vérifiant (C+ )+ = C ; la quatrième enfin montre qu'un cône à faces est l'intersection d'une famille finie de demi-espaces, ce qui permet de conclure que C+ est lui-même un cône. Indications 4.a Utiliser la caractérisation d'un fermé par des suites. 5.a Appliquer le résultat de la question 4.a après avoir montré que K est compact et ne contient pas 0. 5.b Montrer que P(C) est le cône à faces engendré par les P(ci ) et que ces derniers sont dans C. 5.c On pourra considérer V = V+D, où D est la droite vectorielle que contient P(C). 5.d Utiliser la question 5.c pour se ramener au cas où P(C) ne contient pas de droites vectorielles, puis déduire des questions 5.a et 5.b que P(C) est fermé, et enfin remarquer que C est l'image réciproque du fermé P(C) par P. 6.a Utiliser un argument de compacité pour l'existence et l'identité du parallélogramme : kx + yk2 + kx - yk2 = 2(kxk2 + kyk2 ) pour l'unicité. 6.b Paramétrer le segment ] c ; p(a) ] (où c C) par l'application t 7- tc + (1 - t)p(a) Constater que chaque point du segment est plus éloigné de a que p(a) lui-même et particulariser au cas c = (1 + )p(a). 6.c Pour prouver que (C+ )+ C, montrer que si a (C+ )+ alors a = p(a) en remarquant que (p(a) - a) C+ d'après la question 6.b. 7 Pour montrer () = (), construire explicitement une base de E composée de vecteurs de C, à partir d'une base de E et d'un point x intérieur à C. Pour montrer () = (), contruire le point intérieur à C comme un point ayant toutes ses coordonnées strictement positives dans une base de E composée de vecteurs de C. 8.a Pour montrer que ( ) = ( ), constater que si x C {w} alors la boule B(x, ) contient le vecteur x - w/kwk , qui n'est pas dans C. Pour montrer ( ) = ( ), raisonner par contraposée. En prenant un x ne vérifiant pas ( ), montrer qu'il existe un réel mx tel que w C+ = (x|w) > mx kwk (On peut montrer que C+ est fermé et se restreindre au cas où w est de norme 1.) Démontrer ensuite que la boule de centre x et de rayon mx est contenue dans C. 8.c Construire un point frontière de C sur le segment [ x ; x0 ] , puis appliquer la question 8.a. 9.a Montrer que toute face est un cône à faces engendré par un nombre fini de ci . 9.b Considérer l'intersection des demi-espaces wi + où les wi servent à définir les faces. Supposer d'abord que les conditions de la question 7 sont réalisées, et s'y ramener dans le cas contraire. On aura besoin des questions 8.c et 9.a . 10 Montrer que C+ est le cône engendré par les vecteurs définissant les demi-espaces de la question 9.b. On pourra utiliser la relation (C+ )+ = C. Première partie 1 Soit F un sous-espace vectoriel de E de dimension m, et soit (c1 , . . . , cm ) une base de F. On pose cm+i = -ci pour i [[ 1 ; m ]]. On vérifie alors que F est le cône à faces engendré par (c1 , . . . , c2m ). En effet, toute combinaison linéaire positive de c1 , . . . , c2m étant une combinaison des c1 , . . . , cm , elle est dans F. Réciproquement, tout x F s'écrit x= m P 1 i ci = P P i ci + i >0 |i |cm+i i 60 donc x est dans le cône engendré par les ci . Finalement, on a montré le résultat suivant : Tout sous-espace vectoriel de E est un cône à faces. 2 Lorsque n = r = 2, il faut distinguer trois cas. Ce sont bien les seuls cas à envisager car les ci ne sont pas nuls par hypothèse. a) c1 et c2 sont colinéaires et de même sens C+ C est alors la demi-droite dirigée par c1 ou c2 (c'est en fait le cône engendré par c1 seul). C+ est le demiplan contenant C défini par {w E1 | (w|c1 ) > 0} 1 C 1 C Les faces de C sont {0} (par exemple pour w = c1 ) et C entier (pour w c1 ). b) c1 et c2 sont colinéaires et de sens opposé C+ Ici C est la droite contenant c1 et c2 , C+ est la perpendiculaire à C passant par O, et la seule face de C est C entier. 2 c) Enfin, il y a le cas non dégénéré où c1 et c2 ne sont pas colinéaires. On peut faire plusieurs types de dessins, suivant que l'angle entre c1 et c2 est aigu ou obtus. 2 C 1 2 C = C+ 2 C+ 1 C+ 1 C Ici les faces sont C entier (pour w = 0), {0} (pour w à l'intérieur de C+ ) et les demi-droites R+ c1 et R+ c2 (pour w sur la frontière de C+ ). 3 Si n = r = 3, et si (c1 , c2 , c3 ) forme une base orthogonale de E, alors C est la portion d'espace (c'est un huitième d'espace) définie par x > 0, y > 0 et z > 0. De plus, par définition de C+ , le produit scalaire d'un élément w de C+ avec les ci (c'est-à-dire ses coordonnées dans la base (c1 , c2 , c3 )) est positif, donc c C : C+ C. Réciproquement, si x C, on voit que son produit scalaire avec un élément de C est positif : C C+ . En conclusion, C = C+ . Les faces de C sont maintenant : ­ C entier (pour w = 0) ; ­ {0} (par exemple pour w = 1 c1 + 2 c2 + 3 c3 avec tous les i non nuls) ; ­ les quarts de plan engendrés par deux des ci (du type R+ ci + R+ cj ), qui sont obtenus pour w {c1 , c2 , c3 } ; ­ et enfin les demi-droites engendrées par un seul ci (obtenues par exemple pour w = 1 c1 + 2 c2 , avec 1 et 2 tous deux non nuls).