Section 2.6 Permutation Groups
Theorem 2.47.
The symmetric group on
Proof.
The identity of
Example 2.48.
Consider the subgroup
The following table tells us how to multiply elements in the permutation group
Remark 2.49.
Though it is natural to multiply elements in a group from left to right, functions are composed from right to left. Let
Example 2.50.
Permutation multiplication is not usually commutative. Let
Then
but
Subsection 2.6.1 Cycle Notation
The notation that we have used to represent permutations up to this point is cumbersome, to say the least. To work effectively with permutation groups, we need a more streamlined method of writing down and manipulating permutations. A permutationExample 2.51.
The permutation
is a cycle of length
is a cycle of length
Not every permutation is a cycle. Consider the permutation
This permutation actually contains a cycle of length 2 and a cycle of length
Example 2.52.
It is very easy to compute products of cycles. Suppose that
If we think of
and
then for
or
Example 2.53.
The cycles
The product of two cycles that are not disjoint may reduce to something less complicated; the product of disjoint cycles cannot be simplified.
Proposition 2.54.
Let
Proof.
Let
Do not forget that we are multiplying permutations right to left, which is the opposite of the order in which we usually multiply group elements. Now suppose that
However,
Similarly, if
Theorem 2.55.
Every permutation in
Proof.
We can assume that
then
Example 2.56.
Let
Using cycle notation, we can write
Remark 2.57.
From this point forward we will find it convenient to use cycle notation to represent permutations. When using cycle notation, we often denote the identity permutation by
Subsection 2.6.2 Transpositions
The simplest permutation is a cycle of lengthProposition 2.58.
Any permutation of a finite set containing at least two elements can be written as the product of transpositions.
Example 2.59.
Consider the permutation
As we can see, there is no unique way to represent permutation as the product of transpositions. For instance, we can write the identity permutation as
or by
but
Lemma 2.60.
If the identity is written as the product of
then
Proof.
We will employ induction on
where
The first equation simply says that a transposition is its own inverse. If this case occurs, delete
By induction
In each of the other three cases, we can replace
At some point either we will have two adjacent, identical transpositions canceling each other out or
Theorem 2.61.
If a permutation
Proof.
Suppose that
where
Subsection 2.6.3 The Alternating Groups
One of the most important subgroups ofTheorem 2.62.
The set
Proof.
Since the product of two even permutations must also be an even permutation,
where
is also in
Proposition 2.63.
The number of even permutations in
Proof.
Let
by
Suppose that
Therefore,
Example 2.64.
The group
One of the end-of-chapter exercises will be to write down all the subgroups of
Subsection 2.6.4 Dihedral Groups
A special type of permutation group is the dihedral group. Recall the symmetry group of an equilateral triangle in Chapter 2 . Such groups consist of the rigid motions of a regularTheorem 2.66.
The dihedral group,
Theorem 2.67.
The group
Proof.
The possible motions of a regular
We will denote the rotation
Label the
We will leave the proof that
Example 2.70.
The group of rigid motions of a square,
and the reflections are
The order of
The Motion Group of a Cube.
We can investigate the groups of rigid motions of geometric objects other than a regularProposition 2.72.
The group of rigid motions of a cube contains
Theorem 2.73.
The group of rigid motions of a cube is
Proof.
From Proposition 2.72 , we already know that the motion group of the cube has
Subsection 2.6.5 Historical Note
Lagrange first thought of permutations as functions from a set to itself, but it was Cauchy who developed the basic theorems and notation for permutations. He was the first to use cycle notation. Augustin-Louis Cauchy (1789– 1857) was born in Paris at the height of the French Revolution. His family soon left Paris for the village of Arcueil to escape the Reign of Terror. One of the family's neighbors there was Pierre-Simon Laplace (1749– 1827), who encouraged him to seek a career in mathematics. Cauchy began his career as a mathematician by solving a problem in geometry given to him by Lagrange. Cauchy wrote over 800 papers on such diverse topics as differential equations, finite groups, applied mathematics, and complex analysis. He was one of the mathematicians responsible for making calculus rigorous. Perhaps more theorems and concepts in mathematics have the name Cauchy attached to them than that of any other mathematician.Reading Questions 2.6.6 Reading Questions
1.
What is the order of the group
2.
Write the permutation
3.
Write
4.
After reading the section, what questions do you still have? Write at least one well formulated question (even if you think you understand everything).
Exercises 2.6.7 Practice Problems
1.
Write the following permutations in cycle notation.
(a) \((12453)\text{;}\) (b) \((14)(35)\text{;}\) (c) \((13)(25)\text{;}\) (d) \((24)\text{.}\)
2.
Compute each of the following.
(a) \((135)(24)\text{;}\) (b) \((253)\text{;}\) (c) \((14)(23)\text{;}\) (d) \((12)(56)\text{;}\) (e) \((1324)\text{;}\) (f) \((13254)\text{;}\) (g) \((134)(25)\text{;}\) (h) \((14)(235)\text{;}\) (i) \((143)(25)\text{;}\) (j) \((1)\text{;}\) (k) \(4\) (i.e., the order of the element); (l) \(2\text{;}\) (m) \((12)\text{;}\) (n) \((17352)\text{;}\) (o) \((374)\text{;}\) (p) \((476)(1532)\text{.}\)
3.
Express the following permutations as products of transpositions and identify them as even or odd.
(a) \((16)(15)(13)(14)\) (even); (b) \((15)(56)(23)(24)\) (even); (c) \((16)(14)(12)\) (odd); (d) \((17)(72)(25)(54)(14)(42)(23)(15)(54)(46)(63)(32)\) (even); (e) \((14)(42)(26)(63)(37)\) (odd).
5.
List all of the subgroups of
and
Are any of these sets subgroups of
(a) \(\{ (13), (13)(24), (132), (134), (1324), (1342) \}\) is not a subgroup.
(b) \(\{(1), (134), (143), (13), (14), (34)\}\) is a subgroup.
(c) \(\{(13), (134)\}\) is not a subgroup.
6.
Find all of the subgroups in
There are subgroups of orders 1, 2, 3, 4, and 12. You have multiple choices for the subgroups of order 2 and 3.
7.
Find all possible orders of elements in
The possible orders in \(S_7\) are 1, 2, 3, 4, 5, 6, 7, 10, and 12. In \(A_7\) you can only have orders 1, 2, 3, 5, 6, and 7.
8.
Show that
\((12345)(678)\text{.}\)
9.
Does
No. We will give a good reason why in chapter 6.
10.
Find an element of largest order in
\((123)\text{,}\) \((1234)\text{,}\) \((12)(345)\text{,}\) \((123456)\text{,}\) \((123)(4567)\text{,}\) \((123)(45678)\text{,}\) \((1234)(56789)\text{,}\) \((12)(345)(678910)\text{.}\)
Exercises 2.6.8 Collected Homework
C1.
Consider the group
Find
the cyclic subgroup of generated by (Just list out all its elements.)What is
Justify your answer.
C2.
In the previous problem you found a cyclic subgroup of order 6 in