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