対称群 | 群論入門

1 任意集合の対称群

定義 1.1. 集合 $X$ に対して、 $X$ から $X$ への全単射全体の集合を

S_X=\operatorname{Sym}(X)

と書き、 $X$ の対称群 (symmetric group) という。積を写像の合成

\sigma\tau=\sigma\circ\tau,\qquad (\sigma\tau)(x)=\sigma(\tau(x))

によって定める。

命題 1.2. 任意の集合 $X$ に対して、 $S_X$ は写像の合成を積とする群である。単位元は恒等写像 $\operatorname{id}_X$ であり、各元の逆元はその逆写像である。

証明. $\sigma,\tau\in S_X$ を取る。§E1.1 命題 3.5 (3)により $\sigma\circ\tau$ も全単射であるから、 $S_X$ は積について閉じている。写像の合成の結合律§E1.1 命題 2.2により、この積は結合的である。恒等写像 $\operatorname{id}_X$ は全単射であり、任意の $\sigma\in S_X$ に対して $\operatorname{id}_X\circ\sigma=\sigma\circ\operatorname{id}_X=\sigma$ である。また、§E1.1 命題 3.8と§E1.1 系 3.10 (1)により、 $\sigma$ の逆写像 $\sigma^{-1}$ は全単射であり、

\sigma\circ\sigma^{-1}=\sigma^{-1}\circ\sigma=\operatorname{id}_X

を満たす。したがって $S_X$ は群である。▨

2 有限集合上の置換

定義 2.1. $X$ を有限集合とする。 $X$ から $X$ への全単射を $X$ の置換 (permutation) という。置換全体の集合を $\operatorname{Sym}(X)$ と書き、写像の合成を積とする。

$X=\{1,\ldots,n\}$ のとき、 $\operatorname{Sym}(X)$ を $S_n$ と書き、 $n$ 次対称群 (symmetric group of degree n) という。

命題 2.2. 有限集合 $X$ に対して、 $\operatorname{Sym}(X)$ は写像の合成に関して群である。さらに、 $|X|=n$ ならば

|\operatorname{Sym}(X)|=n!

である。

証明.命題 1.2により、 $\operatorname{Sym}(X)$ は群である。

$n=0$ のとき、空集合から空集合への写像は一つだけであり、 $0!=1$ と一致する。 $n\geq1$ のとき、 $X$ の元を一つの順序で並べる。第1の元の像には $n$ 通り、第2の元の像には残る $n-1$ 通りがある。同じ選択を続けると、全単射の個数は $n(n-1)\cdots1=n!$ である。▨

3 対称群の非可換性

例 3.1. $\alpha,\beta\in S_3$ を

\alpha(1)=2,\quad\alpha(2)=1,\quad\alpha(3)=3, \qquad \beta(1)=1,\quad\beta(2)=3,\quad\beta(3)=2

によって定める。積を右側から作用させると

(\alpha\beta)(1)=2,\qquad (\beta\alpha)(1)=3

である。したがって $\alpha\beta\neq\beta\alpha$ であり、 $S_3$ は非可換群である。

4 巡回置換と台

定義 4.1. $X$ の相異なる元 $a_1,\ldots,a_r$ に対して、 $r\geq2$ とする。

a_1\mapsto a_2\mapsto\cdots\mapsto a_r\mapsto a_1

と移し、 $a_1,\ldots,a_r$ 以外の元を固定する置換を

(a_1\,a_2\,\cdots\,a_r)

と書き、長さ $r$ の巡回置換 (cycle) という。

置換 $\sigma\in\operatorname{Sym}(X)$ の台 (support of a permutation) を

\operatorname{supp}(\sigma)=\{x\in X\mid \sigma(x)\neq x\}

によって定める。二つの置換の台が交わらないとき、その二つの置換は互いに素 (disjoint permutations) であるという。

巡回表示の開始点を取り替えても、表される置換は変わらない。例えば

(a_1\,a_2\,\cdots\,a_r) =(a_2\,\cdots\,a_r\,a_1)

である。一方、巡回する向きを逆にすると、表される置換はもとの置換の逆置換になる。

命題 4.2. 有限集合 $X$ 上の互いに素な置換 $\alpha,\beta$ に対して

\alpha\beta=\beta\alpha

が成り立つ。

証明. $x\in X$ を任意に取る。 $x\notin\operatorname{supp}(\alpha)\cup \operatorname{supp}(\beta)$ ならば、二つの積はいずれも $x$ を固定する。

$x\in\operatorname{supp}(\alpha)$ とする。台が交わらないため $\beta(x)=x$ である。また、 $\alpha$ は自身の台を自身へ移すので $\alpha(x)\in\operatorname{supp}(\alpha)$ であり、 $\beta(\alpha(x))=\alpha(x)$ である。したがって

(\alpha\beta)(x)=\alpha(x)=(\beta\alpha)(x)

となる。 $x\in\operatorname{supp}(\beta)$ の場合も $\alpha$ と $\beta$ を交換した同じ計算で等式を得る。すべての $x\in X$ で値が一致するため、 $\alpha\beta=\beta\alpha$ である。▨

