Let $R$ be the finite ring of the integers modulo $q$ or $GF(2^k)$. Let $M$ be $n \times n$ matrix with entries from $R$.
Assume $N,I,J$ are integers and for $ 1 \le i \le N-1$ we have $M^i[I,J]=0$ and $M^N[I,J] \ne 0$.
Q1 How large can $N$ be in terms of $n$, can it be $\exp(Cn)$?
Second question:
For $A \in R, A \ne 0$ assume for $ 1 \le i \le N-1$ we have $M^i[I,J]=A$ and $M^N[I,J] = 0$
Q2 How large can $N$ be in terms of $n$, can it be $\exp(Cn)$?
The Cayley-Hamilton theorem tells us that for each fixed pair $I,J$ the matrix entries $M^i[I,J]$ satisfy a length $n$ linear recurrence $$M^i[I,J] = a_1M^{i-1}[I,J] + a_2 M^{i-2}[I,J] + \cdots + a_n M^{i-n}[I,J]$$ for some fixed constants $a_1, a_2, ..., a_n$. In particular this means if $M^i[I,J] = 0$ for the first $n$ values of $i$ then $M^i[I,J] = 0$ for all $i$, and if $M^i[I,J] = A$ for the first $n+1$ values of $i$ then $M^i[I,J] = A$ for all $i$.
