# Permutation Groups / Permutation Notations / Order of A Permutation / Transpositions

Yao Yao on April 27, 2020

## 1. Permutation Groups

Definition 1: Let $X$ be a set. A permutation of $X$ is simply a bijection $f: X \to X$

• 那既然 permutation 是一个双射函数，那 permutation 的 composition $f \circ g$ 也是一个 permutation
• 同时，双射函数的逆函数存在，且也是双射的，所以 $f^{-1}$ 也是 permutation

Lemma 2: Let $X$ be a set. The set of all permutations on $X$, under the operation of composition $\circ$, forms a Group $S(X)$.

Group 的概念见 Is vector space a field? And what are: Groups / Rings / Fields / Vector Spaces?。简而言之，我们说 $S(X)$ 是 Group 是因为它满足 Group 的 4 个 axiom：

1. Closure: $\forall f, g \in S(X), f \circ g \in S(X)$
2. Associativity: $\forall f, g, h \in S(X), (f \circ g) \circ h = f \circ (g \circ h)$
3. Identity element: $\exists I \in S(X)$ such that $I(X) = X$
4. Inverse element: $\forall f \in S(X), \exists f^{-1} \in S(X)$ such that $f \circ f^{-1} = I$
• 注意交换律 Commutativity 不是 Group 的 axiom
• i.e. $f \circ g \not\equiv g \circ f$

Lemma 3: If $\vert X \vert = n$, then $\vert S(X) \vert = n!$

Definition 4: The Group $S_n$ is the set of permutation of the first $n$ natural numbers $\lbrace 1, 2, \dots, n \rbrace$

## 2. Permutation Notations / Order of A Permutation

$f = \left(\begin{smallmatrix} x_1 & x_2 & \cdots & x_n \\ f(x_1) & f(x_2) & \cdots & f(x_n) \end{smallmatrix}\right)$

$\sigma = \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{smallmatrix}\right) \in S_4$

Definition 5: Let $\sigma \in S_n$. The order of $\sigma$, denoted $\operatorname{order}(\sigma) = m$ is the smallest positive integer $m$ such that $\sigma^{m} = I$ where $I$ is the identity permutation.

\begin{aligned} \sigma &= \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix}\right) \newline \sigma \circ \sigma &= \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix}\right) \circ \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix}\right) = \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{smallmatrix}\right) = I \end{aligned}

Definition 6: Let $\sigma \in S_n$. We say that $\sigma$ is a $k$-cycle if there are integers $x_1, x_2, \dots, x_k$ such that $\sigma(x_1) = x_2, \sigma(x_2) = x_3, \dots, \sigma(x_k) = x_1$ and $\sigma$ holds for every other integer (i.e. $\sigma(x_j) = x_j, \forall j > k$)

• 注意这里并没有说 $x_1 = 1$，比如你可以有 $\sigma(2) = 3, \sigma(3) = 4, \sigma(4) = 2$，这也算是一个 $3$-cycle

$\sigma = \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{smallmatrix}\right) \Rightarrow \sigma = (1,2,3,4)$
• 注意这个表达方式不唯一，明显你写成 $\sigma = (x_k, x_1, x_2, \dots, x_{k-1})$ 也是可以的
• 明显，此时我们可以直接得出：$\sigma$ 的 order 是 $k$
• 好比你一路往右 shift，shift 了一圈 ($k$ 次) 又回到了起点

Definition-Lemma 7: $\forall \sigma \in S_n, \sigma$ can be expressed as a product of disjoint cycles. This decomposition is unique, ignoring 1-cycles, up to order. The cycle type of $\sigma$ is the lengths of cycles in the decomposition.

• 注意这里这个 “up to order” 指 “从 order 的角度来看 (是 unique 的)”，这是数学教材里的一个常用的表达式，具体可以参考 How do I understand the meaning of the phrase “up to~” in mathematics?
• 因为 cycle 的写法不唯一，所以这里它这里 “up to order” 的具体含义就是：如果两个 cycle 的 order 是相同的，就认为是 cycle 是相同的，而不算是违反了 unique

$\sigma = \left(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 1 & 5 & 2 \end{smallmatrix}\right) \Rightarrow \sigma = (1,3)(2,4,5) \Rightarrow \text{ cycle type of } \sigma \text{ is } (2,3)$

• 换言之 cycle decomposition 是严格意义上的 function decomposition

Lemma 8: Let $\sigma \in S_n$ be a permutation with cycle type $(k_1, k_2, \dots, k_l)$. The order of $\sigma$ is the least common multiple of $k_1, k_2, \dots, k_l$

## 3. Transpositions

Definition: A transposition is simply a $2$-cycle.

E.g. $\tau = (1)(3)(5)(2,4) \in S_5$ 就是一个 transposition；一般也简写成 $\tau = (2,4)$

permutation 可以被 cycle decomposition；类似地，cycle 也能被 transposition decomposition，进而也可以认为 permutation 能被 transposition decomposition

• 我们可以特别定义 1-cycle $(x_i)$ 等价于两个 transposition $(x_i,x_j)(x_j,x_i)$ where $x_j$ is a random member in $X$ other than $x_i$，为 transposition decomposition 的合法性铺路

