Size of the smallest matrix satisfying $vA^k=v$ and $vA^i \neq v$ for all $i=1\dots k-1$

Question

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.

Answer 1

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

Answer 2

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.