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.
2. Theorem concerning disjoint cycle decomposition.

Calculation Problems:

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.

Book Problems:

1.

3.

5.

7.

9.

10.

11.

13.

14.

15.

16.