Théorème de Cayley-Hamilton, puissances de matrices et suites récurrentes

Une récurrence semble demander de connaître indéfiniment les termes précédents ; une puissance $A^n$ semble, elle aussi, demander un nombre de multiplications qui augmente avec $n$. Pourtant, lorsqu'une dynamique est linéaire et vit dans un espace de dimension finie, cette impression est trompeuse.

Le problème part d'un exemple élémentaire pour comprendre progressivement ce phénomène. Les notions d'algèbre linéaire nécessaires sont rappelées ou introduites au moment où elles deviennent utiles.

I — D'un système de suites à une relation entre matrices

On définit deux suites réelles $(x_n)$ et $(y_n)$ par

$$x_0=1,\qquad y_0=0$$

et, pour tout $n\geq0$,

$$\begin{cases} x_{n+1}=2x_n+y_n,\\ y_{n+1}=x_n+y_n. \end{cases}$$

1. Deux suites, une même récurrence

(a) Calculer les quatre premiers couples $(x_n,y_n)$.

(b) Montrer que les deux suites satisfont la même relation

$$z_{n+2}=3z_{n+1}-z_n.$$

(c) Expliquer pourquoi deux termes consécutifs d'une suite satisfaisant cette relation déterminent tous les suivants.

On cherche maintenant à comprendre pourquoi la même relation apparaît simultanément pour $x_n$ et $y_n$.

Pour

$$A=\begin{pmatrix}2&1\\1&1\end{pmatrix}, \qquad U_n=\begin{pmatrix}x_n\\y_n\end{pmatrix},$$

on rappelle que

$$\begin{pmatrix}a&b\\c&d\end{pmatrix} \begin{pmatrix}x\\y\end{pmatrix} = \begin{pmatrix}ax+by\\cx+dy\end{pmatrix}.$$

On note $I_2$ la matrice identité.

2. Changer de langage

Montrer que

$$U_{n+1}=AU_n,$$

puis que

$$U_n=A^nU_0$$

pour tout $n\geq0$.

Le calcul de $U_n$ semble donc avoir été remplacé par celui de $A^n$. Il reste à savoir si ce changement est réellement utile.

3. Toutes les puissances sont-elles vraiment nouvelles ?

Calculer $A^2$ et chercher une relation linéaire entre $I_2$, $A$ et $A^2$.

En déduire une relation satisfaite par la suite de matrices

$$(I_2,A,A^2,A^3,\ldots).$$

4. Une compression explicite

On définit

$$p_0=0,\qquad p_1=1,\qquad p_{n+2}=3p_{n+1}-p_n.$$

Montrer que, pour tout $n\geq1$,

$$A^n=p_nA-p_{n-1}I_2.$$

En déduire des expressions de $x_n$ et $y_n$ à l'aide de la seule suite $(p_n)$.

Ainsi, une infinité de matrices $A^n$ est contenue dans l'espace engendré par seulement deux matrices.

5. Le phénomène en dimension 2

Soit désormais

$$B=\begin{pmatrix}a&b\\c&d\end{pmatrix}\in M_2(\mathbb R).$$

On pose

$$\operatorname{tr}(B)=a+d, \qquad \det(B)=ad-bc.$$

(a) Montrer directement que

$$B^2-\operatorname{tr}(B)B+\det(B)I_2=0.$$

(b) En déduire que, pour tout $n\geq0$,

$$B^{n+2}=\operatorname{tr}(B)B^{n+1}-\det(B)B^n.$$

(c) Soit $V_0\in\mathbb R^2$ et $V_n=B^nV_0$. Montrer que chacune des deux coordonnées de $V_n$ satisfait une même récurrence linéaire d'ordre au plus 2, que l'on précisera.

La partie suivante cherche à comprendre ce que devient cette observation lorsque la dimension n'est plus égale à 2.

II — Polynômes d'un endomorphisme et relations d'annulation

Dans toute la suite, $K$ désigne un corps commutatif — on peut garder $K=\mathbb R$ en tête — et $E$ un $K$-espace vectoriel de dimension finie $d\geq1$.

Un endomorphisme de $E$ est une application linéaire de $E$ dans lui-même. On note $\operatorname{End}(E)$ l'ensemble de ces endomorphismes,

$$u^0=\operatorname{Id}_E, \qquad u^{n+1}=u\circ u^n.$$

Après choix d'une base de $E$, un endomorphisme est représenté par une matrice $d\times d$ ; en particulier,

$$\dim\operatorname{End}(E)=d^2.$$

