# 代數導論 (17) - Conjugate Classes of Sn

[TOC]

這邊討論的是對稱群 $S_n$，而討論的 *group action* 是「取共軛」。也就是：

$$
\begin{align}
S_n \times S_n &\to S_n
\newline
(\tau, \sigma) &\mapsto (\tau \sigma \tau^{-1})
\end{align}
$$

## 性質：共軛就是逐元作用

:::danger
**Thm**

假定 $\tau, \sigma \in S_n$。若已知 $\sigma$ 的循環表示為：

$$
\sigma = \prod_{i = 1}^{m}(a_{i,1} \dots a_{i,n_i})
$$

則 $\tau \sigma \tau^{-1}$ 的循環表示為「把所有 $\sigma$ 中的元素替換成 $\tau$ 的作用結果」。即：

$$
\boxed{\begin{align}
\sigma &= \prod_{i = 1}^{m}(a_{i,1} \dots a_{i,n_i})
\newline
&\Rightarrow \tau \sigma \tau^{-1} = \prod_{i = 1}^{m}(\tau(a_{i,1}) \dots (a_{i,n_i}))
\end{align}}
$$

:::

因為任何一個循環表示法取共軛，都可以拆開為共軛的連續合成：

$$
\tau(\dots)(\dots)\tau^{-1} = \tau(\dots)\tau^{-1}\tau(\dots)\tau^{-1}
$$

所以不失一般性地，只要證明單一循環會成立，那麼對於多個循環組成的運算，只要像上面那樣逐個拆開，並將單一循環的結論套用到每個循環就好。

也就是說：假定有一個循環的形式如下的循環：

$$
\sigma = (a_1 \dots a_m)
$$

目標是要證明：

$$
(\tau \sigma \tau^{-1}) = (\tau(a_1) \dots \tau(a_m))
$$

要證明這件事，只要證明兩件事：

1. $(\tau \sigma \tau^{-1})$ 會把 $\tau(a_1) \dots \tau(a_m)$ 往後送一個。
2. 不在這當中的人會送到原來的地方。

對於任意 $\tau(a_i)$，有：

$$
\sigma(a_i) = \begin{cases}
a_{i + 1} & \text{if }1 \leq i \leq m - 1
\newline
a_1 & \text{if }i = m
\end{cases}
$$

所以，把任何一個 $a_i$ 丟進 $(\tau \sigma \tau^{-1})$ 中並化簡，就會發現： $(\tau \sigma \tau^{-1})$ 中的 $\tau^{-1}$ 被消掉了：

$$
\begin{align}
(\tau \sigma \tau^{-1})\tau(a_i) &= \tau(\sigma(a_i))
\newline
&= \tau(a_{i + 1})
\newline
&= \begin{cases}
\tau(a_{i + 1}) & \text{if }1 \leq i \leq m - 1
\newline
\tau(a_1) & \text{if }i = m
\end{cases}
\end{align}
$$

而假定 $a$ 不是 $a_1 \dots a_m$ 的其中一個，那麼這時候：

$$
\sigma(a) = a
$$

因此，把 $\tau(a)$ 帶進去 $(\tau \sigma \tau^{-1})$ 時，就會發現還是 $\tau(a)$：

$$
\begin{align}
(\tau \sigma \tau^{-1})\tau(a) &= \tau(\sigma(a))
\newline
&= \tau(a)
\end{align}
$$

由此得證。

## 定義：Cycle Type & Partition

:::warning
**Def (Cycle Type)**
假定 $\sigma \in S_n$，且把 *1-cycle* 算進去時，$\sigma$ 由 $r$ 個循環組成，且他們的長度由小到大分別為 $n_1 \dots n_r$。即：

$$
n_1 \leq n_2 \leq \dots \leq n_r
$$

其中：

$$
\sum_{i = 1}^{r} n_i = n
$$

則這些長度 $n_1 \dots n_r$ 由小到大所形成的序列，稱為 $\sigma$ 的 *cycle type*。
:::

舉例來說，對於 $S_8$，考慮其中一個元素：

$$
\sigma = (4, 6)(1, 2, 3)
$$

這個元素的 *cycle type* 就是「把所有 *1-cycle* 補回去後，*cycle* 長度由小到大排成的序列」。所以，把它的 *1-cycle* 補回去：

$$
\sigma = (5)(7)(8)(4, 6)(1, 2, 3)
$$

然後把 *cycle* 長度由小到大列出來，也就是：

$$
1, 1, 1, 2, 3,
$$

這個序列就是 $\sigma$ 的 *cycle type*。

