We defined the rotation group \(R_4\) and the dihedral group \(D_4\) as groups of permutations of the vertices of a square. These permutations represent rigid motions of the square in the plane and in three dimensional space respectively. The square has geometric features of interest other than its vertices; for example its diagonals, or its edges. Any geometric motion of the square that returns it to its original position takes each diagonal to a possibly different diagonal, and takes each edge to a possibly different edge. In Figure 6.2.1 we show the results on the sides and diagonals of the rotations of a square. The rotation group permutes the sides of the square and permutes the diagonals of the square as it rotates the square. Thus, we say the rotation group âactsâ on the sides and diagonals of the square.
Figure6.2.1 The results on the sides and diagonals of rotating the square
Problem279
(a)
Write down the two-line notation for the permutation \(\overline{\rho}\) that a \(90\) degree rotation does to the sides of the square.
(b)
Write down the two-line notation for the permutation \(\overline{\rho^2}\) that a 180 degree rotation does to the sides of the square.
(c)
Is \(\overline{\rho^2} = \overline\rho\circ\overline\rho\text{?}\) Why or why not?
(d)
Write down the two-line notation for the permutation \(\widehat{\rho}\) that a 90 degree rotation does to the diagonals \(d_{13}\) and \(d_{24}\) of the square.
(e)
Write down the two-line notation for the permutation \(\widehat{\rho^2}\) that a 180 degree rotation does to the diagonals \(d_{13}\) and \(d_{24}\) of the square.
(f)
Is \(\widehat{\rho^2} = \widehat{\rho}\circ\widehat{\rho}\text{?}\) Why or why not? What familiar permutation is \(\widehat{\rho^2}\) in this case?
We have seen that the fact that we have defined a permutation group as the permutations of some specific set doesn't preclude us from thinking of the elements of that group as permuting the elements of some other set as well. In order to keep track of which permutations of which set we are using to define our group and which other set is being permuted as well, we introduce some new language and notation. We are going to say that the group \(D_4\) âactsâ on the edges and diagonals of a square and the group \(R\) of permutations of the vertices of a cube that arise from rigid motions of the cube âactsâ on the edges, faces, diagonals, etc. of the cube.
Problem280
In Figure 6.1.3 we show a cube with the positions of its vertices and faces labeled. As with motions of the square, we let we let \(\varphi(x)\) be the label of the place where vertex previously in position \(x\) is now.
(a)
In Problem 263 we wrote in two row notation the permutation \(\rho\) of the vertices that corresponds to rotating the cube 90 degrees around a vertical axis through the faces \(t\) (for top) and \(u\) (for underneath). (We rotated in a right-handed fashion around this axis, meaning that vertex 6 goes to the back and vertex 8 comes to the front.) Write in two row notation the permutation \(\overline{\rho}\) of the faces that corresponds to this member \(\rho\) of \(R\text{.}\)
(b)
In Problem 263 we wrote in two row notation the permutation \(\varphi\) that rotates the cube 120 degrees around the diagonal from vertex 1 to vertex 7 and carries vertex 8 to vertex 6. Write in two row notation the \(\overline{\varphi}\) of the faces that corresponds to this member of \(R\text{.}\)
(c)
In Problem 263 we computed the two row notation for \(\rho\circ\varphi\text{.}\) Now compute the two row notation for \(\overline{\rho}\circ\overline{\varphi}\) (\(\overline{\rho}\) was defined in Part 280.a), and write in two row notation the permutation \(\overline{\rho\circ\varphi}\) of the faces that corresponds to the action of the permutation \(\rho\circ\varphi\) on the faces of the cube. (For this question it helps to think geometrically about what motion of the cube is carried out by \(\rho\circ\varphi\text{.}\)) What do you observe about \(\overline{\rho\circ\varphi}\) and \(\overline{\rho}\circ\overline{\varphi}\text{?}\)
We say that a permutation group \(G\) acts on a set \(S\) if, for each member \(\sigma\) of \(G\) there is a permutation \(\overline{\sigma}\) of \(S\) such that
for every member \(\sigma\) and \(\varphi\) of \(G\text{.}\) In Problem 280.c you saw one example of this condition. If we think intuitively of \(\rho\) and \(\varphi\) as motions in space, then following the action of \(\varphi\) by the action of \(\rho\) does give us the action of \(\rho\circ \varphi\text{.}\) We can also reason directly with the permutations in the group \(R\) of rigid motions (rotations) of the cube to show that \(R\) acts on the faces of the cube.
Problem281
Show that a group \(G\) of permutations of a set \(S\) acts on \(S\) with \(\overline{\varphi} = \varphi\) for all \(\varphi\) in \(G\text{.}\)
Problem282
The group \(D_4\) is a group of permutations of \(\{1,2,3,4\}\) as in Problem 255. We are going to show in this problem how this group acts on the two-element subsets of \(\{1,2,3,4\}\text{.}\) In Problem 287 we will see a natural geometric interpretation of this action. In particular, for each two-element subset \(\{i,j\}\) of \(\{1,2,3,4\}\) and each member \(\sigma\) of \(D_4\) we define \(\overline{\sigma}(\{i,j\}) = \{\sigma(i),\sigma(j)\}\text{.}\) Show that with this definition of \(\overline{\sigma}\text{,}\) the group \(D_4\) acts on the two-element subsets of \(\{1,2,3,4\}\text{.}\)
Problem283
Suppose that \(\sigma\) and \(\varphi\) are permutations in the group \(R\) of rigid motions of the cube. We have argued already that each rigid motion sends a face to a face. Thus \(\sigma\) and \(\varphi\) both send the vertices on one face to the vertices on another face. Let \(\{h,i,j,k\}\) be the set of labels next to the vertices on a face \(F\text{.}\)
(a)
What are the vertices of the face \(F'\) that \(F\) is sent to by \(\varphi\text{?}\)
(b)
What are the vertices of the face \(F''\) that \(F'\) is sent to by \(\sigma\text{?}\)
(c)
What are the vertices of the face \(F'''\) that \(F\) is sent to by \(\sigma\circ\varphi\text{?}\)
(d)
How have you just shown that the group \(R\) acts on the faces?
Recall that when you were asked in Problem 45 to find the number of ways to place two red beads and two blue beads at the corners of a square free to move in three-dimensional space, you were not able to apply the quotient principle to answer the question. Instead you had to see that you could divide the set of six lists of two \(R\)s and two \(B\)s into two sets, one of size two in which the \(R\)s and \(B\)s alternated and one of size four in which the two reds (and therefore the two blues) would be side-by-side on the square. Saying that the square is free to move in space is equivalent to saying that two arrangements of beads on the square are equivalent if a member of the dihedral group carries one arrangement to the other. Thus an important ingredient in the analysis of such problems will be how a group can act on colorings of a set of vertices. We can describe the coloring of the square in Figure 6.2.2 as the function \(f\) with
\begin{equation*}
f(1)=R,\; f(2)=R, \; f(3)=B,\;\text{ and }\;f(4)=B\text{,}
\end{equation*}
but it is more compact and turns out to be more suggestive to represent the coloring in Figure 6.2.2 as the set of ordered pairs
Figure6.2.2 The colored square with coloring \(\left\{(1,R),(2,R),(3,B),(4,B)\right\}\)
This gives us an explicity list of which colors are assigned to which vertex.â4âThe reader who has studied Appendix A will recognize that this set of ordered pairs is the relation of the function \(f\text{,}\) but we won't need to make any specific references to the idea of a relation in what follows. Then if we rotate the square through 90 degrees, we see that the set of ordered pairs becomes
The reordering we did in (6.5) suggests yet another simplification of notation. So long as we know we that the first elements of our pairs are labeled by the members of \([n]\) for some integer \(n\) and we are listing our pairs in increasing order by the first component, we can denote the coloring
by \(BRRB\text{.}\) In the case where we have numbered the elements of the set \(S\) we are coloring, we will call this list of colors of the elements of \(S\) in order the standard notation for the coloring. We will call the ordering used in (6.5)the standard ordering of the coloring.
Thus we have three natural ways to represent a coloring of a set: as a function, as a set of ordered pairs, and as a list. Different representations are useful for different things. For example, the representation by ordered pairs will provide a natural way to define the action of a group on colorings of a set. Given a coloring as a function \(f\text{,}\) we denote the set of ordered pairs
suggestively as \((S,f)\) for short. We use \(f(1)f(2)\cdots f(n)\) to stand for a particular coloring \((S,f)\) in the standard notation.
Problem284
Suppose now that instead of coloring the vertices of a square, we color its edges. We will use the shorthand 12, 23, 34, and 41 to stand for the edges of the square between vertex 1 and vertex 2, vertex 2 and vertex 3, and so on. Then a coloring of the edges with 12 red, 23 blue, 34 red and 41 blue can be represented as
If \(\rho\) is the rotation through 90 degrees, then we have a permutation \(\overline{\rho}\) acting on its edges. This permutation acts on the colorings to give us a permutation \(\overline{\overline{\rho}}\) of the set of colorings.
(a)
What is \(\overline{\overline{\rho}}\) of the coloring in (6.6)?
(b)
What is \(\overline{\overline{\rho^2}}\) of the coloring in (6.6)?
If \(G\) is a group that acts on the set \(S\text{,}\) we define the action of \(G\) on the colorings \((S,f)\) by by
We have two bars over \(\sigma\) because \(\sigma\) is a permutation of one set that gives us a permutation \(\overline{\sigma}\) of a second set, and then \(\overline{\sigma}\) acts to give a permutation \(\overline{\overline{\sigma}}\) of a thid set, the set of colorings. For example, suppose we want to analyze colorings of the faces of a cube under the action of the rotation group of the cube as we have defined it on the vertices. Each vertex-permutation \(\sigma\) in the group gives a permutation \(\overline{\sigma}\) of the faces of the cube. Then each permutation \(\overline{\sigma}\) of the faces gives us a permutation \(\overline{\overline{\sigma}}\) of the colorings of the faces.
In the special case that \(G\) is a group of permutations of \(S\) rather than a group acting on \(S\text{,}\) Equation (6.7) becomes
In the case where \(G\) is the rotation group of the square acting on the vertices of the square, the example of acting on a coloring by \(\rho\) that we saw in (6.5) is an example of this kind of action. In the standard notation, when we act on a coloring by \(\sigma\text{,}\) the color in position \(i\) moves to position \(\sigma(i)\text{.}\)
Problem285
Why does the action we have defined on colorings in Equation (6.7) take a coloring to a coloring?
Problem286
Show that if \(G\) is a group of permutations of a set \(S\text{,}\) and \(f\) is a coloring function on \(S\text{,}\) then the equation
Before you try to show that \(\overline{\overline{\sigma}}\) actually is a permutation of the colorings, it would be useful to verify the second part of the definition of a group action, namely that \(\overline{\overline{\sigma}}\circ\overline{\overline{\varphi}} = \overline{\overline{\sigma\circ\varphi}}\text{.}\)
Refer back to Problem 282 in answering the following questions.
(a)
What is the set of two element subsets that you get by computing \(\overline{\sigma}(\{1,2\})\) for all \(\sigma\) in \(D_4\text{?}\)
(b)
What is the multiset of two-element subsets that you get by computing \(\overline{\sigma}(\{1,2\})\) for all \(\sigma\)in \(D_4\text{?}\)
(c)
What is the set of two-element subsets you get by computing \(\overline{\sigma}(\{1,3\})\) for all \(\sigma\) in \(D_4\text{?}\)
(d)
What is the multiset of two-element subsets that you get by computing \(\overline{\sigma}(\{1,3\})\) for all \(\sigma\) in \(D_4\text{?}\)
(e)
Describe these two sets geometrically in terms of the square.
Problem288
This problem uses the notation for permutations in the dihedral group of the square introduced before Problem 259. What is the effect of a 180 degree rotation \(\rho^2\) on the diagonals of a square? What is the effect of the flip \(\varphi_{1|3}\) on the diagonals of a square? How many elements of \(D_4\) send each diagonal to itself? How many elements of \(D_4\) interchange the diagonals of a square?
In Problem 287 you saw that the action of the dihedral group \(D_4\) on two element subsets of \(\{1,2,3,4\}\) seems to split them into two sets, one with two elements and one with 4. We call these two sets the âorbitsâ of \(D_4\) acting on the two elements subsets of \(\{1,2,3,4\}\text{.}\) More generally, the orbit of a permutation group \(G\) determined by an element \(x\) of a set \(S\) on which \(G\) acts is
and is denoted by \(Gx\text{.}\) In Problem 287 it was possible to have \(Gx = Gy\text{.}\) In fact in that problem, \(Gx = Gy\) for every \(y\) in \(Gx\text{.}\)
Problem289
Suppose a group acts on a set \(S\text{.}\) Could an element of \(S\) be in two different orbits? (Say why or why not.)
Notice that thinking in terms of orbits actually hides some information about the action of our group. When we computed the multiset of all results of acting on \(\{1, 2\}\) with the elements of \(D_4\text{,}\) we got an eight-element multiset containing each side twice. When we computed the multiset of all results of acting on \(\{1,3\}\) with the elements of \(D_4\text{,}\) we got an eight-element multiset containing each diagonal of the square four times. These multisets remind us that we are acting on our two-element sets with an eight-element group. The multiorbit of \(G\) determined by an element \(x\) of \(S\) is the multiset
When we used the quotient principle to count circular seating arrangements or necklaces, we partitioned up a set of lists of people or beads into blocks of equivalent lists. In the case of seating \(n\) people around a round table, what made two lists equivalent was, in retrospect, the action of the rotation group \(C_n\text{.}\) In the case of stringing \(n\) beads on a string to make a necklace, what made two lists equivalent was the action of the dihedral group. Thus the blocks of our partitions were orbits of the rotation group or the dihedral group, and we were counting the number of orbits of the group action. In Problem 45, we were not able to apply the quotient principle because we had blocks of different sizes. However, these blocks were still orbits of the action of the group \(D_4\text{.}\) And, even though the orbits have different sizes, we expect that each orbit corresponds naturally to a multiorbit and that the multiorbits all have the same size. Thus if we had a version of the quotient rule for a union of multisets, we could hope to use it to count the number of multiorbits.
Problem291
(a)
Find the orbit and multiorbit of \(D_4\) acting on the coloring
How many elements of the group send the coloring \(RBRB\) to itself? What is the multiplicity of \(RBRB\) in its orbit?
Problem292
(a)
If \(G\) is a group, how is the set \(\{\tau\sigma\mid\tau\in G\}\) related to \(G\text{?}\)
(b)
Use this to show that \(y\) is in the multiorbit \(Gx_{\text{multi}}\) if and only if \(Gx_{\text{multi}} = Gy_{\text{multi}}\text{.}\)
Problem 292.b tells us that, when \(G\) acts on \(S\text{,}\) each element \(x\) of \(S\) is in one and only one multiorbit. Since each orbit is a subset of a multiorbit and each element \(x\) in \(S\) is in one and only one orbit, this also tells us there is a bijection between the orbits of \(G\) and the multiorbits of \(G\text{,}\) so that we have the same number of orbits as multiorbits.
When a group acts on a set, a group element is said to fix an element of \(x \in S\) if \(\overline{\sigma}(x) = x\text{.}\) The set of all elements fixing an element \(x\) is denoted by \(\Fix(x)\text{.}\)
Problem293
Suppose a group \(G\) acts on a set \(S\text{.}\) What is special about the subset \(\Fix(x)\) for an element \(x\) of \(S\text{?}\)
Problem294
Suppose a group \(G\) acts on a set \(S\text{.}\) What is the relationship of the multiplicity of \(x\in S\) in its multiorbit and the size of \(\Fix(x)\text{?}\)
Problem295
What can you say about relationships between the multiplicity of an element \(y\) in the multiorbit \(Gx_{\text{multi}}\) and the multiplicites of other elements? Try to use this to get a relationship between the size of an orbit of \(G\) and the size of \(G\text{.}\)
How does the size of a multiorbit compare to the size of \(G\text{?}\)
We suggested earlier that a quotient principle for multisets might prove useful. The quotient principle came from the sum principle, and we do not have a sum principle for multisets. Such a principle would say that the size of a union of disjoint multisets is the sum of their sizes. We have not yet defined the union of multisets or disjoint multisets, because we haven't needed the ideas until now. We define the union of two multisets \(S\) and \(T\) to be the multiset in which the multiplicity of an element \(x\) is the maximumâ5âWe choose the maximum rather than the sum so that the union of sets is a special case of the union of multisets. of the multiplicity of \(x\) in \(S\) and its multiplicity in \(T\) . Similarly, the union of a family of multisets is defined by defining the multiplicity of an element \(x\) to be the maximum of its multiplicities in the members of the family. Two multisets are said to be disjoint if no element is a member of both, that is, if no element has multiplicity one or more in both. Since the size of a multiset is the sum of the multiplicities of its members, we immediately get the sum principle for multisets.
The size of a union of disjoint multisets is the sum of their sizes.
Taking the multisets all to have the same size, we get the product principle for multisets.
The union of a set of \(m\) disjoint multisets, each of size \(n\) has size \(mn\text{.}\)
The quotient principle for multisets then follows immediately.
If a \(p\)-element multiset is a union of \(q\) disjoint multisets, each of size \(r\text{,}\) then \(q = p/r\text{.}\)
Problem296
How does the size of the union of the set of multiorbits of a group \(G\) acting on a set \(S\) relate to the number of multiorbits and the size of \(G\text{?}\)
Problem297
How does the size of the union of the set of multiorbits of a group \(G\) acting on a set \(S\) relate to the numbers \(|\Fix(x)|\text{?}\)
Problem298
In Problems 296 and 297 you computed the size of the union of the set of multiorbits of a group \(G\) acting on a set \(S\) in two different ways, getting two different expressions must be equal. Write the equation that says they are equal and solve for the number of multorbits, and therefore the number of orbits.
In Problem 298 you stated and proved a theorem that expresses the number of orbits in terms of the number of group elements fixing each element of \(S\text{.}\) It is often easier to find the number of elements fixed by a given group element than to find the number of group elements fixing an element of \(S\text{.}\)
(a)
For this purpose, how does the sum \(\sum_{x\colon x\in S}|\Fix(x)|\) relate to the number of ordered pairs \((\sigma,x)\) (with \(\sigma\in G\) and \(x \in S\)) such that \(\sigma\) fixes \(x\text{?}\)
(b)
Let \(\chi(\sigma)\) denote the number of elements of \(S\) fixed by \(\sigma\text{.}\) How can the number of ordered pairs \((\sigma,x)\) (with \(\sigma\in G\) and \(x\in S\)) such that \(\sigma\) fixes \(x\) be computed from \(\chi(G)\text{?}\) (It is ok to have a summation in your answer.)
(c)
What does this tell you about the number of orbits?
Problem300
A second computation of the result of Problem 299 can be done as follows.
(a)
Let \(\widehat{\chi}(\sigma,x)=1\) if \(\sigma(x)=x\) and let \(\widehat{\chi}(\sigma,x) =0\) otherwise. Notice that \(\widehat{\chi}\) is different from the \(\chi\) in the previous problem, because it is a function of two variables. Use \(\widehat{\chi}\) to convert the single summation in Problem 298 into a double summation over elements \(x\) of \(S\) and elements \(\sigma\) of \(G\text{.}\)
(b)
Reverse the order of the previous summation in order to convert it into a single sum involving the function \(\chi\) given by
\begin{equation*}
\chi(\sigma) =
\mbox{the number of elements of \(S\) left fixed by \(\sigma\)} .
\end{equation*}
In Problem 299 you gave a formula for the number of orbits of a group \(G\) acting on a set \(X\text{.}\) This formula was first worked out by Cauchy in the case of the symmetric group, and then for more general groups by Frobenius. In his pioneering book on Group Theory, Burnside used this result as a lemma, and while he attributed the result to Cauchy and Frobenius in the first edition of his book, in later editions, he did not. Later on, other mathematicians who used his book named the result ``Burnside's Lemma," which is the name by which it is still most commonly known. Let us agree to call this result the Cauchy-Frobenius-Burnside Theorem, or CFB Theorem for short in a compromise between historical accuracy and common usage.
Problem301
In how many ways may we string four (identical) red, six (identical) blue, and seven (identical) green beads on a necklace?
There are five kinds of elements in the rotation group of the cube. For example, there are six rotations by 90 degrees or 270 degrees around an axis connecting the centers of two opposite faces and there are 8 rotations (of 120 degrees and 240 degrees, respectively) around an axis connecting two diagonally opposite vertices.
Problem306
In how many ways may we color the edges of a (regular) \((2n+1)\)-gon free to move around in the plane (so it cannot be flipped) if we use red \(n\) times and blue \(n+1\) times? If this is a number you have seen before, identify it.
Is it possible for a nontrivial rotation to fix any coloring?
Problem307
In how many ways may we color the edges of a (regular) \((2n+1)\)-gon free to move in three-dimensional space so that \(n\) edges are colored red and \(n+1\) edges are colored blue. Your answer may depend on whether \(n\) is even or odd.
Problem308
(Not unusually hard for someone who has worked on chromatic polynomials.) How many different proper colorings with four colors are there of the vertices of a graph which is cycle on five vertices? (If we get one coloring by rotating or flipping another one, they aren't really different.)
Problem309
How many different proper colorings with four colors are there of the graph in Figure 6.2.4? Two graphs are the same if we can redraw one of the graphs, not changing the vertex set or edge set, so that it is identical to the other one. This is equivalent to permuting the vertices in some way so that when we apply the permutation to the endpoints of the edges to get a new edge set, the new edge set is equal to the old one. Such a permutation is called an automorphism of the graph. Thus two colorings are different if there is no automorphism of the graph that carries one to the other one.
