Size of the smallest matrix satisfying $vA^k=v$ and $vA^i \neq v$ for all $i=1\dots k-1$ Suppose that the following holds for a rational matrix $A$ and a vector $v$.
\begin{align*}
vA &\neq v \\
vA^2 &\neq v \\
&\vdots  \\
vA^{k-1} &\neq v \\
vA^k &= v
\end{align*}
If A is a rotation matrix of dimension $k \times k$, then this is possible.
For example for $v=[1~ 0 ~0]$ and $A= \left [ \begin{matrix} 
0 &1& 0\\
0 &0& 1\\
1 & 0 & 0
\end{matrix} \right ]$, $vA\neq v$, $vA^2 \neq v$ and $vA^3=v$.
Can we find a $ n \times n $ matrix satisfying the above equations where $n<k$? Or is it impossible. 
 A: The companion matrix $A$ of the 6th cyclotomic polynomial $\Phi_6(x) = x^2 - x + 1$ is a $2\times 2$ matrix that has integer entries and satisfies $A^6=I$, $A^j\ne I$ for $j<6$:
$$
A=\pmatrix{0&-1\\1&\hphantom- 1}
$$
In general, the companion matrix $A$ of the $k$-th cyclotomic polynomial  is an $n\times n$ matrix with integer entries such that $A^k=I$, $A^j\ne I$ for $j<k$. Here $n=\phi(k) < k$.
A: This is not a complete solution, but it shows that at least in most cases, you can find a matrix of smaller dimension.
Note that being a rational matrix is the main obstacle; with real matrices $n=2$ would always work (and with complex matrices, even $n=1$ works, just put the $k$-th root of $1$ in the only matrix element).
First, let's consider the case that $k$ is divisible by at least two different primes; that is, you can write it as
$$k = \prod_{j=1}^m p_j^{e_j}$$
where $m\ge 2$, the $p_j$ are primes with $p_i\ne p_j$ for $i\ne j$, and $e_j\ge 1$ for all $j$.
Then you can construct a matrix of dimension
$$n = = \sum_{j=1}^m p_j^{e_j}$$
by just forming the direct sum of the permutation matrices for the cyclic permutations of $p_j^{e_j}$ elements, and a vector which is the direct sum of the corresponding vectors $\pmatrix{ 1 & 0 & \cdots & 0}$
For example, take $k=15 = 3^1\cdot 5^1$. Then $n=8$,
$$A=\left(\begin{array}{ccccc|ccc}
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0
\end{array}\right)$$
and $v=\left(\begin{array}{ccccc|ccc}1&0&0&0&0&1&0&0\end{array}\right)$.
Note that this is not necessarily the optimal solution; for example, if $k$ is even, you can treat one factor of $2$ by adding a single $-$ sign to one of the entries of the permutation matrices. That also allows to get $n<k$ for powers of $2$, e.g. for $k=4$ we get $n=2$, $A=\pmatrix{0&-1\\1&0}$, $v=\pmatrix{1&0}$. And obviously for $k=1$, the $1\times 1$ matrix $(-1)$ works.
