Le théorème de Perron-Frobenius

Le théorème que nous allons vous exposer n'est pas seulement splendide.

It is a testament to the fact that beautiful mathematics eventually tend to be useful, and useful mathematics eventually tend to be beautiful.

On en trouve en effet des applications, non seulement un peu partout en mathématiques, mais aussi en économie, en théorie des populations, dans les réseaux sociaux etc². On peut considérer par exemple que l'algorithme PageRank de Google en est un lointain avatar. Ce théorème a été démontré en 1907 par Oskar Perron (1880-1975).

Théorème 11 (de Perron)   Soit $A$ une matrice carrée à coeffficients réels strictement positifs. Alors $A$ a une valeur propre simple $\alpha$ qui est réelle, strictement positive et strictement supérieure au module de toute autre valeur propre. À cette valeur propre maximale $\alpha$ correspond un vecteur propre dont toutes les coordonnées sont strictement positives.

La beauté du résultat tient d'une part à son élégance, d'autre part dans un apparent paradoxe. La décomposition spectrale d'une matrice est liée à l'endomorphisme qu'elle représente, et elle est donc invariante par changement de base. La conclusion du théorème (existence d'une valeur propre réelle supérieure au module de toute autre valeur propre) est liée à l'endomorphisme et non à la matrice. Or l'hypothèse (coefficients strictement positifs) n'est pas invariante par changement de base. Pour comprendre ce paradoxe, il faut interpréter l'hypothèse de façon géométrique. Par exemple en dimension $2$, considérez le quart de plan formé des vecteurs à coordonnées strictement positives. Le fait que $A$ soit à coefficients strictement positifs entraîne que le produit par $A$ d'un vecteur à coordonnées strictement positives reste dans le même quart de plan. En d'autres termes, l'endomorphisme laisse stable ce quart de plan. Il n'est donc pas surprenant qu'il y ait dans ce même quart de plan une direction invariante. Soit dit entre parenthèses, Perron n'en était pas à un paradoxe près :

Soit $N$ le plus grand entier naturel. Si $N>1$, alors $N^2>N$, ce qui contredit la définition. Donc $N=1$.

Démonstration : D'abord quelques notations pour faciliter la lecture. Pour tous vecteurs $u=(u_i)_{i=1,\ldots,n}$ et $v=(v_i)_{i=1,\ldots,n}$ de $\mathbb{R}^n$,

$\bullet$

$u\leqslant v$ signifie $\forall i=1,\ldots,n ,\; u_i\leqslant v_i$,

$\bullet$

$u< v$ signifie $\forall i=1,\ldots,n ,\; u_i< v_i$,

$\bullet$

$\mathbf{0}$ désigne le vecteur nul de $\mathbb{R}^n$,

$\bullet$

$\mathbf{1}$ désigne le vecteur de $\mathbb{R}^n$ dont toutes les coordonnées valent $1$.

Soit $S$ l'ensemble des réels $\lambda\geqslant 0$ tels qu'il existe $v=(v_i)\in \mathbb{R}^n$ vérifiant :

$$\mathbf{0}\leqslant v\leqslant \mathbf{1}$$   et$$\quad \sum_{i=1}^n v_i= 1$$   et$$\quad \lambda v\leqslant A v\;.$$

Soit $\lambda$ une valeur propre de $A$ et $w=(w_i)$ un vecteur propre associé. Pour tout $i=1,\ldots,n$, posons $u_i=\vert w_i\vert$, puis $u=(u_i)_{i=1,\ldots,n}$. Par l'inégalité triangulaire :

$$\lambda w = Aw\;\Longrightarrow \vert\lambda\vert u \leqslant A u\;.$$

En divisant $u$ par la somme de ses coordonnées, on en déduit que $\vert\lambda\vert$ appartient à l'ensemble $S$, qui est donc non vide. Pour tout $i,j=1,\ldots,n$, notons $a_{ij}>0$ le coefficient d'ordre $(i,j)$ de $A$. Tout élément $\beta$ de $S$ vérifie :

