Centrale Maths 1 MP 2016

Mathématiques 1
MP

4 heures Calculatrices autorisées

2016

Matrices positives ( im ) primitives

Ce problème étudie diverses propriétés des matrices primitives et des matrices 
irréductibles, définies dans les
parties III et V respectivement, et s'appuie sur la notion de chemin dans une 
matrice positive, que l'on définit
dans le préambule.
Généralités
-- Dans tout le problème n désigne un entier supérieur ou égal à 2.

Pour tous entiers naturels i et j, avec i < j, la notation ||i,j]] désigne {le EUR N, i EUR le g j}. -- On note M,,(D<) l'ensemble des matrices carrées d'ordre n à coefficients dans Û< (avec IK : [R ou C). Si A est dans M,,(lK), on notera a,|,-- ou |A]... le coefficient de A situé en ligne i et colonne j. On note GL,,([K) l'ensemble des matrices carrées inversibles d'ordre n à coefficients dans [K. On note diag()... À2,. .,À ,,) la matrice diagonale de coefficients diagonaux successifs À1, À2, ..., À,,. (îÿ Si A est une matrice carrée de terme général a, on note a, 'le terme général de la matrice Am. J' -- Soit A dans M,,(lK ). On note Sp(A) (spectre de A) l'ensemble des valeurs propres complexes de A. On appelle rayon spectral de A la quantité p(A) : max{|À|, À EUR Sp(A)}. On dit qu'une valeur propre À de A est dominante si : Vu EUR Sp(A) \ {À}, |,a| < |À|. -- On identifie une matrice A de M,,(Û<) avec l'endomorphisme de [K" qui lui est canoniquement associé. Cela permet de légitimer les notations lm(A) et Ker(A). -- On note AT la transposée d'une matrice A. -- On identifie un élément a : (as,-) de [| >,0 si: V(i 
,j), a...-- > 0.
On dit que A est strictement positive et on note A > 0, si . V(i ,j),a a,|,-- > 
0.
Ces définitions s'appliquent aux vecteurs r de [R" (notations a: > 0 ou r > 0).
On prendra bien garde au fait que l'implication (A > 0 et A : 0) => A > 0 est 
fausse !
-- Il est clair (et on ne demande pas de le démontrer) que les puissances Ak 
(avec le > 1) d'une matrice carrée
positive (respectivement strictement positive) sont positives (respectivement 
strictement positives).
Chemins dans une matrice positive
-- Soit A : (a...--) une matrice positive de M ,,D?( ).
Un chemin dans A est une suite @: (i,,)0 1, telle que: 
Vk EUR ||0, m--1]], a,k ,}... > 0.
Un tel chemin sera noté: i() --> % ik --> e i...
-- On dit que EUR a pour longueur m et qu'il va de i0 (son origine) à i... (son 
extrémité) en passant par les ik.
-- On dit que C' est un chemin élémentaire si io, ..., im sont distincts deux a 
deux.
-- On dit que EUR est un circuit si i... : i0 et un circuit élémentaire si de 
plus io, ..., i,,,11 sont distincts. Dans un
circuit, la notion d'origine et d'extrémité perd de son intérêt. On pourra donc 
dire d'un circuit qu'il passe
par un indice i (sans se préoccuper de la position de i dans ce circuit).

I Si p(A) < 1, alors lim Am : () mä+oo Cette partie est pratiquement indépendante du reste du problème. Elle démontre un résultat qui ne sera utilisé que dans la question IV.B. On dit qu'une norme A r--> ||A|| sur M,,(lK) est sous--multiplicative si : V(A, 
B) EUR M,,([K)2, ||AB|| g ||A|| ||B||.

I.A -- Deuæ eoeemples de normes sous-multiplicatives

1+oo

I.B.1) Soit P dans GL,, (03) et soit T triangulaire supérieure, telles que A : 
PTPÎ1. On se donne 5 > 0. On
pose A : diag(1, 6, 5"*1) et Î : A*1TA.

Montrer que Î est triangulaire supérieure et qu'on peut choisir 5 de sorte que 
N (Î) < 1. I.B.2) Avec ce choix de 5, on pose Q : PA et on munit MAC) de la norme M H HMH : N(Q*1MQ). Montrer que llAll < 1 et en déduire lim Am : O. m-->+oo

