Centrale Maths 1 PSI 2016

Thème de l'épreuve Matrices à coefficients dans {0,1}
Principaux outils utilisés algèbre linéaire, topologie, probabilités

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


Mathématiques 1
PSI

4 heures Calculatrices autorisées

2016

Dans tout ce problème, n est un entier supérieur ou égal à 2 et l'on note :

-- M,,(Ü?) l'ensemble des matrices carrées d'ordre n à coefficients réels ;

-- GLn(R) l'ensemble des éléments inversibles de M,,(lR) ;

-- O,,(UÈ) l'ensemble des matrices orthogonales d'ordre n ;

-- LK,, l'ensemble des éléments de M,,(lR) dont tous les coefficients sont dans 
{D, 1} ;

-- y,, l'ensemble des éléments de M,,(IR) dont tous les coefficients sont dans 
{O, 1] ;

-- ?,, l'ensemble des éléments de M,,(lR) dont tous les coefficients sont dans 
{D, 1} et ne contenant qu'un seul
coefficient non nul par ligne et par colonne ;

-- 'M la transposée d'une matrice M, mais la notation M T est également 
utilisable.

Parexemple:
0 1 1 L 0 1 0
(1 () 1)ex3 & ey2 (1 0 O)e?3
0 0 1

1 1 () eXp(*1)
Ce problème aborde l'étude de matrices à coefficients dans {O, 1} a travers 
plusieurs thématiques indépendantes
les unes des autres. Les deux premières parties étudient quelques propriétés 
algébriques et topologiques des
ensembles SF,, et y,, définis ci--dessus. La partie III étudie le cas 
particulier des matrices de permutation. La
partie IV étudie deux modalités de génération aléatoire de matrices à 
coefficients dans {O, 1}.

H>lÇO @

I Généralités

I.A * Propriétés élémentaires

I.A.1) Justifier que LK,, est un ensemble fini et déterminer son cardinal.

I.A.2) Démontrer que pour tout M EUR y... det(M) < n! et qu'il n'y a pas 
égalité.
I.A.3) Démontrer que y,, est une partie convexe et compacte de M,,(lR).

I.A.4) Soit M EUR y,, et À une valeur propre complexe de M. Démontrer que |À| g 
n et donner un exemple
explicite où l'on a l'égalité.

LB * Étude de x; = x,, @ GL,,(1R)
I.B.l) Faire la liste des éléments de l'é. Préciser (en justifiant) ceux qui 
sont diagonalisables sur IR.

I.B.2) Démontrer que X'2 engendre l'espace vectoriel M2. Est--ce que, pour n 2 
2, ï ;, engendre l'espace
vectoriel M,,(IR) '?

II Deux problèmes d'optimisation

II.A * Étude de la distance à y,,
Pour tout (M,N) EUR (M,,(IR))2, on note

(MW) : tr(tMN)

II.A.1) Démontrer que l'on définit ainsi un produit scalaire sur M,,(ER). 
Expliciter (M |N ) en fonction des
coefficients de M et N.

On notera "M" la norme euclidienne associée.
II.A.2) On fixe A EUR M,,(lR), prouver qu'il existe une matrice M EUR y,, telle 
que :

VNEUR % llA--Mll < llA--Nll
II.A.3) Justifier l'unicité de la matrice M ci--dessus et expliciter ses 
coefficients en fonction de ceux de A.

II.B * Maæimisation du déterminant sur X,, et y,,

II.B.1) Justifier que le déterminant possède un maximum sur SK,, (noté mn) et 
un maximum sur y,, (noté y").

2016--01--14 14:07:36 Page 1/3 @@ BY--NC-SA

II.B.2) Démontrer que la suite (yk)k>2 est croissante.

II.B.3) Soit .] EUR %" la matrice dont tous les coefficients valent 1. On pose 
M = .] -- In.
Calculer det(M ) et en déduire que lim yk : +00.

