대칭군(symmetric group)

수학의 구조를 연구하는 대수학(algebra)은 군에서 출발한다. 그 가운데 많이 활용되는 대칭군에 대해 정리하고자 한다. 먼저 동치관계를 정리하자.

정의 1.1.1집합 $A$ 위에 정의된 관계 $\sim$가 다음 세 조건을 만족하면 이 관계를 $A$ 위의 동치관계(equivalence relation)라고 한다.

$E_1 : a\sim a$

$E_2 : a\sim b \iff b\sim a$

$E_3 : a\sim b, \;\;b\sim c \iff a\sim c$

집합 $A$ 위에 동치관계 $\sim$가 잘 정의되었다면 $A$의 원소 $a,b$에 대하여 $a\sim b$ 일 때 $a$와 $b$는 서로 동치(equivalence)라고 한다. 또 $a$와 동치인 $A$의 원소 전체의 집합을 $a$에 의하여 결정된 동치류(equivalence class) 또는 $a$를 포함하는 동치류라 하고 이 집합을 $\overline {a}$로 적는다.

$$\overline {a}= \{ x \in A| x \sim a \} =\{ x \in A | a \sim x \}$$

정리 1.1.2 집합 $A$ 위에 동치관계  $\sim$가 잘 정의되어 있을 때,

1) $a\sim b \iff \overline{a}=\overline{b}$

2) $a\in \overline{b} \iff b\in \overline{a}\iff \overline{a}=\overline{b}$

3) $\forall a\in A$에 대하여, $a\in \overline{a}$이다.

4) $\forall a, b \in A$에 대하여 $i) \;\;\overline{a} \cap \overline{b}=\phi \;\;\;ii)\;\;\overline{a}=\overline{b}$ 가운데 단 하나가 성립한다.

정의 1.1.3 $n \in  \mathbb{Z},\;\;n \geq 1$이라고 하자. 두 정수 $a,b \in \mathbb{Z}$에 대하여 $a-b$가 $n$의 배수일 때, $a$와 $b$는 법(modulus) $n$에 관하여 서로 합동(congruent)이라 하고 $a\equiv b\;\;(\mod\;\;n)$으로 적는다.

$$a \equiv b \;\;(\mod\;n) \iff n |(a-b)\iff a-b\in n\mathbb{Z}$$

합동관계는 정의 1.1.1을 만족하므로 동치관계이다.

정의 1.1.4 집합 $\mathbb{Z}$ 위의 합동관계 $a\equiv b(\mod n)$에 의해 정의되는 각 동치류를 법 $n$에 관한 $\mathbb{Z}$의 잉여류(residue class)라 하고, 정수 $a$에 의하여 결정된 잉여류를 $\overline{a}$로 나타낸다.

$$\overline{a}=\{x\in \mathbb{Z}|x\equiv a(\mod n)\}=\{a, a\pm n, a \pm 2n. \cdots \}$$

정의 1.1.5 양의 정수 $n$에 대하여, $n$보다 크지 않은 음이 아닌 정수 전체의 집합을 $\mathbb{Z}_n$으로 나타낸다.

$$\mathbb{Z}_n =\{1,2,3,\cdots, n-1\}$$

또 법 $n$에 대한 $\mathbb{Z}$의 잉여류 전체의 집합을 $\mathbb{\overline{Z}}_n$로 나타낸다.

$$\mathbb{\overline{Z}}_n=\{\overline{a}|a \in \mathbb{Z} \}= \{ \overline{1},\overline{2}, \cdots, \overline{n-1}\}$$

정의 1.1.6 집합 $\mathbb{Z}_n =\{1,2,3,\cdots, n-1\}$의 원소 가운데 $n$과 서로 소인 정수 전체의 집합을 $\mathbb{Z}_n ^*$로 나타내고, 집합 $\mathbb{Z}_n ^*$의 원소의 개수를 $\varphi(n)$로 나타낸다.

$$\mathbb{Z}_n ^* =\{a \in \mathbb{Z}_n |(a,n)=1\},\;\;\;\;\varphi(n)=|\mathbb{Z}_n ^*|$$

또, 함수 $\varphi :P\rightarrow \mathbb{Z}, n \mapsto \varphi(n)$를 오일러의 $\varphi$함수라고 한다.

정의 1.1.7 집합 $G(\not= \phi)$ 위에 연산 $ \circ$이 잘 정의되어 있고 아래 공리를 만족하면 $(G,\circ)$를 군(Group)이라고 한다.

$$\forall a,b \in G\Rightarrow a\circ b \in G$$

1) $\forall a,b,c \in G$에 대하여, $(a\circ b)\circ c =a \circ (b \circ c)$

2) $\forall a \in G$에 대하여 $a \circ e =e \circ a=a$인 $\exists e \in G$가 존재한다.

    이 원소 $e$를 $G$의 연산 $\circ$에 관한 항등원(identity)이라고 한다.

