대수학에서 치환과 순환(Permutation and cycle in Algebra)

군론(Group Theory)은 대수학의 진가를 보여주는 추상적 논리로 설계된 과목이라 보아도 이견의 여지가 없을 겁니다. 수학과에서 주 재료로 요리를 담당하고 있지만 물리학, 화학에서도 군론은 상당히 중요합니다. 왜냐면 고학년 과목인 양자역학에서 군론의 힘을 빌려야 하기 때문입니다. 심지어 아예 따로 물리학에서 필요한 군론을 다루는 교재나 분야도 있습니다. 그러나 굳이 거기까지 올라가지 않더라도 때에 따라선 지금 이 포스팅의 목적이기도 한 선형대수학을 할 때 마주하기도 합니다. 벡터공간이나, 행렬식을 말하고자 할 때도 간단하지만 군의 개념이 필요합니다.

 

군 이론의 군들 중 우선적으로 무게를 두고 학습하는 군이 바로 대칭군입니다. 대칭군은 의외로 심플한데, 그저 일대일 함수들을 원소로 갖는 집합이기 때문입니다. 그런데 대칭군을 이해하기 위해선 '치환'을 알아야 하고, 이 치환은 군론 전반에 걸쳐 지속적으로 등장합니다.

---

1. 치환(Permutation)

 

정의($A.A$) 1-1) 치환(Permutation)
집합 $X_n=\left \{ 1,2,\cdots,n \right \}$ 에 대하여 $X_n$ 에서 $X_n $ 으로의 전단사함수(bijective function)^[각주:1] $\sigma : X\rightarrow X$ 를 '치환(Permutation)'이라 정의하고
$$\sigma =\begin{pmatrix}
1 & 2 &3  & \cdots & k & \cdots & n \\ 
\sigma(1) & \sigma(2) & \sigma(3) & \cdots & \sigma(k) & \cdots & \sigma(n)
\end{pmatrix}$$ 과 같이 나타낸다. 이때 $X=\left \{ 1,2,\cdots,n \right \}$ 에서의 모든 치환들의 집합을 $S_n$ 으로 나타내고 '차수가 $n$ 인 대칭군(symmetric group of degree $n$)'이라 부른다. 치환들의 개수는 $n(S_n)={}_nP_n=n!$ 이다.

 

일단 대칭군이 무엇인지는 다음 글에서 자세히 다룹니다. 지금은 위에서 적은 대칭군의 정의만 간단히 기억하시고, 치환의 정의와 기본 개념에 주목해 주시기 바랍니다.

 

치환의 개념을 보면 여기서 치환은 치환적분을 할 때의 치환(Substitution)과는 전혀 다른 것으로, 고등학교 확률과 통계에서 배우는 순열(Permutation)과 같은 의미입니다. 영어 단어도 똑같죠? 순열이라 하면 주어진 개체들을 뽑아서 배열, 즉 순서를 고려하여 나열하는 일을 말합니다. 그래서 이는 곧 전단사함수, 그러니까 일대일대응(One-to-one function)이라 볼 수 있습니다. 어떤 집합 $X_n$에서 자기 자신으로 가는 함수인 것이죠.

 

치환은 위와 같이 행렬로 표기합니다. 1행에는 치환 조작 전이라고 볼 수 있는 $X_n$의 원소들을 순서대로 쓰면 되는 것이고, 2행에는 그 치환에 의해 순서가 바뀌어진 $X_n$의 원소들을 쓰면 됩니다. 1행이 정의역의 원소, 2행이 치역의 원소들로 이루어진 것이라 보면 됩니다. 이렇게 치환을 2행으로 나타내면 '2행 표기법(Two-line notation)'이라 합니다. 그런데 어차피 첫 줄에는 $X_n$의 원소가 순서대로 들어가니까 굳이 쓰고 싶지 않아서 아랫줄만 쓰는 경우도 있습니다. 이러면 '1행 표기법(One-Line notation)'이라 합니다. 몇가지 종류의 치환은 1행 표기법으로만 쓴다는 것을 곧 알게 될 것입니다.

 

