Effective way of checking if all eigenvalues of a matrix are integers Given A matrix with integer entries, it should be checked if all its eigenvalues
 are integers.
Of course, the characteristic polynomial could be calculated, but is there any
 faster (or easier) method ? 
Another possibility would be : Search a bound for the eigenvalues and check for
 each possible integer n, if $A-nI$ is invertible. But this is also cumbersome and another problem is that multiple eigenvalues may not be detected.

For any integer polynomial, we can write down the companion matrix.  For any integer matrix, we can quickly calculate the characteristic polynomial.
So your question is essentially equivalent to (and at least as hard as) the question: How can we tell if all the roots of a polynomial are integers?
I think that the best method here would be the rational root test.  As a corollary, we only need to check integer factors of the determinant.
Note that, if you want to detect multiple roots, you can take the $d$-th power of $A-nI$ (where $d$ is the dimension) and find the dimension of the kernel.  But this is unlikely to be faster than just factoring the characteristic polynomial.
