Faddeev–LeVerrier algorithm: Difference between revisions

Revision as of 03:48, 28 July 2025

Latest revision as of 23:47, 28 July 2025

(2 intermediate revisions by 2 users not shown)

Line 1:

[[Image:Urbain Le Verrier.jpg|220px|thumb|right|[[Urbain Le Verrier]] (1811&ndash;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 [[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 <math>\lambda</math>; by contrast, the Faddeev-Le Verrier algorithm works directly with coefficients of matrix <math>A</math>.

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

Line 9:

The objective is to calculate the coefficients {{math|''c_k''}} 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_n''}} = 1 and(characteristic polynomials are [[Monic polynomial|monic polynomials]]) and {{math|''c''}}₀ = (−1)^''n'' det {{mvar|A}}.

The coefficients {{math|''c_{n- − i}''}} are determined by induction on {{mvar|i}}, using an auxiliary sequence of matrices

:<math> \begin{align}

M_0 &\equiv 0 & c_n &= 1 \qquad &(k=0) \\