또 마지막 줄을 보면, 치환의 특성상 순열의 개념이기 때문에 치환의 총 개수는 항상 원소의 개수에 의해 결정된다는 내용이 들어가 있습니다. $1$부터 $n$까지의 원소들을 무작위로 나열하는 총 가짓수는 $n!$이므로, 치환의 개수도 이와 동일한 것입니다. 

 

 

정의($A.A$) 1-2) 항등치환과 역치환
$X_n=\left \{ 1,2,\cdots,n \right \}$ 의 각 원소들이 자기 자신으로 가는 치환
$$\sigma =\begin{pmatrix}
1 & 2 &3  & \cdots & k & \cdots & n \\ 
1 & 2 & 3 & \cdots & k & \cdots &  n
\end{pmatrix}$$ 을 '항등치환(Identity permutation)'이라 하고 '$\varepsilon$'로 표기한다. 그러면 모든 $\sigma \in S_n$에 대하여 $\sigma \circ \varepsilon=\varepsilon\circ \sigma=\sigma$ 가 성립한다.
더불어 $\sigma$ 는 전단사함수이므로 역함수를 갖고 그 역함수를 '역치환(Inverse permutation)'이라 하며 $\sigma^{-1}$ 로 나타낸다.

 

치환과 대칭군의 개념을 생각하면 항등치환과 역치환이 반드시 존재한다는 사실을 알 수 있습니다. 이는 치환들의 모임인 $S_n$ 은 항등원과 역원을 갖는다는 의미입니다. 따라서 결합법칙만 만족함을 보이면 간단히 이것이 군임을 알 수 있습니다. 결합법칙이 만족함을 어떻게 보일 수 있을까요? 치환은 일대일대응인 함수고, 기본적으로 함수의 합성 연산은 결합법칙을 만족하지요.^[각주:2]

---

예제 1) $S_1$과 $S_2$의 치환을 모두 구하여라.

 

각각 $2!$, $3!$개씩 존재할 것입니다. $S_2$의 모든 치환은

 

$$\begin{pmatrix}
1 &2 \\ 
1 &2 
\end{pmatrix}\;\;,\;\;\begin{pmatrix}
1 &2 \\ 
2 &1 
\end{pmatrix}$$

이고, $S_3$의 모든 치환은

$$\begin{pmatrix}
1 & 2 &3 \\ 
1 &2  &3
\end{pmatrix}\;\;,\;\;\begin{pmatrix}
1 & 2 &3 \\ 
2 &1  &3
\end{pmatrix}\;\;,\;\;\begin{pmatrix}
1 & 2 &3 \\ 
3 &2  &1
\end{pmatrix}
\;\;,\;\;
\begin{pmatrix}
1 & 2 &3 \\ 
1 &3  &2
\end{pmatrix}\;\;,\;\;\begin{pmatrix}
1 & 2 &3 \\ 
2 &3  &1
\end{pmatrix}\;\;,\;\;\begin{pmatrix}
1 & 2 &3 \\ 
3 &1  &2
\end{pmatrix}$$

---

2. 순환

 

1) 정의

 

정의($A.A$) 1-3) 순환(Cycles)
집합 $X-n=\left \{ 1,2,\cdots ,n \right \}=\left \{ a_1,a_2,\cdots ,a_n \right \}$ 라 하자. 이 때 만약 $S_n$의 치환 $\sigma$가
$$a_1\rightarrow a_2\;,\; a_2\rightarrow a_3\;, \;\cdots \;,\; a_{k-1}\rightarrow a_k\;,\;a_k\rightarrow a_1$$ 으로 $X_n$ 의 원소들에 대응되는 함수 구조를 이룰 때,
$$\sigma = \begin{pmatrix} 
a_1 &a_2  &\cdots  & a_k 
\end{pmatrix}$$ 로 나타내고 이것을 '길이가 $k$ 인 순환(Cycle of length $k$)' 또는 '$k$ 순환($k$-cycle)' 이라 한다.

