Mathématiques universitaires — Licence 2 · Bachelor Year 2

3Réduction des endomorphismes

Pour comprendre un endomorphisme, on cherche les directions qu’il se contente d’étirer. Ce chapitre construit la machinerie — valeurs propres, polynômes caractéristique et minimal, le lemme de décomposition des noyaux — et ses récompenses : critères de diagonalisation et de trigonalisation, Cayley–Hamilton, la décomposition de Dunford, et le calcul des puissances et des exponentielles dont se nourrira le Chapitre 16. Partout, $E$ est un $K$ -espace vectoriel de dimension finie ( $K = \R$ ou $\C$ ) et $u \in \mathcal{L}(E)$ , $n = \dim E$ .

3.1 Valeurs propres et vecteurs propres

Définition 3.1

$\lambda \in K$ est une valeur propre de $u$ lorsque $u(x) = \lambda x$ pour un certain $x \neq 0$ (un vecteur propre) ; le sous-espace propre est $E_\lambda(u) = \ker(u - \lambda\,\mathrm{id})$ . L’ensemble des valeurs propres est le spectre $\operatorname{Sp}(u)$ . Un sous-espace $F$ est stable lorsque $u(F) \subseteq F$ ; les sous-espaces propres sont stables, et les sous-espaces stables permettent de définir des endomorphismes induits $u|_F$ .

Théorème 3.2 (Indépendance des sous-espaces propres)

Des vecteurs propres associés à des valeurs propres deux à deux distinctes forment une famille libre ; de manière équivalente, la somme des sous-espaces propres $E_{\lambda_1} + \dots + E_{\lambda_r}$ ( $\lambda_i$ distincts) est directe. En particulier, $u$ a au plus $n$ valeurs propres.

Démonstration. Par récurrence sur $r$ . Supposons $x_1 + \dots + x_r = 0$ avec $x_i \in E_{\lambda_i}$ , l’énoncé étant connu pour $r - 1$ . On applique $u$ et on soustrait $\lambda_r$ fois la relation :

\sum_{i=1}^{r-1} (\lambda_i - \lambda_r)\, x_i = 0 ,

donc par récurrence chaque $(\lambda_i - \lambda_r)x_i = 0$ , c’est-à-dire $x_i = 0$ pour $i < r$ , puis $x_r = 0$ . Une somme directe d’espaces non nuls dans un espace de dimension $n$ a au plus $n$ termes. ∎

La matrice A = psmallmatrix2 & 1\\ 1 & 2 psmallmatrix agissant sur le plan : le vecteur générique e_1 est dévié de sa droite, mais les directions propres v_1 = (1,1) et v_2 = (1,-1) sont simplement étirées — par 3 et par 1 (donc Av_2 = v_2 : l’image en pointillés coïncide avec v_2). La diagonalisation est le changement vers la base (v_1, v_2), où A devient diag(3, 1). — La matrice $A = \left(\begin{smallmatrix}2 & 1\\ 1 & 2\end{smallmatrix}\right)$ agissant sur le plan : le vecteur générique $e_1$ est dévié de sa droite, mais les directions propres $v_1 = (1,1)$ et $v_2 = (1,-1)$ sont simplement étirées — par $3$ et par $1$ (donc $Av_2 = v_2$ : l’image en pointillés coïncide avec $v_2$ ). La diagonalisation est le changement vers la base $(v_1, v_2)$ , où $A$ devient $\operatorname{diag}(3, 1)$ .

Définition 3.3 (Polynôme caractéristique)

$\chi_u(X) = \det(X\,\mathrm{id} - u)$ — calculé dans n’importe quelle base comme $\det(XI_n - A)$ , un polynôme unitaire de degré $n$ , invariant par similitude (Théorème 2.17). Ses racines dans $K$ sont exactement les valeurs propres ( $\lambda$ valeur propre $\iff u - \lambda\,\mathrm{id}$ non injectif $\iff \chi_u(\lambda) = 0$ ), et

\chi_u(X) = X^n - (\operatorname{tr} u)\, X^{n-1} + \dots + (-1)^n \det u .

La multiplicité algébrique $m_\lambda$ d’une valeur propre est sa multiplicité comme racine de $\chi_u$ ; la multiplicité géométrique est $\dim E_\lambda$ , et $1 \leq \dim E_\lambda \leq m_\lambda$ .

Preuve des faits énoncés. Les affirmations sur les coefficients : on développe $\det(XI - A)$ par la formule des permutations ; la permutation identité contribue $\prod_i (X - a_{ii}) = X^n - (\sum a_{ii})X^{n-1} + \dots$ , et toute autre permutation fixe au plus $n - 2$ positions diagonales, contribuant un degré $\leq n - 2$ : les deux coefficients de tête sont ceux annoncés ; $X = 0$ donne le terme constant $\det(-A) = (-1)^n\det A$ .

Géométrique $\leq$ algébrique : posons $d = \dim E_\lambda$ et complétons une base de $E_\lambda$ en une base de $E$ ; la matrice de $u$ est triangulaire supérieure par blocs, avec bloc en haut à gauche $\lambda I_d$ , donc $\chi_u(X) = (X - \lambda)^d\, \chi_{\text{(bloc inférieur)}}(X)$ : la multiplicité de $\lambda$ est au moins $d$ . ∎

Exemple 3.4 (Même $\chi$ , géométrie différente)

Les matrices

\begin{pmatrix}2 & 0\\ 0 & 2\end{pmatrix} \qquad\text{et}\qquad \begin{pmatrix}2 & 1\\ 0 & 2\end{pmatrix}

partagent le polynôme caractéristique $(X - 2)^2$ , la trace, le déterminant, le spectre — pourtant elles ne sont pas semblables : la première a $E_2$ de dimension $2$ (multiplicité géométrique $2$ ), la seconde de dimension $1$ . Le polynôme caractéristique ne voit que les multiplicités algébriques ; les dimensions des sous-espaces propres sont l’invariant plus fin, et le polynôme minimal tranche ( $X - 2$ contre $(X - 2)^2$ ). Morale pour toute discussion de diagonalisabilité : $\chi$ présélectionne les candidats, mais ce sont les noyaux qui votent.

Définition 3.5 (Diagonalisable, trigonalisable)

$u$ est diagonalisable lorsque $E$ a une base de vecteurs propres (matrice : semblable à une matrice diagonale) ; trigonalisable lorsque sa matrice dans une certaine base est triangulaire supérieure.

Théorème 3.6 (Critères de diagonalisabilité)

Les propriétés suivantes sont équivalentes :

$u$ est diagonalisable ;
$E = \bigoplus_{\lambda \in \operatorname{Sp} u} E_\lambda$ ;
$\chi_u$ est scindé sur $K$ et $\dim E_\lambda = m_\lambda$ pour toute valeur propre ;
(suffisant, non nécessaire) $\chi_u$ a $n$ racines distinctes dans $K$ .

Démonstration. (1 $\iff$ 2) : une base de vecteurs propres se répartit en bases des $E_\lambda$ , et réciproquement, en concaténant des bases des facteurs directs, on obtient une base de $E$ (le Théorème 3.2 rend la somme directe ; l’égalité des dimensions la rend totale).

(2 $\iff$ 3) : dans la base diagonale, $\chi_u = \prod (X - \lambda)^{\dim E_\lambda}$ est scindé avec des multiplicités concordantes. Réciproquement, supposons $\chi_u$ scindé avec $\dim E_\lambda = m_\lambda$ partout ; alors la somme directe des sous-espaces propres (directe par le Théorème 3.2) a pour dimension

\sum_{\lambda}\dim E_\lambda = \sum_{\lambda} m_\lambda = \deg\chi_u = n ,

l’égalité centrale venant de ce que le degré d’un polynôme scindé est la somme des multiplicités de ses racines : la somme est $E$ tout entier. Remarquons où chaque hypothèse a servi : le caractère scindé a rempli le degré, l’égalité des multiplicités a rempli les dimensions.

(4 $\Rightarrow$ 1) : $n$ valeurs propres distinctes donnent $n$ vecteurs propres indépendants (Théorème 3.2) : une base. ∎

Méthode 3.7 (Décider de la diagonalisabilité)

En pratique, on teste dans cet ordre — chaque étape peut conclure. (1) Un polynôme annulateur à racines simples scindées se présente-t-il ( $u^2 = \mathrm{id}$ , $u^2 = u$ , $u^k = \mathrm{id}$ ) ? Si oui : diagonalisable, sans calcul (Corollaire 3.17 ci-dessous). (2) On calcule $\chi_u$ ; s’il a $n$ racines distinctes dans $K$ : diagonalisable (Théorème 3.6 (4)). (3) Sinon, pour chaque racine multiple $\lambda$ uniquement, on compare $\dim\ker(u - \lambda\,\mathrm{id})$ à la multiplicité $m_\lambda$ : tout déficit tue la diagonalisabilité ; l’égalité partout la prouve. Ne jamais calculer les sous-espaces propres des racines simples (leur dimension vaut forcément $1$ ), et ne jamais trigonaliser juste pour décider.

Exemple 3.8 (La diagonalisation mise à l’œuvre)

$A = I + J = \left(\begin{smallmatrix}2 & 1 & 1\\ 1 & 2 & 1\\ 1 & 1 & 2\end{smallmatrix}\right)$ , avec $J$ la matrice remplie de $1$ : de $\operatorname{Sp}(J) = \{3, 0\}$ (Exemple 2.19), on tire $\operatorname{Sp}(A) = \{4, 1\}$ , avec sous-espaces propres $\R(1,1,1)$ et le plan $\{x + y + z = 0\}$ : dimensions $1 + 2 = 3$ , diagonalisable (Théorème 3.6 (2)). Puissances sans aucune matrice de changement de base : avec $\Pi = J/3$ le projecteur sur $\R(1,1,1)$ ,

A = 4\,\Pi + 1\cdot(I - \Pi) \quad\Longrightarrow\quad A^k = 4^k\,\Pi + (I - \Pi) = \frac{4^k - 1}{3}\,J + I .

(Vérification en $k = 1$ : $\frac{4-1}3 J + I = A$ .) L’idée finale : lorsque les sous-espaces propres sont visibles, les projecteurs spectraux calculent les puissances plus vite que $PDP^{-1}$ ne le fera jamais — et la formule affiche la dynamique : $A^k$ croît comme $4^k$ le long de $(1,1,1)$ et reste fixe sur le plan orthogonal.

Théorème 3.9 (Trigonalisation)

$u$ est trigonalisable sur $K$ si et seulement si $\chi_u$ est scindé sur $K$ . En particulier, tout endomorphisme d’un $\C$ -espace vectoriel est trigonalisable.