II Chemins dans les matrices positives

Cette partie aborde les notions de base sur les chemins dans une matrice 
positive A (et notamment le lien entre
l'existence de tels chemins et le caractère strictement positif de coefficients 
des puissances de A).

Une bonne compréhension des résultats démontrés ici est importante dans la 
perspective des parties III et IV.
Dans cette partie, A désigne une matrice positive de MAR).

II.A * Réduction d'un chemin a un chemin élémentaire

Montrer que s'il existe dans A un chemin de i vers j, avec i # j, alors il 
existe un chemin élémentaire de i vers j
et de longueur EUR < n -- 1. De même, montrer que s'il existe dans A un circuit passant i, alors il existe un circuit élémentaire passant par i et de longueur EUR < n. II.B * Une caractérisation de l'emistence d'un chemin de i à j Soit A 2 0 dans MAR). Soit i, j dans [[1, n]]. Soit m 2 1. Montrer l'équivalence des propositions : -- il existe dans A un chemin d'origine i, d'extrémité j, de longueur m ; -- le coefficient d'indice i, j de A... (noté aïîÿ' ) est strictement positif. On pourra procéder par récurrence sur l'entier m 2 1. II.C * Chemins dans une puissance de A Soit i, j dans [[1,n]], et soit EUR et m dans D\l*. Montrer l'équivalence des propositions : -- il existe dans A... un chemin d'origine i, d'extrémité j, de longueur EUR ; -- il existe dans A un chemin d'origine i, d'extrémité j, de longueur mt . III Matrices primitives et indice de primitivité Soit A dans MAR), avec A > 0. On dit que A est primitive s'il existe m 2 1 tel 
que A... > 0.
Avec cette définition, il est clair que toute matrice carrée strictement 
positive est primitive.
Dans toute la suite, matrice primitive signifie matrice carrée positive 
primitive.

Si A est primitive, on appelle indice de primitivité de A le plus petit entier 
m 2 1 tel que A... > O.

III.A * Chemins élémentaires dans une matrice primitive

Soit A une matrice primitive de MAR)

Montrer que pour tous i 7': j il existe dans A un chemin élémentaire de i à j 
et de longueur EUR < n -- 1, et que pour tout i il existe dans A un circuit élémentaire passant par i et de longueur EUR < n. III.B * Puissances d'une matrice primitive III.B.1) Donner un exemple simple d'une matrice carrée primitive mais non strictement positive. III.B.2) Soit B > 0 dans MAR) et a: 2 0 dans R" avec sc % 0. Montrer que Br > O.

III.B.3) Soit A une matrice primitive et m EUR IN* tel que A... > 0. Montrer 
que Vp } m, A?" > 0.

On pourra remarquer, en le justifiant, qu'aucune des colonnes 01,02, ...,c,, de 
A n'est nulle.
III.B.4) Prouver que si A est primitive, alors A'" est primitive pour tout le 2 
1.

III.B.5) Montrer que le rayon spectral d'une matrice primitive est strictement 
positif.

III.C * La matrice de Weilandt

On définit la matrice W,, = (w,_,--) de MAR) par w- - :

,, 1 sii=netjEUR{1,2}

{lsi1--*O
OO>--'OO
Ol--'OOO

2016--02--15 20:21:43 Page 2/6 @c) BY--NC-SA

Le but de cette question est de prouver que W,, est primitive, d'indice de 
primitivitê n2 -- 2n + 2.
III.C.1) Montrer que le polynôme caractéristique de W" est X " -- X + 1.

"il n+1
-- 2 -- 2
En déduire Wgac2... : î (Z 1) W];, puis que W;2*2"+2 : I,, + W,, + E (2 2) WË.
k=1 _ k=2 _

III.C.2) Préciser le plus court circuit passant par l'indice 1 dans la matrice 
W,,.

+2n+1

En déduire que la matrice ositive W"2 n'est as strictement ositive.
p ,, p p