5 互いに素な巡回置換への分解

定理 5.1. 有限集合 $X$ の任意の置換 $\sigma$ は、互いに素な長さ2以上の巡回置換の積として表される。恒等置換は空積によって表す。

この分解は、巡回因子を並べる順序と、各巡回表示における開始点の巡回移動を除いて一意である。

証明. $x,y\in X$ に対して、ある整数 $k$ が存在して $y=\sigma^k(x)$ となるとき $x\sim y$ と定める。 $x=\sigma^0(x)$ であるから反射律が成り立つ。 $y=\sigma^k(x)$ ならば $x=\sigma^{-k}(y)$ であるから対称律が成り立つ。 $y=\sigma^k(x)$ かつ $z=\sigma^\ell(y)$ ならば $z=\sigma^{k+\ell}(x)$ であるから推移律が成り立つ。したがって $\sim$ は同値関係であり、 $X$ を $\sigma$ の軌道へ分割する。

軌道 $O$ を一つ取り、 $a\in O$ とする。 $X$ は有限であるから、 $a,\sigma(a),\sigma^2(a),\ldots$ の中には同じ元が二度現れる。全単射 $\sigma$ の逆写像を用いると、ある正の整数 $r$ が存在して $\sigma^r(a)=a$ となる。そのような $r$ の最小値を取れば

a,\sigma(a),\ldots,\sigma^{r-1}(a)

は相異なり、軌道 $O$ のすべての元を尽くす。 $r\geq2$ の軌道に対して

c_O=(a\,\sigma(a)\,\ldots\,\sigma^{r-1}(a))

と定める。この巡回表示は $a$ の選び方を変えても開始点が巡回移動するだけである。

相異なる軌道から得られる巡回置換の台は交わらない。非自明な軌道に対応する $c_O$ をすべて掛けると、各非自明な軌道上では $\sigma$ と同じ値を取り、一元だけの軌道上では $\sigma$ と積の双方がその元を固定する。したがって、その積は $\sigma$ に等しい。互いに素な置換は命題 4.2によって可換であるため、因子の順序は積を変えない。

$\sigma=c_1\cdots c_t$ が互いに素な長さ2以上の巡回置換の積であるとする。 $x\in\operatorname{supp}(\sigma)$ を取ると、 $x$ はただ一つの因子 $c_i$ の台に属する。他の因子は $c_i$ の台を各点ごとに固定するため、任意の整数 $k$ に対して

\sigma^k(x)=c_i^k(x)

が成り立つ。したがって $c_i$ の台は $x$ の $\sigma$ 軌道に一致し、その軌道上で $c_i$ は $\sigma$ と同じ作用をする。よって $c_i$ は

(x\,\sigma(x)\,\ldots\,\sigma^{r-1}(x))

に限られる。各因子は非自明な軌道と一対一に対応するため、別の分解との違いは因子の順序と各巡回表示の開始点だけである。▨

例 5.2. $\sigma\in S_7$ が

1\mapsto3\mapsto2\mapsto1,\qquad 4\mapsto7\mapsto4

と作用し、 $5,6$ を固定するとする。このとき

\sigma=(1\,3\,2)(4\,7)

である。二つの因子は互いに素であるため、順序を交換しても同じ置換を表す。固定点 $5,6$ は分解に書かない。

6 互換分解

定義 6.1. 長さ2の巡回置換 $(a\,b)$ を互換 (transposition) という。

定理 6.2. 有限集合上の任意の置換は、有限個の互換の積として表すことができる。

証明. 長さ $r\geq2$ の巡回置換について

(a_1\,a_2\,\cdots\,a_r) =(a_1\,a_r)(a_1\,a_{r-1})\cdots(a_1\,a_2)

\text{(6.2.1)}

が成り立つ。実際、右辺は $a_1$ を $a_2$ へ移し、 $2\leq j<r$ に対して $a_j$ を $a_{j+1}$ へ移し、 $a_r$ を $a_1$ へ移す。 $a_1,\ldots,a_r$ 以外の元はすべての因子によって固定されるため、右辺は左辺と一致する。

定理 5.1によって任意の置換は有限個の巡回置換の積であり、各巡回因子へ式 (6.2.1)を適用すれば互換の積を得る。恒等置換は互換を一つも含まない空積で表される。▨

互いに素でない巡回置換については、因子の順序を自由に交換することはできない。

例 6.3. $S_3$ の互換 $(1\,2)$ と $(2\,3)$ の台は元 $2$ を共有する。例 3.1の計算により、二つの互換は可換ではない。互いに素であるという仮定を命題 4.2から除くことはできない。

7 置換行列

命題 7.1. $n$ を正の整数とし、 $e_1,\ldots,e_n$ を $\R^n$ の標準基底とする。各 $\sigma\in S_n$ に対して

P_\sigma e_j=e_{\sigma(j)} \qquad(1\leq j\leq n)

を満たす行列 $P_\sigma$ を定める。このとき

\rho\colon S_n\longrightarrow\GL_n(\R), \qquad \sigma\longmapsto P_\sigma

は忠実な行列表示である。

