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
Mots clefs matrices de permutation, distance, loi binomiale, vecteurs aléatoires, python, simulation, loi géométrique

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


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