Faddeev–LeVerrier algorithm

<p>In mathematics (<a href="/facts/Linear_algebra/8VaB4VWk">linear algebra</a>), the Faddeev–LeVerrier algorithm is a <a href="/facts/Recurrence_relation/JolXC71M">recursive</a> method to calculate the coefficients of the  <a href="/facts/Characteristic_polynomial/7m8roDqo">characteristic polynomial</a> 
  
    
      
        
          p
          
            A
          
        
        (
        λ
        )
        =
        det
        (
        λ
        
          I
          
            n
          
        
        −
        A
        )
      
    
    {\displaystyle p_{A}(\lambda )=\det(\lambda I_{n}-A)}
  
 of a square <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a>, A, named after <a href="/facts/Dmitry_Konstantinovich_Faddeev/GawEG0MI">Dmitry Konstantinovich Faddeev</a> and <a href="/facts/Urbain_Le_Verrier/mVzvmAPM">Urbain Le Verrier</a>. Calculation of this polynomial yields the <a href="/facts/Eigenvalue/8TjEoT8u">eigenvalues</a> of A as its roots; as a matrix polynomial in the matrix A itself, it vanishes by the <a href="/facts/Cayley%E2%80%93Hamilton_theorem/pXdJXWkR">Cayley–Hamilton theorem</a>. Computing the characteristic polynomial directly from the definition of the determinant is computationally cumbersome insofar as it introduces a new symbolic quantity 
  
    
      
        λ
      
    
    {\displaystyle \lambda }
  
; by contrast, the Faddeev-Le Verrier algorithm works directly with coefficients of matrix 
  
    
      
        A
      
    
    {\displaystyle A}
  
.
</p><p>The algorithm has been independently rediscovered several times in different forms. It was first published in 1840 by <a href="/facts/Urbain_Le_Verrier/mVzvmAPM">Urbain Le Verrier</a>, subsequently redeveloped by P. Horst, <a href="/facts/Jean-Marie_Souriau/D9ru4GWv">Jean-Marie Souriau</a>, in its present form here by Faddeev and Sominsky, and further by  J. S. Frame, and others. (For historical points, see Householder. An elegant shortcut to the proof, bypassing <a href="/facts/Newton_polynomial/2vRsjpA2">Newton polynomials</a>, was introduced by Hou. The bulk of the presentation here follows Gantmacher, p. 88.)
</p>

Faddeev–LeVerrier algorithm open-in-new

Faddeev–LeVerrier algorithm