# 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? Or is it impossible.

• What is the “rotation matrix of dimension $k\times k$”? – José Carlos Santos Oct 5 '18 at 10:58
• I edited the question. – cssstyler Oct 5 '18 at 11:11

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. Here $$n=\phi(k) < k$$.

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