III.C.3) Montrer que pour tous i, j de [[1, 11], avec i # j, il existe dans W,, 
au moins un chemin d'origine i,
d'extrémité j, et de longueur inférieure ou égale à n -- 1.
On pourra traiter successivement les deux cas 1 $ {i,j} et 1 EUR {i,j}.

; . . 2Î . . .
En dedu1re que la matrice W: 2"+2 est strictement p051t1ve et conclure.

III.D + Indice de primitivitë maæimum

Le but de cette sous--partie est de prouver que si A G M,,(lR) est primitive, 
on a toujours A"2*2"+2 > O, c'est--à--
dire que l'indice de primitivité de A est inférieur ou égal à n2 -- 2n + 2. Ce 
majorant est en fait un maximum,
comme on l'a vu avec la matrice W" de Weilandt dans la question précédente.

Dans toute cette sous--partie, A est une matrice primitive donnée dans M,,(lR).

On peut donc appliquer à la matrice A les résultats de la question HLA.

En particulier, on note EUR EUR [[1, n]] la plus petite longueur d'un circuit 
élémentaire de A.

III.D.1) Par l'absurde, on suppose EUR = n.

Montrer qu'alors tous les circuits de A sont de longueur multiple de n.

En déduire que les matrices A'""+1 (avec [EUR EUR IN) sont de diagonale nulle 
et aboutir à une contradiction.
III.D.2) D'après ce qui précède, il existe dans A un circuit élémentaire C' de 
longueur EUR g n -- 1.

Pour simplifier la rédaction, et parce que cela n'enlève rien à la généralité 
du problème, on suppose qu'il s'agit
du circuit 1 --> 2 --> --> EUR-- 1 --> EUR --> 1 (les n--EUR indices restants 
Æ+ 1, É+ 2, ..., n étant donc situés « en dehors »
du circuit 8).

Nous allons montrer que A"+Ë(n*2> est strictement positive.

Pour cela, on se donne i et j dans [[1,n]]. Tout revient à établir qu'il existe 
dans A un chemin d'origine i,
d'extrémité j et de longueur n + EUR(n -- 2).

a ) Montrer que dans A, on peut former un chemin d'origine i, de longueur n -- 
EUR , et dont l'extrémité est dans
{1, 2, EUR} (on notera k cette extrémité).

On pourra traiter le cas 1 < i { EUR, puis le cas Æ+ 1 { i g n. b) Dire pour quelle raison les EUR premiers coefficients diagonaux de A5 (et en particulier le k--ième) sont strictement positifs. Montrer alors qu'il existe un chemin de longueur n -- 1 dans AË (c'est--à--dire un chemin de longueur EUR (n -- 1) dans A) d'origine le et d'extrémité j. c) En déduire finalement A"+Ë(n*2l > 0, puis A"L2n+2 > 0.

IV Étude des puissances d'une matrice primitive

Cette partie utilise uniquement la définition des matrices primitives : elle 
est pratiquement indépendante de la
partie 111. Par ailleurs, les résultats de la partie IV ne seront pas 
réutilisés dans les parties V et VI.

Pour toute matrice primitive A dans M,,(lR), on admet le résultat suivant :

Le rayon spectral p(A) de A (dont on sait qu 'il est strictement positif) est 
une valeur propre
dominante de A et le sous--espace propre associé est une droite vectorielle qui 
possède un
vecteur directeur oe > 0.

Dans toute cette partie, on se donne une matrice primitive A de M,,(lR).
Pour simplifier les notations, on note r (plutôt que p(A)) le rayon spectral de 
A. On rappelle que r > 0.
Il est clair que AT est primitive, et que A et AT ont le même rayon spectral r.

On peut donc noter 95 (respectivement y) un vecteur directeur strictement 
positif de la droite D : Ker(A--rI,,)
(respectivement de la droite A : Ker(AT -- rl,,)). On note H : lm(A -- rl").

Quitte à multiplier y par un coefiicient strictement positif adéquat, on 
suppose (y | oe) : yT a: : 1.
On note L : scyT (c'est un élément de M,,(lR)).

IV.A + Puissances de la matrice B : A -- rL
IV.A.1) Montrer que H est l'hyperplan orthogonal a la droite A (c'est--à--dire 
H : Al).

2016--02--15 20:21:43 Page 3/6 @c) BY--NC-SA

IV.A.2) Prouver que L est la matrice, dans la base canonique, de la projection 
de il?" sur la droite D, parallè--
lement à l'hyperplan H.

