Mines Maths 1 PSI 2018

Thème de l'épreuve Théorème de Komlos
Principaux outils utilisés matrices, probabilités, espaces vectoriels
Mots clefs déterminant, existence, équivalent

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


CONCOURS MINES
COMMUN... PONTS
..

ECOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES SAINT--ETIENNE, MINES NANCY,
IMT Atlantique, ENSAE PARISTECH.

Concours Centrale-Supélec (Cycle International),
Concours Mines--Télécom, Concours Commun TPE / EIVP.

CONCOURS 2018
PREMIÈRE ÉPREUVE DE MATHÉMATIQUES

Durée de l'épreuve : 3 heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.

Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :

MATHÉMATIQUES I - PSI

L'énoncé de cette épreuve comporte 6 pages de texte.

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur
d 'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant 
les
raisons des initiatives qu'il est amené à prendre.

Théorème de Komlôs

Notations :

-- Si a" est un nombre réel on note [oe] sa partie entière, c'est--à--dire le 
plus grand
entier relatif qui est inférieur ou égal à :r.

-- On appelle cardinal de l'ensemble fini E le nombre de ses éléments, que l'on
note |E |

-- On note P(E) l'ensemble des parties de l'ensemble E.

-- Dans tout le problème on identifiera R" à l'espace des matrices lignes 
M17n(R) et
on notera <:r, y) le produit scalaire canonique des deux vecteurs, soit

'"
<33, y) = ZOEjyja
j=1

les OEj, yj étant les composantes de m, y respectivement.

-- Si V est un sous--ensemble de R" on note Vect(V) l'espace vectoriel engendré 
par V.

On note Vl l'orthogonal de V, c'est-à-dire l'ensemble des vecteurs y tels que 
Voe E
17,  = 0-

-- Si M est une matrice carrée de nombres réels, on note det(M ) son 
déterminant.

Dans tout le problème on pourra utiliser librement la formule de Stirling que 
l'on

rappelle :
" TL
n! Nn_>+oo 27rn (--) .
e

Définition 1 (Espace de Rademaeher) Sin, q E N*, on note

&... = {w = (cul-7j, 1 S i S q, 1 S j S n) tels que w... = ::1, Vi,j}.

Pour touti E {l, - -- ,q} et j EUR {1, - ---- ,n}, on introduit la variable 
aléatoire M... telle
que
Mjflj ! Qq,n _) {--1,1}
au r--> co...».

On munit QI," de la probabilité uniforme P. Cela signifie que les variables 
aléatoires
(M...-, 1 g i S Q» 1 S j S n) sont indépendantes et de même loi :

1
P...... = 1) = 5 = P(M...-- = _1).

Si q = n, on note M(") la matrice aléatoire

M1,1 M1,n
M...) = : .
M...1 . . . M,...
On note Lg"), -- --- , Lg" les vecteurs lignes de M...). Par construction, ce 
sont des vec-

teurs aléatoires indépendants et de même loi.

Le but du problème est de démontrer, qu'ainsi construite, une matrice aléatoire 
est
inversible avec forte probabilité quand n est grand :

Théorème 1 (Komlôs) limn_,oeP(detM(n) = 0) = 0.

A Coefficients binomiaux

1. Soit n E N* : montrer que l'application

... (Z)

