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

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

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

Les premiers couples sont

$$(x_0,y_0)=(1,0),\quad (x_1,y_1)=(2,1),\quad (x_2,y_2)=(5,3),\quad (x_3,y_3)=(13,8).$$

Pour $x_n$, on a

$$x_{n+2}=2x_{n+1}+y_{n+1}.$$

Or $y_{n+1}=x_n+y_n$ et $y_n=x_{n+1}-2x_n$. Ainsi

$$x_{n+2}=2x_{n+1}+x_n+x_{n+1}-2x_n=3x_{n+1}-x_n.$$

De même,

$$y_{n+2}=x_{n+1}+y_{n+1}.$$

Comme $x_{n+1}=2x_n+y_n$ et $x_n=y_{n+1}-y_n$, on obtient

$$y_{n+2}=3x_n+2y_n=3y_{n+1}-y_n.$$

Les deux suites vérifient donc

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

Une fois $z_0$ et $z_1$ connus, cette relation détermine successivement $z_2,z_3,\ldots$ ; une récurrence immédiate donne l'unicité de la suite correspondante.

IDÉEUne récurrence linéaire d'ordre 2 possède une mémoire de dimension 2 : deux termes consécutifs suffisent à déterminer toute la suite.

2. Changer de langage

On a

$$AU_n= \begin{pmatrix}2&1\\1&1\end{pmatrix} \begin{pmatrix}x_n\\y_n\end{pmatrix} = \begin{pmatrix}2x_n+y_n\\x_n+y_n\end{pmatrix} =U_{n+1}.$$

Ainsi $U_{n+1}=AU_n$. Par récurrence,

$$\boxed{U_n=A^nU_0.}$$

Le système de deux relations scalaires couplées devient une seule itération linéaire.

3. Toutes les puissances sont-elles vraiment nouvelles ?

On calcule

$$A^2= \begin{pmatrix}5&3\\3&2\end{pmatrix}.$$

Or

$$3A-I_2= \begin{pmatrix}5&3\\3&2\end{pmatrix}.$$

Donc

$$\boxed{A^2=3A-I_2.}$$

En multipliant par $A^n$,

$$\boxed{A^{n+2}=3A^{n+1}-A^n}$$

pour tout $n\geq0$.

4. Une compression explicite

On montre par récurrence que

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

Pour $n=1$, l'égalité est immédiate. Supposons-la vraie à l'indice $n$. Alors

$$\begin{aligned} A^{n+1} &=p_nA^2-p_{n-1}A\\ &=p_n(3A-I_2)-p_{n-1}A\\ &=(3p_n-p_{n-1})A-p_nI_2\\ &=p_{n+1}A-p_nI_2. \end{aligned}$$

Ainsi, pour tout $n\geq1$,

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

Comme $U_0=(1,0)^T$,

$$U_n=p_n\begin{pmatrix}2\\1\end{pmatrix}-p_{n-1}\begin{pmatrix}1\\0\end{pmatrix}.$$

D'où

$$\boxed{y_n=p_n,\qquad x_n=2p_n-p_{n-1}=p_{n+1}-p_n.}$$

Toutes les puissances de $A$ appartiennent à l'espace vectoriel engendré par $I_2$ et $A$.

5. Le phénomène en dimension 2

Pour

$$B=\begin{pmatrix}a&b\\c&d\end{pmatrix},$$

on a

$$B^2= \begin{pmatrix} a^2+bc&ab+bd\\ ac+cd&bc+d^2 \end{pmatrix}.$$

D'autre part, $(a+d)B-(ad-bc)I_2$ possède exactement les mêmes coefficients. Donc

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

En multipliant par $B^n$,

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

Si $V_n=B^nV_0$, alors

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

L'égalité étant vectorielle, chacune des coordonnées vérifie

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

Cette relation peut avoir un ordre effectif inférieur à 2 dans des cas particuliers, par exemple lorsque $B$ est une matrice scalaire.

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

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

Si

$$P(X)=\sum_i a_iX^i, \qquad Q(X)=\sum_j b_jX^j,$$

