対称群

対称群 (英：semmantic group) とは、要素の入替操作を元とする群のこと。集合 $X$ から $X$ 自身への全単射写像 $\sigma:X\lrarr X$ を元とし、$\sigma$ の合成写像を演算 $\mu$ とする対称群は $(\mathrm{Sym}(X),\mu)$ のように表せる。

$\mathrm{Sym}(X) = \lbrace\sigma\mid\sigma:X\lrarr X\rbrace$

特に $n$ 個の連番 $I_n=\lbrace 1,2,\ldots,n\rbrace$ の対称群を $S_n$ と表す。$\mathrm{Sym}(X)$ と $S_n$ は $|X|=n$ ならば同型である。

$S_n = \mathrm{Sym}(I_n)$

置換

ある集合 $X$ において、全単射写像 $\sigma:X\lrarr X$ を「要素の入替操作」と見るとき、$\sigma$ を置換 (英：permutation) という。英語で置換も順列も "permutation" と訳せるが、これは permutation が順序を入れ替えることを意味しているため。順序の入替という意味では、置換と順列は本質的には同じ意味である。

$\begin{gathered} \sigma \in \mathrm{Sym}(X) \cr \cr \sigma = \begin{pmatrix} x_1 & x_2 & \cdots & x_n \cr \sigma(x_1) & \sigma(x_2) & \dots & \sigma(x_n) \cr \end{pmatrix} \end{gathered}$

よって $n$ 個の元を含む集合の対称群の位数は、$n$ 個中 $n$ 個を取り出し並べた順列の総数と一致する。

$|\mathrm{Sym}(X)| = \mathrm{P}(n,n) = n! \quad (|X|=n)$

対称群の演算

対称群の演算は、置換の合成写像で与えられ、その演算は群の代数的構造を持つ。

$\begin{gathered} \mu:\mathrm{Sym}(X)\times\mathrm{Sym}(X)\to\mathrm{Sym}(X) \cr \cr \mu(\sigma_1,\sigma_2) = \sigma_1\circ\sigma_2 \end{gathered}$

群構造の例：

集合 $I_3=\lbrace 1,2,3\rbrace$ からなる対称群 $S_3=\mathrm{Sym}(I_3)$ の、各置換 $\sigma_i\in S_n$ を以下のように定義する。このとき、対称群の演算が群構造を満たすか試してみる。一般に対称群の演算は非可換である点に注意すること。

$\begin{aligned} \sigma_1 &= \begin{pmatrix} 1 & 2 & 3 \cr 1 & 2 & 3 \cr \end{pmatrix} \cr \sigma_2 &= \begin{pmatrix} 1 & 2 & 3 \cr 1 & 3 & 2 \cr \end{pmatrix} \cr \sigma_3 &= \begin{pmatrix} 1 & 2 & 3 \cr 2 & 1 & 3 \cr \end{pmatrix} \cr \sigma_4 &= \begin{pmatrix} 1 & 2 & 3 \cr 2 & 3 & 1 \cr \end{pmatrix} \cr \sigma_5 &= \begin{pmatrix} 1 & 2 & 3 \cr 3 & 1 & 2 \cr \end{pmatrix} \cr \sigma_6 &= \begin{pmatrix} 1 & 2 & 3 \cr 3 & 2 & 1 \cr \end{pmatrix} \cr \end{aligned}$

二項演算の閉性：

$\begin{aligned} \sigma_2\circ\sigma_3 &= \begin{pmatrix} 1 & 2 & 3 \cr 1 & 3 & 2 \cr \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \cr 2 & 1 & 3 \cr \end{pmatrix} \cr &= \begin{pmatrix} 1 & 2 & 3 \cr 3 & 1 & 2 \cr \end{pmatrix} \cr &= \sigma_5\in S_3 \end{aligned}$

二項演算の結合性：

$\begin{aligned} \sigma_2\circ(\sigma_3\circ\sigma_4) &= \begin{pmatrix} 1 & 2 & 3 \cr 1 & 3 & 2 \cr \end{pmatrix} \circ \left[\begin{pmatrix} 1 & 2 & 3 \cr 2 & 1 & 3 \cr \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \cr 2 & 3 & 1 \cr \end{pmatrix}\right] \cr &= \begin{pmatrix} 1 & 2 & 3 \cr 1 & 3 & 2 \cr \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \cr 1 & 3 & 2 \cr \end{pmatrix} \cr &= \begin{pmatrix} 1 & 2 & 3 \cr 1 & 2 & 3 \cr \end{pmatrix} \cr &= \sigma_1 \cr \cr (\sigma_2\circ\sigma_3)\circ\sigma_4 &= \left[\begin{pmatrix} 1 & 2 & 3 \cr 1 & 3 & 2 \cr \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \cr 2 & 1 & 3 \cr \end{pmatrix}\right] \circ \begin{pmatrix} 1 & 2 & 3 \cr 2 & 3 & 1 \cr \end{pmatrix} \cr &= \begin{pmatrix} 1 & 2 & 3 \cr 3 & 1 & 2 \cr \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \cr 2 & 3 & 1 \cr \end{pmatrix} \cr &= \begin{pmatrix} 1 & 2 & 3 \cr 1 & 2 & 3 \cr \end{pmatrix} \cr &= \sigma_1 \cr \cr \sigma_2\circ(\sigma_3\circ\sigma_4) &= (\sigma_2\circ\sigma_3)\circ\sigma_4 \end{aligned}$

