1
$\begingroup$

This is a more elegant version of the original version which can be found below; it is based on a suggestion by Peter Mueller.

Let $\mathbb{N}$ denote the set of positive integers and for $n\in\mathbb{N}$ let $\text{Mat}(n\times n,\mathbb{Z})$ be the set of integer matrices of the format $n\times n$.

Denote with $B_n$ the set of matrices $A\in \text{Mat}(n\times n,\mathbb{Z})$ such that the sequence $(A^k)_{k\in\mathbb{N}}$ is eventually periodic; that is: $$B_n = \{A\in \text{Mat}(n\times n,\mathbb{Z}): \exists k, \ell\in\mathbb{N} (k\neq \ell \wedge A^k = A^\ell)\}.$$

Is $B_n$ computable for every $n\in\mathbb{N}$?


Original version of the question: Let $\mathbb{N}$ denote the set of positive integers and for $n\in\mathbb{N}$ let $\text{Mat}(n\times n,\mathbb{Z})$ be the set of integer matrices of the format $n\times n$.

For $A\in \text{Mat}(n\times n,\mathbb{Z})$ let the most extreme entry be defined by $$\text{m.e.}(A) = \max \big\{ |A_{ij}|:i, j\in\{1,\ldots,n\} \big\}.$$

We say $A\in \text{Mat}(n\times n,\mathbb{Z})$ is bounded (with respect to the most extreme entry) if there is $M\in\mathbb{N}$ such that for all $k\in\mathbb{N}$ we have $\text{m.e.}(A^k) \leq M$. By $B_n$ we denote the set of bounded matrices $A\in \text{Mat}(n\times n,\mathbb{Z})$ in the sense above.

Is $B_n$ computable for every $n\in\mathbb{N}$?

$\endgroup$
6
$\begingroup$

Of course. The eigenvalues of this matrix (over $\mathbb{C}$) may only be zeros and roots of unity (whose minimal polynomial is of degree at most $n$, as they are roots of the characteristic polynomial), and blocks of size bigger than one in the Jordan normal form may only correspond to the eigenvalue zero.

Note also that the minimal polynomial for primitive roots of unity of degree $n$ is the cyclotomic polynomial $\Phi_n(T)$ of degree $\phi(n)$, the Euler's totient function. It is known that for all $n>2$ we have $\phi(n)>\frac{n}{c\log\log n+\frac{3}{\log\log n}}$ for $c=e^\gamma$. In particular, $\phi(n)>\sqrt{n}$ for all $n>6$.

This suggests the following algorithm:

1) Replace the matrix $A$ by $B:=A^n$. This would kill all nilpotent Jordan blocks.

2) Let $f(T)=\prod_{i=1}^{n^2}\Phi_i(T)$, where $\Phi_i$ is the $i$-th cyclotomic polynomial. Compute $C=f(B)$. If $C=0$, then $A\in B_n$, otherwise $A\notin B_n$.

$\endgroup$
  • 1
    $\begingroup$ The second sentence isn't quite right. For instance $GL(2,\mathbb Z)$ contains elements of orders $2$ and $3$, so $GL(4,\mathbb Z)$ contains elements of order $6$. $\endgroup$ – Peter Mueller Nov 29 '18 at 10:36
  • $\begingroup$ @PeterMueller yes you're right. It makes the argument a little bit more involved - will amend this now. $\endgroup$ – Vladimir Dotsenko Nov 29 '18 at 10:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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