A group orbit/Burnside's lemma question

Question

Consider a set $X$ of $9$ dots arranged in a $3 \times 3$ grid. Let $H$ be the group generated by the permutations on the rows of $X$ and by the permutations on the columns of $X$.

I am asked:

1. How many elements are in $H$?
2. What cycle types appear in $H$?
3. How many elements in $H$ belong to each cycle type?
4. If the $9$ elements in $X$ are colored $3$ each red, white and blue, how many ways can we color $X$, where two colorings are the same if we can move from one coloring to another through operations in $H$?

I have only a few ideas:

1. The group $H$ will be something like $S_3 \times S_3$, because we can permute rows and columns, so that should give me 36 elements in $H$.

2. This clearly looks like I'm supposed to apply Burnside's Lemma. The group acting will be $H$. But I'm not too sure about the rest. I need to count the number of fixed points for every element in $H$.

Thanks.

Answer 1

Welcome to MSE!

You're exactly right that this is a job for Burnside's Lemma. In fact, as is mentioned in the comments, steps $1$, $2$, and $3$ are more or less guiding you towards the use of Burnside's Lemma.

For $1$, you already found the right group. $H = S_3 \times S_3$ works (though you might want to justify to yourself that permuting rows then permuting columns is really the same thing as permuting columns then rows). You also correctly see that $|H| = 36$. So this is a strong start!

For $2$, it sounds like there's a lot of computation you need to do, but notice that, as far as cycle types are concerned, there's really only a few things you can do. Each element of $S_3$ is either the identity, a transposition, or a $3$-cycle. This means each element of $S_3 \times S_3$ is a product of such things. Since there's row/column symmetry as well, you can actually break this down into the following cases. Here $1$ is the identity, $\tau$ is a transposition, and $\sigma$ is a $3$-cycle:

• $(1, 1)$
• $(1, \tau)$
• $(1, \sigma)$
• $(\tau, \tau)$
• $(\tau, \sigma)$
• $(\sigma, \sigma)$

You should convince yourself that every element of $S_3 \times S_3$ has the same cycle structure as one of these. Then you can compute the cycle structure by using, say, $\tau = (1 \ 2)$ and $\sigma = (1 \ 2 \ 3)$ as concrete examples.

For $3$, you want to try to see how many group elements fall into each of the $6$ categories above. Keep in mind the answers should sum to $36$, since that's how many total group elements there are in $H$.

