I am computing the characteristic polynomial of a matrix over a number field, using the minimal polynomial of it. Is there a fast way to verify the characteristic polynomial of a big matrix ?


closed as off-topic by YCor, Greg Martin, abx, Neil Hoffman, Per Alexandersson Nov 27 '18 at 21:11

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – YCor, Greg Martin, abx, Neil Hoffman, Per Alexandersson
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ By "number field" do you mean a finite extension of $\mathbb{Q}$? The question is tagged with "finite-fields" which would rather change the answer. $\endgroup$ – David Zhang Nov 27 '18 at 15:57
  • $\begingroup$ @DavidZhang Yes, I am sorry. It is a finite extension of \mathcal{Q}, just finitely generated. $\endgroup$ – student Nov 27 '18 at 19:46
  • $\begingroup$ See math.stackexchange.com/q/405822/448 $\endgroup$ – David E Speyer Nov 27 '18 at 21:00

You can pick $n+1$ numbers and evaluate the determinant $det(A-tE)$ at these values. This gives you a garantee, but if you just want a rough check, you can pick smaller amount of (random) numbers and evaluate the determinants modulo some prime numbers (which is usually faster).

  • $\begingroup$ Thank you for the answer. You meant, computing eigenvalues (roots) of the polynomial? and then checking whether $det(A-tE)$ is zero? Then, what did you meant by picking smaller amount of random numbers? $\endgroup$ – student Nov 27 '18 at 19:58
  • 3
    $\begingroup$ @student No, I think Victor meant exactly what he wrote, nothing about computing eigenvalues. If you have two polynomials that you want to compare (in your case they're the actual characteristic polynomial and the computed one that you want to check), evaluate both at some specific numbers and see whether you get the same results. If your polynomials have degree $n$ and you get the same results for each of $n+1$ inputs, then the polynomials are the same. If you try only $k$ inputs ($k<n+1$) and get the same results, you can't be sure the polynomials agree (continued in next comment) $\endgroup$ – Andreas Blass Nov 28 '18 at 2:24
  • $\begingroup$ (continuation of previous comment) but you can be pretty confident that they agree if $k$ isn't too small and the $k$ inputs you used are random. $\endgroup$ – Andreas Blass Nov 28 '18 at 2:25
  • $\begingroup$ @AndreasBlass , got it. Thank you very much. The approach seems to be expensive, as I have to calculate determinant $k+1$ times. But,I will see. $\endgroup$ – student Nov 28 '18 at 22:25
  • $\begingroup$ How big are these matrices? And are you using floating point arithmetic? Mathematica can compute a 1000 x 1000 floating point in under 1/10 seconds, and something like MATLAB should be faster. (Exact computations are much slower; large algebraic computations should almost always be done in floating point or modulo a prime.) $\endgroup$ – David E Speyer Nov 28 '18 at 23:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.