Section 10.2 Permutation Groups
Theorem 10.3.
The symmetric group on
Proof.
The identity of
Example 10.4.
Consider the subgroup
The following table tells us how to multiply elements in the permutation group
Remark 10.5.
Though it is natural to multiply elements in a group from left to right, functions are composed from right to left. Let
Example 10.6.
Permutation multiplication is not usually commutative. Let
Then
but
Subsection 10.2.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 10.7.
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 10.8.
It is very easy to compute products of cycles. Suppose that
If we think of
and
then for
or
Example 10.9.
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 10.10.
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 10.11.
Every permutation in
Proof.
We can assume that
then
Example 10.12.
Let
Using cycle notation, we can write
Remark 10.13.
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
Worksheet 10.2.2 Activity: Writing Cycles and Permutations
1.
Can every permutation in
2.
How should we define “cycle”? Write a definition. Some considerations: is
3.
Here are a few permutations of
A transposition (or
4.
Can the cycle
5.
What about the product
6.
Can you write
7.
What numbers of transpositions can you write the identity
Subsection 10.2.3 Transpositions
The simplest permutation is a cycle of lengthProposition 10.14.
Any permutation of a finite set containing at least two elements can be written as the product of transpositions.
Example 10.15.
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 10.16.
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 10.17.
If a permutation
Proof.
Suppose that
where
Subsection 10.2.4 The Alternating Groups
One of the most important subgroups ofTheorem 10.18.
The set
Proof.
Since the product of two even permutations must also be an even permutation,
where
is also in
Proposition 10.19.
The number of even permutations in
Proof.
Let
by
Suppose that
Therefore,
Example 10.20.
The group
One of the end-of-chapter exercises will be to write down all the subgroups of
Subsection 10.2.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.Exercises 10.2.6 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 10.2.7 Collected Homework
1.
The identity can be written as
2.
Bonus: One way you could prove that
Prove that