Faddeev–LeVerrier algorithm: Difference between revisions

Revision as of 17:40, 10 July 2018

Revision as of 17:27, 10 June 2019

Line 3:

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 (mathematics)|matrix]], {{mvar|A}}, named after [[Dmitry Konstantinovich Faddeev]] and [[Urbain Le Verrier]]. Calculation of this polynomial yields the [[eigenvalue]]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 (in [[NC (complexity)|NC complexity class]]).

The algorithm has been independently rediscovered several times, in some form or another. 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.<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><ref>Paul subsequentlyHorst: redeveloped''A bymethod of determining the coefficients of a characteristic equation''. ''Ann. Math. Stat.'' '''6''' 83-84 (1935), {{DOI|10.1214/aoms/1177732612}}</ref><ref>[[Jean-Marie Souriau]], ''Une méthode pour la décomposition spectrale et l'inversion des matrices'', ''Comptes Rend.'' '''227''', 1010-1011 (1948).</ref><ref>D. K. Faddeev, and I. S. Sominsky, ''Sbornik zadatch po vyshej algebra'' ([http://www.isinj.com/aime/Problems%20in%20Higher%20Algebra%20-%20Faddeev,%20Sominskii%20(MIR,1972).pdf Problems in higher algebra], Mir publishers, 1972), Moskow-Leningrad (1949). Problem '''979'''.</ref><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> (For historical points, see Householder.<ref>

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-1011 (1948).</ref> in its present form here by Faddeev and Sominsky,<ref>D. K. Faddeev, and I. S. Sominsky, ''Sbornik zadatch po vyshej algebra'' ([http://www.isinj.com/aime/Problems%20in%20Higher%20Algebra%20-%20Faddeev,%20Sominskii%20(MIR,1972).pdf Problems in higher algebra], Mir publishers, 1972), Moskow-Leningrad (1949). Problem '''979'''.</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 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.&nbsp;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>)