Algorithme de Faddeev-Leverrier [Python]

Les questions [P] utilisent Python. On note {\operatorname{tr}} la trace. Pour {A\in M_n(\mathbb C)}, on pose {A_0=A}, {u_0=1}, puis, pour {1\le k\le n},
{u_k=-\frac1k\operatorname{tr}(A_{k-1}),\quad A_k=(A_{k-1}+u_kI_n)A}L’initialisation {A_0=A} corrige la coquille {A_0=I_n} de l’énoncé et correspond à l’algorithme du corrigé.
Pour les exemples, on utilise {A=(1+|i-j|)_{1\le i,j\le5}}.

1. (a) [P] Écrire chi(A) renvoyant {([u_0,\ldots,u_n],A_n)}. Vérifier sur l’exemple la liste {[1,-5,-90,-224,-184,-48]} et une matrice finale nulle.

1. (b) [P] Écrire CayH(A) renvoyant {P(A)} pour {P(X)=u_0X^n+u_1X^{n-1}+\cdots+u_n}. Vérifier que l’exemple donne la matrice nulle. Commenter.

Soient {x_1,\ldots,x_n\in\mathbb C}, {P(X)=\prod\limits_{i=1}^n(X-x_i)} et {S_p=\sum\limits_{i=1}^nx_i^p}. On note {\sigma_0=1} et {\sigma_k=\sum\limits_{1\le i_1\lt\cdots\lt i_k\le n}x_{i_1}\cdots x_{i_k}}.

2. (a) Développer en série entière {x\mapsto\sum\limits_{i=1}^n(1-x_ix)^{-1}}.

2. (b) En utilisant {P'/P}, montrer que
{\sum_{i=1}^n\frac1{1-x_iX}=\frac{\sum_{k=0}^{n-1}(-1)^k(n-k)\sigma_kX^k}{\sum_{k=0}^n(-1)^k\sigma_kX^k}}

2. (c) En déduire, pour {1\le p\le n-1},
{S_p-\sigma_1S_{p-1}+\cdots+(-1)^{p-1}\sigma_{p-1}S_1+(-1)^pp\sigma_p=0}Quelle récurrence obtient-on pour {p\ge n} ?

3. Exprimer {A_k} comme un polynôme en {A}, pour {0\le k\le n}.

4. Exprimer {\operatorname{tr}(A_k)} avec les fonctions symétriques élémentaires des valeurs propres de {A}.

5. En déduire la valeur de {A_n}.

6. Exprimer les coefficients de {\chi_A} en fonction des traces des {A_k}.

Indications Python

np.trace calcule la trace, np.eye l’identité et A @ B le produit matriciel. Les opérations scalaires et les additions de matrices utilisent les opérateurs usuels.