Démonstration. ( $\Rightarrow$ ) Le polynôme caractéristique d’une matrice triangulaire est $\prod(X - t_{ii})$ : scindé.

( $\Leftarrow$ ) Récurrence sur $n$ . Puisque $\chi_u$ est scindé, il a une racine $\lambda$ : on choisit un vecteur propre $e_1$ . Dans une base commençant par $e_1$ , la matrice est $\begin{pmatrix} \lambda & \ast\\ 0 & B\end{pmatrix}$ , et $\chi_u = (X - \lambda)\chi_B$ : $\chi_B$ est scindé lui aussi. Par l’hypothèse de récurrence appliquée à la matrice $(n-1) \times (n-1)$ $B$ , il existe $Q$ inversible avec $Q^{-1}BQ$ triangulaire supérieure ; en conjuguant la matrice entière par $\begin{pmatrix}1 & 0\\ 0 & Q\end{pmatrix}$ , on la triangularise. ∎

Exemple 3.10 (Trigonaliser à la main)

$B = \begin{pmatrix}3 & -1\\ 1 & 1\end{pmatrix}$ : $\chi_B = X^2 - 4X + 4 = (X - 2)^2$ , et $\ker(B - 2I) = \ker\left(\begin{smallmatrix}1 & -1\\ 1 & -1\end{smallmatrix}\right)$ est la droite engendrée par $e_1' = (1, 1)$ : une seule valeur propre, un sous-espace propre de dimension $1$ — non diagonalisable, mais trigonalisable (Théorème 3.9). On complète la base avec $e_2' = (1, 0)$ et on calcule :

