Théorème de Perron-Frobenius

Pour les articles homonymes, voir Perron et Théorème de Frobenius.

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

1. Désignons par ${\displaystyle S}$ l'ensemble des vecteurs de ${\displaystyle (\mathbb {R} _{+})^{n}}$ non nuls et par ${\displaystyle S^{0}}$ l'ensemble de ces vecteurs (colonne) strictement positifs. Définissons l'application ${\displaystyle r}$ de ${\displaystyle S}$ dans ${\displaystyle \mathbb {R} _{+}}$ par ${\displaystyle 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 ${\displaystyle r(X)=\sup \left\{\lambda \in \mathbb {R} _{+}:\lambda X\leq AX\right\}}$.
   • l'application ${\displaystyle r}$ admet un point de maximum sur S.

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

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

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

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

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

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

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

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

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

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

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

1. • Tout vecteur extremal est strictement positif.

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

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

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

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

Supposons en effet que ${\displaystyle X}$ et ${\displaystyle 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 ${\displaystyle A}$ ayant une composante nulle, ce qui est contradictoire.

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

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

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

On a ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle \Pi '(\rho )\neq 0}$ puisque tous les éléments de ${\displaystyle B(\rho )}$ sont non nuls et de même signe. Ceci montre bien que ${\displaystyle \rho }$ est valeur propre simple de ${\displaystyle A}$^[4].

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

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

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

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

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

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

(ii) ${\displaystyle \Rightarrow }$ (i). Soit ${\displaystyle X}$ un vecteur extrémal de ${\displaystyle A}$ et posons ${\displaystyle Y=DX}$. On a ${\displaystyle 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 ${\displaystyle h}$ le nombre de valeurs propres de ${\displaystyle A}$ de module ${\displaystyle \rho }$. Considérons l'ensemble ${\displaystyle {\mathcal {H}}}$ des nombres ${\displaystyle {\frac {\gamma }{\rho }}}$ où ${\displaystyle \gamma }$ est valeur propre de module ${\displaystyle \rho }$ et montrons que cet ensemble est un sous-groupe du groupe multiplicatif des complexes de module 1. En effet si ${\displaystyle {\frac {\gamma _{1}}{\rho }}=\mathrm {e} ^{i\varphi _{1}}}$ et ${\displaystyle {\frac {\gamma _{2}}{\rho }}=\mathrm {e} ^{i\varphi _{2}}}$ sont 2 éléments de ${\displaystyle {\mathcal {H}}}$, en appliquant le préliminaire ci-dessus il existe ${\displaystyle D_{1}}$ et ${\displaystyle D_{2}}$ tels que ${\displaystyle D_{1}^{-1}AD_{1}=\mathrm {e} ^{i\varphi _{1}}A}$ et ${\displaystyle D_{2}^{-1}AD_{2}=\mathrm {e} ^{i\varphi _{2}}A}$, ce qui entraîne ${\displaystyle \mathrm {e} ^{-i\varphi _{1}}D_{1}^{-1}AD_{1}=\mathrm {e} ^{-i\varphi _{2}}D_{2}^{-1}AD_{2}}$ soit ${\displaystyle \mathrm {e} ^{i(\varphi _{2}-\varphi _{1})}D_{2}D_{1}^{-1}AD_{1}D_{2}^{-1}=A}$, ce qui montre que ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle D}$ telle que ${\displaystyle D^{-1}AD=\mathrm {e} ^{-{\frac {2i\pi }{h}}}A}$. Si ${\displaystyle \Pi (\lambda )}$ désigne le polynôme caractéristique de ${\displaystyle A}$ qui est aussi celui de ${\displaystyle D^{-1}AD}$ on peut écrire ${\displaystyle \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 ${\displaystyle A}$ par la rotation de centre ${\displaystyle O}$ et d'angle ${\displaystyle {\frac {2\pi }{h}}}$. En outre si ${\displaystyle \gamma }$ est une valeur propre, la valeur propre ${\displaystyle \mathrm {e} ^{\frac {2i\pi }{h}}\gamma }$ est de même ordre de multiplicité que ${\displaystyle \gamma }$. En particulier toutes les valeurs propres de module ${\displaystyle \rho }$ sont simples.

Supposons maintenant ${\displaystyle h>1}$ et soit ${\displaystyle X}$ un vecteur extrémal. D'après ce qui précède il existe une matrice diagonale ${\displaystyle \Delta }$ vérifiant ${\displaystyle |\Delta |=I}$ telle que ${\displaystyle \Delta X}$ soit vecteur propre relatif à ${\displaystyle \mathrm {e} ^{\frac {2i\pi }{h}}\rho }$ et ${\displaystyle \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 ${\displaystyle \Delta }$ de manière que sa première composante soit ${\displaystyle 1}$, ce qui assure l'unicité. Mais de la même manière ${\displaystyle \Delta ^{h}X}$ est vecteur propre relatif à ${\displaystyle \mathrm {e} ^{\frac {2ih\pi }{h}}\rho =\rho }$, ce qui implique ${\displaystyle \Delta ^{h}X=X}$ et donc ${\displaystyle \Delta ^{h}=I}$ puisque ${\displaystyle X>0}$ et ${\displaystyle \Delta }$ diagonale. Il en résulte que les éléments diagonaux de ${\displaystyle \Delta }$ sont des racines h-ième de l'unité. Il existe donc une matrice de permutation ${\displaystyle S}$ telle que ${\displaystyle {\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 ${\displaystyle 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 ${\displaystyle s\leq h}$.

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

Partitionnons ${\displaystyle {\tilde {A}}}$ suivant le même schéma que ${\displaystyle {\tilde {\Delta }}}$ : ${\displaystyle {\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 ${\displaystyle \forall k\in \{0,1,\dotsc ,s-1\}n_{k}=k}$.

L'égalité est vraie pour ${\displaystyle k=0}$. Supposons qu'elle le soit jusque ${\displaystyle k-1<s-1}$. L'égalité ${\displaystyle {\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°${\displaystyle 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 ${\displaystyle {\tilde {A}}_{k,l}}$ ne sont pas tous nuls puisque la matrice est irréductible ${\displaystyle \exists l\in \{1,2,\dotsc ,s\}\quad n_{l-1}-n_{k-1}=1+ph(p\in \mathbb {Z} )}$, soit ${\displaystyle n_{l-1}=k+ph}$. Mais comme ${\displaystyle k<s\leq h}$ et ${\displaystyle 0\leq n_{l-1}<h}$ on en déduit ${\displaystyle p=0}$ par élimination des cas ${\displaystyle p<0}$ et ${\displaystyle p>0}$.

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

D'autre part ${\displaystyle \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 ${\displaystyle l-k}$ n'est pas congru à ${\displaystyle 1}$ modulo ${\displaystyle h}$ on a ${\displaystyle {\tilde {A}}_{k,l}=0}$.

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

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