# Counting number of sequences under cyclic permutation

If I have say $2$ A matrices, $2$ B matrices and $1$ C matrix then I would like to know how many distinct traces of products of all of them can be formed.

Assume that $A$, $B$ and $C$ don't commute with each other.

Like $AABBC$, $CAABB$ and $BCAAB$ are distinct products which will have the same trace but $ABABC$ has a different trace.

I would like to know how to count the number of products upto having the same trace.

• Though I don't need it at this point I would be curious to know how the problem might get complicated if one assumes any or more of the pair of matrices commute.
-
Your title does not reflect your question. – lhf Mar 25 '11 at 15:46
If two words are not cyclically related, does that mean their traces are different or could be different? – Douglas Zare Mar 25 '11 at 16:06
Note that your examples don't match the original restrictions (they have only two $A$s, two $B$s, and one $C$). – Arturo Magidin Mar 25 '11 at 16:17
If we consider only the equivalence of strings under cyclic permutations, counting the distinct equivalence classes is a type of necklace problem. If certain matrices commute, then this would create additional equivalences, complicating the counting. – hardmath Mar 25 '11 at 16:24
@Arturo Thanks for pointing out the typo with the number of Bs..corrected that. – Anirbit Mar 25 '11 at 20:32

## 3 Answers

It sounds like you want the orbit counting theorem, also known as Burnside's lemma.

If there is no common factor to the number of matrices of each type, such as when there is only one matrix of type C, then there will be no nontrivial cyclic symmetry so the number of products up to cyclic symmetry will be ${n\choose \#A,\#B,\#C}/n$.

-
In the instant example (2A's,3B's,1C) the position of the C fixes a cycle, so that what results is a count of $\binom{5}{2}$ choices for the remaining positions of A. Of course not much can be said about the distinctness of traces without more explicit information about the matrices. – hardmath Mar 25 '11 at 16:31

If you want to count the number of sequences with a fixed number of different types of letters up to cyclic permutation (words that are not guaranteed to have the same trace), then a complete answer is provided by the Polya(-Redfield) enumeration theorem, which is a corollary of Burnside's lemma.

-
@Qiachu Apologies for being naive. But how is what you are saying different from that of Douglas' answer? Is the difference that you are not assuming the number of matrices of each type to be co-prime to each other as him? – Anirbit Mar 31 '11 at 7:56
Douglas didn't give a complete answer and I gave a link that works out the complete answer. – Qiaochu Yuan Mar 31 '11 at 18:26

Edited since the problem has changed slightly.

Note that it is not necessarily the case that $ABABC$ will have different trace from $AABBC$; it's just that they are not guaranteed to have the same trace.

So, you want to count the number of distinct words, modulo an equivalence relation that identifies two words if they are cyclical permutations of each other.

The number of distinct words with two $A$'s, two $B$s, and one $C$ is $$\frac{5!}{2!2!1!} = 30$$ (the number of ways of ordering $5$ elements; divided by $2!$ to account for the three $A$s, and by $2!$ for the two $B$s).

Each word has five cyclic permutations; can two of them be equal? No: since there is only one $C$, the position of $C$ changes after every cyclical permutation. So each word has five distinct cyclic permutations. That means that the equivalence classes of the 30 words under cyclical permutation have five elements each, and therefore there are exactly 6 equivalence classes.

So there are at most 6 possible distinct values for the trace of a product of all five matrices. However, they need not be all distinct (that will depend on the matrices). But the upper bound for the number of distinct traces is six.

It is not clear to me, however, that given two words that are not cyclic permutations of each other, we will be able to find matrices $A$, $B$, and $C$ such that the trace of the corresponding products are different, or even if we can find matrices that will produce six distinct traces this way.

Here, the fact that there is only one $C$ makes things simpler. More generally, you would need to consider whether there are any "repeats" among the cyclic permutations. E.g., if the problem had two of each, so that the number of distinct words would be $\frac{6!}{2!2!2!} = 90$, then some classes would have fewer than six distinct products: the class of $ABCABC$ only has three distinct cyclic permutations.

If some of the matrices commute, then you would need to consider a weaker equivalence relation between products; e.g., if $C$ commutes with $A$, then the words $ABCAB$ and $ABACB$ are "equivalent", which would coalesce the two equivalence classes you already have. You'd want to use something like the Orbit Counting Lemma mentioned by Douglas.

-
It is not clear to me (although I am willing to believe this) that if two words are not guaranteed to have the same trace then we can actually find matrices such that the corresponding products don't have the same trace. – Qiaochu Yuan Mar 25 '11 at 20:37
@Qiaochu: It is not clear to me either; that's why I said "at most". For that matter, it is not clear to me that you can find matrices that realize all the distinct possibilities at the same time (which is a stronger statement than matrices that distinguish two given distinct non-cyclically-equivalent words). – Arturo Magidin Mar 25 '11 at 20:41
If it helps, I had no trouble finding three GL(2,Z) matrices {A,B,C} that simultaneously realize all 6 {2,2,1} and all 10 {2,3,1} and all 16 {2,2,2}. Probably there is no real obstruction if there are enough possible values for the trace. Of course GL(n,2) doesn't work, as there are only two scalars for traces! However, GL(2,23) is fine. – Jack Schmidt Mar 25 '11 at 21:19
@Jack: It seems reasonable to expect there to be such matrices; it just isn't clear that there will be. – Arturo Magidin Mar 25 '11 at 21:23