Théorème de Perron-Frobenius

En algèbre linéaire et en théorie des graphes, le théorème de Perron-Frobenius, démontré par Oskar Perron et Ferdinand Georg Frobenius, a d'importantes applications en théorie des probabilités (chaînes de Markov), en théorie des systèmes dynamiques, en économie (analyse entrée-sortie), en théorie des graphes, en dynamique des populations (matrices de LeslieMatrice de Leslie) et dans l'aspect mathématique du calcul des pagerank de Google.

Théorème de Perron Frobenius pour une matrice positive irréductible

Théorème de Perron-Frobenius —  Soit $A$ une matrice à coefficients positifs de type $n\times n$ et irréductible.

• Le rayon spectral $\rho$ de $A$ est une valeur propre simple de $A$, et le sous-espace propre associé est une droite vectorielle engendrée par un vecteur (colonne) strictement positif.
• Si $s$ et $S$ sont respectivement le minimum et le maximum des sommes des éléments de chaque ligne de $A$, on a $s\leq \rho \leq S$.
• Si $n\geq 2$ alors $\rho >0$.
• Soit $h$ le nombre de valeurs propres (complexes) de module $\rho$. Le spectre de $A$ dans le plan complexe est invariant par la rotation de centre $O$ et d'angle ${\frac {2\pi }{h}}$. En outre, si $h>1$, il existe une matrice de permutation $S$ telle que ${}^{t}SAS=S^{-1}AS={\begin{pmatrix}0&A_{1,2}&0&\cdots &0\\0&0&A_{2,3}&\cdots &0\\\vdots \\0&0&0&\cdots &A_{h-1,h}\\A_{h,1}&0&0&\cdots &0\end{pmatrix}}$, où les blocs diagonaux (nuls) sont carrés.

Démonstration

Dans toute la démonstration nous identifions naturellement $\mathbb {R} ^{n}$ ou $\mathbb {C} ^{n}$ à l'espace des matrices colonne $n\times 1$ réelles ou complexes.

1. Désignons par $S$ l'ensemble des vecteurs de $(\mathbb {R} _{+})^{n}$ non nuls et par $S^{0}$ l'ensemble de ces vecteurs (colonne) strictement positifs. Définissons l'application $r$ de $S$ dans $\mathbb {R} _{+}$ par $r(X)=\min _{i\in \{1,2,\dotsc ,n\},X_{i}>0}{\frac {[AX]_{i}}{X_{i}}}$. On voit aisément qu'on a également $r(X)=\sup \left\{\lambda \in \mathbb {R} _{+}:\lambda X\leq AX\right\}$.
   • l'application $r$ admet un point de maximum sur S.

L'application $r$ est continue sur $S^{0}$ puisqu'il s'agit alors simplement du minimum d'une famille finie d'applications continues $\left(X\mapsto {\frac {[AX]_{i}}{X_{i}}}\right)_{i\in \{1,2,\dotsc ,n\}}$. Cependant, on ne peut affirmer la continuité sur $S$. Par ailleurs, $S$ et $S^{0}$ ne sont pas compacts. La solution sera de montrer l'existence d'un point de maximum sur une partie compacte $K$ de $S^{0}$ et de vérifier ensuite que ce point réalise aussi le maximum sur $S$. Il suffira pour cela de montrer que $\sup _{X\in S}{r(X)}\leq \sup _{X\in K}{r(X)}$ (en fait égalité, évidemment).

La première chose consiste à remarquer que $r$ est constante sur chaque demi-droite (ouverte) d'origine $0$ incluse dans $S$. On peut par conséquent se limiter à travailler sur la partie $D$ de $S$ formée des vecteurs colonne de norme 1 (nous prendrons la norme $\mathrm {N} _{\infty }(X)=\max _{i\in \{1,2,\dotsc ,n\}}{|X_{i}|}$).

$D$ est compact, mais on n'a pas encore la continuité de $r$ sur $D$. C'est maintenant qu'intervient l'irréductibilité de $A$.

