Math 360, Fall 2013, Assignment 6
I tell them that if they will occupy themselves with the study of mathematics, they will find in it the best remedy against the lusts of the flesh.
- - Thomas Mann, The Magic Mountain
Carefully define the following terms, then give one example and one non-example of each:[edit]
- Orbits (of a permutation).
- Cycle.
- Disjoint cycles.
- Transposition.
- Even permutation.
- Odd permutation.
- Alternating group on $n$ letters.
Carefully state the following theorems (you need not prove them):[edit]
- Theorem concerning generation of $S_n$ by transpositions (Corollary 9.12 in the text).
- Theorem concerning the parity of a permutation (Theorem 9.15).
- Theorem concerning the order of the alternating group (Theorem 9.20).
Solve the following problems:[edit]
- Section 9, problems 3, 5, 9, 10, 15, 24, and 29.
Questions:[edit]
Book Problems:[edit]
- 9.3
Find all orbits of:
$$ \left ( \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 2 & 3 & 5 & 1 & 4 & 6 & 8 & 7 \end{array}\right ) $$
- 9.5
Find all orbits of:
$$ \sigma :\mathbb{Z}\rightarrow \mathbb{Z} $$
where \(\sigma(n)=n+2\).
- 9.9
Compute the product: \((1,2)(4,7,8),7,2,8,1,5\).
- 9.10
Express the permutation as a product of disjoint cycles:
$$ \left ( \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 8 & 2 & 6 & 3 & 7 & 4 & 5 & 1 \end{array} \right ) $$
- 9.15
Find the maximum possible order of an element of \(S_6\).
- 9.24
Which of the permutations in \(S_3\) are even permutations? Give the table for the alternating group \(A_3\).
- 9.29
Show that for every subgroup \(H\) of \(S_n\) for \(n\geq 2\), either all the permutations in \(H\) are even or exactly half of them are even.
Solutions:[edit]
Definitions:[edit]
- Orbits of a Permutation.
Definition:
Let \(\sigma\) be a permutation of \(A\). We define the equivalence relation \(~\) by:$$\forall a,b\in A: a~b \leftrightarrow b = \sigma^n(a)$$
These equivalence classes are the orbits of \(\sigma\).
Example:
Let \(A\) be the set \(\{1,2,3\}\), and \(\sigma = (1,3,2)\). The orbits of \(\sigma\) are \([1]\) and \([2]=[3]\).
Non-Example:
For the same \(A\) and \(\sigma\), \([1]=[2]\) and \([3]\) are not orbits.
- Cycle.
Definition:
A permutation with only one orbit with more than one element is a cycle. So it moves only some elements, and all those elements move together.
Example:
The permutation \(\sigma(x) = x+1\) on \(\mathbb{Z}_n\) is a cycle.
Non-Example:
The permutation \(\sigma(x)=x+2\) on \(\mathbb{Z}_4\) is not a cycle - it turns even integers into even integers, and odd integers into odd integers, so there are two different orbits.
- Disjoint Cycles.
Definition:
Two cycles (on the same set) are disjoint if their non-trivial orbits are disjoint - they move different elements.
Example:
The cycles \((1,2)\) and \((3,4)\) are disjoint.
Non-Example:
The cycles \((1,2,3)\) and \((3,4,5)\) are not disjoint - they share 3.
- Transposition.
Definition:
A transposition is a cycle of "length" 2. (It is self-inverse. It only takes two applications of the permutation to get back the original).
Example:
The cycle \(1,2\) on 8 letters is a transposition - it switches 1 and 2, then switches them back.
Non-Example:
The cycle \(1,2,3\) is not a transposition - it moves three elements.
- Even Permutation.
Definition:
An even permutation is a permutation composed of an even number of transpositions.
Example:
The permutation \((1,2)(3,4)\) is even - it is composed of two transpositions.
Non-Example:
- Odd Permutation.
Definition:
An odd permutation is a permutation that is the composition of an odd number of transpositions.
Example:
Non-Example:
- Alternating Group on \(n\) Letters.
Definition:
The alternating group is the group of even permutations.
Example:
Non-Example:
Theorems:[edit]
- Theorem Concerning Generation of \(S_n\) by Transpositions.
Any permutation is the composition of transpositions. Therefore \(S_n\) is generated by the set of all transpositions. (Not sure exactly which theorem this refers. This is my best guest).
- Theorem Concerning the Parity of a Permutation.
No permutation is both even and odd.
- Theorem Concerning the Order of the Alternating Group
The order of \(A_n\) is \(|S_n|/2 = n!/2\).
Book Problems:[edit]
- 9.3
The orbits are: \(\{1,2,3,5,4\},\{6\},\{7,8\}\)
- 9.5
The orbits are \(\mathbb{E}\) and \(\mathbb{O}\).
- 9.9
\((1,5,8)(2,4,7)(3)(6)\)
- 9.10
Product of disjoint cycles:$$ (1,8)(2)(3,6,4)(5,7) $$
Product of transpositions:$$ (1,8)(3,4)(3,6)(5,7) $$
- 9.15
The maximum order is 6.
- 9.24
Even permutations of \(S_3\):
- 9.29
