X/ENS Maths PC 2018

Thème de l'épreuve Étude de matrices à coefficients dans {-1,1}
Principaux outils utilisés algèbre linéaire, probabilités, analyse, combinatoire
Mots clefs matrice, rang, inégalité de Hoeffding

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 ­ ÉCOLES NORMALES SUPÉRIEURES
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

FILIÈRE

CONCOURS D'ADMISSION 2018

PC

COMPOSITION DE MATHÉMATIQUES ­ (XEULC)
(Durée : 4 heures)

L'utilisation de calculatrices n'est pas autorisée pour cette épreuve.
Toute affirmation doit être clairement et complètement justifiée.

Ce sujet s'intéresse aux matrices carrées de taille n dont tous les 
coefficients sont égaux à 1
ou à -1, et en particulier à la différence maximale entre le nombre de 1 et le 
nombre de -1 que
l'on peut obtenir, si l'on s'autorise à multiplier certaines lignes et colonnes 
d'une telle matrice
par -1.
La partie I s'intéresse à quelques cas particuliers. La partie II montre que 
pour certaines
matrices, cette différence maximale est beaucoup plus petite que n2 . La partie 
III propose au
contraire un minorant à cette différence maximale. La partie IV propose une 
démonstration de la
formule de Stirling utilisée dans la partie III, et rappelée ci-dessous. Enfin, 
la partie V s'intéresse
à la différence minimale entre le nombre de 1 et le nombre de -1.
Les quatre premières parties sont largement indépendantes.

Rappels
La formule de Stirling énonce un équivalent à n!, à savoir
 n n

.
2n
n! 
n
e
On admet par ailleurs la valeur de l'intégrale de Gauss
Z +

x2
e- 2 dx = 2 .
-

Notations
Pour n et k entiers strictement positifs, on notera Mn,k (R) l'espace vectoriel 
des matrices
réelles à n lignes et k colonnes. On notera également Mn (R) = Mn,n (R) 
l'espace vectoriel des
1

matrices carrées de taille n. On notera tM la transposée d'une matrice M  Mn,k 
(R). On identifiera l'espace vectoriel Rn à l'espace vectoriel Mn,1 (R) des 
matrices colonnes à n coordonnées.
En particulier, l'espace vectoriel des nombres réels est identifié à M1 (R).
On étend les notations précédentes aux parties de R : si K est une partie de R, 
on notera par
exemple Mn,k (K) le sous-ensemble de Mn,k (R) constituée des matrices dont tous 
les coefficients
sont à valeurs dans K. Le sujet s'intéressera tout particulièrement à Mn ({-1, 
1}), l'ensemble des
matrices carrées de taille n dont tous les coefficients sont égaux à 1 ou à -1. 
Si A  Mn ({-1, 1}),
on notera
t
XAY | (X, Y )  ({-1, 1}n )2 ,

S(A) :=

M (A) := max S(A).
Pour n > 1, on notera également

M (n) := min {M (A), A  Mn ({-1, 1})} .
Dans tout le sujet, (, A, P) désigne un espace probabilisé sur lequel seront 
définies les différentes variables aléatoires intervenant dans les parties II 
et III. On admettra que toutes les
variables aléatoires introduites peuvent bien être construites sur cet espace. 
On notera P(E) la
probabilité d'un événement E  , et E[X] l'espérance d'une variable aléatoire X 
sur (, A, P)
à valeurs réelles.

Partie I
1. Quel est le cardinal de Mn ({-1, 1}) ? Cet ensemble est-il un sous espace 
vectoriel de
Mn (R) ?
2. Montrer que pour toute matrice A dans Mn ({-1, 1}), l'ensemble S(A) est 
inclus dans
{-n2 , . . . , n2 }. Montrer que l'inclusion est stricte (on pourra penser à un 
argument de
parité), et montrer que S(A) est un ensemble symétrique, au sens où un entier k 
est dans
S(A) si et seulement si -k est dans S(A).
3. Soit A et B dans Mn ({-1, 1}). On suppose qu'il existe des matrices 
diagonales C et D
ne contenant que des 1 et des -1 sur la diagonale, telles que B = CAD. Montrer 
que
S(A) = S(B).
4. Dans cette question seulement, on suppose n = 2, et on note
I=