ka+oo
II.B.4) Soient N : (n...--)...-- EUR yn. Fixons 1 < i,j g n et supposons que 
n...-- EUR ]0.1{.

Démontrer qu'en remplaçant nl- soit par 0, soit par 1, on peut obtenir une 
matrice N ' de yn telle que

]
det(N) < det(N').
En déduire que :cn : y".

III Matrices de permutations

On munit B?" de sa structure euclidienne canonique et on note (e1,...,en) sa 
base canonique.

On note Sn l'ensemble des bijections de l'ensemble { 1, ..., n} dans lui--même 
(appelées permutations).

Pour tout 0 EUR S... on note Pa la matrice de ?" dont le coefficient ligne i, 
colonne j vaut 1 si t = 0( j) et 0 sinon.
On dit que Pa est la matrice de permutation associée à a.

On note ua l'endomorphisme de IR" canoniquement associé à Pa.

III.A + Description de 50,1

III.A.1) Donner deux définitions d'une isométrie vectorielle de R" et démontrer 
leur équivalence.
III.A.2) Démontrer que si M EUR On([R), alors son déterminant vaut 1 ou --1. 
Que penser de la réciproque ?
III.A.3) Démontrer que ?" : X" 0 On([R) et déterminer son cardinal.

III.B + Quelques propriétés des éléments de ?"

III.B.1) Soient a et 0' deux éléments de Sn.
Démontrer que PaPa/ : PU

oa' .

Z-->Sn

Justifier que l'application { k: +--> ak n'est pas injective.

En déduire qu'il existe un entier N 2 1 tel que UN : ld{1
l'ensemble {1,..., n}.

III.B.2) Démontrer que tous les éléments de ?" sont diagonalisables sur C.

...n}7 où Ïd{1,...,n} désigne l'application identité sur

III.B.3) Déterminer les vecteurs propres communs à tous les éléments de ?" dans 
les cas n = 2 et n : 3.

III.B.4) On se propose de démontrer que les seuls sous--espaces vectoriels de 
il?" stables par tous les ua, 0 EUR Sn
sont {OW}, [R", la droite D engendrée par e1 + 62 + + en et l'hyperplan H 
orthogonal a D.

(1) Vérifier que ces quatre sous--espaces vectoriels sont stables par tous les 
ua.

b) Soit V un sous--espace vectoriel de R", non contenu dans D et stable par 
tous les ua. Démontrer qu'il existe
un couple (t,j) EUR {1....,n}2 avect 7': j tel que ei--ej EUR V, puis que les 
n--1 vecteurs (ik--6j (k EUR {1, n}. k 7': j)
appartiennent à V.

O) Conclure.

III.C + Une caractérisation des éléments de ?"

On se donne une matrice M de GLn(R) dont tous les coefficients sont des entiers 
naturels et telle que l'ensemble
formé par tous les coefficients de toutes les puissances successives de NI est 
fini.

Démontrer que M *1 est à coefficients dans N et en déduire que M est une 
matrice de permutation. Que dire
de la réciproque '?

IV Matrices aléatoires de %"

I V.A + Génération par une colonne aléatoire

Soit p EUR ]0,1{. Soient X17 ...,Xn des variables aléatoires mutuellement 
indépendantes, définies sur un espace
probabilisé (Q, A, P) et suivant une même loi de Bernoulli de paramètre p.

IV.A.1) Calculer la probabilité que X 1, ...,X" soient égales.
IV.A.2) Quelle est la loi de S = X 1 + + X" ? On attend une démonstration du 
résultat annoncé.
IV.A.3) Soient i et j dans {1, ...,n}. Donner la loi de la variable aléatoire 
X...-- : Xi >< XJ--

2016--01--14 14:07:36 Page 2/3 ("à BY--NC-SA

IV.A.4) Si au EUR Q, on introduit la matrice colonne

Q -->JV[,,([R)

est ainsi une variable aléatoire.
w H M (ou)

et la matrice M(w) : U(w) t(U(w)). L'application M : {

a) Si au EUR Q, justifier que M(w) EUR LK".

b) Si au EUR Q, justifier que tr(M(w)) EUR {O, ...,n}, que M(w) est 
diagonalisable sur [R et que rg(M(w)) { 1.
c) Si au EUR Q, justifier que M (tu) est une matrice de projection orthogonale 
si et seulement si S (ou) EUR {O, 1}.
IV.A.5) Donner la loi, l'espérance et la variance des variables aléatoires tr(M 
) et rg(M )

IV.A.6) Exprimer Mk en fonction de S et M.

Quelle est la probabilité pour que la suite de matrices (Mk>keN soit 
convergente ?

Montrer que, dans ce cas, la limite est une matrice de projection.

IV.A.7) Quelle est la probabilité que ]VI admette deux valeurs propres 
distinctes ?

