|
In mathematics, ([[linear algebra]]), the '''Faddeev–LeVerrier algorithm''' is a [[Recurrence relation|recursive]] method to calculate the coefficients of the [[characteristic polynomial]] <math>p(\lambda)=\det (\lambda I_n - A)</math> of a square [[matrix]], {{mvar|A}}, named after [[Dmitry Konstantinovich Faddeev]] and [[Urbain Le Verrier]]. Calculation of this polynomial yields the [[eigenvalues]]s of {{mvar|A}} as its roots; as a matrix polynomial in the matrix {{mvar|A}} itself, it vanishes by the fundamental [[Cayley–Hamilton theorem]]. Calculating determinants, however, is computationally cumbersome, whereas this efficient algorithm is computationally significantly more efficient.
[[Urbain Le Verrier]]. Calculation of this polynomial yields the [[eigenvalues]]s of ''A'' as its roots; as a matrix polynomial in ''A'' itself it vanishes by the fundamental [[Cayley–Hamilton theorem]]. Calculating determinants, however, is computationally cumbersome, whereas this efficient algorithm is computationally vastly more efficient.
The algorithm has been independently rediscovered several times, in some form or another. It was first published in 1840 by [[Urbain Le Verrier]],<ref>[[Urbain Le Verrier]]: ''Sur les variations séculaires des éléments des orbites pour les sept planètes principales'', ''J. de Math.'' (1) '''5''', 230 (1840), [http://gallica.bnf.fr/ark:/12148/bpt6k163849/f228n35.capture# Online]</ref> subsequently redeveloped by
P. Horst,<ref>Paul Horst: ''A method of determining the coefficients of a characteristic equation''. ''Ann. Math. Stat.'' '''6,''' 83-84 (1935), {{DOI|10.1214/aoms/1177732612}}</ref>, [[Jean-Marie Souriau]],<ref>[[Jean-Marie Souriau]], ''Une méthode pour la décomposition spectrale et l'inversion des matrices'', ''Comptes Rend.'' '''227''', 1010-101l1011 (1948).</ref>, in its present form here by Faddeev and Sorminski,<ref> D. K. Faddeev, and I. S. Sominskij, ''Sbornik zadatch po vyshej algebra'', Moskow-Leningrad (1949).</ref> and further by J. S. Frame,<ref> J. S. Frame: ''A simple recursion formula for inverting a matrix (abstract)''., ''Bull. Am. Math. Soc.'' '''55,''' 1045 (1949), {{DOI|10.1090/S0002-9904-1949-09310-2}}</ref>, and others. (For further historical points, see Householder.<ref>
{{cite book|ref=harv|first=Alston S.|last=Householder|title=The Theory of Matrices in Numerical Analysis |publisher=Dover Books on Mathematics|year=2006|authorlink=Alston Scott Householder | isbn=0486449726}}</ref>. An elegant shortcut to the proof, bypassing [[Newton polynomial]]s, was introduced by Hou<ref> Hou, S. H. (1998). [http://epubs.siam.org/doi/pdf/10.1137/S003614459732076X "Classroom Note: A Simple Proof of the Leverrier--Faddeev Characteristic Polynomial Algorithm"] ''SIAM review'' '''40(3)''' 706-709, {{doi|10.1137/S003614459732076X}} .</ref> The bulk of the presentation here follows Gantmacher, p. 88.<ref>{{cite book|ref=harv| last= Gantmacher|first=F.R. | title=The Theory of Matrices |year=1960| publisher= Chelsea Publishing|___location= NY | ISBN = 0-8218-1376-5 }}</ref>)
==The Algorithm==
|