Montrons que l'ensemble $K=(A+I)^{n-1}D$ satisfait à notre objectif ( $K$ compact, $r$ continue sur $K$ et $\sup _{X\in S}r(X)=\sup _{X\in K}r(X)$ ).

Tout d'abord $K$ est compact comme image du compact $D$ par une application (linéaire) continue. Ensuite voyons que $K$ est inclus dans $S^{0}$, ce qui montrera bien la continuité de $r$ sur $K$. En effet on sait que $(A+I)^{n-1}>0$ et il en résulte immédiatement que $\left[X\geq 0,X\neq 0\right]\Rightarrow (A+I)^{n-1}X>0$. Par conséquent $r$ possède un point de minimum sur $K$. Enfin pour achever montrons que $\forall W\in D\quad r\left((A+I)^{n-1}(W)\right)\geq r(W)$. En effet $r(W)W\leq AW\Rightarrow r(W)(A+I)^{n-1}W\leq A(A+I)^{n-1}W$ ce qui montre que $r(W)$ est majoré par $r\left((A+I)^{n-1}W\right)=\sup\{\lambda \in \mathbb {R} _{+}\backslash \lambda X\leq AX\}$. Ainsi on a bien $\sup _{W\in S}r(W)=\sup _{X\in K}r(X)$

Nous désignerons désormais par $\rho$ la valeur maximale de $r(X)$ trouvée ci-dessus et par vecteur extrémal tout vecteur $X$ réalisant le maximum de $r$ sur $S$.

1. • Tout vecteur extrémal est vecteur propre de $A$ associé à la valeur propre $\rho$. Réciproquement tout vecteur propre positif relatif à $\rho$ est extrémal.

Soit $X$ un vecteur extrémal. Par définition $\rho X\leq AX$. Supposons que $\rho X\neq AX$. Posons $Y=(A+I)^{n-1}X$. Puisque $AX-\rho X\geq 0$ et $AX-\rho X\neq 0$ on a $(A+I)^{n-1}(AX-\rho X)>0$, soit encore $AY-\rho Y>0$, c'est-à-dire $\rho Y<AY$. On peut trouver $\epsilon >0$ tel que $(\rho +\epsilon )Y\leq AY$, ce qui contredit la maximalité de $\rho$.

Réciproquement si le vecteur positif $X$ vérifie $AX=\rho X$, en écrivant d’une part $\rho X\leq AX$ on voit que $\rho \leq r(X)$ et d’autre part $r(X)X\leq AX=\rho X$ montre que $r(X)\leq \rho$. Ainsi $r(X)=\rho$ et X est extrémal.

1. • Pour toute valeur propre (complexe) $\lambda$ de $A\quad |\lambda |\leq \rho .\quad \rho$ est le rayon spectral de $A$.

En effet de $AZ=\lambda Z$ on tire $A|Z|\geq |\lambda ||Z|$. Donc $|\lambda |\leq r(|Z|)\leq \rho$.

1. • Tout vecteur extremal est strictement positif.

En effet si $X$ est extrémal posons $Z=(A+I)^{n-1}X$. Comme $X\geq 0,X\neq 0$ et $A$ irréductible on a $Z>0$. Comme $X$ est vecteur propre de $A$ relatif à $\rho$ (cf. ci-dessus) on a $Z=(\rho +1)^{n-1}X$ d'où on tire $X=(\rho +1)^{1-n}Z>0$.

1. • Pour tout vecteur propre (complexe) $Z$ de $A$ relatif à une valeur propre $\lambda$ de module $\rho$, le vecteur $|Z|$ (vecteur dont les composantes sont les modules de celles de $Z$) est un vecteur extrémal (et est donc strictement positif ). Il en résulte que chaque vecteur propre de $A$ (éventuellement complexe) relatif à $\lambda$ vérifiant $|\lambda |=\rho$ a toutes ses composantes non nulles.

En effet de $AZ=\lambda Z$ on déduit immédiatement $A|Z|\geq \rho |Z|$, ce qui entraîne $\rho \leq r(|Z|)\leq \rho$ par maximalité de $\rho$, d’où le résultat.

