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