|
[[Image:Urbain Le Verrier.jpg|220px|thumb|right|[[Urbain Le Verrier]] (1811–1877)<br> The discoverer of [[Neptune]].]]
In mathematics ([[linear algebra]]), the '''Faddeev–LeVerrier algorithm''' is a [[Recurrence relation|recursive]] method to calculate the coefficients of the [[characteristic polynomial]] <math>p_A(\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]]. Computing determinantthe characteristic polynomial directly from the definition of characteristicthe polynomial, however,determinant is computationally cumbersome insofar as it introduces a new symbolic quantity <math>\lambda</math>; by contrast, the Faddeev-Le Verrier algorithm works directly with coefficients of matrix <math>A</math>.
because <math>\lambda</math> is new symbolic quantity, whereas this algorithm works directly with coefficients of matrix <math>A</math>.
The algorithm has been independently rediscovered several times, in somedifferent form or anotherforms. 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 Horst: ''A method 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] {{Webarchive|url=https://web.archive.org/web/20160309010057/http://www.isinj.com/aime/Problems%20in%20Higher%20Algebra%20-%20Faddeev,%20Sominskii%20(MIR,1972).pdf |date=2016-03-09 }}, Mir publishers, 1972), Moscow-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>
{{cite book|first=Alston S.|last=Householder|title=The Theory of Matrices in Numerical Analysis |publisher=Dover Books on Mathematics|year=2006|author-link=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| 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==
The objective is to calculate the coefficients {{math|''c<sub>k</sub>''}} of the characteristic polynomial of the {{math|''n''×''n''}} matrix {{mvar|A}},
::<math>p_A(\lambda)\equiv \det(\lambda I_n-A)=\sum_{k=0}^{n} c_k \lambda^k~,</math>
where, evidently, {{math|''c<sub>n</sub>''}} = 1 and(characteristic polynomials are [[Monic polynomial|monic polynomials]]) and {{math|''c''}}<sub>0</sub> = (−1)<sup>''n''</sup> det {{mvar|A}}.
The coefficients are{{math|''c<sub>n determined− recursivelyi</sub>''}} fromare the top down,determined by dintinduction of the sequence of auxiliary matriceson {{mvar|Mi}}, using an auxiliary sequence of matrices
:<math> \begin{align}
M_0 &\equiv 0 & c_n &= 1 \qquad &(k=0) \\
:<math>M_3= A^2-A\mathrm{tr} A -\frac{1}{2}\Bigl(\mathrm{tr} A^2 -(\mathrm{tr} A)^2\Bigr) I,</math>
::<math>c_{n-3}=- \tfrac{1}{6}\Bigl( (\operatorname{tr}A)^3-3\operatorname{tr}(A^2)(\operatorname{tr}A)+2\operatorname{tr}(A^3)\Bigr)=-\frac{1}{3}(c_n \mathrm{tr} A^3+c_{n-1} \mathrm{tr} A^2 +c_{n-2}\mathrm{tr} A); </math>
etc.,<ref>Zadeh, Lotfi A. and Desoer, Charles A. (1963, 2008). ''Linear System Theory: The State Space Approach'' (Mc Graw-Hill; Dover Civil and Mechanical Engineering) {{ISBN|9780486466637}} , pp 303–305;
</ref><ref>Abdeljaoued, Jounaidi and Lombardi, Henri (2004). ''Méthodes matricielles - Introduction à la complexité algébrique'',
(Mathématiques et Applications, 42) Springer, {{ISBN|3540202471}} .</ref>
==An equivalent but distinct expression==
A compact determinant of an {{mvar|m}}×{{mvar|m}}-matrix solution for the above Jacobi's formula may alternatively determine the coefficients {{mvar|c}},<ref>Brown, Lowell S. (1994). ''Quantum Field Theory'', Cambridge University Press. {{ISBN|978-0-521-46946-3}}, p. 54; Also see, Curtright, T. L., Fairlie, D. B. and Alshal, H. (2012). "A Galileon Primer", arXiv:1212.6972 , section 3.</ref><ref>{{Cite book|title=Methods of Modern Mathematical Physics|last1=Reed|first1=M.|last2=Simon|first2=B.|publisher=ACADEMIC PRESS, INC.|year=1978|isbn=0-12-585004-2|volume=4 Analysis of Operators|___location=USA|pages=323–333, 340, 343}}</ref>
:<math>c_{n-m} = \frac{(-1)^m}{m!}
* [[Characteristic polynomial]]
* [[Exterior algebra#Leverrier's algorithm|Exterior algebra § Leverrier's algorithm]]
* [[Horner's method]]
* [[Fredholm determinant]]
|
