Integer eigenvalues in Matlab

Question

I am trying to write a Matlab program which decides if a given (integer) matrix A has integer eigenvalues and if this is the case calculates the eigenvalues and their multiplicities. Any ideas how to get started?

Answer 1

A first step is to be able to get the characteristic polynomial $P$ with integer coefficients. For this, use the Faddeev-Leverrier algorithm.

Indeed, with this algorithm, you can keep integer values all the way long because it uses traces of powers of your matrix $A$.

Of course, the size of $A$ shouldn't be too large ; otherwise, Matlab will switch to "floating point" numbers at a certain step...

Now, for the roots. As roots are usually within a rather narrow range, a simple testing for example with integers between $−1000 \le n \le 1000$ whether $P(n)=0$ or not, will do the job... in at most 1 millisecond. The question of roots with absolute value $>1000$ can be treated in a separate way.

For multiple roots, test if $P(n)=0$ and $P'(n)=0$ for a double root ; if moreover $P(n)=P'(n)=P''(n)=0$, it is triple root, etc.

A different type of action using the "eig" function provides you the floating point values of eignevalues. If you are allowed to use this function, you can take their rounded value (to the next integer) and test whether these rounded values are (exact!) roots of the characteristic polynomial.