1 1
1 1

et

J=

1 1
.
1 -1

Calculer S(I) et S(J), et en déduire S(A) pour tout A  M2 ({-1, 1}).
5. Soit A  Mn ({-1, 1}). Montrer que les affirmations suivantes sont 
équivalentes :
(a) n2  S(A).
(b) Il existe X et Y dans {-1, 1}n tels que A = X t Y .
(c) A est une matrice de rang 1.
6. En déduire la proportion, parmi les matrices de Mn ({-1, 1}), des matrices A 
qui vérifient
n2  S(A).
2

Partie II
Soit k un entier strictement positif et U1 , . . . , Uk une suite de k 
variables aléatoires à valeurs
dans {-1, 1}, indépendantes et de loi uniforme. On note également
Sk =

k
X

Ui .

i=1

!

1. Soit  : R  R la fonction définie par () = ln E[eU1 ] . Établir que
  R,

() 6

2
.
2

2. Soit t  R. Montrer que pour tout  > 0, on a l'inégalité
P(Sk > t) 6 exp(k() - t).
3. En déduire l'inégalité de Hoeffding pour Sk : pour tout t > 0, on a
 2
t
.
P(Sk > t) 6 exp -
2k
On introduit maintenant une variable aléatoire uniforme C :   Mn ({-1, 1}). 
Pour   , on
note Ci,j () les coefficients de la matrice C().
4. Soient X = (x1 , . . . , xn ) et Y = (y1 , . . . , yn ) deux vecteurs 
quelconques dans {-1, 1}n .
Montrer que (xi yj Ci,j )16i,j6n est une famille de n2 variables aléatoires à 
valeurs dans
{-1, 1}, indépendantes et de loi uniforme.
5. Montrer que pour tout t > 0, on a

P(M (C) > tn

3/2

  2
t
- 2 ln 2 n .
) 6 exp -
2

6. On rappelle la notation M (n) = min {M (A) | A  Mn ({-1, 1})} . Montrer que 
pour tout
n > 1, on a

M (n) 6 2 ln 2 n3/2 .
Indication : on pourra commencer par montrer que pour tout  > 0, il existe une 
matrice
A dans Mn ({-1, 1}) telle que
! 

M (A) 6 2 ln 2 +  n3/2 .

Partie III
Dans cette partie, on établit un minorant non trivial pour M (n).
1. Pour A = (ai,j )16i,j6n  Mn ({-1, 1}) et Y = (yi )16i6n  {-1, 1}n , on note

gA (Y ) = max tXAY | X  {-1, 1}n .
Montrer que la fonction gA peut se réécrire
gA (Y ) =

n X
n
X
i=1 j=1

3

ai,j yj .

2. On introduit maintenant une variable aléatoire uniforme Z :   {-1, 1}n . 
Pour  
, on note Zi () les coordonnées de Z(). Montrer que pour tout A = (ai,j 
)16i,j6n 
Mn ({-1, 1}), on a

n  
n
X
1 X n

|n - 2k|,
i  {1, . . . , n},
E
ai,j Zj = n
2
k
j=1

où

!n 
k

k=0

désigne le coefficient binomial. En déduire
n  
n X n
E [gA (Z)] = n
|n - 2k|.
2
k
k=0

3. (a) Montrer que pour m  {0, . . . , n - 1}, on a
m
X
k=0

n-1
n
.
=n
(n - 2k)
m
k

(b) En déduire que pour toute A  Mn ({-1, 1}),
E [gA (Z)] =
où  n2  désigne la partie entière de

n2 n - 1
,
2n-1  n2 

n
2.

4. (a) Montrer que

M (n) >

n2 n - 1
.
2n-1  n2 

(b) Montrer ensuite, à l'aide de la formule de Stirling rappelée en préambule, 
que ce
minorant est équivalent à Cn quand n tend vers l'infini, pour des constantes C 
et
 > 0 que l'on explicitera. Comparer au majorant de M (n) obtenu à la question 6 