其實有一個細節是：每個 $S_n$ 中的元素， *cycle decomposition* 都是唯一的，所以每 $S_n$ 中的元素 *cycle type* 都是唯一的。但這需要證明。不過上課時沒有證明這件事。但可能日後會補。

仔細觀察上面再做的事：找到一個「加總起來是 $n$ 的正整數序列」。這根本就是在問「$n$ 的整數分割」。也因此：列舉 *cycle type* 這件事，其實就是在列舉一個正整數的所有分割方法。而指這邊的「整數分割」定義如下：

:::warning
**Def (整數分割)**

假定 $n \in \mathbb{N}$。若存在正整數序列 $n_1 \dots n_r$：

$$
0 < n_1 \leq n_2 \leq \dots \leq n_r
$$

使得：

$$
n = \sum_{i = 1}^{r}n_r
$$

則稱序列 $n_1 \dots n_r$ 是一個整數 $n$ 的「分割」(*partition*)。
:::

### 觀察：有共軛關係 = Cycle Type 相同
:::danger
**Prop**
假定 $\sigma_1$, $\sigma_2 \in S_n$。則「$\sigma_1$, $\sigma_2$ 互相共軛」的充分必要條件是「$\sigma_2$, $\sigma_2$ 的 *cycle type* 相同」。即：

$$
\begin{align}
&\exists \tau \in S_n.\ \sigma_2 = \tau \sigma \tau^{-1}
\newline
&\iff\sigma_1, \sigma_2 \text{ have same }\mathbf{cycle\ type}
\end{align}
$$

:::

首先，$\Rightarrow$ 是顯然，因為前面已經證明「取共軛」就是把那個用來作用的 $\tau$ 逐一套進 $\sigma$ 每個循環中的每個元素。所以 *cycle type* 仍然一樣。因此，只要證明 $\Leftarrow$ 的方向就可以了。

但這也很直接：假定 $\sigma_1, \sigma$ 具有相同的 *cycle type*。把所有包含 *1-cycle* 的循環列出來後：

$$
\begin{align}
\sigma_1 &= (a_{1, 1} \dots a_{1, n_1})\dots(a_{r, 1} \dots a_{r, n_r})
\newline
\sigma_2 &= (b_{1, 1} \dots b_{1, n_1})\dots(b_{r, 1} \dots b_{r, n_r})
\end{align}
$$

只要令：

$$
\tau(a_{ij}) = b_{ij}
$$

$\tau$ 就是個合法的 *permutation* 了：因為所有的 $a_{ij}$ 就剛好是 $1 \dots n$ 各出現一次，而 $b_{ij}$ 也是，所以 $\tau$ 只是幫 $1 \dots n$ 的順序，由 $\sigma_1$ 中出現排列順序，換成在 $\sigma_2$ 中的排列順序。既然只是交換 $1 \dots n$ 的順序，$\tau$ 就會在 $S_n$ 中。

### 觀察：Cycle Type 數目 = 整數分割方法
:::danger
**Prop**
$S_n$ 的 *conjugacy class* (或說 *orbit*) 數目，和對 $n$ 進行 *partition* 的方法數一樣多。
:::

這其實就是上面的推論：因為「在同一個 *conjugate class*」的充要條件是「*cycle type* 相同」，每一種 *cycle type* 就恰好對應一種 *conjugate class*。

### 觀察：m-cycle 中，Conjugate Class 與 Stabilizer 數目與大小

既然知道每個 *conjugate class* 所對應的 *cycle-type*，就可以用各種排列組合的技巧算出這個 *conjugate class* 中包含了多少元素。舉例來說：以 *m-cycle* 這個 *conjugacy cass* 而言，所有具有：

$$
\sigma = (a_1 \dots a_m)
$$

形式的 *cycle*，都是 *conjugate class* 中的元素。因此，計數這個 *conjugate class* 的大小，就是在算 $a_1 \dots a_m$ 有多少種可能的排列組合這。這是環狀排列的問題：$1 \dots n$ 中選 $m$ 個元素塞進 $a_1 \dots a_m$，但因為整個 *cycle* 轉一圈沒有差別，所以還要再除上 *cycle* 的長度。也就是說：對於 *m-cycle* 這個形式的 *conjugate class*，他的大小為：

$$
\boxed{|orb(\sigma)| = \frac {P^n_{m}}{m}}
$$

而既然 *m-cycle* 這個 *conjugate class* (也就是 *orbit*) 的大小已經知道了，那麼利用 *stabilizer-orbit theorem*，就可以知道 *centralizer* 的大小：

$$
|G_{\sigma}| = \frac {|S_n|}{|orb(\sigma)|} \Rightarrow \boxed{|G_{\sigma}|= m(n - m)!}
$$

