Centrale Maths 2 MP 2012

Thème de l'épreuve Suites récurrentes linéaires et matrices de Hankel
Principaux outils utilisés algèbre linéaire, idéaux, diagonalisation
Mots clefs matrices de Hankel, suites récurrentes linéaires, théorème spectral

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


MP 4 heures Calculatrices autorisées 2012 Mathématiques 2 Ce sujet est divisé en trois parties. La partie III est indépendante des deux premières (même si les parties II et III ont en commun de s'intéresser à des matrices dites de Hankel). Il est attendu des candidat(e)s qu'ils fassent preuve de qualités de rédaction, de clarté et de présentation. Notations Dans tout le problème, K désigne indifféremment R ou C. On note KN l'espace vectoriel des suites à valeurs dans K. Pour tout espace vectoriel E sur K, on note L(E) l'algèbre des endomorphismes de E. On note l'élément de L(KN ) qui à tout x = (xn )nN de KN associe y = (yn )nN dans KN de terme général yn = xn+1 . On note K[X] l'algèbre des polynômes à coefficients dans K, et Km [X] le sous-espace vectoriel de K[X] formé des polynômes de degré inférieur ou égal à m. On rappelle qu'un polynôme non nul est dit unitaire si le coefficient de son monôme de plus haut degré vaut 1. On note Mn (K) l'algèbre des matrices carrées d'ordre n à coefficients dans K. Si M est une matrice carrée, on note t M sa transposée et tr(M ) sa trace. On note Sn (R) l'ensemble des matrices carrées symétriques d'ordre n à coefficients réels. Rappels sur les polynômes d'endomorphisme On effectue ici quelques rappels utiles sur les polynômes d'endomorphisme d'un espace vectoriel. Soit E un espace vectoriel sur K. On note Id l'endomorphisme identité de E. p p Ø Ø ak f k (avec la convention f 0 = Id). Pour tout f de L(E), et tout A = ak X k de K[X], on note A(f ) = k=0 k=0 Pour tout f de L(E), l'application A Ô A(f ) est alors un morphisme d'algèbres de K[X] dans L(E). Rappelons que cela signifie que, pour tous A, B de K[X] et pour tous scalaires , de K, on a : - (A + B)(f ) = A(f ) + B(f ) ; - si A = 1, alors A(f ) = Id ; - (AB)(f ) = A(f ) B(f ) = B(f ) A(f ). Cas particulier (utile dans la suite du problème) : p p Ø Ø - Si E = KN , f = et A = ak X k , alors A() = ak k . k=0 k=0 - Pour tout x de KN , y = A()(x) est donc la suite de terme général yn = p Ø ak xn+k . k=0 I Suites récurrentes linéaires Soit p un entier naturel. On dit qu'un élément x de KN est une suite récurrente linéaire (en abrégé une srl) d'ordre p > 0 s'il existe un p Ø polynôme A = ak X k dans K[X] de degré p, tel que A()(x) soit la suite nulle, c'est-à-dire si : k=0 n N p Ø ak xn+k = ap xn+p + ap-1 xn+p-1 + · · · + a1 xn+1 + a0 xn = 0 (I.1) k=0 On dit que la relation I.1 (dans laquelle, rappelons-le, ap est non nul) est une relation de récurrence linéaire d'ordre p, dont A est un polynôme caractéristique. L'ensemble des suites x de KN qui obéissent à I.1 est noté RA (K). On note R(K) l'ensemble de toutes les suites récurrentes linéaires, quel que soit leur ordre (autrement dit, R(K) est la réunion des RA (K) pour tous les polynômes A non nuls dans K[X]). I.A ­ Ordre (et polynôme) minimal d'une suite récurrente linéaire Soit x une suite récurrente linéaire. 2 avril 2012 17:21 Page 1/4 Montrer que l'ensemble Jx des polynômes A tels que A()(x) = 0 est un idéal de K[X], non réduit à {0}. On rappelle qu'il en résulte deux choses : - d'une part, il existe dans Jx un unique polynôme unitaire B de degré minimal ; - d'autre part, les éléments de Jx sont les multiples de B. Par définition, on dit que B est le polynôme minimal de la suite x, que le degré de B est l'ordre minimal de x, et que la relation B()(x) = 0 est la relation de récurrence minimale de x. I.B ­ Quelques exemples I.B.1) Dans KN , quelles sont les suites récurrentes linéaires d'ordre 0 ? d'ordre 1 ? Quelles sont les suites de KN dont le polynôme minimal est (X - 1)2 ? I.B.2) On considère la suite x définie par x0 = 0, x1 = -1, x2 = 2 et par la relation de récurrence linéaire d'ordre 3 : n N, xn+3 = -3xn+2 - 3xn+1 - xn . Déterminer le polynôme minimal (et donc l'ordre minimal) de la suite x. I.C ­ L'espace vectoriel RA (K) et deux cas particuliers p Ø Soit A = ak X k un élément de K[X], de degré p > 0, que sans perdre de généralité on suppose unitaire. k=0 I.C.1) Prouver que RA (K) est un sous-espace vectoriel de dimension p de KN et qu'il est stable par (on ne demande pas ici de déterminer une base de RA (K), car c'est l'objet des questions suivantes). I.C.2) Déterminer RA (K) quand A = X p (avec p > 1) et en donner une base. I.C.3) Dans cette question, on suppose p > 1 et A = (X - )p , avec dans K . On note EA (K) l'ensemble des x de KN de terme général xn = Q(n)n , où Q est dans Kp-1 [X]. a) Montrer que EA (K) est un sous-espace vectoriel de KN dont on précisera la dimension. b) Montrer l'égalité RA (K) = EA (K). I.D ­ Étude de RA (K) quand A est scindé sur K Dans cette question, on suppose que le polynôme A est scindé sur K. d Ù Plus précisément, on note A = X m0 (X - k )mk , où : k=1 - les scalaires 1 , 2 , . . . , d sont les racines non nulles distinctes éventuelles de A dans K, et m1 , m2 , . . . , md sont leurs multiplicités respectives (supérieures ou égales à 1). Si A n'a pas de racine non nulle, on convient d Ù que d = 0 et que (X - k )mk = 1 ; k=1 - l'entier m0 est la multiplicité de 0 comme racine éventuelle de A. Si 0 n'est pas racine de A, on adopte la convention m0 = 0. d Ø mk = deg A = p. Avec ces notations, on a k=0 En utilisant le théorème de décomposition des noyaux, montrer que RA (K) est l'ensemble des suites x = (xn )n>0 de KN telles que : n > m0 , xn = d Ø Qk (n) nk k=1 où, pour tout k de {1, . . . , d}, Qk est dans K[X] avec deg Qk < mk . d Ø Remarque : si d = 0, la somme Qk (n) nk est par convention égale à 0. k=1 II Matrices de Hankel associées à une suite récurrente linéaire Soit x dans KN . Pour tout entier n de N , on note Hn (x) la matrice de Mn (K) définie par (i, j) {1, . . . , n}2 , [Hn (x)]i,j = xi+j-2 x0 x1 x2 x3 x2 x1 x2 x3 x4 x0 x1 On a par exemple H2 (x) = x3 et H4 (x) = x2 x3 x4 x5 . x1 x2 x4 x3 x4 x5 x6 n On identifie toute matrice de Mn (K) avec l'endomorphisme de K qui lui est associé dans la base canonique. On identifie de même tout élément de Kn avec la matrice-colonne qui lui correspond. 3 2 avril 2012 17:21 4 x0 , H3 (x) = x1 x2 x1 x2 x3 Page 2/4 II.A ­ Calcul du rang de Hn (x) quand x est une suite récurrente linéaire Dans cette section, x est une suite récurrente linéaire d'ordre minimal p > 1 et de polynôme minimal B. II.A.1) Montrer que la famille ( k (x))06k6p-1 est une base de RB (K). En déduire, pour tout n de N , le rang de la famille ( k (x))06k6n-1 . ; RB (K) Kn est injective. II.A.2) Montrer que si n > p, l'application n : v Ô (v0 , . . . , vn-1 ) En déduire que si n > p, alors rang(Hn (x)) = p. Remarque : il est clair que ce résultat reste vrai si p = 0 (car la suite x et les matrices Hn (x) sont nulles). II.B ­ Détermination de la récurrence minimale d'une suite récurrente linéaire Soit x une suite récurrente linéaire non nulle, d'ordre m > 1. Soit p = rang(Hm (x)). II.B.1) Montrer que x est d'ordre minimal p et que le noyau de Hp+1 (x) est une droite vectorielle dont un vecteur directeur peut s'écrire (b0 , . . . , bp-1 , 1), où b0 , . . . , bp-1 sont dans K. II.B.2) Avec ces notations, montrer que le polynôme minimal de x est B = X p + bp-1 X p-1 + · · · + b1 X + b0 . II.C ­ Étude d'un exemple Dans cette question, on considère la suite x = (xn )n>0 définie par x0 = 1, x1 = 1, x2 = 1, x3 = 0, et n N, xn+4 = xn+3 - 2 xn+1 II.C.1) Dans le langage informatique de votre choix (que vous préciserez), écrire une procédure (ou fonction) de paramètre un entier naturel n et renvoyant la liste (ou la séquence, ou le vecteur) des xk pour 0 6 k 6 n. II.C.2) Préciser le rang de Hn (x) pour tout entier n de N et indiquer l'ordre minimal de la suite x. II.C.3) Déterminer la relation de récurrence minimale de la suite x. II.C.4) Donner une formule permettant pour tout n > 1 de calculer directement xn . II.C.5) On décide de modifier uniquement la valeur de x0 , en posant cette fois x0 = 1 . 2 Avec cette modification, reprendre rapidement l'étude des questions II.C.2 et II.C.3. III Valeurs propres des matrices de Hankel réelles Dans toute cette partie, n désigne un entier supérieur ou égal à 3. On note p = [(n + 1)/2] la partie entière de (n + 1)/2. On a donc n = 2p si n est pair, et n = 2p - 1 si n est impair. Rn est muni de sa structure euclidienne canonique dont le produit scalaire est noté é·, ·ê et la norme associée est notée ë · ë. Un élément de x = (x1 , . . . , xn ) de Rn est dit ordonné s'il vérifie si x1 > x2 > . . . > xn . On dit qu'une matrice M = (mi,j )16i,j6n de Mn (R) est une matrice de Hankel s'il existe a = (a0 , . . . , a2n-2 ) R2n-1 tel que pour tous i et j de {1, . . . , n}, mi,j = ai+j-2 . Une telle matrice est notée M = H(a). III.A ­ Préliminaires III.A.1) Montrer que si M est une matrice de Hankel de taille n alors elle admet n valeurs propres réelles 1 , . . . , n (chacune étant répétée autant de fois que sa multiplicité) que l'on peut classer dans l'ordre décroissant 1 > 2 > . . . > n . On note alors Spo(M ) = (1 , . . . , n ) le spectre ordonné de la matrice M , c'est-à-dire le n-uplet ordonné des valeurs propres de M . On s'intéresse au problème suivant : à quelles conditions un n-uplet ordonné de réels peut-il être le n-uplet ordonné des valeurs propres d'une matrice de Hankel de taille n ? III.A.2) Montrer que si R alors le n-uplet (, . . . , ) n'est pas le n-uplet ordonné des valeurs propres d'une matrice de Hankel de taille n. III.B ­ Une première condition nécessaire Soit a = (a0 , . . . , a2n-2 ) un élément de R2n-1 et M = H(a). On note Spo(M ) = (1 , . . . , n ). On définit deux vecteurs v = (v1 , . . . , vn ) et w = (w1 , . . . , wn ) de Rn par 1 si i {1, . . . , p} vi = 2i - 1 a2(i-1) et wi = 2i - 1 1 vi = 2n - 2i + 1 a2(i-1) et wi = si i {p + 1, . . . , n} 2n - 2i + 1 On pose enfin Kn = n - ëwë2 . 2 avril 2012 17:21 Page 3/4 III.B.1) Montrer que n Ø i = i=1 n-1 Ø a2k n Ø et i=1 k=0 III.B.2) Montrer que év, wê = n Ø i et ëvë2 6 Ø n-1 Ø (k + 1) a2k + k=0 n Ø 2n-2 Ø (2n - k - 1) a2k k=n 2i . i=1 i=1 III.B.3) Montrer que 2i = (i - j )2 = n n Ø 2i - év, wê2 et en déduire l'inégalité : i=1 16i Kn n Ø 2i (III.1) i=1 16i 3(1 2 + 1 3 + 2 3 ). III.C ­ D'autres conditions nécessaires Dans cette partie, on admet le résultat suivant : si A et B sont deux matrices de Sn (R) dont les valeurs propres respectives (avec répétitions éventuelles) sont 1 > . . . > n et 1 > . . . > n alors n Ø i n+1-i 6 tr(AB) 6 n Ø i i (III.2) i=1 i=1 Soit B = (bi,j )16i,j6n la matrice de Mn (R) définie par b1,2p-1 = 1 b2p-1,1 = 1 bp,p = -2 tous les autres coefficients de B étant nuls (on rappelle que p désigne la partie entière de (n + 1)/2). III.C.1) Déterminer le spectre ordonné de la matrice B. III.C.2) Soit a = (a0 , . . . , a2n-2 ) un élément de R2n-1 et M = H(a). On note Spo(M ) = (1 , . . . , n ). Établir que 1 - n-1 - 2n > 0 et 21 + 2 - n > 0 (III.3) III.D ­ Cas n = 3 Soient 1 , 2 , 3 trois réels vérifiant 1 > 2 > 3 1 - 2 - 23 > 0 21 + 2 - 3 > 0 a b c On définit la matrice de Hankel M = H(a, b, c, b, a) = b c b , où a, b, c sont réels. c b a III.D.1) Calculer les valeurs propres de M (sans chercher à les ordonner). III.D.2) Expliciter a, b, c (avec b > 0) en fonction de 1 , 2 , 3 , de telle sorte que Spo(M ) = (1 , 2 , 3 ). III.D.3) Que peut-on déduire du résultat précédent, quant à la condition III.3 dans le cas n = 3 ? En utilisant un triplet ordonné (, 1, 1), montrer que pour n = 3, la condition III.1 n'est pas suffisante. · · · FIN · · · 2 avril 2012 17:21 Page 4/4

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


 Centrale Maths 2 MP 2012 -- Corrigé Ce corrigé est proposé par Yvon Vignaud (Professeur en CPGE) ; il a été relu par Samuel Baumard (ENS Ulm) et Benoît Chevalier (ENS Ulm). Ce sujet étudie les suites récurrentes linéaires et les matrices de Hankel qui leur sont associées. Il se compose de trois parties, la troisième étant indépendante des deux premières. · Dans la première partie on étudie l'ensemble des suites récurrentes linéaires. Après avoir défini en I.A le polynôme minimal d'une telle suite comme le polynôme engendrant son idéal annulateur, on analyse en I.B plusieurs exemples. Les sous-parties I.C et I.D étudient l'ensemble des suites récurrentes linéaires associées à un polynôme caractéristique donné lorsqu'il est scindé, d'abord dans le cas particulier où ce polynôme possède une unique racine, puis dans le cas général. · La deuxième partie traite des matrices dites « de Hankel » associées à une suite récurrente linéaire. On y montre notamment que le rang de ces matrices est lié à l'ordre de la récurrence satisfaite par la suite et que les éléments du noyau de l'une de ces matrices sont colinéaires au vecteur formé par les coefficients du polynôme minimal ; ces matrices permettent donc de déterminer rapidement un polynôme minimal. Cette partie se termine par l'étude complète d'un exemple ; on y demande d'écrire une procédure informatique renvoyant la liste des premiers termes de la suite récurrente. · Enfin, la troisième partie étudie le spectre des matrices de Hankel réelles. On établit deux conditions nécessaires pour qu'un n-uplet de réels donné soit le spectre d'une matrice de Hankel. La partie s'achève sur l'étude du cas n = 3, où la deuxième condition nécessaire s'avère suffisante, mais pas la première. La résolution de ce problème requiert une bonne compréhension du formalisme de l'algèbre linéaire pour bien identifier la nature des différents objets rencontrés (endomorphisme, vecteur, matrice, polynôme). En dehors de cette difficulté formelle, ce sujet n'exige pas de virtuosité particulière. Indications Partie I I.A Utiliser la définition des idéaux puis la relation de récurrence satisfaite par x pour montrer que Jx 6= (0). I.B.1 Considérer les suites géométriques et les suites affines. I.B.2 Montrer que le polynôme minimal est un diviseur de (X + 1)3 . I.C.1 Remarquer qu'une suite récurrente est entièrement déterminée par ses premières valeurs. I.C.2 Montrer qu'une suite annulée par Xp est nulle à partir d'un certain rang. I.C.3.a Interpréter EA (K) comme l'image de Kp-1 [X] par un morphisme injectif. I.C.3.b Montrer que ( - Id ) E(X-)k (K) E(X-)k-1 (K). d I.D Appliquer le théorème de décomposition des noyaux à B(X) = (X-k )m k=1 k . Partie II II.A.1 Supposer que la famille possède une relation de dépendance linéaire non triviale et aboutir à une contradiction sur la minimalité de p. II.A.2 Remarquer à nouveau qu'une suite récurrente est entièrement déterminée par ses premières valeurs. Montrer que les colonnes de Hn (x) sont les images par n d'une certaine famille. II.B.1 Appliquer le théorème du rang à Hp+1 (x) et remarquer que Hp (x) est une sous-matrice de Hp+1 (x). II.B.2 Montrer que les coefficients de B et les scalaires bi forment deux familles de solutions d'un même système de Cramer. II.C.2 Appliquer les résultats des questions II.B.1 et II.A.2 à H4 (x). II.C.3 Appliquer la propriété démontrée à la question II.B.2 à H4 (x). II.C.4 Factoriser le polynôme minimal et appliquer le résultat de la question I.D. II.C.5 Remarquer que changer la valeur de x0 est sans effet sur les valeurs xn suivantes, puis trouver une relation d'ordre 2 satisfaite par x. Partie III III.A.1 Remarquer que A est symétrique réelle. III.A.2 Considérer les coefficients m2,2 et m1,3 . III.B.1 Si M est diagonalisable de spectre {1 , . . . , n } alors Tr (Mk ) = n P ki . i=1 III.B.2 Utiliser le résultat de la question III.B.1 pour montrer l'égalité demandée. Pour en déduire l'inégalité, développer le carré de la norme de v. III.B.3 Symétriser la double somme en faisant apparaître les contributions j < i et en remarquant que les contributions pour i = j sont nulles. Puis développer (i - j )2 pour obtenir l'identité souhaitée. L'inégalité s'en déduit grâce à l'inégalité de Cauchy-Schwarz. III.C.1 Calculer B en développant selon la première colonne. III.C.2 Calculer Tr (MA) et conclure en utilisant la propriété admise sur les traces. III.D.1 Calculer le polynôme caractéristique de M. III.D.2 Exprimer a et c en fonction des trois valeurs propres trouvées avant d'en déduire b. I. Suites récurrentes linéaires I.A Comme le rappelle l'énoncé du problème, puisque est un endomorphisme de l'espace KN , l'application P 7 P() est un morphisme de K-algèbres. En particulier, pour tous polynômes A et B on a (A-B)() = A()-B() et (BA)() = B()A(). Soit x une suite récurrente linéaire et montrons que Jx = {A K[X] | A()(x) = 0} est un idéal de K[X] : · Par hypothèse x est récurrente, ce qui signifie qu'il existe un polynôme non nul A K[X] tel que A()(x) = 0. On en déduit que A Jx puis que Jx 6= {0}. · Soient A, B Jx . Les propriétés algébriques rappelées ci-dessus donnent (A - B)()(x) = A()(x) - B()(x) = 0 - 0 = 0 Ainsi A - B Jx . De ceci, on déduit que Jx est un sous-groupe additif de K[X] non réduit à {0}. · Soient A Jx et B K[X]. De A()(x) = 0 il vient (BA)()(x) = (B() A())(x) = B()(0) = 0 puisque B() est linéaire. On en déduit que BA Jx , ce qui montre que Jx possède la propriété d'absorption des idéaux. En conclusion, Jx est un idéal non nul de K[X]. I.B.1 Une suite x est récurrente linéaire d'ordre 0 si et seulement s'il existe a0 K tel que a0 xn = 0 pour tout n N. Comme a0 6= 0 on peut simplifier par a0 et conclure que La seule et unique suite récurrente linéaire d'ordre 0 est la suite nulle. Une suite x est récurrente linéaire d'ordre 1 si et seulement si (a0 , a1 ) K × K n N a1 xn+1 + a0 xn = 0 c'est-à-dire, en posant r = -a0 /a1 , si et seulement si r K n N xn+1 = rxn Autrement dit, Les suites récurrentes linéaires d'ordre 1 sont les suites géométriques. Soit une suite x dont le polynôme minimal est (X - 1)2 = X2 - 2X + 1, de telle sorte que n N2 xn+2 - 2xn+1 + xn = 0 2 L'équation caractéristique (r-1) = 0 correspondante admet 1 comme racine double, si bien que (, µ) K2 n N xn = + µn Si µ était nul, on aurait xn+1 - xn = 0 pour tout n N, et par suite X - 1 serait annulateur de x, ce qui contredirait la minimalité de (X - 1)2 ; par conséquent µ est non nul. Réciproquement, supposons x de la forme xn = + µn avec µ 6= 0. Comme x n'est ni constante ni géométrique, son ordre minimal est supérieur ou égal à 2, ce qui assure que son polynôme minimal B est de degré au moins 2. On sait que n N xn+2 - 2xn+1 + xn = 0 donc (X-1)2 Jx . Puisque Jx est engendré par B, celui-ci divise (X-1)2 dans K[X] ; puisqu'il est de degré au moins 2 et unitaire, B(X) = (X - 1)2 . En conclusion, Les suites de polynôme minimal (X - 1)2 sont les suites affines non constantes. I.B.2 Par définition, le polynôme P donné par P(X) = X3 + 3X2 + 3X + 1 = (X + 1)3 est un polynôme caractéristique de la relation de récurrence xn+3 + 3xn+2 + 3xn+1 + xn = 0 satisfaite par x. En conséquence, l'idéal annulateur Jx contient (X+1)3 et est engendré par un diviseur B de (X + 1)3 . Par ailleurs, comme x n'est ni nulle ni géométrique, le résultat de la question I.B.1 nous assure que le degré de son polynôme minimal B est supérieur ou égal à 2 ; comme de plus B est un polynôme unitaire, on en déduit que B(X) = (X + 1)p avec p {2, 3}. Montrons que (X + 1)2 annule x. Pour cela, montrons par récurrence que P(n) : xn+2 + 2xn+1 + xn = 0 est vraie pour tout n N. · P(0) est vraie car x2 + 2x1 + x0 = 2 - 2 + 0 = 0. · P(n) = P(n + 1) : soit n > 0 fixé et supposons que P(n) soit vraie. De la relation de récurrence linéaire satisfaite par x d'une part et de P(n) d'autre part on déduit que xn+3 + 2xn+2 + xn+1 = (xn+3 + 3xn+2 + 3xn+1 + xn ) - (xn+2 + 2xn+1 + xn ) = 0-0=0 ce qui signifie que P(n + 1) est vraie. · Conclusion : Ainsi, n > 0 xn+2 + 2xn+1 + xn = 0 x a pour polynôme minimal (X + 1)2 et est d'ordre minimal 2. En considérant les premières valeurs de x, (0, -1, 2, -3, . . .), on pouvait aussi conjecturer que n N xn = (-1)n n avant de le démontrer rapidement par récurrence. On reconnaît alors une suite du type (nn )n avec ici = 1, et donc une suite d'ordre 2 satisfaisant l'équation de récurrence linéaire xn+2 - 2xn+1 + 2 xn = 0.