u(e_1') = (2, 2) = 2e_1', \qquad u(e_2') = (3, 1) = 1\cdot e_1' + 2\, e_2' ,

donc dans la base $(e_1', e_2')$ la matrice est $T = \left(\begin{smallmatrix}2 & 1\\ 0 & 2\end{smallmatrix}\right)$ . L’idée finale : la diagonale de $T$ était forcée (les deux entrées doivent être la valeur propre double $2$ ) ; seule l’entrée du coin dépendait du choix de $e_2'$ , et remettre $e_2'$ à l’échelle peut lui donner n’importe quelle valeur non nulle — le « $1$ » récalcitrant est l’ombre de la partie nilpotente que Dunford isolera.

3.2 Polynômes d’un endomorphisme

Définition 3.11

Pour $P = \sum a_k X^k \in K[X]$ , on pose $P(u) = \sum a_k u^k \in \mathcal{L}(E)$ . L’application $P \mapsto P(u)$ est un morphisme d’algèbres $K[X] \to \mathcal{L}(E)$ (Définition 1.33) ; son noyau $\{P : P(u) = 0\}$ est un idéal de $K[X]$ , non nul (la famille $(\mathrm{id}, u, \dots, u^{n^2})$ est liée dans $\mathcal{L}(E)$ , de dimension $n^2$ ), donc engendré par un unique polynôme unitaire $\mu_u$ : le polynôme minimal (Théorème 1.26).

Proposition 3.12

$P(u) = 0 \iff \mu_u \mid P$ ; les valeurs propres de $u$ sont racines de tout polynôme annulateur, et les racines de $\mu_u$ sont exactement les valeurs propres.
Si $F$ est stable, $\mu_{u|_F} \mid \mu_u$ .

Démonstration. (1) La divisibilité est la définition d’un générateur. Si $u(x) = \lambda x$ , $x \neq 0$ , alors $0 = P(u)(x) = P(\lambda)x$ , donc $P(\lambda) = 0$ : les valeurs propres sont racines des annulateurs, en particulier de $\mu_u$ . Réciproquement, si $\lambda$ est une racine, $\mu_u = (X - \lambda)Q$ avec $Q(u) \neq 0$ (degré de $\mu_u$ minimal) : on choisit $y$ avec $Q(u)(y) \neq 0$ ; alors $(u - \lambda)(Q(u)(y)) = \mu_u(u)(y) = 0$ exhibe le vecteur propre $Q(u)(y)$ .

(2) $\mu_u(u|_F) = \mu_u(u)|_F = 0$ , et on applique (1) à $u|_F$ . ∎

Exemple 3.13 (Polynômes minimaux trouvés à la main)

Le polynôme minimal se calcule en testant les degrés successifs. Pour la matrice remplie de $1$ $J \in \mathcal{M}_3(\R)$ : $J \neq \lambda I$ (le degré $1$ est exclu), et $J^2 = 3J$ , donc

\mu_J = X^2 - 3X = X(X - 3) :

degré $2$ , scindé, racines simples — $J$ est diagonalisable de spectre $\{0, 3\}$ (Corollaire 3.17 ci-dessous), ce qui confirme l’Exemple 2.19 sans un seul déterminant. Pour la matrice d’échange $A$ de l’Exemple 3.15 : $A \neq \pm I$ et $A^2 = I$ donnent $\mu_A = X^2 - 1$ . Dans les deux cas le schéma est le même : on devine une identité de bas degré à partir de la structure (le rang un force $J^2 = (\operatorname{tr}J)\,J$ ; une involution force $A^2 = I$ ), puis on vérifie qu’aucun diviseur propre n’annule. Les polynômes minimaux sont d’ordinaire trouvés, non calculés à partir de $\chi$ .

Théorème 3.14 (Lemme de décomposition des noyaux)

Si $P = P_1 P_2 \cdots P_r$ avec les $P_i$ deux à deux premiers entre eux, alors

\ker P(u) = \ker P_1(u) \oplus \dots \oplus \ker P_r(u),

et les projections sur les facteurs sont des polynômes en $u$ .

Démonstration. Il suffit de traiter $r = 2$ et de récurrer. Bézout dans $K[X]$ (Théorème 1.26) : $U P_1 + V P_2 = 1$ , donc pour tout $x$ ,

x = \underbrace{U(u)P_1(u)(x)}_{=:\,x_2} + \underbrace{V(u)P_2(u)(x)}_{=:\,x_1}.

Si $x \in \ker P(u)$ : $P_2(u)(x_2) = U(u)\,P(u)(x) = 0$ (les polynômes en $u$ commutent), donc $x_2 \in \ker P_2(u)$ , et symétriquement $x_1 \in \ker P_1(u)$ : la somme remplit $\ker P(u)$ ; les deux facteurs sont contenus dans $\ker P(u)$ ( $P_i \mid P$ ). Caractère direct : $x \in \ker P_1(u) \cap \ker P_2(u)$ donne $x = U(u)P_1(u)x + V(u)P_2(u)x = 0$ . Les formules pour $x_1, x_2$ exhibent les projections comme $V(u)P_2(u)$ et $U(u)P_1(u)$ . ∎

Exemple 3.15 (Le lemme des noyaux avec projecteurs explicites)

Soit $A = \left(\begin{smallmatrix}0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\end{smallmatrix}\right)$ (échange des deux premières coordonnées). Alors $A^2 = I$ : le polynôme $X^2 - 1 = (X - 1)(X + 1)$ annule $A$ , ses facteurs sont premiers entre eux, et Bézout est explicite :

\frac{1}{2}(X + 1) - \frac12(X - 1) = 1 .

En suivant la preuve du Théorème 3.14, les projections sur $\ker(A - I)$ et $\ker(A + I)$ sont les polynômes en $A$

\pi_+ = \frac{A + I}{2} = \frac12\begin{pmatrix} 1 & 1 & 0\\ 1 & 1 & 0\\ 0 & 0 & 2\end{pmatrix}, \qquad \pi_- = \frac{I - A}{2} = \frac12\begin{pmatrix} 1 & -1 & 0\\ -1 & 1 & 0\\ 0 & 0 & 0\end{pmatrix}.

Vérification : $\pi_+ + \pi_- = I$ , $\pi_+\pi_- = 0$ , $\pi_\pm^2 = \pi_\pm$ , et les images sont le plan $\{x = y\}$ (vecteurs symétriques, valeur propre $1$ ) et la droite $\R(1, -1, 0)$ (antisymétriques, valeur propre $-1$ ). Le lemme des noyaux n’est pas un énoncé d’existence : les coefficients de Bézout sont les formules des projecteurs.

Exemple 3.16 (Les projecteurs calculent aussi l’exponentielle)

La même matrice d’échange, un cran plus loin. Puisque $A = \pi_+ - \pi_-$ avec des projecteurs orthogonaux au sens algébrique ( $\pi_+\pi_- = 0$ ), toute puissance obéit à $A^k = \pi_+ + (-1)^k\pi_-$ , et la série exponentielle se regroupe par projecteur :

\eu^{tA} = \sum_k \frac{t^k}{k!}\bigl(\pi_+ + (-1)^k\pi_-\bigr) = \eu^{t}\,\pi_+ + \eu^{-t}\,\pi_- = \begin{pmatrix} \cosh t & \sinh t & 0\\ \sinh t & \cosh t & 0\\ 0 & 0 & \eu^{t} \end{pmatrix}.

(Vérification en $t = 0$ : l’identité ; dérivée en $0$ : $A$ .) La décomposition propre convertit une série de matrices en deux séries scalaires — le mécanisme exact sur lequel tournera le Chapitre 16 pour tout système diagonalisable, et la raison pour laquelle les fonctions hyperboliques gouvernent les couplages symétriques.

Corollaire 3.17 (Diagonalisabilité via le polynôme minimal)

$u$ est diagonalisable $\iff$ $\mu_u$ est scindé sur $K$ à racines simples $\iff$ un polynôme annulateur de $u$ est scindé à racines simples.

Démonstration. Si $P(u) = 0$ avec $P = \prod_{i}(X - \lambda_i)$ ( $\lambda_i$ distincts), le lemme donne $E = \ker P(u) = \bigoplus_i \ker(u - \lambda_i)$ : une somme directe de sous-espaces propres, donc $u$ est diagonalisable (Théorème 3.6). Réciproquement, un $u$ diagonalisable est annulé par $\prod_{\lambda \in \operatorname{Sp}u}(X - \lambda)$ (qui annule chaque sous-espace propre), lequel est scindé à racines simples ; et $\mu_u$ le divise tout en ayant les mêmes racines (Proposition 3.12) : $\mu_u$ est exactement ce produit. ∎

Exemple 3.18

Les projections vérifient $p^2 = p$ : annulées par $X(X-1)$ , scindé à racines simples — diagonalisables de spectre $\subseteq \{0, 1\}$ , et $E = \ker p \oplus \ker(p - \mathrm{id})$ : l’analyse géométrique de l’année 1, reprouvée en une ligne. Les symétries ( $s^2 = \mathrm{id}$ , annulateur $X^2 - 1$ ) : diagonalisables lorsque $\operatorname{char} K \neq 2$ , de spectre $\subseteq \{\pm 1\}$ . Un endomorphisme avec $u^3 = u^2$ et $u^2 \neq u$ : annulé par $X^2(X - 1)$ , pas nécessairement diagonalisable — le critère le détecte (la racine double $0$ doit être testée : diagonalisable si et seulement si de plus $\ker u^2 = \ker u$ ).

Exemple 3.19 (Le corps décide : une rotation dans $\R^3$ )

Soit $R$ le quart de tour autour de l’axe des $z$ :

R = \begin{pmatrix} 0 & -1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix}, \qquad \chi_R = (X - 1)(X^2 + 1).

Sur $\R$ : la seule valeur propre est $1$ , de sous-espace propre l’axe $\R e_3$ — une droite de vecteurs fixes, et aucune réduction supplémentaire : $R$ n’est ni diagonalisable ni trigonalisable dans $\mathcal{M}_3(\R)$ ( $\chi_R$ n’est pas scindé). Sur $\C$ : trois valeurs propres distinctes $1, \iu, -\iu$ , donc $R$ est diagonalisable, de vecteurs propres $e_3$ et $e_1 \mp \iu e_2$ . La géométrie était audible dans l’algèbre : les rotations du plan n’ont aucune direction invariante réelle, et les valeurs propres complexes $\pm\iu$ de module $1$ stockent l’angle ( $\pm\frac\pi2$ ) que la matrice réelle ne peut exprimer qu’en mélangeant les coordonnées.

Exemple 3.20 (Minimal contre caractéristique)

Pour $D = \operatorname{diag}(2, 2, 3)$ : $\chi_D = (X - 2)^2(X - 3)$ mais $\mu_D = (X - 2)(X - 3)$ , puisque $(D - 2I)(D - 3I) = 0$ (vérifier sur la base canonique) tandis qu’aucun facteur seul n’annule $D$ . Pour le bloc de décalage $N = \left(\begin{smallmatrix}0 & 1\\ 0 & 0\end{smallmatrix}\right) \oplus (3)$ , c’est-à-dire $N' = \left(\begin{smallmatrix}0 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 3\end{smallmatrix}\right)$ : $\chi_{N'} = X^2(X - 3)$ et $\mu_{N'} = X^2(X - 3)$ — la racine double est véritablement nécessaire parce que $N'$ n’est pas diagonalisable du côté du noyau ( $N'e_2 = e_1 \neq 0$ ). Règle empirique : $\mu$ et $\chi$ partagent leurs racines (Proposition 3.12) ; la multiplicité dans $\mu$ mesure la taille du plus grand bloc nilpotent, celle dans $\chi$ la dimension totale du sous-espace caractéristique.

Théorème 3.21 (Cayley–Hamilton)

$\chi_u(u) = 0$ ; par conséquent $\mu_u \mid \chi_u$ , et $\deg \mu_u \leq n$ .

Démonstration. Fixons $x \neq 0$ et soit $d$ maximal tel que $(x, u(x), \dots, u^{d-1}(x))$ soit libre ; écrivons

u^d(x) = -a_0 x - a_1 u(x) - \dots - a_{d-1}u^{d-1}(x),

et posons $P_x = X^d + a_{d-1}X^{d-1} + \dots + a_0$ , de sorte que $P_x(u)(x) = 0$ . Complétons la famille libre en une base de $E$ : dans celle-ci, $u$ a la forme par blocs $\begin{pmatrix} C & \ast\\ 0 & D\end{pmatrix}$ où $C$ est la matrice compagnon de $P_x$ , dont le polynôme caractéristique est $P_x$ (développer $\det(XI - C)$ selon la première colonne, par récurrence sur $d$ ). Donc $\chi_u = P_x \cdot \chi_D$ , et

\chi_u(u)(x) = \chi_D(u)\bigl(P_x(u)(x)\bigr) = 0 .

L’argument vaut pour tout $x$ : $\chi_u(u) = 0$ . ∎

Exemple 3.22 (Cayley–Hamilton à l’œuvre)

$A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ : $\chi_A = X^2 - 5X - 2$ , donc $A^2 = 5A + 2I$ . Toute puissance de $A$ se réduit à une combinaison de $I$ et $A$ :

A^4 = (5A + 2I)^2 = 25A^2 + 20A + 4I = 145A + 54I = \begin{pmatrix} 199 & 290\\ 435 & 634\end{pmatrix},

et l’inverse vient gratuitement : $A(A - 5I) = 2I$ donne

A^{-1} = \tfrac12(A - 5I) = \begin{pmatrix} -2 & 1\\ 3/2 & -1/2\end{pmatrix}.

L’idée finale : Cayley–Hamilton comprime toute l’algèbre $K[A]$ en $\operatorname{Vect}(I, A, \dots, A^{n-1})$ — $\dim K[A] = \deg\mu_A \leq n$ , si grandes que soient les puissances dont on a besoin.

Remarque 3.23 (Pièges courants)

(i) Les valeurs propres ne s’additionnent pas : $\operatorname{Sp}(A + B)$ n’est pas $\operatorname{Sp}A + \operatorname{Sp}B$ , et une somme de matrices diagonalisables n’est pas nécessairement diagonalisable — $\left(\begin{smallmatrix}1 & 1\\ 0 & 0\end{smallmatrix}\right) + \left(\begin{smallmatrix}0 & 0\\ 0 & 1\end{smallmatrix}\right) = \left(\begin{smallmatrix}1 & 1\\ 0 & 1\end{smallmatrix}\right)$ est une somme de deux matrices diagonalisables (chacune a des valeurs propres distinctes) et n’est pas diagonalisable ; seules les familles qui commutent se comportent bien (Exercice 3.9). (ii) « $\chi_u$ est scindé » est une hypothèse sur le corps : une rotation du plan a $\chi = X^2 - 2\cos\theta\,X + 1$ , scindé sur $\C$ , pas sur $\R$ — diagonalisable dans $\mathcal{M}_2(\C)$ , non trigonalisable dans $\mathcal{M}_2(\R)$ . (iii) L’inégalité va de géométrique $\leq$ algébrique, jamais dans l’autre sens ; tester seulement $\dim E_\lambda \geq 1$ ne prouve rien sur la diagonalisabilité. (iv) $\mu_u$ n’est pas $\chi_u$ : l’égalité a lieu exactement lorsque chaque valeur propre a une seule chaîne de blocs (par exemple les matrices compagnons, le problème du week-end de ce chapitre) ; employer $\chi$ là où $\mu$ est requis gonfle tout calcul de puissance. (v) Le $d$ et le $\nu$ de Dunford sont des polynômes en $u$ — une décomposition $u = d' + \nu'$ ayant les bonnes propriétés mais avec $d'\nu' \neq \nu'd'$ n’est pas celle de Dunford et n’est jamais unique.

Remarque 3.24 (Où ce chapitre est utilisé)

La réduction est la bête de somme du reste du livre : les puissances et exponentielles de matrices animent les systèmes différentiels linéaires du Chapitre 16 ; le théorème spectral du Chapitre 12 est la diagonalisation rendue orthogonale ; les fonctions génératrices (Chapitre 23) redérivent analytiquement les asymptotiques de récurrence du problème du week-end de ce chapitre. Dans le volume de l’année 3, le même programme se déroule en dimension infinie : la théorie spectrale des opérateurs compacts autoadjoints, où des suites de valeurs propres remplacent les spectres finis, et la théorie de Perron–Frobenius des matrices positives, qui explique pourquoi les valeurs propres dominantes des problèmes de comptage sont positives et simples.

3.3 Nilpotents et décomposition de Dunford

Proposition 3.25 (Endomorphismes nilpotents)

Pour $u$ avec $\chi_u$ scindé, les propriétés suivantes sont équivalentes : $u^n = 0$ ; $u^k = 0$ pour un certain $k$ ; $\operatorname{Sp}(u) = \{0\}$ ; $\chi_u = X^n$ ; $u$ est trigonalisable à diagonale nulle. Un endomorphisme nilpotent a $\mu_u = X^{\text{(indice de nilpotence)}}$ , et un indice $\leq n$ .

Démonstration. $u^k = 0$ fait de toute valeur propre une racine de $X^k$ : spectre $\{0\}$ (non vide lorsque $\chi$ est scindé — sur $\C$ toujours). Alors $\chi_u = X^n$ (toutes racines nulles) et Cayley–Hamilton donne $u^n = 0$ ; la trigonalisation (Théorème 3.9) place des zéros sur la diagonale (la diagonale porte les valeurs propres). Réciproquement, soit $A$ strictement triangulaire supérieure : $a_{ij} = 0$ pour $j \leq i$ . On montre par récurrence que

(A^k)_{ij} = 0 \qquad \text{dès que } j \leq i + k - 1,

c’est-à-dire que chaque puissance repousse la région nulle d’une diagonale vers le haut. Pour $k = 1$ c’est l’hypothèse. Pour l’étape,

(A^{k+1})_{ij} = \sum_{\ell} (A^k)_{i\ell}\,a_{\ell j} ,

et chaque terme s’annule : soit $\ell \leq i + k - 1$ (le premier facteur est $0$ par récurrence), soit $\ell \geq i + k$ , auquel cas $j \leq i + k \leq \ell$ tue le second facteur. En $k = n$ la condition $j \leq i + n - 1$ vaut pour tous $i, j \leq n$ : $A^n = 0$ . Le polynôme minimal divise $X^n$ et l’annulation définit l’indice. ∎

Théorème 3.26 (Décomposition de Dunford)

Supposons $\chi_u$ scindé sur $K$ (automatique pour $K = \C$ ). Alors il existe un unique couple $(d, \nu)$ avec

u = d + \nu, \qquad d \text{ diagonalisable}, \quad \nu \text{ nilpotent}, \quad d\nu = \nu d ,

et de plus $d$ et $\nu$ sont des polynômes en $u$ .

Démonstration. Existence. Écrivons $\chi_u = \prod_{i=1}^{r} (X - \lambda_i)^{m_i}$ ( $\lambda_i$ distincts) et posons $N_i = \ker(u - \lambda_i)^{m_i}$ , les sous-espaces caractéristiques. Par Cayley–Hamilton et le lemme des noyaux (Théorème 3.14),

E = N_1 \oplus \dots \oplus N_r ,

avec des projections $\pi_i$ polynomiales en $u$ ; chaque $N_i$ est stable (les polynômes en $u$ commutent avec $u$ ). Définissons $d = \sum_i \lambda_i \pi_i$ : un polynôme en $u$ , diagonalisable (il agit comme $\lambda_i$ sur $N_i$ , donc $E$ se décompose en ses sous-espaces propres). Alors $\nu = u - d$ est un polynôme en $u$ (donc commute avec $d$ ), et sur chaque $N_i$ il agit comme $u - \lambda_i$ , avec $(u - \lambda_i)^{m_i} = 0$ là : $\nu^{\max m_i} = 0$ sur chaque facteur, donc $\nu$ est nilpotent.

Unicité. Soit $u = d' + \nu'$ un autre tel couple. Puisque $d'$ et $\nu'$ commutent l’un avec l’autre, ils commutent avec $u = d' + \nu'$ , donc avec tout polynôme en $u$ — en particulier avec $d$ et $\nu$ . Alors $d - d'$ est diagonalisable (deux applications diagonalisables qui commutent sont simultanément diagonalisables : Exercice 3.9) et égale $\nu' - \nu$ , qui est nilpotente : si $\nu^k = 0$ et $\nu'^{k'} = 0$ , la commutation autorise le développement du binôme

(\nu' - \nu)^{k + k' - 1} = \sum_{j=0}^{k+k'-1}\binom{k + k' - 1}{j} \,\nu'^{\,j}\,(-\nu)^{k + k' - 1 - j} ,