6. Donner un sens à $P(u)$

Pour

$$P(X)=a_0+a_1X+\cdots+a_rX^r\in K[X],$$

on définit

$$P(u)=a_0\operatorname{Id}_E+a_1u+\cdots+a_ru^r.$$

(a) Montrer que, pour tous $P,Q\in K[X]$,

$$(P+Q)(u)=P(u)+Q(u)$$

et

$$(PQ)(u)=P(u)\circ Q(u).$$

(b) En déduire que deux endomorphismes de la forme $P(u)$ et $Q(u)$ commutent toujours.

On appelle polynôme annulateur de $u$ tout polynôme non nul $P\in K[X]$ tel que

$$P(u)=0.$$

7. Pourquoi un polynôme annulateur existe-t-il toujours ?

(a) Réinterpréter la relation trouvée à la question 3 comme l'annulation de la matrice $A$ par un polynôme.

(b) Montrer que tout multiple d'un polynôme annulateur est encore annulateur.

(c) En utilisant uniquement

$$\dim\operatorname{End}(E)=d^2,$$

montrer que tout endomorphisme de $E$ possède au moins un polynôme annulateur non nul.

(d) Quel contrôle cette démonstration donne-t-elle sur le degré d'un tel polynôme ? Expliquer ce qu'elle ne dit pas encore.

On rappelle la division euclidienne dans $K[X]$ : si $P\neq0$, alors pour tout $Q\in K[X]$, il existe un unique couple $(S,R)$ tel que

$$Q=SP+R,$$

avec $R=0$ ou $\deg R<\deg P$.

8. Réduire toutes les puissances à un nombre fini d'entre elles

Soit

$$P(X)=X^r+a_{r-1}X^{r-1}+\cdots+a_1X+a_0$$

un polynôme annulateur unitaire de $u$.

(a) Soit $Q\in K[X]$ et soit $R$ le reste de la division euclidienne de $Q$ par $P$. Montrer que

$$Q(u)=R(u).$$

(b) En déduire que toutes les puissances de $u$ appartiennent à

$$\operatorname{Vect}\bigl(\operatorname{Id}_E,u,\ldots,u^{r-1}\bigr).$$

(c) Montrer plus précisément que

$$u^{n+r}+a_{r-1}u^{n+r-1}+\cdots+a_0u^n=0$$

pour tout $n\geq0$.

Soit maintenant $v\in E$ et soit $\ell:E\to K$ une forme linéaire. On définit

$$s_n=\ell(u^n(v)).$$

Montrer que $(s_n)$ satisfait la récurrence linéaire

$$s_{n+r}+a_{r-1}s_{n+r-1}+\cdots+a_0s_n=0.$$

III — Le théorème de Cayley-Hamilton

Soit $u\in\operatorname{End}(E)$. Si $A$ est sa matrice dans une base de $E$, on définit

$$\chi_u(X)=\det(XI_d-A).$$

9. Le polynôme caractéristique

(a) Si $A'=S^{-1}AS$ est la matrice de $u$ dans une autre base, montrer que

