TOPICS
Search

Faddeev-LeVerrier Algorithm


The Faddeev-LeVerrier algorithm computes the coefficients of the characteristic polynomial of an n×n matrix A over a field of characteristic 0 or greater than n. Write the monic polynomial as

 p(t)=det(tI-A)=t^n+c_1t^(n-1)+...+c_n,
(1)

where I is the identity matrix. Starting with B_0=I, the recurrence for k=1,...,n is

c_k=-(Tr(AB_(k-1)))/k
(2)
B_k=AB_(k-1)+c_kI,
(3)

where Tr denotes the matrix trace (Hou 1998).

To derive the recurrence, expand the adjugate matrix of tI-A as

 adj(tI-A)=sum_(k=0)^(n-1)t^(n-1-k)B_k.
(4)

Multiplying by tI-A and comparing coefficients with p(t)I yields the matrix recurrence and B_n=0. On the other hand, differentiating the determinant gives p^'(t) as the matrix trace of the adjugate matrix. Comparing coefficients gives Tr(B_k)=(n-k)c_k for 1<=k<n, which together with B_n=0 gives the trace recurrence. Setting t=0 in the adjugate expansion gives adj(A)=(-1)^(n-1)B_(n-1).

Related recurrences compute the Drazin inverse (Greville 1973) and the Pfaffian (Bär 2021). Barnett (1989) treats the extension to polynomial matrices.


See also

Adjugate Matrix, Characteristic Polynomial

Explore with Wolfram|Alpha

References

Bär, C. "The Faddeev-LeVerrier Algorithm and the Pfaffian." Linear Algebra Appl. 630, 39-55, 2021. https://doi.org/10.1016/j.laa.2021.07.023.Barnett, S. "Leverrier's Algorithm: A New Proof and Extensions." SIAM J. Matrix Anal. Appl. 10, 551-556, 1989. https://doi.org/10.1137/0610040.Greville, T. N. E. "The Souriau-Frame Algorithm and the Drazin Pseudoinverse." Linear Algebra Appl. 6, 205-208, 1973. https://doi.org/10.1016/0024-3795(73)90021-9.Hou, S.-H. "Classroom Note: A Simple Proof of the Leverrier-Faddeev Characteristic Polynomial Algorithm." SIAM Rev. 40, 706-709, 1998. https://doi.org/10.1137/S003614459732076X.

Cite this as:

Weisstein, Eric W. "Faddeev-LeVerrier Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Faddeev-LeVerrierAlgorithm.html

Subject classifications