# compleixty of rational checking of eigenvalues

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?

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.

• 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. Jan 22 '14 at 3:08
• 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$.
– user13756
Jan 22 '14 at 5:38
• 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. Jan 25 '14 at 21:27