### 3.1 Transposition Decomposition and Commutativity

\begin{aligned} (1,2) &= \left(\begin{smallmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{smallmatrix}\right) \\ (1,3) \circ (1,2) &= \left(\begin{smallmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{smallmatrix} \right) \\ \Rightarrow (1,3)(1,2) &= (1,2,3) \end{aligned} \begin{aligned} (1,3) &= \left(\begin{smallmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{smallmatrix}\right) \\ (1,2) \circ (1,3) &= \left(\begin{smallmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{smallmatrix}\right) \\ \Rightarrow (1,2)(1,3) &= (1,3,2) \end{aligned}

### 3.2 How to Decompose a $k$-Cycle into Transpositions: $c_k = \tau_1 \tau_2 \dots \tau_{k-1}$

1. $(x_1, x_2, \dots, x_k) = (x_1, x_2)(x_2, x_3) \dots (x_{k-1}, x_k)$
2. $(x_1, x_2, \dots, x_k) = (x_1, x_k)(x_1, x_{k-1}) \dots (x_1, x_{2})$

\begin{aligned} \left(\begin{matrix} x_1 & x_2 & \dots & x_{k-3} & x_{k-2} & x_{k-1} & x_{k} \end{matrix}\right) & \Leftarrow \text{ original X} \\ \left(\begin{matrix} x_1 & x_2 & \dots & x_{k-3} & x_{k-2} & x_{k} & x_{k-1} \end{matrix}\right) & \Leftarrow (x_{k-1}, x_k) \text{ applied} \\ \left(\begin{matrix} x_1 & x_2 & \dots & x_{k-3} & x_{k-1} & x_{k} & x_{k-2} \end{matrix}\right) & \Leftarrow (x_{k-2}, x_{k-1}) \text{ applied} \\ \left(\begin{matrix} x_1 & x_2 & \dots & x_{k-2} & x_{k-1} & x_{k} & x_{k-3} \end{matrix}\right) & \Leftarrow (x_{k-3}, x_{k-2}) \text{ applied} \\ \dots & \\ \left(\begin{matrix} x_1 & x_3 & \dots & x_{k-2} & x_{k-1} & x_{k} & x_{2} \end{matrix}\right) & \Leftarrow (x_{2}, x_{3}) \text{ applied} \\ \left(\begin{matrix} x_2 & x_3 & \dots & x_{k-2} & x_{k-1} & x_{k} & x_{1} \end{matrix}\right) & \Leftarrow (x_{1}, x_{2}) \text{ applied} \end{aligned}

\begin{aligned} \left(\begin{matrix} x_1 & x_2 & x_3 & x_4 & \dots & x_{k-1} & x_{k} \end{matrix}\right) & \Leftarrow \text{ original X} \\ \left(\begin{matrix} x_2 & x_1 & x_3 & x_4 & \dots & x_{k-1} & x_{k} \end{matrix}\right) & \Leftarrow (x_1, x_2) \text{ applied} \\ \left(\begin{matrix} x_2 & x_3 & x_1 & x_4 & \dots & x_{k-1} & x_{k} \end{matrix}\right) & \Leftarrow (x_1, x_3) \text{ applied} \\ \left(\begin{matrix} x_2 & x_3 & x_4 & x_1 & \dots & x_{k-1} & x_{k} \end{matrix}\right) & \Leftarrow (x_1, x_4) \text{ applied} \\ \dots & \\ \left(\begin{matrix} x_2 & x_3 & x_4 & x_5 & \dots & x_1 & x_{k} \end{matrix}\right) & \Leftarrow (x_1, x_{k-1}) \text{ applied} \\ \left(\begin{matrix} x_2 & x_3 & x_4 & x_5 & \dots & x_{k} & x_1 \end{matrix}\right) & \Leftarrow (x_1, x_{k}) \text{ applied} \\ \end{aligned}

### 3.3 How to Compose a Permutation with A Transposition: $\sigma \tau = ?, \tau \sigma = ?$

(1) 假设 $a, b$ 处在 $\sigma$ 的一个 cycle 内，假设这个 cycle 是 $\gamma = (a, x_1, x_2, \dots, x_r, b, y_1, y_2, \dots, y_s)$。为了演示方便，我们不妨假设有一个 $X = \lbrace 1, 2, \dots, n \rbrace$ 的子集刚好就是 $X’ = \lbrace a, x_1, x_2, \dots, x_r, b, y_1, y_2, \dots, y_s \rbrace$，那么 $\gamma$ 可以简写成：

$\gamma = \left(\begin{smallmatrix} a & x_1 & x_2 & \dots & x_r & b & y_1 & y_2 & \dots & y_s \\ x_1 & x_2 & \dots & x_r & b & y_1 & y_2 & \dots & y_s & a \end{smallmatrix}\right)$

$\tau \gamma = \left(\begin{smallmatrix} \vert & a & x_1 & x_2 & \dots & x_r & \vert & b & y_1 & y_2 & \dots & y_s & \vert \\ \vert & x_1 & x_2 & \dots & x_r & a & \vert & y_1 & y_2 & \dots & y_s & b & \vert \end{smallmatrix}\right)$

$\gamma \tau = \left(\begin{smallmatrix} a & x_1 & x_2 & \dots & x_r & b & y_1 & y_2 & \dots & y_s \\ x_1 & x_2 & \dots & x_r & b & y_1 & y_2 & \dots & y_s & a \end{smallmatrix}\right) \circ \left(\begin{smallmatrix} a & x_1 & x_2 & \dots & x_r & b & y_1 & y_2 & \dots & y_s \\ b & x_1 & x_2 & \dots & x_r & a & y_1 & y_2 & \dots & y_s \end{smallmatrix}\right) = \left(\begin{smallmatrix} a & \vert & x_1 & x_2 & \dots & x_r & b & \vert & y_1 & y_2 & \dots & y_s \\ y_1 & \vert & x_2 & \dots & x_r & b & x_1 & \vert & y_2 & \dots & y_s & a \end{smallmatrix}\right)$

(2) 假设 $a, b$ 处在 $\sigma$ 的两个 cycle 内，假设这两个 cycles 分别为 $\gamma_1 = (a, x_1, x_2, \dots, x_r), \gamma_2 = (b, y_1, y_2, \dots, y_s)$

$\tau (\gamma_1 \gamma_2) = \left(\begin{smallmatrix} a & x_1 & x_2 & \dots & x_r & b & y_1 & y_2 & \dots & y_s \\ b & x_1 & x_2 & \dots & x_r & a & y_1 & y_2 & \dots & y_s \end{smallmatrix}\right) \circ \left(\begin{smallmatrix} a & x_1 & x_2 & \dots & x_r & \vert & b & y_1 & y_2 & \dots & y_s \\ x_1 & x_2 & \dots & x_r & a & \vert & y_1 & y_2 & \dots & y_s & b \end{smallmatrix}\right) = \left(\begin{smallmatrix} a & x_1 & x_2 & \dots & x_r & b & y_1 & y_2 & \dots & y_s \\ x_1 & x_2 & \dots & x_r & b & y_1 & y_2 & \dots & y_s & a \end{smallmatrix}\right)$ \begin{aligned} (\gamma_1 \gamma_2) \tau &= \left(\begin{smallmatrix} a & x_1 & x_2 & \dots & x_r & \vert & b & y_1 & y_2 & \dots & y_s \\ x_1 & x_2 & \dots & x_r & a & \vert & y_1 & y_2 & \dots & y_s & b \end{smallmatrix}\right) \circ \left(\begin{smallmatrix} a & x_1 & x_2 & \dots & x_r & b & y_1 & y_2 & \dots & y_s \\ b & x_1 & x_2 & \dots & x_r & a & y_1 & y_2 & \dots & y_s \end{smallmatrix}\right) = \left(\begin{smallmatrix} a & x_1 & x_2 & \dots & x_r & b & y_1 & y_2 & \dots & y_s \\ y_1 & x_2 & \dots & x_r & a & x_1 & y_2 & \dots & y_s & b \end{smallmatrix}\right) \\ & \overset{\text{重排列一下}}{=} \left(\begin{smallmatrix} b & x_1 & x_2 & \dots & x_r & a & y_1 & y_2 & \dots & y_s \\ x_1 & x_2 & \dots & x_r & a & y_1 & y_2 & \dots & y_s & b \end{smallmatrix}\right) \end{aligned}

### 3.4 Inversions / Parity / Sign of A Permutation

Definition: Let $\sigma \in S(X)$ be a permutation. An inversion of $\sigma$ is an pair $(i, j) \in X^2$ such that $i < j$ while $\sigma(i) > \sigma(j)$

• 按照这个定义，任意一个 transposition 都算是一个 inversion

Definition: Permutaion $\sigma$ is odd when its number of inversions, $\operatorname{inv}(\sigma)$, is odd; otherwise even

Definition: The sign of permutation $\sigma$ is the parity of its number of inversions, i.e $\operatorname{sgn}(\sigma) = (-1)^{\operatorname{inv}(\sigma)}$

Lemma: $\operatorname{inv}(\sigma) = \operatorname{inv}(\sigma^{-1}), \operatorname{sgn}(\sigma) = \operatorname{sgn}(\sigma^{-1})$

Lemma: $\operatorname{inv}(\sigma \tau) \equiv \operatorname{inv}(\sigma) + \operatorname{inv}(\tau) \, (mod \, 2)$

• $a \equiv b \, (mod \, p)$ 表示 (a - b) % p == 0

Lemma: $\operatorname{sgn}(\sigma \tau) = \operatorname{sgn}(\sigma) \times \operatorname{sgn}(\tau)$

Lemma: Suppose there are $N_c$ disjoint cycles, including 1-cycles, in permutation $\sigma \in S_n$, then $\operatorname{sgn}(\sigma) = (-1)^{n - N_c}$

Proof: 根据 transposition decomposition，任意一个 $k$-cycle ($k \geq 2$) 都可以分解成 $k-1$ 个 decompositions，相当于贡献了 $k-1$ 个 inversions