Centrale Maths 1 MP 2016

Thème de l'épreuve Matrices positives (im)primitives
Principaux outils utilisés calcul matriciel, valeurs propres, déterminants, permutations
Mots clefs chemins, matrices positives, matrices primitives, matrices imprimitives, indice de primitivité, matrices irréductibles, Weilandt, Romanovsky

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 MP 4 heures Calculatrices autorisées 2016 Matrices positives ( im ) primitives Ce problème étudie diverses propriétés des matrices primitives et des matrices irréductibles, définies dans les parties III et V respectivement, et s'appuie sur la notion de chemin dans une matrice positive, que l'on définit dans le préambule. Généralités -- Dans tout le problème n désigne un entier supérieur ou égal à 2. Pour tous entiers naturels i et j, avec i < j, la notation ||i,j]] désigne {le EUR N, i EUR le g j}. -- On note M,,(D<) l'ensemble des matrices carrées d'ordre n à coefficients dans Û< (avec IK : [R ou C). Si A est dans M,,(lK), on notera a,|,-- ou |A]... le coefficient de A situé en ligne i et colonne j. On note GL,,([K) l'ensemble des matrices carrées inversibles d'ordre n à coefficients dans [K. On note diag()... À2,. .,À ,,) la matrice diagonale de coefficients diagonaux successifs À1, À2, ..., À,,. (îÿ Si A est une matrice carrée de terme général a, on note a, 'le terme général de la matrice Am. J' -- Soit A dans M,,(lK ). On note Sp(A) (spectre de A) l'ensemble des valeurs propres complexes de A. On appelle rayon spectral de A la quantité p(A) : max{|À|, À EUR Sp(A)}. On dit qu'une valeur propre À de A est dominante si : Vu EUR Sp(A) \ {À}, |,a| < |À|. -- On identifie une matrice A de M,,(Û<) avec l'endomorphisme de [K" qui lui est canoniquement associé. Cela permet de légitimer les notations lm(A) et Ker(A). -- On note AT la transposée d'une matrice A. -- On identifie un élément a : (as,-) de [| >,0 si: V(i ,j), a...-- > 0. On dit que A est strictement positive et on note A > 0, si . V(i ,j),a a,|,-- > 0. Ces définitions s'appliquent aux vecteurs r de [R" (notations a: > 0 ou r > 0). On prendra bien garde au fait que l'implication (A > 0 et A : 0) => A > 0 est fausse ! -- Il est clair (et on ne demande pas de le démontrer) que les puissances Ak (avec le > 1) d'une matrice carrée positive (respectivement strictement positive) sont positives (respectivement strictement positives). Chemins dans une matrice positive -- Soit A : (a...--) une matrice positive de M ,,D?( ). Un chemin dans A est une suite @: (i,,)0 1, telle que: Vk EUR ||0, m--1]], a,k ,}... > 0. Un tel chemin sera noté: i() --> % ik --> e i... -- On dit que EUR a pour longueur m et qu'il va de i0 (son origine) à i... (son extrémité) en passant par les ik. -- On dit que C' est un chemin élémentaire si io, ..., im sont distincts deux a deux. -- On dit que EUR est un circuit si i... : i0 et un circuit élémentaire si de plus io, ..., i,,,11 sont distincts. Dans un circuit, la notion d'origine et d'extrémité perd de son intérêt. On pourra donc dire d'un circuit qu'il passe par un indice i (sans se préoccuper de la position de i dans ce circuit). I Si p(A) < 1, alors lim Am : () mä+oo Cette partie est pratiquement indépendante du reste du problème. Elle démontre un résultat qui ne sera utilisé que dans la question IV.B. On dit qu'une norme A r--> ||A|| sur M,,(lK) est sous--multiplicative si : V(A, B) EUR M,,([K)2, ||AB|| g ||A|| ||B||. I.A -- Deuæ eoeemples de normes sous-multiplicatives 1+oo I.B.1) Soit P dans GL,, (03) et soit T triangulaire supérieure, telles que A : PTPÎ1. On se donne 5 > 0. On pose A : diag(1, 6, 5"*1) et Î : A*1TA. Montrer que Î est triangulaire supérieure et qu'on peut choisir 5 de sorte que N (Î) < 1. I.B.2) Avec ce choix de 5, on pose Q : PA et on munit MAC) de la norme M H HMH : N(Q*1MQ). Montrer que llAll < 1 et en déduire lim Am : O. m-->+oo II Chemins dans les matrices positives Cette partie aborde les notions de base sur les chemins dans une matrice positive A (et notamment le lien entre l'existence de tels chemins et le caractère strictement positif de coefficients des puissances de A). Une bonne compréhension des résultats démontrés ici est importante dans la perspective des parties III et IV. Dans cette partie, A désigne une matrice positive de MAR). II.A * Réduction d'un chemin a un chemin élémentaire Montrer que s'il existe dans A un chemin de i vers j, avec i # j, alors il existe un chemin élémentaire de i vers j et de longueur EUR < n -- 1. De même, montrer que s'il existe dans A un circuit passant i, alors il existe un circuit élémentaire passant par i et de longueur EUR < n. II.B * Une caractérisation de l'emistence d'un chemin de i à j Soit A 2 0 dans MAR). Soit i, j dans [[1, n]]. Soit m 2 1. Montrer l'équivalence des propositions : -- il existe dans A un chemin d'origine i, d'extrémité j, de longueur m ; -- le coefficient d'indice i, j de A... (noté aïîÿ' ) est strictement positif. On pourra procéder par récurrence sur l'entier m 2 1. II.C * Chemins dans une puissance de A Soit i, j dans [[1,n]], et soit EUR et m dans D\l*. Montrer l'équivalence des propositions : -- il existe dans A... un chemin d'origine i, d'extrémité j, de longueur EUR ; -- il existe dans A un chemin d'origine i, d'extrémité j, de longueur mt . III Matrices primitives et indice de primitivité Soit A dans MAR), avec A > 0. On dit que A est primitive s'il existe m 2 1 tel que A... > 0. Avec cette définition, il est clair que toute matrice carrée strictement positive est primitive. Dans toute la suite, matrice primitive signifie matrice carrée positive primitive. Si A est primitive, on appelle indice de primitivité de A le plus petit entier m 2 1 tel que A... > O. III.A * Chemins élémentaires dans une matrice primitive Soit A une matrice primitive de MAR) Montrer que pour tous i 7': j il existe dans A un chemin élémentaire de i à j et de longueur EUR < n -- 1, et que pour tout i il existe dans A un circuit élémentaire passant par i et de longueur EUR < n. III.B * Puissances d'une matrice primitive III.B.1) Donner un exemple simple d'une matrice carrée primitive mais non strictement positive. III.B.2) Soit B > 0 dans MAR) et a: 2 0 dans R" avec sc % 0. Montrer que Br > O. III.B.3) Soit A une matrice primitive et m EUR IN* tel que A... > 0. Montrer que Vp } m, A?" > 0. On pourra remarquer, en le justifiant, qu'aucune des colonnes 01,02, ...,c,, de A n'est nulle. III.B.4) Prouver que si A est primitive, alors A'" est primitive pour tout le 2 1. III.B.5) Montrer que le rayon spectral d'une matrice primitive est strictement positif. III.C * La matrice de Weilandt On définit la matrice W,, = (w,_,--) de MAR) par w- - : ,, 1 sii=netjEUR{1,2} {lsi1--*O OO>--'OO Ol--'OOO 2016--02--15 20:21:43 Page 2/6 @c) BY--NC-SA Le but de cette question est de prouver que W,, est primitive, d'indice de primitivitê n2 -- 2n + 2. III.C.1) Montrer que le polynôme caractéristique de W" est X " -- X + 1. "il n+1 -- 2 -- 2 En déduire Wgac2... : î (Z 1) W];, puis que W;2*2"+2 : I,, + W,, + E (2 2) WË. k=1 _ k=2 _ III.C.2) Préciser le plus court circuit passant par l'indice 1 dans la matrice W,,. +2n+1 En déduire que la matrice ositive W"2 n'est as strictement ositive. p ,, p p III.C.3) Montrer que pour tous i, j de [[1, 11], avec i # j, il existe dans W,, au moins un chemin d'origine i, d'extrémité j, et de longueur inférieure ou égale à n -- 1. On pourra traiter successivement les deux cas 1 $ {i,j} et 1 EUR {i,j}. ; . . 2Î . . . En dedu1re que la matrice W: 2"+2 est strictement p051t1ve et conclure. III.D + Indice de primitivitë maæimum Le but de cette sous--partie est de prouver que si A G M,,(lR) est primitive, on a toujours A"2*2"+2 > O, c'est--à-- dire que l'indice de primitivité de A est inférieur ou égal à n2 -- 2n + 2. Ce majorant est en fait un maximum, comme on l'a vu avec la matrice W" de Weilandt dans la question précédente. Dans toute cette sous--partie, A est une matrice primitive donnée dans M,,(lR). On peut donc appliquer à la matrice A les résultats de la question HLA. En particulier, on note EUR EUR [[1, n]] la plus petite longueur d'un circuit élémentaire de A. III.D.1) Par l'absurde, on suppose EUR = n. Montrer qu'alors tous les circuits de A sont de longueur multiple de n. En déduire que les matrices A'""+1 (avec [EUR EUR IN) sont de diagonale nulle et aboutir à une contradiction. III.D.2) D'après ce qui précède, il existe dans A un circuit élémentaire C' de longueur EUR g n -- 1. Pour simplifier la rédaction, et parce que cela n'enlève rien à la généralité du problème, on suppose qu'il s'agit du circuit 1 --> 2 --> --> EUR-- 1 --> EUR --> 1 (les n--EUR indices restants Æ+ 1, É+ 2, ..., n étant donc situés « en dehors » du circuit 8). Nous allons montrer que A"+Ë(n*2> est strictement positive. Pour cela, on se donne i et j dans [[1,n]]. Tout revient à établir qu'il existe dans A un chemin d'origine i, d'extrémité j et de longueur n + EUR(n -- 2). a ) Montrer que dans A, on peut former un chemin d'origine i, de longueur n -- EUR , et dont l'extrémité est dans {1, 2, EUR} (on notera k cette extrémité). On pourra traiter le cas 1 < i { EUR, puis le cas Æ+ 1 { i g n. b) Dire pour quelle raison les EUR premiers coefficients diagonaux de A5 (et en particulier le k--ième) sont strictement positifs. Montrer alors qu'il existe un chemin de longueur n -- 1 dans AË (c'est--à--dire un chemin de longueur EUR (n -- 1) dans A) d'origine le et d'extrémité j. c) En déduire finalement A"+Ë(n*2l > 0, puis A"L2n+2 > 0. IV Étude des puissances d'une matrice primitive Cette partie utilise uniquement la définition des matrices primitives : elle est pratiquement indépendante de la partie 111. Par ailleurs, les résultats de la partie IV ne seront pas réutilisés dans les parties V et VI. Pour toute matrice primitive A dans M,,(lR), on admet le résultat suivant : Le rayon spectral p(A) de A (dont on sait qu 'il est strictement positif) est une valeur propre dominante de A et le sous--espace propre associé est une droite vectorielle qui possède un vecteur directeur oe > 0. Dans toute cette partie, on se donne une matrice primitive A de M,,(lR). Pour simplifier les notations, on note r (plutôt que p(A)) le rayon spectral de A. On rappelle que r > 0. Il est clair que AT est primitive, et que A et AT ont le même rayon spectral r. On peut donc noter 95 (respectivement y) un vecteur directeur strictement positif de la droite D : Ker(A--rI,,) (respectivement de la droite A : Ker(AT -- rl,,)). On note H : lm(A -- rl"). Quitte à multiplier y par un coefiicient strictement positif adéquat, on suppose (y | oe) : yT a: : 1. On note L : scyT (c'est un élément de M,,(lR)). IV.A + Puissances de la matrice B : A -- rL IV.A.1) Montrer que H est l'hyperplan orthogonal a la droite A (c'est--à--dire H : Al). 2016--02--15 20:21:43 Page 3/6 @c) BY--NC-SA IV.A.2) Prouver que L est la matrice, dans la base canonique, de la projection de il?" sur la droite D, parallè-- lement à l'hyperplan H. IV.A.3) Vérifier que L est de rang 1, qu'elle est strictement positive, et que LT y : y. IV.A.4) Montrer que AL : LA : rL. En déduire : Vm EUR IN*, (A -- rL)m : A'" -- rmL. IV.B + La matrice B : A --rL vérifie p(B) < r Dans cette question, on pose B = A -- rL. On va montrer que p(B) < r et en déduire un résultat intéressant sur la suite des puissances successives de A. Soit A une valeur propre non nulle de B et soit 2 un vecteur propre associé. IV.B.1) Montrer que Lz : 0, puis Az : Àz. En déduire p(B) { r. IV.B.2) Par l'absurde, on suppose p(B) : r. On peut donc choisir À de telle sorte que |À| : r. Montrer qu'alors À : r puis Lz : z et aboutir à une contradiction. Conclure. 1 TTL IV.B.3) Déduire de ce qui précède (et de la sous--partie IV.A) que lim (--A) : L. me+oo r IV.C + Le rayon spectral de A est une valeur propre simple Dans cette sous--partie, on montre que la valeur propre dominante de A (c'est--à--dire son rayon spectral r) est simple (on sait déjà que le sous--espace propre associé est une droite vectorielle). Soit u la multiplicité de r comme valeur propre de A et soit T : PAPÎ1 une réduite triangulaire de A. ... En examinant la diagonale de (--T) quand m --> +00, montrer que la : 1. r V Matrices carrées positives irréductibles Soit A : (d,-1j) dans M,,(iR), avec A 2 0. On dit que A est irréductible si, pour tous i et j dans [[1,n]], il existe £Î}' > 0. Avec cette définition, il est clair que toute matrice primitive est irréductible. m 2 0 (dépendant a priori de i et j) tel que a Dans toute la suite, matrice irréductible signifie matrice carrée positive irréductible. Dans toute cette partie, A est une matrice positive donnée dans M,,(lR). V.A + Premières propriétés des matrices irréductibles V.A.1) Exprimer l'irréductibilité de A en termes de chemins dans A. V.A.2) Montrer que si A est irréductible, alors pour tous i et j dans [[1, n]], il existe m EUR [[0, n-- l]] (dépendant () ,-Îÿ>0. a priori de i et ]) tel que a V.A.3) Donner un exemple simple d'une matrice carrée irréductible mais non primitive. V.A.4) Montrer que si A n'est pas irréductible, alors A2 n'est pas irréductible. En revanche, donner un exemple simple d'une matrice A irréductible telle que A2 ne soit pas irréductible. V.A.5) Montrer que le rayon spectral d'une matrice irréductible est strictement positif. V.B + Deum caractérisations de l'irréductibilité et une condition nécessaire V.B.1) Pour la matrice positive A de M,,(iR), montrer que les conditions suivantes sont équivalentes : -- la matrice A est irréductible ; -- la matrice B = l,, + A + A2 + + A"*1 est strictement positive ; -- la matrice C = (l,, + A)"*1 est strictement positive. V.B.2) Soit A irréductible. Montrer qu'aucune ligne (et aucune colonne) de A n'est identiquement nulle. V.C + Deuæ conditions suffisantes de primitivité Dans cette question, A est une matrice irréductible donnée. V.C.1) On suppose que Vi EUR [[1, n]], a,-y,- > 0. Montrer que A"*1 > 0 (donc A est primitive). On raisonnera en termes de chemins dans A. V.C.2) On suppose que : Ei EUR [[1, n]], a...- > 0. Montrer que A est primitive. Pour tous j et le dans |Ïl,n]], on pourra montrer qu'il existe dans A un chemin dej à le et passant par i, et considérer le maximum m des longueurs des chemins ainsi obtenus. On prouvera que A... > 0. 2016--02--15 20:21:43 Page 4/6 @c) BY--NC-SA VI Le coefficient d'imprimitivité Soit A : (a...--) dans M,,(lR), avec A 2 0. On dit que A est imprimitive si A est irréductible mais n'est pas primitive. Pour toute matrice A imprimitive dans Mn(lR), on admet le résultat suivant : Les valeurs propres À de A telles que |À| : p(A) sont simples. Ce sont les solutions de l'équa-- tion À" : p(A)p pour un certain entier p 2 2. En particulier p(A) est valeur propre simple de A. Plus généralement, la totalité du spectre de A est invariante dans la multiplication par a; : exp(2i7r/p). Par ailleurs, et pour la valeur propre p(A), la matrice A possède un vecteur propre a: > O. L'indice p 2 2 dont il est question dans le résultat précédent est appelé le coefiicient d'imprimitivité de A. Remarque : si on rapproche ce qui précède et le résultat admis au début de la partie IV, on peut fort bien dire qu'une matrice primitive a pour coefficient d'imprimitivité p = 1. VI.A + Diagonales des puissances d'une matrice imprimitive Soit A une matrice imprimitive de coefficient d'imprimitivité p 2 2. Pour tout entier m non multiple de p, montrer que la diagonale de A... est identiquement nulle. On pourra s'intéresser à la trace de A'". En déduire que le résultat de la question IV.B.3 ne tient plus si A est imprimitive. VI.B + Une matrice de Weilandt « modifiée » 1 sil (donc fiq : w). Montrer que flr est valeur propre de A et conclure. VI.B + Coeficient d'imprimitiuité et longueur des circuits Dans cette question, on va établir un théorème de Romanovsky en 1936, établissant que le coefficient d'impri-- mitivité p d'une matrice irréductible (éventuellement p = 1 dans le cas d'une matrice primitive) est le pgcd des longueurs des circuits passant un indice donné (ce pgcd ne dépendant en fait pas de l'indice en question). Soit A E M,,(Ü?) une matrice irréductible. Pour tout i de [[1,n]], on note L,- : {m G N*, aîZ-" > O} l'ensemble (non vide) des longueurs des circuits de A qui passent par i, et on note di le pgcd des éléments de Li. () (> 13 >0et ai,- >0. Pour tout [EUR dans {0} U Lj, montrer que d,,- divise r + k + s. En déduire que d,,- divise dj. VI.B.1) Soit i,j dans [[1,n]]. On sait qu'il existe r et s dans N tels que a Par symétrie, il en résulte évidemment que tous les d,- sont égaux. On note d leur valeur commune. VI.B.2) Montrer que si p = 1 (c'est--à--dire si A est primitive), alors ol : 1 (utiliser la question lll.B.3). 2016--02--15 20:21:43 Page 5/6 @c) BY--NC-SA VI.D.3) Dans la suite de cette question, on suppose p 2 2. Montrer que p divise d (utiliser la question VIA). VI.D.4) On va montrer que d divise p. Il en résultera bien sûr l'égalité d : p. On rappelle que la diagonale de A est nulle (c'est une conséquence de la question VIA). Soit XA(OE) : det (OEIn -- A) le polynôme caractéristique de A. 11 On sait que XA(oe) : î: e(a) H{OEIn -- A]jya..., où la somme est étendue aux permutations a de [[1,n]]. cr j=1 On fixe une permutation a de [[1, 71], on pose \IJ(a) : H{oeln -- Alj,a(j) et on suppose \IJ(U) % 0. j=1 On note H l'ensemble des éléments j de [[1,n]] tels que a(j) % j, et card(H) : h, avec 0 < h < n. a) Montrer que \IJ(U) : (--1)hæ"*h H ajya(j). jEURH b) La restriction à H de la permutation a se décompose en produits de cycles a supports disjoints (et de longueur 2 2 puisque par hypothèse aucun des éléments de H n'est invariant par 0"). Soit 5 : (j1, j2, ..., j...), avec m 2 2, l'un quelconque des cycles entrant dans cette décomposition. Montrer que j1 _) j2--n --> j... +) j1 est un circuit dans la matrice A. En déduire que m, puis h, sont des multiples de d. c) Montrer finalement que XA(:c) s'écrit : XA (a:) = a:" + a1æ"*d + a2æ"*2d + + akx"*kd + En déduire que d est un diviseur de p (utiliser le résultat de la question VLC). Conclure. oooFlNooo 2016--02--15 20:21:43 Page 6/6 @c) BY--NC-SA

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


 Centrale Maths 1 MP 2016 -- Corrigé Ce corrigé est proposé par Damien Garreau (ENS Ulm) ; il a été relu par Loïc Devilliers (ENS Cachan) et Benjamin Monmege (Enseignant-chercheur à l'université). Ce sujet est consacré à l'étude des matrices à coefficients positifs, et plus précisément à certaines sous-classes de ces matrices : les matrices primitives et irréductibles. · Dans la première partie, on montre que les itérés d'une matrice convergent vers 0 lorsque le rayon spectral de cette matrice est strictement inférieur à 1. Les résultats nécessaires concernant les normes matricielles sont redémontrés. Les résultats de cette première partie ne sont utilisés que dans la partie IV. · La deuxième partie introduit la notion de chemin dans une matrice positive. Les résultats de cette partie sont utilisés constamment dans la suite du sujet : il est nécessaire de bien les comprendre. · Une matrice telle que Am > 0 pour un certain m est dite primitive. On montre dans la troisième partie que m 6 n2 - 2n + 2, et que cette borne est atteinte 2 au sens où il existe une matrice primitive Wn telle que Wn n -2n+1 n'est pas strictement positive. · La quatrième partie est consacrée à l'étude des puissances d'une matrice primitive. On montre à la fin de cette partie que le rayon spectral d'une matrice primitive est une valeur propre simple. · Dans la partie V, on introduit la notion de matrice irréductible, qui est un peu plus faible que celle de matrice primitive. Quelques propriétés et caractérisations des matrices irréductibles sont démontrées, dont certaines sont utilisées dans la dernière partie. · La partie VI concerne les matrices imprimitives, c'est-à-dire irréductibles mais non primitives. Le coefficient d'imprimitivité est un entier qui mesure ce « défaut ». Le théorème de Perron-Frobenius est admis et utilisé pour démontrer un résultat de Romanovsky (1936) qui relie le coefficient d'imprimitivité au plus grand diviseur commun des longueurs des circuits passant par un indice donné. Ces six parties sont de difficulté à peu près constante. Le théorème du rang et le théorème de Cayley-Hamilton sont les principaux outils utilisés. L'ensemble est trop long pour espérer le terminer dans le temps imparti. Le sujet est intéressant : il amène à démontrer un résultat moderne en admettant un résultat classique, le théorème de Perron-Frobenius. Il peut toutefois être déroutant dans la mesure où il considère les matrices d'une manière inhabituelle pour un sujet de concours, mais qui prend tout son sens dans le cadre de la théorie des probabilités, où une matrice positive (convenablement renormalisée) est associée aux probabilités de transition d'une chaîne de Markov sur un graphe. Il est probable que ce point de vue sera de nouveau exploité par de futurs sujets. Indications I.A.1 I.B.1 I.B.2 II.C III.A III.B.1 III.B.4 III.B.5 III.C.1 III.C.2 III.C.3 Ne pas oublier de montrer que N est une norme. b Calculer T. b Remarquer que kAk = N(T). m Remarquer que (A ) = Am . Se servir de la question II.B. Construire un exemple avec n = 2. Appliquer le résultat de la question III.B.3 à la matrice Ak . Utiliser la question III.B.4. Calculer le déterminant en développant par rapport à la première colonne. Utiliser la question III.C.1. Se servir de la question III.C.1. (kn+1) III.D.1 Remarquer que ai,i = 0, puis utiliser la question III.B.3 pour aboutir à une contradiction. III.D.2.b Utiliser la question II.C. IV.A.1 Montrer que H est un hyperplan grâce au théorème du rang, puis utiliser t t la propriété (Xu | v) = (u | X v) pour montrer que H = . IV.A.2 Montrer que L est une projection, puis que Im (L) = D et Ker (L) = H. t IV.A.3 Utiliser y x = 1. m IV.C Calculer Tr [((1/r)A) ]. V.A.2 Utiliser la question II.A. V.A.3 Chercher un exemple avec n = 2. V.A.5 Raisonner par l'absurde. Utiliser le fait qu'une matrice dont toutes les valeurs propres sont nulles est nilpotente, puis construire un chemin de longueur arbitrairement grande. V.B.2 Si une ligne de A est nulle, alors elle est nulle pour tous les Am avec m N . V.C.1 Construire un chemin de longueur n - 1 entre i et j en remarquant qu'on peut concaténer des chemins de longueur a et b pourvu que le point d'arrivée du premier soit le point de départ du second, et que la longueur du chemin obtenu est alors a + b. V.C.2 Pour tous j et k, montrer qu'il existe un chemin de j à k passant par i, puis considérer la longueur maximale m de tels chemins. Compléter ensuite ces chemins pour qu'ils soient tous de longueur m et montrer que Am > 0. VI.A Décrire précisément le spectre de A, puis écrire Tr (Am ). Utiliser le fait que la somme des mh pour 0 6 h 6 p - 1 est nulle si m n'est pas multiple de p. VI.B.2 Calculer directement le déterminant en développant par rapport à la première colonne, puis remarquer que Zn n = 2Zn . VI.C.1 Écrire les coefficients du polynôme caractéristique en fonction des fonctions symétriques élémentaires. Remarquer que celles-ci sont à la fois homogènes et invariantes par permutation. VI.C.2 Remarquer que kj = 1, puis utiliser le fait que r annule A . VI.D.3 Montrer que Li {kp | k N}. VI.D.4.a Séparer le produit en un produit sur H multiplié par un produit sur le complémentaire de H, puis utiliser la définition de H. VI.D.4.c Utiliser les questions VI.D.4.a et VI.D.4.b. I. Si (A) < 1, alors lim Am = 0 m+ I.A.1 Montrons que l'application N : Mn (K) - R+ est une norme. · Soit A Mn (K) telle que N(A) = 0. D'après la définition de N, n P 1 6 i 6 n |ai,j | = 0 j=1 Comme tous les termes de cette somme sont positifs, ai,j = 0 pour tous i et j. On en déduit A = 0. · Soient K et A Mn (K). On a n P N(A) = Max 16i6n j=1 n P = Max || |ai,j | = Max || n P 16i6n j=1 16i6n = || Max j=1 n P 16i6n j=1 et donc N(A) = || N(A) (par définition) |ai,j | (par homogénéité de |·|) |ai,j | (par linéarité) |ai,j | (car || > 0) · Soient A et B deux éléments de Mn (K). On a N(A + B) = Max n P 16i6n j=1 n P 6 Max 16i6n j=1 n P 6 Max 16i6n j=1 par suite (par définition) |ai,j + bi,j | (inégalité triangulaire) (|ai,j | + |bi,j |) |ai,j | + Max n P 16i6n j=1 N(A + B) 6 N(A) + N(B) |bi,j | La séparation, l'homogénéité et l'inégalité triangulaire sont vérifiées, N est une norme sur Mn (K). Montrons maintenant qu'elle est sous-multiplicative. Soient A et B Mn (K), n P N(AB) = Max |(AB)i,j | 16i6n j=1 = Max n n P P 16i6n j=1 k=1 n P n P N(AB) 6 Max 16i6n j=1k=1 ai,k bk,j |ai,k bk,j | par l'inégalité triangulaire. Par conséquent, n n P P N(AB) 6 Max |ai,k | |bk,j | 16i6n k=1 n P 6 Max 16i6n k=1 et finalement Ainsi, j=1 [|ai,k | N(B)] N(AB) 6 N(A)N(B) L'application N est une norme sous-multiplicative sur Mn (K). I.A.2 Montrons que k · k est une norme. · Soit A Mn (K) telle que kAk = N(Q-1 AQ) = 0. D'après la question I.A.1, la fonction N est une norme donc Q-1 AQ = 0. Comme Q est inversible, A = 0. · Soient A Mn (K) et K. Alors kAk = N(Q-1 (A)Q) = N((Q-1 AQ)) et d'après la question I.A.1, kAk = || kAk. · Soient A, B Mn (K). (définition de k · k) kA + Bk = N(Q-1 (A + B)Q) = N(Q-1 AQ + Q-1 BQ) (question I.A.1) 6 N(Q-1 AQ) + N(Q-1 BQ) kA + Bk 6 kAk + kBk Ainsi k · k est une norme. Montrons qu'elle est sous-multiplicative. Soient A et B Mn (K), kABk = N(Q-1 (AB)Q) = N (Q-1 AQ)(Q-1 BQ) (question I.A.1) 6 N(Q-1 AQ)N(Q-1 BQ) kABk 6 kAkkBk L'application k · k est une norme sous-multiplicative sur Mn (K). I.B.1 L'ensemble des matrices triangulaires supérieures est stable par multiplication b est triangulaire par des matrices diagonales. Comme et -1 sont diagonales, T supérieure. Notons ti,j les éléments de la matrice T. Il est clair que Calculons -1 = diag(1, -1 , . . . , -(n-1) ) t1,1 t1,2 2 t1,3 ··· 0 t t ··· 2,2 2,3 . . . .. .. b = -1 T = .. T . .. .. . tn-1,n-1 0 ··· ··· 0 n-1 t1,n n-2 t2,n .. . tn-1,n tn,n b Définissons Soit 1 6 i 6 n. Notons b ti,j les éléments de la matrice T. fi () = n P j=1 b ti,j = |ti,i | + |ti,i+1 | + · · · + n-i |ti,n | On remarque que les ti,i sont les valeurs propres de A, et par conséquent tous de module strictement inférieur à 1, puisque (A) < 1. On en déduit que fi (0) < 1 pour tout i. Pour tout i, on déduit de la continuité des fi l'existence d'un réel strictement positif i tel que fi (i ) < 1. Soit = Min i > 0. Comme fi est une fonction 16i6n b = Max fi (), ce qui prouve que croissante pour tout i, fi () < 1. De plus, N(T) 16i6n b est triangulaire supérieure et on peut choisir tel que N(T) b < 1. T