Mines Maths 1 PSI 2007

Thème de l'épreuve Pseudo-inverse et matrice stochastique
Principaux outils utilisés espaces vectoriels de dimension finie, applications linéaires, matrices, changements de base, théorème du rang
Mots clefs pseudo-inverse, matrice stochastique, théorème de Perron-Frobenius

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


A 2007 MATH. I PSI ECOLE NATIONALE DES PONTS ET CHAUSSEES. ECOLES NATIONALES SUPÉRIEURES DE L'AÉRONAUTIQUE ET DE L'ESPACE, DE TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT-ÉTIENNE, DES MINES DE NANCY, DES TELECOMMUNICATIONS DE BRETAGNE. ECOLE POLYTECHNIQUE (Filière TSI). CONCOURS D'ADMISSION 2007 PREMIÈRE ÉPREUVE DE MATHÉMATIQUES Filière PSI (Durée de l'épreuve : 3 heures) L'usage d'ordinateur ou de calculette est interdit. Sujet mis à la disposition des concours : ENSAE (Statistique), ENSTIM, INT, TPE-EIVP, Cycle international Les candidats sont priés de mentionner de façon apparente sur la première page de la copie : MATHÉMATIQ UES I _ PSI. L'énoncé de cette épreuve comporte 5 pages de texte. Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre. Pseudo--inverse et matrice stochastique Pour K = R ou C, on note Mn...(K) l'ensemble des matrices a n lignes et m colonnes à coefficients dans K. Pour toute matrice M EUR Mn,n(llä), on appelle endomorphisme canoniquement associé à M , l'endomorphisme de R", noté m, dont M est la matrice dans la base canonique de R". Si M EUR M......(K), M (i, j) représente le coefficient en ligne i et colonne j de la matrice M. On note In la matrice identité de Mnn(R). La matrice (colonne) de M...fllR) dont tous les coefficients valent 1 est notée Jn. Pour M EUR M...AK), on considère la norme HMH = max ZW(?£J)l- j=1 1SiSn Définition 1 On dit qu'une matrice M EUR M......(R) est positive (respective-- ment strictement positive), lorsque tous ses coefilcients sont positifs (respec-- tivement strictement positifs) Une matrice positive M EUR M......(R) est dite stochastique lorsque M J... = J... On désigne par 76,1 C M1,n(lR) l'ensemble des matrices lignes stochas-- tiques. On admet le théorème suivant : Théorème 1 (COMP 2006, filière MP) SoitlD une matrice stochastique strictement positive de Mnn(lR). Le réel 1 est valeur propre simple de P et il eæiste un unique élément de IC... noté XO... tel que XOO : XOOP. De plus, quel que soit X EUR IC... 1 k--1 _ Xoe = ;.ËIËOOZ EXP". j=0 L'objectif de ce problème est de trouver une méthode de calcul de X00 en utilisant la notion de pseudo--inverse. Définition 2 Soit A E Mn,n(lR), une matrice A' E Mnn(R) est un pseudo-- inverse de A lorsque les trois propriétés suivantes sont satisfaites : AA' = A'A (1) A = AA'A (2) A' = A'AA'. (3) Dorénavant, P est une matrice stochastique, strictement positive, de M,,,,(R). I Préliminaires D 1 -- Montrer que HMNH 5 MM... HNH pour toutes les matricesM EUR M,,,(K) et N E M,,,,,(K). Cl 2 -- Montrer que HPH : 1. D 3 -- Montrer que pour tout k 2 l, Pk est une matrice stochastique. II Pseudo-inverse Soit A une matrice de M,,,,(R) et & l'endomorphisme de R" canonique-- ment associé. D 4 -- Montrer que l'existence d'un pseudo--inverse implique que rang(a) : rang(a2). Inversement, on suppose maintenant que rang(a) : rang(a2). On note 7° cet entier. D 5 -- Montrer que le noyau et l'image de a sont en somme directe: R" : lm(a) @ Ker(a). D 6 -- Montrer qu'il existe B E M,),(R), B inversible et W EUR M...,(R), W inversible, telles que _ B 0 _, AW+oo [EUR _ J=Ü existe et donner sa valeur. D 17 -- Montrer que (In --AA') est stochastique et que (In --AA')A : O. D 18 -- Montrer que In --AA' : JnXOO. FIN DU PROBLÈME

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


 Mines Maths 1 PSI 2007 -- Corrigé Ce corrigé est proposé par David Lecomte (Professeur en CPGE) ; il a été relu par Vincent Puyhaubert (Professeur en CPGE) et Benoît Chevalier (ENS Ulm). Les sujets de concours sur les pseudo-inverses de matrices, classiques il y a une dizaine d'années, n'avaient pas reparu depuis. Ils reviennent apparemment au goût du jour avec ce problème d'algèbre linéaire des Mines. Cet énoncé présente aussi l'originalité de construire sur le problème des Mines MP de la session 2006, dans lequel on étudie les éléments propres des matrices stochastiques strictement positives. Ces dernières sont les matrices à coefficients strictement positifs et dont la somme sur chaque ligne est égale à 1. L'année précédente, vos collègues de MP devaient montrer une version du théorème de Perron-Frobenius : une telle matrice P admet 1 comme valeur propre simple et on peut y associer un unique vecteur propre X qui soit stochastique strictement positif. L'objectif de notre problème est d'étudier les liens entre matrices stochastiques et pseudo-inverses, dans le but d'identifier ce vecteur X . On procède en trois étapes. · Dans un premier temps, on étudie des normes sur les espaces de matrices, particulièrement adaptées aux matrices stochastiques positives ; · Puis on s'intéresse à la notion de pseudo-inverse définie par l'énoncé en introduction. En particulier, on caractérise les matrices qui admettent un pseudo-inverse et on montre que dans ce cas, le pseudo-inverse est unique ; · On arrive enfin au but du problème. Plus précisément, on montre que : étant donnée une matrice P Mn,n (R) stochastique strictement positive, la matrice A = In - P admet un pseudo-inverse A . Et si, par chance, on met la main sur A , alors In - AA est une matrice dont toutes les lignes sont égales au vecteur X que l'on cherche. De difficulté moyenne, cette épreuve est assurément un très bon problème pour réviser le programme d'algèbre linéaire. L'emphase est mise sur le programme de première année de CPGE, car la partie du programme sur la réduction de matrices y a une place très marginale. Le problème permet donc de voir si le candidat est à l'aise avec la dualité entre matrices et applications linéaires, la manipulation de matrices (produits et sommes), et l'utilisation des principaux résultats dans les espaces de dimension finie. Indications I. Préliminaires 1 Utiliser la définition du produit matriciel et l'inégalité triangulaire pour majorer (MN)(i, j) . Puis sommer sur j et intervertir les sommes. La fin consiste simplement à utiliser la définition de la norme. 2 Procéder par récurrence. II. Pseudo-inverse 4 Se rappeler que si u et v sont des endomorphismes d'un espace vectoriel, alors Im (uv) Im u. Utiliser ceci pour montrer d'abord que rang a2 6 rang a ; puis, conjointement aux propriétés que possèdent a et un pseudo-inverse, pour obtenir rang a 6 rang a2 . 5 Montrer d'abord que Im a = Im a2 . Puis en déduire que Ker a + Im a = Rn . Conclure à l'aide du théorème du rang. 6 Se placer dans une base de Rn adaptée à la somme directe Rn = Im a Ker a. Le rang de B est égal au rang de A. -1 B 0 7 Vérifier que W W-1 est un pseudo-inverse de A. 0 0 8 Travailler dans la base utilisée à la question 6. 9 Montrer d'abord que Ker (aa ) = Ker a ; une inclusion est toujours vraie. L'autre utilise la relation (2) satisfaite par A du fait qu'elle admet un pseudo-inverse. En couplant ceci au théorème du rang, établir que Im (aa ) = Im a. 10 Vérifier que D, mis en évidence à la question 8, n'est autre que B-1 . III. Calcul de X 12 Montrer que 2P - P2 est stochastique. Compte tenu du fait que A = In - P et A2 = In - (2P - P2 ), montrer que a et a2 ont le même noyau, à l'aide du théorème 1 donné par l'énoncé. En déduire que Ker ac = Ker a2c ; conclure. 13 Le théorème du rang et le théorème 1 de l'introduction permettent de calculer la valeur commune de rang a et rang a2 . k-1 P 14 Poser D = In - C et calculer (In - C)j C en écrivant C en fonction de D. j=0 15 Se servir des résultats de la partie II pour écrire A et A sous forme de matrices par blocs. La matrice B est inversible donc le calcul de la question 14 peut être appliqué à In - B. Ne pas oublier, d'ailleurs, que P = In - A. 16 Les résultats de la première partie sont utiles pour majorer k(In - Pk )A k. 17 Les matrices A et A commutent donc In - AA = In - A A. Se rappeler que A s'écrit en fonction de P, qui est stochastique. 18 Appliquer le théorème 1, qui donne une manière de calculer X à partir d'un X quelconque dans Kn . Prendre, pour X, le vecteur ligne dont tous les coefficients sont nuls sauf celui en ie position qui vaut 1. I. Préliminaires 1 Soient M Mn,r (K) et N Mr,m (K). Rappelons la formule définissant le produit matriciel : MN appartient à Mn,m (K) et r P (i, j) [[ 1 ; n ]] × [[ 1 ; m ]] (MN)(i, j) = M(i, k) N(k, j) k=1 Donc kMNk = max m P 16i6n j=1 m P r P (MN)(i, j) = max M(i, k) N(k, j) 16i6n j=1 k=1 Soit i [[ 1 ; n ]]. D'après l'inégalité triangulaire, r r P P M(i, k) N(k, j) 6 |M(i, k)| |N(k, j)| j [[ 1 ; m ]] d'où k=1 r m P P M(i, k) N(k, j) 6 j=1 k=1 m P r P k=1 |M(i, k)| |N(k, j)| j=1k=1 Commençons par intervertir ces deux sommes finies : m P r r P m P P M(i, k) N(k, j) 6 |M(i, k)| |N(k, j)| k=1 j=1 j=1 k=1 | {z (S) } Dans la somme (S), les termes M(i, k) sont indépendants de l'indice de sommation, qui est j, ce qui permet de les mettre en facteur : m P r r m P P P M(i, k) N(k, j) 6 |M(i, k)| |N(k, j)| j=1 k=1 j=1 k=1 Puis, par définition de kNk, on a m P k [[ 1 ; r ]] |N(k, j)| 6 kNk j=1 d'où m P r P M(i, k) N(k, j) 6 kNk j=1 k=1 r P |M(i, k)| 6 kNk kMk k=1 Cette inégalité est valable pour tout i [[ 1 ; n ]]. On conclut donc kMNk 6 kMk kNk 2 P est une matrice stochastique de Mn,n (K), ce qui signifie que PJn = Jn . Autrement dit, puisque Jn est la matrice colonne dont tous les coefficients valent 1, i [[ 1 ; n ]] (PJn )(i, 1) = 1 En exprimant le terme général de PJn à l'aide de la définition du produit matriciel, n P i [[ 1 ; n ]] P(i, k) = 1 k=1 P est positive donc chacun de ses coefficient est positif, égal à sa valeur absolue, d'où n P i [[ 1 ; n ]] |P(i, k)| = 1 Par suite, Autrement dit, max r P 16i6n k=1 k=1 |P(i, k)| = 1 kPk = 1 3 On définit, pour tout entier k non nul, la propriété Q(k) : « Pk est une matrice stochastique. » · Q(1) est vraie par hypothèse. · Q(k) = Q(k + 1) : Pk et P sont stochastiques. Alors Pk+1 Jn = Pk (PJn ) = Pk Jn = Jn En outre, d'après la formule définissant le produit matriciel, les coefficients de Pk+1 sont des sommes de produits de coefficients de P et Pk . Ces deux matrices étant à coefficients positifs, Pk+1 est également à coefficients positifs. C'est donc une matrice stochastique et Q(k + 1) est vraie. · Conclusion : Q(k) est vraie pour tout entier k non nul. Pour tout entier k non nul, Pk est stochastique. II. Pseudo-inverse 4 Supposons que A admet un pseudo-inverse A . Notons a l'endomorphisme de Rn canoniquement associé à A . Les relations matricielles entre A et A se traduisent en termes d'endomorphismes de la manière suivante : aa = a a a = aa a et a = a aa Rappelons la relation suivante, triviale, qui peut être considérée comme du cours : si f et g sont deux endomorphismes d'un espace vectoriel E, alors Im (f g) Im f . Cela tient simplement au fait que Im (f g) = f g(E) = f (g(E)) f (E) = Im f Si E est, de plus, de dimension finie, on a rang (f g) 6 rang f puisque le rang d'une application linéaire est la dimension de son image. Les deux premières relations donnent a = a2 a . D'après la formule rappelée en remarque, rang a = rang (a2 a ) 6 rang a2 . Mais on a aussi a2 = a a donc, toujours d'après cette formule, rang a2 6 rang a. Par suite, Si A admet un pseudo-inverse, alors a et a2 ont le même rang. 5 Observons d'abord que Im a = Im a2 . En effet, l'inclusion Im a2 Im a est triviale ; de plus, d'après la question précédente, ces deux sous-espaces ont la même dimension, à savoir rg a. Maintenant, soit y Rn . Par définition, a(y) appartient à Im a, qui est égal à Im a2 comme on vient de le voir. Il existe donc x Rn tel que a(y) = a2 (x), et on a 0 = a(y) - a2 (x) = a(y - a(x)) Autrement dit, y - a(x) appartient à Ker a. On peut alors écrire y = y - a(x) + a(x) | {z } |{z} Ker a ce qui montre que Im a Rn = Ker a + Im a