Math 360, Fall 2021, Assignment 11

The danger already exists that the mathematicians have made a covenant with the devil to darken the spirit and to confine man in the bonds of Hell.

- Saint Augustine

Read:

1. Section 9.

Carefully define the following terms, then give one example and one non-example of each:

1. Fixed point (of a permutation $\pi$).
2. Moving point (of a permutation $\pi$).
3. Disjoint (permutations $\pi$ and $\sigma$).
4. Orbit (of a permutation $\pi$).
5. Cycle.
6. $(i_1,\dots,i_k)$ (the cycle determined by the sequence $i_1,\dots,i_k$).
7. Length (of a cycle).

Carefully state the following theorems (you do not need to prove them):

1. Theorem relating $\sigma\tau$ to $\tau\sigma$, when $\sigma$ and $\tau$ are disjoint.
2. Theorem concerning disjoint cycle decomposition.

Carefully practice the following calculations, giving a worked example of each:

1. Conversion of two-row notation to cycle notation.
2. Conversion of cycle notation to two-row notation.
3. Composition of two permutations, expressed in cycle notation.
4. Inversion of a permutation, expressed in cycle notation.

Solve the following problems:

1. Section 9, problems 1, 3, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, and 16. (Hint for 14-16: recall that the order of a finite group element $g$ is the least positive integer $n$ with $g^n=1$. For a permutation, this will be the least common multiple of the lengths of the cycles in its disjoint cycle decomposition.)

--------------------End of assignment--------------------

Definitions:

1. Fixed point (of a permutation $\pi$): $i$ is said to be a fixed point of $\pi$ if $\pi (i) = i$.
2. Moving point (of a permutation $\pi$): $i$ is said to be a moving point of $\pi$ if not $\pi (i) = i$.
3. Disjoint (permutations $\pi$ and $\sigma$): Suppose $\pi , \sigma \in S_n$ if every point moved by $\pi$ is fixed by $\sigma$, and every point moved by $\sigma$ is fixed by $\pi$. For example: $(1 5 3)(2 4)$.
4. Orbit (of a permutation $\pi$): Suppose $\pi \in S_n$. Define a relation $~_{\pi}$ on $\{1, \dots , n\}$ as following: $i ~_{\pi} \iff \exists k \in \mathbb Z$ with $\pi^{k}(i) = j.$
5. Cycle: $\pi$ is a cycle if it has exactly one moving obit. For example, $(2 3 4)(1)(5)(6)$, $(2 3 4)$ is a moving obit and $1,5,6$ are all fixed points
6. $(i_1,\dots,i_k)$ (the cycle determined by the sequence $i_1,\dots,i_k$): the cycle notation means the cycle that sends $i_1$ to $i_2$, $i_2$ to $i_3$ $\cdots$ and $i_l$ to $i_1$. Note that $(i_1, i_2 \dots i_l) = (i_l, i_1 \dots i_{l-i})$. For example, cycle $(1 2 3 4 5 6) = (6 1 2 3 4 5)$.
7. Length (of a cycle): $l$ is called the length of $(i_1, i_2 \dots i_l)$. Any cycle of length $l$ is an l-cycle. For example: $(1 2 3 4)$ is a 4-cycle with length 4.

Theorems:

1. Theorem relating $\sigma\tau$ to $\tau\sigma$, when $\sigma$ and $\tau$ are disjoint: Disjoint permutations commute. If $\sigma , \pi$ are disjoint, $\sigma \pi = \pi \sigma$.
2. Theorem concerning disjoint cycle decomposition: Every $\pi \in S_n$ can be written as a product of disjoint cycles. This expression is unique up to the order in which the cycles are listed. (The identity map is the empty product, the product of no cycles at all).

Calculation Problems:

1. Conversion of two-row notation to cycle notation: $\begin{pmatrix}1&2&3&4&5&6\\2&1&3&6&5&4\end{pmatrix} = (1 2)(4 6)$
2. Conversion of cycle notation to two-row notation: $(1 3 6)(2 4) = \begin{pmatrix}1&2&3&4&5&6\\3&4&6&2&5&1\end{pmatrix}$
3. Composition of two permutations, expressed in cycle notation: $(1 2)(4 6)(1 3 6)(2 4) = (2 6)(1 3 4)$
4. Inversion of a permutation, expressed in cycle notation: $[(1 3 6)(2 4)]^{-1} = (4 2)(1 6 3)$

Book Problems:

1. (1 5 2)(4 6)

3. (1 2 3 5 4)(7 8)

5. $(1 3 5 7 \dots)(2 4 6 8 \dots)$

7. (1 4 5 8 7 2)

9. (1 5 8)(2 4 7)

10. (1 8)(3 6 4)(5 7)

11. (1 3 4)(2 6)(5 8 7)

13.

a. What is the order of the cycle (1, 4, 5, 7)? Answer: 4

b. State a theorem suggested by part (a): lcm

c. $lcm(2,3) = 6; lcm(2,4) = 4$

d. 10. 6, 11. 6

e. lcm(all orders of disjoint cycles)

14. 6

15. 6

16. 12