置換群

$\{1,\dots,n\}$ 的所有雙射構成對稱群 $S_n$,元素叫置換 (permutation),共 $n!$ 個,運算是函數合成。兩列記法上列是輸入、下列是輸出;合成 $\sigma\tau$ 慣例上先做 $\tau$ 再做 $\sigma$(像函數 $\sigma(\tau(x))$),而且一般 $\sigma\tau\ne\tau\sigma$。

循環分解:任何置換可寫成不相交循環的乘積,而且除了循環的先後順序與每個循環的起點寫法以外是唯一的;階 = 循環長度的 $\text{lcm}$。反置換就是把每個對應反過來。奇偶性:每個置換是若干對換的乘積,個數的奇偶固定,偶置換構成交錯群 $A_n$($|A_n| = n!/2$);逆序對的奇偶也能判定。

算例:兩列記法 $\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$(把 1→2、2→3、3→1)就是 3-循環 $(1\,2\,3)$,階 3,下列 $2,3,1$ 有 2 個逆序對,偶置換;$\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$。

Cayley 定理說每個群都是某個置換群的子群,所以 $S_n$ 是「萬群之母」;$A_5$ 不可解是一般五次方程沒有根式公式解的關鍵(Galois 理論;個別五次方程如 $x^5 = 2$ 仍可用根式解);行列式的定義就是對所有置換按符號加總。