Skip to main content

Section 18.2 Discovery guide

Discovery 18.1. Fixed sets for \(S_n\).

The elements of the symmetric group \(S_n\) are defined by their action on the set

\begin{equation*} X = \{ 1, 2, 3, \dotsc, n \} \text{.} \end{equation*}

(a)

Suppose you have an element \(p\) of \(S_n\) expressed as a product of disjoint cycles. How can you tell the fixed set \(X^p\) just from this expression?

(b)

Recall that we can tell whether two elements of \(S_n\) are conjugate by writing each of the two permutations as a product of disjoint cycles and then comparing their cycle structures. Looking back at Discovery 14.7, determine the relationship between the fixed sets \(X^p\) and \(X^q\text{,}\) and the “transition” element \(g\) obtained in that activity to realize the conjugacy relation \(q = \inv{g} p g\text{.}\)

Discovery 18.2. Fixed sets of conjugate elements.

(a)

Based on the pattern in Task b of Discovery 18.1, make a conjecture about the abstract pattern for fixed sets under conjugate elements when a group \(G\) acts on a set \(X\text{:}\)

If \(a,b\) are conjugate group elements and \(g\) is a group element that realizes the conjugacy relation \(a = \inv{g} b g\text{,}\) then the relationship between elements in the fixed sets \(X^a\) and \(X^b\) is .

Then try to prove your conjecture.

(b)

For a finite group acting on a finite set, what does Task a say about the sizes of the fixed sets \(X^a\) and \(X^b\) when group elements \(a\) and \(b\) are conjugate?

Discovery 18.3.

Consider the alphabet

\begin{equation*} \Sigma = \{ \mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}, \mathrm{e}, \mathrm{x}, \mathrm{y}, \mathrm{z} \} \text{.} \end{equation*}

Using a bijection between \(\Sigma\) (in the order listed) and the set

\begin{equation*} \{1,2,3,4,5,6,7,8\}\text{,} \end{equation*}

we obtain an action of \(S_8\) on \(\Sigma\text{.}\) For example, the three-cycle \(\threecycle{1}{5}{8}\) becomes \(\threecycle{\mathrm{a}}{\mathrm{e}}{\mathrm{z}}\) instead.

This action of \(S_8\) on \(\Sigma\) induces an action of \(S_8\) on the set \(X\) of all possible \(8\)-letter words that can be made from the alphabet \(\Sigma\) without repeating letters. For example, for \(p = \threecycle{1}{5}{8}\text{,}\) we have

\begin{equation*} \grpact{p}{ \mathrm{z} \mathrm{b} \mathrm{c} \mathrm{d} \mathrm{x} \mathrm{y} \mathrm{e} \mathrm{a} } = \mathrm{a} \mathrm{b} \mathrm{c} \mathrm{d} \mathrm{x} \mathrm{y} \mathrm{z} \mathrm{e}\text{,} \end{equation*}

so that where ever \(\mathrm{a}\) appears in the word it turns into \(\mathrm{e}\text{,}\) where ever \(\mathrm{e}\) appears in the word it turns into \(\mathrm{z}\text{,}\) where ever \(\mathrm{z}\) appears in the word it turns into \(\mathrm{a}\text{,}\) and all other letters are left unchanged.

(a)

How many \(8\)-letter words from alphabet \(\Sigma\) with no repeated letters are possible? That is, how many words does \(X\) contain? How does this compare to the order of \(S_8\text{?}\)

(b)

How many different orbits are there? (A group action with this property is called transitive.)

Discovery 18.4.

Continue with the same alphabet \(\Sigma\) and set of \(8\)-letter words \(X\) as in Discovery 18.3, but now we will restrict our attention to the action of a subgroup \(G\) of \(S_8\) on \(X\text{.}\) Let \(H\) represent the subgroup of \(S_8\) consisting of those permutations that only permute \(1,2,3,4,5\) and leave \(6,7,8\) fixed (though some of those first five numbers might be fixed as well), and let \(K\) represent the subgroup of \(S_8\) consisting of those permutations that only permute \(6,7,8\) and leave \(1,2,3,4,5\) fixed (though again some of \(6,7,8\) might be fixed as well). Then take

