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

  • 2
    $\begingroup$ How close is this to asking whether solvability of diophantine equations in homogeneous polynomials is decidable? $\endgroup$ – Andrej Bauer Dec 19 '18 at 15:03
  • 2
    $\begingroup$ How close? this is just finding a much harder problem, that is undecidable. Linear algebra is simpler than algebraic geometry. $\endgroup$ – YCor Dec 19 '18 at 16:45
  • 7
    $\begingroup$ 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. $\endgroup$ – François Brunault Dec 19 '18 at 21:22

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.

Browse other questions tagged or ask your own question.