Mines Maths 1 PC 2007

A 2007 MATH. I PC

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 PC

(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ÉMATIQUES I _ PC.

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

Mines Maths 1 PC 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 dernière, 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.
Cette épreuve est assurément un très bon problème, de difficulté moyenne, 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.
3 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
(i, j)  [[ 1 ; n ]] × [[ 1 ; m ]]

r
P

(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,
j  [[ 1 ; m ]]

r
P

M(i, k) N(k, j) 6

r
m P
P

M(i, k) N(k, j) 6

j=1 k=1

|M(i, k)| |N(k, j)|

k=1

k=1

d'où

r
P

m P
r
P

|M(i, k)| |N(k, j)|

j=1k=1

Commençons par intervertir ces deux sommes finies :
m
m P
r
r P
P
P
|M(i, k)| |N(k, j)|
M(i, k) N(k, j) 6
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
k  [[ 1 ; r ]]

m
P

|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
k=1

Par suite,

max

r
P

|P(i, k)| = 1

16i6n k=1

Autrement dit,

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.