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

Réagissez !

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.