$$\forall i=1\ldots,n ,\; \beta v_i\leqslant \sum_{j=1}^n a_{ij} v_j \leqslant \left(\max_{j=1}^n v_j\right) \left(\sum_{j=1}^n a_{ij}\right)\;.$$

Donc $\beta\leqslant \max_i \sum_j a_{ij}$ : l'ensemble $S$ est borné. Soit $\alpha$ la borne supérieure de $S$, et $(\alpha_n)_{n\in\mathbb{N}}$ une suite d'éléments de $S$ convergeant vers $\alpha$. À chacun des $\alpha_n$ correspond un vecteur $v^{(n)}$, dont les coordonnées sont positives ou nulles et de somme $1$, et tel que $\alpha_n v^{(n)}\leqslant Av^{(n)}$. Par le théorème de Bolzano-Weierstrass, on peut extraire de la suite $(v^{(n)})_{n\in\mathbb{N}}$ une sous-suite $(v^{(n_k)})_{k\in\mathbb{N}}$ convergente. Soit $v$ la limite de cette sous-suite. Les coordonnées de $v$ sont encore positives ou nulles et de somme $1$ et en particulier $v$ est non nul. En passant à la limite en $k$ :

$$\forall k\in \mathbb{N} ,\;\alpha_{n_k} v^{(n_k)}\leqslant Av^{(n_k)} \;\Longrightarrow\; \alpha v \leqslant A v\;.$$

Supposons $\alpha v\neq A v$. Le vecteur $Av-\alpha v$ a toutes ses coordonnées positives ou nulles et l'une au moins est non nulle. Donc son produit par $A$ a toutes ses coordonnées strictement positives (d'après l'hypothèse sur $A$) : $A(Av -\alpha v)>\mathbf{0}$. Notons $v'$ le vecteur proportionnel à $A v$ dont toutes les coordonnées sont positives ou nulles et de somme $1$ : $Av'>\alpha v'$, donc il existe $\varepsilon >0$ tel que $Av'>(\alpha+ \varepsilon )v'$, ce qui contredit la définition de $\alpha$ comme borne supérieure de $S$. On conclut donc que $\alpha v=Av$, donc $\alpha$ est valeur propre, et $v$ est un vecteur propre associé à $\alpha$. A priori, les coordonnées de $v$ sont positives ou nulles. Mais alors les coordonnées de $A v$ sont strictement positives. Puisque $Av=\alpha v$, on en conclut que $\alpha>0$ et $v>\mathbf{0}$. Montrons maintenant que $\alpha$ est strictement supérieure au module de toute autre valeur propre. Soit $\lambda$ une valeur propre de $A$ et $w=(w_i)$ un vecteur propre associé. Nous avons déjà montré que $\vert\lambda\vert\in S$, en utilisant l'inégalité triangulaire.

$$\lambda w = Aw\;\Longrightarrow \vert\lambda\vert u \leqslant A u\;.$$

Comme $\alpha$ est la borne supérieure de $S$, $\vert\lambda\vert\leqslant \alpha$. Supposons $\vert\lambda\vert=\alpha$ : $\alpha u \leqslant A u$. Par le raisonnement déjà effectué ci-dessus, on en conclut que nécessairement $\alpha u = A u$, donc les inégalités dans la majoration ci-dessus sont en fait des égalités. Mais ceci n'est possible que si $u$ est proportionnel à $w$. Mais alors, $u$ est aussi vecteur propre associé à $\lambda$, donc $\lambda=\alpha$. Il ne reste qu'un petit point à démontrer, mais c'est le plus délicat : $\alpha$ est valeur propre simple. Pour cela, nous commençons par montrer que le sous-espace propre associé à $\alpha$ est une droite. Soit $w$ un vecteur propre associé à $\alpha$ et comme ci-dessus $u$ le vecteur des modules des coordonnées de $w$. Par un raisonnement déjà vu,

