Votre navigateur n'accepte pas le Javascript. La navigation sur ce site risque de ne pas fonctionner correctement.

085. Le polynôme caractéristique par la méthode de Faddeev

Vous allez voir une belle application des sommes de Newton vues dans l’article précédent. Toutes les matrices considérées seront à coefficients dans un corps de caractéristique nulle.

Le but de cette section est de construire un algorithme qui calcule petit à petit les coefficients du polynôme caractéristique d’une matrice $A$.

Vous découvrirez le lien entre la trace, les racines d’un polynôme, le polynôme caractéristique d’une matrice, avec effet graduel :

  • dans le cas où $A$ est une matrice carrée d’ordre $2$ triangulaire supérieure,
  • dans le cas où $A$ est une matrice carrée d’ordre $3$ triangulaire supérieure,
  • dans le cas où $A$ est une matrice carrée d’ordre $n\geq 1$ triangulaire supérieure,
  • dans le cas général, $A$ étant une matrice carrée d’ordre $n\geq 1.$

La méthode dans le cas où $A$ est carrée d’ordre $2$ et triangulaire supérieure

Les notations

Pour bien comprendre, vous allez supposer que la matrice $A$ est triangulaire supérieure. Notez $\lambda_1$ et $\lambda_2$ les coefficients diagonaux de $A$.

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

Notez $P$ le polynôme caractéristique de $A$, défini par $P(x) = \det(xI-A) = (x-\lambda_1)(x-\lambda_2).$

En développant ce polynôme, il existe deux scalaires $\alpha_1$ et $\alpha_2$ tels que $P(x)=x^2+\alpha_1x+\alpha_2.$

Les sommes de Newton sont définies par :

$N_1 = \lambda_1+\lambda_2$

$N_2 = \lambda_1^2+\lambda_2^2$

et elles vérifient les relations fondamentales :

$N_1+\alpha_1 = 0$

$N_2+\alpha_1N_1+2\alpha_2 = 0.$

Le calcul des coefficients avec la trace

Prenez la première relation $N_1+\alpha_1 = 0$.

Comment obtenir $N_1$ ?

Vu l’expression de la matrice $A$ :

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

Vous avez immédiatement $\tr(A) = N_1$. Par conséquent, $\alpha_1 = -\tr(A).$

Prenez la seconde relation $N_2+\alpha_1N_1+2\alpha_2 = 0.$

Considérez les coefficients diagonaux de la matrice $A(A+\alpha_1I) :$

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

Aussitôt : $\tr(A(A+\alpha_1I))=N_2+\alpha_1N_1=-2\alpha_2$

Vous en déduisez que :