3) $\forall a \in G$에 대하여 $a\circ x=x\circ a=e$인 원소 $x \in G$가 존재한다.

   이 원소 $x$를 $a$의 연산 $\circ$에 관한 역원이라 하고 $a^{-1}$로 적는다.

아래 교환법칙까지 성립하면 아벨군(abelian group) 또는 가환군(commutative group)이라고 한다.

4) $\forall a,b \in G$에 대하여, $a\circ b=b \circ a$

정의 1.1.8 집합 $X$에서 $X$ 자신 위로의 일대일 대응 $\sigma : X\rightarrow X$를 $X$ 위의 치환(permutation)이라고 한다. 또 집합 $X$ 위의 치환 전체의 집합을 $S(X)$로 적는다. 집합 $S(X)$는두 치환의 합성사상 $\circ$에 대하여 군을 이룬다. 군 $(S(X),\circ)$를 $X$ 위의 대칭군(symmetric group)이라고 한다.

집합 $X=\{x_1 ,x_2, \cdots,x_n \}$일 때, 치환 $\sigma : X\rightarrow X$를 $$\sigma=\pmatrix{x_1&x_2&\cdots &x_n\\\sigma(x_1)&\sigma(x_2)&\cdots&\sigma(x_n)}$$으로 나타내면 편리하다. 특히 집합 $X_n =\{1,2,\cdots,n\}$ 위의 치환  $\sigma : X_n \rightarrow X_n$를 $$\sigma=\pmatrix{1&2&\cdots &n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)}$$으로 나타낼 때 2행은 $1,2,\cdots,n$의 순열이다. $$\sigma^{-1}=\pmatrix{\sigma(1)&\sigma(2)&\cdots&\sigma(n)\\1&2&\cdots &n}$$이다.

정의 1.1.9 집합 $X_n =\{1,2,\cdots,n\}$ 위의 치환 전체의 집합 $S(X_n)$을 $S_n$으로 나타내고, 대칭군 $(S_n , \circ)$를 $n$차 대칭군이라고 한다. $|S_n|=n!$

 

치환을 표현하는 방법은 여러가지가 있는데 여기선 순환치환의 곱으로 나타내는 방법을 쓰기로 하자.

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

보기 대칭군 $S_3=\{1,\;\;(1\;2\;3),\;\;(1\;3\;2),\;\;(1\;2),\;\;(1\;3),\;\;(2\;3)\}$

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

$(1\;2)^{-1}=(1\;2)\quad(1\;3)^{-1}=(1\;3)\quad (2\;3)^{-1}=(2\;3)$

$\sigma=(1\;2\;3), \quad \tau=(1\;2)$에 대하여

$\sigma \circ \tau=(1\;2\;3) \circ (1\;2)=(1\;3),\quad\tau\circ\sigma=(1\;2) \circ (1\;2\;3)=(2\;3)$이므로

$\sigma \circ \tau \not=\tau\circ\sigma$이다. 따라서 아벨군이 아니다.

대칭군 $S_n$에서 두 순환치환 $\sigma=\pmatrix{i_1&i_2&\cdots&i_r},\;\;\tau=\pmatrix{j_1&j_2&\cdots&j_s}$에 공통문자가 없는 경우에 $\sigma \circ \tau =\tau\circ\sigma$이다.

치환 $$\sigma=\pmatrix{1&2&3&4&5&6\\4&6&2&1&5&3}\in S_6$$에 대하여

$$1\rightarrow4\rightarrow1;\quad 2\rightarrow 6\rightarrow 3 \rightarrow 2;\quad5\rightarrow5$$

이므로, $\sigma$에 의헤 세 부분집합 $\{1,4\},\{2,6,3\},\{5\}$로 분할되고 또 $\sigma$는 각 부분집합에 순환치환 $(1\;4),\;\;(2\;6\;3),\;\;(5)$를 유도한다. 이런 의미에서 $\sigma$를

$$(1\;4)\circ(2\;6\;3),\quad (1\;4)\circ(2\;6\;3)\circ(5),\quad (5)\circ(1\;4)\circ(2\;6\;3)$$

과 같이 나타낸다.

일반적으로, $n\geq2$일 때 임의의 치환 $\sigma \in S_n$는 다음과 같이 공통문자가 들어 있지 않은 순환치환의 곱으로 나타내어진다.

$$\sigma=\pmatrix{i_1&i_2&\cdots&i_r}\circ\pmatrix{j_1&j_2&\cdots&j_s}\circ\cdots\circ\pmatrix{l_1&l_2&\cdots&l_t}$$

$$1\leq r \leq s \leq\cdots \leq t,\quad r+s+\cdots+t=n$$

이러한 분해를 치환 $\sigma$의 표준분해(standard decomposition)라 하고, $\sigma$를 $\{r,s,\cdots,t\}$형 치환이라고 한다. 

정리 1.1.10 $n\geq2$일 떄, 대칭군 $S_n$에 대하여 다음이 성립한다.

