How to test if a primitive matrix has an eigenvalue of unit modulus

Question

Let $M$ be a primitive matrix with non-negative integer entries. Here, primitive means that there exists some exponent $n$ such that the entries of $M^n$ are all strictly positive integers. I want to algorithmically test if $M$ has any eigenvalues $\lambda$ for which $|\lambda| = 1$. Does such a test exist?

To give some more context, the Perron-Frobenius theorem says that the eigenvalue of largest modulus for $M$ is a simple eigenvalue, and is a real number greater than $1$. It's of particular interest to be able to identify those primitive matrices whose other eigenvalues $\lambda$ all lie in the punctured disk $\{z\mid 0<|z|<1\}\subset\mathbb{C}$ (sometimes called irreducible Pisot matrices). It's easy to identify if $0$ is an eigenvalue, but testing the boundary of the disk seems more tricky.

I want to emphasise that I would like the test to be complete, not 'accurate up to some bounded error', so it's not enough to numerically find approximate eigenvalues and then check their modulus, as this could produce false positives/negatives.

Answer 1

STEP 1. Calculate the characteristic polynomial $\chi_A\in \mathbb{Z}[x]$ and decompose it in irreducibles over $\mathbb{Q}$ (or $\mathbb{Z}$): $\chi_A=f_1\cdots f_k$. For each $f_i$, denoted by $f$, we proceed as follows. We may assume that $n=degree(f)\geq 3$ (and even $\geq 5$).

If $f(e^{i\theta})=0$, then $f(e^{-i\theta})=0$ and $x^2-2\alpha x+1$ is a factor of $f$ in $\mathbb{Q}[\alpha][x]$ where $\alpha=\cos(\theta)$ is algebraic over $\mathbb{Q}$.

STEP 2. Calculate the "formal" euclidean division $(f:q)$: $f(x)=q(x)(x^2-2\alpha x+1)+u(\alpha)x+v(\alpha)$; note that $u,v\in\mathbb{Z}[\alpha]$ and have degrees $n-1$ and $n-2$; the condition to be fulfilled is: $u,v$ have a common real root in the open interval $]-1,1[$.

STEP 3. Calculate $g=gcd(u,v)$. Note that, if $n$ is large, then the coefficients along the calculation of the gcd can become very large!

STEP 4. Using STURM, the Sturm's algorithm, find the number of real roots of $g$ inside $]-1,1[$. If you find $p$ such roots, then $f$ has $2p$ roots with modulus $1$. Again STURM is a polynomial long division and the coefficients can become large; yet, in general, the degree of $g$ is small.

Three instances:

i) $f(x)=x^4+x^3+x^2+x+1$. Then $u=8\alpha^3+4\alpha^2-2\alpha,v=-4\alpha^2-2\alpha+1$ and $g=4\alpha^2+2\alpha-1$. $g$ has $2$ valid roots and therefore $f$ has $4$ roots of modulus $1$, that is not a scoop !

ii) $f(x)=x^5+2$. Then $u=16\alpha^4-12\alpha^2+1,v=-8\alpha^3+4\alpha+2$ and $g=1$. $f$ has no roots of modulus $1$, that is no more a scoop.

iii) $f(x)=x^{20}+x^{15}-3x^{10}+2x^7-5x^6+3x^5-x^4+2x^2-4x+1$. Then $g=1$ (Maple en 0"04).