Disjoint cycle 的性質

其中一個好處就是很容易求出 inverse. 首先來看單一一個 cycle 的情況.

証明. 令 $\tau$ = (a_k a_{k - 1} ^... a₂ a₁) 我們直接證明 $\tau$ ^. $\sigma$ 是 identity. 也就是要證對所有 x $\in$ {1,..., n}, ( $\tau$ ^. $\sigma$ )(x) = x.

如果 x $\not\in$ {a₁,..., a_k} 則自然 $\sigma$ (x) = $\tau$ (x) = x, 所以此時

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

反之, 如果 x $\in$ {a₁,..., a_k}, 則當 x = a_i, 其中 1 $\le$ i $\le$ k - 1 時, 因 $\sigma$ (x) = $\sigma$ (a_i) = a_{i + 1} 且 2 $\le$ i + 1 $\le$ k, 故

( $\displaystyle \tau$ ^. $\displaystyle \sigma$ )(x) = $\displaystyle \tau$ ( $\displaystyle \sigma$ (a_i)) = $\displaystyle \tau$ (a_{i + 1}) = a_i = x.

而當 x = a_k 時

( $\displaystyle \tau$ ^. $\displaystyle \sigma$ )(x) = $\displaystyle \tau$ ( $\displaystyle \sigma$ (a_k)) = $\displaystyle \tau$ (a₁) = a_k = x.

故得 $\tau$ ^. $\sigma$ 是 S_n 的 identity, 也就是說 $\tau$ = $\sigma^{-1}_{}$ . $\qedsymbol$

若 $\sigma$ = $\sigma_{1}^{}$ ^... $\sigma_{r}^{}$ 是 $\sigma$ 的 disjoint cycle decomposition. 則我們可以利用 Lemma 3.4.6 將每一個 $\sigma_{i}^{}$ 的 inverse 求出. Lemma 3.4.6 也告訴我們這些 $\sigma_{1}^{-1}$ ,..., $\sigma_{r}^{-1}$ 是 disjoint cycles. 所以可以很容易的就將 $\sigma^{-1}_{}$ 的 disjoint cycle decomposition 寫出. 例如若 $\sigma$ = (1 2 3)(4 5), 我們馬上得 $\sigma^{-1}_{}$ = (3 2 1)(5 4).

寫成 disjoint cycle 的另一個好處是能夠很快的求出 S_n 中元素的 order. 我們還是先來看單一一個 cycle 的情況.

証明. 若 $\sigma$ = (a₁ a₂ ^... a_{k - 1} a_k), 我們要證當 1 $\le$ i $\le$ k - 1 時, $\sigma^{i}_{}$ 不是 S_n 中的 identity, 而 $\sigma^{k}_{}$ 是 S_n 的 identity.

當 1 $\le$ i $\le$ k - 1 時, $\sigma^{i}_{}$ (a₁) = a_{i + 1}. 由於 2 $\le$ i + 1 $\le$ k, 我們知 a_{i + 1} $\ne$ a₁, 也就是說 $\sigma^{i}_{}$ (a₁) $\ne$ a₁. 所以 $\sigma^{i}_{}$ 不可能是 identity.

另外,若 x $\not\in$ {a₁,..., a_k} 時, 當然有 $\sigma^{k}_{}$ (x) = x. 而由定義知對所有的 x $\in$ {a₁,...a_k} 皆有 $\sigma^{k}_{}$ (x) = x. 所以得 $\sigma^{k}_{}$ 是 identity. $\qedsymbol$

我們已知ㄧ個 cycle 的 order 為何, 但要求一些 disjoint cycles 的乘積的 order 我們需要以下這個一般 group 的性質:

証明. 回顧一下, ord(a) = n 等價於下面兩條件: (1) aⁿ = e; (2) 如果 a^r = e 則 n | r.

若令 ord(a) = n 且 ord(b) = m, 而 l = lcm[n, m], 則由 a^.b = b^.a 知 (a^.b)^l = a^{l .}b^l = e. 此證明了 l 符合 ord(a^.b) 的條件 (1).

現若 (a^.b)^r = e, 知 a^{r .}b^r = e, 也就是 a^r = b^-r. 然而 a^r $\in$ $\langle$ a $\rangle$ 且 b^-r $\in$ $\langle$ b $\rangle$ , 故知 a^r $\in$ $\langle$ a $\rangle$ $\cap$ $\langle$ b $\rangle$ . 利用假設 $\langle$ a $\rangle$ $\cap$ $\langle$ b $\rangle$ = {e}, 得 a^r = e 且 b^-r = (b^r)^-1 = e (也就是 b^r = e). 因 ord(a) = n, ord(b) = m, 利用條件 (2) 知 n | r 且 m | r. 也就是 r 是 n, m 的公倍數. 再利用最小公倍數的性質知 l = lcm[n, m] | r. 此證明了 l 符合 ord(a^.b) 的條件 (2). 所以 ord(a^.b) = l = lcm[ord(a),ord(b)]. $\qedsymbol$

