ads Permutation Groups

Section 15.3 Permutation Groups

Subsection 15.3.1 The Symmetric Groups

At the risk of boggling the reader’s mind, we will now examine groups whose elements are functions. Recall that a permutation on a set

A

is a bijection from

A

into

A .

Suppose that

A = {1, 2, 3} .

There are

3! = 6

different permutations on

A .

We will call the set of all 6 permutations

S_{3} .

They are listed in the following table. The matrix form for describing a function on a finite set is to list the domain across the top row and the image of each element directly below it. For example

r_{1} (1) = 2 .

🔗

Table 15.3.1. Elements of

S_{3}

$i = (\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \end{array})$	$r_{1} = (\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \end{array})$	$r_{2} = (\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array})$
$f_{1} = (\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \end{array})$	$f_{2} = (\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 2 & 1 \end{array})$	$f_{3} = (\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array})$

🔗

The operation that will give

{i, r_{1}, r_{2}, f_{1}, f_{2}, f_{3}}

a group structure is function composition. Consider the “product”

r_{1} \circ f_{3} :

\begin{matrix} r_{1} \circ f_{3} (1) = r_{1} (f_{3} (1)) = r_{1} (2) = 3 \\ r_{1} \circ f_{3} (2) = r_{1} (f_{3} (2)) = r_{1} (1) = 2 \\ r_{1} \circ f_{3} (3) = r_{1} (f_{3} (3)) = r_{1} (3) = 1 \end{matrix} .

🔗

The images of 1, 2, and 3 under

r_{1} \circ f_{3}

and

f_{2}

are identical. Thus, by the definition of equality for functions, we can say

r_{1} \circ f_{3} = f_{2}

. The complete table for the operation of function composition is given in Table 15.3.2.

🔗

Table 15.3.2. Operation Table for

S_{3}

\begin{array}{ccccccc} \circ & i & r_{1} & r_{2} & f_{1} & f_{2} & f_{3} \\ i & i & r_{1} & r_{2} & f_{1} & f_{2} & f_{3} \\ r_{1} & r_{1} & r_{2} & i & f_{3} & f_{1} & f_{2} \\ r_{2} & r_{2} & i & r_{1} & f_{2} & f_{3} & f_{1} \\ f_{1} & f_{1} & f_{2} & f_{3} & i & r_{1} & r_{2} \\ f_{2} & f_{2} & f_{3} & f_{1} & r_{2} & i & r_{1} \\ f_{3} & f_{3} & f_{1} & f_{2} & r_{1} & r_{2} & i \end{array}

🔗

List 15.3.3.

🔗

We don’t even need the table to verify that we have a group. Based on the following observations, the set of all permutations on any finite set will be a group.

Function composition is always associative.
The identity for the group is $i .$ If $g$ is any one of the permutations on $A$ and $x \in A,$

$\begin{array}{lr} (g \circ i) (x) = g (i (x)) = g (x) & (i \circ g) (x) = i (g (x)) = g (x) \end{array}$

Therefore $g \circ i = i \circ g = g .$
A permutation, by definition, is a bijection. In Chapter 7 we proved that this implies that it must have an inverse and the inverse itself is a bijection and hence a permutation. Hence all elements of $S_{3}$ have an inverse in $S_{3} .$ If a permutation is displayed in matrix form, its inverse can be obtained by exchanging the two rows and rearranging the columns so that the top row is in order. The first step is actually sufficient to obtain the inverse, but the sorting of the top row makes it easier to recognize the inverse.

For example, let’s consider a typical permutation on ${1, 2, 3, 4, 5},$ $f = (\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 2 & 1 & 4 \end{array}) .$

$f^{- 1} = (\begin{array}{ccccc} 5 & 3 & 2 & 1 & 4 \\ 1 & 2 & 3 & 4 & 5 \end{array}) = (\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{array}) .$

🔗

Note 15.3.4.

🔗

From Table 15.3.2, we can see that

S_{3}

is non-abelian. Remember, non-abelian is the negation of abelian. The existence of two elements that don’t commute is sufficient to make a group non-abelian. In this group,

