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$, where $n \in \mathbb{N}$. I have tried every way that I can think of. Is it possible that a problem like this is undecidable?
$\begingroup$
$\endgroup$
11
-
2$\begingroup$ 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. $\endgroup$– Xandi TuniCommented May 15, 2010 at 23:07
-
$\begingroup$ @Hej: Do you know any two integer matrices $A$ and $B$ which generate the semigroup that doesn't have this property? $\endgroup$– Andrey RekaloCommented May 16, 2010 at 0:06
-
$\begingroup$ Two comments. 1) Can you tell us why you are interested in this? Maybe someone can see another approach to take when it is seen what the problem's setting is. 2) Can you tell us what ways you have thought of? What you are asking is equivalent to asking if the discriminants of the characteristic polynomials of the matrices in that semigroup are never squares except for powers of A and B. (The characteristic polynomial of a product of matrices is unchanged by cyclic shifts in the order of multiplication, so you could assume the first matrix in your product is A, say.) $\endgroup$– KConradCommented May 16, 2010 at 0:19
-
3$\begingroup$ 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). $\endgroup$– JSECommented May 16, 2010 at 2:08
-
2$\begingroup$ 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. $\endgroup$– HejCommented May 16, 2010 at 21:14
|
Show 6 more comments
2 Answers
$\begingroup$
$\endgroup$
7
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.
answered May 16, 2010 at 4:34
-
3$\begingroup$ 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! $\endgroup$ Commented May 16, 2010 at 4:53
-
1$\begingroup$ @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". $\endgroup$ Commented May 16, 2010 at 4:58
-
$\begingroup$ 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. $\endgroup$ Commented May 16, 2010 at 5:06
-
$\begingroup$ Bjorn, I just started to look at the link you posted and in the introduction the author says she uses Paterson's method but also that in Chapter 3 (the very one you direct us to look at) she shows Paterson's method "does not suit for problems of 2 x 2 matrices". Hej's problem of course is specifically about 2 x 2 matrices, so do you really think there is a way to modify your argument to really work in the 2 x 2 case? $\endgroup$– KConradCommented May 16, 2010 at 5:11
-
5$\begingroup$ 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. $\endgroup$ Commented May 16, 2010 at 6:20
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ @ 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. $\endgroup$– HejCommented Nov 12, 2010 at 3:00
-
1$\begingroup$ @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. $\endgroup$– user6976Commented Nov 12, 2010 at 3:08