証明. 我們首先證 ord( $\sigma_{1}^{}$ ^. $\sigma_{2}^{}$ ) = lcm[n₁, n₂]. 因 $\sigma_{1}^{}$ 和 $\sigma_{2}^{}$ 是 disjoint, 所以 $\sigma_{1}^{}$ ^. $\sigma_{2}^{}$ = $\sigma_{2}^{}$ ^. $\sigma_{1}^{}$ . 因此只要我們證得 $\langle$ $\sigma_{1}^{}$ $\rangle$ $\cap$ $\langle$ $\sigma_{2}^{}$ $\rangle$ = {e}, 則由 Lemma 3.4.7 和 Lemma 3.4.8 知 ord( $\sigma_{1}^{}$ ^. $\sigma_{2}^{}$ ) = lcm[n₁, n₂]. 現若 $\tau$ $\in$ $\langle$ $\sigma_{1}^{}$ $\rangle$ $\cap$ $\langle$ $\sigma_{2}^{}$ $\rangle$ , 則存在 i 和 j 使得 $\tau$ = $\sigma_{1}^{i}$ = $\sigma_{2}^{j}$ . 若 $\tau$ 不是 S_n 的 identity, 即存在 a $\in$ {1,..., n} 使得 $\tau$ (a) $\ne$ a. 也就是說 $\sigma_{1}^{i}$ (a) $\ne$ a. 這當然就保證 a 必須出現在 $\sigma_{1}^{}$ 的 cycle 中 (否則 $\sigma_{1}^{}$ (a) = a 會得到 $\sigma_{1}^{i}$ (a) = a). 然而 $\sigma_{2}^{}$ 和 $\sigma_{1}^{}$ 是 disjoint, 故 a 必不會出現在 $\sigma_{2}^{}$ 的 cycle 中. 也就是說 $\sigma_{2}^{}$ (a) = a. 這會造成 $\sigma_{2}^{j}$ (a) = a, 與當初假設 $\sigma_{2}^{j}$ (a) = $\tau$ (a) $\ne$ a 相矛盾. 因此 $\tau$ 非得是 S_n 的 identity 不可. 因此得證 $\langle$ $\sigma_{1}^{}$ $\rangle$ $\cap$ $\langle$ $\sigma_{2}^{}$ $\rangle$ = {e}, 同時得 ord( $\sigma_{1}^{}$ ^. $\sigma_{2}^{}$ ) = lcm[n₁, n₂].

接下來我們可以用數學歸納法. 因 $\sigma_{1}^{}$ ,... $\sigma_{r-1}^{}$ , $\sigma_{r}^{}$ 是 disjoint, 故有

( $\displaystyle \sigma_{1}^{}$ ^... $\displaystyle \sigma_{r-1}^{}$ )^. $\displaystyle \sigma_{r}^{}$ = $\displaystyle \sigma_{r}^{}$ ^.( $\displaystyle \sigma_{1}^{}$ ^... $\displaystyle \sigma_{r-1}^{}$ ).

再套用前面的論述, 我們有

$\displaystyle \langle$ $\displaystyle \sigma_{1}^{}$ ^... $\displaystyle \sigma_{r-1}^{}$ $\displaystyle \rangle$ $\displaystyle \cap$ $\displaystyle \langle$ $\displaystyle \sigma_{r}^{}$ $\displaystyle \rangle$ = {e}.

因此由歸納假設 ord( $\sigma_{1}^{}$ ^... $\sigma_{r-1}^{}$ ) = lcm[n₁,..., n_{r - 1}] 及 Lemma 3.4.8 得

ord( $\displaystyle \sigma$ )	=	ord(( $\displaystyle \sigma_{1}^{}$ ^... $\displaystyle \sigma_{r-1}^{}$ )^. $\displaystyle \sigma_{r}^{}$ )
	=	lcm[lcm[n₁,..., n_{r - 1}], n_r]
	=	lcm[n₁,..., n_{r - 1}, n_r].

$\qedsymbol$

Proposition 3.4.9 告訴我們一個很快的方法計算 S_n 的元素的 order. 例如若 $\sigma$ = (1 2 3)(4 5) 則 ord( $\sigma$ ) = lcm[2, 3] = 6. 這比你一個一個去乘快多了. 不過要記住 Proposition 3.4.9 只能當 disjoint cycle 乘在一起才適用. 例如 (1 2 3)(3 2 1) 是 identity. 其 order 為 1 不是 lcm[3, 3] = 3.