r_{1}

and

f_{3}

is one such pair:

r_{1} \circ f_{3} = f_{2}

while

f_{3} \circ r_{1} = f_{1},

r_{1} \circ f_{3} \neq f_{3} \circ r_{1} .

Caution: Don’t take this to mean that every pair of elements has to have this property. There are several pairs of elements in

S_{3}

that do commute. In fact, the identity,

i,

must commute with everything. Also every element must commute with its inverse.

🔗

Definition 15.3.5. Symmetric Group.

🔗

Let

A

be a nonempty set. The set of all permutations on

A

with the operation of function composition is called the symmetric group on

A,

denoted

S_{A} .

🔗

The cardinality of a finite set

A

is more significant than the elements, and we will denote by

S_{n}

the symmetric group on any set of cardinality

n,

n \geq 1 .

Example 15.3.6. The significance of $S_{3}$ .

Our opening example,

S_{3},

is the smallest non-abelian group. For that reason, all of its proper subgroups are abelian: in fact, they are all cyclic. Figure 15.3.7 shows the Hasse diagram for the subgroups of

S_{3} .

described in detail following the image — Figure 15.3.7. Lattice diagram of subgroups of $S_{3}$

Example 15.3.8. Smallest Symmetric Groups.

🔗

Theorem 15.3.9.

🔗

For

n \geq 1,

| S_{n} | = n!

and for

n \geq 3,

S_{n}

is non-abelian.

Proof.

The first part of the theorem follows from the extended rule of products (see Chapter 2). We leave the details of proof of the second part to the reader after the following hint. Consider

f

S_{n}

where

f (1) = 2,

f (2) = 3,

f (3) = 1,

and

f (j) = j

for

3 < j \leq n .

Therefore the cycle representation of

f

(1, 2, 3) .

Now define

g

in a similar manner so that when you compare

f (g (1))

and

g (f (1))

you get different results.

🔗

Subsection 15.3.2 Cycle Notation

🔗

A second way of describing a permutation is by means of cycles, which we will introduce first with an example. Consider

f \in S_{8}

defined using the now-familiar matrix notation:

f = (\begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 8 & 2 & 7 & 6 & 5 & 4 & 1 & 3 \end{array})

🔗

Consider the images of 1 when

f

is applied repeatedly. The images

f (1),

f (f (1)),

f (f (f (1))), \dots

are

8, 3, 7, 1, 8, 3, 7, \dots .

In Figure 15.3.10(a), this situation is represented by a graph with vertices 1, 8, 3, and 7 and shows that the values that you get by repeatedly applying

f

cycle through those values. This is why we refer to this part of

f

as a cycle of length 4. Of course starting at 8, 3, or 7 also produces the same cycle with only the starting value changing.

🔗
Figure 15.3.10. Representations of a cycle of length 4

🔗

Figure 15.3.10(a) illustrates how the cycle can be represented in a visual manner, but it is a bit awkward to write. Part (b) of the figure presents a more universally recognized way to write a cycle. In (b), a cycle is represented by a list where the image of any number in the list is its successor. In addition, the last number in the list has as its image the first number.

🔗

The other elements of the domain of

f

are never reached if you start in the cycle

(1, 8, 3, 7),

and so looking at the images of these other numbers will produce numbers that are disjoint from the set

{1, 8, 3, 7} .

The other disjoint cycles of

f

are (2), (4, 6), and (5). We can express

f

as a product of disjoint cycles:

f = (1, 8, 3, 7) (2) (4, 6) (5)

f = (1, 8, 3, 7) (4, 6),

where the absence of 2 and 5 implies that

f (2) = 2

and

f (5) = 5 .

🔗

Note 15.3.11. Disjoint Cycles.

🔗

We say that two cycles are disjoint if no number appears in both cycles, as is the case in our expressions for

f

above. Disjoint cycles can be written in any order. Thus, we could also say that

f = (4, 6) (1, 8, 3, 7) .

🔗

