Mines Maths 1 MP 2006

A 2006 MATH. 1 MP

ECOLE NATIONALE DES PONTS ET CHAUSSEES.
ECOLES NATIONALES SUPERIEURES DE L'AÉRONAUTIQUE ET DE L'ESPACE,
DE TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS,
DES MINES DE PARIS, DES MINES DE SAINT-ETIENNE, DES MINES DE NANCY,
DES TÉLÉCOMMUNICATIONS DE BRETAGNE.
ECOLE POLYTECHNIQUE (Filière TSI).

CONCOURS D'ADMISSION 2006
PREMIÈRE ÉPREUVE DE MATHÉMATIQUES
Filière MP

(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 - MP.

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.

Pour K = R ou C, on note M...;(K) l'ensemble des matrices à n lignes
et 1 colonnes à coefficients dans K. Un élément de M...;(R) sera considéré
comme élément de Mn,1(C). Dans la suite, on identifie les matrices carrées
(respectivement les matrices colonnes) et les endomorphismes (respective--
ment les vecteurs) canoniquement associés dans C'": par exemple, on note
par la même lettre une matrice T de Mn,n(R) et l'endomorphisme de C"
dont T est la matrice dans la base canonique de C".

Si ,M EUR M...(K) et a: EUR K, (M :::)2 désigne la i--ième composante du
vecteur M :1: E K". On note 1" la matrice identité de Mn,n(C). Pour 33 =
(331, ,:cn) E K", on note

HOEH1 -- Z |OEz'l et I|Mll1-- ---- Sup

oeEURK"\{O} ||î'îll1

pour M EUR Mn,n(K ), la norme matricielle subordonnée.

Définition 1 On dit qu'une matrice M EUR M...;(R),de coefiîcients notés
(mi--351 S i S n, 1 5 j 5 l), est positive (respectivement strictement po-'
sitive}, ce que l'on note M 2 0 (respectivement M > 0}, lorsque tous ses '
coeflicients sont positifs (respectivement strictement positifs ) :

mij Z 0 (resp. mij > O)pourtout(i,j) EUR{1,--- ,n} >< {1,---- ,l}.

Pour deus: matrices M et N de M...;(R), M 2 N (respectivement M > N )
lorsque M ---- N 2 O (reSpectivemerit M ---- N > O).'

Une matrice M EUR M,...(R) de coefilcients notés (ml--351 £ i,j S n) est
dite stochastique lorsqu'elle est positive et que de plus

ZmÜ = 1, pour toutj E {l, ,n}.,

On définit les ensembles B, B+ et E par:
B ={oeEURR"/æ20etæ#0},
+={oeER"/OE>O},
2 = {CE E R" /llell1 = 1}-

Nous souhaitons montrer le résultat suivant :

Théorème 1 (Perron--Frobenius) Soit T E Mn,n(R) stochastique telle
que (ln +T)""1 > 0. Il eæiste un vecteur strictement positif 5130 satisfaisant
Ta:0 : (130. Toutes les valeurs propres de T sont de module inférieur à 1 et
pour tout vecteur y de 2 0 B,

1 -- 230
-- ] :
k--l--i>Ëbok ZT y

I

10)

11)

Les deux parties sont dans une large mesure indépendantes.

Un vecteur propre strictement positif

on suppose que T est un élément positif de M,...(R) tel que
P = (L,, +T)""1 est strictement positive.

Montrer que pour tout 513 EUR B, l'ensemble I'OE : {9 EUR R+ / 9513 _<_ T:c} est
non vide, fermé et borné.

On note 9(oe) son plus grand élément.

Montrer que pour tout a: EUR B, on peut calculer 9(æ) de la manière sui--

vante:
9(oe)=min{ 0 et tout 513 EUR B, 9(ozoe) : 9(a:).
Montrer que P(B) C E'".

Montrer que pour tout 513 EUR B, 9(Pæ) Z 9(æ) et 9(Pæ) > 0.

Soit 11: EUR B un vecteur propre de T. Montrer que 9(Pa:) : 9(æ).

Soit :L' EUR B tel que 9(Pa:) : 9(a:), montrer que a: est un vecteur propre
de T pour la valeur propre 9(æ).

Soit G = B D 2. Montrer que l'application 9 est continue de P(C) dans
R.

Justifier l'existence de 330 EUR P(C) tel que 9(oe0) : sup 9(33).
OEEURP(C)

Montrer que sup 9(æ) Z sup 9(a:)
æEURP(C) xEURC

Montrer que sup 9(æ) : sup 9(oe).
_OEEURB æEURC

12) Montrer que sup 9(a:) : sup 9(æ) et que 9(æ0) : sup 9(:c)
OEEC ,æEURP(C) æEURC

On pose (% : 9(æ0).

13) Montrer que 330 est un vecteur propre, strictement positif, de T pour la
valeur pr0pre 90 et que 90 > 0.

II Une méthode d'approximatîon

On suppose maintenant que T est stochastique et telle que P = (I" +T)"'1
est strictement positive.

Pour un vecteur a: = (561, ---- ,:b,,) de (C", on note æ+ le vecteur (loell, 
--- , |xnl),
où |z| est le module du complexe 2. Pour tout entier k _>_ 1, on pose

14) Soit 9 E C et a: E C" un vecteur propre deT pour la valeur propre 9.
Montrer que |Hloe+ S Taï".

15)" En déduire que 19] £ 90.

16) Montrer que |9| ||æ+||1 S |læ+||1 et en déduire que |9| S 1.

