École AVOSZ

Connectez-vous

085. Maîtrisez le calcul du polynôme caractéristique avec la méthode de Faddeev

Yannis TRIANTAPHYLIDES

Cet article détaille une application des sommes de Newton qui ont été présentées dans l’article précédent.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 084.

L’objectif principal du présent document est de construire un algorithme qui calcule, petit à petit, les coefficients du polynôme caractéristique d’une matrice $A\comma$ à coefficients dans un corps $\K$ de caractéristique nulle.

L’organisation est découpée en quatre parties.

Tout d’abord, le cas où $A$ est une matrice carrée d’ordre $2\comma$ triangulaire supérieure, est traité. Puis vous passerez au cas où la matrice $A$ est carrée d’ordre $3\comma$ en étant triangulaire supérieure. Dans la troisième partie, $n$ désigne un entier naturel non nul. Le cas où la matrice $A$ est carrée d’ordre $n$ et triangulaire supérieure généralise les deux parties précédentes. Dans la dernière partie, un argument supplémentaire sera mis en avant et permettra de conclure pour toutes les matrices carrées d’ordre non nul.

Première partie : la méthode dans le cas où la matrice $A$ est carrée d’ordre $2$ et est triangulaire supérieure

Introduisez des notations

Soit $A$ une matrice carrée d’ordre $2$ à coefficients dans $\K$ et qui soit triangulaire supérieure. Notez $\lambda_1$ et $\lambda_2$ les coefficients diagonaux de $A.$ Vous avez :

A = \begin{pmatrix} \lambda_1 & \ast \\ 0 & \lambda_2 \end{pmatrix}.

Soit $I_2$ la matrice identité d’ordre $2.$ Notez $P$ le polynôme caractéristique de $A.$ Il est égal à :

P(X) = \det(XI_2-A) = (X-\lambda_1)(X-\lambda_2).

En développant ce polynôme, vous constatez qu’il existe deux éléments de $\K\comma$ notés $\alpha_1$ et $\alpha_2\comma$ tels que :

P(X)=X^2+\alpha_1X+\alpha_2.

Vous introduisez les sommes de Newton, qui sont définies par :