de
la partie II.

Partie IV
Dans cette partie, on établit la formule de Stirling à l'aide d'une étude 
d'intégrales.
1. Pour n  N, on pose
In =

Z

+

xn e-x dx.
0

Déterminer par récurrence In pour tout n  N.

2. Montrer que pour n > 1, on a

 n n  Z + 
x n -xn
dx.
In =
n 
1+ 
e
e
n
- n
3. Soit U l'ouvert de R2 défini par
U := {(t, x)  R2 | t > 0 et x > -t},
et soit f la fonction définie sur U par
f (t, x) = t2 ln(1 +
4

x
) - tx.
t

(a) Montrer que pour (t, x)  U , on a
x60

f (t, x) 6 -

x2
.
2

(b) Pour x > 0, montrer que l'on a
t > 1,

f (t, x) 6 f (1, x).

Pour cela, on pourra commencer par écrire
certaine fonction F que l'on étudiera.

f
t (t, x)

sous la forme tF (x/t) pour une

4. Déduire des questions précédentes la formule de Stirling.

Partie V
Dans cette dernière partie, on fixe A  Mn ({-1, 1}) et on note
m(A) := min(S(A)  N).
1. Pour Y  {-1, 1}n , montrer que l'on a

min tXAY

| X  {-1, 1}n 6 n

et en déduire m(A) 6 n.
2. En s'inspirant de la question précédente et des méthodes développées dans 
les parties II et
III, montrer que l'on a également
p
m(A) 6 2n ln(2n).

5

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



