$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Algèbre > Algèbre linéaire > Matrices >

Théorème de Perron-Frobenius

Le théorème de Perron-Frobenius est un théorème donnant l'existence d'une valeur propre "dominante" pour une matrice dont tous les coefficients sont strictement positifs, ou plus généralement dont une puissance a tous ses coefficients strictement positifs.

Définition : Une matrice est dite primitive si elle admet une puissance dont tous les termes sont strictement positifs.
Théorème de Perron-Frobenius : Soit $A$ une matrice primitive. Alors elle admet une valeur propre réelle strictement positive $r>0$ telle que
  • pour toute autre valeur propre $s$ de $A$, on a $|s|<r$ ($r$ est une valeur propre dominante);
  • $r$ est une valeur propre simple (son espace propre associé est de dimension 1);
  • il existe un unique vecteur $x^+$ de norme $1$ à coordonnées strictement positives tel que $Ax^+=rx^+.$
La valeur propre $r$ s'appelle la valeur propre de Perron de $A$ et $x^+$ est le vecteur propre de Perron associé.

Le vecteur de Perron-Frobenius est utilisé par les algorithmes de Google pour calculer l'importance d'une page, aussi appelée PageRank. Google voit le web comme un graphe, dont les sommets sont les pages et les arêtes sont les liens allant d'une page vers l'autre. Chaque arête est affectée d'un poids, correspondant à la probabilité qu'on a, lorsqu'on quitte une page, d'aller vers la page suivante. Si d'une page part 4 liens, chaque lien est donc affecté d'un poids 1/4. Prenons l'exemple suivant (où le web comporte 5 pages) :
Dans cet exemple, il est raisonnable de penser que la "Page 4" est la plus importante car c'est vers cette page que le plus d'autres pages pointent. Ensuite, on penser que la "Page 5" est plus importante que la "Page 2", car si elles ont chacun un lieu entrant, celui de la "Page 5" vient de la page la plus importante, etc...

Le point de départ du PageRank est de donner des valeurs numériques à l'importance d'une page modélisant le phénomène précédent. L'idée est d'associer à chaque page la probabilité qu'on a, lorsqu'on visite le web, d'être à cette page donnée. Ceci peut se faire à l'aide de l'algorithme suivant. On introduit la matrice de transition du graphe, qui s'écrit

Le coefficient $a_{i,j}$ représente la probabilité, étant sur la page $j$, d'aller sur la page $i$. On introduit aussi le vecteur initial

qui représente l'état initial : on a autant de chances d'être sur n'importe quel page. On itère ensuite la matrice $A$ par la relation

Le vecteur $X_n$ représente la probabilité d'être sur chaque page lorsqu'on a suivi $n$ liens. Il se trouve que la suite $(X_n)$ converge, et que les termes de la limite donnent le poids de chaque page. Et ce vecteur limite n'est autre que le vecteur de Perron-Frobenius de la matrice $A$ (même si ici elle n'est pas primitive, il faut un petit peu tricher!).

La méthode que l'on décrit ici est très générale en probabilité. Elle consiste à rechercher l'état stable d'une chaine de Markov (ou graphe probabiliste).

Consulter aussi...
Recherche alphabétique
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Recherche thématique
  • Algèbre
  • Analyse
  • Applications
  • Arithmétique
  • Probabilité et statistiques
  • Géométrie
  • Fondements
  • Histoire
  • Mathématiques discrètes
  • Mathématiques interactives