$$\det(XI_d-A')=\det(XI_d-A).$$

La définition de $\chi_u$ ne dépend donc pas de la base choisie.

(b) Montrer que $\chi_u$ est un polynôme unitaire de degré $d$.

10. Retrouver la dimension 2

Pour $B\in M_2(K)$, établir

$$\chi_B(X)=X^2-\operatorname{tr}(B)X+\det(B).$$

Comparer alors la question 5 avec l'égalité

$$\chi_B(B)=0.$$

Le phénomène découvert en dimension 2 est général.

Théorème de Cayley-Hamilton. Pour tout endomorphisme $u$ d'un espace vectoriel de dimension finie, $\chi_u(u)=0$. La démonstration générale du théorème n'est pas demandée dans ce problème.

11. Ce que Cayley-Hamilton apporte

(a) Pour tout $n\geq0$, soit $R_n$ le reste de la division euclidienne de $X^n$ par $\chi_u$. Montrer que

$$u^n=R_n(u)$$

et que

$$\deg R_n<d.$$

(b) Si

$$\chi_u(X)=X^d+c_{d-1}X^{d-1}+\cdots+c_0,$$

écrire la relation de récurrence satisfaite par les puissances $u^n$.

(c) Comparer ce résultat à l'existence obtenue à la question 7. Quelle information supplémentaire essentielle apporte Cayley-Hamilton ?

12. Une puissance élevée sans diagonalisation

On considère

$$M=\begin{pmatrix} 0&0&1\\ 1&0&1\\ 0&1&0 \end{pmatrix}.$$

(a) Calculer son polynôme caractéristique.

(b) En déduire une relation entre $I_3$, $M$ et $M^3$.

(c) Calculer le reste de $X^{20}$ dans la division par

$$X^3-X-1,$$

en cherchant à éviter vingt multiplications successives.

(d) En déduire $M^{20}$.

IV — Suites récurrentes et systèmes linéaires : deux langages

Nous avons montré qu'une relation polynomiale sur un endomorphisme engendre des récurrences. On établit maintenant une réciproque.

Soient $r\geq1$ et

$$P(X)=X^r+a_{r-1}X^{r-1}+\cdots+a_0.$$

On considère une suite $(s_n)$ vérifiant

$$s_{n+r}+a_{r-1}s_{n+r-1}+\cdots+a_0s_n=0.$$

13. Transformer une récurrence en dynamique matricielle

On pose

$$V_n= \begin{pmatrix} s_n\\ s_{n+1}\\ \vdots\\ s_{n+r-1} \end{pmatrix}.$$

Pour $r=1$, on lit simplement $C=(-a_0)$. Pour $r\geq2$, on pose

$$C= \begin{pmatrix} 0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&&&\ddots&\vdots\\ 0&0&0&\cdots&1\\ -a_0&-a_1&-a_2&\cdots&-a_{r-1} \end{pmatrix}.$$

(a) Montrer que

$$V_{n+1}=CV_n.$$

(b) En déduire

$$V_n=C^nV_0.$$

Si $\pi_1$ désigne la première coordonnée, montrer alors que

$$s_n=\pi_1(C^nV_0).$$

(c) Mettre ce résultat en regard de la dernière question de la partie II : quel lien général obtient-on entre suites récurrentes linéaires et itérations d'applications linéaires en dimension finie ?

14. Toute dynamique linéaire finie produit des récurrences

Soit $A\in M_d(K)$ et $V_0\in K^d$. On définit la suite $(V_n)$ par

$$V_{n+1}=AV_n.$$

Si

$$\chi_A(X)=X^d+c_{d-1}X^{d-1}+\cdots+c_0,$$

montrer que chacune des coordonnées de $V_n$, et plus généralement toute combinaison linéaire fixe de ces coordonnées, satisfait

$$s_{n+d}+c_{d-1}s_{n+d-1}+\cdots+c_0s_n=0.$$

Retrouver ainsi la récurrence de la question 1 à partir du polynôme caractéristique de la matrice $A$ de la première partie.

15. Un autre observateur : la trace des puissances

Pour une matrice $A\in M_d(K)$, on pose

$$t_n=\operatorname{tr}(A^n).$$

Montrer que $(t_n)$ satisfait elle aussi la récurrence associée à $\chi_A$.

Expliquer pourquoi ce résultat relève exactement du même principe que les questions précédentes, bien que la suite $(t_n)$ n'ait pas été présentée initialement comme une coordonnée d'un vecteur $A^nv$.

V — Jusqu'où peut-on comprimer ?

Cayley-Hamilton assure qu'un endomorphisme d'un espace de dimension $d$ est annulé par un polynôme de degré $d$. Mais cette borne n'est pas toujours optimale.

On appelle polynôme minimal de $u$ un polynôme annulateur unitaire de plus petit degré ; on le note $\mu_u$.

16. La dimension réellement nécessaire

(a) Montrer que tout polynôme annulateur de $u$ est divisible par $\mu_u$. En déduire l'unicité de $\mu_u$.

(b) Déduire du théorème de Cayley-Hamilton que

$$\mu_u\mid\chi_u.$$

(c) Si $m=\deg\mu_u$, montrer que

$$\bigl(\operatorname{Id}_E,u,\ldots,u^{m-1}\bigr)$$

est une famille libre et qu'elle engendre tous les polynômes en $u$.

En notant

$$K[u]=\{P(u)\mid P\in K[X]\},$$

conclure que

$$\dim K[u]=\deg\mu_u.$$

(d) Sur $E=\mathbb R^2$, prendre

$$u=2\operatorname{Id}_E.$$

Déterminer $\chi_u$ et $\mu_u$, puis donner un troisième polynôme annulateur qui ne soit égal ni à l'un ni à l'autre.

(e) Expliquer précisément, dans cet exemple puis dans le cas général, la différence entre les trois expressions :

• « un polynôme annulateur » ;
• « le polynôme minimal » ;
• « le polynôme caractéristique ».