Disjoint cycle decomposition

用如式子 (3.1) 的方法表示 S_n 的元素有時稍嫌麻煩. 我們介紹一個簡便的表示法. 這個方法稱為 cycle 表示法. 它不只使用簡便, 而且許多 S_n 的性質都可利用這方法簡單求得. 可以說是相當的重要.

Definition 3.4.3   令 i₁, i₂..., i_k 是在 {1, 2,..., n} 中 k 個相異整數. 我們用

(i₁  i₂   ^...   i_k)

表示 S_n 中的一個元素 $\sigma$ 將 s $\in$ {1, 2,..., n} 送到

$$\sigma$$(s) = $$\left\{\vphantom{ \begin{array}{ll} i_{j+1}, & \hbox{若 $s=i_j$ ... ...} \\ s, & \hbox{若 $s\not\in\{i_1,\dots,i_k\}$.} \\ \end{array}%% }\right.$$$$\begin{array}{ll} i_{j+1}, & \hbox{若 $s=i_j$ 且 $1\le j\le k-1$... ...若 $s=i_k$;} \\ s, & \hbox{若 $s\not\in\{i_1,\dots,i_k\}$.} \\ \end{array}$$

換句話說 $\sigma$ 將 i₁ $\mapsto$ i₂, i₂ $\mapsto$ i₃, ..., i_{k - 1} $\mapsto$ i_k, 而將 i_k 送回 i₁, 而將 i₁,..., i_k 以外的元素原封不動.

我們稱 (i₁  i₂   ^...   i_k) 是一個 k-cycle.

例如在 S₅ 中我們有以下的等式:

(1  2  3) = $$\left(\vphantom{ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 4 & 5 \\ \end{array}%% }\right.$$$$\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 4 & 5 \\ \end{array}$$$$\left.\vphantom{ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 4 & 5 \\ \end{array}%% }\right)$$

一個 cycle 是 S_n 中的元素, 反之任一 S_n 中的元素未必是一個 cycle. 不過它們都可寫成一些 cycle 的乘積 (別忘了這裡指的是合成). 我們就用式子 (3.1) 當例子來將 $\sigma$ 用 cycle 表示出來. 因 $\sigma$ 將 1 $\mapsto$ 2 所以我們先寫下

(1  2

接著 $\sigma$ 將 2 $\mapsto$ 3 所以繼續寫下

(1  2  3

然後 $\sigma$ 將 3 $\mapsto$ 1 所以我們寫下

(1  2  3)

用 ``)'' 將 3 框住表示 $\sigma$ 將 3 送回 1. 這樣我們寫下了一個 3-cycle. 不過這 (1  2  3) 並不是 $\sigma$, 別忘了 $\sigma$ 還將 4 $\mapsto$ 5 及 5 $\mapsto$ 4. 所以需補上 (4  5) 這一個 cycle. 因此我們將式子 (3.1) 表成

$$\sigma$$ = (4  5)(1  2  3).

這裡其實我們是將 (1  2  3) 看成是 S₅ 中的

$$\left(\vphantom{ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 4 & 5 \\ \end{array}%% }\right.$$$$\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 4 & 5 \\ \end{array}$$$$\left.\vphantom{ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 4 & 5 \\ \end{array}%% }\right)$$

這一個元素, 而

(4  5) = $$\left(\vphantom{ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 5 & 4 \\ \end{array}%% }\right.$$$$\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 5 & 4 \\ \end{array}$$$$\left.\vphantom{ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 5 & 4 \\ \end{array}%% }\right)$$

所以將之相乘得 $\sigma$. 同法式子 (3.2) 中的 $\tau$ 將 1 $\mapsto$ 3, 故先寫下

(1  3

接著 $\tau$ 將 3 $\mapsto$ 5 所以繼續寫下

(1  3  5

而後 $\tau$ 將 5 $\mapsto$ 2, 故寫

(1  3  5  2

接著 $\tau$ 將 2 $\mapsto$ 4, 所以寫下

(1  3  5  2  4

最後 $\tau$ 將 4 送回 1 故補上 ``)'' 得

$$\tau$$ = (1  3  5  2  4).

注意此時每一個元素的動作都用這一個 cycle 表示出來了, 所以 $\tau$ 是一個 5-cycle.

接下來我們看

$$\sigma$$ ^. $$\tau$$ = (4  5)(1  2  3)(1  3  5  2  4)

會是甚麼? 當然了你可以將這些 cycles 還原成原來複雜的形式再計算, 不過這裡我們想直接用 cycle 的看法來處理. 首先觀察 (1  3  5  2  4) 將 1 $\mapsto$ 3, 不過後面的 (1  2  3) 將 3 $\mapsto$ 1, 最後 (4  5) 固定 1 所以知 $\sigma$ ^. $\tau$ 將 1 $\mapsto$ 1. 也就是說在 $\sigma$ ^. $\tau$ 的 cycle 寫法中 1 不會出現. 現在看 2: (1  3  5  2  4) 將 2 $\mapsto$ 4, 而後面的 (1  2  3) 將 4 固定住, 最後 (4  5) 將 4 $\mapsto$ 5 故知 $\sigma$ ^. $\tau$ 將 2 $\mapsto$ 5, 所以我們寫下

(2  5

然而 (1  3  5  2  4) 將 5 $\mapsto$ 2, 而後面的 (1  2  3) 將 2 $\mapsto$ 3, 最後 (4  5) 固定 3, 所以得 $\sigma$ ^. $\tau$ 將 5 $\mapsto$ 3, 我們記下

(2  5  3

然而 (1  3  5  2  4) 將 3 $\mapsto$ 5, 且 (1  2  3) 將 5 固定住, 最後 (4  5) 將 5 $\mapsto$ 4 故知 $\sigma$ ^. $\tau$ 將 3 $\mapsto$ 4, 所以繼續寫下

(2  5  3  4

最後 (1  3  5  2  4) 將 4 $\mapsto$ 1, 而後面的 (1  2  3) 將 1 $\mapsto$ 2, 然後 (4  5) 固定 2, 所以得 $\sigma$ ^. $\tau$ 將 4 送回了 2, 我們得知

$$\sigma$$ ^. $$\tau$$ = (2  5  3  4).

兩個 cycles (i₁   ^...   i_k) 和 (j₁   ^...   j_l) 如果其中 {i₁,..., i_k} $\cap$ {j₁,..., j_l} = $\emptyset$ 則稱此兩 cycle 為 disjoint cycles. 如果將 S_n 中的元素寫成一些兩兩 disjoint 的 cycles 的乘積 (當然包括只有一個 cycle 的情況), 我們就稱之為 disjoint cycle decomposition. 如前面 (4  5)(1  2  3) 和 (1  3  5  2  4) 就分別是 $\sigma$ 和 $\tau$ 的 disjoint cycle decomposition.

我們簡單的說明一下對任意的 $\sigma$ $\in$ S_n, 其 disjoint cycle decomposition 是存在的. 作法就如同前面的例子, 任取一數 a₁ $\in$ {1,..., n} 我們先考慮 $\sigma$ 將 a₁ 送到何處? 若 $\sigma$(a₁) = a₁, 則知 a₁ 不會出現在 cycle decomposition 之中, 所以我們繼續考慮其他的數. 如果 $\sigma$(a₁) = a₂$\ne$a₁ 則寫下

(a₁  a₂

接下來看 $\sigma$(a₂) 為何? ... 如此繼續下去直到第一個 a_k 使得 $\sigma$(a_k) 會和前面的某數相同. 也就是說 a₁,..., a_k 都相異但 $\sigma$(a_k) $\in$ {a₁,..., a_{k - 1}}. 不過此時 $\sigma$(a_k) 非得等於 a₁ 不可, 因為若 $\sigma$(a_k) = a_i, 其中 i > 1, 則已知 $\sigma$(a_{i - 1}) = a_i, 由 $\sigma$ 是 1-1 知 a_k = a_{i - 1} 這和 a₁,..., a_k 兩兩相異矛盾, 所以得 $\sigma$(a_k) = a₁. 也就是說我們得到一個 cycle:

(a₁   ^...   a_k).

接下來我們考慮 {a₁,..., a_k} 以外的數 b₁, 再利用同樣的方式得到一個 cycle. 如此繼續下去直到將所有 {1,..., n} 考慮完畢, 然後得 $\sigma$ 就是這些 cycles 的乘積. 當然了利用 $\sigma$ 是 1-1 我們很容易看出這樣做出的 cycles 都是 disjoint.

接下來我們要說 disjoint cycle decomposition 是唯一的. 不過這裡的唯一性要說明一下. 首先觀察 (1  2  3) 這一個 cycle 其實它和 (2  3  1) 及 (3  1  2) 都表示同一個函數: 即 1 $\mapsto$ 2, 2 $\mapsto$ 3, 3 $\mapsto$ 1. 因此我們將之視為同一 cycle (不過要注意 (1  3  2) 是不同的 cycle). 另外 (1  2  3)(4  5) 和 (4  5)(1  2  3) 也是同一個函數所以我們也將之視為同樣的 decomposition.

Lemma 3.4.4   令 $\sigma$ = (a₁  a₂  ^...  a_k) 和 $\tau$ = (b₁  b₂  ^...  b_l) 是 S_n 的兩個 cycles.

1. 如果 k = l 且 a₁ = b₂, a₂ = b₃, ..., a_{k - 1} = b_k, a_k = b₁, 則 $\sigma$ = $\tau$.
2. 如果 $\sigma$ 和 $\tau$ 是 disjoint, 即 {a₁,..., a_k} $\cap$ {b₁,..., b_l} = $\emptyset$, 則 $\sigma$ ^. $\tau$ = $\tau$ ^. $\sigma$.

証 明. 我們曾經強調過, 要說明兩個 S_n 中的元素是相同的只要將之視為函數, 將 {1,..., n} 中任意數代入都相等就可.

(1) 若 x $\in$ {1,..., n} 但 x $\not\in${a₁,..., a_k}, 則知 $\sigma$(x) = x, 但由假設知

{a₁,..., a_k} = {b₁,..., b_l},

所以 x $\not\in${b₁,..., b_l}, 也就是說 $\tau$(x) = x.

若 x $\in$ {a₁,..., a_k}, 假設 x = a_i, 1$\le$i$\le$k - 2, 則

$$\sigma$$(x) = $$\sigma$$(a_i) = a_{i + 1} = b_{i + 2}.

此時因 a_i = b_{i + 1}, 所以

$$\tau$$(x) = $$\tau$$(b_{i + 1}) = b_{i + 2}.

而當 x = a_{k - 1} 時,

$$\sigma$$(x) = $$\sigma$$(a_{k - 1}) = a_k = b₁.

此時因 a_{k - 1} = b_k, 故

$$\tau$$(x) = $$\tau$$(b_k) = b₁.

最後當 x = a_k 時,

$$\sigma$$(x) = $$\sigma$$(a_k) = a₁ = b₂.

此時因 a_k = b₁ 所以

$$\tau$$(x) = $$\tau$$(b₁) = b₂.

得證對所有的 x $\in$ {1,..., n} 皆有 $\sigma$(x) = $\tau$(x), 因此知 $\sigma$ = $\tau$.

(2) 此時由假設 $\sigma$ 和 $\tau$ 是 disjoint, 所以 x $\in$ {1,..., n} 可分成三種情況: (a) x $\not\in${a₁,..., a_k} $\cup$ {b₁,..., b_l}; (b) x $\in$ {a₁,..., a_k}; (c) x $\in$ {b₁,..., b_l}.

當 x 是屬狀況 (a) 時, 得 $\sigma$(x) = $\tau$(x) = x 故

($$\sigma$$ ^. $$\tau$$)(x) = $$\sigma$$($$\tau$$(x)) = $$\sigma$$(x) = x,

同理知 ($\tau$ ^. $\sigma$)(x) = x.

當 x 是屬狀況 (b) 時, 得 $\sigma$(x) $\in$ {a₁,..., a_k} 但由 disjoint 知 x 和 $\sigma$(x) 皆不屬於 {b₁,..., b_l} 故 $\tau$(x) = x 且 $\tau$($\sigma$(x)) = $\sigma$(x). 所以知

($$\sigma$$ ^. $$\tau$$)(x) = $$\sigma$$($$\tau$$(x)) = $$\sigma$$(x)

且

($$\tau$$ ^. $$\sigma$$)(x) = $$\tau$$($$\sigma$$(x)) = $$\sigma$$(x).

最後若 x 是屬狀況 (c) 時, 同狀況 (b) 可知

($$\sigma$$ ^. $$\tau$$)(x) = $$\tau$$(x) = ($$\tau$$ ^. $$\sigma$$)(x).

故得 $\sigma$ ^. $\tau$ = $\tau$ ^. $\sigma$. $\qedsymbol$

Remark 3.4.5   在 Lemma 中我們證得

(a₁  a₂  ^...  a_{k - 1}  a_k)

和

(a_k  a₁  ^...  a_{k - 2}  a_{k - 1})

為同一 cycle. 對 (a_k  a₁  ^...  a_{k - 2}  a_{k - 1}) 再套用一次 Lemma 可得

(a_{k - 1}  a_k  ^...  a_{k - 3}  a_{k - 2})

也是同一 cycle. 如此一直循環下去我們可得到同一個 k-cycle 有 k 種寫法.

另外我們要強調的是若 $\sigma$ 和 $\tau$ 不是 disjoint 時, 則 $\sigma$ ^. $\tau$ 並不一定等於 $\tau$ ^. $\sigma$ (前面已給過例子了).

現在我們可以說如果將 Lemma 3.4.4 的這兩種狀況忽略 (即不管一個 cycle 的循環或兩個 disjoint cycle 的順序), 那麼任一個 S_n 的元素寫成 disjoint cycle decomposition 的寫法唯一. 假設 $\sigma$ $\in$ S_n 有兩種 disjoint cycle decompositions: $\sigma$ = $\sigma_{1}^{}$ ^... $\sigma_{r}^{}$ 和 $\sigma$ = $\tau_{1}^{}$ ^... $\tau_{s}^{}$, 其中 $\sigma_{1}^{}$,...,$\sigma_{r}^{}$ 和 $\tau_{1}^{}$,...,$\tau_{s}^{}$ 分別是兩組 disjoint cycles. 假設 a₁ $\in$ {1,..., n} 在 $\sigma_{1}^{}$ 這個 cycle 出現, 而 $\sigma_{1}^{}$(a₁) = a₂, 則我們有

$$\sigma_{1}^{}$$ = (a₁  a₂  ^...

然而 $\sigma_{1}^{}$,...,$\sigma_{r}^{}$ 是 disjoint 所以 a₁, a₂ 不會在 $\sigma_{2}^{}$,...,$\sigma_{r}^{}$ 中出現; 也就是說當 i 符合 2$\le$i$\le$r 時 $\sigma_{i}^{}$(a₁) = a₁ 因此由 $\sigma$ = $\sigma_{1}^{}$ ^... $\sigma_{r}^{}$ 知

$$\sigma \sigma_{1}^{} \sigma_{r}^{} \sigma_{1}^{}$$ (3.5)

不過由於 $\sigma$ = $\tau_{1}^{}$ ^... $\tau_{s}^{}$, a₁ 一定會在某一個 $\tau_{i}^{}$ 中出現, 否則如果 a₁ 在所有的 $\tau_{i}^{}$ 都沒出現則知 $\tau_{i}^{}$(a₁) = a₁, 然而若真如此, 則得

$$\sigma$$(a₁) = $$\tau_{1}^{}$$ ^... $$\tau_{s}^{}$$(a₁) = a₁.

此和上式 (3.5) 相矛盾. 其實由於 $\tau_{1}^{}$,...,$\tau_{s}^{}$ 是 disjoint, a₁ 只會出現在唯一的 $\tau_{i}^{}$ 中. 我們不妨假設 a₁ 出現在 $\tau_{1}^{}$ 中 (別忘了 $\tau_{1}^{}$,...,$\tau_{s}^{}$ 是 disjoint 所以它們可以兩兩交換). 因為 a₁ 不會在其他的 $\tau_{i}^{}$ 出現, 當 i 符合 2$\le$i$\le$s 時, 我們有 $\tau_{i}^{}$(a₁) = a₁. 因此知

$$\sigma \tau_{1}^{} \tau_{s}^{} \tau_{1}^{}$$ (3.6)

結合 (3.5) 和 (3.6) 兩式, 我們得 $\tau_{1}^{}$(a₁) = a₂. 也就是說

$$\tau_{1}^{}$$ = (a₁  a₂  ^...

對 a₂ 用同樣的論述可得 $\sigma_{1}^{}$(a₂) = $\tau_{1}^{}$(a₂), 如此一直下去我們可得 $\sigma_{1}^{}$ = $\tau_{1}^{}$. 因此用歸納法可知 r = s 且 對所有的 i 皆有 $\sigma_{i}^{}$ = $\tau_{i}^{}$. 我們證得了 S_n 中所有的元素皆存在唯一的 disjoint cycle decomposition.