dans lequel chaque terme meurt : soit $j \geq k'$ (premier facteur nul), soit $k + k' - 1 - j \geq k$ (second facteur nul), et l’un des deux vaut toujours. Une nilpotente diagonalisable est nulle (son spectre est $\{0\}$ et elle est diagonale dans une certaine base) : $d = d'$ , $\nu = \nu'$ . ∎

Exemple 3.27 (Puissances et exponentielles)

$A = \begin{pmatrix} 3 & 1\\ -1 & 1\end{pmatrix}$ : $\chi_A = X^2 - 4X + 4 = (X-2)^2$ , valeur propre unique $2$ , sous-espace propre de dimension $1$ : non diagonalisable. Dunford : $D = 2I$ , $N = A - 2I = \begin{pmatrix} 1 & 1\\ -1 & -1\end{pmatrix}$ , $N^2 = 0$ . Alors

A^k = (2I + N)^k = 2^k I + k\,2^{k-1} N , \qquad \eu^{tA} = \eu^{2t}(I + tN),

par le binôme (termes qui commutent), resp. par la série exponentielle (Chapitre 16) scindée sur des facteurs qui commutent. La réduction transforme la dynamique matricielle en dynamique scalaire.

Remarque 3.28 (Perspectives au sein de ce volume)

La réduction est un carrefour ; voici les quatre voies à surveiller. Au Chapitre 5, des normes adaptées transforment « toutes les valeurs propres de module $< 1$ » en « une certaine norme d’opérateur $< 1$ », faisant gouverner par les spectres la convergence des puissances et des séries. Au Chapitre 16, la recette de l’Exemple 3.27 devient la solution générale de $X' = AX$ : Dunford scinde $\eu^{tA}$ en blocs polynôme-fois-exponentielle, et la stabilité se lit sur les parties réelles des valeurs propres. Au Chapitre 12, un produit scalaire force ce que la seule algèbre linéaire ne peut : les matrices symétriques deviennent orthogonalement diagonalisables, sans aucune partie nilpotente. Et au Chapitre 23, les asymptotiques en valeur propre dominante du problème du week-end de ce chapitre réapparaissent analytiquement, comme la plus petite singularité d’une fonction génératrice — deux langages pour un même taux de croissance.

3.4 Exercices

Exercice 3.1 ★

Diagonaliser (valeurs propres, bases des sous-espaces propres, $P$ inversible) :

A = \begin{pmatrix} 1 & 2\\ 2 & 1 \end{pmatrix}, \qquad B = \begin{pmatrix} 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0 \end{pmatrix}.

Solution

Solution de Exercice 3.1.

$A$ : $\chi_A = X^2 - 2X - 3 = (X - 3)(X + 1)$ . Vecteurs propres : pour $3$ : $(1,1)$ ; pour $-1$ : $(1,-1)$ . Donc $P = \begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ donne $P^{-1}AP = \operatorname{diag}(3, -1)$ .

$B = J - I$ où $J$ est la matrice remplie de $1$ . $J$ est de rang $1$ avec $Jv = 3v$ pour $v = (1,1,1)$ et $Jw = 0$ sur le plan $x + y + z = 0$ : le spectre de $B$ est $\{2, -1\}$ avec sous-espaces propres $\operatorname{Vect}(1,1,1)$ (dimension $1$ ) et $\{x + y + z = 0\}$ (dimension $2$ , base $(1,-1,0), (1,0,-1)$ ). $P$ ayant ces trois colonnes donne $P^{-1}BP = \operatorname{diag}(2, -1, -1)$ .

Exercice 3.2 ★

Montrer que $C = \begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix}$ n’est pas diagonalisable, de deux manières : par les sous-espaces propres, et par le polynôme minimal.

Solution

Solution de Exercice 3.2.

Sous-espaces propres : $\chi_C = (X-1)^2$ , valeur propre unique $1$ ; $\ker(C - I) = \ker\begin{pmatrix} 0&1\\ 0&0\end{pmatrix}$ est la droite $\operatorname{Vect}(e_1)$ : dimension $1 < 2 = m_1$ , donc non diagonalisable (Théorème 3.6).

Polynôme minimal : $\mu_C$ divise $(X-1)^2$ et $C \neq I$ , donc $\mu_C = (X-1)^2$ : une racine double, donc non diagonalisable (Corollaire 3.17).

Exercice 3.3 ★

Soit $u$ vérifiant $u^2 - 5u + 6\,\mathrm{id} = 0$ . Prouver que $u$ est diagonalisable, déterminer les spectres possibles, et calculer $u^k$ comme combinaison de $\mathrm{id}$ et $u$ .

Solution

Solution de Exercice 3.3.

$X^2 - 5X + 6 = (X-2)(X-3)$ : scindé à racines simples, donc $u$ est diagonalisable (Corollaire 3.17), avec $\operatorname{Sp}(u) \subseteq \{2, 3\}$ . Spectres possibles : $\{2\}$ ( $u = 2\,\mathrm{id}$ ), $\{3\}$ ( $u = 3\,\mathrm{id}$ ), ou $\{2, 3\}$ .

Puissances : on cherche $u^k = a_k\,\mathrm{id} + b_k\,u$ . Sur les sous-espaces propres, cela s’écrit $2^k = a_k + 2b_k$ et $3^k = a_k + 3b_k$ : en résolvant, $b_k = 3^k - 2^k$ , $a_k = 3\cdot2^k - 2\cdot 3^k$ :

u^k = (3\cdot 2^k - 2\cdot 3^k)\,\mathrm{id} + (3^k - 2^k)\, u .

(Valable pour les trois spectres : les identités valent valeur propre par valeur propre.)

Exercice 3.4 ★★

Soit $u$ diagonalisable et $F$ un sous-espace stable. Prouver que $u|_F$ est diagonalisable (restreindre un polynôme annulateur à racines simples scindées).

Solution

Solution de Exercice 3.4.

$u$ diagonalisable : $P = \prod_{\lambda}(X - \lambda)$ sur le spectre annule $u$ , est scindé, à racines simples. Alors $P(u|_F) = P(u)|_F = 0$ : la restriction est annulée par un polynôme scindé à racines simples, donc diagonalisable (Corollaire 3.17).

Exercice 3.5 ★★

(Fibonacci) Soit $A = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ . Diagonaliser $A$ sur $\R$ , et en déduire la formule de Binet pour la suite de Fibonacci ( $F_0 = 0$ , $F_1 = 1$ , $F_{n+1} = F_n + F_{n-1}$ ) :

F_n = \frac{\varphi^n - \psi^n}{\sqrt 5}, \qquad \varphi = \frac{1 + \sqrt5}{2},\ \psi = \frac{1 - \sqrt5}{2}.

Solution

Solution de Exercice 3.5.

$\chi_A = X^2 - X - 1$ , racines $\varphi$ et $\psi$ (distinctes) : diagonalisable, de vecteurs propres $(\varphi, 1)$ et $(\psi, 1)$ . La récurrence donne $\begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix} = A^n \begin{pmatrix}1\\ 0\end{pmatrix}$ . Décomposons $(1, 0)$ sur les vecteurs propres : $(1,0) = \frac{1}{\varphi - \psi}\bigl((\varphi, 1) - (\psi, 1)\bigr)$ avec $\varphi - \psi = \sqrt5$ . Appliquer $A^n$ multiplie chaque composante propre par la puissance $n$ -ième de sa valeur propre ; en lisant la seconde coordonnée :

F_n = \frac{\varphi^n - \psi^n}{\sqrt 5} .

(Vérification : $n = 1$ donne $\frac{\varphi - \psi}{\sqrt5} = 1$ .)

Exercice 3.6 ★★

Soit $u \in \mathcal{L}(E)$ avec $u^2$ diagonalisable et $u$ inversible ( $K = \C$ ). Prouver que $u$ est diagonalisable. Donner un contre-exemple lorsque $u$ n’est pas inversible.

Solution

Solution de Exercice 3.6.

Soit $P = \prod_i (X - \mu_i)$ annulant $u^2$ , scindé à racines simples $\mu_i$ (le spectre de $u^2$ ). Puisque $u$ est inversible, $0$ n’est pas valeur propre de $u^2$ ( $\det u^2 = (\det u)^2 \neq 0$ ), donc tous les $\mu_i \neq 0$ . Alors

Q(X) = \prod_i (X^2 - \mu_i) = \prod_i (X - \sqrt{\mu_i})(X + \sqrt{\mu_i})

annule $u$ : $\;Q(u) = \prod_i (u^2 - \mu_i\,\mathrm{id}) = P(u^2) = 0$ . Ses racines $\pm \sqrt{\mu_i}$ (racines carrées complexes) sont deux à deux distinctes car les $\mu_i$ sont distincts et non nuls ( $\sqrt{\mu_i} = -\sqrt{\mu_j}$ donnerait $\mu_i = \mu_j$ ). Scindé + racines simples : $u$ est diagonalisable.

Contre-exemple sans inversibilité : $u = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : $u^2 = 0$ est diagonalisable, $u$ ne l’est pas.

Exercice 3.7 ★★

Calculer la décomposition de Dunford, $A^k$ , et $\eu^{tA}$ pour

A = \begin{pmatrix} 2 & 1 & 0\\ 0 & 2 & 1\\ 0 & 0 & 2 \end{pmatrix}.

Solution

Solution de Exercice 3.7.