1. • Le sous-espace propre de $A$ relatif à la valeur propre $\rho$ est une droite vectorielle.

Supposons en effet que $X$ et $Y$ soient 2 vecteurs propres linéairement indépendants. On sait (cf. ci-dessus) que ces 2 vecteurs ont toutes leurs composantes non nulles. Il est possible de former une combinaison linéaire non nulle ayant par exemple la première composante nulle. Cette combinaison est ainsi un vecteur propre de $A$ ayant une composante nulle, ce qui est contradictoire.

1. • $\rho$ est une valeur propre simple de $A$.

Désignons par $B(\lambda )$ la comatrice transposée de $\lambda I-A$. Remarquons tout d'abord que le sous-espace propre relatif à $\rho :\quad ker(\rho I-A)$ étant de dimension 1 il en résulte que $\rho I-A$ est de rang $n-1$ et que par suite il y a au moins un cofacteur non nul, ce qui montre que $B(\rho )\neq 0$. De plus on sait que $(\lambda I-A)B(\lambda )=\mathrm {det} (\lambda I-A)I$. En particulier $(\rho I-A)B(\rho )=0$, ce qui montre que les colonnes non nulles de $B(\rho )$ sont des vecteurs propres de $A$ relatives à $\rho$ et par suite que ces colonnes non nulles sont toutes multiples de l'une d'entre elles et ont toutes leurs composantes non nulles et de même signe. Mais on a aussi $B(\rho )(\rho I-A)=0$, soit en transposant $(\rho I-{}^{t}A)\;{}^{t}B(\rho )=0$. Or ${}^{t}A$ est aussi une matrice positive irréductible puisque $({}^{t}A+I)^{n-1}={}^{t}\left((A+I)^{n-1}\right)>0$. Le raisonnement précédent appliqué à ${}^{t}A$ permet ainsi de montrer que les colonnes non nulles de ${}^{t}B(\rho )$ et donc les lignes non nulles de $B(\rho )$ ont tous leurs éléments non nuls et de même signe. Finalement on en déduit facilement que $B(\rho )$ a tous ses éléments non nuls et de même signe. En effet soient $B_{i,j}(\rho )$ et $B_{k,l}(\rho )$ deux éléments quelconques de $B(\rho )$. Si $B_{i,j}(\rho )=0$ toute sa ligne est nulle, donc $B_{i,l}(\rho )=0$, par suite toute la colonne $l$ est nulle et ainsi $B_{k,l}(\rho )=0$. Finalement on en déduit que $B(\rho )=0$, ce qui est exclu. D'autre part le signe de $B_{i,j}(\rho )$ est celui de $B_{i,l}(\rho )$ et finalement celui de $B_{k,l}(\rho )$. Tous les éléments de $B(\rho )$ sont bien non nuls et de même signe.

Posons $\Pi (\lambda )=\mathrm {det} (\lambda I-A)$ (polynôme caractéristique). On a $\Pi '(\lambda )=\sum _{i=1}^{n}B_{i,i}(\lambda )=\mathrm {Tr} (B(\lambda ))$. En effet désignons par $A_{i}(\lambda )$ la i_ème colonne de la matrice $\lambda I-A$.

On a $\Pi '(\lambda )={\frac {d}{d\lambda }}{\text{det}}(A_{1}(\lambda ),A_{2}(\lambda ),\dotsc ,A_{n}(\lambda ))=\sum _{i=1}^{n}{\text{det}}(A_{1}(\lambda ),A_{2}(\lambda ),\dotsc ,A_{i}'(\lambda ),\dotsc ,A_{n}(\lambda ))$. Mais $A_{i}'(\lambda )$ a tous ses éléments nuls sauf le i_ème qui est égal à 1. Le résultat s'ensuit immédiatement. On a donc $\Pi '(\rho )\neq 0$ puisque tous les éléments de $B(\rho )$ sont non nuls et de même signe. Ceci montre bien que $\rho$ est valeur propre simple de $A$.

