Friday, November 23, 2012

Permutation groups and cycles

In this lecture, we talked about permutation groups, cycles, and the order of a group. Nicolas Simard temporarily filled, as Henri Darmon was away at a conference.

1Permutation groups¶

A permutation of a set $T$ is a bijection $T \to T$. If $T$ is finite - for example, $\mathbb N$ - then the set of all permutations is denoted $\Sigma_T$ or $S_n$ (we'll use the latter notation) where $n = |T|$.

Of course, the actual elements in $T$ don't matter. We will refer to them as $1, 2, 3, \ldots n$ in the rest of the section, but they could really be anything and none of the properties would change.

1.1Proving that it's a group¶

To prove that $S_n$ is a group, we need to show that it satisfies the following properties:

(0) If $f, g \in S_n$ (so they are bijections between 2 sets of $n$ elements) then $f \circ g$ and $g \circ f$ are also bijective. Well, this is sort of a necessary condition when defining composition, so $\checkmark$
(1) Assocativity: $(F \circ g) \circ h(t) = (f \circ g)(h(t)) = f(g(h(t))) = f(g\circ h(t)) = f\circ (g\circ h)(t)$ for all $t$.
(2) Identity element: $1_R: T \to T$ is $1_T(t) = t$. Then $1_T \circ f = f \circ 1_T = f$.
(3) $f^{-1}$ is the inverse of $f$ (it can always be defined because $f$ is bijective). Then $f \circ f^{-1} = f^{-1} \circ f = 1_T$.

1.2Number of elements in a permutation group¶

The number of elements in $S_n$ is $n!$. Reason: for $f(1)$, there are $n$ choices. For $f(2)$, since we need to preserve injectivity, there are $n-1$ choices. Etc.

1.3Examples and notation¶

If $n=1$, $S_n = \{1_T\}$ (so just the identity function).

If $n=2$, there are 2 functions, which we can write as follows:

$$1_T = \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix} \qquad \sigma = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$$

(The top row is the domain, the bottom row is the range. $\sigma$ is just an arbitrary name for the other function in this set. Note that these are not actually matrices - this is just the notation.)

If $n=3$, there are $3! = 6$ functions, which we can enumerate as follows:

$$\left \{\begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} \right \}$$

1.4Composition¶

Composing two functions in a permutation group is easy. Let's look at an example in $S_5$.

$$f = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{pmatrix} \qquad g = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 &4 & 3 & 2 & 1 \end{pmatrix}$$

then, their composition $f \circ g$ is found by mapping each element to its image under $g$, then under $f$:

$$f \circ g = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 4 & 3 & 2 \end{pmatrix}$$

Incidentally, composition is only commutative in $S_1$ and $S_2$; for all other $n$, it is not.

2Cycles¶

The notation for a cycle is $\sigma = (1, 2, 3)$. This tells us that $1 \to 2$, $2 \to 3$, $3 \to 1$ in a permutation group. Any other element in $S_n$ but not mentioned in the cycle simply stays the same. Note that this is equivalent to $(2, 3, 1)$ which is equivalent to $(3, 1, 2)$ (so cycles are invariant under rotation or something).

Another example of a cycle: $(4, 1)$ which means that $4 \to 1$, $1 \to 4$, $2 \to 2$ and $3 \to 3$. Incidentally, a cycle of two elements (like this one) is called a transposition.

2.1Cycle decomposition¶

We can decompose any permutation group into cycles. Some examples:

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{pmatrix} = (1, 2, 3) (4, 5)$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 1 & 4 & 5 \end{pmatrix} = (1, 3, 6, 5, 4)(2) = (1, 3, 6, 5, 4)$$

In the latter example, the (2) at the end is not necessary to write so we can just omit it.

3Order¶

The order of a group $G$ is the number of elements in $G$. We can write this as $|G|$ or $\#G$. So $|S_n| = n!$, $|\mathbb Z / n \mathbb Z| = n$. We can think of it as the cardinality of the set under $G$, basically, but the notion of an order is separate.

The order of an element in $G$ is the size of its cycle. We can write it as $|<g>|$ or $|\# <g>|$. If $G = <g>$ for some $g$, then $G$ is cyclic (i.e., it's generated by one cycle? Not completely sure about the notation here).

Example: the group $(\mathbb Z, +)$ is cyclic, generated by one.