### 觀察：m-cycle 的 Stabilizer 形式

接下來要問的是：對於任何一個 *m-cycle* $\sigma$，他的 *Stabilizer*，長怎樣？首先，$\langle \sigma \rangle$ 一定會在裡面，因為這根本就是：

$$
(\sigma^{i}) \sigma (\sigma^{i})^{-1} = \sigma(\sigma^i) (\sigma^{i})^{-1} = \sigma
$$

除此之外，循環表示不出現在 $a_1 \dots a_m$ 中的那些元素 $\tau$，也會在裡面。這是因為：既然循環表示法中沒有 $a_1 \dots a_m$ 中任何元素，所以 $\tau$ 有：

$$
\tau(a_i) = a_i \quad \forall i = 1\dots m
$$

但這樣一來，依照前面的性質：

$$
\begin{align}
(\tau \sigma\tau^{-1}) &= (\tau(a_1) \dots \tau(a_m))
\newline
&= (a_1 \dots a_m)
\end{align}
$$

因此，這樣的 $\tau$ 也會在 *centralizer* 裡面。更進一步，因為 *Stabilizer* 是個子群，所以任意具有：

$$
\sigma^{i}\tau_j
$$

形式的元素，都會是 $\sigma$ 的 *stabilizer*。其中，$\tau_j$ 是那些「作用在任何 $a_1 \dots a_m$ 時，不會產生變化的那須 *permutation*」因此：以下的集合就會在 *stabilizer* 中：

$$
S = \{\sigma^i\tau_j \mid 1 \leq i \leq m, \tau_j(a_i) = a_i \forall i \}
$$

事實上，可以證明：$S$ 就是 $\sigma$ 的 *stabilizer*：

:::danger
**Thm**

假定 $\sigma \in S_n$ 是一個 *m-cycle*。則 $\sigma$ 的 *stabilizer* 是以下集合：

$$
G_{\sigma} = \{\sigma^i\tau_j \mid 1 \leq i \leq m, \tau_j(a_i) = a_i \forall i \}
$$

:::

但這個其實明顯的：因為 $\langle \sigma \rangle$ 裡面就只有 $m$ 種不同元素，而 $\tau_j$ 就是 $a_1 \dots a_m$ 以外剩下 $(n - m)$ 個元素的 *permutation* 方法總數，因此就是 $(n - m)!$。所以只要證明：這所有的表示法中，任兩種表法都不會表出相同的元素，就可以了。假定：

$$
\sigma^{i}\tau_j = \sigma^{i'}\tau_{j'}
$$

目標是 $i = i'$ 且 $j = j'$。老樣子把每個元素帶進去。假定這個元素 $a$ 是 $a_1 \dots a_m$ 中的一員，那麼 $\tau_i$ 與 $\tau_{i'}$ 作用上去都沒有用：

$$
\begin{align}
\tau_i(a) &= a
\newline
\tau_{i'}(a) &= a
\end{align} \Rightarrow\sigma^{i}(a) = \sigma^{i'}(a)\ \forall a \in \{a_1 \dots a_m\}
$$

因為對於任意 $a_1 \dots a_m$ 都對，$\sigma$ 又是個 *m-cycle*。所以依照循環群的性質：

$$
\sigma^{i} = \sigma^{i'} \Rightarrow i = i'
$$

另外一方面，如果 $a$ 不在 $a_1 \dots a_m$ 中，因為 $\tau_{j}$ 與 $\tau_{j'}$ 都是 $a_1 \dots a_m$ 以外的元素的 *permutation*，所以 $\tau$ 作用之後，還是 $a_1 \dots a_m$ 以外的元素，因此不管被 $\sigma$ 作用幾次都維持不變。所以：

$$
\begin{align}
\sigma^i(\tau_j(a)) &= \tau_j(a)
\newline
\sigma^{i'}\tau_{j'}(a) &= \tau_{j'}(a)
\newline
\Rightarrow &\tau_{j}(a) = \tau_{j'}(a)\ \forall a \not\in\{a_1 \dots a_m\}
\end{align}
$$

因為 $\tau_j$ 與 $\tau_{j'}$ 是那些「不是 $a_1 \dots a_m$」的元素間的 *permutation*，所以只要任意不再 $a_1 \dots a_m$ 中的 $a$ 都相等，兩個 *oermutation* 就相等。因此：

$$
\tau_j = \tau_{j'}
$$

由此得證：這 $m \cdot (m - n)!$ 個元素，都是相異的元素，因此得證兩個集合大小相等，所以這個集合就剛好是 $G_{\sigma}$。