1.1 Permutations
Definition 1.1.1. Let \(S\) be a non-empty set. A one to one mapping from \(S\) onto itself is a
permutation.
Example 1.1.2. Let \(S = \{1\, , \, 2\, , \, 3\, , \, 4\}\). We define a permutation \(\alpha : \, S\longrightarrow S\) by \(\alpha (1) = 2\, , \, \alpha (2) = 3\, ,\)
\(\alpha (3) = 1\, , \, \alpha (4) = 4\). Hence; \(\alpha \)
\[\alpha = \begin {pmatrix} 1 & 2 & 3 & 4\\ 2 & 3 & 1 & 4\\ \end {pmatrix} \hspace {0.7cm}\text {showing mappings and ``not" a matrix.}\]
Clearly, \(\alpha \) is \(1-1\) and onto and hence it is a permutation.
Theorem 1.1.3. The set of all permutation of a non-empty set \(S\) is a group with respect to
composition of permutations. This is called a symmetric group denoted as \(Sym(S)\).
Consider \(\, S = \{1\, , \, 2\, , \, 3\, , \, 4\, , \, 5\}\). Let \(\, \delta = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\, \) and \(\, \gamma = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 2 & 3\\ \end {pmatrix}\,\, \) in \(Sym(S)\) or \(S_5\)
Compute:
- (i)
- \(\gamma \delta = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 2 & 3\\ \end {pmatrix} \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix} = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 2 & 1 & 3 & 5\\ \end {pmatrix}\)
- (ii)
- \(\gamma ^2 = \gamma \gamma = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 2 & 3\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 2 & 3\\ \end {pmatrix} = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 2 & 5 & 4 & 1\\ \end {pmatrix}\)
- (iii)
- \(\delta \gamma ^2 = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 2 & 5 & 4 & 1\\ \end {pmatrix} = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 4 & 1 & 5 & 2\\ \end {pmatrix}\)
Proof. Let \(\operatorname {Sym}(S)\) be the set of bijections \(S\rightarrow S\) under composition.
Closure: a composition of bijections is a bijection. Associativity: composition of functions is always associative. Identity: the identity map \(\iota (s)=s\) is a bijection and satisfies \(\iota \circ f = f\circ \iota = f\). Inverses: a bijection has a two-sided inverse function, which is itself a bijection, and \(f\circ f^{-1} = f^{-1}\circ f = \iota \).
Hence \(\operatorname {Sym}(S)\) is a group. □
Note. No property of \(S\) was used beyond its being a set, so this holds for infinite \(S\) as well. When \(S\) is finite with \(n\) elements the group is \(S_n\), of order \(n!\), and Cayley’s theorem later shows every finite group is isomorphic to a subgroup of some \(S_n\) — which is why permutation groups are not one example among many but the general case in disguise.
Exercise 1.1.4. Work out the following
- (a)
- \(\delta ^2 \gamma \)
- (b)
- \(\delta \gamma \)
- (c)
- \(\delta ^5\)
- (d)
- Is the group commutative?
Solutions (Gabriel’s way!!!)
- (a)
- \(\delta ^2 \gamma = \delta \delta \gamma = \begin {bmatrix} \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix} \end {bmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 2 & 3\\ \end {pmatrix}\) \begin {align*} &= \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 5 & 3 & 1 & 2\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 2 & 3\\ \end {pmatrix}\\\\ & = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 1 & 4 & 5 & 3\\ \end {pmatrix} \end {align*}
- (b)
- \(\delta \gamma = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 2 & 3\\ \end {pmatrix} = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 5 & 2 & 4 & 3\\ \end {pmatrix}\)
- (c)
- \(\delta ^5 = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\) \begin {align*} & = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 1 & 3 & 2 & 4\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\\\\ & = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 2 & 3 & 4 & 5\\ \end {pmatrix}\begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix}\\\\ & = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1\\ \end {pmatrix} \end {align*}
\(\therefore \, \delta ^5 = \delta \,\) and \(\, \delta ^4 = (1)(2)(3)(4)(5)\)
- (d)
- \(\gamma \delta = \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 2 & 1 & 3 & 5\\ \end {pmatrix} \neq \begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 5 & 2 & 4 & 3\\ \end {pmatrix} = \delta \gamma \)
\(\therefore \,\) The group is not commutative.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.