\left\{\begin{align*} N_1 &= \lambda_1+\lambda_2\\ N_2 &= \lambda_1^2+\lambda_2^2. \end{align*} \right.

Il a été vu dans l’article précédent qu’elles vérifient les relations suivantes :

\left\{\begin{align*} &N_1+\alpha_1 = 0\\ &N_2+\alpha_1N_1+2\alpha_2 = 0. \end{align*} \right.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 084.

Calculez les coefficients du polynôme $P$ avec la trace

Vu l’expression de la matrice $A\comma$ vous avez $\tr(A)=N_1.$ Compte tenu de la relation $N_1+\alpha_1 = 0\comma$ vous avez :

\alpha_1 = -\tr(A).

Pour la suite, vous considérez les coefficients diagonaux de la matrice $A(A+\alpha_1I_2)\comma$ vous obtenez :

\begin{align*}A(A+\alpha_1 I_2) &= \begin{pmatrix} \lambda_1 & \ast \\ 0 & \lambda_2\end{pmatrix}\begin{pmatrix} \lambda_1+\alpha_1 & \ast \\ 0 & \lambda_2+\alpha_1\end{pmatrix} \\ &=\begin{pmatrix} \lambda_1(\lambda_1+\alpha_1) & \ast \\ 0 & \lambda_2(\lambda_2+\alpha_1)\end{pmatrix} \\ &=\begin{pmatrix} \lambda_1^2+\alpha_1\lambda_1 & \ast \\ 0 & \lambda_2^2+\alpha_1\lambda_2\end{pmatrix}. \end{align*}

En sommant les coefficients diagonaux, vous obtenez :

\tr\bigl(A(A+\alpha_1I_2)\bigr)=N_2+\alpha_1N_1.

Or, $N_2+\alpha_1N_1+2\alpha_2 = 0\comma$ ce qui produit :

\tr\bigl(A(A+\alpha_1I_2)\bigr)=-2\alpha_2.

Vous avez finalement obtenu ce qui suit :

\boxed{\left\{\begin{align*} \alpha_1 &= -\tr(A)\\ \alpha_2 &= -\frac{1}{2}\tr\bigl(A(A+\alpha_1I_2)\bigr). \end{align*}\right. }

Deuxième partie : la méthode dans le cas où $A$ est carrée d’ordre $3$ et est triangulaire supérieure

Soit $A$ une matrice carrée d’ordre $3$ à coefficients dans $\K$ et qui soit triangulaire supérieure. Notez $\lambda_1\comma$ $\lambda_2$ et $\lambda_3$ les coefficients diagonaux de $A.$ Vous avez :

A = \begin{pmatrix} \lambda_1 & \ast & \ast \\ 0 & \lambda_2 & \ast \\ 0 & 0 & \lambda_3 \end{pmatrix}.

Soit $I_3$ la matrice identité d’ordre $3.$ Notez $P$ le polynôme caractéristique de $A.$ Il est égal à :

P(X) = \det(XI_3-A) = (X-\lambda_1)(X-\lambda_2)(X-\lambda_3).

En développant ce polynôme, vous constatez qu’il existe trois éléments de $\K\comma$ notés $\alpha_1\comma$ $\alpha_2$ et $\alpha_3\comma$ tels que :

P(X)=X^3+\alpha_1X^2+\alpha_2X+\alpha_3.

Les sommes de Newton sont définies par :

\left\{\begin{align*} N_1 &= \lambda_1+\lambda_2+\lambda_3\\ N_2 &= \lambda_1^2+\lambda_2^2+\lambda_3^2\\ N_3 &= \lambda_1^3+\lambda_2^3+\lambda_3^3. \end{align*} \right.

Elles vérifient les relations suivantes :

\left\{\begin{align*} &N_1+\alpha_1 = 0\\ &N_2+\alpha_1N_1+2\alpha_2 = 0\\ &N_3+\alpha_1N_2+\alpha_2N_1+3\alpha_3 = 0. \end{align*} \right.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 084.

Utilisez la trace

Comme précédemment, vous avez $\tr(A) = N_1 = -\alpha_1.$ Soit :

\alpha_1 = -\tr(A).

De même :

\begin{align*} A(A+\alpha_1I_3) &= \begin{pmatrix} \lambda_1 & \ast & \ast \\ 0 & \lambda_2 & \ast \\ 0 & 0 & \lambda_3 \end{pmatrix}\begin{pmatrix} \lambda_1+\alpha_1 & \ast & \ast \\ 0 & \lambda_2+\alpha_1 & \ast \\ 0 & 0 & \lambda_3+\alpha_1 \end{pmatrix}\\ &= \begin{pmatrix} \lambda_1(\lambda_1+\alpha_1) & \ast & \ast \\ 0 & \lambda_2(\lambda_2+\alpha_1) & \ast \\ 0 & 0 & \lambda_3(\lambda_3+\alpha_1) \end{pmatrix} \\ &= \begin{pmatrix} \lambda_1^2+\alpha_1\lambda_1 & \ast & \ast \\ 0 & \lambda_2^2+\alpha_1\lambda_2 & \ast \\ 0 & 0 & \lambda_3^2+\alpha_1\lambda_3 \end{pmatrix}. \end{align*}

Ainsi, $\tr\bigl(A(A+\alpha_1I_3\bigr) =N_2+\alpha_1N_1 = -2\alpha_2.$ Vous avez encore :

\alpha_2 = -\frac{1}{2}\tr\bigl(A(A+\alpha_1I_3)\bigr).

Vous utilisez le même processus :

A(A+\alpha_1I_3) + \alpha_2 I_3 = \begin{pmatrix} \lambda_1^2+\alpha_1\lambda_1 +\alpha_2& \ast & \ast \\ 0 & \lambda_2^2+\alpha_1\lambda_2 +\alpha_2& \ast \\ 0 & 0 & \lambda_3^2+\alpha_1\lambda_3 +\alpha_2\end{pmatrix}.

Par multiplication des coefficients diagonaux de deux matrices triangulaires supérieures, il vient :

A\bigl(A(A+\alpha_1I_3) + \alpha_2 I_3\bigr) = \begin{pmatrix} \lambda_1^3+\alpha_1\lambda_1^2 +\alpha_2\lambda_1& \ast & \ast \\ 0 & \lambda_2^3+\alpha_1\lambda_2^2 +\alpha_2\lambda_2& \ast \\ 0 & 0 & \lambda_3^3+\alpha_1\lambda_3^2 +\alpha_2\lambda_3\end{pmatrix}.

En prenant à nouveau la trace, vous avez :

\tr\bigl(A(A(A+\alpha_1I_3)+\alpha_2I_3 )\bigr) = N_3+\alpha_1N_2+\alpha_2N_1 = -3\alpha_3.

Ainsi :

\alpha_3 = -\frac{1}{3}\tr\bigl(A(A(A+\alpha_1I_3)+\alpha_2I_3 )\bigr).

Utilisez des notations adaptées

Les parenthèses commencent à s’enchaîner. Plutôt que de les combiner, vous allez présenter les calculs en utilisant une suite de matrices. Les coefficients du polynôme caractéristique de la matrice $A$ se calculent comme suit.

Vous posez $A_1=A\comma$ vous avez $\alpha_1 = -\tr(A_1).$

Puis vous posez $A_2 = A(A_1+\alpha_1I_3).$ Vous obtenez $\alpha_2 = -\frac{1}{2}\tr(A_2).$

Enfin, vous posez $A_3 = A(A_2+\alpha_2I_3)\comma$ il vient $\alpha_3 = -\frac{1}{3}\tr(A_3).$

Troisième partie : la méthode dans le cas où $A$ est triangulaire supérieure, carrée d’ordre $n$ avec $n$ un entier naturel non nul

Soit $n$ un entier naturel non nul. Soit $A$ une matrice à coefficients dans $\K$ qui soit triangulaire supérieure et carrée d’ordre $n.$ Vous notez $I_n$ la matrice identité d’ordre $n.$

Définissez deux suites

Vous définissez la suite finie $(A_i)_{1\leq i\leq n}$ de matrices et la suite finie $(\beta_i)_{1\leq i \leq n}$ d’éléments de $\K$ de la façon suivante.

Vous partez avec $A_0 = 0$ et $\beta_0=1.$ Puis, pour tout entier $i$ appartenant à l’intervalle $\llbracket 1, n\rrbracket\comma$ vous posez :

\left\{\begin{align*} A_i &= A(A_{i-1} +\beta_{i-1}I_n )\\ \beta_i &= -\frac{1}{i}\tr(A_i). \end{align*} \right.

Notez que vous avez bien $A_1 = A$ et $\beta_1 = -\tr(A_1)\comma$ conformément aux études précédentes.

Notez $\lambda_1, \dots,\lambda_n$ les coefficients diagonaux de la matrice $A.$ Ainsi :

A=\begin{pmatrix} \lambda_1 & \ast & \cdots & \ast \\ 0 & \lambda_2 & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ast \\ 0 & \cdots & 0 & \lambda_n \end{pmatrix}.

Le polynôme caractéristique de la matrice $A$ est égal à :

P(X)=\det(XI_n-A)=\prod_{i=1}^n (X-\lambda_i).

Il existe $n$ scalaires $\alpha_1,\dots,\alpha_n$ tels que :

P(X)=X^n+\sum_{i=1}^n\alpha_ix^{n-i}.

Les $n$ sommes de Newton sont définies, pour tout entier $k$ appartenant à l’intervalle $\llbracket 1, n\rrbracket\comma$ par :

N_k = \sum_{i=1}^n \lambda_i^k.

Pour tout entier $k$ compris entre $1$ et $n\comma$ vous avez les $n$ relations suivantes :

\sum_{i=0}^{k-1} \alpha_iN_{k-i} + k\alpha_k=0.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 084.

Effectuez une récurrence forte et limitée

Pour tout entier naturel $k$ appartenant à l’intervalle $\llbracket 1, n\rrbracket\comma$ notez $\mathscr{P}(k)$ la propriété stipulant que $\alpha_k = \beta_k$ et que, pour tout $j$ appartenant à l’intervalle $\llbracket 1, n\rrbracket\comma$ le coefficient diagonal situé à la ligne $j$ et à la colonne $j$ de la matrice $A_k$ est égal à $\sum_{i=0}^{k-1}\beta_i\lambda_j^{k-i}.$

Initialisation. Pour $k=1\comma$ vous prenez la première relation de Newton. Donc $N_1+\alpha_1=0.$

Or, $A_1 = A$ et $\beta_1 = -\tr(A_1)$ donc :

\beta_1 = -\tr(A) =- \sum_{i=1}^n \lambda_i = -N_1 = -(-\alpha_1) = \alpha_1.

Soit $j$ un entier appartenant à l’intervalle $\llbracket 1, n\rrbracket.$ Comme $A_1 = A\comma$ le coefficient diagonal situé à la ligne $j$ et à la colonne $j$ de $A_1$ est le même que celui situé à la ligne $j$ et à la colonne $j$ de $A$ qui est :

\lambda_j =\beta_0 \lambda_j=\sum_{i=0}^{0}\beta_i\lambda_j^{1-i}.

La propriété $\mathscr{P}(1)$ est vérifiée.

Hérédité. Soit $k$ un entier compris appartenant à l’intervalle $\llbracket 1, n-1\rrbracket.$ Supposez que les propriétés $\mathscr{P}(1),\dots, \mathscr{P}(k)$ soient vérifiées.

D’une part, vous avez la relation de Newton :

\sum_{i=0}^{k} \alpha_iN_{k+1-i} + (k+1)\alpha_{k+1}=0.

D’après l’hypothèse de récurrence :

\sum_{i=0}^{k} \beta_iN_{k+1-i} + (k+1)\alpha_{k+1}=0.

D’autre part, $A_{k+1} = A(A_{k} +\beta_{k}I_n ).$

Soit $j$ un entier appartenant à l’intervalle $\llbracket 1, n\rrbracket.$ La matrice $A_k + \beta_k I_n$ est triangulaire supérieure, son coefficient diagonal situé à la ligne $j$ et à la colonne $j$ est, d’après l’hypothèse de récurrence $\sum_{i=0}^{k-1}\beta_i\lambda_j^{k-i}$ augmenté de $\beta_k$ soit :

\sum_{i=0}^{k-1}\beta_i\lambda_j^{k-i} + \beta_k.

Les deux matrices $A$ et $A_k + \beta_k I_n$ étant triangulaires supérieures, le coefficient diagonal situé à la ligne $j$ et à la colonne $j$ de la matrice $A_{k+1}$ est égal à $\lambda_j$ multiplié par $\sum_{i=0}^{k-1}\beta_i\lambda_j^{k-i} + \beta_k\comma$ soit :

\begin{align*} \lambda_j\left(\sum_{i=0}^{k-1}\beta_i\lambda_j^{k-i} + \beta_k\right) &= \sum_{i=0}^{k-1}\beta_i\lambda_j^{k+1-i} + \beta_k\lambda_j\\ &= \sum_{i=0}^{k}\beta_i\lambda_j^{k+1-i}. \end{align*}

Calculez maintenant la trace de la matrice $A_{k+1}.$ Vous obtenez :

\begin{align*} \tr(A_{k+1}) &= \sum_{j=1}^n \sum_{i=0}^{k}\beta_i\lambda_j^{k+1-i}\\ &= \sum_{i=0}^{k} \sum_{j=1}^n\beta_i\lambda_j^{k+1-i}\\ &= \sum_{i=0}^{k}\left(\beta_i \sum_{j=1}^n\lambda_j^{k+1-i}\right)\\ &=\sum_{i=0}^{k} \beta_i N_{k+1-i}\\ &=-(k+1)\alpha_{k+1}. \end{align*}

Or $\beta_{k+1}=-\frac{1}{k+1}\tr(A_{k+1})\comma$ du coup, il vient $\alpha_{k+1}=\beta_{k+1}.$

La propriété $\mathscr{P}(k+1)$ est vérifiée.

Conclusion. Par récurrence, vous venez de démontrer que, pour tout $k$ compris entre $1$ et $n\comma$ les scalaires $\alpha_k$ et $\beta_k$ sont égaux.

Quatrième partie : traitez le cas général

Vous avez établi un lemme

Soient $n$ un entier naturel non nul, $\K$ un corps de caractéristique nulle et $I_n$ la matrice identité d’ordre $n.$

Pour toute matrice $A$ carrée d’ordre $n$ triangulaire supérieure à coefficients dans $\K\comma$ vous posez $A_0 = 0$ et $\beta_0=1.$

Pour tout $i$ compris entre $1$ et $n$, vous définissez une matrice notée $A_i$ et un élément de $\K$ noté $\beta_i\comma$ tels que $A_i = A(A_{i-1} +\beta_{i-1}I_n )$ et $\beta_i = -\frac{1}{i}\tr(A_i).$

Le polynôme caractéristique de la matrice $A$ est égal à :

P(X)=\det(XI_n-A)=\sum_{i=0}^n\beta_ix^{n-i}.

Passez au cas général

Soit $n$ un entier naturel non nul. Soient $A$ une matrice carrée d’ordre $n$ à coefficients dans un corps de caractéristique nulle, et $I_n$ la matrice identité d’ordre $n.$

Ce corps est contenu dans un corps de rupture $\K$ du polynôme caractéristique de la matrice $A\comma$ qui est aussi de caractéristique nulle. En tant que polynôme de $\K[X]\comma$ le polynôme caractéristique de $A$ est scindé.

Via le critère de trigonalisation, il existe une matrice inversible $Q$ à coefficients dans $\K$ telle que $Q^{-1}AQ = T$ où $T$ est une matrice triangulaire supérieure à coefficients dans $\K.$

Vous appliquez le lemme précédent à la matrice $T.$

Vous posez $T_0 = 0$ et $\beta_0=1.$

Pour tout $i$ compris entre $1$ et $n\comma$ vous définissez $T_i = T(T_{i-1} +\beta_{i-1}I _n)$ et $\beta_i = -\frac{1}{i}\tr(T_i).$

Alors, le polynôme caractéristique de la matrice $T$ est égal à $\sum_{i=0}^n\beta_iX^{n-i}.$

Comme les matrices $T$ et $A$ sont semblables, elles ont le même polynôme caractéristique. Il reste à voir pourquoi, si vous appliquez l’algorithme du lemme directement sur la matrice $A\comma$ vous trouvez encore le même polynôme.

Vous posez $A_0 = 0$ et $\gamma_0=1.$

Pour tout $i$ compris entre $1$ et $n$, définissez $A_i = A(A_{i-1} +\gamma_{i-1}I )$ et $\gamma_i = -\frac{1}{i}\tr(A_i).$

Vous allez montrer par récurrence limitée que les nombres $\gamma_i$ et $\beta_i$ sont égaux.

Pour tout $i$ appartenant à l’intervalle $\llbracket 0, n\rrbracket\comma$ vous notez $\mathscr{Q}(i)$ la propriété stipulant que $\gamma_i = \beta_i$ et que $Q^{-1}A_iQ = T_i.$

Initialisation. pour $i=0\comma$ $\gamma_0=1$ et $\beta_0=1.$ Comme $A_0 = T_0 = 0\comma$ vous avez $Q^{-1}A_0Q=T_0\comma$ donc $\mathscr{Q}(0)$ est vérifiée.

Hérédité. Soit $i$ un entier appartenant à l’intervalle $\llbracket 0, n-1\rrbracket.$ Vous supposez que $\mathscr{Q}(i)$ est vérifiée.

D’une part :

\begin{align*} Q^{-1}A_{i+1}Q &= Q^{-1} A(A_{i} +\gamma_{i}I_n )Q\\ &=Q^{-1} A(A_{i} +\beta_{i}I_n )Q\\ &=(Q^{-1} AQ)(Q^{-1}(A_{i} +\beta_{i}I_n )Q)\\ &=T(Q^{-1}(A_{i} +\beta_{i}I )Q)\\ &=T(Q^{-1}A_iQ+\beta_i Q^{-1}I_nQ)\\ &=T(T_i+\beta_iI_n)\\ &=T_{i+1}. \end{align*}

D’autre part :

\begin{align*} \beta_{i+1} &=-\frac{1}{i+1}\tr(T_{i+1})\\ &=-\frac{1}{i+1}\tr(Q^{-1}A_{i+1}Q)\\ &=-\frac{1}{i+1}\tr\bigl(Q^{-1}(A_{i+1}Q)\bigr)\\ &=-\frac{1}{i+1}\tr\bigl((A_{i+1}Q)Q^{-1}\bigr)\\ &=-\frac{1}{i+1}\tr\bigl(A_{i+1}(QQ^{-1})\bigr)\\ &=-\frac{1}{i+1}\tr(A_{i+1}I_n)\\ &=-\frac{1}{i+1}\tr(A_{i+1})\\ &=\gamma_{i+1}. \end{align*}

Donc la propriété $\mathscr{Q}(i+1)$ est vérifiée.

Conclusion. Vous avez montré par récurrence que, pour tout entier $i$ appartenant à l’intervalle $\llbracket 0, n\rrbracket\comma$ les coefficients $\gamma_i$ et $\beta_i$ sont égaux.

Donc le polynôme caractéristique $P$ de la matrice $A$ est égal à :

P(X)=\sum_{i=0}^n\gamma_i X^{n-i}.

Concluez

Pour tout entier naturel $n\geq 1\comma$ pour toute matrice $A$ carrée d’ordre $n$ à coefficients dans un corps de caractéristique nulle, vous posez $A_0 = 0$ et $\alpha_0=1.$ La notation $I_n$ désigne la matrice identité d’ordre $n.$

Pour tout $i$ compris entre $1$ et $n\comma$ vous posez :

\left\{\begin{align*} A_i &= A(A_{i-1} +\alpha_{i-1}I_n )\\ \alpha_i &= -\frac{1}{i}\tr(A_i). \end{align*} \right.

Alors, le polynôme caractéristique de la matrice $A$ est égal à :

P(X)= \sum_{i=0}^n\alpha_iX^{n-i}.

Ce processus est appelé méthode de Faddeev.