alors l'additivité est immédiate. Pour le produit,

$$P(u)\circ Q(u)=\sum_{i,j}a_ib_j u^{i+j}.$$

Les coefficients devant $u^k$ sont précisément ceux du produit $PQ$. Ainsi

$$\boxed{(PQ)(u)=P(u)\circ Q(u).}$$

Comme $PQ=QP$ dans $K[X]$,

$$P(u)Q(u)=Q(u)P(u).$$

IDÉEUne identité polynomiale peut être transportée vers un endomorphisme en remplaçant $X$ par $u$ ; les polynômes en un même endomorphisme commutent entre eux.

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

La relation de la première partie s'C�crit

$$A^2-3A+I_2=0,$$

c'est-à-dire $P(A)=0$ pour

$$P(X)=X^2-3X+1.$$

Si $P(u)=0$ et $Q\in K[X]$, alors

$$(QP)(u)=Q(u)P(u)=0.$$

Tout multiple d'un polynôme annulateur est donc encore annulateur.

Comme $\operatorname{End}(E)$ est de dimension $d^2$, la famille de $d^2+1$ endomorphismes

$$\operatorname{Id}_E,u,u^2,\ldots,u^{d^2}$$

est liée. Il existe donc des scalaires $a_0,\ldots,a_{d^2}$, non tous nuls, tels que

$$a_0\operatorname{Id}_E+a_1u+\cdots+a_{d^2}u^{d^2}=0.$$

Le polynôme

$$P(X)=a_0+a_1X+\cdots+a_{d^2}X^{d^2}$$

est non nul et vérifie $P(u)=0$.

Ainsi tout endomorphisme en dimension finie possède un polynôme annulateur. Cette preuve donne un annulateur de degré au plus $d^2$, mais elle ne fournit ni un polynôme privilégié ni une relation de degré $d$.

8. Réduire toutes les puissances

La division euclidienne donne

$$Q=SP+R, \qquad R=0\ \text{ou}\ \deg R<r.$$

En évaluant en $u$,

$$Q(u)=S(u)P(u)+R(u)=R(u),$$

car $P(u)=0$.

Il faut distinguer deux unicités : le reste $R$ est l'unique reste de la division euclidienne de $Q$ par le polynôme $P$ fixé ; si $P$ n'est pas minimal, il peut en revanche exister un autre polynôme de degré $<r$ qui prenne la même valeur en $u$.

En particulier, pour $Q=X^n$,

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

De plus,

$$P(u)=u^r+a_{r-1}u^{r-1}+\cdots+a_0\operatorname{Id}_E=0.$$

En multipliant par $u^n$,

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

Si $s_n=\ell(u^n(v))$, on applique cette égalité à $v$, puis la forme linéaire $\ell$. On obtient

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

IDÉEToute relation polynomiale satisfaite par un endomorphisme produit automatiquement des récurrences pour ses observations linéaires.

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

9. Le polynôme caractéristique

Si $A'=S^{-1}AS$, alors

$$XI_d-A'=S^{-1}(XI_d-A)S.$$

Par multiplicativité du déterminant,

