Faddeev–LeVerrier algorithm: Difference between revisions

Revision as of 21:31, 9 June 2021

Revision as of 23:11, 17 June 2021

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>pp_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 determinant from the definition of characteristic polynomial, however, is computationally cumbersome,

because <math>\lambda</math> is new symbolic quantity, whereas this algorithm works directly with coefficients of matrix <math>A</math>.

Line 9:

==The Algorithm==

The objective is to calculate the coefficients {{math|''c_k''}} of the characteristic polynomial of the {{math|''n''×''n''}} matrix {{mvar|A}},

::<math>pp_A(\lambda)\equiv \det(\lambda I_n-A)=\sum_{k=0}^{n} c_k \lambda^k~,</math>

where, evidently, {{math|''c_n''}} = 1 and {{math|''c''}}₀ = (−1)^''n'' det {{mvar|A}}.

Line 38:

The proof relies on the modes of the [[adjugate matrix]], {{math|''B_k ≡ M_n−k''}}, the auxiliary matrices encountered. &nbsp;

This matrix is defined by

::<math>(\lambda I-A) B = I ~ pp_A(\lambda)</math>

and is thus proportional to the [[Resolvent formalism|resolvent]]

:<math>B = (\lambda I-A)^{-1} I ~ pp_A(\lambda) ~. </math>

It is evidently a matrix polynomial in {{math|''λ''}} of degree {{math|''n−1''}}. Thus,

Line 58:

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

::<math>\lambda \frac{\partial pp_A(\lambda) }{ \partial \lambda} -n p =\operatorname{tr} AB~.</math>

This is but the trace of the defining equation for {{mvar|B}} by dint of [[Jacobi's formula]],

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

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

Inserting the polynomial mode forms in this auxiliary equation yields

Line 75:

and, in comportance with the [[Cayley–Hamilton theorem]],

:<math> \operatorname{adj}(A) =(-)^{n-1} M_{n}=(-)^{n-1} (A^{n-1}+c_{n-1}A^{n-2}+ ...+c_2 A+ c_1 I)=(-)^{n-1} \sum_{k=1}^n c_k A^{k-1}~.</math>