対称群
Contents
対称群
対称群 (英：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} \]