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$ Sep 15 '15 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
    Sep 15 '15 at 16:32
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$ Jan 5 '16 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
    Jan 6 '16 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 drust@math.uni-bielefeld.de, or reply to this comment. $\endgroup$
    – Dan Rust
    Jan 4 '17 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.