証明. $P_{\sigma^{-1}}P_\sigma e_j=e_j$ がすべての標準基底ベクトルについて成り立つため、 $P_\sigma$ は可逆であり、 $P_\sigma^{-1}=P_{\sigma^{-1}}$ である。また、任意の $\sigma,\tau\in S_n$ に対して

P_\sigma P_\tau e_j =P_\sigma e_{\tau(j)} =e_{\sigma(\tau(j))} =P_{\sigma\tau}e_j

である。したがって $P_\sigma P_\tau=P_{\sigma\tau}$ であり、 $\rho$ は群準同型である。 $P_\sigma=I$ ならば、各 $j$ に対して $e_{\sigma(j)}=P_\sigma e_j=e_j$ であるから $\sigma(j)=j$ である。ゆえに $\sigma$ は恒等置換であり、 $\ker\rho$ は自明である。§E7.3 命題 2.2によって $\rho$ は単射である。▨

8 演習

問題 8.1.

$(1\,4\,3\,2)^{-1}$ を一つの巡回置換として表せ。
$\sigma=(1\,3\,5)(2\,4)$ と $\tau=(1\,2)$ に対して、 $\sigma\tau$ と $\tau\sigma$ の巡回分解を求めよ。
互いに素な巡回分解で固定点を長さ1の巡回置換として自由に挿入すると、一意性の主張をどのように変更する必要があるか説明せよ。

解答 (演習の要点).

(1)について、 $(1\,4\,3\,2)$ は $1\mapsto4$ 、 $4\mapsto3$ 、 $3\mapsto2$ 、 $2\mapsto1$ と移すので、その逆置換は $4\mapsto1$ 、 $3\mapsto4$ 、 $2\mapsto3$ 、 $1\mapsto2$ と移す。すなわち逆置換は $1\mapsto2\mapsto3\mapsto4\mapsto1$ と巡回し、

(1\,4\,3\,2)^{-1}=(1\,2\,3\,4)

である。

(2)について、 $(\sigma\tau)(x)=\sigma(\tau(x))$ である。 $\sigma$ は $1\mapsto3$ 、 $3\mapsto5$ 、 $5\mapsto1$ 、 $2\mapsto4$ 、 $4\mapsto2$ と移し、 $\tau$ は $1$ と $2$ を入れ替えて $3,4,5$ を固定する。したがって

(\sigma\tau)(1)=\sigma(2)=4,\quad(\sigma\tau)(4)=\sigma(4)=2,\quad(\sigma\tau)(2)=\sigma(1)=3,\quad(\sigma\tau)(3)=\sigma(3)=5,\quad(\sigma\tau)(5)=\sigma(5)=1

であり、 $\sigma\tau=(1\,4\,2\,3\,5)$ である。同様に

(\tau\sigma)(1)=\tau(3)=3,\quad(\tau\sigma)(3)=\tau(5)=5,\quad(\tau\sigma)(5)=\tau(1)=2,\quad(\tau\sigma)(2)=\tau(4)=4,\quad(\tau\sigma)(4)=\tau(2)=1

であり、 $\tau\sigma=(1\,3\,5\,2\,4)$ である。二つはともに長さ $5$ の巡回置換であるが、 $(\sigma\tau)(1)=4\ne3=(\tau\sigma)(1)$ であるから互いに異なる。

(3)について、 $a\in X$ に対して、恒等置換を長さ $1$ の巡回置換 $(a)$ と書き、その成分集合を $\{a\}$ とする。長さ $2$ 以上の巡回置換 $(a_1\,\cdots\,a_r)$ の成分集合は $\{a_1,\ldots,a_r\}$ とする。長さ $1$ の因子を自由に挿入してよいとすると、定理 5.1の一意性は成り立たない。たとえば $X=\{1,2,3,4\}$ では $(1\,2)=(1\,2)(3)=(1\,2)(3)(4)$ であり、因子の個数が異なる三つの表示がある。一意性の主張は次のように変更する必要がある。任意の置換 $\sigma$ は、成分集合が $X$ の分割をなす巡回置換（長さ $1$ のものを含む）の積として表され、そのような表示は因子の順序と各巡回表示の開始点を除いて一意である。存在は、定理 5.1の分解に、 $\sigma$ の各固定点 $a$ について $(a)$ を付け加えれば得られる。そのような表示を取り、 $a\in X$ を成分集合に含む因子を $c$ とする。成分集合は互いに交わらないので、 $c$ 以外の因子は $c$ の成分集合の元を固定し、 $\sigma$ は $c$ の成分集合の上で $c$ と一致する。したがって $c$ の成分集合は $\{\sigma^k(a)\mid k\in\Z\}$ 、すなわち $a$ の $\sigma$ による軌道であり、 $c=(a\,\sigma(a)\,\cdots\,\sigma^{r-1}(a))$ （ $r$ は軌道の元の個数）である。よって因子の成分集合は $\sigma$ の軌道の全体として定まり、各因子は開始点の取り方を除いて定まる。長さ $1$ の因子はちょうど $\sigma$ の固定点に対応する。▨

§E7.4対称群