1. Soit $X>0$ un vecteur propre relatif à $\rho$. On a donc $\sum _{i=1}^{n}A_{i,j}X_{j}=\rho X_{i}$. Soit $q$ l'indice d'une composante $X_{j}$ maximale. On a $\rho X_{q}=\sum _{j=1}^{n}A_{q,j}X_{j}\leq \sum _{j=1}^{n}A_{q,j}X_{q}\leq SX_{q}$ et en simplifiant par $X_{q}>0$ on obtient $\rho \leq S$. La démonstration est symétrique pour $s$ en considérant cette fois l'indice d'une composante $X_{j}$ minimale.

Si $n\geq 2$ alors $s>0$ (sinon il y aurait une ligne nulle, soit la j-ème et la matrice ne serait pas irréductible puisque dans ${\mathcal {G}}(A)$ le sommet $j$ ne pourrait être l'origine d'un chemin aboutissant à un autre sommet). Donc dans ce cas $0<s\leq \rho$.

1. Disposition des valeurs propres dans le plan complexe.
   • Démontrons d'abord l'équivalence entre les propositions suivantes :

(i) $\gamma =\rho \mathrm {e} ^{i\phi }$ est une valeur propre de $A$.

(ii) Il existe une matrice $D$ vérifiant $|D|=I$ (unité) telle que $D^{-1}AD=\mathrm {e} ^{i\phi }A$.

(i) $\Rightarrow$ (ii). Soit $Y$ un vecteur propre relatif à $\gamma$. On a vu ci-dessus (cf. (1)) que $|Y|$ était un vecteur extrémal et donc un vecteur propre relatif à $\rho$. On peut écrire $Y=D|Y|$ où $D$ est une matrice diagonale dont tous les éléments diagonaux sont de module 1. Par ailleurs on peut poser $\gamma =\rho \mathrm {e} ^{i\phi }$. On a donc $AD|Y|=\rho \mathrm {e} ^{i\phi }D|y|$ d'où $\mathrm {e} ^{-i\phi }D^{-1}AD|Y|=\rho |Y|=A|Y|$. Mais l'égalité $\mathrm {e} ^{-i\phi }D^{-1}AD|Y|=A|Y|$ entraîne $\mathrm {e} ^{-i\phi }D^{-1}AD=A$. En effet Posons $W=\mathrm {e} ^{-i\phi }D^{-1}AD$. On voit immédiatement que $\forall i\forall j|W_{i,j}|=A_{i,j}$. En écrivant l'égalité $W|Y|=A|Y|$ pour la ligne $i:\quad \sum _{j=1}^{n}W_{i,j}|Y_{j}|=\sum _{j=1}^{n}A_{i,j}|Y_{j}|$ et en tenant compte de $|W_{i,j}|=A_{i,j}$ et $|Y|>0$ on obtient le résultat demandé.

(ii) $\Rightarrow$ (i). Soit $X$ un vecteur extrémal de $A$ et posons $Y=DX$. On a $AY=ADX=\mathrm {e} ^{i\phi }DAD^{-1}DX=\mathrm {e} ^{i\phi }DAX=\mathrm {e} ^{i\phi }D\rho X=\mathrm {e} ^{i\phi }\rho Y=\gamma Y$.

