대수학에서 순환의 서로소의 뜻과 교환법칙(Commutative laws in Mutually disjoint of Cycle)

순환에서는 서로소라는 개념이 중요할 뿐만 아니라 서로소인 순환들에 대해서 성립하는 규칙들이 있습니다. 이를 소개하고 몇가지 증명을 해보려 합니다. 여기서 서로소는 정수론에서 두 소수가 서로소(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$

 

증명의 원리는 순환을 하나씩 발견한다는 개념에 착안합니다. 첫 순환을 돌았을 때 비순환원소가 자기 자신으로 가지 않는다면 또 다른 순환을 찾는 것이지요. 이러한 방식을 반복하여 순환들의 곱으로 나타낼 수 있다는 것입니다.

 

 

 

 

[참고문헌]

선형대수학, 청문각, 강경태 및 송석준 지음