The Order of the Matrix

If $k$ is the order of $A$ , then the minimum polynomial $m(X)$ of $A$ must divide $X^k-1$ . Since $X^k - 1 \; = \; \prod_{j | k} \Phi_j(X)$ we deduce that $m(X)$ must be a product of cyclotomic polynomials $m(X) \; = \; \Phi_{j_1}(X)\Phi_{j_2}(X) \cdots \Phi_{j_m}(X)$ where $1 \le j_1 < j_2 < \cdots < j_m$ and $j_1,j_2,\ldots,j_m$ are all divisors of $k$ . Since $k$ is the order of $A$ , no smaller power of $A$ is equal to the identity $I$ , and hence $m(X)$ does not divide $X^j - 1$ for any $j < k$ . Thus we deduce that the least common multiple of $j_1,j_2,\ldots,j_m$ is equal to $k$ .

On the other hand, $A$ is a $6\times6$ matrix, and hence $m(X)$ divides the characteristic polynomial $\chi(X)$ of $A$ , which has degree $6$ . Since $\Phi_j(X)$ has degree $\varphi(j)$ for any $j \in \mathbb{N}$ , we deduce that $\varphi(j_1) + \varphi(j_2) + \cdots + \varphi(j_m) \le 6$ .

The positive integers $k$ for which $\varphi(k) \le 6$ are $1,2,3,4,5,6,7,8,9,10,12,14,18$ , with $\begin{array}{|c|c|} \hline \varphi(k) & k \\ \hline 1 & 1,2 \\ 2 & 3,4,6 \\ 4 & 5,8,10,12 \\ 6 & 7,9,14,18 \\ \hline \end{array}$ Possible values for $m(X)$ , and matching values for the order $k$ , are: $\begin{array}{|c|c|c|} \hline \mbox{Degree} & m(X) & k \\ \hline 1 & \Phi_1,\Phi_2 & 1,2 \\ \hline 2 & \Phi_3,\Phi_4,\Phi_6,\Phi_1\Phi_2 & 3,4,6,2 \\ \hline 3 & \begin{array}{c} \Phi_1\Phi_3,\Phi_1\Phi_4,\Phi_1\Phi_6 \\ \Phi_2\Phi_3,\Phi_2\Phi_4,\Phi_2\Phi_6 \end{array} & \begin{array}{c}3,4,6\\6,4,6\end{array} \\ \hline 4 & \begin{array}{c} \Phi_5,\Phi_8,\Phi_{10},\Phi_{12} \\ \Phi_3\Phi_4,\Phi_3\Phi_6,\Phi_4\Phi_6 \\ \Phi_1\Phi_2\Phi_3,\Phi_1\Phi_2\Phi_4,\Phi_1\Phi_2\Phi_6 \end{array} & \begin{array}{c} 5,8,10,12 \\ 12,6,12 \\ 6,4,6 \end{array} \\ \hline 5 & \begin{array}{c} \Phi_1\Phi_5,\Phi_1\Phi_8,\Phi_1\Phi_{10},\Phi_1\Phi_{12} \\ \Phi_2\Phi_5,\Phi_2\Phi_8,\Phi_2\Phi_{10},\Phi_2\Phi_{12} \\ \Phi_1\Phi_3\Phi_4,\Phi_1\Phi_3\Phi_6,\Phi_1\Phi_4\Phi_6 \\ \Phi_2\Phi_3\Phi_4,\Phi_2\Phi_3\Phi_6,\Phi_2\Phi_4\Phi_6 \end{array} & \begin{array}{c} 5,8,10,12\\10,8,10,12\\12,6,12\\12,6,12 \end{array} \\ \hline 6 & \begin{array}{c} \Phi_7,\Phi_9,\Phi_{14},\Phi_{18} \\ \Phi_3\Phi_5,\Phi_3\Phi_8,\Phi_3\Phi_{10},\Phi_3\Phi_{12} \\ \Phi_4\Phi_5,\Phi_4\Phi_8,\Phi_4\Phi_{10},\Phi_4\Phi_{12} \\ \Phi_6\Phi_5,\Phi_6\Phi_8,\Phi_6\Phi_{10},\Phi_6\Phi_{12} \\ \Phi_1\Phi_2\Phi_5,\Phi_1\Phi_2\Phi_8,\Phi_1\Phi_2\Phi_{10},\Phi_1\Phi_2\Phi_{12} \\ \Phi_3\Phi_4\Phi_6 \\ \Phi_1\Phi_2\Phi_3\Phi_4,\Phi_1\Phi_2\Phi_3\Phi_6,\Phi_1\Phi_2\Phi_4\Phi_6 \end{array} & \begin{array}{c} 7,9,14,18 \\ 15,24,30,12\\ 20,8,20,12\\30,24,30,12 \\10,8,10,12\\12\\12,6,12 \end{array} \\ \hline \end{array}$ Thus the largest possible value of $k$ is $30$ , and it is obtained with any one of $\Phi_3(X)\Phi_{10}(X)$ , $\Phi_6(X)\Phi_5(X)$ and $\Phi_6(X)\Phi_{10}(X)$ as minimum polynomial.

It remains to show that a $6\times6$ matrix can be found with the desired minimum polynomial. Considering companion matrices, the matrix $\left( \begin{array}{cccccc} 0 &-1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -1 \\ 0 & 0 & 1 & 0 & 0 & -1 \\ 0 & 0 & 0 & 1 & 0 & -1 \\ 0 & 0 & 0 & 0 & 1 & -1 \end{array} \right)$ has minimum and characteristic polynomial $\Phi_6(X)\Phi_5(X)$ , and hence has order $30$ .