1
$\begingroup$

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.
  • 0
    @Arturo Thanks for pointing out the typo with the number of Bs..corrected that.2011-03-25

3 Answers 3

1

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.

  • 0
    @Jack: It seems reasonable to expect there to be such matrices; it just isn't clear that there will be.2011-03-25
1

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

  • 0
    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.2011-03-25
1

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.

  • 0
    Douglas didn't give a complete answer and I gave a link that works out the complete answer.2011-03-31