Propriétés : (Algorithme de Faddeev)
Soit A ∈ Mn (R). On pose B0 = In et pour k ∈ J1; n − 1K on définit les matrices Bk
par récurrence : Bk = ABk−1 − tr(AB k
k−1 )
In . On a alors, au signe près, le polynôme
caractéristique de A : χA (X) = det (XIn − A) = X n + a1 X n−1 + · · · + an−1 X + an
avec ak = −tr(AB k
k−1 )
pour tout k ∈ J1; nK.
preuve :
1) χ0A (X) = tr (t com(XIn − A))
P
On note (ai,j (X))16i,j6n les coefficients de (XIn − A). On a : χA (X) = ε(σ)aσ(1),1 (X) . . . aσ(n),n (X)
σ∈Sn
donc en dérivant :
n
!
X X
χ0A (X) = ε(σ)aσ(1),1 (X) . . . aσ(k−1),k−1 (X)a0σ(k),k (X)aσ(k+1),k+1 (X) . . . aσ(n),n (X)
σ∈Sn k=1
soit en échangeant l’ordre de sommation :
n
X
χ0A (X) = det (C1 (X), . . . , Ck−1 (X), Ck0 (X), Ck+1 (X), . . . , Cn (X))
k=1
où Ck (X) représente la k colonne de (XIn − A). Or les coefficients de Ck (X) ne dépendent de X qu’à
ème
la k ème ligne, donc Ck0 (X) est le k ème vecteur colonne de la base canonique t (0, . . . 0, 1, 0, . . . 0). Si donc on
développe det (C1 (X), . . . , Ck−1 (X), Ck0 (X), Ck+1 (X), . . . , Cn (X)) par rapport à la k ème colonne on ob-
tient alors le k ème cofacteur de la diagonale de (XIn − A). Finalement, χ0A (X) est égal à la somme des co-
facteurs des éléments diagonaux de (XIn − A), donc χ0A (X) = tr (com(XIn − A)) = tr (t com(XIn − A)).
2) Identification des Bk et ak
On pose χA (X) = X n + a1 X n−1 + · · · + ak X n−k + · · · + an−1 X + an , on a donc :
χ0A (X) = nX n−1 + · · · + (n − k)ak X n−k−1 + · · · + an−1
Or chaque cofacteur de (XIn −A) est un polynôme en X de degré au plus n−1, on peut donc décomposer
t
com(XIn − A) en matrices (Bk )06k6n−1 dont les coefficients ont le même degré en X :
t
com(XIn − A) = B0 X n−1 + · · · + Bk X n−k−1 + · · · + Bn−1
Soit en prenant la trace et en identifiant au polynôme χ0A (X) :
tr(B0 ) = n; . . . ; tr(Bk ) = (n − k)ak ; . . . ; tr(Bn−1 ) = an−1 (∗)
On se sert maintenant de l’égalité, toujours vraie (XIn − A)t com(XIn − A) = det(XIn − A)In soit :
(XIn − A) B0 X n−1 + · · · + Bk X n−k−1 + · · · + Bn−1 = χA (X)In
En développant le membre de gauche et en identifiant à nouveau avec le degré, on a alors :
B0 = In ; . . . ; Bk − ABk−1 = ak In ; . . . ; −ABn−1 = an In (∗∗)
soit en prenant à nouveau la trace :
tr(B0 ) = n; . . . ; tr(Bk ) = tr(ABk−1 ) + nak ; . . . ; 0 = tr(ABn−1 ) + nan (∗ ∗ ∗)
Maintenant, en retranchant (∗) à (∗ ∗ ∗), on trouve ak = −tr(ABk
k−1 )
pour tout k ∈ J1; nK.
−tr(ABk−1 )
Reste alors à reprendre (∗∗) en remplaçant ak par k pour trouver finalement :
tr(ABk−1 )
Bk = ABk−1 − In (∀k ∈ J1; n − 1K)
k
José Gregorio : [Link]
1
Algorithme en Scilab :
Cet algorithme prend en entrée une matrice carrée A et retourne un vecteur p dont les composantes sont
les coefficients (ak )16k6n du polynôme caractéristique de A. Il retourne aussi B = A−1 si A est inversible.
function [B,p]=faddeev(A)
n=size(A,1) ;
B=eye(n,n) ;
p=ones(1,n+1) ;
for i=2:n+1
p(i)=-trace(A*B)/(i-1) ;
if(i<>n+1) then B=A*B+p(i)*eye(n,n) ;end ;
end
if(p(n+1)<>0) then B=-B/p(n+1) ;
else B=("la matrice n''est pas inversible") ; end ;
endfunction
Remarques :
1. Cette méthode est assez performante puisqu’elle permet, sans coût supplémentaire, de trouver A−1
quand A est inversible et det(A), on le voit à la fin de la ligne (∗∗) où l’on a −ABn−1 = an In .
2. Une question du jury pourrait être : quelle est le coût de cet algorithme ? Il faut y avoir un peu
réfléchi avant (combien de multiplications, d’additions ?). On peut aussi comparer cet algorithme
avec la commande poly(A,’x’) de Scilab sur des exemples.
Thèmes abordés :
* Algorithme
* Matrice
* Determinant
* Polynôme caractéristique
Bibliographie :
“Les maths en tête, Algèbre” de Xavier Gourdon (ELLIPSES)
On peut aussi trouver une preuve différente de cet algorithme (avec les formules de Newton) dans
“Oraux X-ENS, algèbre 2” de S. Francinou, H. Gianella, S. Nicolas (CASSINI)
José Gregorio : [Link]