IV.B * Génération par remplissage aléatoire

Soit p EUR ]0, 1{. On part de la matrice nulle de M,,(lR), notée M0- Pour tout 
k EUR N, on construit la matrice Mk+1
a partir de la matrice M k de la manière suivante

-- on parcourt en une vague la matrice et chaque coefficient nul est changé en 
1 avec la probabilité p ;

-- chaque action sur un coefiicient est indépendante de ce qui se passe sur les 
autres et des vagues précédentes.

Les M k sont donc des variables aléatoires à valeurs dans X,, et l'on considère 
qu'elles sont définies sur un espace
probabilisê commun (Q, A, P). Voici un exemple de réalisation de cette 
évolution pour n = 2

0 0 1 0 1 0 1 1 1 1 1 1
M0" (0 0)"M1_<10)_'M2--<10)4M3_<1 @) "M4' (1 1) "M5_ (1 1)
Pour le 2 1, le nombre de modifications réalisées lors de la k--ième vague est 
noté N k. Dans l'exemple ci--dessus :
N1 2, N2 0, [V3 1, N4 1, N5 0.
On s'intéresse au plus petit indice [4 pour lequel la matrice M k ne comporte 
que des 1 ; on dit alors qu'elle est

totalement remplie. Dans l'exemple précédent, ce premier indice vaut 4.

Onn0teq:1--petm=n2.

IV.B.1) Dans toute cette question on utilise le langage Python. M désigne une 
matrice carrée d'ordre n. Ses
lignes et ses colonnes sont numérotées de 0 à n -- 1. L'expression M[i, j] 
permet d'accéder à l'élément situé à
l'intersection de la ligne i et de la colonne j et len(M) donne l'ordre de la 
matrice M.

a ) Ecrire une fonction Somme (M) qui renvoie la somme des coefficients de la 
matrice M.

b ) Écrire une fonction Bernoulli (p) qui renvoie 1 avec la probabilité p et 0 
avec la probabilité 1-- p. On pourra
utiliser l'expression random() qui renvoie un réel de l'intervalle {O, 1{ selon 
la loi uniforme.

EUR) À l'aide de la fonction Bernoulli (p), écrire une fonction Modifie (M,p) 
qui modifie aléatoirement la ma--
trice M suivant le principe décrit au IV.B ci--dessus.

d) Écrire une fonction Simulation (n,p) qui renvoie le plus petit entier le tel 
que Mk est totalement remplie
a partir d'un remplissage aléatoire de la matrice nulle d'ordre 11 (qui peut 
être obtenue par zeros((n,n))). Il
n'est pas demandé de mémoriser les M k.

IV.B.2) Donner la loi de N1, puis la loi conditionnelle de N2 sachant (N1 : i) 
pour i dans un ensemble a
préciser. N1 et N2 sont--elles indépendantes '?

IV.B.3) Soient i et j dans {1, n}. Le plus petit entier k 2 1 tel que le 
coefficient ligne i, colonne j de Mk
vaut 1 est noté T...-- (dans l'exemple ci--dessus : TL1 : 1 et TL2 : 3). Donner 
la loi de T....
IV.B.4) Pour un entier k: 2 1, donner la valeur de P(T...-- } ki)

IV.B.5) Soient ?" 2 1 un entier et S,. : N1 + + N,.. Que représente S,, ? 
Donner sa loi (on pourra utiliser la
question précédente).

IV.B.6) On note N le plus petit indice le pour lequel la matrice M k est 
totalement remplie.

a ) Proposer une démarche pour approcher l'espérance de N a l'aide d'une 
simulation informatique utilisant les
fonctions précédentes.

b) Donner une expression de la valeur exacte de cette espérance faisant 
intervenir q et m.

oooFlNooo

