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

Yao Yao on April 27, 2020

参考文献:

Table of Contents:

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

第一种写法是把 permutation $f$ 的 domain $X$ 列在第一行,把 image $f(X)$ 列在第二行,形如:

以下我们为了方便我们主要研究 $S_n$。第一种写法的举例:

这种写法的问题在于:看不出 $\sigma$ 的 order。那具体啥是 permutation 的 order?

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.

举例:

为此我们需要一种 “表达能力” 更强的 notation,于是我们有了下文的 cycle notation.

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

由此我们可以有第二种写法:如果 permutation $\sigma$ 是一个 $k$-cycle,我们可以写成 $\sigma = (x_1, x_2, \dots, x_k)$。举例:

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

但并不是每个 permutation 都能写成一个完整的 $k$-cycle,所以我们我们扩展一下第二种写法,称为 cycle decomposition of permutation:

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

注意这里应该这么看:$k$-cycle 本身也是 permutation,所以上面其实是说:任意一个 permutation 都能看做是几个 disjoint 的 $k$-cycle-styled 的 permutation 的 composition, i.e. $\sigma = c_{k_1} \circ c_{k_2} \circ \dots \circ c_{k_l}$

  • 换言之 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

但在讲 transposition decomposition 之前,我要强调一下 Commutativity 的问题。

前面有讲,$S_n$ 或者 $S(X)$ 作为一个 group 是不保证 Commutativity 的。但要注意,在 cycle decomposition 的定义里,我们有一个很关键的修饰语——disjoint。可以证明,disjoint 的 $k$-cycles 是满足 Commutativity 的

但在 transposition decomposition 的时候,我们并没有强调 disjoint,实际情况也不可能要求它 disjoint,所以一般情况下 transposition 是没有 Commutativity 的。举例:对 $X = \lbrace 1,2,3 \rbrace$ 而言:

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

一个 $k$-cycle $(x_1, x_2, \dots, x_k)$ 可以有两种 decomposition:

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

注意根据 function composition 的定义,是右边的 transposition 先执行

第一种分解方式:

第二种分解方式:

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

考虑这么一个问题:假设有一个 permutation $\sigma \in S_n$ 有 $n_c$ 个 disjoint cycles,现在有一个 transposition $\tau = (a, b) \in S_n$,问 $\tau \sigma$ 和 $\sigma \tau$ 会有多少个 disjoint cycles?

这个问题要分两种情况考虑:

(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$ 可以简写成:

那么 $\tau \gamma$ 就相当于把 $\gamma$ permuate 后的结果里的 $a, b$ 再 swap 一次,于是有:

相当于把 $\gamma$ 切成了两个新的 disjoint cyles

同理,$\gamma \tau$ 相当于先把 $X’$ 里的 $a, b$ swap 之后,再按 $\gamma$ permutate,于是有:

同样也是相当于把 $\gamma$ 切成了两个新的 disjoint cyles

因为 $\tau$ 不会影响其他的 cycle,所以 $\tau \sigma$ 和 $\sigma \tau$ 在这中情况下会有 $n_c + 1$ 个 disjoint cycles

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

类似地,有:

相当于把 $\gamma_1$ 和 $\gamma_2$ 合并成了一个新的大 cyle

因为 $\tau$ 不会影响其他的 cycle,所以 $\tau \sigma$ 和 $\sigma \tau$ 在这中情况下会有 $n_c - 1$ 个 disjoint cycles

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

特别地,我们认为 1-cycle 贡献了 0 个 inversion

于是 $\operatorname{inv}(\sigma) = \sum_{i=1}^{N_c} k_i - 1 = n - N_c. \blacksquare$



blog comments powered by Disqus