Counting Conjugacy Classes: $A^6 = I$ This question is inspired by this earlier post.  The question that I'm interested in is as follows:

Let $S= \{A \in \mathbb{Q}^{k \times k} : A^6 = I \text{ and }A^n \ne I \text{ for any }0 < n < 6\}$. How many orbits under conjugation by $GL_k(\mathbb{Q})$ does $S$ contain?

Per the argument that I've given in the linked post, it suffices to list representatives in rational canonical form.  Thus, it is equivalent to enumerate the multisets of irreducible polynomials $\{p_1,\dots,p_n\}$ (which are the polynomials corresponding to companion matrix blocks) each of which divides $x^6-1$, whose degrees sum to $k$, and whose lcm divides $x^6 - 1$ but no polynomial of the form $x^n - 1$ for $n < 6$.
Of course, there is only one such multiset in the case of $k=2$, hence the answer to the linked question.  As $k$ grows things get trickier. For $k=5$, we have
$$
\{x^2 - x + 1, x \pm 1, x \pm 1, x\pm 1\}\\
\{x^2 + x + 1, x+1, x\pm 1, x\pm 1\}\\
\{x^2 - x + 1,  x^2 \pm x + 1 ,x \pm 1\}\\
\{x^2 + x + 1, x^2 + x + 1, x+1\}\\
$$
For a total of $14$ conjugacy classes.
How might one approach this problem in general?  
 A: Please read my comments under the OP's question.  In this answer, I would like to only address the case $m=6$, that is, the situation the OP asks for.  I do not know how to deal with the general exponent $m$.  
As we have established, the characteristic polynomial involved in each indecomposable block of $A$ is one of the following four cyclotomic polynomials: $$\Phi_1(x)=x-1\,,\,\,\Phi_2(x)=x+1\,,\,\,\Phi_3(x)=x^2+x+1\,,\text{ and }\Phi_6(x)=x^2-x+1\,.$$ Now, $A$ must have at least one indecomposable block of size $2\times 2$.  Let $a$ and $b$ denote the number of $2$-by-$2$ indecomposable blocks of $A$ and the number of $1$-by-$1$ blocks of $A$.  Then, $a\geq 1$ and $2a+b=k$. Denote by $J_1,J_2,\ldots,J_a$ the $2$-by-$2$ blocks of $A$, whereas $K_1,K_2,\ldots,K_b$ the $1$-by-$1$ blocks.  We may assume that $J_1,J_2,\ldots,J_p$ have $\Phi_6$ as the characteristic polynomial, whereas $J_{p+1},J_{p+2},\ldots,J_a$ have $\Phi_3$ as the characteristic polynomial.  Similarly, suppose that $K_1,K_2,\ldots,K_q$ have $\Phi_2$ as the characteristic polynomial, whilst $K_{q+1},K_{q+2},\ldots,K_b$ have $\Phi_1$ as the characteristic polynomial.
If $p\geq 1$, then there is no restriction on $q$.  Thus, for each fixed $a\in\Biggl\{1,2,\ldots,\left\lfloor\dfrac{k}{2}\right\rfloor\Biggr\}$, there are $a$ ways to choose $p\geq 1$ and $b+1=k-2a+1$ ways to choose $q$.  Thus, for $p\geq 1$, there are
$$\begin{align}\sum_{a=1}^{\left\lfloor\frac{k}2\right\rfloor}\,a(k-2a+1)&=(k-1)\,\sum_{a=1}^{\left\lfloor\frac{k}2\right\rfloor}\,a-4\,\sum_{a=1}^{\left\lfloor\frac{k}2\right\rfloor}\,\frac{a(a-1)}{2}
\\
&=\frac{k-1}{2}\,\left\lfloor\frac{k}{2}\right\rfloor\,\left(\left\lfloor\frac{k}{2}\right\rfloor+1\right)-\frac{2}{3}\,\left\lfloor\frac{k}{2}\right\rfloor\,\left(\left\lfloor\frac{k}{2}\right\rfloor+1\right)\,\left(\left\lfloor\frac{k}{2}\right\rfloor-1\right)
\end{align}$$
corresponding conjugacy classes.  
If $b=0$, then $q\geq1$ is required.  Thus, for each fixed $a\in\Biggl\{1,2,\ldots,\left\lfloor\dfrac{k}{2}\right\rfloor\Biggr\}$, there are $b=k-2a$ ways to choose $q\geq 1$.  Hence, for $p=0$, there are
$$\sum_{a=1}^{\left\lfloor\frac{k}2\right\rfloor}\,(k-2a)=k\,\left\lfloor\frac{k}{2}\right\rfloor-\left\lfloor\frac{k}{2}\right\rfloor\,\left(\left\lfloor\frac{k}{2}\right\rfloor+1\right)$$
corresponding conjugacy classes.
This shows that
$$N(k,6)=\frac{1}{6}\,\left\lfloor\frac{k}{2}\right\rfloor\,\left(3\,(k-3)\,\left\lfloor\frac{k}{2}\right\rfloor-4\,\left\lfloor\frac{k}{2}\right\rfloor^2+9\,k-5\right)$$
is the total number of conjugacy classes.  We have
$$N(1,6)=0\,,\,\,N(2,6)=1\,,\,\,N(3,6)=3\,,\,\,N(4,6)=7\,,\text{ and }N(5,6)=12\,.$$
(The OP miscounted something.  From his list, there should be $12$ distinct conjugacy classes for $k=5$.)
Note that
$$\frac{(k-1)(k^2+10k-3)}{24}\leq N(k,6)\leq \frac{k(k-1)(k+10)}{24}\,.$$
The left-hand side is an equality iff $k$ is an odd positive integer.  The right-hand side is an equality iff $k=1$ or $k$ is an even positive integer.
A: If $A\in M_n(\mathbb{Q}),A^6=I$, then $A$ is diagonalizable over $\mathbb{C}$ and its eigenvalues must be chosen among $1,-1$ or the couples $(j,j^2)$ or $(-j,-j^2)$ where $j=e^{2i\pi/3}$. Since the minimal polynomials of the above eigenvalues in $\mathbb{Q}[x]$ have degree $2$, our matrices are classified by the eligible sequences with elements in the box $ 1, -1, (j, j ^ 2), (- j, -j ^ 2) $, elements encoded by $(1,2,3,4)$, ordered by $1\leq 2\leq 3\leq 4$ with $length(1)=length(2)=1,length(3)=length(4)=2$. One condition is $\sum_i length(i)=k$. 
EDIT. The other condition is $order(A)=6$, that is, EITHER the element $4$ is in the considered sequence OR the couple $2,3$ is in the sequence.
Note that the number of similar classes is the same as in $M_n(\mathbb{R})$.
For example, when $k=4$, there are $7$ eligible sequences (then $7$ similar classes)
[1, 1, 4][1, 2, 3][1, 2, 4]                          [2, 2, 3][2, 2, 4][3, 4]                             [4, 4]
A rudimentary procedure (with computer) gives explicitly the list of the similarity classes and, of course, the number of classes.
For $k=5$, there are $12$ similar classes. 
[1, 1, 1, 4][1, 1, 2, 3][1, 1, 2, 4]                          [1, 2, 2, 3][1, 2, 2, 4][1, 3, 4]                           [1, 4, 4][2, 2, 2, 3][2, 2, 2, 4]                           [2, 3, 3][2, 3, 4][2, 4, 4]
For $k=6$, $20$ classes.
For $k=7$, $29$ classes.
These results are consistent with the counting Batominovski's formula (thanks to him for pointing out an error in the previous version of my post).