1. • Soit $h$ le nombre de valeurs propres de $A$ de module $\rho$. Considérons l'ensemble ${\mathcal {H}}$ des nombres ${\frac {\gamma }{\rho }}$ où $\gamma$ est valeur propre de module $\rho$ et montrons que cet ensemble est un sous-groupe du groupe multiplicatif des complexes de module 1. En effet si ${\frac {\gamma _{1}}{\rho }}=\mathrm {e} ^{i\varphi _{1}}$ et ${\frac {\gamma _{2}}{\rho }}=\mathrm {e} ^{i\varphi _{2}}$ sont 2 éléments de ${\mathcal {H}}$, en appliquant le préliminaire ci-dessus il existe $D_{1}$ et $D_{2}$ tels que $D_{1}^{-1}AD_{1}=\mathrm {e} ^{i\varphi _{1}}A$ et $D_{2}^{-1}AD_{2}=\mathrm {e} ^{i\varphi _{2}}A$, ce qui entraîne $\mathrm {e} ^{-i\varphi _{1}}D_{1}^{-1}AD_{1}=\mathrm {e} ^{-i\varphi _{2}}D_{2}^{-1}AD_{2}$ soit $\mathrm {e} ^{i(\varphi _{2}-\varphi _{1})}D_{2}D_{1}^{-1}AD_{1}D_{2}^{-1}=A$, ce qui montre que $\mathrm {e} ^{i(\varphi _{2}-\varphi _{1})}={\frac {\mathrm {e} ^{i\varphi _{2}}}{\mathrm {e} ^{i\varphi _{1}}}}\in {\mathcal {H}}$ qui est bien un sous-groupe du groupe des complexes de module 1. En fait ce sous-groupe étant d'ordre $h$ et donc formé de racines h-ième de 1, il coïncide avec l'ensemble de ces racines h-ième.

Il existe donc $D$ telle que $D^{-1}AD=\mathrm {e} ^{-{\frac {2i\pi }{h}}}A$. Si $\Pi (\lambda )$ désigne le polynôme caractéristique de $A$ qui est aussi celui de $D^{-1}AD$ on peut écrire $\Pi (\lambda )=\mathrm {det} (\lambda I-\mathrm {e} ^{-{\frac {2i\pi }{h}}}A)=\mathrm {e} ^{(-1)^{n}{\frac {2in\pi }{h}}}\;\Pi (\mathrm {e} ^{\frac {2i\pi }{h}}\lambda )$. Ceci montre bien l'invariance de l'ensemble des valeurs propres de $A$ par la rotation de centre $O$ et d'angle ${\frac {2\pi }{h}}$. En outre si $\gamma$ est une valeur propre, la valeur propre $\mathrm {e} ^{\frac {2i\pi }{h}}\gamma$ est de même ordre de multiplicité que $\gamma$. En particulier toutes les valeurs propres de module $\rho$ sont simples.

Supposons maintenant $h>1$ et soit $X$ un vecteur extrémal. D'après ce qui précède il existe une matrice diagonale $\Delta$ vérifiant $|\Delta |=I$ telle que $\Delta X$ soit vecteur propre relatif à $\mathrm {e} ^{\frac {2i\pi }{h}}\rho$ et $\Delta ^{-1}A\Delta =\mathrm {e} ^{\frac {2i\pi }{h}}A.\quad \Delta$ est défini à un facteur près, la valeur propre étant simple et le sous-espace propre étant par conséquent une droite vectorielle. Nous pouvons donc décider de choisir $\Delta$ de manière que sa première composante soit $1$, ce qui assure l'unicité. Mais de la même manière $\Delta ^{h}X$ est vecteur propre relatif à $\mathrm {e} ^{\frac {2ih\pi }{h}}\rho =\rho$, ce qui implique $\Delta ^{h}X=X$ et donc $\Delta ^{h}=I$ puisque $X>0$ et $\Delta$ diagonale. Il en résulte que les éléments diagonaux de $\Delta$ sont des racines h-ième de l'unité. Il existe donc une matrice de permutation $S$ telle que ${\tilde {\Delta }}={}^{t}SDS=S^{-1}DS={\begin{pmatrix}\mathrm {e} ^{{\frac {2i\pi }{h}}n_{0}}I_{0}&0&0&\cdots &0\\0&\mathrm {e} ^{{\frac {2i\pi }{h}}n_{1}}I_{1}&0&\cdots &0\\0&0&\mathrm {e} ^{{\frac {2i\pi }{h}}n_{2}}I_{2}&\cdots &0\\.&.&.&\cdots \\.\\0&0&0&\cdots &\mathrm {e} ^{{\frac {2i\pi }{h}}n_{s-1}}I_{s-1}\end{pmatrix}}$ avec $n_{i}\in \mathbb {N} ,\quad n_{0}=0<n_{1}<n_{2}<\dotsb <n_{s-1}<h,\qquad I_{0},I_{1},\dotsc ,I_{s-1}$étant des matrices unités. On a évidemment $s\leq h$.

