Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $A = \begin{pmatrix} 3&1 \\ 0&1 \end{pmatrix}$ and $B = \begin{pmatrix} 1&0\\ 1&2 \end{pmatrix}$. 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?

share|improve this question
    
Can't seem to get the latex right, but these are two by two matrices. –  Hej May 15 '10 at 22:54
    
Markdown was munching your backslashes. –  S. Carnahan May 15 '10 at 22:59
2  
It could, in principle, be undecidable, but I very much doubt that. Without any further arguments, it sounds rather like defeatism to me at that point. –  Xandi Tuni May 15 '10 at 23:07
3  
Heuristically, the 2^n words of length n in your semigroup are going to have determinant around 6^n, so I guess the "probability" of the discriminant being a square is something like 6^{-n/2}; so I guess it seems reasonable to me that you'd expect only finitely many integer eigenvalues, and none if you don't find any early on. (Yes, I know there are the A^m and B^n, but hey, heuristics are heuristics...) It's much less clear to me what to expect when the matrices are in SL_2(Z). –  JSE May 16 '10 at 2:08
2  
Andrey, for example if $A=[3,1;0,1]$ and $B=[1,0;1,4]$, then $AB$ has integer eigenvalues. I think (3,2) is special in a mysterious way relating to the Collatz problem. –  Hej May 16 '10 at 21:14

2 Answers 2

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.

Proof: 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 this survey article. Thus one cannot have an algorithm that would answer the integer eigenvalue question for $A \otimes C$ and $B \otimes C$ in general.

share|improve this answer
    
+1: wow. $ $ –  Pete L. Clark May 16 '10 at 4:53
3  
But, but, but... how can there be a zero matrix in <A,B> is A and B are invertible? Maybe your general problem is too general! –  Victor Protsak May 16 '10 at 4:53
1  
@Bjorn: But is it an answer to the question? In general, yes, it's undecidable but in this particular case... Almost every real number has irrationality exponent 2 (metric NT) but to find the irrationality exponent of a given number, like $\pi$, is a different task (diophantine NT). It looks like the original problem is quite diophantine, but it's really hard to write it "in symbols". –  Wadim Zudilin May 16 '10 at 4:58
    
Exactly! It seems the result of the paper is not applicable here. Besides, the authors claim that their particular problem for integer matrices is undecidable for $n\times n$ matrices, when $n>2$ and decidable for $2\times 2$-matrices. –  Andrey Rekalo May 16 '10 at 5:06
5  
Wow, I didn't expect my answer to be so controversial! My proof proves what it claims to prove, nothing more. I answered only the question with a question mark: "Is it possible that a problem like this is undecidable?" I agree with all of you that this has no bearing on the answer for the two particular 2 by 2 matrices. @KConrad: I think that Vesa Halava is male. –  Bjorn Poonen May 16 '10 at 6:20

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.

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

share|improve this answer
    
@ Mark. What I was worried about is that the problem would be unprovable in the Peano arithmetic but the problem of whether there is an algorithm that can determine whether a seimgroup generated by two input matrices contains a matrix with integer eigenvalues is interesting on its own. –  Hej Nov 12 '10 at 3:00
1  
@Hej: As you can see even for products like $A^nB^m$ the problem is equivalent to solvability of certain exponential Diophantine equation. So the problem is not easy. As far as I know, this is not the kind of problems for which one can prove independence from PA by existing methods. In any case, you should modify the question replacing "undecidability" by "unprovability in PA". These are completely different questions. –  Mark Sapir Nov 12 '10 at 3:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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