Given a square matrix $A\in k^{n\times n}$ and a vector $x\in k^n$ over some field $k$, is there an algorithm to test whether there are $s\in\mathbb{N}$ and $\lambda\in k$ such that $A^sx=\lambda x$? In other words, is there an algorithm to check whether $x$ is an eigenvector of some power of the matrix $A$?
By a change of basis we may assume without loss of generality that $x=e_1$. An algorithm for a fixed field, say $k=\mathbb{Q}$, would also help a lot! Thanks for your answers.
Let $f(T)$ be the monic polynomial of smallest degree such that $f(A)x=0$ (which is cheap to compute if $n$ isn't too big.) Then $A^sx=\lambda x$ if and only if $f(T)$ divides $T^s-\lambda$.
So a necessary condition is that $f(T)$ has all roots of same length.
To obtain a necessary and sufficient condition, in the case $k=\mathbb Q$, requires some number theory and (symbolic) algebra: Let $\alpha$ be a root of $f(T)$. Set $g(T)=\alpha^{\deg f}f(T/\alpha)$. So one has to decide if $g(T)$ divides $T^s-1$ for some $s$. In order to do so, one can compute the product $G(T)$ of all the Galois conjugates of $g(t)$. Note that $G(T)\in\mathbb Q[T]$ is monic. If one of the coefficients of $G(T)$ isn't an integer, then $G(T)$ never divides $T^s-1$. So assume that $G(T)\in\mathbb Z[T]$.
At this stage one could use a theorem by Kronecker, which says that all roots of $G(T)$ are roots of unity if and only if all complex roots of $G(T)$ are on the unit circle. Algebraically, this might be a little difficult to decide.
An alternative therefore is: For each irreducible factor $F(T)$ of $G(T)$, we need to decide if $F(T)$ divides some $T^s-1$. But that is equivalent to $F(T)$ being a cyclotomic polynomial. For $m=\deg F(T)$ there are only finitely many (and computable) $s\in\mathbb N$ such that $\phi(s)=m$ ($\phi$ is Euler's totient function). For each of these $s$ check if $F(T)$ is the $s$-th cyclotomic polynomial.