IV.A.3) Vérifier que L est de rang 1, qu'elle est strictement positive, et que 
LT y : y.
IV.A.4) Montrer que AL : LA : rL. En déduire : Vm EUR IN*, (A -- rL)m : A'" -- 
rmL.

IV.B + La matrice B : A --rL vérifie p(B) < r Dans cette question, on pose B = A -- rL. On va montrer que p(B) < r et en déduire un résultat intéressant sur la suite des puissances successives de A. Soit A une valeur propre non nulle de B et soit 2 un vecteur propre associé. IV.B.1) Montrer que Lz : 0, puis Az : Àz. En déduire p(B) { r. IV.B.2) Par l'absurde, on suppose p(B) : r. On peut donc choisir À de telle sorte que |À| : r. Montrer qu'alors À : r puis Lz : z et aboutir à une contradiction. Conclure. 1 TTL IV.B.3) Déduire de ce qui précède (et de la sous--partie IV.A) que lim (--A) : L. me+oo r IV.C + Le rayon spectral de A est une valeur propre simple Dans cette sous--partie, on montre que la valeur propre dominante de A (c'est--à--dire son rayon spectral r) est simple (on sait déjà que le sous--espace propre associé est une droite vectorielle). Soit u la multiplicité de r comme valeur propre de A et soit T : PAPÎ1 une réduite triangulaire de A. ... En examinant la diagonale de (--T) quand m --> +00, montrer que la : 1.
r

V Matrices carrées positives irréductibles
Soit A : (d,-1j) dans M,,(iR), avec A 2 0. On dit que A est irréductible si, 
pour tous i et j dans [[1,n]], il existe
£Î}' > 0.

Avec cette définition, il est clair que toute matrice primitive est 
irréductible.

m 2 0 (dépendant a priori de i et j) tel que a

Dans toute la suite, matrice irréductible signifie matrice carrée positive 
irréductible.

Dans toute cette partie, A est une matrice positive donnée dans M,,(lR).

V.A + Premières propriétés des matrices irréductibles
V.A.1) Exprimer l'irréductibilité de A en termes de chemins dans A.

V.A.2) Montrer que si A est irréductible, alors pour tous i et j dans [[1, n]], 
il existe m EUR [[0, n-- l]] (dépendant

()
,-Îÿ>0.

a priori de i et ]) tel que a
V.A.3) Donner un exemple simple d'une matrice carrée irréductible mais non 
primitive.

V.A.4) Montrer que si A n'est pas irréductible, alors A2 n'est pas irréductible.

En revanche, donner un exemple simple d'une matrice A irréductible telle que A2 
ne soit pas irréductible.

V.A.5) Montrer que le rayon spectral d'une matrice irréductible est strictement 
positif.

V.B + Deum caractérisations de l'irréductibilité et une condition nécessaire

V.B.1) Pour la matrice positive A de M,,(iR), montrer que les conditions 
suivantes sont équivalentes :

-- la matrice A est irréductible ;

-- la matrice B = l,, + A + A2 + + A"*1 est strictement positive ;

-- la matrice C = (l,, + A)"*1 est strictement positive.

V.B.2) Soit A irréductible. Montrer qu'aucune ligne (et aucune colonne) de A 
n'est identiquement nulle.

V.C + Deuæ conditions suffisantes de primitivité
Dans cette question, A est une matrice irréductible donnée.
V.C.1) On suppose que Vi EUR [[1, n]], a,-y,- > 0. Montrer que A"*1 > 0 (donc A 
est primitive).

On raisonnera en termes de chemins dans A.

V.C.2) On suppose que : Ei EUR [[1, n]], a...- > 0. Montrer que A est primitive.

Pour tous j et le dans |Ïl,n]], on pourra montrer qu'il existe dans A un chemin 
dej à le et passant par i,
et considérer le maximum m des longueurs des chemins ainsi obtenus. On prouvera 
que A... > 0.

2016--02--15 20:21:43 Page 4/6 @c) BY--NC-SA

VI Le coefficient d'imprimitivité

Soit A : (a...--) dans M,,(lR), avec A 2 0.

On dit que A est imprimitive si A est irréductible mais n'est pas primitive.
Pour toute matrice A imprimitive dans Mn(lR), on admet le résultat suivant :

