09 · Valeurs et vecteurs propres¶
Intuition
Une matrice déforme l'espace : elle tourne, étire, écrase. Mais il existe souvent des directions privilégiées que la transformation ne fait qu'allonger ou raccourcir, sans les faire tourner.
Ces directions sont les vecteurs propres, et le facteur d'allongement est la valeur propre associée.
Trouver ces directions, c'est trouver le point de vue depuis lequel la matrice devient simple — c'est tout l'objet du chapitre suivant.
1. Définitions¶
Définition
Soit \(\mathbf{A}\) une matrice carrée d'ordre \(n\). Un scalaire \(\lambda\) est valeur propre de \(\mathbf{A}\) s'il existe un vecteur \(\mathbf{x} \neq \mathbf{0}\) tel que
Un tel \(\mathbf{x}\) est un vecteur propre associé à \(\lambda\).
La condition \(\mathbf{x}\neq\mathbf{0}\) est essentielle
\(\mathbf{A}\mathbf{0} = \lambda\mathbf{0}\) est vrai pour tout \(\lambda\). Sans exclure le vecteur nul, tout scalaire serait valeur propre et la notion serait vide.
En revanche, \(\lambda = 0\) peut être valeur propre : cela signifie qu'il existe \(\mathbf x\neq\mathbf 0\) avec \(\mathbf{Ax}=\mathbf 0\), c'est-à-dire que \(\mathbf A\) n'est pas inversible.
1.1 Sous-espace propre¶
L'ensemble des vecteurs propres associés à \(\lambda\), complété par le vecteur nul, est
C'est un sous-espace vectoriel : stable par somme et par multiplication par un scalaire. Sa dimension est appelée multiplicité géométrique de \(\lambda\).
2. Le polynôme caractéristique¶
Le point de départ du calcul
Le polynôme caractéristique de \(\mathbf{A}\) est
C'est un polynôme de degré \(n\) en \(\lambda\), dont les racines sont exactement les valeurs propres.
Deux conventions
Certains ouvrages définissent \(\chi_{\mathbf A}(\lambda) = \det(\lambda\mathbf I - \mathbf A)\), ce qui change le signe global quand \(n\) est impair mais pas les racines. Les deux conventions donnent les mêmes valeurs propres ; adoptez celle de votre enseignant et n'en changez pas en cours de copie.
2.1 Cas \(2\times2\) — la formule à connaître¶
Démonstration. Pour \(\mathbf A = \begin{pmatrix}a&b\\c&d\end{pmatrix}\) :
Gain de temps considérable
En dimension 2, on n'écrit jamais \(\mathbf{A}-\lambda\mathbf{I}\) : on lit directement la trace et le déterminant.
2.2 Relations générales¶
Si \(\lambda_1,\dots,\lambda_n\) sont les valeurs propres comptées avec multiplicité (dans \(\mathbb{C}\)) :
Le meilleur outil de vérification du chapitre
Après avoir trouvé les valeurs propres, vérifiez que leur somme donne la trace et leur produit le déterminant. C'est instantané et cela détecte quasiment toutes les erreurs de calcul.
3. Méthode de résolution¶
Les quatre étapes
- Calculer \(\chi_{\mathbf{A}}(\lambda) = \det(\mathbf{A}-\lambda\mathbf{I})\).
- Résoudre \(\chi_{\mathbf{A}}(\lambda)=0\) : ce sont les valeurs propres.
- Vérifier somme = trace et produit = déterminant.
- Pour chaque \(\lambda\), résoudre le système \((\mathbf{A}-\lambda\mathbf{I})\mathbf{x}=\mathbf{0}\) par le pivot.
Le système de l'étape 4 est toujours singulier
C'est normal et attendu : \(\det(\mathbf A-\lambda\mathbf I)=0\) par construction. Vous obtiendrez donc toujours au moins une ligne nulle après échelonnement.
Si vous n'en obtenez pas, c'est que la valeur propre est fausse — ou que le calcul de \(\chi_{\mathbf A}\) l'était.
3.1 Exemple d'ordre 2¶
Valeurs propres. \(\operatorname{tr}=7\), \(\det = 12-2 = 10\).
Valeurs propres : \(\lambda_1 = 2\), \(\lambda_2 = 5\).
Vérification : \(2+5 = 7\) ✓ et \(2\times5 = 10\) ✓
Vecteurs propres pour \(\lambda=2\).
Le système \(2x+y=0\) (la seconde ligne est identique) donne \(y = -2x\).
Vecteurs propres pour \(\lambda=5\).
Le système \(-x+y=0\) donne \(y = x\).
Vérification directe : \(\mathbf{A}\begin{pmatrix}1\\1\end{pmatrix} = \begin{pmatrix}5\\5\end{pmatrix} = 5\begin{pmatrix}1\\1\end{pmatrix}\) ✓
3.2 Exemple d'ordre 3¶
Développons selon la deuxième ligne (deux zéros) :
Valeurs propres : \(\lambda=3\) (multiplicité algébrique 2) et \(\lambda=1\) (multiplicité 1).
Vérification : \(3+3+1 = 7 = \operatorname{tr}\) ✓ ; \(3\times3\times1 = 9\), et \(\det\mathbf A = 3(4-1) = 9\) ✓
Sous-espace \(E_3\).
Une seule équation indépendante : \(-x+z=0\), soit \(z = x\), et \(y\) libre.
Sous-espace \(E_1\).
Équations : \(x+z=0\) et \(y=0\).
4. Multiplicités¶
Deux multiplicités à distinguer
- Algébrique \(m_a(\lambda)\) : ordre de \(\lambda\) comme racine de \(\chi_{\mathbf{A}}\).
- Géométrique \(m_g(\lambda) = \dim E_\lambda\) : nombre de directions propres indépendantes.
On a toujours
Dans l'exemple d'ordre 3 ci-dessus : pour \(\lambda=3\), \(m_a = m_g = 2\) — les deux coïncident.
Contre-exemple où elles diffèrent :
\(\chi(\lambda) = (1-\lambda)^2\), donc \(m_a(1) = 2\). Mais
donne \(y = 0\) et \(x\) libre : \(E_1 = \operatorname{Vect}\binom10\), de dimension 1. \(m_g(1) = 1 < 2 = m_a(1)\).
C'est l'obstruction à la diagonalisation
Cette matrice n'est pas diagonalisable, précisément parce qu'elle n'a qu'une seule direction propre alors qu'il en faudrait deux. Le chapitre 10 en fait le critère central.
5. Propriétés utiles¶
À connaître
| Propriété | Énoncé |
|---|---|
| Matrice triangulaire | Les valeurs propres sont les coefficients diagonaux |
| Inversibilité | \(\mathbf A\) inversible \(\iff\) 0 n'est pas valeur propre |
| Puissance | \(\lambda\) v.p. de \(\mathbf A\) \(\implies\) \(\lambda^k\) v.p. de \(\mathbf A^k\) |
| Inverse | \(\lambda\) v.p. de \(\mathbf A\) inversible \(\implies\) \(\frac1\lambda\) v.p. de \(\mathbf A^{-1}\) |
| Transposée | \(\mathbf A\) et \(\mathbf A^\top\) ont le même polynôme caractéristique |
| Polynôme | \(\lambda\) v.p. \(\implies\) \(P(\lambda)\) v.p. de \(P(\mathbf A)\) |
Le vecteur propre est conservé dans toutes ces opérations : si \(\mathbf{Ax}=\lambda\mathbf{x}\), alors \(\mathbf{A}^k\mathbf{x} = \lambda^k\mathbf{x}\), avec le même \(\mathbf x\).
Théorème d'indépendance
Des vecteurs propres associés à des valeurs propres deux à deux distinctes sont linéairement indépendants.
Conséquence majeure : si \(\mathbf{A}\) d'ordre \(n\) possède \(n\) valeurs propres distinctes, elle possède \(n\) vecteurs propres indépendants — elle est donc diagonalisable.
6. Théorème de Cayley-Hamilton¶
Énoncé
Toute matrice carrée annule son propre polynôme caractéristique :
Exemple d'ordre 2. Si \(\chi(\lambda)=\lambda^2-t\lambda+d\) avec \(t = \operatorname{tr}\mathbf A\) et \(d = \det\mathbf A\), alors
C'est exactement la relation constatée à l'exercice 4 du chapitre 05 et utilisée pour inverser au chapitre 08.
Une « démonstration » séduisante et fausse
« \(\chi_{\mathbf A}(\mathbf A) = \det(\mathbf A - \mathbf A\mathbf I) = \det(\mathbf 0) = 0\). »
C'est faux : \(\chi_{\mathbf A}(\lambda)\) est un polynôme scalaire, et y substituer une matrice n'est pas la même opération que remplacer \(\lambda\) par \(\mathbf A\) à l'intérieur du déterminant. Le résultat est juste, le raisonnement ne l'est pas.
Application pratique : Cayley-Hamilton permet de réduire toute puissance \(\mathbf{A}^k\) à une combinaison de \(\mathbf{I}, \mathbf{A},\dots, \mathbf{A}^{n-1}\), et de calculer \(\mathbf{A}^{-1}\) quand \(\det\mathbf A\neq0\).
Exemples traités¶
Exemple 1 — Valeurs propres complexes
\(\operatorname{tr}=0\), \(\det=1\), donc \(\chi(\lambda)=\lambda^2+1\).
Aucune valeur propre réelle. C'est géométriquement évident : \(\mathbf R\) est la rotation d'angle \(\frac\pi2\), et aucune direction du plan n'est préservée par une rotation d'un quart de tour.
Dans \(\mathbb{C}\), les valeurs propres sont \(i\) et \(-i\).
Info
Toute matrice réelle d'ordre impair a au moins une valeur propre réelle : un polynôme réel de degré impair a toujours une racine réelle. En dimension 3, toute rotation possède donc un axe.
Exemple 2 — Utiliser les propriétés
Soit \(\mathbf{A}\) d'ordre 3 avec valeurs propres \(1\), \(2\), \(-3\). Déterminer les valeurs propres de \(\mathbf{A}^2 - 2\mathbf{A}+3\mathbf{I}\).
Posons \(P(X) = X^2-2X+3\). Les valeurs propres de \(P(\mathbf A)\) sont les \(P(\lambda_i)\) :
- \(P(1) = 1-2+3 = 2\)
- \(P(2) = 4-4+3 = 3\)
- \(P(-3) = 9+6+3 = 18\)
Vérification : \(\det(P(\mathbf A)) = 2\times3\times18 = 108\) et \(\operatorname{tr}(P(\mathbf A)) = 23\).
Exemple 3 — Matrice stochastique
Les lignes somment à 1 : d'après l'exercice 9 du chapitre 08, \(\lambda=1\) est valeur propre, de vecteur propre \(\binom11\).
L'autre valeur propre s'obtient par la trace : \(\lambda_1+\lambda_2 = 1{,}3\), donc \(\lambda_2 = 0{,}3\).
Vérification par le déterminant : \(0{,}42-0{,}12 = 0{,}30\), et \(1\times0{,}3 = 0{,}3\) ✓
Interprétation
La valeur propre 1 correspond à l'état d'équilibre. La seconde, \(0{,}3 < 1\), mesure la vitesse de convergence vers cet équilibre : l'écart à l'équilibre est multiplié par \(0{,}3\) à chaque étape.
C'est le principe des chaînes de Markov, au programme de recherche opérationnelle en deuxième année.
Erreurs fréquentes¶
| Erreur | Correction |
|---|---|
| Accepter \(\mathbf x = \mathbf 0\) comme vecteur propre | Interdit par définition |
| Refuser \(\lambda = 0\) | Autorisé, signifie non inversible |
| Oublier de vérifier trace et déterminant | Perte de temps garantie |
| Confondre \(m_a\) et \(m_g\) | \(m_g \leqslant m_a\), pas d'égalité en général |
| Résoudre \((\mathbf A - \lambda\mathbf I)\mathbf x = \mathbf x\) | C'est \(= \mathbf 0\) |
| Chercher des valeurs propres réelles quand \(\Delta<0\) | Il n'y en a pas dans \(\mathbb R\) |
Exercices¶
★ Exercice 1. Déterminer valeurs propres et vecteurs propres.
a) \(\begin{pmatrix}3&0\\0&-2\end{pmatrix}\) b) \(\begin{pmatrix}5&2\\2&5\end{pmatrix}\) c) \(\begin{pmatrix}1&2\\3&2\end{pmatrix}\)
★ Exercice 2. Sans calcul, donner les valeurs propres.
a) \(\begin{pmatrix}2&5&7\\0&-1&3\\0&0&4\end{pmatrix}\) b) \(\mathbf{I}_5\) c) \(\begin{pmatrix}0&0\\0&0\end{pmatrix}\)
★★ Exercice 3. Pour \(\mathbf{A}=\begin{pmatrix}1&1&1\\1&1&1\\1&1&1\end{pmatrix}\) :
a) Calculer \(\mathbf{A}^2\) et en déduire une relation annulatrice. b) Déterminer les valeurs propres et leurs multiplicités. c) Déterminer les sous-espaces propres.
★★ Exercice 4. Soit \(\mathbf{A}=\begin{pmatrix}2&1&0\\0&2&0\\0&0&3\end{pmatrix}\).
a) Valeurs propres et multiplicités algébriques. b) Sous-espaces propres et multiplicités géométriques. c) Que peut-on en conclure quant à la diagonalisabilité ?
★★ Exercice 5. Soit \(\mathbf{A}\) telle que \(\mathbf{A}^2=\mathbf{A}\) (matrice de projection).
a) Montrer que les seules valeurs propres possibles sont 0 et 1. b) Donner un exemple d'ordre 2 ayant les deux.
★★★ Exercice 6. Déterminer les éléments propres de
Indication : la somme de chaque ligne est constante.
★★★ Exercice 7. Soit \(\mathbf{A}\) d'ordre \(n\) et \(\lambda\) une valeur propre de vecteur propre \(\mathbf{x}\).
a) Montrer que \(\lambda^k\) est valeur propre de \(\mathbf{A}^k\), de même vecteur propre. b) Si \(\mathbf{A}\) est inversible, montrer que \(\frac1\lambda\) est valeur propre de \(\mathbf{A}^{-1}\). c) Montrer que \(\mathbf{A}\) et \(\mathbf{A}^\top\) ont les mêmes valeurs propres. d) Ont-elles les mêmes vecteurs propres ? Donner un contre-exemple.
★★★ Exercice 8. Soit \(\mathbf{A}\) d'ordre 3 vérifiant \(\mathbf{A}^3 = \mathbf{A}\).
a) Quelles sont les valeurs propres possibles ? b) Si de plus \(\operatorname{tr}\mathbf{A}=1\) et \(\det\mathbf{A}=0\), déterminer le spectre.
★★★★ Exercice 9. Soit \(\mathbf{F}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\) (matrice de Fibonacci).
a) Déterminer ses valeurs propres. On notera \(\varphi\) la plus grande. b) Déterminer les vecteurs propres. c) En admettant que \(F_n = \alpha\varphi^n + \beta\psi^n\) pour des constantes \(\alpha,\beta\) à déterminer, retrouver la formule de Binet. d) En déduire que \(F_n\) est l'entier le plus proche de \(\dfrac{\varphi^n}{\sqrt5}\).
★★★★ Exercice 10 — lien informatique. L'algorithme PageRank attribue à chaque page web un score. Soit \(\mathbf{M}\) la matrice de transition d'un surfeur aléatoire sur un graphe à \(n\) pages.
a) Justifier que \(\mathbf{M}^\top\) admet 1 comme valeur propre. b) Le score PageRank est le vecteur propre associé, normalisé. Expliquer pourquoi la méthode de la puissance — itérer \(\mathbf{v}_{k+1} = \mathbf{M}^\top\mathbf{v}_k\) — converge vers ce vecteur. c) Le taux de convergence dépend du rapport \(|\lambda_2|/|\lambda_1|\). Google utilise un facteur d'amortissement \(d = 0{,}85\) qui garantit \(|\lambda_2|\leqslant d\). Combien d'itérations pour gagner 6 chiffres de précision ? d) Pourquoi ne calcule-t-on jamais le polynôme caractéristique d'une matrice de plusieurs milliards de lignes ?
Corrigés¶
Corrigé — Exercice 1
a) Diagonale : valeurs propres \(3\) et \(-2\), de vecteurs propres \(\binom10\) et \(\binom01\).
b) \(\operatorname{tr}=10\), \(\det=25-4=21\). \(\chi(\lambda)=\lambda^2-10\lambda+21 = (\lambda-3)(\lambda-7)\).
\(\lambda=3\) : \(\begin{pmatrix}2&2\\2&2\end{pmatrix}\) donne \(y=-x\), vecteur \(\binom{1}{-1}\). \(\lambda=7\) : \(\begin{pmatrix}-2&2\\2&-2\end{pmatrix}\) donne \(y=x\), vecteur \(\binom11\).
Info
La matrice est symétrique, et les deux vecteurs propres sont orthogonaux : \(1\times1 + (-1)\times1 = 0\). Ce n'est pas un hasard, c'est le théorème spectral.
c) \(\operatorname{tr}=3\), \(\det=2-6=-4\). \(\chi(\lambda)=\lambda^2-3\lambda-4 = (\lambda-4)(\lambda+1)\).
\(\lambda=4\) : \(\begin{pmatrix}-3&2\\3&-2\end{pmatrix}\) donne \(3x=2y\), vecteur \(\binom23\). \(\lambda=-1\) : \(\begin{pmatrix}2&2\\3&3\end{pmatrix}\) donne \(y=-x\), vecteur \(\binom{1}{-1}\).
Corrigé — Exercice 2
a) Triangulaire supérieure : valeurs propres \(2\), \(-1\), \(4\).
b) \(\mathbf{I}_5\) : la seule valeur propre est \(1\), de multiplicité algébrique et géométrique 5 (tout vecteur non nul est propre).
c) La matrice nulle : seule valeur propre \(0\), de multiplicité 2.
Corrigé — Exercice 3
a) \(\mathbf{A}^2 = \begin{pmatrix}3&3&3\\3&3&3\\3&3&3\end{pmatrix} = 3\mathbf{A}\).
Relation : \(\mathbf{A}^2-3\mathbf{A}=\mathbf{0}\), soit \(\mathbf{A}(\mathbf{A}-3\mathbf{I})=\mathbf{0}\).
b) Toute valeur propre \(\lambda\) vérifie \(\lambda^2-3\lambda=0\), donc \(\lambda\in\{0,3\}\).
\(\operatorname{tr}\mathbf{A}=3\), et il y a 3 valeurs propres comptées avec multiplicité. Si \(3\) apparaît \(k\) fois, la trace vaut \(3k = 3\), donc \(k=1\).
\(\lambda=3\) de multiplicité 1, \(\lambda=0\) de multiplicité 2.
c) \(E_3\) : \(\mathbf{A}-3\mathbf{I}\) a pour lignes \((-2,1,1)\) répétées. Le système \(-2x+y+z=0\) … en fait les trois lignes sont \((-2,1,1)\), \((1,-2,1)\), \((1,1,-2)\). En résolvant : \(x=y=z\).
\(E_0 = \ker\mathbf{A}\) : le système est \(x+y+z=0\) (les trois lignes identiques).
Les multiplicités géométriques égalent les algébriques : \(\mathbf{A}\) est diagonalisable.
Corrigé — Exercice 4
a) Triangulaire : valeurs propres \(2\) (deux fois sur la diagonale) et \(3\). \(\chi(\lambda) = (2-\lambda)^2(3-\lambda)\), donc \(m_a(2)=2\), \(m_a(3)=1\).
b) \(\mathbf{A}-2\mathbf{I} = \begin{pmatrix}0&1&0\\0&0&0\\0&0&1\end{pmatrix}\). Système : \(y=0\) et \(z=0\), \(x\) libre.
\(\mathbf{A}-3\mathbf{I} = \begin{pmatrix}-1&1&0\\0&-1&0\\0&0&0\end{pmatrix}\). Système : \(y=0\) puis \(x=0\), \(z\) libre.
c) \(m_g(2) = 1 < 2 = m_a(2)\) : \(\mathbf{A}\) n'est pas diagonalisable.
On dispose de \(1+1 = 2\) directions propres indépendantes, alors qu'il en faudrait 3 pour former une base.
Corrigé — Exercice 5
a) Soit \(\lambda\) valeur propre, de vecteur propre \(\mathbf{x}\neq0\).
Donc \((\lambda^2-\lambda)\mathbf{x} = \mathbf{0}\). Comme \(\mathbf{x}\neq\mathbf{0}\), on a \(\lambda^2 = \lambda\), soit \(\lambda\in\{0,1\}\). \(\blacksquare\)
b) \(\mathbf{A} = \begin{pmatrix}1&0\\0&0\end{pmatrix}\) vérifie \(\mathbf{A}^2=\mathbf{A}\), avec valeurs propres 1 et 0.
C'est la projection orthogonale sur l'axe des abscisses : les vecteurs de cet axe sont fixés (\(\lambda=1\)), ceux de l'axe des ordonnées sont écrasés (\(\lambda=0\)).
Corrigé — Exercice 6
Somme des lignes \(= 5\) pour chaque ligne. Donc \(\lambda=5\) est valeur propre, de vecteur propre \(\mathbf{u} = (1,1,1)^\top\).
Autres valeurs propres. Remarquons que \(\mathbf{A} = 2\mathbf{J} - \mathbf{I}\) où \(\mathbf{J}\) est la matrice de 1 partout (celle de l'exercice 3). Les valeurs propres de \(\mathbf J\) sont \(3\) (une fois) et \(0\) (deux fois), donc celles de \(2\mathbf J - \mathbf I\) sont
Vérification : \(\operatorname{tr}\mathbf A = 3\), et \(5-1-1 = 3\) ✓ \(\det\mathbf A = 5\times(-1)\times(-1) = 5\). Vérification par Sarrus : \(1+8+8-4-4-4 = 5\) ✓
Sous-espaces.
\(E_{-1} = \ker(\mathbf A+\mathbf I) = \ker(2\mathbf J) = \ker\mathbf J\), soit l'hyperplan \(x+y+z=0\) :
\(m_g(-1) = 2 = m_a(-1)\) : diagonalisable.
Corrigé — Exercice 7
a) Par récurrence. \(\mathbf{A}^1\mathbf{x} = \lambda\mathbf{x}\) ✓ Si \(\mathbf{A}^k\mathbf{x}=\lambda^k\mathbf{x}\), alors
✓ \(\blacksquare\)
b) Si \(\mathbf{A}\) est inversible, \(\lambda\neq0\) (sinon 0 serait valeur propre). De \(\mathbf{Ax}=\lambda\mathbf{x}\), on applique \(\mathbf{A}^{-1}\) :
✓
c) \(\chi_{\mathbf{A}^\top}(\lambda) = \det(\mathbf{A}^\top-\lambda\mathbf{I}) = \det\big((\mathbf{A}-\lambda\mathbf{I})^\top\big) = \det(\mathbf{A}-\lambda\mathbf{I}) = \chi_{\mathbf{A}}(\lambda)\).
Mêmes polynômes, donc mêmes racines. \(\blacksquare\)
d) Non. Contre-exemple : \(\mathbf{A} = \begin{pmatrix}1&1\\0&2\end{pmatrix}\).
Pour \(\lambda=1\) : \(\mathbf A - \mathbf I = \begin{pmatrix}0&1\\0&1\end{pmatrix}\) donne \(E_1 = \operatorname{Vect}\binom10\).
Pour \(\mathbf{A}^\top = \begin{pmatrix}1&0\\1&2\end{pmatrix}\) et \(\lambda=1\) : \(\begin{pmatrix}0&0\\1&1\end{pmatrix}\) donne \(y=-x\), soit \(\operatorname{Vect}\binom{1}{-1}\).
Vecteurs propres différents pour la même valeur propre.
Info
Les vecteurs propres de \(\mathbf{A}^\top\) s'appellent les vecteurs propres à gauche de \(\mathbf{A}\). Ils coïncident avec ceux de droite si et seulement si \(\mathbf{A}\) est normale — en particulier si elle est symétrique.
Corrigé — Exercice 8
a) Si \(\mathbf{Ax}=\lambda\mathbf{x}\) avec \(\mathbf x\neq0\), alors \(\mathbf{A}^3\mathbf{x}=\lambda^3\mathbf{x}\) et \(\mathbf{A}^3\mathbf{x} = \mathbf{Ax}=\lambda\mathbf{x}\).
Donc \(\lambda^3 = \lambda\), soit \(\lambda(\lambda-1)(\lambda+1)=0\) :
b) Notons \(a\), \(b\), \(c\) les multiplicités de \(-1\), \(0\), \(1\), avec \(a+b+c=3\).
- \(\det\mathbf{A} = (-1)^a\cdot0^b\cdot1^c = 0\) impose \(b\geqslant1\) ;
- \(\operatorname{tr}\mathbf{A} = -a+c = 1\).
Avec \(a+b+c=3\), \(b\geqslant1\) et \(c = a+1\) : \(a + b + a + 1 = 3\), soit \(2a+b = 2\).
- Si \(a=0\) : \(b=2\), \(c=1\). Spectre \(\{0,0,1\}\).
- Si \(a=1\) : \(b=0\), ce qui contredit \(b\geqslant1\).
Spectre : \(0\) de multiplicité 2, \(1\) de multiplicité 1.
Corrigé — Exercice 9
a) \(\operatorname{tr}\mathbf F = 1\), \(\det\mathbf F = -1\).
\(\Delta = 1+4 = 5\), racines
\(\varphi\) est le nombre d'or. Notons que \(\varphi\psi = -1\) et \(\varphi+\psi=1\) ✓
b) Pour \(\lambda\) valeur propre : \(\mathbf{F}-\lambda\mathbf{I} = \begin{pmatrix}1-\lambda&1\\1&-\lambda\end{pmatrix}\).
La seconde ligne donne \(x = \lambda y\). Vecteur propre : \(\binom{\lambda}{1}\).
Donc \(\binom{\varphi}{1}\) et \(\binom{\psi}{1}\).
c) Cherchons \(\alpha,\beta\) à partir des conditions initiales.
- \(F_0 = 0\) : \(\alpha+\beta = 0\), donc \(\beta = -\alpha\) ;
- \(F_1 = 1\) : \(\alpha\varphi + \beta\psi = \alpha(\varphi-\psi) = 1\).
Or \(\varphi-\psi = \sqrt5\), donc \(\alpha = \frac{1}{\sqrt5}\) et \(\beta = -\frac{1}{\sqrt5}\).
Vérification \(n=5\) : \(\varphi^5 \approx 11{,}0902\), \(\psi^5\approx -0{,}0902\), différence \(\approx 11{,}180\), divisée par \(\sqrt5\approx2{,}2361\) donne \(5\) ✓ (et \(F_5 = 5\)).
d) \(|\psi| = \frac{\sqrt5-1}{2} \approx 0{,}618 < 1\), donc
Pour \(n\geqslant0\), cette quantité vaut au plus \(\frac{1}{\sqrt5}\approx 0{,}447 < 0{,}5\). Donc \(F_n\), qui est entier, est bien l'entier le plus proche de \(\frac{\varphi^n}{\sqrt5}\). \(\blacksquare\)
Ce que révèle la diagonalisation
Une suite définie par récurrence linéaire a une formule close, et cette formule est donnée par les valeurs propres de la matrice de récurrence. Le terme dominant \(\varphi^n\) dit que Fibonacci croît exponentiellement à taux \(\varphi\) — ce qu'aucune inspection de la relation \(F_{n+2}=F_{n+1}+F_n\) ne rend évident.
Corrigé — Exercice 10
a) \(\mathbf{M}\) est stochastique (chaque ligne somme à 1, ce sont les probabilités de transition depuis une page). D'après l'exercice 9 du chapitre 08, \(\mathbf{M}\mathbf{u} = \mathbf{u}\) : 1 est valeur propre de \(\mathbf M\).
Or \(\mathbf{M}\) et \(\mathbf{M}^\top\) ont le même polynôme caractéristique (exercice 7c). Donc 1 est aussi valeur propre de \(\mathbf{M}^\top\). \(\blacksquare\)
b) Décomposons \(\mathbf{v}_0\) sur une base de vecteurs propres de \(\mathbf{M}^\top\) :
avec \(\lambda_1 = 1\) et \(|\lambda_i| < 1\) pour \(i\geqslant2\).
Alors
Les termes \(\lambda_i^k\) tendent vers 0 puisque \(|\lambda_i|<1\). Il reste \(c_1\mathbf{w}_1\) : la suite converge vers le vecteur propre associé à 1, à un facteur près. \(\blacksquare\)
c) L'erreur est dominée par \(|\lambda_2|^k \leqslant 0{,}85^k\). On veut \(0{,}85^k \leqslant 10^{-6}\) :
Environ 85 itérations suffisent, quelle que soit la taille du graphe. C'est le chiffre souvent cité pour PageRank — de l'ordre de la centaine d'itérations, pour des milliards de pages.
d) Trois raisons rédhibitoires :
- Le polynôme caractéristique d'une matrice \(n\times n\) est de degré \(n\). Pour \(n = 10^9\), il faudrait manipuler un polynôme de degré un milliard.
- Il n'existe aucune formule par radicaux pour les racines d'un polynôme de degré \(\geqslant5\) — théorème d'Abel-Ruffini. Toute méthode serait de toute façon itérative.
- Le calcul du polynôme caractéristique est numériquement instable : de minuscules perturbations des coefficients déplacent énormément les racines.
En pratique, on ne calcule jamais \(\chi_{\mathbf A}\) pour trouver des valeurs propres, même en petite dimension. On utilise l'algorithme QR, ou — quand une seule valeur propre suffit, comme ici — la méthode de la puissance, qui ne demande que des produits matrice-vecteur. Sur une matrice creuse, chaque itération coûte \(O(\text{nombre de liens})\), ce qui rend PageRank calculable.
Chapitre suivant : Diagonalisation.