# 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

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.

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 = (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

• cycle type of $\sigma$ 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.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})$

### 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$ 可以简写成：

(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)$

### 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