Characteristic polynomial #381
Description
The problem here is that we cannot compute it straightforward. For example, if you symbolically, even via Gaussian elimination, compute a determinant of a matrix 6x6, you will get almost 500'000'000-complex expression, which is hard to simplify into a polynomial.
So there should be a separate algorithm for computing it.
Activity
mednik commentedon Aug 7, 2021
There is a variation of the straightforward approach: https://en.wikipedia.org/wiki/Faddeev%E2%80%93LeVerrier_algorithm
SymPy uses an improvement over this called https://en.wikipedia.org/wiki/Samuelson%E2%80%93Berkowitz_algorithm , it performs no division so may be used in symbolic situations over arbitrary rings, however it looks like it is even slower.
Now if your matrices are over something good like R, C or F_p, there are some other approaches, as far as I understand you have to google "Krylov method for characteristic polynomial".
Take the characteristic polynomial back out
Rafael-SOWNet commentedon Aug 5, 2026
Attempted and withdrawn, with what I found, in case it saves the next person the same hour.
det(x*I - A)is a two-line change on top of the existingDeterminant-- putx - a[i][i]on the diagonal, negate the rest, take the determinant. It gives the right polynomial and the right roots. It also comes back NaN at particular values of x.The cause is that
Determinantis computed by Gaussian elimination, which divides, so the answer carries the conditions under which those divisions were legal. On an ordinary numeric matrix those conditions are about the entries and are harmless. On the shifted matrix the pivots are polynomials inx, so the conditions readnot (x - 1) = 0and the like -- and every one of them is a removable singularity of a polynomial that is defined everywhere. The conditions are correct of the determinant and wrong of the characteristic polynomial.Stripping them off afterwards does not work, in either order: strip-then-simplify leaves the underlying
0/0, and simplify-then-strip has already collapsed the false condition to NaN.So it needs one of:
Determinantsays Laplace was rejected for N! memory, but for the sizes anyone writes a characteristic polynomial for that is not the binding cost); orDeterminanton any symbolic matrix, not just this one.I have taken my attempt back out rather than leave an API on master that is NaN at some of its own points. Leaving this open, and the note above is the useful part of the attempt.
Reduce radicals and read the trigonometric tables backwards (ASC-Comm…
Rafael-SOWNet commentedon Sep 30, 2026
Taken up again in #1625. The blocker I described has gone:
Determinantnow uses Bareiss or Laplace (#992, #999), which leave no division, sodet(x I - A)has a value everywhere. For example, [[1, 2], [3, 4]] givesx ^ 2 - 5 * x - 2.A square matrix has a characteristic polynomial (ASC-Community#1625)