Annexe A — Théorème de Perron-Frobenius
En 1907, Oskar Perron (1880-1975) a publié une théorie des matrices strictement positives, que Georg Ferdinand Frobenius (1849-1917) a étendu en 1908, 1909 et 1912 au cas des matrices positives au sens large1. Le théorème de Perron-Frobenius, qui résume cette théorie, est en quelque sorte la pièce centrale de la plupart des algorithmes de convergence des matrices stochastiques, et en particulier des algorithmes de PageRank. Nous avons donc cru intéressant de mettre une démonstration en appendice, car en plus de garantir la convergence des algorithmes, le concept de flot est inhérent à la preuve (lemme de propagation de la stricte inégalité).
Théorème A.1 (Perron-Frobenius).
Soit une matrice carrée positive de taille , irréductible. Alors, il existe une valeur propre de , notée , strictement positive, qui a les propriétés suivantes :
- Il existe un vecteur propre gauche et un vecteur propre droit associés à strictement positifs.
- Pour toute valeur propre de , .
- L’espace propre associé à est de dimension .
- Pour toute matrice positive inférieure à , et pour toute valeur propre de , , avec égalité seulement si .
- Si a la cyclicité , alors les valeurs de de module sont exactement les , avec , et les espaces propres associés sont de dimension .
Preuve.
Pour démontrer le théorème de Perron-Frobenius, nous aurons besoin du lemme suivant, que nous appellerons lemme de propagation de la stricte inégalité.
Lemme A.1.
Si est une matrice positive irréductible de taille , et si et sont deux vecteurs positifs tels que , avec au moins une composante pour laquelle il y a inégalité stricte, alors .
En effet, soit une composante pour laquelle il y a inégalité stricte. Comme la matrice est irréductible, pour chaque composante , il existe tel que . On en déduit que , avec inégalité stricte en . En utilisant l’opérateur , on s’assure que chaque composante « bénificiera » par propagation de la stricte inégalité présente en . En d’autres termes, .
Grâce à ce lemme, nous pouvons maintenant aborder la démonstration proprement dite.
-
Considérons l’ensemble des vecteurs positifs de de norme (on prendra la norme : si , ).
Pour chaque de , on pose
À l’évidence, est un réel positif, puisque minoré par et majoré par . Considérons maintenant . est un réel (fini) strictement positif, car on a l’encadrement :
Pour montrer que est une valeur propre, considérons une suite d’éléments de telle que converge vers . Comme est compact, il est possible (théorème de Bolzano-Weierstrass) d’extraire une suite qui converge vers un vecteur .
est un vecteur propre (à droite) de , associé à la valeur . En effet, nous avons . Si il n’y a pas égalité, alors d’après le Lemme 1.1,
ce qui contredit2 le caractère maximal de .
On a donc , ce qui démontre que est un vecteur propre (droit) de , associé à . Le caractère strictement positif de est assuré par le lemme de propagation de la stricte inégalité.
En raisonnant avec , on trouve une valeur propre associée à un vecteur propre gauche de strictement positif. Pour prouver (a), il nous suffit de montrer que . Quitte à interchanger et , supposons . Il suffit alors de prendre tel que 3 et de constater que , ce qui impose , d’où l’égalité.
-
La preuve est la même que pour montrer que . Si , avec , alors , d’où .
-
Le fait que soit une valeur propre simple se démontre aussi grâce au lemme de propagation de la stricte inégalité. En effet, si l’espace propre est de dimension supérieure à 2, il existe un vecteur propre non homogène à . Le vecteur est également un vecteur propre associé à . Par construction, il est non nul, positif, et une de ses composantes au moins est nulle. Par propagation de la stricte inégalité, itérations de vont rendre cette composante strictement positive, ce qui est contradictoire et démontre que est une racine simple.
-
Même preuve que (b) : si , avec , alors , d’où .
Cas d’égalité : impose . est donc strictement positif, puisque homogène à . est une matrice positive qui vérifie , donc .
-
Quitte à considérer , on peut supposer que . Considérons la relation d’équivalence sur les composantes suivante : deux composantes et sont équivalentes si il existe une composante telle que et soient strictement positifs, ou une composante telle que et soient strictement positifs. Alors, la cyclicité de est égale au nombre de classe d’équivalence dans les composantes. En effet, la cyclicité de correspond à la cyclicité sur le graphe sous-jacent (les sommets correspondant aux composantes et les arêtes aux coefficients non nuls). Comme le graphe est fortement connexe (puisque la matrice est irréductible), cette cyclicité se trouve en mettant dans la même classe d’équivalence les successeurs et les antécédents de chaque composantes.
Soient , …, les classes d’équivalence pour la relation antécédent/successeur, rangées dans l’ordre de succession.
-
Si est une racine -ième de l’unité, alors est valeur propre de , et un vecteur propre associé est , avec
En effet, pour dans , on a
-
Soit une valeur propre de module , et un vecteur propre associé. On écrit alors :
En fait, il y a forcément égalité, sinon par le lemme de propagation de la stricte inégalité, ne serait plus valeur propre maximale. Notons au passage que est homogène à . Pour des nombres complexes, la valeur absolue d’une somme n’est égale à la somme des valeurs absolues que si tous les éléments (non nuls) ont même phase. Comme les coefficients de sont positifs, cela implique que tous les antécédents d’une composante donnée de par ont même phase. Or, par construction, les successeurs ont aussi même phase. On peut en déduire que toutes les composantes d’une même classe d’équivalence ont la même phase. De plus, si est la phase de la composante , alors . Par cyclicité, et en utilisant la convention d’écriture , on a :
est donc une racine -ième de l’unité.
Remarquons enfin que compte tenu de tout ce qui a été dit, le vecteur est colinéaire au vecteur défini par
L’espace propre associé à est donc de dimension .
C.Q.F.D.
-
□