Find $n$ for given square matrix $M$ and vectors $v,w$ in $$w=M^nv$$
Trial (updated)
(as vujazzman suggested)
Jordan normal form: $$ w = (A J^n A^{-1})v$$ $$ A^{-1}w = J^n A^{-1}v$$
After this solve $J_{i,i}^n$ for diagonal elements ($\lambda^n$) not zero or unity.
Problem: In trials with known $n$ no row was equal at left an right side for this equation. (edit: I missed a factor before result)
with numbers:
$$M=\begin{pmatrix} -6 & 0 & 1 & 1 \\ 0 & 5 & 1 & 1 \\ 1 & 0 & 4 & 0 \\ 1 & 1 & 2 & 3\end{pmatrix} $$ $$v= \begin{pmatrix}1 \\ 3 \\ 4 \\ 7 \end{pmatrix}$$ $$\text{just for testing } n=5$$
$$\rightarrow w=M^5 v = \begin{pmatrix}3069 \\ 39932 \\ 5908 \\ 23189 \end{pmatrix}$$
$$M=AJA^{-1}$$ $$A=\begin{pmatrix} -11.1983 & 0.1078 & 0.3311 & 0.0927 \\ -0.1876 & -0.3812 & -3.9066 & 2.2532 \\ 1.0992 & -0.0757 & 2.3579 & 0.0630 \\ 1 & 1 & 1 & 1\end{pmatrix}$$
$$J=\begin{pmatrix} -6.1875 & 0 & 0 & 0 \\ 0 & 2.5753 & 0 & 0 \\ 0 & 0 & 4.1404 & 0 \\ 0 & 0 & 0 & 5.4718\end{pmatrix}$$
$$A^{-1}=\begin{pmatrix} -0.0878 & -0.0009 & 0.0068 & 0.0096 \\ -0.0099 & -0.3327 & -0.8920 & 0.8068 \\ 0.039 & -0.0197 & 0.3788 & 0.0169 \\ 0.0587 & 0.3533 & 0.5064 & 0.1667\end{pmatrix}$$
$$\text{insert in } A^{-1}w = J^n A^{-1}v$$ $$\begin{pmatrix}-39.875883 \\ 121.33529 \\ 1963.52008 \\ 21144.0205 \end{pmatrix}=\begin{pmatrix} -6.1875 & 0 & 0 & 0 \\ 0 & 2.5753 & 0 & 0 \\ 0 & 0 & 4.1404 & 0 \\ 0 & 0 & 0 & 5.4718\end{pmatrix}^{n=5}\begin{pmatrix}0.0044 \\ 1.0712 \\ 1.6136 \\ 4.3108 \end{pmatrix}$$ now (just for testing) computed with $n=5$ $$\begin{pmatrix}-39.875883 \\ 121.33529 \\ 1963.52008 \\ 21144.0205 \end{pmatrix}=\begin{pmatrix}-39.875883 \\ 121.33529 \\ 1963.52008 \\ 21144.0205 \end{pmatrix} \text{ q.e.d.}$$
Now its working...
To be complete: computing of $n$ if not known $$21144.0205/4.3108=5.4718^n$$ $$\log_{5.4718}(4904.894799)=\log(4904.894799)/\log(5.4718)=n$$ $$\rightarrow n=5$$
Lets first make a weak assumption on $M$, lets suppose it has an eigenvalue $\lambda$ which is not zero or a root of unity. In this case, $n$ can be determined (or determined not to exist), by taking the Jordan normal form of $M = AJA^{-1}$ and considering the resulting equation $A^{-1}w = J^n (A^{-1}v)$. There is a row of $J^n$ consisting of $\lambda^n$ in one entry and the rest zeros. Due to the conditions on $\lambda$, there will be at most one solution for $n$. If there is a solution, check it in the original equation. In this case $n$ is the unique solution. Otherwise, there is no solution.
If $M$ doesn't satisfy the condition, the situation is more complicated, but in any case you still want to first reduce the problem by taking the Jordan decomposition. Enumerating all what can happen is probably still possible, you essentially need to answer the original problem for $M$ a Jordan block with root of unity or zero eigenvalue.