Integer matrices with no integer eigenvalues - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T20:54:52Z http://mathoverflow.net/feeds/question/24829 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24829/integer-matrices-with-no-integer-eigenvalues Integer matrices with no integer eigenvalues Hej 2010-05-15T22:45:22Z 2010-11-12T03:03:16Z <p>Let <code>$A = \begin{pmatrix} 3&amp;1 \\ 0&amp;1 \end{pmatrix}$</code> and <code>$B = \begin{pmatrix} 1&amp;0\\ 1&amp;2 \end{pmatrix}$</code>. I want to show that the only elements of the semigroup generated by $A$ and $B$ that have integer eigenvalues are elements of the form $A^n$ and $B^n$, $n \in \mathbb{N}$. I have tried every way that I can think of. Is it possible that a problem like this is undecidable? </p> http://mathoverflow.net/questions/24829/integer-matrices-with-no-integer-eigenvalues/24861#24861 Answer by Bjorn Poonen for Integer matrices with no integer eigenvalues Bjorn Poonen 2010-05-16T04:34:45Z 2010-05-16T04:34:45Z <p>The general problem of this type is undecidable. More precisely, there is no algorithm that takes as input two $n \times n$ integer matrices and decides whether the semigroup they generate contains a matrix all of whose eigenvalues are integers.</p> <p><strong>Proof:</strong> Given two $n \times n$ integer matrices $A$ and $B$, choose a prime $p \ge 5$ such that $p>n$, choose a degree $p$ monic integral polynomial $f(x)$ with the full symmetric group $S_p$ as Galois group, let $C$ be a $p \times p$ integer matrix with characteristic polynomial $f(x)$, and consider the tensor products (Kronecker products) $A \otimes C$ and $B \otimes C$. An element of the semigroup generated by these two $np \times np$ matrices has the form $M \otimes C^m$ for some $M$ in the semigroup generated by $A$ and $B$ and some $m \ge 1$. Each eigenvalue of $M$ is of degree at most $n$ over $\mathbf{Q}$, but each eigenvalue of $C^m$ is of degree exactly $p$, so the eigenvalues of $M \otimes C^m$ are all integers if and only if the all eigenvalues of $M$ are $0$, which holds if and only if $M$ is nilpotent. Thus the semigroup generated by $A \otimes C$ and $B \otimes C$ contains a matrix all of whose eigenvalues are integers if and only if the semigroup generated by $A$ and $B$ contains the zero matrix. But the latter property is undecidable: see Chapter 3 of <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.5792&amp;rep=rep1&amp;type=pdf" rel="nofollow">this survey article</a>. Thus one cannot have an algorithm that would answer the integer eigenvalue question for $A \otimes C$ and $B \otimes C$ in general.</p> http://mathoverflow.net/questions/24829/integer-matrices-with-no-integer-eigenvalues/45779#45779 Answer by Mark Sapir for Integer matrices with no integer eigenvalues Mark Sapir 2010-11-12T02:24:35Z 2010-11-12T03:03:16Z <p>I just found this problem. If you try the matrix $A^nB^m$, then your question for such matrices is equivalent to this number theory question: Can $9^n+2\cdot 9^n\cdot 2^m-12\cdot 3^n\cdot 2^m+2\cdot 3^n+4^{m}\cdot 9^n+4^{m}+2\cdot 2^m+9$ be a square provided $m,n\ne 0$. Note that if we denote $3^n$ by $x$, $2^m$ by $y$, we get a quartic polynomial in $x,y$. I hope number theorists here can say something about this exponential Diophantine equation. </p> <p>The answer to problem with question mark is "obviously NO". To be undecidable, you should have a mass problem. For given $A,B$, you have the following problem: given a product $W(A,B)$ is it true that the matrix has an integer eigenvalue. That problem is obviously decidable. The question of whether this is true for <em>every</em> word $W$ requires answer "yes" or "no" and is not a mass problem. You can still ask whether it is independent from ZF or even ZFC (or unprovable in the Peano arithmetic). What Bjorn had in mind is a completely different and much harder problem when you include $A, B$ in the input and ask if for this $A$, $B$ some product $W(A,B)$ not of the form $A^n, B^m$ has an integer eigenvalue. This is a mass problem which could be undecidable (although he, of course, did not prove it). But this has nothing to do with the original question. </p>