Permutations

Section 1.5 Permutations

Definition 1.5.1. Permutations.

Let \(A\) be a nonempty set. A permutation of \(A\) is a bijective function \(\sigma\colon A\rightarrow A\text{.}\) We denote by \(S_A\) the set of all permutations of \(A\text{:}\) i.e.,

\begin{equation*} S_A=\{\sigma\colon A\rightarrow A\mid \sigma \text{ bijective}\}\text{.} \end{equation*}

If \(A=\{1,2,\dots, n\}\) for some positive integer \(n\text{,}\) we will write \(S_n\) for \(S_A\text{.}\)

🔗

Specimen 10. Permutation group.

Let \(A\) be a nonempty set. The pair \((S_A, \circ)\text{,}\) where \(\circ\) is function composition, is a group called the permutation group of \(A\text{.}\)

🔗

The group identity of \(S_A\) is the identity function \(\id\colon A\rightarrow A\) defined as \(\id(a)=a\) for all \(a\in A\text{.}\) Given a permutation \(\sigma\in S_A\text{,}\) its group inverse is the inverse function \(\sigma^{-1}\text{.}\)

🔗

If \(A\) is finite of cardinality \(\abs{A}=n\text{,}\) then a standard counting argument shows that \(\abs{S_A}=n!\text{.}\)

🔗

Notation 1.5.2. Table notation.

Let \(A=\{a_1,a_2,\dots, a_n\}\text{,}\) where the \(a_i\) are distinct. Given a permutation \(\sigma\colon A\rightarrow A\) satisfying

\begin{equation*} \sigma(a_i)=b_i \end{equation*}

for all \(1\leq i\leq n\text{,}\) we represent \(\sigma\) using table notation as

\begin{equation*} \sigma=\left( \begin{array}{cccc} a_1\amp a_2\amp \dots \amp a_n\\ b_1\amp b_2\amp \dots \amp b_n \end{array} \right) \end{equation*}

🔗

Example 1.5.3. Permutations: table notation.

Write down all elements of \(S_3\) using table notation.

🔗

Although table notation gives a clear and direct representation of a permutation, it is a bit cumbersome notationally, especially when we begin to compute compositions of multiple permutations. Cycle notation, described below, is a sleeker more computationally friendly manner of notating permutations.

🔗

Definition 1.5.4. Cycles.

Let \((a_1,a_2,\dots, a_k)\) be a \(k\)-tuple of distinct elements of the set \(A\text{.}\) The permutation \(\sigma\in A\) defined as

\begin{align*} \sigma(a_i) \amp =a_{i+1}, 1\leq i\leq k-1\\ \sigma(a_k) \amp =a_1\\ \sigma(a) \amp =a \text{ for } a\notin\{a_1,a_2,\dots, a_k\} \end{align*}

is called the k-cycle of \(A\) associated to the tuple \((a_1,a_2,\dots, a_k)\text{,}\) and is denoted

\begin{equation*} \sigma=(a_1\ a_2\,\dots a_k)\text{.} \end{equation*}

Two cycles

\begin{align*} \sigma\amp =(a_1\ a_2\,\dots a_k) \amp \tau=(b_1\ b_2\,\dots b_\ell) \end{align*}

are disjoint if \(\{a_1,a_2,\dots, a_k\}\cap \{b_1,b_2,\dots, b_\ell\}=\emptyset\text{.}\)

🔗

Proposition 1.5.5. Cycle arithmetic.

Let \(\sigma=(a_1\ a_2\, \dots a_k)\) and \(\tau=(b_1\ b_2\,\dots b_\ell)\) be cycles of the set \(A\text{.}\)

For all \(1\leq i\leq k\text{,}\) we have

\begin{equation*} \sigma=(a_i\ a_{i+1}\dots\, a_k\ a_1\dots a_{i-1})\text{.} \end{equation*}

🔗

🔗
\(\ord \sigma=k\text{.}\)
🔗

🔗
\(\displaystyle \sigma^{-1}=(a_k\ a_{k-1}\,\dots a_1)\)
🔗

🔗
If \(\sigma \) and \(\tau\) are disjoint, then \(\sigma\tau=\tau\sigma\text{:}\) i.e., disjoint cycles commute.
🔗

🔗
If \(\sigma=\sigma_1\sigma_2\cdots \sigma_r\text{,}\) where the \(\sigma_i\) are pairwise disjoint cycles, then the order of \(\sigma\) is the least common multiple of the orders of the \(\sigma_i\text{:}\) i.e.,

\begin{equation} \ord \sigma=\lcm(\ord\sigma_1,\ord\sigma_2,\dots, \ord\sigma_r)\text{.}\tag{1.5.1} \end{equation}

🔗

🔗

🔗

Proof.

Left as a homework exercise.

🔗

Theorem 1.5.6. Cycle decomposition.

Let \(A\) be a finite set, and let \(\sigma\in S_A\text{.}\)

We can write

\begin{equation} \sigma=\sigma_1\sigma_2\cdots \sigma_r\tag{1.5.2} \end{equation}

where the \(\sigma_i\) are pairwise disjoint cycles.

🔗

🔗
If we assume that the union of the set of elements appearing in the cycles \(\sigma_i\) is all of \(A\text{,}\) then the set \(\{\sigma_1,\sigma_2,\dots, \sigma_r\}\) of disjoint cycles appearing in the decomposition (1.5.2) is uniquely determined by \(\sigma\text{.}\)
🔗

🔗

🔗

Proof.

The following is an outline for proving this theorem. Fix \(\sigma\in S_A\text{.}\)