En posant de même ${\tilde {A}}=S^{-1}AS$ on trouve ${\tilde {\Delta }}^{-1}{\tilde {A}}{\tilde {\Delta }}=\mathrm {e} ^{\frac {2i\pi }{h}}{\tilde {A}}$.

Partitionnons ${\tilde {A}}$ suivant le même schéma que ${\tilde {\Delta }}$ : ${\tilde {A}}={\begin{pmatrix}{\tilde {A}}_{1,1}&{\tilde {A}}_{1,2}&\cdots &{\tilde {A}}_{1,s}\\{\tilde {A}}_{2,1}&{\tilde {A}}_{2,2}&\cdots &{\tilde {A}}_{2,s}\\.&\cdots &.\\{\tilde {A}}_{s,1}&{\tilde {A}}_{s,2}&\cdots &{\tilde {A}}_{s,s}\end{pmatrix}}$.

Nous allons montrer par récurrence que $\forall k\in \{0,1,\dotsc ,s-1\}n_{k}=k$.

L'égalité est vraie pour $k=0$. Supposons qu'elle le soit jusque $k-1<s-1$. L'égalité ${\tilde {\Delta }}^{-1}{\tilde {A}}{\tilde {\Delta }}=\mathrm {e} ^{\frac {2i\pi }{h}}{\tilde {A}}$ donne en ce qui concerne la ligne de blocs N°$k\quad \forall l\in \{1,2,\dotsc ,s\}\mathrm {e} ^{\frac {2i\pi }{h}}{\tilde {A}}_{k,l}=\mathrm {e} ^{{\frac {2i\pi }{h}}(n_{l-1}-n_{k-1})}{\tilde {A}}_{k,l}$. Comme les ${\tilde {A}}_{k,l}$ ne sont pas tous nuls puisque la matrice est irréductible $\exists l\in \{1,2,\dotsc ,s\}\quad n_{l-1}-n_{k-1}=1+ph(p\in \mathbb {Z} )$, soit $n_{l-1}=k+ph$. Mais comme $k<s\leq h$ et $0\leq n_{l-1}<h$ on en déduit $p=0$ par élimination des cas $p<0$ et $p>0$.

Donc $n_{l-1}=k=(k-1)+1=n_{k-1}+1$. Ceci ne peut se réaliser que si $n_{l-1}$ est le successeur immédiat de $n_{k-1}$ dans la suite croissante des $n_{j}$. Donc $l-1=k-1+1=k$ et $n_{l-1}=n_{k}=k$, ce qui achève la récurrence.

D'autre part $\mathrm {e} ^{\frac {2i\pi }{h}}{\tilde {A}}_{k,l}=\mathrm {e} ^{{\frac {2i\pi }{h}}(l-k)}{\tilde {A}}_{k,l}$ montre que si $l-k$ n'est pas congru à $1$ modulo $h$ on a ${\tilde {A}}_{k,l}=0$.

Il reste à prouver que $s=h$. Or en considérant la dernière ligne de blocs on ne peut avoir $n_{l-1}=l-1=s+ph$ que si $p=-1$. En effet si $p\geq 0$ on a $l>s$, ce qui est impossible et si $p<-1,n_{l-1}<0$ également exclu. Donc $l-1=s-h$ soit $l=s-h+1$. Mais $0<l=s-h+1$ et donc $s>h-1$ soit $s\geq h$. Comme on a évidemment $s\leq h$ on a $s=h$, ce qui a achève la démonstration.

Le théorème de Perron Frobenius est donc complètement démontré.

Applications pratiques

• Ce théorème permet de montrer, sous certaines conditions, qu'une chaîne de Markov ergodique sur un espace d'états fini converge en loi vers son unique mesure invariante.

• Le vecteur de Google utilisé lors du calcul des PageRank de Google est un vecteur de Perron-Frobenius.