순환에서는 서로소라는 개념이 중요할 뿐만 아니라 서로소인 순환들에 대해서 성립하는 규칙들이 있습니다. 이를 소개하고 몇가지 증명을 해보려 합니다. 여기서 서로소는 정수론에서 두 소수가 서로소(relatively prime)라는 의미보다는 집합론에서의 두 집합의 서로소(mutally disjoint)의 개념에 가깝습니다.
1. 서로소(Mutually disjoint)
1) 정의
정의($A.A$) 1-6) 순환의 서로소
$S_n$의 두 순환 $\sigma =\begin{pmatrix}
a_1 &a_2 &\cdots &a_k
\end{pmatrix}\;,\; \tau=\begin{pmatrix}
b_1 &b_2 &\cdots &b_r
\end{pmatrix}$ 가 서로 공통된 성분을 갖지 않아 $\left \{ a_1,\cdots ,a_k \right \}\cap \left \{ b_1,\cdots ,b_r \right \}=\emptyset$ 이면 $\sigma , \tau$ 는 '서로소(Mutally disjoint)'라 한다.
두 순환에 있어서 순환에 참가하는 원소들이 중복되면 안된다는 것입니다. 예를 들어서 $S_6$의 순환 $(2\;,4)$와 $(3\;6\;5\;1)$ 은 서로소이지만, $(2\;1\;3)$ 과 $(3\;1\;4\;2)$는 서로소가 아닙니다.
2) 서로소와 교환법칙
정리($A.A$) 1.2) 두 순환이 서로소이면 교환법칙이 성립한다.
$S_n$의 두 순환 $\sigma ,\tau$가 서로소이면 $\sigma\tau=\tau\sigma$ 이다.
증명) $S_n$의 두 순환을 $\sigma =\begin{pmatrix} a_1 &a_2 &\cdots &a_k \end{pmatrix}\;\;,\;\; \tau=\begin{pmatrix} b_1 &b_2 &\cdots &b_r \end{pmatrix}$ 라 하고 서로소라 가정하자. 즉 $\left \{ a_1,\cdots ,a_k \right \}\cap \left \{ b_1,\cdots ,b_r \right \}=\emptyset$ 이다. 그러면 모든 $x\in \left \{ 1,\cdots ,n \right \}$ 에 대해 $$(\sigma\tau)(x)=(\tau\sigma)(x)$$ 를 보이면 된다. 이 때 $x$는 반드시 다음 세가지 경우 중 하나에 속한다.
i) $x\in \left \{ a_1,\cdots ,a_k \right \}$ 이 경우 $x=a_i\;\;\left ( 1\leq i\leq k \right )$ 라 하자. 그러면 $\sigma (a_i)=a_j\;\;\left ( i\neq j\Rightarrow a_i\neq a_j \right )$ 이고, 이 $a_j$는 $\tau$에선 $a_j\rightarrow a_j$ 이므로(서로소니까) $\tau(x)=x$가 성립한다. 그러므로 $(\sigma\tau)(x)=\sigma(\tau(x))=\sigma(x)=\tau(\sigma(x))=(\tau\sigma)(x)$
ii) $x\in \left \{ b_1,\cdots ,b_k \right \}$ i)과 비슷하게, $x\in \left \{ b_1,\cdots ,b_k \right \}$ 이면 $\tau(x)=\left \{ b_1,\cdots,b_r \right \}\; , \; \sigma(x)=x$가 되어 $(\sigma\tau)(x)=\sigma(\tau(x))=\sigma(\tau(x))=\tau(\sigma(x))=(\tau\sigma)(x)$ iii) $x\notin \left \{ a_1,\cdots ,a_k,b_1,\cdots,b_r \right \}$ $\sigma(x)=x=\tau(x)$ 이므로 $(\sigma\tau)(x)=(\tau\sigma)(x)$ 가 바로 성립한다. $_\blacksquare$
서로소인 순환들에 대하여 교환법칙이 성립한다는 뜻입니다. 예제 하나로 이것이 성립하는지 한번만이라도 확인을 하고 넘어가 봅시다.
예제 1) 이전 포스팅에서 다루었던
$$\sigma =\begin{pmatrix}
2 & 4 & 3
\end{pmatrix}\;,\;\tau=\begin{pmatrix}
1 & 2 & 4& 3
\end{pmatrix}$$
에 대하여 교환법칙이 성립하는지 살펴보아라.
sol)
$$\sigma\tau =\begin{pmatrix}
2 & 4 & 3
\end{pmatrix}\begin{pmatrix}
1 & 2 & 4& 3
\end{pmatrix}=\begin{pmatrix}
1 &4 &2 &3
\end{pmatrix}$$
반면에,
$$\tau\sigma = \begin{pmatrix}
1 & 2 & 3 &4 \\
2& 4 &1 &3
\end{pmatrix}\begin{pmatrix}
1 &2 &3 &4 \\
1 &4 &2 &3
\end{pmatrix}=\begin{pmatrix}
1 & 2 & 3 &4 \\
2& 3 &4 &1
\end{pmatrix}=\begin{pmatrix}
2 &3 &4 & 1
\end{pmatrix}$$
그러므로 $\sigma\tau \neq \tau\sigma$ 입니다.
직관적으로 생각하면 함수의 합성은 순서가 중요하여 일반적으로 $\left ( f\circ g \right )=f(g(x))\neq \left ( g\circ f \right )=g(f(x))$ 가 성립하기 때문에, 치환에서도 교환법칙이 꼭 성립하라는 보장은 없을 것이라 예상할 수 있습니다. 이제 증명을 해봅시다.
증명) $S_n$의 두 순환을 $\sigma =\begin{pmatrix} a_1 &a_2 &\cdots &a_k \end{pmatrix}\;\;,\;\; \tau=\begin{pmatrix} b_1 &b_2 &\cdots &b_r \end{pmatrix}$ 라 하고 서로소라 가정하자. 즉 $\left \{ a_1,\cdots ,a_k \right \}\cap \left \{ b_1,\cdots ,b_r \right \}=\emptyset$ 이다. 그러면 모든 $x\in \left \{ 1,\cdots ,n \right \}$ 에 대해
$$(\sigma\tau)(x)=(\tau\sigma)(x)$$
를 보이면 된다. 이 때 $x$는 반드시 다음 세가지 경우 중 하나에 속한다.
i) $x\in \left \{ a_1,\cdots ,a_k \right \}$
이 경우 $x=a_i\;\;\left ( 1\leq i\leq k \right )$ 라 하자. 그러면 $\sigma (a_i)=a_j\;\;\left ( i\neq j\Rightarrow a_i\neq a_j \right )$ 이고, 이 $a_j$는 $\tau$에선 $a_j\rightarrow a_j$ 이므로(서로소니까) $\tau(x)=x$가 성립한다. 그러므로 $(\sigma\tau)(x)=\sigma(\tau(x))=\sigma(x)=\tau(\sigma(x))=(\tau\sigma)(x)$
ii) $x\in \left \{ b_1,\cdots ,b_k \right \}$
i)과 비슷하게, $x\in \left \{ b_1,\cdots ,b_k \right \}$ 이면 $\tau(x)=\left \{ b_1,\cdots,b_r \right \}\; , \; \sigma(x)=x$가 되어 $(\sigma\tau)(x)=\sigma(\tau(x))=\sigma(\tau(x))=\tau(\sigma(x))=(\tau\sigma)(x)$
iii) $x\notin \left \{ a_1,\cdots ,a_k,b_1,\cdots,b_r \right \}$
$\sigma(x)=x=\tau(x)$ 이므로 $(\sigma\tau)(x)=(\tau\sigma)(x)$ 가 바로 성립한다. $_\blacksquare$
정리($A.A$) 1.3)
$S_n$에서 모든 치환 $\sigma$는 서로소인 순환들의 곱으로 나타낼 수 있다.
증명) $\sigma$가 항등치환이면 증명할 것이 없으니 항등치환이 아니라고 하자. 그러면 $\left \{ 1,\cdots ,n \right \}$ 에서 $\sigma(x)\neq x$인 첫 원소 $a_1$이 존재하는데, $\sigma(a_1)=a_2$ 라 두자. (단, $a_1\neq a_2$) $\sigma$가 전단사함수이기 때문에 $\left \{ 1,\cdots ,n \right \}$ 의 서로 다른 $a_1,a_2,\cdots a_k$ 가 존재하여 $\sigma(a_1)=a_2\;,\;\sigma(a_2)=a_3, \;\cdots\;, \sigma(a_k)=a_1$ 을 만족한다. 여기서 $\sigma_1=\begin{pmatrix} a_1 &a_2 &\cdots &a_k \end{pmatrix}$ 라 두면, 이에 포함되지 않는 비순환원소 $x\notin \left\{ a_1,\,a_2\,\cdots \,a_n \right\}$ 에 대하여 $\sigma(x)=x$ 이면 $\sigma=\sigma_1$ 이므로 이 순환이 유일해 더 이상 증명할 것이 없다.
$\sigma\neq \sigma_1$ 이면 $\left \{ 1,\cdots ,n \right \}-\left \{ a_1,\cdots ,a_k \right \}$ 에서 $\sigma(x)\neq x$ 인 첫 원소를 $b_1$이라 하고, 동일한 과정을 반복하여 $\left \{ 1,\cdots ,n \right \}-\left \{ a_1,\cdots ,a_k \right \}$ 에 서로 다른 $b_1,\cdots ,b_k$ 가 존재하여 두번째 순환 $\sigma_2=\begin{pmatrix}
b_1 &b_2 &\cdots &b_r
\end{pmatrix}$ 을 얻는다. 물론 이 때 두 순환은 $\left \{ a_1,a_2,\cdots ,a_k \right \}\cap \left \{ b_1,b_2,\cdots ,b_k \right \}=\emptyset $ 으로 서로소이다.
이후에도 $\left \{ 1,\cdots ,n \right \}$ 는 유한집합이므로 동일한 과정을 통해 서로소인 순환 $\sigma_1,\sigma_2,\cdots ,\sigma_t$ 가 존재하여
$$\sigma=\sigma_1\,\sigma_2\,\cdots \,\sigma_t$$ $_\blacksquare$
증명의 원리는 순환을 하나씩 발견한다는 개념에 착안합니다. 첫 순환을 돌았을 때 비순환원소가 자기 자신으로 가지 않는다면 또 다른 순환을 찾는 것이지요. 이러한 방식을 반복하여 순환들의 곱으로 나타낼 수 있다는 것입니다.
[참고문헌]
선형대수학, 청문각, 강경태 및 송석준 지음
'대수학(Abstract Algebra) > 순열, 치환' 카테고리의 다른 글
부호함수와 치환(Signum function with Permutation) (0) | 2020.12.08 |
---|---|
대수학에서 호환과 짝치환, 홀치환 (Transposition and even, odd permutation in Algebra) (2) | 2020.12.08 |
대칭군(The symmetric group) (0) | 2020.12.06 |
대수학에서 치환과 순환(Permutation and cycle in Algebra) (2) | 2020.12.03 |
연산과 군, 환, 체의 간단한 개념 (Basic concept of Binary operation, Group, Ring, and Field) (1) | 2020.12.03 |
댓글