Faddeev–LeVerrier algorithm
From Wikipedia, the free encyclopedia
In mathematics (linear algebra), the Faddeev–LeVerrier algorithm is a recursive method to calculate the coefficients of the characteristic polynomial of a square matrix, A, named after Dmitry Konstantinovich Faddeev and Urbain Le Verrier. Calculation of this polynomial yields the eigenvalues of A as its roots; as a matrix polynomial in the matrix A itself, it vanishes by the Cayley–Hamilton theorem. Computing the characteristic polynomial directly from the definition of the determinant is computationally cumbersome insofar as it introduces a new symbolic quantity ; by contrast, the Faddeev-Le Verrier algorithm works directly with coefficients of matrix .
The algorithm has been independently rediscovered several times in different forms. It was first published in 1840 by Urbain Le Verrier, subsequently redeveloped by P. Horst, Jean-Marie Souriau, in its present form here by Faddeev and Sominsky, and further by J. S. Frame, and others.[1][2][3][4][5] (For historical points, see Householder.[6] An elegant shortcut to the proof, bypassing Newton polynomials, was introduced by Hou.[7] The bulk of the presentation here follows Gantmacher, p. 88.[8])