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).