# Is the set of power matrices decidable?

Let $$\text{Mat}(n\times n,\mathbb{Z})$$ denote the collection of integer $$n\times n$$ matrices. We say $$M\in \text{Mat}(n\times n,\mathbb{Z})$$ is a power matrix if there is an integer $$k>1$$ and a matrix $$A\in \text{Mat}(n\times n,\mathbb{Z})$$ such that $$A^k = M$$. Let $$\text{Pow}(n\times n,\mathbb{Z})$$ denote the set of $$n\times n$$ power matrices.

Is the set $$\text{Pow}(n\times n,\mathbb{Z})$$ computable for every positive integer $$n$$?

• How close is this to asking whether solvability of diophantine equations in homogeneous polynomials is decidable? – Andrej Bauer Dec 19 '18 at 15:03
• How close? this is just finding a much harder problem, that is undecidable. Linear algebra is simpler than algebraic geometry. – YCor Dec 19 '18 at 16:45
• It is not hard to bound the coefficients of the characteristic polynomial $\chi_A$ in terms of $M$ alone, so there are only a finite number of possibilities for $\chi_A$. Also, if the logarithmic Mahler measure $m(\chi_M)$ is $>0$ (which amounts to say $\chi_M$ is not a product of cyclotomic polynomials), then we can also bound $k$, because $m(\chi_M) = k m(\chi_A)$ and there is a lower bound for the Mahler measure of a polynomial of degree $n$ with integer coefficients. – François Brunault Dec 19 '18 at 21:22