$$\det(XI_d-A')=\det(S^{-1})\det(XI_d-A)\det(S)=\det(XI_d-A).$$

Le polynôme caractéristique ne dépend donc pas de la base choisie.

Dans le développement de $\det(XI_d-A)$, le terme de plus haut degré provient du produit des $d$ termes $X$ de la diagonale ; son coefficient vaut 1. Ainsi

$$\boxed{\chi_u\text{ est unitaire de degré }d.}$$

10. Retrouver la dimension 2

Pour

$$B=\begin{pmatrix}a&b\\c&d\end{pmatrix},$$

on a

$$\begin{aligned} \chi_B(X) &=(X-a)(X-d)-bc\\ &=X^2-(a+d)X+ad-bc. \end{aligned}$$

Donc

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

La relation de la question 5 est exactement $\chi_B(B)=0$ : le calcul direct en dimension 2 est un cas particulier du théorème général.

11. Ce que Cayley-Hamilton apporte

La division euclidienne donne

$$X^n=Q_n\chi_u+R_n, \qquad \deg R_n<d.$$

Comme $\chi_u(u)=0$,

$$\boxed{u^n=R_n(u).}$$

Ainsi

$$\boxed{u^n\in\operatorname{Vect}(\operatorname{Id}_E,u,\ldots,u^{d-1}).}$$

Si

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

Cayley-Hamilton donne

$$u^d+c_{d-1}u^{d-1}+\cdots+c_0\operatorname{Id}_E=0.$$

En multipliant par $u^n$,

$$\boxed{u^{n+d}+c_{d-1}u^{n+d-1}+\cdots+c_0u^n=0.}$$

La question 7 assurait seulement l'existence d'un annulateur de degré au plus $d^2$. Cayley-Hamilton fournit un annulateur canonique, construit à partir de $u$, unitaire et de degré exactement $d$.

12. Une puissance élevée sans diagonalisation

On calcule

$$XI_3-M= \begin{pmatrix} X&0&-1\\ -1&X&-1\\ 0&-1&X \end{pmatrix},$$

puis

$$\boxed{\chi_M(X)=X^3-X-1.}$$

Cayley-Hamilton donne

$$\boxed{M^3=M+I_3.}$$

Modulo $X^3-X-1$, on a $X^3\equiv X+1$, puis

$$X^5\equiv X^2+X+1.$$

Par exponentiation rapide,

$$X^{10}\equiv(X^2+X+1)^2\equiv4X^2+5X+3,$$

puis

$$X^{20}\equiv(4X^2+5X+3)^2.$$

En réduisant à nouveau avec $X^3\equiv X+1$ et $X^4\equiv X^2+X$,

$$\boxed{X^{20}\equiv65X^2+86X+49\pmod{X^3-X-1}.}$$

Donc

$$\boxed{M^{20}=65M^2+86M+49I_3.}$$

Or

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

Finalement,

$$\boxed{ M^{20}= \begin{pmatrix} 49&65&86\\ 86&114&151\\ 65&86&114 \end{pmatrix}.}$$

IDÉEPour calculer une grande puissance $A^n$, on peut calculer le reste de $X^n$ modulo un polynôme annulateur de $A$, puis remplacer $X$ par $A$.

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

13. Transformer une récurrence en dynamique matricielle

Pour $r=1$, la matrice compagnon se réduit à $C=(-a_0)$ et la vérification ci-dessous reste valable.

Par définition,

$$V_{n+1}= \begin{pmatrix} s_{n+1}\\s_{n+2}\\\vdots\\s_{n+r} \end{pmatrix}.$$

Les $r-1$ premières lignes de $CV_n$ décalent les coordonnées. La dernière vaut

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

par la relation de récurrence. Ainsi

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

Par récurrence,

$$\boxed{V_n=C^nV_0.}$$

La première coordonnée de $V_n$ vaut $s_n$, donc

$$\boxed{s_n=\pi_1(C^nV_0).}$$

La question 8 montre qu'une identité polynomiale satisfaite par une dynamique linéaire produit des suites récurrentes ; ici, réciproquement, toute suite satisfaisant une récurrence linéaire à coefficients constants devient l'observation d'une dynamique linéaire en dimension finie.

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

Avec $V_0\in K^d$, on a $V_n=A^nV_0$. Cayley-Hamilton donne

$$A^{n+d}+c_{d-1}A^{n+d-1}+\cdots+c_0A^n=0.$$

En appliquant cette égalité à $V_0$,

$$V_{n+d}+c_{d-1}V_{n+d-1}+\cdots+c_0V_n=0.$$

Chaque coordonnée, et plus généralement toute forme linéaire appliquée à cette relation, vérifie donc

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

Pour

$$A=\begin{pmatrix}2&1\\1&1\end{pmatrix},$$

on a

$$\chi_A(X)=X^2-3X+1.$$

On retrouve donc

$$\boxed{s_{n+2}=3s_{n+1}-s_n,}$$

ce qui redonne simultanément les récurrences de $x_n$ et de $y_n$.

15. Un autre observateur : la trace des puissances

En prenant la trace dans

$$A^{n+d}+c_{d-1}A^{n+d-1}+\cdots+c_0A^n=0,$$

et en utilisant la linéarité de la trace, on obtient

$$\boxed{t_{n+d}+c_{d-1}t_{n+d-1}+\cdots+c_0t_n=0.}$$

On peut lire ce résultat dans l'espace vectoriel $M_d(K)$ : l'application $B\mapsto\operatorname{tr}(B)$ est une forme linéaire. De la même manière, chaque coefficient $(A^n)_{ij}$ satisfait une récurrence issue de $\chi_A$.

IDÉESuites récurrentes linéaires et itérations linéaires en dimension finie sont deux façons de décrire le même mécanisme : un état de dimension finie évolue linéairement, et toute observation linéaire de cet état satisfait une récurrence.

V — Jusqu'où peut-on comprimer ?

16. La dimension réellement nécessaire

Soit $\mu_u$ un polynôme annulateur unitaire de degré minimal. Si $P$ est un autre polynôme annulateur, effectuons la division euclidienne

$$P=Q\mu_u+R, \qquad \deg R<\deg\mu_u.$$

En évaluant en $u$,

$$0=P(u)=Q(u)\mu_u(u)+R(u)=R(u).$$

Si $R\neq0$, il serait un annulateur de degré strictement inférieur à celui de $\mu_u$, contradiction. Ainsi $R=0$, donc

$$\boxed{\mu_u\mid P.}$$

Si deux polynômes unitaires de degré minimal existaient, chacun diviserait l'autre ; ils seraient donc égaux. Le polynôme minimal est unique.

Comme $\chi_u$ est annulateur par Cayley-Hamilton,

$$\boxed{\mu_u\mid\chi_u.}$$

Posons $m=\deg\mu_u$. Supposons qu'il existe une relation

$$a_0I+a_1u+\cdots+a_{m-1}u^{m-1}=0$$

avec des coefficients non tous nuls. Le polynôme correspondant serait un annulateur non nul de degré strictement inférieur à $m$, contradiction. La famille

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

est donc libre.

Par ailleurs, la division de tout $P\in K[X]$ par $\mu_u$ donne un reste de degré $<m$, donc tout $P(u)$ appartient à l'espace engendré par cette famille. Ainsi

$$\boxed{(\operatorname{Id}_E,u,\ldots,u^{m-1})\text{ est une base de }K[u]}$$

et

$$\boxed{\dim K[u]=\deg\mu_u.}$$

Pour $u=2I_E$ sur $E=\mathbb R^2$,

$$\chi_u(X)=(X-2)^2,$$

alors que

$$\mu_u(X)=X-2.$$

Par exemple,

$$P(X)=(X-2)(X+1)$$

est également annulateur, puisqu'il est multiple de $\mu_u$.

On distingue donc :

• un polynôme annulateur : tout polynôme non nul $P$ tel que $P(u)=0$.
• le polynôme minimal : l'unique annulateur unitaire de plus petit degré ; il divise tout polynôme annulateur.
• le polynôme caractéristique : $\det(XI-A)$, polynôme canonique unitaire de degré $\dim E$, qui annule $u$ par Cayley-Hamilton.

Ils ne coïncident pas en général.

IDÉEL'espace $K[u]$ contient toutes les puissances de $u$ et sa dimension est exactement $\deg\mu_u$. Cayley-Hamilton donne en particulier $\dim K[u]\leq\dim E$.

Pour approfondir

[SOURCE] Agrégation interne de mathématiques 2025, première épreuve : exercice préliminaire 1, questions 1 à 4, puis partie III, questions 14 à 17 — prolongements des parties II, IV et V. Sujet officiel

[SOURCE] Agrégation interne de mathématiques 2022, première épreuve : exercice préliminaire, questions 2 et 3 — matrice compagnon et démonstration de Cayley-Hamilton, en prolongement des parties III et IV. Sujet officiel