13
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ How close is this to asking whether solvability of diophantine equations in homogeneous polynomials is decidable? $\endgroup$
    – Andrej Bauer
    Commented Dec 19, 2018 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
    Commented Dec 19, 2018 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
    Commented Dec 19, 2018 at 21:22

0

Reset to default

You must log in to answer this question.