2016--01--14 14:07:36 Page 3/3 ("à BY--NC-SA

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



Centrale Maths 1 PSI 2016 -- Corrigé
Ce corrigé est proposé par Nicolas Weiss (Professeur agrégé) ; il a été relu par
Pierre-Elliott Bécue (ENS Cachan) et Sophie Rainero (Professeur en CPGE).

Le sujet adopte plusieurs points de vue (algèbre, topologie, probabilités) pour
étudier des propriétés des matrices à coefficients dans {0, 1}.
· La première partie s'intéresse à l'ensemble noté Yn des matrices à 
coefficients
dans [ 0 ; 1 ] et montre en particulier que les matrices inversibles à 
coefficients
dans {0, 1} engendrent l'espace vectoriel Mn (R).
· Dans la deuxième partie, on étudie d'abord un aspect métrique des matrices à
coefficients dans [ 0 ; 1 ] : on peut donner un sens à la distance à Yn d'une 
matrice
de Mn (R). Ensuite, on prouve que le déterminant atteint un maximum sur Yn ,
et que ce maximum est atteint pour une matrice à coefficients dans {0, 1}.
· La troisième partie traite du cas particulier des matrices de permutation :
ce sont les matrices carrées dont chaque ligne et chaque colonne ne comporte
qu'un seul coefficient valant 1, les autres étant nuls ; elles constituent « une
représentation du groupe symétrique ».
· Enfin, la quatrième partie envisage le cas de matrices aléatoires à 
coefficients
dans {0, 1} engendrées par des vecteurs aléatoires ou par remplissage aléatoire,
et utilise Python.
Une des originalités de ce sujet est qu'il permettait aux candidats de montrer
leur capacité à produire des algorithmes (écrits en Python). Chaque thème est 
par
ailleurs abordé de façon assez classique, même si certaines questions demandent 
de
trouver le bon angle d'attaque. La dernière partie nécessite une compréhension 
en
profondeur de la loi binomiale.

Indications
Partie I
I.A.3 La compacité est hors programme : remplacer le mot « compact » par
« fermé et borné ».
I.A.4 Majorer un coefficient bien choisi de Mv avec v vecteur propre.
I.B.1 Étudier directement le spectre de chaque matrice de X2 .
I.B.2 Procéder par identification pour écrire une matrice de M2 (R) comme 
combinaison linéaire des éléments de X2 . Généraliser en utilisant l'inclusion
de GLn (R) dans GLn+1 (R)

1 0
M 7-
0 M
Partie II
II.A.2 Utiliser le fait que Yn est fermé et borné dans Mn (R).
II.A.3 L'explicitation de M revient à étudier le minimum de la fonction carré 
sur
des segments bien choisis.
II.B.1 Exploiter le résultat des questions I.A.1 et I.A.3.
II.B.2 Réutiliser l'inclusion de GLn (R) dans GLn+1 (R) (voir indication I.B.2).
II.B.3 Si on pose n = det(M), alors on peut établir la relation de récurrence
n  N ,

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

II.B.4 Isoler le terme où intervient le coefficient ni,j dans le développement 
de
det(N) suivant la ligne i ou la colonne j.
Partie III
III.B.1 Aucune application d'un ensemble infini dans un ensemble fini ne peut 
être
injective.
III.B.2 Le polynôme XN - 1 annule P pour un certain N  N.
III.B.3 L'étude des vecteurs propres de P(12) et P(123) suffit à conclure ((12) 
désigne
la permutation de {1, 2, 3} qui transforme 123 en 213 et (123) celle qui
transforme 123 en 231).
III.B.4.b Expliciter ce qu'implique la non appartenance à D sur les coordonnées 
d'un
vecteur.
III.C Voir indication donnée pour la question III.B.1.
Partie IV
IV.A.3 Séparer les cas i = j et i 6= j.
IV.A.4.a Calculer directement les coefficients de M().
IV.A.4.b Utiliser le théorème spectral car M() est symétrique réelle.
IV.A.4.c
IV.A.5
IV.B.2
IV.B.6.b

2

Calculer M() .
Utiliser la question IV.A.4.b.
Choisir deux valeurs i et j de N1 () et N2 () incompatibles mais possibles.
Calculer l'espérance de N après avoir prouvé que
P(N 6 k) =

16i,j6n

P(Ti,j 6 k)

I. Généralités
I.A.1 Chaque matrice de Xn possède n2 coefficients, qui peuvent être égaux à 0 
ou 1
indépendamment les uns des autres. Ainsi,
2

L'ensemble Xn est fini de cardinal 2(n ) .
I.A.2 Montrons par récurrence que la propriété P(n) : « det(M) < n! pour tout
M  Yn » est vraie pour tout n > 2.

