任何一個置換寫成對換的乘積時對換個數的奇偶性不變？

01-30

設 $S_n$ 表示 $n$ 元對稱群， $sigmain S_n$ 是一個置換，對 $n$ 進行歸納可以得到 $sigma$ 可以寫成有限個對換 $sigma_1,sigma_2cdots,sigma_k$ 的乘積
$sigma=sigma_1cdotssigma_k$
現在想證明如果 $sigma$ 可以寫成兩組不同對換的乘積，那麼這兩組對換的個數奇偶性相同，即如果
$sigma=sigma_1sigma_2cdotssigma_k= au_1 au_2cdots au_l$
其中 $sigma_1,sigma_2,cdots,sigma_k$ 和 $au_1, au_2,cdots au_l$ 都是對換，那麼

$kequiv lpmod{2}$
歸納法好像不怎麼行得通，我知道有一個證明是用排列的逆序數，但不喜歡這樣證明，請問有什麼比較好的證明嗎？

以下這個證明算是最直觀、自然且初等（除了置換的表示和規則以外，基本不再需要任何預備知識）的了，然而非常巧妙，曾經給我留下了很深刻的印象。

證明的關鍵基於以下的觀察與計算：

考慮最簡單的三元集 $left{ x,y,z ight}$ ，以及三元置換群 $S_{3}$ （對於更複雜的置換群，情況並沒有本質性的改變）。顯然，輪換 $left( z y x ight)$ 可以寫成對換分解 $left( x y ight)left( x z ight)$ ，其中 $x$ 在被置換為 $z$ 的同時，還起著過渡/承接/中間元（隨你怎麼叫吧）的作用——將 $z$ 通過 $z ightarrow x ightarrow y$ 的軌道置換為 $y$ 。我們要完成的計劃是——在不改變置換本身的前提下，改變對換的中間元 $x$ ，將 $x$ 移至對換分解序列的最左端，且使得其右邊任何對換中都不再包含 $x$ 。

這個「改變中間元」的技巧是可以實現的，只需用另外一個元素替代原有中間元即可。既然 $x$ 被置換為 $z$ ，而 $x$ 不再做中間元，那就用 $z$ 做中間元好了—— $left( x z ight)left( y z ight)$ ，也一樣是 $left( z y x ight)$ 這個輪換，同時 $x$ 也被移至對換分解序列的最左端。

這一技巧對於任意能寫成兩個對換複合的置換都適用。

這個技巧是證明的關鍵步驟，餘下的問題就都是平凡的討論了：

設置換 $sigma$ 的兩個不同的對換分解分別為 $au_{1} au_{2}cdots au_{m}$ 和 $au_{1}^prime au_{2}^primecdots au_{n}^prime$ ，則有 $sigma^{-1}= au_{m} au_{m-1}cdots au_{1}$ 。那麼顯然 $sigmacircsigma^{-1}= au_{1}^prime au_{2}^primecdots au_{n}^prime au_{m} au_{m-1}cdots au_{1}=e$ 。這樣一來，問題就歸結為證明單位（恆等）置換的任何對換分解只能是偶數個對換 $pi_{1}pi_{2}cdotspi_{k}$ 的複合。為證明 $k$ 是偶數，需要證明 $forall k>2$ ， $e$ 還可以分解為 $k-2$ 個對換的複合；重複這一過程直至最後，可以發現若 $k$ 為奇數，則最後將會得到單位置換 $e$ 等於某一個對換的荒謬結論，問題也就得到了證明。

從 $k$ 個對換削減至 $k-2$ 個對換，我們需要考慮任意一個出現在單位置換的對換分解序列 $pi_{1}pi_{2}cdotspi_{k}$ 中的數字 $x$ ，顯然 $exists 1leq h leq k, pi_{h}=left( x y ight)$ 且 $forall h<l leq k, pi_{l}left( x ight)=x$ ，然後分以下四種情形進行討論：

若 $pi_{h-1}=left(x y ight)$ ，則顯然可以在對換分解序列 $pi_{1}pi_{2}cdotspi_{k}$ 中消去 $pi_{h-1}$ 和 $pi_{h}$ ，因同一對換彼此互逆。
若 $pi_{h-1}=left( u v ight) wedge left{ x,y ight}capleft{ u,v ight}=emptyset$ ，即兩置換不相交，則 $pi_{h-1}$ 不改變 $x$ ，這意味著調換 $pi_{h-1}$ 和 $pi_{h}$ 的次序對於原置換並無改變，那麼進行這一調換，可見 $pi_{h}$ 在 $pi_{1}pi_{2}cdotspi_{k}$ 中的位置向左移一步，亦即 $pi_{1}pi_{2}cdotspi_{k}=pi_{1}pi_{2}cdots pi_{h}pi_{h-1} cdotspi_{k}$ ，而這令 $pi_{h}=left( x y ight)$ 中的 $x$ 也向序列 $pi_{1}pi_{2}cdotspi_{k}$ 的左端平移。
若 $pi_{h-1}=left(x z ight), z eq x,y$ ，則利用以上的「改變中間元」技巧得到—— $pi_{h-1}pi_{h}=left( x z ight)left( x y ight)=left( x y ight)left( y z ight)=pi_{h}pi^{prime}_{h-1}$ （其中 $pi^{prime}_{h-1}=left( y z ight)$ ）。可以發現，用 $pi_{h},pi^{prime}_{h-1}$ 分別取代 $pi_{h-1}, pi_{h}$ 的位置以後，置換 $pi_{1}pi_{2}cdotspi_{k}$ 本身不變，而 $pi_{h}=left( x y ight)$ 中的 $x$ 照樣朝序列 $pi_{1}pi_{2}cdotspi_{k}$ 的左端平移了。
若 $pi_{h-1}=left(y z ight), z eq x,y$ ，則利用以上的「改變中間元」技巧得到—— $pi_{h-1}pi_{h}=left( y z ight)left( x y ight)=left( x z ight)left( y z ight)=pi_{h}^{prime}pi_{h-1}$ （其中 $pi^{prime}_{h}=left( x z ight)$ ）。可以發現，用 $pi^{prime}_{h},pi_{h-1}$ 分別取代 $pi_{h-1}, pi_{h}$ 的位置以後，置換 $pi_{1}pi_{2}cdotspi_{k}$ 本身不變，而 $pi_{h}=left( x y ight)$ 中的 $x$ 照樣朝序列 $pi_{1}pi_{2}cdotspi_{k}$ 的左端平移了。

