Re: Fast test for integer-rooted polynomial

[Dirk Laurie <dirk.laurie@gmail.com>]

Op Wo. 10 Apr. 2019 om 03:10 het Gordon Royle <gordon.royle@uwa.edu.au> geskryf:

> This is a very simple task, but I want to do it billions of times, and so I want it to be as fast as possible.
>
> I have written a suitable Pari/GP routine to do it, but just naively, and I wonder if there is a clever way to do it.
>
>
> INPUT: Billions of symmetric matrices of smallish order (say at most 16 x 16) each of which has small integer entries.
>
> OUTPUT: The input matrices that have only integer eigenvalues.
>
> From the nature of the problem, I know that any integer eigenvalues lie in {0,1,2, …, n} where n is the order of the matrix.
>
>
> What I do currently:
>
> - get Pari to compute the characteristic polynomial (charpoly())
> - factor the characteristic polynomial
> - check that the factors are all linear

Why don't you just compute the eigenvalues numerically, round them to
the nearest integer, and abort if the rounding discards too much?
Depending on what "small" means, this process can be made quite
foolproof.