🔗

Step 1.

Prove that the relation

\begin{equation*} a\sim a'\iff a'=\sigma^n(a) \text{ for some } n\in \Z \end{equation*}

is an equivalence relation on \(A\)

🔗

Step 2.

Let \(C_1, C_2,\dots, C_r\) be the equivalence classes defined by the relation above. Prove that for each \(1\leq i\leq r\) and each \(a\in C_i\text{,}\) we have

\begin{equation*} C_i=\{a, \sigma(a), \sigma^2(a), \dots, \sigma^{n_i-1}(a)\}\text{,} \end{equation*}

where \(n_i=\abs{C_i}\) and \(\sigma^n(a)=a\text{.}\)

🔗

Step 3.

For each \(1\leq i\leq r\text{,}\) pick \(a_i\in C_i\) such that

\begin{equation*} C_i=\{a_i, \sigma(a_i), \dots, \sigma^{n_i-1}(a_i)\}\text{,} \end{equation*}

and let \(\sigma_i\) be the cycle

\begin{equation*} \sigma_i=\left(a_i\ \sigma(a_i)\ \dots \ \sigma^{n_i-1}(a_i)\right)\text{.} \end{equation*}

Show that

\begin{equation*} \sigma=\sigma_1\sigma_2\cdots \sigma_r\text{.} \end{equation*}

🔗

Step 4 (uniqueness).

Assume \(\sigma=\tau_1\tau_2\cdots \tau_s\) be a decomposition of \(\sigma\) into disjoint cycles \(\tau_i\text{,}\) and that the union of elements appearing in the \(\tau_i\) is \(A\text{.}\) For each \(1\leq i\leq s\text{,}\) let \(D_i\) be the set of elements of \(A\) appearing in the cycle \(\tau_i\text{.}\)

Prove that \(\{D_1,D_2,\dots, D_s\}=\{C_1, C_2,\dots, C_r\}\text{.}\)
🔗

🔗
Prove that \(s=r\) and that after a reordering, we have \(D_i=C_i\) for all \(1\leq i\leq r\text{.}\)
🔗

🔗
Prove that \(\tau_i=\sigma_i\text{.}\)
🔗

🔗

🔗

Remark 1.5.7. Uniqueness of cycle decomposition.

Let’s make a few important remarks about the uniqueness of cycle decomposition.

First off, to have any uniqueness property whatsoever, the cycle decomposition must be a disjoint one. Indeed, for all \(2\)-cycles \((a\ b)\) we have

\begin{equation*} \id=(a\ b)(a\ b)\text{,} \end{equation*}

giving us many different ways of writing \(\id\) as a composition of 2-cycles.

🔗

🔗
Although the cycles \(\sigma_i\) appearing in a disjoint cycle decomposition

\begin{equation*} \sigma=\sigma_1\sigma_2\cdots \sigma_r \end{equation*}

are unique, the order in which they appear in this expression is not unique. Indeed, since disjoint cycles commute, we can order the \(\sigma_i\) on the right side of the equation any way we like!

🔗

🔗
Furthermore, remember that any given cycle

\begin{equation*} \tau=(a_1\ a_2\, \dots a_k) \end{equation*}

can itself be expressed in many (in fact \(k\)) different ways.

🔗

🔗

🔗

Example 1.5.8. Cycle decomposition.

We work in the group \(S_7\text{.}\) Let

\begin{align*} \sigma \amp = \begin{pmatrix} 1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\\ 3\amp 5\amp 1\amp 7\amp 2\amp 4\amp 6 \end{pmatrix}\\ \sigma_1 \amp =(1\ 4\ 5\ 6)\\ \sigma_2 \amp =(2\ 7\ 3)\\ \sigma_3 \amp =(2\ 4\ 6)\text{.} \end{align*}

Compute disjoint cycle decompositions of the following permutations.
1. \(\displaystyle \sigma\)
  🔗
  
  🔗
2. \(\displaystyle \sigma^{-1}\)
  🔗
  
  🔗
3. \(\displaystyle \sigma_1\sigma_2\sigma_3\)
  🔗
  
  🔗
4. \(\displaystyle \sigma_1\sigma_3\sigma_2\)
  🔗
  
  🔗
🔗
🔗
Compute \(\ord \sigma\text{.}\)
🔗

🔗
True or false: \(\sigma_1\sigma_2\sigma_3=\sigma_1\sigma_3\sigma_2\text{.}\)
🔗

🔗

🔗

Solution.

🔗

Although the previous examples should make clear how to decompose an arbitrary permutation into disjoint cycles, we record here a more official description of this procedure.

🔗

Procedure 1.5.9.

Let \(A\) be a finite set, and let \(\sigma\in S_A\text{.}\) To compute a decomposition of \(\sigma\) into disjoint cycles, proceed as follows.

Initialize: set \(\sigma:=\emptyset\text{,}\) the empty product of cycles.
🔗

🔗
If all elements of \(A\) appear in the cycles appearing in \(\sigma\text{,}\) then stop.
🔗

Otherwise, pick any \(a\in A\) that does not appear in \(\sigma\) and compute the cycle

\begin{equation*} \tau=(a\ \sigma(a)\ \sigma^2(a)\, \dots \sigma^{n_1-1}(a)) \end{equation*}

it generates by evaluating at successive powers \(\sigma^i(a)\) until you get an output of \(a\text{.}\)

🔗

Update: set \(\sigma:=\sigma\tau\) and repeat Step 2.
🔗

🔗

🔗

Prev Top Next