以上四種情形顯然涵蓋了全部可能出現的情況。情形1顯然把 $k$ 個對換複合而成的單位置換 $e=pi_{1}pi_{2}cdotspi_{k}$ 直接削減為 $k-2$ 個。而在情形2、3、4中，我們得到的仍是 $k$ 個對換的複合，但 $x$ 出現的位置將不斷地提前，也就是說指標 $h$ 將不斷下降，直至 $h=1$ 。那麼，最終結果僅剩以下兩種可能性：

單位置換的對換分解 $e=pi_{1}pi_{2}cdotspi_{k}$ 被削減為 $e=pi_{1}pi_{2}cdotspi_{h-2}pi_{h+1}cdotspi_{k}$ 這樣 $k-2$ 個對換的複合（對應於以上情形1）。
單位置換 $e$ 被分解為另一系列的 $k$ 個對換 $pi^{prime}_{1}pi^{prime}_{2}cdotspi^{prime}_{k}$ 之複合，其中 $x$ 僅被包含於 $pi^{prime}_{1}$ 中，而剩下的 $pi^{prime}_{2}, cdots ,pi^{prime}_{k}$ 皆與 $x$ 無關（對應於以上情形2、3、4）。然而，這意味著—— $x=eleft( x ight)=pi^{prime}_{1}pi^{prime}_{2}cdotspi^{prime}_{k}left( x ight)=pi^{prime}_{1}left( x ight)=y eq x$ （ $x eq x$ ，你是擅自停葯了嗎？）。

因此，單位置換的對換分解總是可以從 $k$ 個對換的複合削減至 $k-2$ 個，進而證明了 $k$ 是偶數。

而這已經完成了置換奇偶性不變的證明。

我蠻喜歡這個證明的，而且話說這個是抽象代數里的定理吧……

考慮向量空間 $R^{n}$ ，它有個標準基：

$forall sigma in S_{n}$ ，定義一個線性變換

$T_{sigma } :R^{n} ightarrow R^{n}$

$e_{i} ightarrow e_{sigma(i) }$

先看一個準備知識：

$sigma =(i,j)$ ，

$det T_{sigma } =-1$ （註：就是下面這個）

那接下來對於 $forall sigma, au in S_{n}$ ，我們知道

所以， $T_{sigma au } =T_{sigma } T_{ au }$

也就有 $detT_{sigma au } =detT_{sigma } cdot detT_{ au }$

設 $sigma=sigma_1sigma_2cdotssigma_k= au_1 au_2cdots au_l$ ，其中 $sigma_i$ 和 $au_i$ 都是對換

然後就有

$detT_{sigma} =detT_{sigma_{1} }cdot detT_{sigma_{2} }cdot cdot cdot detT_{sigma_{k} }=(-1)^{k}$

$detT_{ au } =detT_{ au_{1} }cdot detT_{ au_{2} }cdot cdot cdot detT_{ au_{l} }=(-1)^{l}$

所以 $k,l$ 的奇偶性相同，所以將一個置換寫成對換的乘積，所需對換的個數奇偶性唯一.

我來補充一個這個!

考慮 $S_n$ 在多項式環 $mathbb{Q}[X_1,...,X_n]$ 上的作用: $sigma in S_n$ 作用在 $X_i$ 上得到 $X_{sigma(i)}$ 。

考慮多項式 $P=prod_{1leqslant i<jleqslant n}(X_i-X_j)$ 。我們觀察到 $sigma(P)=pm P$ 。

假如 $sigma$ 能被寫成偶數多個對換的複合，那麼 $sigma(P)=+P$ ，如果 $sigma$ 能被寫成奇數多個對換的複合，那麼 $sigma(P)=-P$ 。

於是這兩種情況中只有一種能發生，一旦 $sigma$ 能被寫成奇數多個對換的複合，那麼它就不能被寫成偶數多個對換的複合；反之也是。

考慮 $S_n$ 作用到 $n$ 個元素上得到的 $n$ 次忠實復表示對應的矩陣表示 $Phi$ ，對於對換 $sigma_i$ ， $Phi(sigma_i)$ 左乘對應交換兩行的初等變換，由行列式的性質知道 $det(Phi(sigma_i))=-1$ ，故 $sigma=sigma_1sigma_2cdotssigma_k= au_1 au_2cdots au_lLeftrightarrow det(Phi(sigma))=(-1)^k=(-1)^l$

證明的關鍵是行列式交換兩行後變號，artin的代數上用子式展開定義行列式，可以繞過逆序數。

1，每一個置換都可以寫成不相交的輪換的積，

2，每一個n-輪換都可以寫成n個對換的積，

3，不相交的輪換乘積可交換。

搞清楚以上三條你就明白了，有啥不懂的你問我，我再更新答案。