est croissante sur {D, -- ---- , [n/2l}. En déduire que pour tout [EUR E {O, -- 
-- -- ,n},
n < n .
k _ ln/2l

2. Trouver un équivalent de ( ) quand n tend vers l'infini. En déduire qu'il 
existe

n
[ra/2]
un entier no tel que pour n 2 no,

n 2"
(wa) î ? ...

3. Montrer que pour tout entier non nul n et tout [EUR E {O, -- -- -- ,n},
" k--1 k
2 < n .

On note (e,-, 1 S i S n) la base canonique de R" et v = ZÎ=1 ei. On identifie 
QLn et le

sous--ensemble de R" "
{Zwi 61, (001, ' ' ' 7wn) EUR Ql,n} '
i=1

4. Pour tout i E {l, -- - -- ,n}, exprimer e,- en fonction de v et v -- 2e,-. 
En déduire que
Vect(Q1,n) = R".

Dimension 2

5. Déterminer l'espérance de det M (2).

6. Montrer que la variance de det M (2) est égale à 2.

7. Calculer P(det M?) = o).

C Quelques bornes

On suppose dorénavant n 2 2.

8. Quelle est la probabilité que les deux premières lignes de M (") soit égales 
ou
opposées?

En déduire que P(det M(") = O) 2 21_" si n 2 2.

9. Soient A, -- - -- ,ln des vecteurs non nuls de R". Montrer que ces vecteurs 
sont liés si
et seulement si, il existe j EUR {1,-- --- ,n -- 1} tel que

lj+1 EUR Vect({l1, - ° - ,lj}).

En déduire que

n--1

P(det M(") = 0) g 2 P(LÊË1 e Vect(Lgn>7 . .. ,Lg")))_ (2)

j=1

Soit "H un sous--espace vectoriel de R'" de dimension (1. On rappelle que "Hl 
est un
sous--espace vectoriel de dimension n -- d et que ("i--l')l = 'H.

10. Montrer alors qu'il existe des réels (d...-, 1 S i S n -- d, 1 S j S n) 
tels que

06171 . . . OZLn fil 0
oe=(oe1,------,oen)efi<=> ; ; ; =
an--d,1 - - - an--d,n mn 0
11. En utilisant le pivot de Gauss, montrer qu'il existe 1 S il < < id S n tel
que pour tout (y1, -- --- ,yd) EUR Rd il existe un unique 513 = (1171, -- ---- 
,x") E "H tel que

oeik =yk pour k= 1,----- ,d.
12. En déduire que
P(LY" @ %) $ $*",

puis que pour tout j EUR {1,- --- , n -- 1},

P (LW

... & Vect(Lâ"), . ... ,L(."))) < 2j--". (3)

Indication : on pourra utiliser la conséquence suivante de la formule des 
probabilités
totales

P(LÊOE, @ Vect(Lâ"), . ... , Lg")))

= 2 P(Läïä e vec...1,... , t) | L3") = l , LE") = 'J')

11,----,ljeQ...
>< P(LY" = [l, . ... , Lg") = l,»)
et l'indépendance des vecteurs lignes.
Soit q < n et ou E 9%". On note ll, - -- , lq ses vecteurs lignes.

13. Montrer que l'on peut trouver un vecteur non nul orthogonal a Vect(li, i = 
1, -- -- - , q)
qui soit a coordonnées dans Z.

D Théorème de Erdôs-Littlewood-Ofibrd

Définition 2 Soit n un entier non nul. Soit A un sous-ensemble de P({1, - ---- 
,n}). On
dit que A est une anti--chaine si denoe éléments distincts A,B quelconques de A 
sont

incomparables, c'est--â-dire tels que A n'est pas inclus dans B et B n'est pas 
inclus dans
A.

Commençons par un exemple. Soit k EUR {1,----- ,n} et Ak l'ensemble des parties 
de
{1,----- ,n} de cardinal k.

14. Montrer que Ak est une anti--chaîne et que

n 2"
|Ak| S <[n/2l) S fia

la deuxième inégalité ayant lieu pour n assez grand.

Définition 3 Soit A une anti--chaine et A E A, de cardinal noté lA|. On note SA,

\

l'ensemble des bijeeti0ns o de {1, -- ---- ,n} dans lui--même telles que la 
restriction de a a
{1,------ , |Al} soit une bijection de {1, -- ---- , |Al} dans A.

15. Quel est le cardinal de S A ?

16. Soit B E A avec B % A. Montrer que SA m 53 = (Ô.

17. En déduire que si ak désigne, pour k: S n, le nombre d'éléments de A de 
cardinal

k, alors
n

2 ÎÏ g1.
=()

k

18. Montrer que

"" 5 (ln/21) '

Soitv= v1,----,vn ER"telqueuZl,pourt0utj=l,---,n.SiAC 1,-----,n
3

on pose
5A = 2 "j -- 2 %

jeA jEURAC

où AC est le complémentaire de A dans {l, - -- - , n}.

19. Montrer que si A C B C {1,------ ,n}, A # B, alors

sB--sAZ2.

20. Soit J un intervalle ouvert de R de longueur 2 : montrer que si n est assez 
grand

alors 1
P(< Lg"), @ > e J) S --_

\/ñ
Montrer que cette propriété reste vraie si l'on suppose seulement que pour tout
j EUR{1,...,TL}, "'le 1-

Indicati0n : construire une bijection entre 91,7, et l'ensemble des parties de 
{l, -- - -- , n}
Construire une anti--chaîne intéressante.

E Universalité

Dans tout ce qui suit, k est un entier inférieur à n.

Définition 4 Soit V C 1117". L'ensemble V est dit k-um'versel si pour tous les 
k--uplets
1 Sj1 e{L---.n}k weflm i=l m=l
jl<... O.

26. Montrer que si n est assez grand alors n -- tn 2 n/ 2 et

n--1
215
2 P(LÊOE1 EUR Vect(Lgn),-w , Lÿ")) S " -- (6)
j=n_tn+1 lnn
Indication : on distinguera les cas selon que Vect(L@, - --- , Lgn)) est 
k--universel

ou pas et l'on prendra k = [ln n].

F Théorème de Komlôs

27. En déduire le théorème de Komlôs.

Indication : on pourra partir de (2) et choisir convenablement une suite (75... 
n 2 l).

FIN DU PROBLÈME

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



Mines Maths 1 PSI 2018 -- Corrigé
Ce corrigé est proposé par Hervé Diet (professeur agrégé) ; il a été relu par 
Théo
Lenoir (ENS Ulm) et Florian Metzger (docteur en mathématiques).

Ce sujet porte sur l'espace de Rademacher, défini comme le sous-ensemble q,n
de Mq,n (R) constitué des matrices à coefficients dans {-1, 1}. On prouve le 
théorème
de Komlós qui s'énonce ainsi : si M(n) est une variable aléatoire à valeurs 
dans n,n
qui suit la loi uniforme, alors
lim P(det(M(n) ) = 0) = 0

n+

En d'autres termes, une matrice aléatoire est inversible avec forte probabilité 
lorsque
n est grand.
Le sujet fait largement appel aux matrices et aux probabilités. Il se compose de
six parties connectées les unes aux autres.
· La première établit quelques majorations sur les coefficients binomiaux à 
l'aide
de raisonnements classiques (équivalents, récurrences, etc.). Ces majorations
permettront de calculer des limites dans la suite du sujet.
· La partie B étudie de manière exhaustive le cas de la dimension 2.

· La partie C donne quelques bornes sur les probabilités qui seront utilisées 
ultérieurement. Ces résultats sont établis en travaillant sur des espaces 
vectoriels.
· La partie D porte sur des aspects ensemblistes (cardinal, dénombrement) et sur
les anti-chaînes qui sont les sous-ensembles de P({1, ..., n}) dont les éléments
sont incomparables (ni A  B ni B  A si A 6= B). On démontre alors un
théorème d'Erdös-Littlewood-Offord : si v  Rn tel que |vj | 6 1 pour tout
j  [[ 1 ; n ]], si J est un intervalle de R de longueur 2 et si n est assez 
grand,

1
(n)
P hL1 , vi  J 6 
n
(n)

où L1

désigne la première ligne de la matrice aléatoire M(n) .

· Ce théorème est exploité dans la partie E. Cela permet de prouver des 
majorations nécessaires pour la suite.
· La dernière partie est consacrée à la démonstration du théorème de Komlós.
On y exploite tous les résultats établis précédemment.
Le sujet est assez difficile pour la filière PC. Il comporte des raisonnements 
qui
peuvent être déstabilisants et la manipulation des probabilités requiert 
beaucoup de
rigueur. Comme le sujet suit une progression linéaire, il n'est pas judicieux 
de passer
une partie puisqu'elle servira à coup sûr pour la suite. Cela en fait un sujet 
utile en
fin de révision car il couvre nombre de thèmes d'algèbre au programme.

Indications

n
n
1 Étudier le rapport
/
. Étendre la propriété à k > n/2 par symétrie
k+1
k
des coefficients binomiaux.
2 Différencier les cas n pair
puis utiliser la formule de Stirling pour cher et impair

n
cher un équivalent de
.
n/2
3 Traiter le cas k = 0 à part. Faire un raisonnement par récurrence sur k.

4 Prouver que 1,n engendre tous les éléments de la base canonique de Rn .
5 Calculer l'espérance de E(M1,1 ) puis utiliser les propriétés de l'espérance.
6 Appliquer la formule de transfert.
8 Commencer par déterminer les valeurs de
P(Mi,j = Mk,l ) et P(Mi,j = -Mk,l ) avec (i, j) 6= (k, l)
On pourra ensuite poursuivre les calculs et noter que det(M(n) ) = 0 lorsque les
colonnes L1 et L2 sont liées.

9 Utiliser l'équivalence démontrée pour décomposer l'événement det(M(n) ) = 0 .

10 Définir une base de H et la relier aux i,j .

11 La méthode du pivot de Gauss donne les n - d pivots, et les colonnes sans 
pivot
donnent les indices 1 6 j1 < j2 < · · · < jd 6 n.
12 Attention à tourner la page du sujet pour voir les indications.

13 Exploiter la méthode d'orthogonalisation de Gram-Schmidt sans normaliser les
vecteurs pour construire le vecteur voulu.
15 Étudier la restriction de  à {1, . . . , |A|}.

17 Utiliser la question précédente pour décomposer l'ensemble A.
P
P
19 Étudier la différence
vj -
vj pour montrer qu'il reste au moins un élément
jB

jA

et en déduire une minoration.

20 Prouver d'abord que AJ = {A  P({1, . . . , n}) | sA  J} est une anti-chaîne.
21 Écrire la négation de la définition proposée.

23 Trouver une majoration de la probabilité désirée qui ne dépende que de n. 
Étudier
la limite du produit de ce terme et de n pour conclure.
24 Raisonner par l'absurde sur le nombre de coordonnées non nulles de v.
25 Choisir une suite d'indices 1 6 j1 < j2 < · · · < jk 6 n tels que l'on 
puisse ramener
le problème de 1,n à 1,m et appliquer le résultat de la question 20.
27 Scinder la somme obtenue en deux morceaux, de 1 à n - tn puis de n - tn + 1
à n -
1 et majorer chaque partie.
Choisir

 une suite (tn ) à croissance moins rapide
que ( ln n), par exemple (ln n)1/4 .

A. Coefficients binomiaux
 
n
1 Soit n  N et k un entier tel que k + 1 6 n/2. Le coefficient binomial
est
k
non nul, ce qui permet de considérer

n
k+1
n!
k!(n - k)!
  =
×
(k + 1)!(n - k - 1)!
n!
n
k
n-k
n+1
=
=
-1
k+1
k+1

La fonction x 7 1/x est décroissante sur R+ et k +1 est inférieur à n/2 donc à 
n/2.
On en déduit que
1
1
2
>
=
k+1
n/2
n

soit

d'où

n
k+1
2
2
2
  > (n + 1) - 1 = 2 + - 1 = 1 + > 1
n
n
n
n
k

n
L'application k 
7
est croissante sur {0, . . . , n/2}.
k

D'après le résultat précédent, on a

n
j n ko
n
n
 k  0, . . . ,
6
k
n/2
2

n
n
Il suffit alors de remarquer que
=
donc, si k > n/2 alors
k
n-k
jnk
n
n
= n - k <
= n - k 6
k>
2
2
2
 
n
car n - k est entier. Par croissance de k 7
sur [[ 0 ; n/2 ]], on obtient
k

jnk
n
n
n
=
6
si k >
k
n-k
n/2
2
La majoration est aussi vraie lorsque k > n/2. En conclusion,
k  {0, . . . , n}

n
n
6
k
n/2

2 Soit n  N, on va faire l'étude selon la parité de n.
· Considérons le cas où n est pair. Soit p  N tel que n = 2p. Alors

(2p)!
n
=
n/2
p!2

On peut maintenant utiliser la formule de Stirling et écrire
 2p

2p

2 × 2p
22p
e
n
=

2p
p
n/2
p
2p
e
et finalement, lorsque n est pair,

 r
2
2n
n

×
n/2

n
· Voyons maintenant le cas n impair. Soit p  N tel que n = 2p + 1 ; alors

jnk 
1
(2p + 1)!
n
2p + 1
= p+
=p
d'où
=
=
n/2
p
2
2
p!(p + 1)!
On peut astucieusement réutiliser le travail précédent en remarquant que
r
(2p + 1)!
2 22p+1
2p + 1 (2p)!
22p
=
·

2
·
=
· 

p!(p + 1)!
p+1
p!2
p

2p

Ainsi, en remarquant que 2p  2p + 1, il vient à nouveau
r

 r
2
22p+1
2
2n
n

·
=
×
n/2

n
2p + 1
En conclusion,

On a

r

r

2
2n
n
× .

n/2 n+ 
n

2
< 1 puisque 2 < . L'équivalent précédent implique alors que

2n
n
n0  N n > n0
=
6
n/2
n

3 Soit n  N, la propriété attendue se démontre aisément pour k = 0 puisque
 
1
1
n -1
2 = 1 × = < 1 = n0
0
2
2
Montrons par récurrence sur k  {1, . . . , n} que la propriété
 
n k-1
P(k) :
2
6 nk
k
est vraie pour tout k  {1, . . . , n}.
 
n 0
· P(1) est vraie car
2 = n × 1 = n = n1 .
1
· P(k) = P(k + 1) : supposons que pour tout k  [[ 1 ; n-1 ]] la propriété P(k)
est vraie. Alors

n!
n!
2(n - k)
n
2k =
2k =
2k-1 ×
k+1
(k + 1)!(n - k - 1)!
k!(n - k)!
k+1