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

参考文献：

• 5. Permutation Groups
• The Order of a Permutation
• Class 17: More Permutations
• The Sign of a Permutation by Matt Baker

1. Permutation GroupsPermalink

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: $\mathrm{\forall }f,g\in S(X),f\circ g\in S(X)$
2. Associativity: $\mathrm{\forall }f,g,h\in S(X),(f\circ g)\circ h=f\circ (g\circ h)$
3. Identity element: $\mathrm{\exists }I\in S(X)$ such that $I(X)=X$
4. Inverse element: $\mathrm{\forall }f\in S(X),\mathrm{\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 $|X|=n$, then $|S(X)|=n!$

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

2. Permutation Notations / Order of A PermutationPermalink

第一种写法是把 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 $\mathrm{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,\mathrm{\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: $\mathrm{\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

举例：

注意这里应该这么看：$k$-cycle 本身也是 permutation，所以上面其实是说：任意一个 permutation 都能看做是几个 disjoint 的 $k$-cycle-styled 的 permutation 的 composition, i.e. $\sigma =c_{k_1}\circ c_{k_2}\circ \cdots \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. TranspositionsPermalink

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 CommutativityPermalink

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

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

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

3.2 How to Decompose a $k$-Cycle into Transpositions: $c_k={\tau }_1{\tau }_2\dots {\tau }_{k-1}$Permalink

一个 $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 =?$Permalink

考虑这么一个问题：假设有一个 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=\{1,2,\dots ,n\}$ 的子集刚好就是 $X^{\prime }=\{a,x_1,x_2,\dots ,x_r,b,y_1,y_2,\dots ,y_s\}$，那么 $\gamma$ 可以简写成：

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

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

同理，$\gamma \tau$ 相当于先把 $X^{\prime }$ 里的 $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 PermutationPermalink

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, $\mathrm{inv}(\sigma )$, is odd; otherwise even

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

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

Lemma: $\mathrm{inv}(\sigma \tau )\equiv \mathrm{inv}(\sigma )+\mathrm{inv}(\tau )(mod2)$

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

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

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

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

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

于是 $\mathrm{inv}(\sigma )=\sum _{i=1}^{N_c}{k}_i-1=n-N_c.◼$