Les valeurs propres À de A telles que |À| : p(A) sont simples. Ce sont les 
solutions de l'équa--
tion À" : p(A)p pour un certain entier p 2 2. En particulier p(A) est valeur 
propre simple
de A. Plus généralement, la totalité du spectre de A est invariante dans la 
multiplication par
a; : exp(2i7r/p). Par ailleurs, et pour la valeur propre p(A), la matrice A 
possède un vecteur
propre a: > O.

L'indice p 2 2 dont il est question dans le résultat précédent est appelé le 
coefiicient d'imprimitivité de A.

Remarque : si on rapproche ce qui précède et le résultat admis au début de la 
partie IV, on peut fort bien dire
qu'une matrice primitive a pour coefficient d'imprimitivité p = 1.

VI.A + Diagonales des puissances d'une matrice imprimitive

Soit A une matrice imprimitive de coefficient d'imprimitivité p 2 2.

Pour tout entier m non multiple de p, montrer que la diagonale de A... est 
identiquement nulle.
On pourra s'intéresser à la trace de A'".

En déduire que le résultat de la question IV.B.3 ne tient plus si A est 
imprimitive.

VI.B + Une matrice de Weilandt « modifiée »

1 sil (donc fiq : w). Montrer que flr est valeur propre de A 
et conclure.

VI.B + Coeficient d'imprimitiuité et longueur des circuits

Dans cette question, on va établir un théorème de Romanovsky en 1936, 
établissant que le coefficient d'impri--
mitivité p d'une matrice irréductible (éventuellement p = 1 dans le cas d'une 
matrice primitive) est le pgcd des
longueurs des circuits passant un indice donné (ce pgcd ne dépendant en fait 
pas de l'indice en question).

Soit A E M,,(Ü?) une matrice irréductible. Pour tout i de [[1,n]], on note L,- 
: {m G N*, aîZ-" > O} l'ensemble
(non vide) des longueurs des circuits de A qui passent par i, et on note di le 
pgcd des éléments de Li.

() (>
13 >0et ai,- >0.

Pour tout [EUR dans {0} U Lj, montrer que d,,- divise r + k + s. En déduire que 
d,,- divise dj.

VI.B.1) Soit i,j dans [[1,n]]. On sait qu'il existe r et s dans N tels que a

Par symétrie, il en résulte évidemment que tous les d,- sont égaux. On note d 
leur valeur commune.

VI.B.2) Montrer que si p = 1 (c'est--à--dire si A est primitive), alors ol : 1 
(utiliser la question lll.B.3).

2016--02--15 20:21:43 Page 5/6 @c) BY--NC-SA

VI.D.3) Dans la suite de cette question, on suppose p 2 2.

Montrer que p divise d (utiliser la question VIA).

VI.D.4) On va montrer que d divise p. Il en résultera bien sûr l'égalité d : p.

On rappelle que la diagonale de A est nulle (c'est une conséquence de la 
question VIA).
Soit XA(OE) : det (OEIn -- A) le polynôme caractéristique de A.

11

On sait que XA(oe) : î: e(a) H{OEIn -- A]jya..., où la somme est étendue aux 
permutations a de [[1,n]].
cr j=1
On fixe une permutation a de [[1, 71], on pose \IJ(a) : H{oeln -- Alj,a(j) et 
on suppose \IJ(U) % 0.
j=1
On note H l'ensemble des éléments j de [[1,n]] tels que a(j) % j, et card(H) : 
h, avec 0 < h < n. a) Montrer que \IJ(U) : (--1)hæ"*h H ajya(j). jEURH b) La restriction à H de la permutation a se décompose en produits de cycles a supports disjoints (et de longueur 2 2 puisque par hypothèse aucun des éléments de H n'est invariant par 0"). Soit 5 : (j1, j2, ..., j...), avec m 2 2, l'un quelconque des cycles entrant dans cette décomposition. Montrer que j1 _) j2--n --> j... +) j1 est un circuit dans la matrice A.
En déduire que m, puis h, sont des multiples de d.
c) Montrer finalement que XA(:c) s'écrit : XA (a:) = a:" + a1æ"*d + a2æ"*2d + + 
akx"*kd +
En déduire que d est un diviseur de p (utiliser le résultat de la question 
VLC). Conclure.

oooFlNooo

2016--02--15 20:21:43 Page 6/6 @c) BY--NC-SA