Théorème de Perron-Frobenius

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Perron et Théorème de Frobenius.

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

Théorème de Perron Frobenius pour une matrice positive irréductible[modifier | modifier le code]

Théorème de Perron-Frobenius —  Soit A une matrice à coefficients positifs 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 \le \rho \le S.
  • Si n\ge 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 {}^tSAS=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.

Applications pratiques[modifier | modifier le code]

  • Ce théorème permet de montrer, sous certaines conditions, qu'une chaîne de Markov 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[2].

Notes et références[modifier | modifier le code]

  1. Carl Meyer, Matrix analysis and applied linear algebra, SIAM (ISBN 0-89871-454-0, lire en ligne)8.3.6 p. 681)
  2. a et b Bachir Bekka, Le théorème de Perron-Frobenius, les chaînes de Markov et un célèbre moteur de recherche
  3.  \Pi'(\rho)=\mathrm{Tr}(B(\rho)) et \rho est la plus grande racine réelle (c'est une racine simple) du polynôme réel \Pi(\lambda) qui vérifie \lim_{\lambda \rightarrow +\infty}\Pi(\lambda)=+\infty . On voit que B(\rho) est strictement positive.