3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is $n$ known / is it feasible to work with $M^n$? $\endgroup$ Commented Sep 15, 2015 at 16:27
  • $\begingroup$ Sure, if $\lambda$ is an eigenvalue of $M$ then $\lambda^n$ is an eigenvalue of $M^n$, so you can assume $M$ is a positive integer matrix (finding $n$ is a finite check). $\endgroup$
    – Dan Rust
    Commented Sep 15, 2015 at 16:32

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ In step 2 here, I am not sure what you mean by the formal euclidean divisor? I cannot seem to work out how you got u and v in your examples. It would be great if you could elaborate on this step! $\endgroup$ Commented Jan 5, 2016 at 12:02
  • 1
    $\begingroup$ @ Scott Balchin , in fact it is the standard euclidean division; I added the word "formal" because it is not a digital calculation; indeed the coefficients depend on the parameter $\alpha$. The remainder of the division is a polynomial in $x$ of degree $1$ and with coefficients in $\mathbb{Q}[\alpha]$. Practically, this calculation requires a formal calculation software as Maple, Mathematica,...Note that the previous method is valid when $A\in M_n(\mathbb{Z})$ or even when $A\in M_n(\mathbb{Q})$. $\endgroup$
    – user91684
    Commented Jan 6, 2016 at 19:04
  • $\begingroup$ @loupblanc We would like to cite this answer in a paper being prepared. Would you be happy to provide a real name that we may use in the citation, or would you prefer we use your username here? Feel free to email myself at [email protected], or reply to this comment. $\endgroup$
    – Dan Rust
    Commented Jan 4, 2017 at 20:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .