Faddeev–LeVerrier algorithm: Difference between revisions

Revision as of 05:51, 1 March 2016

Revision as of 06:23, 1 March 2016

Line 2:

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-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>)

==The Algorithm==

Line 19:

M_1= I ~, \quad c_{n-1} = - \mathrm{tr} A ; \qquad M_2= A-I\mathrm{tr} A , \quad c_{n-2}=-\frac{1}{2}\Bigl(\mathrm{tr} A^2 -(\mathrm{tr} A)^2\Bigr) ;

</math>

<math>M_3= A^2-A\mathrm{tr} A -\frac{1}{2}\Bigl(\mathrm{tr} A^2 -(\mathrm{tr} A)^2\Bigr) I, \qquad 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); \qquad \cdots </math> etc.

Observe {{math|''A⁻¹ {{=}} − M_n /c₀'' {{=}} (−)^''n''−1''M_n''/det''A''}} terminates the recursion at {{mvar| λ}}. This could be used to obtain the inverse or the determinant of {{mvar|A}}.

Line 43:

which thus dictates the recursion

:<math> M_{m} =A M_{m-1} +c_{n-m+1} I ~,</math>

for {{mvar|m}}=1,...,{{mvar|n}}. Note that ascending index amounts to descending in powers of {{mvar|λ}}, but the polynomial coefficients {{mvar|c}} are yet to be determined in terms of the {{mvar|M}}s and {{mvar|A}}.

This can be easiest achieved through the following auxiliary equation (Hou, 1998),

Line 49:

This is but the trace of the the defining equation for {{mvar|B}} after multiplying it by {{mvar|B}} on the right, and utilizing [[Jacobi's formula]],

:<math>\frac{\partial p(\lambda)}{\partial \lambda}= p(\lambda) \sum^\infty _{m=0}\lambda ^{-(m+1)} \operatorname{tr}A^m =

p(\lambda) ~ \operatorname{tr} \frac{I}{\lambda I -A}\equiv\operatorname{tr} B~. </math>

Inserting the polynomial mode forms in this auxiliary equation yields

Line 60:

This completes the recursion of the previous section, unfolding in descending powers of {{mvar|λ}}. Further note in the algorithm that, more directly,

:<math> M_{m} =A M_{m-1} - \frac{1}{m-1} (\operatorname{tr}A M_{m-1}) I ~.</math>

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.</ref>

Line 73 ⟶ 72:

{{reflist}}

{{DEFAULTSORT:Faddeev-LeVerrier algorithm}}

[[Category:Polynomials]]

[[Category:Matrix theory]]