3
$\begingroup$

Given a matrix $A$ with rational entries, how to check whether all the eigenvalues of $A$ are rational?

What's the complexity of this problem? It seems that this can be done in polynomial time, but is there a tighter upper bound?

$\endgroup$
3
$\begingroup$

The problem is in P for the following reason.

Eigenvalues are the solutions of a univariate polynomial. Finding a solution of a univariate polynomial over $\mathbb{Q}$ can be done in polynomial time by:

Lenstra, A.K.; Lenstra, H.W.jun.; Lovász, László: Factoring polynomials with rational coefficients. (English) Math. Ann. 261, 515-534 (1982).

The polynomial has only rational roots iff all factors have degree 1.

$\endgroup$
  • 1
    $\begingroup$ It seems that the OP knows that the problem is in P, but is looking for a tighter upper bound. Are you familiar enough with the extensive follow up work to suggest what the tightest upper bounds are? I imagine that would be more interesting to the OP. $\endgroup$ – Artem Kaznatcheev Jan 22 '14 at 3:08
  • 2
    $\begingroup$ By the phrasing of the question the OP is only guessing or feeling that the problem is in P but is unsure. About a tighter upper bound, I believe that it might be done in uniform $TC^0$. $\endgroup$ – Dilworth Jan 22 '14 at 5:38
  • $\begingroup$ I think that if you added an explanation for why it is doable in uniform $TC^0$ (or a reference) to your answer then that would be interesting since it is tighter than what the OP already knows. $\endgroup$ – Artem Kaznatcheev Jan 25 '14 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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