Set of integer matrices $A$ such that $(A^k)_{k\in\mathbb{N}}$ is eventually periodic

Question

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}$?

Answer 1

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