2
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.