$A = 2I + N$ avec $N$ le décalage ( $N e_2 = e_1$ , $Ne_3 = e_2$ ), $N^3 = 0$ , $N^2 = E_{13}$ : c’est la décomposition de Dunford ( $2I$ diagonale, $N$ nilpotente, elles commutent ; l’unicité en fait la bonne). Binôme à termes qui commutent :

A^k = 2^k I + k 2^{k-1} N + \binom k2 2^{k-2} N^2 = \begin{pmatrix} 2^k & k2^{k-1} & \binom k2 2^{k-2}\\ 0 & 2^k & k2^{k-1}\\ 0 & 0 & 2^k \end{pmatrix},

\eu^{tA} = \eu^{2t}\Bigl(I + tN + \frac{t^2}{2}N^2\Bigr) = \eu^{2t}\begin{pmatrix} 1 & t & t^2/2\\ 0 & 1 & t\\ 0 & 0 & 1 \end{pmatrix}.

Exercice 3.8 ★★

Soit $A \in \mathcal{M}_n(\C)$ avec $A^k = I$ pour un certain $k \geq 1$ . Prouver que $A$ est diagonalisable et que ses valeurs propres sont des racines $k$ -ièmes de l’unité. En déduire qu’une matrice complexe inversible d’ordre fini, semblable à une matrice triangulaire à diagonale unité, est l’identité.

Solution

Solution de Exercice 3.8.

$X^k - 1$ annule $A$ et est scindé sur $\C$ avec les $k$ racines distinctes $\eu^{2\iu\pi j/k}$ : $A$ est diagonalisable (Corollaire 3.17) et ses valeurs propres, racines de $X^k - 1$ , sont des racines $k$ -ièmes de l’unité.

Si de plus $A$ est semblable à une matrice triangulaire à diagonale unité : toutes les valeurs propres valent $1$ , et $A$ , diagonalisable de seule valeur propre $1$ , vaut $P\,I\,P^{-1} = I$ .

Exercice 3.9 ★★★

(Diagonalisation simultanée) Soit $u, v$ diagonalisables et qui commutent. Prouver qu’ils sont simultanément diagonalisables : une certaine base diagonalise les deux. (Chaque sous-espace propre de $u$ est $v$ -stable ; diagonaliser les restrictions de $v$ à ces sous-espaces, en utilisant l’Exercice 3.4.)

Solution

Solution de Exercice 3.9.

Écrivons $E = \bigoplus_\lambda E_\lambda(u)$ (Théorème 3.6). Chaque $E_\lambda(u)$ est $v$ -stable : pour $x \in E_\lambda$ , $u(v(x)) = v(u(x)) = \lambda v(x)$ . La restriction de $v$ à $E_\lambda(u)$ est diagonalisable (Exercice 3.4) : on choisit une base de $E_\lambda(u)$ faite de vecteurs propres de $v$ . En concaténant ces bases sur tous les $\lambda$ , on obtient une base de $E$ dont les vecteurs sont vecteurs propres à la fois de $u$ (par appartenance à $E_\lambda(u)$ ) et de $v$ (par construction).

Exercice 3.10 ★★★

Soit $u \in \mathcal{L}(\C^n)$ . Prouver que $u$ est diagonalisable si et seulement si tout sous-espace $u$ -stable admet un supplémentaire $u$ -stable. (Pour $\Leftarrow$ : appliquer la propriété à $F = \sum_\lambda E_\lambda(u)$ , la somme de tous les sous-espaces propres ; si un supplémentaire stable $G$ était non nul, trigonaliser $u|_G$ produirait un vecteur propre de $u$ à l’intérieur de $G$ — contredisant $G \cap F = \{0\}$ .)

Solution

Solution de Exercice 3.10.

( $\Rightarrow$ ) Soit $u$ diagonalisable et $F$ stable. Alors $u|_F$ est diagonalisable (Exercice 3.4) : $F$ a une base de vecteurs propres, qui se prolonge, à l’intérieur de chaque sous-espace propre global $E_\lambda$ , en une base de $E_\lambda$ (théorème de la base incomplète dans $E_\lambda$ , en partant de la partie de la base de $F$ qui s’y trouve — noter $F = \bigoplus_\lambda (F \cap E_\lambda)$ puisque $u|_F$ est diagonalisable). Les vecteurs ajoutés engendrent un supplémentaire stable (chacun est dans un certain $E_\lambda$ , donc leur engendré est $u$ -stable).

( $\Leftarrow$ ) Soit $F = \sum_\lambda E_\lambda(u)$ (un sous-espace stable) et $G$ un supplémentaire stable. Si $G \neq \{0\}$ : $\chi_{u|_G}$ est scindé sur $\C$ , donc $u|_G$ a un vecteur propre $x \in G$ (Théorème 3.9 ou directement l’existence d’une racine) ; mais tout vecteur propre de $u$ est dans $F$ , donc $x \in F \cap G = \{0\}$ : contradiction. Ainsi $G = \{0\}$ et $E = F$ : les sous-espaces propres remplissent $E$ , c’est-à-dire $u$ est diagonalisable.

Exercice 3.11 ★★★

(Rayon spectral à la Gelfand allégé, aperçu $2\times2$ de l’analyse à venir) Soit $A \in \mathcal{M}_2(\C)$ dont les deux valeurs propres sont de module $< 1$ . Prouver que $A^k \to 0$ coefficient par coefficient quand $k \to \infty$ . (Trigonaliser : $A = P(T)P^{-1}$ avec $T$ triangulaire supérieure ; calculer $T^k$ explicitement — distinguer valeurs propres égales et distinctes — et majorer.)

Solution

Solution de Exercice 3.11.

Trigonaliser : $A = PTP^{-1}$ , $T = \begin{pmatrix} \lambda & c\\ 0 & \mu\end{pmatrix}$ , $\abs\lambda, \abs\mu < 1$ . Alors $A^k = PT^kP^{-1}$ , et il suffit que $T^k \to 0$ .

Valeurs propres distinctes : la récurrence donne

T^k = \begin{pmatrix} \lambda^k & c\,\dfrac{\lambda^k - \mu^k}{\lambda - \mu}\\[4pt] 0 & \mu^k \end{pmatrix},

et chaque coefficient tend vers $0$ ( $\abs{\lambda}^k, \abs\mu^k \to 0$ ).

Valeurs propres égales ( $\mu = \lambda$ ) : $T = \lambda I + cE_{12}$ et $T^k = \lambda^k I + k\lambda^{k-1}cE_{12}$ ; le coefficient $k\lambda^{k-1} \to 0$ puisque $\abs\lambda < 1$ (la géométrique l’emporte sur le polynôme). Dans les deux cas $T^k \to 0$ coefficient par coefficient, d’où $A^k = PT^kP^{-1} \to 0$ (la multiplication matricielle par $P, P^{-1}$ fixés est continue dans les coefficients — chaque coefficient du produit est une combinaison linéaire fixée).

Exercice 3.12 ★★

Soit $u \in \mathcal{L}(\C^n)$ avec $\operatorname{rk} u = 1$ ( $n \geq 2$ ). Montrer que $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ , et que $u$ est diagonalisable si et seulement si $\operatorname{tr} u \neq 0$ . (Rappeler de l’Exercice 2.5 que $u^2 = (\operatorname{tr} u)\,u$ .)

Solution

Solution de Exercice 3.12.

$\ker u$ est de dimension $n - 1$ (théorème du rang), donc $0$ est une valeur propre de multiplicité géométrique $n - 1$ , et $\chi_u$ est divisible par $X^{n-1}$ (Définition 3.3 : géométrique $\leq$ algébrique). En écrivant $\chi_u = X^{n-1}(X - \alpha)$ ; le coefficient de $X^{n-1}$ valant $-\operatorname{tr} u$ , on obtient $\alpha = \operatorname{tr} u$ : $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ .

Si $\operatorname{tr} u \neq 0$ : la valeur propre $\operatorname{tr} u$ est une racine de $\chi_u$ , donc elle porte un vecteur propre ; les sous-espaces propres pour $0$ et $\operatorname{tr} u$ ont pour dimensions $n - 1$ et $\geq 1$ , de somme $\geq n$ : ils remplissent $E$ , et $u$ est diagonalisable (Théorème 3.6). Si $\operatorname{tr} u = 0$ : par l’Exercice 2.5, $u^2 = (\operatorname{tr} u)u = 0$ avec $u \neq 0$ : $u$ est un nilpotent non nul, et un nilpotent diagonalisable est nul (Proposition 3.25) : non diagonalisable.

3.5 Problème : récurrences linéaires et matrices compagnons

Une récurrence linéaire $u_{n+k} = a_{k-1}u_{n+k-1} + \dots + a_0 u_n$ est une puissance de matrice déguisée, et la réduction la convertit en formules closes, taux de croissance et estimations d’erreur. Ce problème du week-end développe le dictionnaire — matrices compagnons d’un côté, opérateur de décalage sur l’espace des suites de l’autre — prouve le théorème fondamental des récurrences linéaires (la solution générale est $\sum_i Q_i(n)\lambda_i^n$ sur les racines du polynôme caractéristique), et dépense les dividendes en approximation diophantienne de $\sqrt2$ , en comptage de chemins et de mots, et sur un anneau de suites couplées que seule la diagonalisation simultanée sait démêler.

Problème 3.1

Problème du week-end — le théorème fondamental des récurrences linéaires

Fixons $k \geq 1$ , des scalaires $a_0, \dots, a_{k-1} \in \C$ avec $a_0 \neq 0$ , le polynôme unitaire $P = X^k - a_{k-1}X^{k-1} - \dots - a_1 X - a_0$ , et la récurrence

(\mathcal R)\colon\quad u_{n+k} = a_{k-1}u_{n+k-1} + \dots + a_1 u_{n+1} + a_0 u_n \qquad (n \geq 0).

La matrice compagnon de $P$ est

C = \begin{pmatrix} 0 & 1 & & \\ & \ddots & \ddots & \\ & & 0 & 1\\ a_0 & a_1 & \cdots & a_{k-1} \end{pmatrix} \in \mathcal{M}_k(\C).

Partie I — Le dictionnaire compagnon.

