代数的構造である群は，対称性を捉えるのに非常に便利な概念である．ここでは，置換とその演算を考え，それによって構成される群について扱う．
置換群
一般の集合に対して，置換は次のように定義される．
$X$を集合とする．全単射$\sigma :X\to X$を$X$の置換(permutation)という．
また，$\sigma ^{-1}$を$\sigma$の逆置換(inverse permutation)という．
$S$を集合$X$の置換全体からなる集合とし，$S$上の演算$\phi$を
\[ \sigma \tau =\sigma \circ \tau \quad (\sigma ,\tau \in S)\]
により定めるとき，$S$は$\phi$に関して群であり，$S$を$X$の置換群(permutation group)という．
定義2において，$S$が群であることを確認する．
まず，任意の$x\in X$及び$\sigma ,\tau ,\upsilon \in S$に対し
\[ ((\sigma \circ \tau )\circ \upsilon )(x)=(\sigma \circ \tau )(\upsilon (x))=\sigma (\tau (\upsilon (x)))=\sigma ((\tau \circ \upsilon )(x))=(\sigma \circ (\tau \circ \upsilon ))(x)\]
であるから
\[ (\sigma \circ \tau )\circ \upsilon =\sigma \circ (\tau \circ \upsilon )\]
が成り立つ．
また，$\mathrm{id}_X\in S$は$S$の単位元である．実際，任意の$x\in X$及び$\sigma \in S$に対し
\[ (\sigma \circ \mathrm{id}_X)(x)=\sigma (\mathrm{id}_X(x))=\sigma (x)\]
\[ (\mathrm{id}_X\circ \sigma )(x)=\mathrm{id}_X(\sigma (x))=\sigma (x)\]
であるから
\[ \sigma \circ \mathrm{id}_X=\mathrm{id}_X\circ \sigma =\sigma \]
が成り立つ．
さらに，任意の$\sigma \in S$に対し，逆置換$\sigma ^{-1}\in S$は$\sigma$の逆元である．実際，任意の$x\in X$に対し
\[ (\sigma \circ \sigma ^{-1})(x)=\sigma (\sigma ^{-1}(x))=x=\mathrm{id}_X(x)\]
\[ (\sigma ^{-1}\circ \sigma )(x)=\sigma ^{-1}(\sigma (x))=x=\mathrm{id}_X(x)\]
であるから
\[ \sigma \circ \sigma ^{-1}=\sigma ^{-1}\circ \sigma =\mathrm{id}_X\]
が成り立つ．
ただし，$S$は可換群であるとは限らない．
対称群
以下，$n\in \mathbb{N}$とする．
$\{ 1,2,\dots ,n\} $の置換群を$n$次対称群($n$-th symmetric group)といい，$S_n$(または$\mathfrak{S}_n$，$\mathrm{Sym}(n)$，$\Sigma _n$)で表す．また，$S_n$の元を$n$次の置換($n$-th permutation)という．
\[ |S_n|=n!\]
$\sigma \in S_n$とすると，$\sigma :\{ 1,2,\dots ,n\} \to \{ 1,2,\dots ,n\}$は全単射であるから
\[ \sigma (1),\sigma (2),\dots ,\sigma (n)\]
は$1,2,\dots ,n$の並び替えである．したがって，$S_n$の元の個数は$n!$である．$\blacksquare$
$S_n$の元の表記方法には，二行記法，一行記法の2種類がある．
$\sigma \in S_n$は次のように表す，
- $\begin{pmatrix}1&2&\cdots &n\\ \sigma (1)&\sigma (2)&\cdots &\sigma (n)\end{pmatrix}$
- $\begin{pmatrix}\sigma (1)&\sigma (2)&\cdots &\sigma (n)\end{pmatrix}$
$\sigma \in S_4$を
\[ \sigma (1)=2,\sigma (2)=4,\sigma (3)=1,\sigma (4)=3\]
により定めるとき
\[ \sigma =\begin{pmatrix}1&2&3&4\\ 2&4&1&3\end{pmatrix}\]
である．$\sigma$は次のように表記してもよい．
\[ \sigma =\begin{pmatrix}3&1&4&2\\ 1&2&3&4\end{pmatrix}=\begin{pmatrix}2&4&1&3\end{pmatrix}\]
$S_n$は可換群でない．
$3$次対称群$S_3$は
\[ S_3=\left\{ \begin{pmatrix}1&2&3\\ 1&2&3\end{pmatrix},\begin{pmatrix}1&2&3\\ 1&3&2\end{pmatrix},\begin{pmatrix}1&2&3\\ 2&1&3\end{pmatrix},\begin{pmatrix}1&2&3\\ 2&3&1\end{pmatrix},\begin{pmatrix}3&1&2\\ 1&2&3\end{pmatrix},\begin{pmatrix}1&2&3\\ 3&2&1\end{pmatrix}\right\} \]
であり，例えば
\[ \sigma =\begin{pmatrix}1&2&3\\ 1&3&2\end{pmatrix},\quad \tau =\begin{pmatrix}1&2&3\\ 2&1&3\end{pmatrix}\]
とすると
\[ (\sigma \circ \tau )(3)=\sigma (\tau (3))=\sigma (3)=2\]
\[ (\tau \circ \sigma )(3)=\tau (\sigma (3))=\tau (2)=1\]
であるから，$\sigma \circ \tau \neq \tau \circ \sigma$であり，$S_3$は可換群でない．
巡回置換と互換
巡回置換
$m\in \mathbb{N}$とする．$\sigma \in S_n$に対し，$\sigma ^m$を
\[ \sigma ^m\coloneqq \begin{cases}\sigma &(m=1)\\ \sigma ^{m-1}\circ \sigma &(m\in \mathbb{N}\setminus \{ 1\} )\end{cases}\]
により定めることにする．
また，$i\le n$かつ$i\neq \sigma (i)$を満たす$i\in \mathbb{N}$に対し，$\sigma ^m(i)=i$となる最小の$m\in \mathbb{N}$を$N$とし
\[ S=\{ i,\sigma (i),\sigma ^2(i),\dots ,\sigma ^{N-1}(i)\} \]
とする．
\[ \sigma (j)\begin{cases}\neq j&(j\in S)\\ =j&(j\not\in S)\end{cases}\]
であるとき，$\sigma$を長さ(length)$N$の巡回置換(cycle)といい，$(i,\sigma (i),\sigma ^2(i),\dots ,\sigma ^{N-1}(i))$で表す．
$\sigma \in S_5$が
\[ \sigma (1)=1,\sigma (2)=3,\sigma (3)=5,\sigma (4)=4,\sigma (5)=2\]
により定められているとき
\[ \sigma ^2(2)=(\sigma \circ \sigma )(2)=\sigma (\sigma (2))=\sigma (3)=5\]
\[ \sigma ^3(2)=(\sigma \circ \sigma \circ \sigma )(2)=\sigma (\sigma ^2(2))=\sigma (5)=2\]
であるから，$\sigma$は長さ$3$の巡回置換であり，$(2,3,5)$で表す($(3,5,2),(5,2,3)$と表しても良い)．
定義5において，巡回置換の長さ$N$が$i$の値により変わらない(巡回置換の長さの定義がwell-definedである)ことを確認する．
まず
\[ i,\sigma (i),\sigma ^2(i),\dots ,\sigma ^{N-1}(i)\]
が相異なることを示す．$N$の定義より，任意の$N-1$以下の正の整数$k$に対し，$i\neq \sigma ^k(i)$が成り立つ．
ここで，$p,q$を$p<q$となる$N$未満の正の整数とし，$\sigma ^p(i)=\sigma ^q(i)$であると仮定すると
\[ i=\sigma ^N(i)=\sigma ^{N-q}(\sigma ^q(i))=\sigma ^{N-q}(\sigma ^p(i))=\sigma ^{N+p-q}(i)\]
となるが，$N>N+p-q$より，$N$の最小性に矛盾する．
さて，任意の$j\in S$に対し，ある$m\in \mathbb{N}$が存在し，$j=\sigma ^m(i)$と表されるから
\[ j,\sigma (j),\sigma ^2(j),\dots ,\sigma ^{N-1}(j)\]
すなわち
\[ \sigma ^m(i),\sigma ^{m+1}(i),\dots ,\sigma ^{m+N-1}(i)\]
は
\[ i,\sigma (i),\sigma ^2(i),\dots ,\sigma ^{N-1}(i)\]
の並び替えである．よって，ある$N$未満の非負整数$m^{\prime}$が存在し，$\sigma^N(j)=\sigma ^{m^{\prime}}(j)$となる．ただし，$\sigma ^0(i)=i$とする．$m^{\prime}\neq 0$であると仮定すると$\sigma ^{m^{\prime}-1}(j)=\sigma ^{N-1}(j)$となり
\[ i,\sigma (i),\sigma ^2(i),\dots ,\sigma ^{N-1}(i)\]
が相異なることに矛盾する．したがって$\sigma ^N(j)=j$であり，巡回置換の長さは$i$に依存しない．
$i,j,p,q\in \mathbb{N}$，$i\le n$かつ$j\le n$とし，巡回置換$\sigma ,\tau ,\in S_n$を
\[ \sigma =(i,\sigma (i),\sigma ^2(i),\dots ,\sigma ^p(i))\]
\[ \tau =(j,\tau (j),\tau ^2(j),\dots ,\tau ^q(j))\]
により定める．
$i,\sigma (i),\sigma ^2(i),\dots ,\sigma ^p(i),j,\tau (j),\tau ^2(j),\dots ,\tau ^q(j)$が相異なるとき，$\sigma$と$\tau$は互いに素(disjoint)であるという．
互いに素な巡回置換の積は可換である．
$i,j,p,q\in \mathbb{N}$，$i\le n$かつ$j\le n$とし，互いに素な巡回置換$\sigma ,\tau ,\in S_n$を
\[ \sigma =(i,\sigma (i),\sigma ^2(i),\dots ,\sigma ^p(i))\]
\[ \tau =(j,\tau (j),\tau ^2(j),\dots ,\tau ^q(j))\]
により定め，集合$S,T$を
\[ S=\{ i,\sigma (i),\sigma ^2(i),\dots ,\sigma ^p(i)\} \]
\[ T=\{ j,\tau (j),\tau ^2(j),\dots ,\tau ^q(j)\} \]
とする．$S\cap T=\emptyset$に注意する．
このとき
\[ (\sigma \circ \tau )(k)=\sigma (\tau (k))=\begin{cases}\sigma (k)&(k\in S)\\ \tau (k)&(k\in T)\\ k&(k\not \in S\cup T)\end{cases}\]
\[ (\tau \circ \sigma )(k)=\tau (\sigma (k))=\begin{cases}\sigma (k)&(k\in S)\\ \tau (k)&(k\in T)\\ k&(k\not \in S\cup T)\end{cases}\]
であるから，$\sigma \circ \tau =\tau \circ \sigma$が成り立つ．$\blacksquare$
任意の置換は互いに素な巡回置換の積で(順序を除いて)一意に表される．
ただし，恒等置換は$0$個の巡回置換の積で，巡回置換は$1$個の巡回置換の積で表されるものと考える．
$\sigma =\begin{pmatrix}1&2&\cdots &n\\ \sigma (1)&\sigma (2)&\cdots &\sigma (n)\end{pmatrix}\in S_n$とし，$S=\emptyset$とする．次の操作を考える．
$m\neq \sigma (m)$を満たす$m\in \{ 1,2,\dots ,n\} \setminus S$をとる．数列$\{ \sigma _i\}_{i=1}^{\infty}$を
\[ \sigma _1=m,\quad \sigma _{i+1}=\sigma (\sigma _i)\quad (i\in \mathbb{N})\]
により定めると，任意の$i\in \mathbb{N}$に対し，$\sigma _i\in \{ 1,2,\dots ,n\}$であるから，ある$p,q\in \mathbb{N}$が存在し，$p<q$かつ$\sigma _p=\sigma _q$となる．このような$(p,q)$の組のうち，$p$が最小であるものを$(s,t)$とすると，$s=1$である．
実際，$s\neq 1$とすると，$\sigma$は全単射であるから$\sigma _{s-1}=\sigma _{t-1}$となり，$(s,t)$の最小性に矛盾する．
よって，$(\sigma _1,\sigma _2,\dots ,\sigma _{t-1})$は巡回置換である．
$S$を$S\cup \{ \sigma _1,\sigma _2,\dots ,\sigma _{t-1}\}$に置き換える．
この操作を，条件を満たす$m$が存在しなくなるまで繰り返すと，$\sigma$は得られた互いに素な巡回置換の積で表すことができる．また，その表し方は一意的である．$\blacksquare$
互換
長さ$2$の巡回置換を互換(transposition)という．
$i<n$を満たす$i\in \mathbb{N}$に対し，$(i,i+1)$を基本互換(fundamental transpositions)(または隣接互換(adjacent transpositions))という．
$\sigma \in S_4$が
\[ \sigma (1)=1,\sigma (2)=2,\sigma (3)=4,\sigma (4)=3\]
により定められているとき，$\sigma$は互換であり，$(3,4)$で表す($(4,3)$と表しても良い)．
任意の置換は基本互換の積で表される．
定理1とは異なり，任意の置換を互換の積で表す方法は複数ある場合がある．
定理2の証明は直感的に理解するとよい．まず，置換は$1,2,\dots ,n$の並び替えに対応する．任意の$1,2,\dots ,n$の並び替えは
\[ 1,2,\dots ,n\]
から始めて，以下の操作
$n$個の正の整数の列から隣り合う2つの数を選び，順序を交換する(場所を入れかえる)
を繰り返すことで得られる．これを厳密に議論すると，次のようになる．
$n$未満の正の整数$i$に対し，互換の列$\{ \sigma _i\} _{i=1}^{n-1}$を
\[ \sigma _i=(i,i+1)\quad (i=1,2,\dots ,n-1)\]
により定める．
$\sigma \in S_n$とする．任意の$j\in \mathbb{N}$に対し，次の操作を繰り返し行う．
$j-1$以下の任意の正の整数$k$に対し，$\sigma (k)=k$であり，$\sigma (j)\neq j$であるとき，$j+1$以上$n$以下の整数$i$が存在し，$\sigma (i)=j$となる．このとき
\[ \tau _j=\sigma _j\circ \sigma _{j+1}\circ \dots \circ \sigma _{i-1}\circ \sigma \in S_n\]
とおくと，$\tau _j(j)=j$である．
このとき，$\sigma =\tau _{n-1}\circ \tau _{n-2}\circ \dots \circ \tau _1$であるから，$\sigma$は基本互換の積で表すことができる．$\blacksquare$
置換の符号
差積
変数$x_1,x_2,\dots ,x_n$の差積(product of differences, difference product)(またはヴァンデルモンド多項式(Vandermonde polynomial))$\Delta (x_1,x_2,\dots ,x_n)$を次のように定義する．
\[ \Delta (x_1,x_2,\dots ,x_n)\coloneqq \prod _{i<j\\ i,j\in \{ 1,2,\dots ,n\} }(x_i-x_j)\]
差積と互換の間には，次のような関係がある．
$x_1,x_2,\dots ,x_n$を変数，$\sigma$を互換とすると，次が成り立つ．
\[ \Delta (\sigma (x_1),\sigma (x_2),\dots ,\sigma (x_n))=-\Delta (x_1,x_2,\dots ,x_n)\]
$\sigma =(p,q)\in S_n$とし，$p<q$とする．
\[ x_{\sigma (p)}-x_{\sigma (q)}=x_q-x_p=-(x_p-x_q)\]
$i<p$のとき
\[ (x_{\sigma (i)}-x_{\sigma (p)})(x_{\sigma (i)}-x_{\sigma (q)})=(x_i-x_q)(x_i-x_p)=(x_i-x_p)(x_i-x_q)\]
$p<i<q$のとき
\[ (x_{\sigma (p)}-x_{\sigma (i)})(x_{\sigma (i)}-x_{\sigma (q)})=(x_q-x_i)(x_i-x_p)=(x_p-x_i)(x_i-x_q)\]
$i>q$のとき
\[ (x_{\sigma (p)}-x_{\sigma (i)})(x_{\sigma (q)}-x_{\sigma (i)})=(x_q-x_i)(x_p-x_i)=(x_p-x_i)(x_q-x_i)\]
$i,j$が$p,q$とは異なるとき
\[ x_{\sigma (i)}-x_{\sigma (j)}=x_i-x_j\]
であるから，$\sigma$によって$x_p-x_q$のみが$-1$倍され，それ以外は不変であるから
\[ \Delta (\sigma (x_1),\sigma (x_2),\dots ,\sigma (x_n))=-\Delta (x_1,x_2,\dots ,x_n)\]
が成り立つ．$\blacksquare$
置換の符号
置換$\sigma$が奇数個の互換の積で表されるとき，$\sigma$を奇置換(odd permutation)といい，$\sigma$が偶数個の互換の積で表されるとき，$\sigma$を偶置換(even permutation)という．
置換$\sigma$の符号(sign, signature)$\mathrm{sgn} \ \sigma$を次のように定義する．
\[ \mathrm{sgn} \ \sigma =\begin{cases}1&(\sigma は偶置換)\\ -1&(\sigma は奇置換)\end{cases}\]
定義10がwell-definedである(置換を互換の積で表したとき，用いる互換の個数の偶奇はその表し方に依らない)ことを確認する．
$s,t\in \mathbb{N}$とする．また，変数$x_1,x_2,\dots ,x_n$と置換$\sigma \in S_n$に対して
\[ \Delta (\sigma (x_1),\sigma (x_2),\dots ,\sigma (x_n))\]
を$\sigma \Delta$で表すことにする．
$\sigma$が，互換$\tau _1,\tau _2,\dots ,\tau _s,\upsilon _1,\upsilon _2,\dots ,\upsilon _t\in S_n$を用いて
\[ \sigma =\tau _1\tau _2\dots \tau _s=\upsilon _1\upsilon _2\dots \upsilon _t\]
と表されるとき，命題3より
\[ \sigma \Delta =(\tau _1\tau _2\dots \tau _s)\Delta =\tau _1(\tau _2(\dots (\tau _s \Delta )))=(-1)^s\Delta \]
\[ \sigma \Delta =(\upsilon _1\upsilon _2\dots \upsilon _t)\Delta =\upsilon _1(\upsilon _2(\dots (\upsilon _t \Delta )))=(-1)^t\Delta \]
よって$(-1)^s=(-1)^t$であるから，$s$と$t$の偶奇は一致する．
$\sigma ,\tau \in S_n$とするとき，次が成り立つ．
- $\mathrm{sgn}\ \sigma \tau =(\mathrm{sgn}\ \sigma )(\mathrm{sgn}\ \tau )$
- $\mathrm{sgn}\ \sigma =\mathrm{sgn}\ \sigma ^{-1}$
- $r,s\in \mathbb{N}$とする．$\sigma$が$r$個の互換の積で，$\tau$が$s$個の互換の積で表されるとすると，$\sigma \tau$は$r+s$個の積で表されるから
\[ \mathrm{sgn}\ \sigma \tau =(-1)^{r+s}=(-1)^r(-1)^s=(\mathrm{sgn}\ \sigma )(\mathrm{sgn}\ \tau )\quad \blacksquare \] - $r\in \mathbb{N}$とする．$\sigma$が$r$個の互換$\tau _1,\tau _2,\dots ,\tau _r\in S_n$の積で
\[ \sigma =\tau _1\tau _2\dots \tau _r\]
と表されるとき，$\tau _1^{-1},\tau _2^{-1},\dots ,\tau _r^{-1}$も互換であり
\[ \sigma ^{-1}=\tau _r^{-1}\dots \tau _2^{-1}\tau _1^{-1}\]
となるから，$\mathrm{sgn}\ \sigma ^{-1}=(-1)^r=\mathrm{sgn}\ \sigma \blacksquare$