X/ENS Maths PC 2018 -- Corrigé
Ce corrigé est proposé par Philippe Bouafia (professeur à l'ENSEA) ; il a été 
relu
par Hervé Diet (professeur agrégé) et Guillaume Batog (professeur en CPGE).

Dans ce problème, on étudie la différence maximale, notée M(A), entre le nombre
de 1 et de -1 que l'on peut obtenir en partant d'une matrice carrée initiale A 
de
dimension n × n à coefficients dans {-1, 1}, et en multipliant certaines de ses 
lignes
et colonnes par -1.

· La première partie vise à se familiariser avec les objets du problème, par 
exemple
en étudiant le cas n = 2, qui peut se traiter « à la main ». La fin de cette 
partie
étudie sous quelles conditions il est possible d'éliminer tous les -1 d'une 
matrice A de taille quelconque en multipliant certaines lignes et colonnes par 
-1.

· Dans les deuxième et troisième parties, on s'intéresse à l'évolution 
asymptoMin
M(A). De manière assez surprenante,
tique de la quantité M(n) =
AMn ({-1,1})

on utilise des méthodes probabilistes pour résoudre ce problème de nature 
purement combinatoire.
· La quatrième partie est indépendante du reste du problème : on y démontre la
célébrissime formule de Stirling, qui donne un équivalent de n ! lorsque n  +,
par des méthodes qui couvrent à peu près le programme d'analyse : formules
intégrales, calcul différentiel à plusieurs variables, théorème de convergence 
dominée, etc.
· Enfin, la dernière partie est moins guidée. Elle reprend essentiellement 
toutes
les méthodes des parties précédentes pour étudier le problème dual de l'écart
minimal entre le nombre de 1 et de -1 que l'on peut obtenir en multipliant
certaines lignes ou colonnes de A par -1.

Ce problème fait intervenir des parties extrêmement variées du programme :
combinatoire, probabilités, analyse, algèbre linéaire, et même, de manière 
implicite,
des espaces vectoriels normés. Il contient nombre de questions astucieuses 
(sans être
infaisables) qui le rendent formateur.

Indications
Partie I
I.3 Montrer que DY parcourt {-1, 1}n lorsque Y parcourt {-1, 1}n.

I.4 Pour le calcul de S(A), essayer de se ramener au cas des matrices I et J 
par des
opérations du type « multiplication d'une ligne ou d'une colonne par +
- 1 ».

I.5 Montrer les équivalences (a)  (b) et (b)  (c).

I.6 Pour toute matrice A  Mn ({-1, 1}) de rang 1, compter le nombre de couples
2
t
(X, Y)  ({-1, 1}n) tels que A = X Y.
Partie II
II.2 Appliquer l'inégalité de Markov.
II.3 Appliquer la question II.1, puis le résultat de la question II.2 pour une 
valeur
judicieusement choisie de .
II.5 Exprimer {M(C) > tn3/2 } comme une union d'événements dont on pourra
majorer la probabilité grâce à la question II.3.
II.6 Si un événement est de probabilité non nulle, alors il est non vide.
Partie III
III.2 Utiliser une loi binomiale.

n
n-1
n-1
III.3.a Montrer que (n - 2k)
=n
-n
.
k
k
k-1
III.3.b Reprendre le résultat de la question III.2 et distinguer les k selon 
que n - 2k
soit positif ou négatif.
III.4.a Revenir à la définition de l'espérance pour calculer E(gA (Z)).
Partie IV
IV.3.b Montrer que la fonction partielle t 
7 f (t, x) est décroissante sur [ 1 ; + [
en considérant sa dérivée.
n
Z + 

x
1+ 
e -x n dx à l'aide du
IV.4 Déterminer la limite de l'intégrale

n
- n
théorème de convergence dominée.
Partie V
V.1 Remarquer que, si u et v sont deux réels dont l'un est positif et l'autre 
négatif,
alors |u + v| 6 max(|u| , |v|).
Montrer que, pour tout (z1 , . . . , zn )  Rn , on peut construire pas à pas une
n
P
suite finie x1 , . . . , xn  {-1, 1} telle que
xi zi 6 max (|z1 | , . . . , |zn |).
i=1

V.2 Introduire  > 0 et une variable aléatoire Z à valeurs dans {-1, 1}n comme
dans la question III.2, puis montrer que
!
n
p
P
P
Max
ai,j Zj 6 2n ln(2n) +  > 0
i[[ 1 ; n ]] j=1

en s'inspirant des méthodes de la deuxième partie.

Partie I
Donnons-nous une matrice A  Mn ({-1, 1}) ainsi que deux vecteurs X
et Y dans {-1, 1}n. Notons que
t

X AY =

n P
n
P

xi yj ai,j

i=1j=1

est la somme des éléments de la matrice (xi yj ai,j )16i,j6n , obtenue à partir
de A en multipliant pour tout i  [[ 1 ; n ]] la ie ligne par xi , et pour tout
j  [[ 1 ; n ]] la j e colonne par yj .
Pour se forger une intuition, on peut penser à l'image suivante. Plutôt
qu'à une matrice A à coefficients dans {-1, 1}, pensons à un damier de taille
n×n rempli de jetons bifaces noirs et blancs, et dont les faces visibles sont 
initialement données par la matrice A (1 pour blanc et -1 pour noir). À chaque
tour, vous avez le droit de retourner tous les jetons d'une ligne ou bien d'une
t
colonne, comme au jeu Othello. La quantité X AY représente alors l'avance
qu'ont les blancs par rapport aux noirs, si l'on a retourné toutes les lignes i
pour lesquelles xi = -1, et toutes les colonnes j pour lesquelles yj = -1.
Si l'on poursuit cette image, la quantité M(A) représente l'avance maximale que 
peuvent atteindre les blancs en jouant de manière optimale.
Une question naturelle se pose : est-il possible d'atteindre une configuration
sans jetons noirs ? Autrement dit, peut-on avoir M(A) = n2 ? Cette question
sera résolue à la fin de la première partie.
I.1 Un élément de Mn ({-1, 1}) est déterminé par ses n2 coefficients pris dans
l'ensemble {-1, 1} de cardinal 2 d'où
2

Card Mn ({-1, 1}) = 2n

De manière plus formelle, la phrase « un élément de Mn ({-1, 1}) est
déterminé par ses n2 coefficients pris dans {-1, 1} » signifie que l'application

n2

Mn ({-1, 1}) - {-1, 1}
:
(ai,j )
7- (a1,1 , a1,2 , . . ., a2,1 , a2,2 , . . ., . . . )

|
{z
} |
{z
}

ligne 1

ligne 2

est bijective. On en déduit que les ensembles de départ Mn ({-1, 1}) et
2
d'arrivée {-1, 1}n ont le même cardinal, et on conclut en notant que
2
2
2
Card {-1, 1}n = (Card {-1, 1})n = 2n .
Un tel niveau de précision n'est cependant pas exigé. En combinatoire,
l'usage est d'adopter un style de rédaction plus informel que dans les autres
branches des mathématiques.
Par ailleurs, la matrice nulle n'appartient pas à Mn ({-1, 1}), donc
L'ensemble Mn ({-1, 1}) n'est pas un sous-espace vectoriel de Mn (R).
I.2 Soit A une matrice de Mn ({-1, 1}) et k  S(A). Par définition de S(A), il 
existe
des vecteurs X, Y  {-1, 1}n tels que
t

k = X AY =

n P
n
P

ai,j xi yj

i=1j=1

Ainsi k est un entier relatif car c'est une somme de 1 et -1. D'après 
l'inégalité
triangulaire,
n P
n
n P
n
P
P
|k| 6
|ai,j | |xi | |yj | =
1 = n2
i=1j=1

i=1j=1

Les entiers ai,j xi yj valent -1 ou 1. En particulier, ils sont impairs, de 
sorte que k
s'écrit comme une somme de n2 entiers impairs. Il en découle que k a la même 
parité
que n2 , donc que n. En particulier, si n est pair, alors 1 6 S(A), et si n est 
impair,
alors 0 6 S(A). En conclusion,
S(A) est strictement inclus dans {-n2 , . . . , n2 }.
Montrons à présent que S(A) est symétrique. Soit k  S(A). Il existe des vecteurs
t
X, Y  {-1, 1}n tels que k = X AY. Comme l'ensemble {-1, 1} est stable par
multiplication par -1, le vecteur -Y appartient également à {-1, 1}n. Ceci 
implique
que -k = t X A(-Y)  S(A). Réciproquement, dans le cas où -k  S(A), on déduit
de ce qui précède que k = -(-k)  S(A).
Un entier k est dans S(A) si et seulement si -k est dans S(A).
I.3 Notons que l'application
(
{-1, 1}n
- {-1, 1}n
:
Y = (y1 , . . . , yn ) 7- DY = (d1,1 y1 , . . . , dn,n yn )

est bien définie. Les coefficients diagonaux de D sont tous dans {-1, 1} et, 
comme
12 = (-1)2 = 1, on en déduit que D2 est la matrice identité d'où    = id .
En particulier,  est une bijection sur {-1, 1}n. De la même manière, on montre 
que
t
l'application  : X 7 C X réalise une bijection sur {-1, 1}n. Il vient que
k  S(B)  X, Y  {-1, 1}n
 X, Y  {-1, 1}n

 X, Y  {-1, 1}n

 X , Y  {-1, 1}n
k  S(B)  k  S(A)

t

k = X CADY

t
t
k=
C X A (DY)
t

k = (X) A(Y)
t

k = X AY

( et  bijectives)

car  et  sont des bijections sur {-1, 1}n. On conclut
S(A) = S(B)
I.4 Introduisons deux vecteurs X = (x1 , x2 ) et Y = (y1 , y2 ) de {-1, 1}2 et 
calculons

 1 1
y1
t
X IY = x1 x2
= (x1 + x2 )(y1 + y2 )
1 1
y2

Or la somme x1 + x2 ne peut prendre comme valeurs que -2, 0 ou 2, et il en va de
même pour la somme y1 + y2 . Cela implique que S(I)  {-4, 0, 4}. Montrons que
cette inclusion est en réalité une égalité. L'ensemble S(I) étant symétrique 
d'après la
question I.2, il suffit pour cela de montrer que 0  S(I) et 4  S(I), ce qui se 
fait par
des choix judicieux de vecteurs X et Y :

 1 1
 1 1
1
1
0= 1 1
et
4= 1 1
1 1
-1
1 1
1
d'où

S(I) = {-4, 0, 4}