$$\alpha w = A w\;\Longrightarrow \alpha u \leqslant A u \;\Longrightarrow\; \alpha u = A u \;\Longrightarrow u>\mathbf{0}\;.$$

De sorte qu'aucun vecteur propre associé à $\alpha$ ne peut avoir de coordonnée nulle. Mais si on pouvait trouver deux vecteurs propres indépendants associés à $\alpha$, alors on pourrait en former une combinaison linéaire, qui serait encore vecteur propre associé à $\alpha$, et dont par exemple la première coordonnée serait nulle. C'est impossible, donc le sous-espace propre associé à $\alpha$ est de dimension $1$. Nous allons utiliser cela pour démontrer que $\alpha$ est racine simple du polynôme caractéristique $P_A(X)=\mathrm{det}(A-X I)$. Considérons le polynôme $P_A(\alpha+X)$, qui est le déterminant de $(A-\alpha I)-X I$. Son terme constant, qui est le déterminant de $A-\alpha I$, est nul. Le coefficient du terme de degré $1$ est la trace (somme des coefficients diagonaux) de la comatrice de $A-\alpha I$ (matrice des mineurs d'ordre $n-1$, affectés de signes alternés). Notons $C$ cette comatrice. Comme le sous-espace propre associé à $\alpha$ est de dimension $1$, $A-\alpha I$ est de rang $n-1$, donc la matrice $C$ n'est pas nulle. Nous voulons démontrer que sa trace est non nulle. Or $C(A-\alpha I)=(A-\alpha I)C=0$, car le déterminant de $A-\alpha I$ est nul. En particulier, tous les vecteurs colonnes de $C$ sont des vecteurs propres de $A$ associés à $\alpha$. En tant que tels, ils sont proportionnels à $v$, dont toutes les coordonnées sont strictement positives. Les vecteurs lignes sont des vecteurs propres de ${^t\!A}$ associés à $\alpha$ : ils sont donc également proportionnels à un vecteur à coordonnées strictement positives. Ceci entraîne que tous les coefficients de $C$ sont tous non nuls et de même signe (tous strictement positifs ou tous strictement négatifs). En particulier la trace est non nulle, et $\alpha$ est racine simple de $P_A(X)$.$\square$ Ferdinand Georg Frobenius (1849-1917) étendit en 1912 le théorème de son jeune collègue Perron aux matrices à coefficients positifs ou nuls, dont une puissance entière a ses coefficients strictement positifs (matrices irréductibles). C'est la version qui est à la base de la plupart des applications, en particulier aux chaînes et processus de Markov, mais nous aurons l'occasion de vous en reparler.

Professeur à l'université de Tübingen, puis de Göttingen, Perron est l'auteur de 218 articles, dont quelques uns publiés après 80 ans, ce qui est une longévité assez exceptionnelle. Il a par ailleurs continué sa pratique assidue de l'alpinisme bien au-delà de 70 ans. Quant à Frobenius, professeur à Zürich, puis Berlin, on lui doit une grande partie de la théorie des matrices, en particulier ce qui concerne les matrices compagnons. Il a montré qu'une matrice quelconque est semblable à une matrice diagonale par blocs, dont les blocs sont des matrices compagnons. Il est resté célèbre pour ses colères et ses opinions tranchées : voyez ce qu'il écrit au sujet de Sophus Lie (1842-1899).

Lie se contente de très peu de connaissances dans ses innombrables papiers. Il a lu très peu de travaux des grands mathématiciens classiques et en a compris encore moins. Ce que Lie nous fournit, c'est une doctrine de méthodes de peu d'utilité, dont le formalisme dénudé, qui à y bien penser nous rappelle les pires moments de la théorie des invariants, doit rebuter tout lecteur au goût éduqué.