Finally, for $4$, we apply Burnside's Lemma. For each of the $6$ categories above, how many fixed points are there? That is, how many colorings stay the same after you apply a permutation from that category? Here you'll again want to work with the concrete example $\tau = (1 \ 2)$ and $\sigma = (1 \ 2 \ 3)$. Remember every element in a cycle (where now we're viewing $H$ as a subgroup of $S_9$ acting on all of $X$) has to get the same color! So we expect $3^{\text{number of cycles}}$ many fixed points.

Now what does Burnside's Lemma tell us?

The number of orbits (which is what you're looking for) is the average number of fixed points

So the answer to your problem will be

$$\frac{1}{36} \sum_g 3^{\text{number of cycles in $g$}}$$

But the $6$ categories we identified all have the same number of cycles. And we figured out in part $3$ how many $g$ belong to each category. So we can split this sum up based on which category we're in (call them $C_1, \ldots, C_6$) and find:

$$ \frac{1}{36} \left ( \sum_{C_1} 3^{\text{number of cycles in $(1,1)$}} + \sum_{C_2} 3^{\text{number of cycles in $(1, \tau)$}} + \ldots + \sum_{C_6} 3^{\text{number of cycles in $(\sigma, \sigma)$}} \right ) $$

But we know that the number of cycles is the same in each of these sums, so we can turn our repeated addition into multiplication. We find the number of distinct colorings is

$$ \frac{1}{36} \left ( |C_1| 3^{\text{number of cycles in $(1,1)$}} + |C_2| 3^{\text{number of cycles in $(1, \tau)$}} + \ldots + |C_6| 3^{\text{number of cycles in $(\sigma, \sigma)$}} \right ) $$

where you'll know $|C_i|$ from part $3$ and "number of cycles in $-$" from playing around with the categories you found in part $2$.

---

As an aside, you can also get a computer algebra system like sage to do most of this heavy lifting (such as computing cycle decompositions, etc.) for you. See here for some relevant documentation.

---

I hope this helps ^_^

Answer 2

Maybe I can help with some data. I would not attack this problem with pen and paper but use a CAS to assist as was suggested already. A very similar problem appeared at MSE at the following MSE link where the symmetric group was paired with the cyclic one instead of the another instance of the symmetric group. The latter post computes the cycle index, which answers your question about the number of elements, the cycle types and the number of elements of each cycle type. More importantly, it also explains the algorithm to compute the cycle index. I have implemented this algorithm in Maple for $n\times m$ boards. We get for the 3x3 case the following cycle index, which you may use to check your work:

$$Z(P_{3,3}) = 1/36\,{a_{{1}}}^{9}+1/6\,{a_{{1}}}^{3}{a_{{2}}}^{3} +1/4\,a_{{1}}{a_{{2}}}^{4}+2/9\,{a_{{3}}}^{3} +1/3\,a_{{3}}a_{{6}}.$$

This says that e.g. there are twelve instances of cycle type $a_3 a_6.$ Once we have the cycle index we may use the Polya Enumeration Theorem (PET) to compute the number of non-isomorphic colorings. This is the same as Burnside which requires the colors to be constant on each cycle, yielding the substitution $a_d = R^d + W^d + B^d$, corresponding to a red, a white and a blue cycle respectively. Here is an excerpt from the substituted cycle index for a 3x3 board:

$$\cdots+6\,{B}^{3}{R}^{6}+17\,{B}^{3}{R}^{5}W+ 43\,{B}^{3}{R}^{4}{W}^{2} \\ +54\,{B}^{3}{R}^{3}{W}^{3}+43\,{B}^{3}{R}^{2}{W}^{4} +17\,{B}^{3}R{W}^{5}+6\,{B}^{3}{W}^{6}+\cdots$$

This means that there are $54$ colorings using three instances of three different colors, which you can again use to check your work. The Maple code for the case of an $n\times m$ board goes as follows:

pet_cycleind_symm :=
proc(n)
option remember;
local l;
    
    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

    polyvars := indets(poly);
    indvars := indets(ind);

    for v in indvars do
        pot := op(1, v);

        subs1 :=
        [seq(polyvars[k]=polyvars[k]^pot,
             k=1..nops(polyvars))];

        subs2 := [v=subs(subs1, poly)];

        res := subs(subs2, res);
    od;

    res;
end;


pet_cycleind_mat :=
proc(n, m)
option remember;
local rowind, colind, cind, term_a, term_b, v_a, v_b,
    len_a, len_b, inst_a, inst_b, p;

    cind := 0;

    if n=1 then
        return pet_cycleind_symm(m);
    else
        rowind := pet_cycleind_symm(n);
    fi;

    if m=1 then
        return pet_cycleind_symm(n);
    else
        colind := pet_cycleind_symm(m);
    fi;

    for term_a in rowind do
        for term_b in colind do
            p := 1;
            for v_a in indets(term_a) do
                len_a := op(1, v_a);
                inst_a := degree(term_a, v_a);

                for v_b in indets(term_b) do
                    len_b := op(1, v_b);
                    inst_b := degree(term_b, v_b);

                    p := p*a[lcm(len_a, len_b)]
                    ^(gcd(len_a, len_b)*inst_a*inst_b);
                od;
            od;

            cind := cind +
            lcoeff(term_a)*lcoeff(term_b)*p;
        od;
    od;

    cind;
end;

colors_ABC :=
proc(n, m)
option remember;
local cind;

    cind := pet_cycleind_mat(n, m);

    expand(pet_varinto_cind(A+B+C, cind));
end;

We can easily compute the cycle index for e.g. a 4x4 board, which gives

$$Z(P_{4,4}) = {\frac {{a_{{1}}}^{16}}{576}} +1/48\,{a_{{1}}}^{8}{a_{{2}}}^{4}+1/36\,{a_{{1}}}^{4}{a_{{3}}}^{4} \\ +{\frac {17\,{a_{{2}}}^{8}}{192}}+ {\frac {13\,{a_{{4}}}^{4}}{48}}+1/16\,{a_{{1}}}^{4}{a_{{2}}}^{6} +1/6\,{a_{{1}}}^{2}{a_{{3}}}^{2}a_{{2}}a_{{6}} \\ +1/9\,{a_{{3}}}^{5}a_{{1}}+1/12\,{a_{{2}}}^{2}{a_{{6}}}^{2} +1/6\,a_{{4}}a_{{12}}.$$

Remark. I just noticed that this problem (two instances of the symmetric group) appeared verbatim at the following MSE link II.