정리($A.A$) 1.1)
$\sigma$ 를 $k$-순환이라 하자. 그러면 $\sigma^{-1}$ 또한 $k$-순환이다. 구체적으로 말하자면 $\sigma = \begin{pmatrix}
a_1 & a_2 &\cdots   & a_{k-1} & a_k
\end{pmatrix}$ 일 때 $\sigma^{-1}\begin{pmatrix}
 a_k &  a_{k-1} & \cdots  & a_2 &a_1 
\end{pmatrix}$ 이다.

 

순환은 말그대로 원소들이 서로를 도는 구조라는 것입니다.

 

 

[그림 1] 순환의 구조

 

 

---

예제 3) $\sigma=\begin{pmatrix}
1 &2  &3  &4  &5  &6 \\ 
1 &3  &6  &4  &2  &5 
\end{pmatrix}$ 은 순환인가? 

 

1과 4는 자기 자신으로 가니까 숫자가 바뀔 일이 없는데, 나머지 2,3,5,6의 경우 $2\rightarrow 3 \rightarrow 6 \rightarrow 5 \rightarrow 2\;\;\cdots$ 으로 계속 맞물리며 반복됩니다. 네개의 원소가 돌아가니 4-순환(4-cycle)에 해당하고, 

$$\sigma =\begin{pmatrix}
2 & 3 &  6& 5
\end{pmatrix}=\begin{pmatrix}
3 & 6 &  5& 2
\end{pmatrix}=\begin{pmatrix}
6 & 5 &  2& 3
\end{pmatrix}=\begin{pmatrix}
5 & 2 &  3& 6
\end{pmatrix}$$

으로 총 4개의 표기법이 존재합니다.

 

[그림 2] $S_8$의 치환 중 하나.

 

2) 순환을 이용한 합성의 계산

 

치환의 합성은 합성함수인데, 치환 표기법에서는 종종 합성 기호 $\circ$ 을 생략해서 나타냅니다. $S_4$의 두 치환

$$\sigma =\begin{pmatrix}
1 &2  &3  &4 \\ 
1 &4  &2  &3 
\end{pmatrix}\;,\;\tau =\begin{pmatrix}
1 & 2 & 3 &4 \\ 
 2& 4 &1  &3 
\end{pmatrix}$$

에 대한 합성 $\sigma\tau$ 는 

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

로 계산됩니다.

 

치환의 합성 계산은 처음에 배울때 생소하게 느껴질 것입니다. 함수의 합성에서 $h(x)=\left ( f\circ g \right )(x)=f(g(x))$ 를 따질 때 정의역 동그라미 세 개를 그리는 경우, 먼저가는 함수가 $g(x)$고 나중에 가는 함수가 $f(x)$인 것처럼, 치환 $\sigma\tau$ 에서도 $\tau$ 를 먼저 계산하고 $\sigma$를 계산합니다. 위의 예에서 1을 예로 들면, $\tau$에서 $1\rightarrow 2$로 가고 $\sigma$에서 $2\rightarrow 4$로 가니까, $\sigma\tau$에서 $1\rightarrow 4$로 가는 것입니다. 그런데

$$\sigma =\begin{pmatrix}
2 & 4 & 3
\end{pmatrix}\;,\;\tau=\begin{pmatrix}
1 & 2 &  4& 3
\end{pmatrix}$$

이기 때문에 표기 역시

$$\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}$$

 

으로 할 수 있습니다. 즉 순환의 합성은 순환으로 나타낼 수 있다는 말입니다.

 

 

 

 

1. 전단사함수란 일대일대응 함수를 말합니다. [본문으로]
2. 물론 사실 합성함수가 임의의 두 함수에 대해 존재한다고 단정할 수는 없습니다. 하지만, 두 함수가 일대일대응이라면, 반드시 두 함수를 합성시킬 수 있습니다. 왜 그런지는 합성함수(집합론에서의)의 정의를 떠올려 보시기 바랍니다. [본문으로]