1

Recently I am learning Faddeev-LeVerrier Algorithm. It's also described in Faddeeva's book Computational methods of Linear Algebra,1959, section 25, in which it's proved by mathematical induction that each step one of the coefficient of the characteristic polynomial is obtained.

To me the introducing of the auxiliary matrix $M_i$ ( or $B_i$ as used in the book) is a kind of magic. I guess this auxiliary matrix was constructed specifically according to Newton's Identity (also considering the iterative nature of the computation process), but I am not able to see the clear path from Newton's Identity to this auxiliary matrix.

Is there any information elaborating on the details for determine the auxiliary matrix and the algorithm in general? By "general", I am refereeing to the general strategy such as that shared by Jacobi/SOR iteration methods for decomposing $A=D+E$ in different ways. Thanks!

bruin
  • 257
  • 1
    Maybe this is naive, but I always thought it was just an explicit recursive repackaging of rewriting elementary symmetric polynomials (coefficients of the characteristic polynomial) in terms of the power-sum symmetric polynomials (traces of powers of the matrix), maybe with an optimization or few added in. – Joshua P. Swanson Jun 12 '21 at 02:12

0 Answers0