\begin{equation*} G = H K \isoto H \times K \isoto S_5 \times S_3 \text{.} \end{equation*}

(a)

How many elements does each orbit under the action of \(G\) contain? How does this compare to the order of \(G\text{?}\)

(b)

Combine your answer to Task a of Discovery 18.3 with your answer to Task a of this activity to determine how many orbits there are under the action of \(G\) on \(X\text{.}\)

In AUMAT 250 Discrete Mathematics we learn (without explicit use of group theory) that the answer to Task b of Discovery 18.4 is the same as the answer to the question “How many bytes contain exactly five zeros and three ones?” We do this by giving such a binary word “extra structure” to help us count: we might temporarily label the five zeros as

\begin{equation*} 0_{\mathrm{a}}, 0_{\mathrm{b}}, 0_{\mathrm{c}}, 0_{\mathrm{d}}, 0_{\mathrm{e}} \end{equation*}

and the three ones as

\begin{equation*} 1_{\mathrm{x}}, 1_{\mathrm{y}}, 1_{\mathrm{z}} \text{.} \end{equation*}

Then in any given word containing these eight symbols, we may permute the zeros in place (that is, permute the set \(\{ \mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}, \mathrm{e} \} \)) and permute the ones in place (that is, permute the set \(\{ \mathrm{x}, \mathrm{y}, \mathrm{z} \} \)) without actually changing the pattern of zeros and ones in the byte.

In other problems, it is much more difficult to count the number of orbits when the orbits do not all have the same size. A common strategy in mathematics is to attempt to count something in two different ways, leading to some sort of equality. In this case, we will attempt to count the number of pairs of a group element \(g\) and a set element \(x\) with the property that \(\grpact{g}{x} = x\text{.}\) The two ways to do this are to count the stabilizer \(G_x\) for each set element \(x\) one-by-one, or to count the fixed set \(X^g\) for each group element \(g\) one-by-one. Let's explore the patterns that arise from this double-counting in a simple example where we can easily check our results.

Discovery 18.5.

We have seen before that \(S_3\) is isomorphic to a subgroup of \(\GL_3(\R)\) by associating each element of \(S_3\) to the corresponding permutation matrix (though at the time we did not have the concept of isomorphism to use to describe the situation).

Using this isomorphism, we may take \(S_3\) to act on the set

\begin{equation*} X = \left\{ \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \left[\begin{array}{r} 0 \\ 1 \\ -1 \end{array}\right], \left[\begin{array}{r} 0 \\ -1 \\ 1 \end{array}\right], \left[\begin{array}{r} 1 \\ 0 \\ -1 \end{array}\right], \left[\begin{array}{r} 1 \\ -1 \\ 0 \end{array}\right], \left[\begin{array}{r} -1 \\ 0 \\ 1 \end{array}\right], \left[\begin{array}{r} -1 \\ 1 \\ 0 \end{array}\right] \right\} \end{equation*}

by matrix multiplication. The effect is to permute the coordinates of each vector; for example, if \(p = \twocycle{1}{2}\) then

\begin{equation*} p\left(\left[\begin{array}{r} 0 \\ 1 \\ -1 \end{array}\right]\right) = \left[\begin{array}{r} 1 \\ 0 \\ -1 \end{array}\right] \end{equation*}

(a)

Partition \(X\) into the orbits under the described action of \(S_3\text{.}\) What is the number of orbits and the size of each orbit?

(b)

Determine the size of the stabilizer of each element in \(X\text{.}\) Don't forget the identity permutation!

(c)

Let \(N\) represent the number of pairs of a permutation \(p\) and a set element \(x\) so that \(p(x) = x\text{.}\) Now that we know the size of each stabilizer, we can express \(N\) as a sum of the sizes of the stabilizers — do this, with the ten numbers in the sum grouped in brackets by orbit.