$\left\{\begin{align*}
\alpha_1 &= -\tr(A)\\
\alpha_2 &= -\dfrac{1}{2}\tr(A(A+\alpha_1I)).
\end{align*}\right.$

La méthode dans le cas où $A$ est carrée d’ordre $3$ et triangulaire supérieure

Dans ce cas là il y a un coefficient de plus sur la diagonale principale. Notez $\lambda_1$, $\lambda_2$ et $\lambda_3$ les coefficients diagonaux de $A$.

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

Notez $P$ le polynôme caractéristique de $A$, défini par $P(x) = \det(xI-A) = (x-\lambda_1)(x-\lambda_2)(x-\lambda_3).$

En développant ce polynôme, il existe trois scalaires $\alpha_1$, $\alpha_2$ et $\alpha_3$ tels que $P(x)=x^3+\alpha_1x^2+\alpha_2x+\alpha_3.$

Les sommes de Newton sont définies par :

$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$

et elles vérifient les relations fondamentales :

$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.$

Appliquez la trace sur des matrices bien choisies

Comme $A = \begin{pmatrix} \lambda_1 & \times & \times \\ 0 & \lambda_2 & \times \\ 0 & 0 & \lambda_3 \end{pmatrix},$ vous tirez $\tr(A) = N_1 = -\alpha_1$, du coup $\alpha_1 = -\tr(A).$

De même :

$\begin{align*}
A(A+\alpha_1I) &= \begin{pmatrix} \lambda_1 & \times & \times \\ 0 & \lambda_2 & \times \\ 0 & 0 & \lambda_3 \end{pmatrix}\begin{pmatrix} \lambda_1+\alpha_1 & \times & \times \\ 0 & \lambda_2+\alpha_1 & \times \\ 0 & 0 & \lambda_3+\alpha_1 \end{pmatrix}\\
&= \begin{pmatrix} \lambda_1(\lambda_1+\alpha_1) & \times & \times \\ 0 & \lambda_2(\lambda_2+\alpha_1) & \times \\ 0 & 0 & \lambda_3(\lambda_3+\alpha_1) \end{pmatrix} \\
&= \begin{pmatrix} \lambda_1^2+\alpha_1\lambda_1 & \times & \times \\ 0 & \lambda_2^2+\alpha_1\lambda_2 & \times \\ 0 & 0 & \lambda_3^2+\alpha_1\lambda_3 \end{pmatrix} \\
\end{align*}$

Aussitôt, pas de souci, $\tr(A(A+\alpha_1I) =N_2+\alpha_1N_1 = -2\alpha_2$ et par suite, vous avez encore $\alpha_2=-\dfrac{1}{2}\tr(A(A+\alpha_1I)).$

Maintenant que $\alpha_2$ est calculé :

$A(A+\alpha_1I) + \alpha_2 I = \begin{pmatrix} \lambda_1^2+\alpha_1\lambda_1 +\alpha_2& \times & \times \\ 0 & \lambda_2^2+\alpha_1\lambda_2 +\alpha_2& \times \\ 0 & 0 & \lambda_3^2+\alpha_1\lambda_3 +\alpha_2\end{pmatrix} $

et donc

$A(A(A+\alpha_1I) + \alpha_2 I) = \begin{pmatrix} \lambda_1^3+\alpha_1\lambda_1^2 +\alpha_2\lambda_1& \times & \times \\ 0 & \lambda_2^3+\alpha_1\lambda_2^2 +\alpha_2\lambda_2& \times \\ 0 & 0 & \lambda_3^3+\alpha_1\lambda_3^2 +\alpha_2\lambda_3\end{pmatrix}$

Vous reprenez la trace.

$\tr( A(A(A+\alpha_1I)+\alpha_2I )) = N_3+\alpha_1N_2+\alpha_2N_1 = -3\alpha_3$, du coup :

$\alpha_3 = -\dfrac{1}{3}\tr(A(A(A+\alpha_1I)+\alpha_2I )).$

Utilisez des notations adaptées

Les parenthèses commencent à s’enchaîner. Plutôt que de les combiner, vous allez définir une suite de matrices et de scalaires.

Posez $A_1 = A$ et $\beta_1 = -\tr(A_1)$,

$A_2 = A(A_1+\beta_1I)$ et $\beta_2 = -\dfrac{1}{2}\tr(A_2)$ et

$A_3 = A(A_2+\beta_2I)$ et $\beta_3 = -\dfrac{1}{3}\tr(A_3).$

Alors il est établi que pour tout entier naturel $i$ compris entre $1$ et $3$, $\beta_i = \alpha_i$ et le polynôme caractéristique de $A$ est égal à $x^3+\beta_1x^2+\beta_2x+\beta_3.$

Et maintenant, la démonstration dans le cas où la matrice $A$ est carrée d’ordre $n\geq 1$, triangulaire supérieure

La situation

Soit $n$ un entier naturel non nul.

Soit $A$ une matrice carrée d’ordre $n$ triangulaire supérieure.

On définit la suite finie $(A_i)_{1\leq i\leq n}$ de matrices et la suite finie $(\beta_i)_{1\leq i \leq n}$ de scalaires de la façon suivante.

On pose artificiellement $A_0 = 0$ et $\beta_0=1.$

Pour tout $i$ compris entre $1$ et $n$, $A_i = A(A_{i-1} +\beta_{i-1}I )$ et $\beta_i = -\dfrac{1}{i}\tr(A_i).$

Notez qu’on a bien $A_1 = A$ et $\beta_1 = -\tr(A_1)$ ce qui justifie a posteriori le fait de poser $A_0=0$ et $\beta_0=1.$

Notez $\lambda_1$, …, $\lambda_n$ les coefficients diagonaux de la matrice $A$.

$A = \begin{pmatrix}
\lambda_1 & \times & \times \\
0 & \cdots & \times\\
0 & 0 & \lambda_n
\end{pmatrix}$

Notez $P(x)=\det(xI-A)=\Pi_{i=1}^n (x-\lambda_i)$ le polynôme caractéristique de $A$. En le développant, il existe $n$ scalaires $\alpha_1$, …, $\alpha_n$ tels que $P(x) = x^n+\alpha_1x^{n-1}+\cdots + \alpha_{n-1}x+\alpha_n.$ Posez $\alpha_0 = 1$. De façon plus formelle, $P(x)=\sum_{i=0}^n\alpha_ix^{n-i}.$

Vous définissez $n$ sommes de Newton en posant, pour tout entier $k$ compris entre $1$ et $n$, $N_k = \sum_{i=1}^n \lambda_i^k.$

Pour tout entier $k$ compris entre $1$ et $n$, vous avez les $n$ relations de Newton :

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

Effectuez une récurrence limitée

Pour tout entier naturel $k$ compris entre $1$ et $n$, notez $Q(k)$ la propriété : “$\alpha_k = \beta_k$ et pour tout $j$ compris entre $1$ et $n$, 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 : $k=1$. Prenez la première relation de Newton. $N_1+\alpha_1=0.$

Il a été vu ci-dessus que $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 compris entre $1$ et $n$. Comme $A_1 = A$, 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}$, donc la propriété $Q(1)$ est vérifiée.

Hérédité. Soit $k$ un entier compris entre $1$ et $n-1$. Supposez $Q(1)$, …, $Q(k)$ et montrez $Q(k+1)$.

D’une part, on a 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, celle-ci s’écrit :

$\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 ).$

