Centrale Maths 1 PSI 2016

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