17) En déduire 90 = 1.

18) Montrer que pour tout j 2 1, Tj et R, sont des matrices stochastiques.

19) Établir, pour tout k: 2 1, les inégalités suivantes:

...... s 1 et "murs 1.

.

20) Montrer que pour tout k 2 1, ||TRk ---- R,,Hl <

2
k.

21) Soit &: E C", montrer que la suite (Rkæ, k 2 1) a au moins une valeur
d'adhérence.

22)

23)

24)

25) _

26)
27)
28)

29)

Soit y une valeur d'adhérence de la suite (ka, k 2 1), montrer que
Ty : y et que pour tout k 2 1, Rky : y.

Soit y et 2 deux valeurs d'adhérence de (Rkæ, k _>_ 1), montrer pour tous
les entiers ... et l, l'identité suivante:

y -- z : R;(R...æ ---- z) -- R...(R;æ -- y).

Montrer que la suite (Run, k 2 1) a exactement une valeur d'adhérence.

Montrer qu'il existe une matrice R telle que Ra: : klim Rka: pour tout
---+ 00
a: E C" et klim ||R;ç -- R||1 : 0.

Montrer que T et R commutent.

Montrer que RT : R et R2 = R.
Caractériser R en fonction de Ker(T -- In) et Im(T --- In).

On admet que Ker(T --- I,...) est de dimension 1. Pour 33 E B, expliciter
R3: en fonction de "su..., ||oe0||1 et 230.

FIN DU PROBLÈME

Ce théorème possède d 'innombrabIes applications. L'une des dernières est

son utilisation dans le classement (PageRank) des pages Web effectué par le
plus connu des moteurs de recherche. -

Mines Maths 1 MP 2006 -- Corrigé
Ce corrigé est proposé par Guillaume Dujardin (ENS Cachan) ; il a été relu par
Roger Mansuy (Professeur en CPGE) et Walter Appel (Professeur en CPGE).

Ce sujet a pour objectif de démontrer une version du théorème de 
PerronFrobenius, qui est un résultat important d'algèbre.
De nombreux problèmes peuvent être modélisés et exprimés par une relation
faisant intervenir une matrice, notons-la T, par exemple en théorie des 
graphes, en
probabilités (chaînes de Markov), dans les systèmes dynamiques discrets, dans 
l'étude
des suites récurrentes, etc. Sous certaines conditions, le comportement 
asymptotique
est essentiellement contrôlé par le module de la plus grande valeur propre de T.
L'enjeu du théorème de Perron-Frobenius est de donner une condition suffisante 
pour
qu'une matrice admette une valeur propre positive supérieure aux modules de 
toutes
les autres valeurs propres. En outre, cette valeur propre est alors de 
multiplicité 1 et
il existe un vecteur propre associé dont les coefficients sont tous strictement 
positifs.
Ce résultat admet de très nombreuses applications pratiques.
L'énoncé se place résolument dans un cadre probabiliste (sans demander un 
quelconque raisonnement de probabilités) en introduisant des matrices, dites 
stochastiques, dont chaque coefficient est compris entre 0 et 1, et dont la 
somme sur une
colonne vaut 1 : ces nombres s'interprètent naturellement comme des 
probabilités.
Pour ces matrices, l'hypothèse classique du théorème est que T soit 
irréductible,
c'est-à-dire qu'elle ne soit pas semblable, via une matrice de permutation, à 
une matrice triangulaire par blocs (cette propriété a une interprétation 
naturelle dans les
chaînes de Markov). Cette condition est équivalente à ce que tous les 
coefficients de
(In + T)n-1 soient strictement positifs, et c'est la formulation retenue par 
l'énoncé.
L'épreuve se compose de deux parties :
· Dans la première partie, on démontre l'existence d'un vecteur propre x0 de T,
pour une certaine valeur propre 0 > 0 qui majore le module des autres valeurs
propres de T, et dont toutes les composantes sont strictement positives. Tout
en se familiarisant avec les notations introduites par l'énoncé, on est amené à
utiliser des propriétés de compacité dans l'espace normé Rn et à manipuler des
bornes supérieures de parties de R.
· Dans la seconde partie, on établit les autres propriétés annoncées dans le 
théorème de Perron-Frobenius, cité dès les préliminaires. On introduit des 
suites de
matrices stochastiques convergentes de sorte que la matrice limite (elle aussi
stochastique) ait les propriétés souhaitées pour conclure ; on admet toutefois
que dim Ker (T - In ) = 1.
Ces deux parties sont largement indépendantes : il suffit en effet d'admettre le
résultat principal de la première partie (donné à la question 13) pour pouvoir 
traiter
la seconde dans son intégralité. Le sujet peut par ailleurs paraître un peu 
long pour
une épreuve de trois heures.