Soit $j$ un entier compris entre $1$ et $n$. La matrice $A_k + \beta_k I$ 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$ étant triangulaires supérieures, le coefficient diagonal situé à la ligne $j$ et à la colonne $j$ de $A_{k+1}$ est égal à $\lambda_j$ multiplié par $\sum_{i=0}^{k-1}\beta_i\lambda_j^{k-i} + \beta_k$, 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 $A_{k+1}$.

$\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}=-\dfrac{1}{k+1}\tr(A_{k+1})$, il vient aussitôt $\alpha_{k+1}=\beta_{k+1}.$

La propriété $Q(k+1)$ est vérifiée.

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

Et maintenant, le cas général

Vous avez établi un lemme que vous pouvez généraliser

Pour toute matrice $A$ carrée d’ordre $n$ triangulaire supérieure à coefficients dans un corps de caractéristique nulle, vous posez $A_0 = 0$ et $\beta_0=1.$

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

Alors le polynôme caractéristique de $A$ défini par $P(x)=\det(xI-A)$ est égal à $\sum_{i=0}^n\beta_ix^{n-i}.$

Il reste à enlever l’hypothèse “triangulaire supérieure”

Vous y arrivez par conjugaison. Soit $n$ un entier naturel non nul.

Soit $A$ une matrice carrée d’ordre $n$ à coefficients dans un corps de caractéristique nulle.

Son polynôme caractéristique admet un corps de rupture $\K$ dans lequel il est scindé.

Il existe donc une matrice inversible $P$ à coefficients dans $\K$ telle que $P^{-1}AP = T$ où $T$ est triangulaire supérieure.

Appliquez la méthode de Faddeev à la matrice $T$ (elle calcule bien le polynôme caractéristique de $T$.)

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

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

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

Comme $T$ et $A$ sont semblables, elles ont le même polynôme caractéristique. Il reste à voir pourquoi, si on applique l’algorithme de Faddeev directement sur la matrice $A$, on trouvera le même polynôme.

Maintenant 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 = -\dfrac{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$ compris entre $0$ et $n$ notez $R(i)$ la propriété : “$\gamma_i = \beta_i.$ et $P^{-1}A_iP = T_i$”

Initialisation : pour $i=0$, $\gamma_0=1$ et $\beta_0=1$. Comme $A_0 = T_0 = 0$, $P^{-1}A_0P=0$, donc $R(1)$ est vérifiée.

Hérédité. Soit $i$ un entier compris entre $0$ et $n-1$. Supposez $R(i)$. Vous allez montrer $R(i+1)$.

$\begin{align*}
P^{-1}A_{i+1}P &= P^{-1} A(A_{i} +\gamma_{i}I )P\\
&=P^{-1} A(A_{i} +\beta_{i}I )P\\
&=(P^{-1} AP)(P^{-1}(A_{i} +\beta_{i}I )P)\\
&=T(P^{-1}(A_{i} +\beta_{i}I )P)\\
&=T(P^{-1}A_iP+\beta_i P^{-1}IP)\\
&=T(T_i+\beta_iI)\\
&=T_{i+1}
\end{align*}$

$\begin{align*}
\beta_{i+1} &=-\dfrac{1}{i+1}\tr(T_{i+1})\\
&=-\dfrac{1}{i+1}\tr(P^{-1}A_{i+1}P)\\
&=-\dfrac{1}{i+1}\tr(A_{i+1}PP^{-1})\\
&=-\dfrac{1}{i+1}\tr(A_{i+1})\\
&=\gamma_{i+1}
\end{align*}$

Donc $R(i+1)$ est vérifiée.

Comment calculer le polynôme caractéristique avec la méthode de Faddeev ?

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

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

Alors le polynôme caractéristique de $A$ défini par $P(x)=\det(xI-A)$ est égal à $\sum_{i=0}^n\alpha_ix^{n-i}.$

Lisez d'autres articles !

Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !

Aidez-moi sur Facebook !

Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.

Partagez !

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.