The Faddeev-LeVerrier algorithm computes the coefficients of the characteristic polynomial of
an matrix
over a field of characteristic
0 or greater than
.
Write the monic polynomial as
|
(1)
|
where
is the identity matrix. Starting with
, the recurrence for
is
|
(2)
| |||
|
(3)
|
where
denotes the matrix trace (Hou 1998).
To derive the recurrence, expand the adjugate matrix of
as
|
(4)
|
Multiplying by and comparing coefficients
with
yields the matrix recurrence and
.
On the other hand, differentiating the determinant
gives
as the matrix trace of the adjugate
matrix. Comparing coefficients gives
for
,
which together with
gives the trace recurrence. Setting
in the adjugate expansion gives
.
Related recurrences compute the Drazin inverse (Greville 1973) and the Pfaffian (Bär 2021). Barnett (1989) treats the extension to polynomial matrices.