Indications
Partie I
I.3 Utiliser le résultat de la question précédente.
I.4 Utiliser le fait que P est strictement positive et qu'un vecteur de B est 
toujours
non nul.
I.5 Utiliser le fait que P et T commutent pour montrer successivement que
x  Px , puis que, si x  B, alors Tx  B.
I.6 Utiliser la question 3.
I.7 Raisonner par l'absurde en supposant que Tx - (x)x 6= 0.
I.8 Remarquer que C  B et utiliser le résultat de la question 4.
I.9 Dans un premier temps, montrer que P(C) est compacte.
I.10 Utiliser le résultat de la question 5.
I.11 Utiliser le résultat de la question 3.
I.12 Utiliser les questions précédentes.
I.13 Montrer que 0 = (Px0 ) et faire la synthèse des résultats précédents.
Partie II
II.14 T étant stochastique, elle est positive.
II.15 Utiliser la question précédente et le fait qu'un vecteur propre est, par 
définition,
non nul.
II.16 Utiliser le fait que T est positive, puis le fait qu'elle est 
stochastique.
II.17 Justifier que 1 est valeur propre de T et utiliser le résultat de la 
question 13.
t

II.18 Notons e = (1, . . . , 1)  Rn . Vérifier qu'une matrice S de Mn,n (R) est 
stot
chastique si et seulement si elle est positive et S e = e. Utiliser ensuite 
cette
caractérisation.
II.19 Utiliser le fait que la norme k · k1 est une norme matricielle 
subordonnée à une
norme sur Rn .
II.20 Utiliser la définition de Rk .
II.21 Montrer que la suite (Rk x)k>1 est bornée dans (Rn , k · k1 ).
II.22 Utiliser le résultat de la question 20.
II.23 Utiliser le fait que Rm et Rl sont des polynômes en T.
II.24 Raisonner par l'absurde en supposant que la suite (Rk x)k>1 admet au moins
deux valeurs d'adhérence distinctes et utiliser la question précédente. Utiliser
la question 21 pour conclure.
II.25 À l'aide de la question précédente, justifier que la suite (Rk x)k>1 
converge.
II.26 Constater que T commute avec Rk et effectuer un passage à la limite.
II.27 Utiliser le résultat de la question 20 et deux passages à la limite.
II.28 Montrer que Ker (T - In ) = Im R et que Im (T - In ) = Ker R à l'aide de 
la
question précédente et du théorème du rang.
II.29 Utiliser l'énoncé du théorème de Perron-Frobenius donné par l'énoncé pour
conjecturer l'expression de Rx.

I. Un vecteur propre strictement positif
1

Avant de commencer ce corrigé, nous attirons l'attention du lecteur sur le fait
que si les matrices stochastiques, qui interviennent naturellement en théorie
des probabilités, sont « positives » au sens donné par l'énoncé, la notion
de positivité qui est utilisée pour les définir n'a que peu de rapport avec
celle des matrices symétriques « positives » qui figurent au programme de
mathématiques des classes de MP.