1) $\forall \sigma \in S_n$는 유한 개 순환치환의 곱으로 나타내어진다.

2) $r$항 순환치환  $\pmatrix{i_1&i_2&\cdots&i_r}$는 $r-1$개 호환의 곱으로 나타내어진다.

$$\pmatrix{i_1&i_2&\cdots&i_r}=\pmatrix{i_1&i_r}\circ\cdots\circ\pmatrix{i_1&i_3}\circ\pmatrix{i_1&i_2}$$

3) $\forall \sigma \in S_n$는 유한 개 호환의 곱으로 나타내어진다.

치환 $\sigma\in S_n$의 표준분해가

$$\sigma=\pmatrix{i_1&i_2&\cdots&i_r}\circ\pmatrix{j_1&j_2&\cdots&j_s}\circ\cdots\circ\pmatrix{l_1&l_2&\cdots&l_t}$$

일 때

$$N(\sigma)=(r-1)+(s-1)+\cdots+(t-1)$$

이라고 하면, $N(\sigma)$는 $\sigma$에 의해 결정되는 정수이고 $\sigma$는 $N(\sigma)$개 호환의 곱으로 나타내어진다. 일반적으로 $\sigma$를 표준분해하는 방법은 여러 가지가 있으나, 이때 나타나는 호환의 개수가 짝수인지 홀수인지는 항상 일정하다.

$$(a\;\;b)\circ \pmatrix{a&c_1&\cdots&c_n&b&d_1&\cdots&d_n}=\pmatrix{a&c_1&\cdots&c_n}\circ\pmatrix{b&d_1&\cdots&d_n}$$

$$(a\;\;b)\circ\pmatrix{a&c_1&\cdots&c_n}\circ\pmatrix{b&d_1&\cdots&d_n}=\pmatrix{a&c_1&\cdots&c_n&b&d_1&\cdots&d_n}$$

따라서, $\sigma$의 표준분해에서 $a,b$가 동일한 순환치환 안에 들어 있으면 $N((a\;\;b)\circ\sigma)=N(\sigma)-1$이고 $a,b$가 서로 다른 순환치환 안에 들어 있으면 $N((a\;\;b)\circ\sigma)=N(\sigma)+1$이다. 즉, $N((a\;\;b)\circ\sigma)=N(\sigma)\pm1$이다. 이제 치환 $\sigma$가 $\sigma=(a_1\;\;b_1)\circ(a_2\;\;b_2)\circ\cdots\circ(a_m\;\;b_m)$과 같이 $m$개의 호환의 곱으로 분해되어 있다고 하자. 이때, $(a_i\;\;b_i)^2 =1$이므로

$$(a_1\;\;b_1)\circ(a_2\;\;b_2)\circ\cdots\circ(a_m\;\;b_m)\circ\sigma=1$$

이므로 위의 결과에 의하여

$$N(\sigma)\pm1 \pm 1\cdots \pm 1=N(1)=0\quad\quad(\pm 1은 \;\;m개)$$

이 등식에 있는 $m$개의 $\pm1$ 중에서 $+1$이 $m_1$개, $-1$이 $m_2$개 있으면 $N(\sigma)=m_1 -m_2,\;\;m=m_1 +m_2$이므로 $N(\sigma)=m-2m_2$이다. 따라서, $N(\sigma)$가 짝수이면 $m$도 짝수이고 $N(\sigma)$가 홀수이면 $m$도 홀수이다. 그러므로, $\sigma$를 호환의 곱으로 분해할 때 나타나는 호환의 개수 $m$이 짝수인지 홀수인지는 분해하는 방법에 관계없이 일정하다.

치환 $\sigma\in S_n$가 짝수개의 호환의 곱으로 나타내어질 때 $\sigma$를 짝수치환(even permutation), 홀수개의 호환의 곱으로 나타내어질 때는 홀수치환(odd permutation)이라고 한다.

정리 1.1.11 $n\geq2$일 때, 대칭군 $(S_n,\circ)$에서 짝수치환 전체의 집합을 $A_n$으로 나타내면, 집합 $A_n$은 합성 연산 $\circ$에 관하여 군을 이루고 또한 $\displaystyle{|A_n|=\frac{|S_n|}{2}=\frac{n!}{2}}$이다.

 

 $S_3$의 곱셈표

 

$\circ$	1	(12) $\tau$	(23) $\tau\circ\sigma$	(123)  $\sigma$	(132)  $\sigma^2$	(13) $\sigma\circ\tau$
1	1	(12)	(23)	(123)	(132)	(13)
(12) $\tau$	(12)	1	(123)	(23)	(13)	(132)
(23) $\tau\circ\sigma$	(23)	(132)	1	(13)	(12)	(123)
(123) $\sigma$	(123)	(13)	(12)	(132)	1	(23)
(132) $\sigma^2$	(132)	(23)	(13)	1	(123)	(12)
(13) $\sigma\circ\tau$	(13)	(123)	(132)	(12)	(23)	1

 

 

$S_4$의 구조