a b
 Y2 .
· P(2) : soit
c d
a
c

b
= ad - bc 6 ad 6 1 < 2!
d

car les coefficients a, b, c et d sont compris entre 0 et 1. Donc P(2) est 
vraie.
· P(n) = P(n + 1) : supposons la propriété P vraie au rang n et considérons un 
élément M  Yn+1 . Majorons le développement de det(M) suivant sa
première colonne.
det(M) =

n+1
P
i=1

b i,1 6
(-1)i+1 Mi,1 M

n+1
P
i=1

b i,1
|Mi,1 | M

b i,1 désigne le mineur correspondant à Mi,1 . Mais 0 6 Mi,1 6 1 et M
b i,1
où M
est le déterminant d'une matrice de Yn . Aussi par hypothèse de récurrence,
on obtient
det(M) < (n + 1) × 1 × n! < (n + 1)!
Donc P(n + 1) est vraie.
· Conclusion : P(n) est vraie pour tout n > 2.
Pour tout M  Yn , det(M) < n!

L'hypothèsen >2 faite par le sujet est nécessaire car Y1 = { x | 0 6 x 6 1}
et X1 = { 0 , 1 }. Or 1 = 1!
La compacité est hors programme en PSI. Dans le cas d'un espace vectoriel
de dimension finie sur R, la compacité d'un sous-espace est le fait d'être à
la fois partie fermée et bornée de l'espace ambiant.
Soit (Mk )kN une suite d'éléments de Yn qui converge vers M  Mn (R). Pour tout
couple (i, j)  [[ 1 ; n ]]2 et tout entier k, on a
I.A.3

0 6 (Mk )i,j 6 1
d'où en faisant tendre k vers +
0 6 Mi,j 6 1
c'est-à-dire M  Yn . On vient de montrer que toute suite convergente d'éléments
de Yn converge dans Yn , soit
L'ensemble Yn est fermé dans Mn (R).
Tous les coefficients des matrices de Yn étant compris entre 0 et 1, toute norme
sur Mn (R) est majorée sur Yn . Ainsi

L'ensemble Yn est borné dans Mn (R).
Soient M et N des éléments de Yn et t  [ 0 ; 1 ]. Pour tout (i, j)  [[ 1 ; n 
]]2 , on a
(tM + (1 - t)N)i,j = t Mi,j + (1 - t) Ni,j
Puisque Mi,j , Ni,j , t et 1-t appartiennent à [ 0 ; 1 ], il vient directement 
l'encadrement
0 6 t Mi,j + (1 - t) Ni,j 6 t + (1 - t) = 1
Ceci étant vrai pour tout (i, j), la matrice t M + (1 - t) N appartient bien à 
Yn , et
L'ensemble Yn est convexe dans Mn (R).
t

I.A.4 Soient v = (v1 , · · ·, vn ) un vecteur propre de M  Yn associé à la 
valeur
propre , et i0  [[ 1 ; n ]] un entier tel que |vi0 | = max{|v1 | , · · ·, |vn 
|}. On a
n
P
(Mv)i0 = vi0 =
Mi0 ,j vj
j=1

Il n'y a plus qu'à majorer en valeur absolue cette dernière somme.
|| |vi0 | 6

n
P

Mi0 ,j vj

j=1

6

n
P

|Mi0 ,j vj |

n
P

|vj |

n
P

|vi0 |

j=1

6

car M  Yn

j=1

6

par définition de i0

j=1

|| |vi0 | 6 n |vi0 |
Comme tout vecteur propre est non nul, on a nécessairement |vi0 | > 0, ce qui 
permet
de conclure.
Toute valeur propre complexe  de M  Yn vérifie || 6 n.
L'entier n est valeur propre d'une matrice de Yn , comme on peut le constater à 
l'aide
de l'égalité qui suit.

1 ··· 1
1
n
1
 ..
..   ..  =  ..  = n  .. 
.
.
. .  . 
1 ··· 1

1

n

1

1
 ..
L'entier n est valeur propre de  .
1

··· 1
.. .
.
··· 1

I.B.1 Le déterminant de toute matrice M de X2 est à valeur dans {-1, 0, 1}. Il 
ne
peut être nul que si les produits des deux diagonales de M sont égaux car
a
c

b
= ad - bc
d