単位元の存在：

$\begin{aligned} \sigma_1\circ\sigma_3 &= \begin{pmatrix} 1 & 2 & 3 \cr 1 & 2 & 3 \cr \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \cr 2 & 1 & 3 \cr \end{pmatrix} \cr &= \begin{pmatrix} 1 & 2 & 3 \cr 2 & 1 & 3 \cr \end{pmatrix} \cr &= \sigma_3 \cr \cr \sigma_3\circ\sigma_1 &= \begin{pmatrix} 1 & 2 & 3 \cr 2 & 1 & 3 \cr \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \cr 1 & 2 & 3 \cr \end{pmatrix} \cr &= \begin{pmatrix} 1 & 2 & 3 \cr 2 & 1 & 3 \cr \end{pmatrix} \cr &= \sigma_3 \cr \end{aligned}$

逆元の存在：

$\begin{aligned} \sigma_4\circ\sigma_5 &= \begin{pmatrix} 1 & 2 & 3 \cr 2 & 3 & 1 \cr \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \cr 3 & 1 & 2 \cr \end{pmatrix} \cr &= \begin{pmatrix} 1 & 2 & 3 \cr 1 & 2 & 3 \cr \end{pmatrix} \cr &= \sigma_1 \cr \cr \sigma_5\circ\sigma_4 &= \begin{pmatrix} 1 & 2 & 3 \cr 3 & 1 & 2 \cr \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \cr 2 & 3 & 1 \cr \end{pmatrix} \cr &= \begin{pmatrix} 1 & 2 & 3 \cr 1 & 2 & 3 \cr \end{pmatrix} \cr &= \sigma_1 \cr \end{aligned}$

巡回置換

ある集合 $X$ の置換 $\sigma\in\mathrm{Sym}(X)$ により、次式が満たされるとき、この周期的な巡回を $(x_1 ~x_2 ~\cdots ~x_k)$ と表し、長さ $k$ の巡回置換 (英：cyclic permutation) という。

$x_1\xmapsto{\sigma} x_2\xmapsto{\sigma}\cdots\xmapsto{\sigma} x_k\xmapsto{\sigma} x_1$

巡廻置換は置換ごとに一つとは限らない。例えば次の置換 $\sigma$ を例えに考えると、

$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \cr 5 & 6 & 1 & 4 & 3 & 2 \cr \end{pmatrix}$

$\sigma$ には次の三つの巡回置換があることを確認できる。

$\begin{gathered} 1\xmapsto{\sigma} 5\xmapsto{\sigma} 3\xmapsto{\sigma} 1 \cr 2\xmapsto{\sigma} 6\xmapsto{\sigma} 2 \cr 4\xmapsto{\sigma} 4 \end{gathered}$

よって $\sigma$ は次式のように三つの巡回置換に分解することができ、この分解をサイクル分解 (英：cycle decomposition) という。長さが $1$ の巡回置換は表記を省略できる。

$\begin{aligned} \sigma &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \cr 5 & 6 & 1 & 4 & 3 & 2 \cr \end{pmatrix} \cr &= (1~5~3)(2~6) \end{aligned}$

恒等置換

入れ替えが発生しない置換、つまり長さが $1$ の巡回置換 $\sigma$ を恒等置換 (英：identity permutation) という。

$\sigma_0 = \sigma_0\sigma$

互換

二つの要素のみを入れ替える置換、つまり長さが $2$ の巡回置換 $\sigma$ を互換 (英；transposition) という。

$\sigma_0 = \sigma_0\sigma^2$

置換の符号

任意の置換 $\sigma$ は、異なる互換の積で表すことができる。このとき、互いに異なる互換 $\sigma_i$ の数 $n$ が奇数の場合は $\sigma$ を奇置換 (英：odd permutation)、偶数の場合は $\sigma$ を偶置換 (英：even permutation) と呼ぶ。

$\sigma = \sigma\prod_{i}^n \sigma_i$

このとき、$\sigma$ が奇置換であるときに $-1$ 、偶置換であるときに $+1$ を割り当てたものを置換の符号 (英：parity of a permutation) という。

$\mathrm{sgn}(\sigma) = \begin{cases} -1 & \text{if }\sigma\text{ is odd permutation} \cr +1 & \text{if }\sigma\text{ is even permutation} \cr \end{cases}$

関連記事

• 順列と組合せ
• 群
• 合成写像