Montrer qu’une suite $(u_n)$ vérifie $(\mathcal R)$ si et seulement si les vecteurs $v_n = (u_n, u_{n+1}, \dots, u_{n+k-1})^{\mathsf T}$ vérifient $v_{n+1} = Cv_n$ , d’où $v_n = C^n v_0$ .
Prouver que $\chi_C = P$ (développer $\det(XI - C)$ selon la première colonne et récurrer sur $k$ ), puis que $\mu_C = P$ également (passer à $C^{\mathsf T}$ , pour laquelle $e_1$ est cyclique, et noter qu’une matrice et sa transposée ont le même polynôme minimal).
Montrer que pour chaque racine $\lambda$ de $P$ , le vecteur $(1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ engendre le sous-espace propre de $C$ pour $\lambda$ ; en déduire que tout sous-espace propre de $C$ est de dimension $1$ , et que $C$ est diagonalisable si et seulement si $P$ a $k$ racines distinctes.
Supposer que $P$ a des racines distinctes $\lambda_1, \dots, \lambda_k$ . Montrer que les suites géométriques $(\lambda_i^n)_n$ forment une base de l’espace des solutions de $(\mathcal R)$ , de sorte que toute solution est $u_n = \sum_i c_i\lambda_i^n$ pour des constantes $c_i$ uniques.
Résoudre complètement : $u_{n+2} = u_{n+1} + 6u_n$ , $u_0 = 1$ , $u_1 = 8$ .

Partie II — L’opérateur de décalage et le théorème fondamental. Soit $\mathcal{S}$ le $\C$ -espace vectoriel de toutes les suites complexes et $S \in \mathcal{L}(\mathcal{S})$ le décalage, $S\bigl((u_n)_n\bigr) = (u_{n+1})_n$ .

Montrer que l’ensemble des solutions de $(\mathcal R)$ est $\ker P(S)$ , et qu’il est de dimension exactement $k$ (envoyer une solution sur ses valeurs initiales).
Expliquer pourquoi le lemme de décomposition des noyaux (Théorème 3.14) s’applique à $S$ sur $\mathcal{S}$ de dimension infinie sans aucun changement, et écrire la décomposition résultante de $\ker P(S)$ pour $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ ( $\lambda_i$ distincts, tous non nuls puisque $a_0 \neq 0$ ).
Pour $\lambda \neq 0$ et $m \geq 1$ , montrer

$\ker\,(S - \lambda\,\mathrm{id})^m = \bigl\{\,\bigl(Q(n)\,\lambda^n\bigr)_n : Q \in \C_{m-1}[X]\,\bigr\},$

de dimension $m$ . (Calculer $(S - \lambda)\bigl(Q(n)\lambda^n\bigr) = \lambda^{n+1}(\Delta Q)(n)$ avec $\Delta Q = Q(X + 1) - Q(X)$ , et utiliser que $\Delta$ abaisse le degré ; pour la dimension, la majorer par $m$ via les valeurs initiales.)
(Le théorème fondamental des récurrences linéaires) Conclure : si $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ avec les $\lambda_i$ distincts et non nuls, les solutions de $(\mathcal R)$ sont exactement les suites

$u_n = \sum_{i=1}^{r} Q_i(n)\,\lambda_i^n, \qquad Q_i \in \C_{m_i - 1}[X],$

avec des polynômes $Q_i$ déterminés de manière unique.
Résoudre complètement : $u_{n+2} = 4u_{n+1} - 4u_n$ , $u_0 = 1$ , $u_1 = 0$ , et vérifier la réponse sur $u_2$ .

Partie III — Racines dominantes et dividendes diophantiens.

Supposer les racines simples avec $\abs{\lambda_1} > \abs{\lambda_i}$ pour $i \geq 2$ , et $u_n = \sum_i c_i \lambda_i^n$ avec $c_1 \neq 0$ . Montrer $u_n \sim c_1\lambda_1^n$ et $u_{n+1}/u_n \to \lambda_1$ .
(Pell) Définir $a_{n+1} = a_n + 2b_n$ , $b_{n+1} = a_n + b_n$ , $a_0 = b_0 = 1$ . Montrer que $q(a, b) = a^2 - 2b^2$ vérifie $q(a_{n+1}, b_{n+1}) = -q(a_n, b_n)$ , d’où $a_n^2 - 2b_n^2 = (-1)^{n+1}$ ; relier ceci au déterminant de $M = \left(\begin{smallmatrix}1 & 2\\ 1 & 1\end{smallmatrix}\right)$ .
En déduire l’estimation d’erreur

$\Bigl|\frac{a_n}{b_n} - \sqrt2\Bigr| = \frac{1}{b_n\,(a_n + \sqrt2\,b_n)} \leq \frac{1}{2b_n^2},$

et montrer qu’elle décroît géométriquement avec un rapport $3 - 2\sqrt2$ (trouver les valeurs propres de $M$ et la croissance de $b_n$ ).
(Croissance générale) À partir de la question 9, prouver : (a) si toute racine vérifie $\abs{\lambda_i} \leq \rho$ , alors $\abs{u_n} \leq C\,n^{m-1}\rho^n$ avec $m = \max_i m_i$ ; (b) s’il existe une unique racine $\lambda_1$ de module maximal et $Q_1 \neq 0$ , alors $u_{n+1}/u_n \to \lambda_1$ — le vérifier sur la solution de la question 10.

Partie IV — Comptage de chemins et de mots. Pour un graphe fini de sommets $\{1, \dots, N\}$ , la matrice d’adjacence $A$ a $A_{ij} = 1$ si $ij$ est une arête, sinon $0$ .

Prouver que $(A^n)_{ij}$ est le nombre de chemins de longueur $n$ de $i$ à $j$ (suites de $n$ arêtes, chaque pas le long d’une arête).
(Le triangle) Pour le graphe complet à $3$ sommets, $A = J - I$ : en utilisant le spectre de $J$ (Exemple 2.19), montrer

$(A^n)_{ii} = \frac{2^n + 2(-1)^n}{3}, \qquad (A^n)_{ij} = \frac{2^n - (-1)^n}{3} \quad (i \neq j),$

et vérifier les deux en $n = 2$ en énumérant les chemins.
(Mots sans $11$ ) Soit $w_n$ le nombre de mots binaires de longueur $n$ sans deux $1$ consécutifs. Encoder les mots par leur dernière lettre pour obtenir une matrice de transfert, montrer $w_{n+2} = w_{n+1} + w_n$ , en déduire $w_n = F_{n+2}$ (Fibonacci, Exercice 3.5), et donner le taux de croissance $\lim w_{n+1}/w_n$ .
(Le chemin) Pour le graphe en chemin $1 - 2 - 3$ , montrer que les valeurs propres de $A$ sont $\sqrt2, 0, -\sqrt2$ de vecteurs propres $(1, \pm\sqrt2, 1)$ et $(1, 0, -1)$ , et en déduire que le nombre de chemins de longueur $n$ d’un bout à l’autre est $\bigl((\sqrt2)^n + (-\sqrt2)^n\bigr)/4$ : nul pour $n$ impair, et $2^{\,n/2 - 1}$ pour $n$ pair. Vérifier en $n = 4$ .
(Formule de la trace) Montrer que le nombre total de chemins fermés de longueur $n$ (tous points de départ) est $\operatorname{tr}(A^n) = \sum_i \lambda_i^n$ , et le vérifier sur le triangle.

Partie V — Un anneau de suites : diagonalisation simultanée. Fixons $k \geq 3$ , soit $\omega = \eu^{2\iu\pi/k}$ , et soit $W \in \mathcal{M}_k(\C)$ le décalage cyclique : $W e_i = e_{i+1}$ (indices modulo $k$ , colonnes indexées $0, \dots, k-1$ ).

Montrer que $W^{\mathsf T}$ est la matrice compagnon de $X^k - 1$ , en déduire $\chi_W = \mu_W = X^k - 1$ , et que $W$ est diagonalisable avec les $k$ valeurs propres simples $\omega^j$ et les vecteurs propres $f_j = (1, \omega^{-j}, \omega^{-2j}, \dots, \omega^{-(k-1)j})^{\mathsf T}$ .
Une matrice circulante est $C = c_0 I + c_1 W + \dots + c_{k-1}W^{k-1}$ . Montrer que toutes les circulantes commutent, que la base $(f_0, \dots, f_{k-1})$ les diagonalise toutes simultanément, et que les valeurs propres de $C$ sont $\widehat c(\omega^j) = \sum_m c_m \omega^{jm}$ , $j = 0, \dots, k-1$ .
En déduire $\det C = \prod_{j=0}^{k-1} \widehat c(\omega^j)$ , et vérifier que $k = 3$ retrouve la factorisation de l’Exercice 2.8.
(La moyenne sur le collier) Soit $x^{(n+1)} = Mx^{(n)}$ avec $M = \frac12(W + W^{-1})$ : chacun des $k$ nombres disposés en anneau est remplacé par la moyenne de ses deux voisins. Montrer que les valeurs propres de $M$ sont $\cos(2\pi j/k)$ , et que le coefficient de $x^{(0)}$ sur $f_0$ est la moyenne $\frac1k\sum_m x^{(0)}_m$ (sommer les coordonnées des $f_j$ ).
Conclure : pour $k$ impair, $x^{(n)}$ converge vers le vecteur constant dont la valeur est la moyenne des valeurs initiales ; pour $k = 4$ , exhiber la valeur propre responsable de la non-convergence et l’obstruction exacte (un coefficient de moyenne alternée qui doit s’annuler).
(Synthèse) En une phrase chacun : comment la matrice compagnon convertit l’analyse de $(\mathcal R)$ en réduction ; où le lemme de décomposition des noyaux n’a eu besoin d’aucune dimension finie ; pourquoi les valeurs propres dominantes gouvernent taux de croissance et erreur diophantienne ; pourquoi les puissances de la matrice d’adjacence comptent les chemins ; et ce qu’apportent les matrices qui commutent. Nommer les deux sommets : le théorème fondamental des récurrences linéaires, et — pour les matrices positives de la partie IV, dans le volume de l’année 3 — le théorème de Perron–Frobenius.

Solution

Solution de Problème 3.1.

1. Les $k - 1$ premières coordonnées de $Cv_n$ sont $u_{n+1}, \dots, u_{n+k-1}$ (la surdiagonale décale), et la dernière est $a_0 u_n + \dots + a_{k-1}u_{n+k-1}$ . Donc $v_{n+1} = Cv_n$ vaut pour tout $n$ si et seulement si les dernières coordonnées coïncident pour tout $n$ , c’est-à-dire si et seulement si $(\mathcal R)$ vaut. En itérant, $v_n = C^nv_0$ .

2. Développons $D_k(X) = \det(XI_k - C)$ selon la première colonne : les deux entrées non nulles sont $X$ (position $(1,1)$ ) et $-a_0$ (position $(k,1)$ ). Le premier mineur est de forme $D_{k-1}$ pour les coefficients $a_1, \dots, a_{k-1}$ ; le second mineur est triangulaire supérieur de diagonale $-1$ : déterminant $(-1)^{k-1}$ , de signe $(-1)^{k+1}$ dû à la position. La récurrence sur $k$ (base $k = 1$ : $X - a_0$ ) donne

D_k(X) = X\bigl(X^{k-1} - a_{k-1}X^{k-2} - \dots - a_1\bigr) - a_0 = P(X).

Pour $\mu_C$ : puisque $Q(C^{\mathsf T}) = Q(C)^{\mathsf T}$ pour tout polynôme, $C$ et $C^{\mathsf T}$ ont les mêmes annulateurs, donc le même polynôme minimal. Pour $C^{\mathsf T}$ : les colonnes donnent $C^{\mathsf T}e_1 = e_2$ , …, $C^{\mathsf T}e_{k-1} = e_k$ , donc $(e_1, C^{\mathsf T}e_1, \dots, (C^{\mathsf T})^{k-1}e_1)$ est la base canonique : libre. Un polynôme $Q \neq 0$ de degré $< k$ a alors $Q(C^{\mathsf T})e_1 \neq 0$ (c’est une combinaison non triviale de vecteurs de base) : $\deg\mu \geq k$ . Comme $\mu \mid \chi = P$ avec $\deg P = k$ : $\mu_C = P$ .

3. Pour $v = (1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ : les lignes $1$ à $k-1$ de $Cv$ donnent $\lambda, \lambda^2, \dots, \lambda^{k-1}$ , c’est-à-dire $\lambda$ fois les $k - 1$ premières entrées de $v$ ; la dernière ligne donne $\sum_m a_m\lambda^m = \lambda^k - P(\lambda) = \lambda^k = \lambda\cdot\lambda^{k-1}$ . Donc $Cv = \lambda v$ . Réciproquement, les équations $(Cx)_i = \lambda x_i$ pour $i < k$ donnent $x_{i+1} = \lambda x_i$ : tout vecteur propre est proportionnel à $v$ — tout sous-espace propre est de dimension exactement $1$ . Diagonalisable si et seulement si les dimensions des sous-espaces propres somment à $k$ (Théorème 3.6) si et seulement s’il y a $k$ valeurs propres distinctes si et seulement si $P$ a $k$ racines distinctes (les valeurs propres sont les racines de $\chi_C = P$ ).

4. Chaque $(\lambda_i^n)_n$ résout $(\mathcal R)$ : $\lambda_i^{n+k} = \lambda_i^n\,\lambda_i^k = \lambda_i^n\sum_m a_m\lambda_i^m$ . Liberté : une combinaison nulle $\sum_i c_i\lambda_i^n = 0$ pour $n = 0, \dots, k-1$ est un système de Vandermonde (Exercice 2.11) en les $c_i$ : tous $c_i = 0$ . L’espace des solutions est de dimension $k$ (question 6, dont la preuve est élémentaire et indépendante) : $k$ solutions libres forment une base, et les coordonnées sont uniques.

5. $P = X^2 - X - 6 = (X - 3)(X + 2)$ : solution générale $u_n = A\,3^n + B(-2)^n$ . Conditions initiales : $A + B = 1$ , $3A - 2B = 8$ : $A = 2$ , $B = -1$ :

u_n = 2\cdot 3^n - (-2)^n .

(Vérification : $u_2 = u_1 + 6u_0 = 14$ et $2\cdot9 - 4 = 14$ .)

6. $P(S)\bigl((u_n)\bigr)$ est la suite $n \mapsto u_{n+k} - a_{k-1}u_{n+k-1} - \dots - a_0u_n$ : elle s’annule si et seulement si $(\mathcal R)$ vaut, donc l’ensemble des solutions est $\ker P(S)$ , un sous-espace. L’application $\ker P(S) \to \C^k$ , $u \mapsto (u_0, \dots, u_{k-1})$ , est linéaire, injective (la récurrence détermine $u_{k}, u_{k+1}, \dots$ à partir des $k$ premières valeurs, par récurrence) et surjective (on définit $u_n$ récursivement à partir de n’importe quelle donnée initiale) : dimension $k$ .

7. La preuve du Théorème 3.14 n’utilise que : l’identité de Bézout dans $\C[X]$ , et le fait que les polynômes en un endomorphisme fixé commutent. Ni l’une ni l’autre ne mentionne la dimension de l’espace ambiant : le lemme vaut mot pour mot pour $S \in \mathcal{L}(\mathcal{S})$ . Ainsi

\ker P(S) = \bigoplus_{i=1}^{r} \ker\,(S - \lambda_i\,\mathrm{id})^{m_i}.

8. Pour $Q \in \C[X]$ : $(S - \lambda)\bigl(Q(n)\lambda^n\bigr)_n$ a pour terme $n$ -ième $Q(n{+}1)\lambda^{n+1} - \lambda Q(n)\lambda^n = \lambda^{n+1}(\Delta Q)(n)$ , avec $\Delta Q = Q(X{+}1) - Q(X)$ de degré $\deg Q - 1$ (les termes de tête se compensent). En itérant, $(S - \lambda)^m\bigl(Q(n)\lambda^n\bigr) = \bigl(\lambda^{n+m}(\Delta^m Q)(n)\bigr)_n$ , et $\Delta^m Q = 0$ lorsque $\deg Q \leq m - 1$ : l’ensemble de droite est contenu dans le noyau. C’est un sous-espace de dimension $m$ : les suites $(n^j\lambda^n)_n$ , $0 \leq j < m$ , sont libres, car $\sum_j c_j n^j\lambda^n = 0$ pour tout $n$ force (en divisant par $\lambda^n \neq 0$ ) le polynôme $\sum_j c_jX^j$ à s’annuler en tout $n \in \N$ , donc à être nul. Réciproquement $\dim\ker(S - \lambda)^m \leq m$ : en développant $(S - \lambda)^m = \sum_j \binom mj(-\lambda)^{m-j}S^j$ , l’équation $(S - \lambda)^m u = 0$ est une récurrence linéaire d’ordre $m$ (coefficient de tête $1$ ), donc $u$ est déterminée par $u_0, \dots, u_{m-1}$ comme à la question 6. L’égalité des dimensions conclut.

9. On combine les questions 7 et 8 : toute solution se décompose de manière unique en somme d’éléments des $\ker(S - \lambda_i)^{m_i}$ , c’est-à-dire $u_n = \sum_i Q_i(n)\lambda_i^n$ avec $\deg Q_i \leq m_i - 1$ ; les $Q_i$ sont uniques car la décomposition est directe et, dans chaque facteur, les coefficients de $Q_i$ sont des coordonnées dans la base $(n^j\lambda_i^n)_j$ (question 8). Vérification de cohérence sur les dimensions : $\sum_i m_i = k$ .

10. $P = X^2 - 4X + 4 = (X - 2)^2$ : solutions $(a + bn)2^n$ . Données initiales : $a = 1$ , $2(a + b) = 0$ , donc $b = -1$ :

u_n = (1 - n)\,2^n .

Vérification : $u_2 = 4u_1 - 4u_0 = -4$ , et $(1 - 2)\cdot4 = -4$ .

11. Écrivons $u_n = \lambda_1^n\bigl(c_1 + \sum_{i\geq2} c_i(\lambda_i/\lambda_1)^n\bigr)$ ; chaque rapport est de module $< 1$ , donc le crochet tend vers $c_1 \neq 0$ : $u_n \sim c_1\lambda_1^n$ . En particulier $u_n \neq 0$ pour $n$ grand, et

\frac{u_{n+1}}{u_n} = \lambda_1\,\frac{c_1 + o(1)}{c_1 + o(1)} \longrightarrow \lambda_1 .

12. On calcule :

q(a_{n+1}, b_{n+1}) = (a_n + 2b_n)^2 - 2(a_n + b_n)^2 = -a_n^2 + 2b_n^2 = -q(a_n, b_n).

Avec $q(a_0, b_0) = 1 - 2 = -1$ : $a_n^2 - 2b_n^2 = (-1)^{n+1}$ . Structurellement : $q(a, b) = (a - \sqrt2\,b)(a + \sqrt2\,b)$ et l’application linéaire $M$ multiplie le facteur $a + \sqrt2 b$ par $1 + \sqrt2$ et le facteur $a - \sqrt2 b$ par $1 - \sqrt2$ (calculer : $a_{n+1} + \sqrt2 b_{n+1} = (1 + \sqrt2)(a_n + \sqrt2 b_n)$ ) ; le produit est multiplié par $(1 + \sqrt2)(1 - \sqrt2) = -1 = \det M$ à chaque pas.

13. Puisque $a_n^2 - 2b_n^2 = (a_n - \sqrt2 b_n)(a_n + \sqrt2 b_n) = (-1)^{n+1}$ ,

\Bigl|\frac{a_n}{b_n} - \sqrt2\Bigr| = \frac{\abs{a_n^2 - 2b_n^2}}{b_n(a_n + \sqrt2 b_n)} = \frac{1}{b_n(a_n + \sqrt2 b_n)} \leq \frac1{2b_n^2},

en utilisant $a_n \geq b_n \geq 1$ (par récurrence : les deux croissent) donc $a_n + \sqrt2 b_n \geq (1 + \sqrt2)b_n \geq 2b_n$ . Valeurs propres de $M$ : $\chi_M = X^2 - 2X - 1$ , racines $1 \pm \sqrt2$ ; puisque $(a_0, b_0)$ a une composante non nulle sur le vecteur propre dominant (toutes les entrées positives), $b_n \sim c(1 + \sqrt2)^n$ avec $c > 0$ (question 11). D’où l’erreur est $\asymp (1 + \sqrt2)^{-2n} = (3 + 2\sqrt2)^{-n}$ : décroissance géométrique de rapport $1/(3 + 2\sqrt2) = 3 - 2\sqrt2 \approx 0{,}172$ .

14. (a) À partir de la question 9 : $\abs{u_n} \leq \sum_i \abs{Q_i(n)}\abs{\lambda_i}^n \leq \bigl(\sum_i \abs{Q_i(n)}\bigr)\rho^n$ , et chaque $\abs{Q_i(n)} \leq C_i n^{m_i - 1} \leq C_i n^{m-1}$ pour $n \geq 1$ : on somme les constantes. (b) Soit $\rho' = \max_{i \geq 2}\abs{\lambda_i} < \abs{\lambda_1}$ et $d = \deg Q_1$ , de coefficient de tête $c \neq 0$ . Alors $u_n = Q_1(n)\lambda_1^n + R_n$ avec $\abs{R_n} \leq Cn^{m-1}\rho'^n$ , et

\frac{R_n}{Q_1(n)\lambda_1^n} = O\Bigl(n^{m-1-d} \bigl(\rho'/\abs{\lambda_1}\bigr)^n\Bigr) \longrightarrow 0

(la géométrique l’emporte sur le polynôme). Donc

u_n \sim Q_1(n)\,\lambda_1^n \sim c\,n^d\lambda_1^n, \qquad \frac{u_{n+1}}{u_n} \longrightarrow \lambda_1 \quad\text{(puisque } Q_1(n{+}1)/Q_1(n) \to 1\text{)}.

Vérification sur la question 10 : pour $u_n = (1-n)2^n$ le rapport est

\frac{(-n)2^{n+1}}{(1-n)2^n} = 2\,\frac{-n}{1-n} \longrightarrow 2 = \lambda_1 .

15. Récurrence sur $n$ . Pour $n = 1$ , $A_{ij}$ compte les chemins de longueur $1$ . Étape : un chemin de longueur $n + 1$ de $i$ à $j$ est un chemin de longueur $n$ de $i$ vers un sommet $\ell$ suivi d’une arête $\ell j$ :

\#\{\text{chemins}\} = \sum_{\ell} (A^n)_{i\ell}A_{\ell j} = (A^{n+1})_{ij}.

16. $J = 3\Pi$ où $\Pi = J/3$ est la projection sur $\operatorname{Vect}(1,1,1)$ parallèlement au plan $x + y + z = 0$ ( $\Pi^2 = \Pi$ puisque $J^2 = 3J$ ). Alors $A = J - I = 2\Pi - (I - \Pi)$ , et puisque $\Pi$ et $I - \Pi$ sont des projections complémentaires,

A^n = 2^n\,\Pi + (-1)^n (I - \Pi), \qquad\text{c'est-à-dire}\qquad (A^n)_{ij} = \frac{2^n}3 + (-1)^n\Bigl(\delta_{ij} - \frac13\Bigr),

ce qui donne les deux formules affichées. En $n = 2$ : diagonale $(4 + 2)/3 = 2$ (chemins $i \to \ell \to i$ pour les deux voisins $\ell$ ) ; hors diagonale $(4 - 1)/3 = 1$ (l’unique chemin $i \to \ell \to j$ par le troisième sommet).

17. Soit $w_n^{(0)}, w_n^{(1)}$ le nombre de mots admissibles de longueur $n$ finissant par $0$ , resp. par $1$ . En ajoutant une lettre : un $0$ peut suivre n’importe quoi, un $1$ seulement un $0$ :

\begin{pmatrix} w_{n+1}^{(0)}\\ w_{n+1}^{(1)}\end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix} \begin{pmatrix} w_n^{(0)}\\ w_n^{(1)}\end{pmatrix}.

En sommant, $w_{n+2} = w_{n+1} + w_n$ (ou : conditionner sur la première lettre). Avec $w_1 = 2$ , $w_2 = 3$ : $w_n = F_{n+2}$ par récurrence ( $F_3 = 2$ , $F_4 = 3$ , même récurrence). Croissance : les racines de $X^2 - X - 1$ sont $\varphi > \abs\psi$ (Exercice 3.5), et la composante en $\varphi$ est non nulle (les $w_n$ sont positifs et $\psi^n \to 0$ ), donc la question 11 donne $w_{n+1}/w_n \to \varphi = \frac{1 + \sqrt5}2$ .

18. $A = \left(\begin{smallmatrix} 0&1&0\\ 1&0&1\\ 0&1&0\end{smallmatrix}\right)$ . Vérification :

A(1, \pm\sqrt2, 1)^{\mathsf T} = (\pm\sqrt2, 2, \pm\sqrt2)^{\mathsf T} = \pm\sqrt2\,(1, \pm\sqrt2, 1)^{\mathsf T}, \qquad A(1, 0, -1)^{\mathsf T} = 0 :

valeurs propres $\sqrt2, -\sqrt2, 0$ ( $= 2\cos\frac\pi4, 2\cos\frac{3\pi}4, 2\cos\frac\pi2$ ). On décompose $e_1$ sur la base propre et on lit la troisième coordonnée, ou l’on utilise la symétrie : avec $v_\pm = (1, \pm\sqrt2, 1)$ , $v_0 = (1, 0, -1)$ , on vérifie $e_1 = \frac14 v_+ + \frac14 v_- + \frac12 v_0$ , donc pour $n \geq 1$

(A^n)_{13} = \Bigl(\tfrac14(\sqrt2)^n v_+ + \tfrac14(-\sqrt2)^n v_- + 0\Bigr)_{\!3} = \frac{(\sqrt2)^n + (-\sqrt2)^n}{4},

nul pour $n$ impair (graphe biparti : les extrémités sont à distance paire), et $2\cdot 2^{n/2}/4 = 2^{n/2 - 1}$ pour $n$ pair. En $n = 4$ : $2^{1} = 2$ , en accord avec les deux chemins $1\,2\,1\,2\,3$ et $1\,2\,3\,2\,3$ .

19. Les chemins fermés de longueur $n$ issus de $i$ sont $(A^n)_{ii}$ ; en sommant sur $i$ on obtient $\operatorname{tr}(A^n)$ . En trigonalisant $A$ (sur $\C$ ), $A^n$ est triangulaire de diagonale $\lambda_i^n$ : $\operatorname{tr}(A^n) = \sum_i\lambda_i^n$ . Triangle : $\operatorname{tr}(A^n) = 3\,\frac{2^n + 2(-1)^n}3 = 2^n + 2(-1)^n = 2^n + (-1)^n + (-1)^n$ : le spectre $\{2, -1, -1\}$ , cohérent avec la question 16.

20. Les colonnes de $W^{\mathsf T}$ : $W^{\mathsf T}e_i = e_{i-1}$ pour $i \geq 1$ et $W^{\mathsf T}e_0 = e_{k-1}$ ; en réétiquetant dans l’ordre $e_0, e_1, \dots$ c’est exactement la matrice compagnon de $X^k - 1$ ( $a_0 = 1$ , autres $a_m = 0$ ). Question 2 : $\chi_{W} = \chi_{W^{\mathsf T}} = X^k - 1 = \mu_{W}$ . Les racines $\omega^j$ ( $j = 0, \dots, k-1$ ) sont les $k$ racines $k$ -ièmes distinctes de l’unité : $W$ est diagonalisable (question 3, ou Exercice 3.8 : $W^k = I$ ). Vecteurs propres : $Wf_j = \sum_m \omega^{-jm}e_{m+1} = \sum_{m'}\omega^{-j(m'-1)}e_{m'} = \omega^j f_j$ .

21. Les circulantes sont des polynômes en $W$ , et les polynômes en une matrice fixée commutent entre eux. Chaque $f_j$ est un vecteur propre de toute puissance : $W^m f_j = \omega^{jm}f_j$ , donc

Cf_j = \sum_m c_m\omega^{jm} f_j = \widehat c(\omega^j)\,f_j :

la base $(f_0, \dots, f_{k-1})$ (libre : Vandermonde en les $\omega^{-j}$ distincts, Exercice 2.11) diagonalise toute circulante d’un coup, avec les valeurs propres annoncées.

22. Le déterminant est le produit des valeurs propres (diagonaliser) : $\det C = \prod_{j}\widehat c(\omega^j)$ . Pour $k = 3$ , $c_0 = a$ , $c_1 = b$ , $c_2 = c$ et $\omega = j = \eu^{2\iu\pi/3}$ :

\det C = (a + b + c)(a + bj + cj^2)(a + bj^2 + cj^4),

et $j^4 = j$ : exactement la factorisation de l’Exercice 2.8.

23. $M = \frac12(W + W^{-1})$ est une circulante ( $W^{-1} = W^{k-1}$ ), de valeurs propres $\frac12(\omega^j + \omega^{-j}) = \cos\frac{2\pi j}k$ sur la même base $f_j$ . Coordonnées : écrivons $x^{(0)} = \sum_j \alpha_j f_j$ . Les coordonnées de $f_j$ somment à $\sum_m \omega^{-jm}$ , qui vaut $k$ pour $j = 0$ et $0$ sinon (somme géométrique de raison $\omega^{-j} \neq 1$ ). En sommant les coordonnées de $x^{(0)}$ : $\sum_m x^{(0)}_m = \alpha_0\,k$ , donc $\alpha_0 = \frac1k\sum_m x^{(0)}_m$ , la moyenne.

24. $x^{(n)} = M^nx^{(0)} = \sum_j \alpha_j\cos^n\bigl(\tfrac{2\pi j}k\bigr)f_j$ . Pour $k$ impair, $\abs{\cos(2\pi j/k)} < 1$ pour tout $j \neq 0$ (l’angle n’est jamais $0$ ni $\pi$ ), donc tous les termes sauf $j = 0$ tendent vers $0$ : $x^{(n)} \to \alpha_0 f_0$ , le vecteur constant égal à la moyenne — moyenner sur un anneau impair égalise. Pour $k = 4$ les valeurs propres sont $1, 0, -1, 0$ : le terme $j = 2$ $\alpha_2(-1)^nf_2$ avec $f_2 = (1, -1, 1, -1)^{\mathsf T}$ oscille indéfiniment. L’obstruction est la moyenne alternée : en multipliant les coordonnées de $x^{(0)}$ par $(-1)^m$ et en sommant, le même calcul de somme géométrique donne $\sum_m (-1)^mx^{(0)}_m = 4\alpha_2$ : le processus converge si et seulement si $x^{(0)}_0 - x^{(0)}_1 + x^{(0)}_2 - x^{(0)}_3 = 0$ , et converge alors vers la moyenne.

25. La matrice compagnon convertit une récurrence scalaire d’ordre $k$ en une récurrence vectorielle d’ordre un, de sorte que les formules closes deviennent des énoncés sur $C^n$ — le terrain de la réduction (questions 1–5). Le lemme de décomposition des noyaux est pure algèbre polynomiale (Bézout plus commutation), donc il scinde $\ker P(S)$ même si $\mathcal{S}$ est de dimension infinie (questions 7–9). Les valeurs propres dominantes gouvernent la croissance parce que toute autre contribution est géométriquement négligeable après normalisation — ce qui explique aussi pourquoi l’erreur de Pell décroît au carré de la racine dominante (questions 11–14). Les puissances de la matrice d’adjacence comptent les chemins parce que la multiplication matricielle somme sur les sommets intermédiaires, donc les spectres comptent les chemins fermés (questions 15–19). Les matrices qui commutent partagent une base propre, et une base de Fourier diagonalise alors toute l’algèbre des circulantes d’un seul geste (questions 20–24). Sommets : le théorème fondamental des récurrences linéaires (question 9) ; et pour les matrices positives, la raison pour laquelle les racines dominantes comme $\varphi$ ou $1 + \sqrt2$ sont automatiquement réelles, positives et simples est le théorème de Perron–Frobenius, prouvé dans le volume de l’année 3.