# 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?

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:
• 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$. – Dilworth 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. – Artem Kaznatcheev Jan 25 '14 at 21:27