Soit x un élément de B. Montrons que x est un ensemble non vide car il contient 
0.
Puisque T est une matrice positive de Mn,n (R), il vient que, pour tout i  {1, 
. . . , n},
n
P
le réel (Tx)i =
tij xj est positif en tant que somme de produits de réels positifs.
j=1

On a donc

i  {1, . . . , n}

(0x)i = 0 6 (Tx)i

Ceci s'écrit encore 0x 6 Tx. On en déduit que 0  x .
Montrons maintenant que x est borné. Puisque x  B, on a x 6= 0. On en déduit
qu'il existe i  {1, . . . , n} tel que xi > 0. Ainsi, pour tout   x , on a xi 6 
(Tx)i .
Ceci prouve que x est borné par (Tx)i /xi .
Enfin, on montre que x est fermé. Si (m )mN est une suite d'éléments de x
convergeant vers   R, alors
i  {1, . . . , n} m  N

(m xi ) 6 (Tx)i

On en déduit, en passant à la limite quand m tend vers l'infini dans cette 
inégalité,
que, pour tout i  {1, . . . , n}, xi 6 (Tx)i . Cette dernière inégalité valant 
pour tout
i, on en déduit que x 6 Tx. Puisqu'en outre   R+ comme limite de réels positifs,
on a finalement   x . On a donc montré que
x est une partie non vide, fermée et bornée de R.
En fait, x est une partie non vide fermée et bornée bien particulière de R.
En effet, c'est un segment, comme le lecteur pourra aisément le montrer en
adaptant la réponse à la question suivante : x = [ 0 ; (x) ].
2 D'après la question précédente, x est une partie non vide et majorée de R ; 
elle
admet donc une borne supérieure. x étant en outre fermée dans R, on en déduit
que sa borne supérieure est aussi son plus grand élément. Ceci justifie la 
définition
de (x). Notons

(Tx)i .
Mx = min
1 6 i 6 n et xi 6= 0
xi
Si   x , alors pour tout i  {1, . . . , n} tel que xi 6= 0, on a xi 6 (Tx)i , 
et donc
 6 (Tx)i /xi . On en déduit que  6 Mx . Puisque (x)  x , on a en particulier
(x) 6 Mx

En outre, si   x est tel que  < Mx , alors on peut choisir  > 0 tel que
 +  6 Mx . On a alors pour tout i  {1, . . . , n} tel que xi 6= 0,
( + )xi 6 Mx xi 6

(Tx)i
xi = (Tx)i
xi

De plus, pour i  {1, . . . , n} tel que xi = 0, on a trivialement 0 = ( + )xi 6 
(Tx)i .
On en déduit  +   x . On a donc montré qu'aucun élément de x strictement
inférieur à Mx n'est un majorant de x . Or (x) est le plus grand élément de x .
On en déduit Mx 6 (x).
Finalement, on a montré que

(Tx)i .
(x) = min
1 6 i 6 n et xi 6= 0
xi
3 Soient x  B et  > 0. Pour tout i  {1, . . . , n}, on a l'équivalence
(x)i 6= 0  xi 6= 0
et l'identité

(T(x))i = (Tx)i

(T(x))i
(Tx)i
(Tx)i
=
=
. On en déduit que
(x)i
xi
xi

(Tx)i .
(T(x))i .
1 6 i 6 n et xi 6= 0 =
1 6 i 6 n et (x)i =
6 0
xi
(x)i

Ainsi, si xi 6= 0, alors

et donc, avec la question précédente
(x) = (x)
4 Soit x  B. Il existe j0  {1, . . . , n} tel que xj0 > 0. Alors, puisque P est
strictement positive, on a, pour tout i  {1, . . . , n},
(Px)i =

n
P

pij xj > pij0 xj0 > 0

j=1

On en déduit que Px  B+ . Donc
P(B)  B+
5 Remarquons que, si x et y sont des vecteurs de Rn tels que 0 6 x 6 y et si
M  Mn,n (R) est positive, alors Mx 6 My. En effet, pour tout i  {1, . . . , n}, 
on a
(Mx)i =

n
P

mij xj 6

j=1

n
P

mij yj = (My)i

j=1

Soient maintenant x  B et   x . Par définition de x , on a 0 6 x 6 Tx. La
matrice P étant positive, on déduit de la remarque ci-dessus que P(x) 6 PTx. En
outre, puisque la matrice P = (In + T)n-1 est un polynôme en T, elle commute 
avec
T. On a donc Px 6 TPx et par conséquent   Px . Finalement, on a montré que
pour tout x  B, x  Px . On en déduit
x  B

(x) 6 (Px)