Each set of brackets should contain a number of repeats of the same number added together — why did this happen?

Hint.

See Task b of Discovery 17.9.

(d)

Use the Orbit-Stabilizer Theorem to replace each number in your sum from Task c with a fraction (though in at least one instance the denominator will be \(1\)). Each of these fractions should have the same numerator.

Even more, each fraction within a set of brackets should have the same denominator, and this denominator should be the same as the number of terms in that set of brackets. Why did this happen?

(e)

Since the sum in each set of brackets contains the same number of terms as the common denominator in that set of brackets, you can simplify (rather than compute) each set of brackets in your result from Task d, leaving you with a single number in each set of brackets. In fact, each set of brackets should contain the same number as every other set of brackets. What does this number in each set of brackets represent again? And what does the number of numbers represent? (That is, why did we set up these brackets in the first place?)

(f)

Now let's count \(N\) the other way — for each permutation \(p\) in \(S_3\text{,}\) determine the size of the fixed set \(X^p\text{,}\) and verify that these sizes add up to the same total as your sums for \(N\) is the previous tasks in this activity.

(g)

Your final expression for \(N\) as a sum in Task e no longer requires knowing the size of each stabilizer. Think about how this expression could be combined with the total from Task f to “solve” for the number of orbits.

Discovery 18.6.

Now let's recover the overall pattern of Discovery 18.5. Consider the abstract situation of a finite group \(G\) acting on a finite set \(X\text{.}\)

(a)

Fill in the pattern: The number of orbits in \(X\) is equal to the sum of divided by .

Hint.

You should base your answer on the pattern in Task g of Discovery 18.5.

(b)

How many terms will there be in the sum mentioned in Task a?

Based on this, we can revise the pattern from Task a: The number of orbits in \(X\) is equal to the of .

(The second blank here should essentially be filled with the same answer as the first blank in Task a.)

(c)

Further refine your answer to Task a of this activity by incorporating the knowledge gained in Task b of Discovery 18.2 to reduce the number of terms in the sum.

Discovery 18.7.

Note: This problem is taken from the textbook, so if you get stuck you can read about it there afterwards.

Cut a strip of paper. On each side of the strip, draw four dividing lines across the width of the strip to create five squares. (Here we refer to the short dimension of the strip as the width. Don't worry if your divisions have created rectangles instead of squares.) Number the squares on one side from 1 to 5, then flip over and number from 6 to 10, with 6 on the underside of the “same” square as 1. Give the strip a half-twist and then tape the ends together — you now have a Möbius band! Your numbering should now run continuously from 1 to 10 and then start over at 1.

When holding the strip, one “end” should be in a horizontal orientation while the “opposite end” twists into a vertical orientation. We can obtain an order-\(2\) symmetry of the shape by rotating \(180\) degrees about the axis through these two “ends”. We can also obtain an order-\(10\) symmetry by “rotating” the squares so that each shifts to its neighbour's position. (See Figure 18.3 in the textbook if you are unsure about these descriptions.)

So the symmetry group of this divided Möbius band is isomorphic to \(D_{10}\text{.}\) Take \(X\) to be the set of painted Möbius bands where we permit ourselves three colours and paint each square a solid colour. Once the numbers are painted over, we will not be able to tell one band from another if the second can be obtained from the first by symmetries. So while the size of \(X\) is \(3^{10}\text{,}\) the number of “different” bands is a smaller number — it is the number of orbits in \(X\) under the described action of \(D_{10}\text{.}\)

Use what you learned in Discovery 18.6 to figure out the number of different bands possible.

Hint.

To cut down on the calculations, you may wish to use the pattern from Task c of Discovery 18.6 in particular. The conjugacy classes of \(D_{10}\) are:

  • the identity all by itself;

  • pairs of a power of \(r\) with its inverse (though this puts \(r^5\) in a class by itself);

  • all results of an even power of \(r\) times \(s\) (including \(r^0 s = s\)); and

  • all results of an odd power of \(r\) times \(s\text{.}\)