Note 15.3.12. Composition of Permutations.

🔗

We will now consider the composition of permutations written in cyclic form by an example. Suppose that

f = (1, 8, 3, 7) (4, 6)

and

g = (1, 5, 6) (8, 3, 7, 4)

are elements of

S_{8} .

To calculate

f \circ g,

we start with simple concatenation:

\begin{matrix} (15.3.1) & f \circ g = (1, 8, 3, 7) (4, 6) (1, 5, 6) (8, 3, 7, 4) \end{matrix}

🔗

Although this is a valid expression for

f \circ g,

our goal is to express the composition as a product of disjoint cycles as

f

and

g

were individually written. We will start by determining the cycle that contains 1. When combining any number of cycles, they are always read from right to left, as with all functions. The first cycle in (15.3.1) does not contain 1; thus we move on to the second. The image of 1 under that cycle is 5. Now we move on to the next cycle, looking for 5, which doesn’t appear. The fourth cycle does not contain a 5 either; so

f \circ g (1) = 5 .

🔗

At this point, we would have written “

f \circ g = (1, 5

” on paper. We repeat the steps to determine

f \circ g (5) .

This time the second cycle of (15.3.1) moves 5 to 6 and then the third cycle moves 6 to 4. Therefore,

f \circ g (5) = 4 .

We continue until the cycle (1, 5, 4, 3) is completed by determining that

f \circ g (3) = 1 .

The process is then repeated starting with any number that does not appear in the cycle(s) that have already been completed.

🔗

The final result for our example is

f \circ g = (1, 5, 4, 3) (6, 8, 7) .

Since

f (2) = 2

and

g (2) = 2,

f \circ g (2) = 2

and we need not include the one-cycle (2) in the final result, although it can be included.

Example 15.3.13. Some Compositions.

$(1, 2, 3, 4) (1, 2, 3, 4) = (1, 3) (2, 4)$
$(1, 4) (1, 3) (1, 2) = (1, 2, 3, 4) .$

Notice that cyclic notation does not indicate the set which is being permuted. The examples above could be in

S_{5},

where the image of 5 is 5. This ambiguity is usually overcome by making the context clear at the start of a discussion.

🔗

Definition 15.3.14. Transposition.

🔗

A transposition is a cycle of length 2.

🔗

Observation 15.3.15. About transpositions.

🔗

f = (1, 4)

and

g = (4, 5)

are transpositions in

S_{5} .

However,

f \circ g = (1, 4, 5)

and

g \circ f = (1, 5, 4)

are not transpositions; thus, the set of transpositions is not closed under composition. Since

f^{2} = f \circ f

and

g^{2} = g \circ g

are both equal to the identity permutation,

f

and

g

are their own inverses. In fact, every transposition is its own inverse.

🔗

Theorem 15.3.16. Decomposition into Cycles.

🔗

Every cycle of length greater than 2 can be expressed as a product of transpositions.

Proof.

We need only indicate how the product of transpositions can be obtained. It is easy to verify that a cycle of length

k,

(a_{1}, a_{2}, a_{3}, \dots, a_{k}),

is equal to the following product of

k - 1

transpositions:

(a_{1}, a_{k}) \dots (a_{1}, a_{3}) (a_{1}, a_{2})

🔗

Of course, a product of cycles can be written as a product of transpositions just as easily by applying the rule above to each cycle. For example,

(1, 3, 5, 7) (2, 4, 6) = (1, 7) (1, 5) (1, 3) (2, 6) (2, 4)

🔗

Unlike the situation with disjoint cycles, we are not free to change the order of these transpositions.

🔗

Subsection 15.3.3 Parity of Permutations and the Alternating Group

🔗

A decomposition of permutations into transpositions makes it possible to classify them and identify an important family of groups.

🔗

The proofs of the following theorem appears in many abstract algebra texts.

🔗

Theorem 15.3.17.

🔗

Every permutation on a finite set can be expressed as the product of an even number of transpositions or an odd number of transpositions, but not both.

🔗

Theorem 15.3.17 suggests that

S_{n}

can be partitioned into its “even” and “odd” elements. For example, the even permutations of

S_{3}

are

i,

r_{1} = (1, 2, 3) = (1, 3) (1, 2)

and

r_{2} = (1, 3, 2) = (1, 2) (1, 3) .

They form a subgroup,

{i, r_{1}, r_{2}}

S_{3} .

🔗

In general:

🔗

Definition 15.3.18. The Alternating Group.

🔗

Let

n \geq 2 .

The set of even permutations in

S_{n}

is a proper subgroup of

S_{n}

called the alternating group on

{1, 2, \dots, n},

denoted

A_{n} .

🔗

We justify our statement that

A_{n}

is a group:

🔗

Theorem 15.3.19.

🔗

Let

n \geq 2 .

The alternating group is indeed a group and has order

\frac{n!}{2} .

Proof.

In this proof, the symbols

s_{i}

and

t_{i}

stand for transpositions and

p,

q

are even nonnegative integers. If

f, g \in A_{n},

we can write the two permutations as products of even numbers of transpositions,

f = s_{1} s_{2} \dots s_{p}

and

g = t_{1} t_{2} \dots t_{q} .

Then

f \circ g = s_{1} s_{2} \dots s_{p} t_{1} t_{2} \dots t_{q}

Since

p + q

is even,

f \circ g \in A_{n},

and

A_{n}

is closed with respect to function composition. With this, we have proven that

A_{n}

is a subgroup of

S_{n}

by Theorem 11.5.5.

To prove the final assertion, let

B_{n}

be the set of odd permutations and let

τ = (1, 2) .

Define

θ : A_{n} \to B_{n}

θ (f) = f \circ τ .

Suppose that

θ (f) = θ (g) .

Then

f \circ τ = g \circ τ

and by the right cancellation law,

f = g .

Hence,

θ

is an injection. Next we show that

θ

is also a surjection. If

h \in B_{n},

h

is the image of an element of

A_{n} .

Specifically,

h

is the image of

h \circ τ .

\begin{aligned} θ (h \circ τ) & = (h \circ τ) \circ τ \\ = h \circ (τ \circ τ) Why? \\ = h \circ i Why? \\ = h \end{aligned}

Since

θ

is a bijection,

| A_{n} | = | B_{n} | = \frac{n!}{2} .

Example 15.3.20. The Sliding Tile Puzzle.

Consider the sliding-tile puzzles pictured in Figure 15.3.21. Each numbered square is a tile and the dark square is a gap. Any tile that is adjacent to the gap can slide into the gap. In most versions of this puzzle, the tiles are locked into a frame so that they can be moved only in the manner described above. The object of the puzzle is to arrange the tiles as they appear in Configuration (a). Configurations (b) and (c) are typical starting points. We propose to show why the puzzle can be solved starting with (b), but not with (c).

Figure 15.3.21. Configurations of the sliding tile puzzle

We will associate a change in the configuration of the puzzle with an element of

S_{16} .

Imagine that a tile numbered 16 fills in the gap. For any configuration of the puzzle, the identity

i,

is the function that leave the configurate “as is.” In general, if

f \in S_{16},

and

1 \leq k \leq 16,

f (k)

is the position to which the tile in position

k

is moved by

f

that appears in the position of

k

in configuration (a). If we call the functions that, starting with configuration (a), result in configurations (b) and (c) by the names

f_{1}

and

f_{2},

respectively,

f_{1} = (1, 5, 3, 7) (2, 6, 4, 8) (9, 10) (11, 14, 13, 12) (15) (16)

and

f_{2} = (1, 5, 3, 7, 15) (2, 6, 4, 8) (9, 10) (11, 14, 13, 12) (16) .

How can we interpret the movement of one tile as a permutation? Consider what happens when the 12 tile of

i

slides into the gap. The result is a configuration that we would interpret as

(12, 16),

a single transposition. Now if we slide the 8 tile into the 12 position, the result is or

(8, 16, 12) .

Hence, by “exchanging” the tiles 8 and 16, we have implemented the function

(8, 12) (12, 16) = (8, 12, 16) .

Every time you slide a tile into the gap, the new permutation is a transposition composed with the old permutation. Now observe that to start with initial configuration and terminate after a finite number of moves with the gap in its original position, you must make an even number of moves. Thus, configuration corresponding any permutation that leaves 16 fixed cannot be solved if the permutation is odd. Note that

f_{2}

is an odd permutation; thus, Puzzle (c) can’t be solved. The proof that all even permutations, such as

f_{1},

can be solved is left to the interested reader to pursue.

🔗

Subsection 15.3.4 Dihedral Groups

🔗

Observation 15.3.23. Realizations of Groups.

🔗

By now we’ve seen several instances where a group can appear through an isomorphic copy of itself in various settings. The simplest such example is the cyclic group of order 2. When this group is mentioned, we might naturally think of the group

[Z_{2}; +_{2}],

but the groups

[{- 1, 1}; \cdot]

and

[S_{2}; \circ]

are isomorphic to it. None of these groups are necessarily more natural or important than the others. Which one you use depends on the situation you are in and all are referred to as realizations of the cyclic group of order 2. The next family of groups we will study, the dihedral groups, has two natural realizations, first as permutations and second as geometric symmetries.

🔗

The family of dihedral groups is indexed by the positive integers greater than or equal to 3. For

k \geq 3,

D_{k}

will have

2 k

elements. We first describe the elements and the operation on them using geometry.

🔗

We can describe

D_{n}

in terms of symmetries of a regular

n

-gon (

n = 3 :

equilateral triangle,

n = 4 :

square,

n = 5 :

regular pentagon,

\dots

). Here we will only concentrate on the case of

D_{4} .

If a square is fixed in space, there are several motions of the square that will, at the end of the motion, not change the apparent position of the square. The actual changes in position can be seen if the corners of the square are labeled. In Figure 15.3.24, the initial labeling scheme is shown, along with the four axes of symmetry of the square.

🔗
Figure 15.3.24. Axes of symmetry of the square

🔗

It might be worthwhile making a square like this with a sheet of paper. Be careful to label the back so that the numbers match the front. Two motions of the square will be considered equivalent if the square is in the same position after performing either motion. There are eight distinct motions. The first four are

0^{\circ},

90^{\circ},

180^{\circ},

and

270^{\circ}

clockwise rotations of the square, and the other four are the

180^{\circ}

flips along the axes

l_{1},

l_{2},

l_{3},

and

l_{4} .

We will call the rotations

i, r_{1},

r_{2},

and

r_{3},

respectively, and the flips

f_{1},

f_{2},

f_{3},

and

f_{4},

respectively. Figure 15.3.25 illustrates

r_{1}

and

f_{1} .

For future reference, we also include the permutations to which they correspond.

🔗

What is the operation on this set of symmetries? We will call the operation “followed by” and use the symbol

*

to represent it. The operation will be to combine motions, applying motions from right to left, as with functions. We will illustrate how

*

is computed by finding

r_{1} * f_{1} .

Starting with the initial configuration, if you perform the

f_{1}

motion, and then immediately perform

r_{1}

on the result, we get the same configuration as if we just performed

f_{4},

which is to flip the square along the line

l_{4} .

Therefore,

r_{1} * f_{1} = f_{4} .

An important observation is that

f_{1} * r_{1} \neq f_{4},

meaning that this group is nonabelian. The reader is encouraged to verify this on their own.

🔗

We can also realize the dihedral groups as permutations. For any symmetric motion of the square we can associate with it a permutation. In the case of

D_{4},

the images of each of the numbers 1 through 4 are the positions on the square that each of the corners 1 through 4 are moved to. For example, since corner 4 moves to position 1 when you perform

r_{1},

the corresponding function will map 4 to 1. In addition, 1 gets mapped to 2, 2 to 3 and 3 to 4. Therefore,

r_{1}

is the cycle

(1, 2, 3, 4)

. The flip

f_{1}

transposes two pairs of corners and corresponds to

(1, 4) (2, 3) .

If we want to combine these two permutations, using the same names as with motions, we get

r_{1} \circ f_{1} = (1, 2, 3, 4) \circ (1, 4) (2, 3) = (1) (2, 4) (3) = (2, 4)

🔗

Notice that this permutation corresponds with the flip

f_{4} .

🔗

Although

D_{4}

isn’t cyclic (since it isn’t abelian), it can be generated from the two elements

r_{1}

and

f_{1} :

D_{4} = ⟨ r_{1}, f_{1} ⟩ = {i, r_{1}, r_{1}^{2}, r_{1}^{3}, f_{1}, r_{1} \circ f_{1}, r_{1}^{2} \circ f_{1}, r_{1}^{3} \circ f_{1}}

🔗

It is quite easy to describe any of the dihedral groups in a similar fashion. Here is the formal definition

🔗

Definition 15.3.26. Dihedral Group.

🔗

Let

n

be a positive integer greater than or equal to 3. If

r = (1, 2, \dots, n),

n

-cycle, and

f = (1, n) (2, n - 1) \dots

Then

D_{n} = ⟨ r, f ⟩ = {i, r, r^{2}, \dots, r^{n - 1}, f, r \circ f, r^{2} \circ f, \dots, r^{n - 1} \circ f}

🔗

is the

n

th dihedral group.

🔗

Note 15.3.27. Caution.

🔗

You might notice that we use a script

D,

D,

for the dihedral groups. Occasionally you might see an ordinary

D

in other sources for the dihedral groups. Don’t confuse it with the set of divisors of

n,

which we denote by

D_{n} .

Normally the context of the discussion should make the meaning of

D_{n}

clear.

Example 15.3.28. A Letter-facing Machine.

An application of

D_{4}

is in the design of a letter-facing machine. Imagine letters entering a conveyor belt to be postmarked. They are placed on the conveyor belt at random so that two sides are parallel to the belt. Suppose that a postmarker can recognize a stamp in the top right corner of the envelope, on the side facing up. In Figure 15.3.29, a sequence of machines is shown that will recognize a stamp on any letter, no matter what position in which the letter starts. The letter

P

stands for a postmarker. The letters

R

and

F

stand for rotating and flipping machines that perform the motions of

r_{1}

and

f_{1} .

The arrows pointing up indicate that if a letter is postmarked, it is taken off the conveyor belt for delivery. If a letter reaches the end, it must not have a stamp. Letter-facing machines like this have been designed (see [16]). One economic consideration is that

R

-machines tend to cost more than

F

-machines.

R

-machines also tend to damage more letters. Taking these facts into consideration, the reader is invited to design a better letter-facing machine. Assume that

R

-machines cost

$ 800

and

F

-machines cost

$ 500 .

Be sure that all corners of incoming letters will be examined as they go down the conveyor belt.

🔗

Exercises 15.3.5 Exercises

🔗

1.

🔗

Given

f = (\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{array}),

g = (\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{array}),

and

h = (\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \end{array}),

compute

$f \circ g$
$g \circ h$
$(f \circ g) \circ h$
$f \circ (g \circ h)$
$h^{- 1}$
$h^{- 1} \circ g \circ h$
$f^{- 1}$

Answer.

$(\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{array})$
$(\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{array})$
$(\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{array})$
$(\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{array})$
$(\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 3 \end{array})$
$(\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{array})$
$(\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{array})$

🔗

2.

🔗

Write

f,

g,

and

h

from Exercise 1 as products of disjoint cycles and determine whether each is odd or even.

🔗

3.

🔗

Do the left cosets of

A_{3} = {i, r_{1}, r_{2}}

over

S_{3}

form a group under the induced operation on left cosets of

A_{3} ?

What about the left cosets of

⟨ f_{1} ⟩ ?

Answer.

S_{3} / A_{3}

is a group of order two. The operation on left cosets of

H = ⟨ f_{1} ⟩

is not well defined and so a group cannot be formed from left cosets of

H .

🔗

4.

🔗

In its realization as permutations, the dihedral group

D_{3}

is equal to

S_{3} .

Can you give a geometric explanation why? Why isn’t

D_{4}

equal to

S_{4} ?

🔗

5.

🔗

Complete the list of elements of $D_{4}$ and write out a table for the group in its realization as symmetries.
List the subgroups of $D_{4}$ in a lattice diagram. Are they all cyclic? To what simpler groups are the subgroups of $D_{4}$ isomorphic?

Answer.

D_{4} = {i, r, r^{2}, r^{3}, f_{1}, f_{2}, f_{3}, f_{4}}

Where

i

is the identity function,

r = (\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{array}),

and

\begin{array}{cc} f_{1} = (\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{array}) & f_{2} = (\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{array}) \\ f_{3} = (\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \end{array}) & f_{4} = (\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{array}) \end{array}

The operation table for the group is

\begin{array}{cc} \circ & \begin{array}{cccccccc} i & r & r^{2} & r^{3} & f_{1} & f_{2} & f_{3} & f_{4} \end{array} \\ \begin{matrix} i \\ r \\ r^{2} \\ r^{3} \\ f_{1} \\ f_{2} \\ f_{3} \\ f_{4} \end{matrix} & \begin{array}{cccccccc} i & r & r^{2} & r^{3} & f_{1} & f_{2} & f_{3} & f_{4} \\ r & r^{2} & r^{3} & i & f_{4} & f_{3} & f_{1} & f_{2} \\ r^{2} & r^{3} & i & r & f_{2} & f_{1} & f_{4} & f_{3} \\ r^{3} & i & r & r^{2} & f_{3} & f_{4} & f_{2} & f_{1} \\ f_{1} & f_{3} & f_{2} & f_{4} & i & r^{2} & r & r^{3} \\ f_{2} & f_{4} & f_{1} & f_{3} & r^{2} & i & r^{3} & r \\ f_{3} & f_{2} & f_{4} & f_{1} & r^{3} & r & i & r^{2} \\ f_{4} & f_{1} & f_{3} & f_{2} & r & r^{3} & r^{2} & i \end{array} \end{array}

A lattice diagram of its subgroups is

All proper subgroups are cyclic except

{i, r^{2}, f_{1}, f_{2}}

and

{i, r^{2}, f_{3}, f_{4}} .

Each 2-element subgroup is isomorphic to

Z_{2}

;

{i, r, r^{2}, r^{3}}

is isomorphic to

Z_{4}

; and

{i, r^{2}, f_{1}, f_{2}}

and

{i, r^{2}, f_{3}, f_{4}}

are isomorphic to

Z_{2} \times Z_{2} .

🔗

6.

🔗

Design a better letter-facing machine (see Example 15.3.28). How can you verify that a letter-facing machine does indeed check every corner of a letter? Can it be done on paper without actually sending letters through it?

🔗

7.

🔗

Prove by induction that if

r \geq 1

and each

t_{i},

is a transposition, then

(t_{1} \circ t_{2} \circ \dots \circ t_{r})^{- 1} = t_{r} \circ \dots \circ t_{2} \circ t_{1}

Answer.

One solution is to cite Exercise 3 at the end of Section 11.3. It can be directly applied to this problem. An induction proof of the problem at hand would be almost identical to the proof of the more general statement.

(t_{1} t_{2} \dots t_{r})^{- 1} = t_{r}^{- 1} \dots t_{2}^{- 1} t_{1}^{- 1} by Exercise 3 of  Section 11.3 = t_{r} \dots t_{2} t_{1} since each transposition inverts itself . ◼

🔗

8.

🔗

How many elements are there in

D_{5}

? Describe them geometrically.

🔗

9.

🔗

Complete the proof of Theorem 15.3.9.

Answer.

Part I: That

| S_{k} | = k!

follows from the Rule of Products.

Part II: Let

f

be the function defined on

{1, 2, ..., n}

f (1) = 2,

f (2) = 3,

f (3) = 1,

and

f (j) = j

for

4 \leq j \leq n;

and let

g

be defined by

g (1) = 1,

g (2) = 3,

g (3) = 2,

and

g (j) = j

for

4 \leq j \leq n .

Note that

f

and

g

are elements of

S_{n} .

Next,

(f \circ g) (1) = f (g (1)) = f (1) = 2,

while

(g \circ f) (1) = g (f (1)) = g (2) = 3,

hence

f \circ g \neq g \circ f

and

S_{n}

is non-abelian for any

n \geq 3 .

🔗

10.

🔗

How many left cosets does

A_{n},

n \geq 2

have?

🔗

11.

🔗

Prove that

f \circ r = r^{n - 1} \circ f

D_{n} .

🔗

12.

🔗

Prove that the tile puzzles corresponding to $A_{16} \cap {f \in S_{16} | f (16) = 16}$ are solvable.
If $f (16) \neq 16,$ how can you determine whether $f$ ’s puzzle is solvable?

🔗

13.

🔗

Prove that $S_{3}$ is isomorphic to $R_{3},$ the group of $3 \times 3$ rook matrices (see Section 11.2 exercises).
Prove that for each $n \geq 2,$ $R_{n}$ is isomorphic to $S_{n} .$

Answer.

Both groups are non-abelian and of order 6; so they must be isomorphic, since only one such group exists up to isomorphism. The function $θ : S_{3} \to R_{3}$ defined by $\begin{array}{cc} θ (i) = I & θ (f_{1}) = F_{1} \\ θ (r_{1}) = R_{1} & θ (f_{2}) = F_{2} \\ θ (r_{2}) = R_{2} & θ (f_{3}) = F_{3} \end{array}$ is an isomorphism,
Recall that since every function is a relation, it is natural to translate functions to Boolean matrices. Suppose that $f \in S_{n} .$ We will define its image, $θ (f),$ by

$θ (f)_{k j} = 1 \Leftrightarrow f (j) = k$

That $θ$ is a bijection follows from the existence of $θ^{- 1} .$ If $A$ is a rook matrix,

$\begin{aligned} θ^{- 1} (A) (j) = k & \Leftrightarrow The 1 in column j of A appears in row k \\ \Leftrightarrow A_{k j} = 1 \end{aligned}$

For $f, g \in S_{n},$

$\begin{aligned} θ (f \circ g)_{k j} = 1 & \Leftrightarrow (f \circ g) (j) = k \\ \Leftrightarrow \exists l such that g (j) = l and f (l) = k \\ \Leftrightarrow \exists l such that θ (g)_{l j} = 1 and θ (f)_{k l} = 1 \\ \Leftrightarrow (θ (f) θ (g))_{k j} = 1 \end{aligned}$

Therefore, $θ$ is an isomorphism.

You have attempted of activities on this page.

Prev Top Next

Section 15.3 Permutation Groups

Subsection 15.3.1 The Symmetric Groups

Note 15.3.4.

Definition 15.3.5. Symmetric Group.

Example 15.3.6. The significance of S3.

Example 15.3.8. Smallest Symmetric Groups.

Theorem 15.3.9.

Proof.

Subsection 15.3.2 Cycle Notation

Note 15.3.11. Disjoint Cycles.

Note 15.3.12. Composition of Permutations.

Example 15.3.13. Some Compositions.

Definition 15.3.14. Transposition.

Observation 15.3.15. About transpositions.

Theorem 15.3.16. Decomposition into Cycles.

Proof.

Subsection 15.3.3 Parity of Permutations and the Alternating Group

Theorem 15.3.17.

Definition 15.3.18. The Alternating Group.

Theorem 15.3.19.

Proof.

Example 15.3.20. The Sliding Tile Puzzle.

Subsection 15.3.4 Dihedral Groups

Observation 15.3.23. Realizations of Groups.

Definition 15.3.26. Dihedral Group.

Note 15.3.27. Caution.

Example 15.3.28. A Letter-facing Machine.

Exercises 15.3.5 Exercises

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

Example 15.3.6. The significance of $S_{3}$ .