9장 - 궤도, 순환, 그리고 교대군

이 장은 치환 이론을 두 방향으로 심화한다. 첫째, 순환(cycle)을 궤도(orbit) 자료로 해석한다. 둘째, 치환을 우(even)와 기(odd)의 두 부류로 나누어 교대군(alternating group)으로 이어지는 패리티(parity)를 도입한다. 핵심 개념은 패리티가 단순한 계산상의 우연이 아니라 **구조적 불변량(structural invariant)**이라는 점이다. 마지막에 가서 $A_n$은 표준 준동형사상 $\mathrm{sgn}:S_n\to {\mathbb{Z}}_2$의 핵(kernel)으로 등장하며, 이는 자명한 경우를 넘어서는 몫군(quotient group)의 첫 번째 자연스러운 예를 제공한다.

§9.1 치환의 궤도

정의 9.1

$\sigma$을 유한집합 $X$의 치환이라 하자. **$\sigma$ 아래 $x$의 궤도(orbit)**는 다음과 같다.

$X$이 유한이고 $\sigma$이 전단사이므로, 반복 적용은 결국 $x$로 되돌아와야 한다. 즉 ${\sigma }^k(x)=x$을 만족하는 가장 작은 양의 정수 $k$가 존재하며, 궤도는 $\{x,\sigma (x),\dots ,{\sigma }^{k-1}(x)\}$이다.

정리 9.2 (궤도는 집합을 분할한다)

$\sigma \in S_n$이라 하자. $\sigma$의 궤도들은 $\{1,2,\dots ,n\}$을 분할한다.

증명

궤도들이 공집합이 아니고, 그 합집합이 $\{1,\dots ,n\}$ 전체이며, 서로 다른 궤도들이 서로소임을 보여야 한다.

공집합이 아니고 덮음. 모든 원소 $x\in \{1,\dots ,n\}$는 ${\mathrm{Orb}}_{\sigma }(x)$에 속한다($n=0$을 취하라, 즉 ${\sigma }^0(x)=x$). 따라서 모든 원소는 적어도 하나의 궤도에 들어간다.

서로소이거나 같음. ${\mathrm{Orb}}_{\sigma }(x)\cap {\mathrm{Orb}}_{\sigma }(y)\ne \varnothing$이라 가정하자. 그러면 ${\sigma }^r(x)={\sigma }^s(y)$을 만족하는 정수 $r,s$가 존재한다. $\sigma$이 전단사이므로 $x={\sigma }^{s-r}(y)$이다. 따라서 임의의 $t$에 대해,

$${\sigma }^t(x)={\sigma }^{t+s-r}(y)\in {\mathrm{Orb}}_{\sigma }(y).$$

이는 ${\mathrm{Orb}}_{\sigma }(x)\subseteq {\mathrm{Orb}}_{\sigma }(y)$임을 보인다. 대칭적인 논증에 의해 ${\mathrm{Orb}}_{\sigma }(y)\subseteq {\mathrm{Orb}}_{\sigma }(x)$이다. 그러므로 두 궤도는 같다.

따라서 궤도들은 서로 같거나 서로소이며, 그 합집합은 $\{1,\dots ,n\}$이다. $■$

예. $\sigma =\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 3& 5& 1& 6& 2& 4\end{array}\right)\in S_6$이라 하자.

궤도를 추적하면:

• $1$에서 시작: $1\to 3\to 1$. 궤도: $\{1,3\}$.
• $2$에서 시작: $2\to 5\to 2$. 궤도: $\{2,5\}$.
• $4$에서 시작: $4\to 6\to 4$. 궤도: $\{4,6\}$.

분할: $\{1,3\}\bigsqcup \{2,5\}\bigsqcup \{4,6\}=\{1,2,3,4,5,6\}$. 확인 완료.

§9.2 순환 구조와 궤도

정리 9.3 (궤도는 순환이다)

$\sigma$의 비자명한 궤도들(크기 $\ge 2$인 것들)은 $\sigma$의 서로소 순환 분해(disjoint cycle decomposition)에 나타나는 순환들과 정확히 대응한다. 고정점(크기 $1$인 궤도)은 $1$-순환에 대응하며, 이는 관례상 생략한다.

증명

$O=\{x,\sigma (x),{\sigma }^2(x),\dots ,{\sigma }^{k-1}(x)\}$을 크기 $k$인 궤도라 하자. 그러면 $O$로 제한된 $\sigma$은 순환 $(x\sigma (x){\sigma }^2(x)\cdots {\sigma }^{k-1}(x))$으로 작용한다. 즉 각 원소를 다음 원소로 보내고, 마지막 원소는 $x$로 되돌린다.

역으로, $(a_1{a}_2\cdots a_k)$이 서로소 순환 분해에 나타나는 순환이면, $i<k$에 대해 $\sigma (a_i)=a_{i+1}$이고 $\sigma (a_k)=a_1$이므로, $\{a_1,\dots ,a_k\}$은 정확히 $a_1$의 궤도이다.

궤도들이 $\{1,\dots ,n\}$을 분할하고 서로소 순환들이 고정되지 않은 원소들을 분할하므로, 이 대응은 전단사이다. $■$

예 (계속). 위의 치환 $\sigma$은 궤도 $\{1,3\}$, $\{2,5\}$, $\{4,6\}$을 가진다. 서로소 순환 분해는 다음과 같다.

크기 $2$인 각 궤도는 $2$-순환을 준다. 궤도와 순환은 같은 정보를 담는다.

그림: 동일한 치환에 대한 궤도 분할과 서로소 순환 표기.

왼쪽의 각 궤도 고리는 오른쪽의 서로소 순환 하나가 된다. 이 정리는 새로운 자료를 더하는 것이 아니라, 순환 표기가 궤도 분할과 각 궤도 위에서의 $\sigma$의 작용을 함께 기록하는 압축된 방식일 뿐임을 말해준다.

§9.3 호환

정의 9.4

**호환(transposition)**은 $2$-순환 $(ab)$로서, $a$와 $b$을 맞바꾸고 나머지는 모두 고정한다.

정리 9.5 (호환 분해)

모든 치환 $\sigma \in S_n$는 호환들의 곱으로 쓸 수 있다.

증명

서로소 순환 분해 정리(8장)에 의해 모든 치환은 서로소 순환들의 곱이다. 따라서 각 $k$-순환을 호환들의 곱으로 쓰면 충분하다.

$$(a_1{a}_2\cdots a_k)=(a_1{a}_k)(a_1{a}_{k-1})\cdots (a_1{a}_3)(a_1{a}_2).$$

검증: 우변을 $a_1$에 적용하면, $(a_1{a}_2)$이 $a_1\mapsto a_2$을 보내고, 이후의 어떤 호환도 $a_2$을 움직이지 않는다(뒤에 나타나지 않으므로). 따라서 $a_1\mapsto a_2$이다. $2\le j\le k-1$에 대해 $a_j$에 적용하면: $(a_1{a}_2)$은 $a_j$을 고정하고, 이어서 $i>j$에 대한 각 $(a_1{a}_i)$은 $a_j$을 고정하며, 호환 $(a_1{a}_j)$은 $a_j\mapsto a_1$을 보내고, 그 다음 $(a_1{a}_{j+1})$은 $a_1\mapsto a_{j+1}$을 보내며, 이후의 호환들은 $a_{j+1}$을 고정한다. 따라서 $a_j\mapsto a_{j+1}$이다. $a_k$에 적용하면: $(a_1{a}_k)$은 $a_k\mapsto a_1$을 보내고, 이후의 어떤 호환도 $a_1$을 움직이지 않는다. 따라서 $a_k\mapsto a_1$이다. 이는 순환과 일치한다. $■$

주의. 호환 분해는 유일하지 않다. 예를 들어:

마지막 표현은 두 개 대신 네 개의 호환을 사용한다. 그러나 주목하라: $2$과 $4$은 모두 짝수이다. 이는 우연이 아니다.

§9.4 우치환과 기치환 --- 패리티 정리

이것은 이 장에서 가장 어려운 정리이다. 핵심은 $\sigma$의 호환 분해가 유일하지 않더라도, 패리티(호환 개수의 짝/홀)는 항상 동일하다는 것이다.

정의 9.6 (역위)

$\sigma \in S_n$에 대해, **역위(inversion)**란 $i<j$이고 $\sigma (i)>\sigma (j)$인 쌍 $(i,j)$이다. **역위수(inversion number)**는 다음과 같다.

예. $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)\in S_4$이라 하자. $i<j$인 모든 쌍 $(i,j)$을 나열하면:

따라서 $\mathrm{inv}(\sigma )=3$이며, 이는 홀수이다.

그림: 음영 칸으로 표시한 역위 쌍.

음영 칸은 정확히 역위 쌍 $(1,2)$, $(1,4)$, $(3,4)$이다. 이를 천천히 살펴볼 가치가 있다. 여기서 패리티는 임의의 부호 약속이 아니라, 순서가 어긋난 쌍의 개수의 패리티이다. 인접 호환이 이 개수를 $2$을 법으로 하여 1만큼 바꾸기 때문에 보조정리 9.7이 성립한다.

보조정리 9.7 (인접 호환과 역위)

${\tau }_k=(kk+1)$이 인접 호환이면, 임의의 $\sigma \in S_n$에 대해:

특히, $\mathrm{inv}(\sigma {\tau }_k)\equiv \mathrm{inv}(\sigma )+1(\mathrm{mod}2)$이다.

증명

호환 ${\tau }_k$은 위치 $k$와 $k+1$의 값을 맞바꾸고, 다른 모든 위치는 그대로 둔다. $i<j$인 쌍 $(i,j)$을 생각하자:

• $i$과 $j$ 모두 $\{k,k+1\}$에 속하지 않는 경우: 그 쌍은 $\mathrm{inv}(\sigma )$과 $\mathrm{inv}(\sigma {\tau }_k)$에 동일하게 기여한다.
• $i,j$ 중 정확히 하나만 $\{k,k+1\}$에 속하는 경우: 가령 $j=k$이고 $i<k$이라 하자. 그러면 $\sigma {\tau }_k(i)=\sigma (i)$이고 $\sigma {\tau }_k(k)=\sigma (k+1)$이다. $\sigma (i)$ vs $\sigma (k)$의 상대적 순서는 $\sigma (i)$ vs $\sigma (k+1)$와 다를 수 있으나, 특히 쌍 $(k,k+1)$에 대해서는 이것이 바뀌는 부분이다.
• 역위 여부가 반드시 뒤집히는 유일한 쌍은 $(k,k+1)$ 자신이다. 즉 $\sigma (k)<\sigma (k+1)$이면(역위가 아님) $\sigma {\tau }_k(k)=\sigma (k+1)>\sigma (k)=\sigma {\tau }_k(k+1)$이고(역위), 그 역도 성립한다.

더 정확히는: $f(i,j)$을 쌍 $(i,j)$이 역위 개수에 기여하는 값으로 정의하자. $(k,k+1)$을 제외한 모든 쌍에 대해 그 효과를 생각해 보자. $i<k$인 쌍 $(i,k)$에 대해: $\sigma {\tau }_k(i)=\sigma (i)$이고 $\sigma {\tau }_k(k)=\sigma (k+1)$이다. 쌍 $(i,k+1)$에 대해: $\sigma {\tau }_k(i)=\sigma (i)$이고 $\sigma {\tau }_k(k+1)=\sigma (k)$이다. 따라서 쌍 $(i,k)$과 $(i,k+1)$은 $\{\sigma (k),\sigma (k+1)\}$에서 $\{\sigma (k+1),\sigma (k)\}$으로 역위 기여를 통째로 맞바꾸며, 이는 한쪽이 잃은 만큼 다른 쪽이 얻는다는 뜻이다. 이 쌍들로부터의 순변화는 0이다. $j>k+1$인 쌍 $(k,j)$과 $(k+1,j)$에 대해서도 마찬가지이다.

따라서 역위 개수의 전체 변화는 오직 쌍 $(k,k+1)$에서만 비롯되며, 이는 정확히 한 번 뒤집힌다. 그러므로 $\mathrm{inv}(\sigma {\tau }_k)=\mathrm{inv}(\sigma )\pm 1$이다. $■$

보조정리 9.8 (임의의 호환은 홀수 개의 인접 호환의 곱이다)

$i<j$에 대해, 호환 $(ij)$은 다음과 같이 쓸 수 있다.

이는 $2(j-i)-1$개의 인접 호환(홀수 개)으로 이루어진다.

증명

위치 $i,i+1,\dots ,j$에 있는 원소들을 생각하자. 호환 $(ij)$은 $j-i$개의 인접 교환을 통해 $i$를 위치 $j$로 “거품처럼 밀어 올린” 다음, (이제 밀려난) $j$를 $j-i-1$개의 교환으로 되돌린다. 총합: $(j-i)+(j-i-1)=2(j-i)-1$이며, 이는 홀수이다.

명시적으로: 먼저 $(j-1j)$을 적용하고, 그 다음 $(j-2j-1)$, …, 그리고 $(ii+1)$을 적용하여 $j$을 위치 $i$로 가져오고 $i,i+1,\dots ,j-1$을 각각 한 칸씩 오른쪽으로 이동시킨다. 그런 다음 $(i+1i+2)$, …, $(j-1j)$을 적용하여 원소 $i+1,\dots ,j-1$을 원래 위치로 복원한다. 순효과는 오직 위치 $i$과 $j$만 맞바뀌는 것이다. $■$

정리 9.9 (패리티 정리 --- 이 장의 핵심 정리)

$\sigma \in S_n$이 $r$개의 호환의 곱으로도 쓰일 수 있고 $s$개의 호환의 곱으로도 쓰일 수 있으면, $r\equiv s(\mathrm{mod}2)$이다.

증명 (역위 세기를 통해)

$\sigma ={\tau }_1{\tau }_2\cdots {\tau }_r$로 쓰자. 여기서 각 ${\tau }_i$는 호환이다. $\mathrm{inv}(e)=0$(짝수)인 항등치환 $e$에서 시작한다.

보조정리 9.8에 의해, 각 호환 ${\tau }_i$은 홀수 개의 인접 호환의 곱이다. 보조정리 9.7에 의해, 각 인접 호환은 $\mathrm{inv}$의 패리티를 바꾼다. 패리티 변화가 홀수 번 일어나면 순패리티 변화가 생긴다. 따라서 각 호환 ${\tau }_i$은 $\mathrm{inv}$의 패리티를 뒤집는다.

$e$에 $r$개의 호환을 적용하면:

$$\mathrm{inv}(\sigma )\equiv \mathrm{inv}(e)+r\equiv r(\mathrm{mod}2).$$

마찬가지로, 다른 분해로부터:

$$\mathrm{inv}(\sigma )\equiv s(\mathrm{mod}2).$$

따라서 $r\equiv s(\mathrm{mod}2)$이다. $■$

정의 9.10 (우치환과 기치환)

치환 $\sigma \in S_n$가 짝수 개의 호환의 곱으로 쓰일 수 있으면 **우치환(even)**이고, 홀수 개의 곱으로 쓰일 수 있으면 **기치환(odd)**이다. 패리티 정리에 의해 이 분류는 잘 정의된다. 즉 $\sigma$가 둘 다일 수는 없다.

동치로, $\sigma$가 우치환일 필요충분조건은 $\mathrm{inv}(\sigma )$가 짝수인 것이다.

§9.5 부호 준동형사상

정의 9.11 (치환의 부호)

$\mathrm{sgn}:S_n\to \{+1,-1\}$을 다음으로 정의한다.

동치로, $\sigma ={\tau }_1\cdots {\tau }_r$이 임의의 호환 분해이면 $\mathrm{sgn}(\sigma )=(-1{)}^r$이다.

정리 9.12 (sgn은 군 준동형사상이다)

사상 $\mathrm{sgn}:S_n\to (\{+1,-1\},\cdot )$은 잘 정의된 전사 군 준동형사상이다.

증명

잘 정의됨: 패리티 정리(정리 9.9)에 의해 $(-1{)}^r$는 호환 분해의 선택이 아니라 오직 $\sigma$에만 의존한다.

준동형사상: $\sigma ={\tau }_1\cdots {\tau }_r$과 $\rho ={\mu }_1\cdots {\mu }_s$을 호환 분해라 하자. 그러면

$$\sigma \rho ={\tau }_1\cdots {\tau }_r{\mu }_1\cdots {\mu }_s$$

은 $r+s$개의 호환의 곱이다. 따라서

$$\mathrm{sgn}(\sigma \rho )=(-1{)}^{r+s}=(-1{)}^r\cdot (-1{)}^s=\mathrm{sgn}(\sigma )\cdot \mathrm{sgn}(\rho ).$$

전사: $n\ge 2$에 대해, 호환 $(12)$은 $\mathrm{sgn}(12)=-1$을 가지고, 항등치환은 $\mathrm{sgn}(e)=+1$를 가진다. 따라서 $\{+1,-1\}$의 두 원소가 모두 상으로 나온다. $■$

따름정리 9.13

모든 $\sigma ,\tau \in S_n$에 대해:

1. $\mathrm{sgn}(\sigma \tau )=\mathrm{sgn}(\sigma )\mathrm{sgn}(\tau )$.
2. $\mathrm{sgn}({\sigma }^{-1})=\mathrm{sgn}(\sigma )$.
3. $\mathrm{sgn}(e)=+1$.

증명

(1)은 준동형사상 성질이다. (2)의 경우: $\mathrm{sgn}(\sigma )\mathrm{sgn}({\sigma }^{-1})=\mathrm{sgn}(\sigma {\sigma }^{-1})=\mathrm{sgn}(e)=(-1{)}^0=1$이므로, $(\pm 1{)}^{-1}=\pm 1$에서 $\mathrm{sgn}({\sigma }^{-1})=\mathrm{sgn}(\sigma {)}^{-1}=\mathrm{sgn}(\sigma )$이다. (3)은 빈 곱으로부터 즉시 따른다. $■$

§9.6 $k$-순환의 패리티

정리 9.14 (순환의 부호)

$k$-순환은 정확히 $k-1$개의 호환의 곱이다. 따라서:

$k$-순환은 $k$이 홀수일 필요충분조건으로 우치환이다.

증명

호환 분해는 다음과 같다.

$$(a_1{a}_2\cdots a_k)=(a_1{a}_k)(a_1{a}_{k-1})\cdots (a_1{a}_3)(a_1{a}_2).$$

이는 $k-1$개의 호환의 곱이다. (검증은 정리 9.5에서 주어졌다.)

따라서 $\mathrm{sgn}(a_1\cdots a_k)=(-1{)}^{k-1}$이다.

이제 $(-1{)}^{k-1}=+1$일 필요충분조건은 $k-1$이 짝수인 것이고, 이는 $k$가 홀수인 것과 동치이다. $■$

빠른 참조표:

정리 9.15 (순환형으로부터의 부호)

$\sigma$이 순환 길이 $k_1,k_2,\dots ,k_r$(고정점에 대한 $1$-순환을 포함하여, 즉 $k_1+k_2+\cdots +k_r=n$)을 갖는 서로소 순환 분해를 가지면,

여기서 $c(\sigma )$은 고정점을 포함한 순환의 총 개수이다.

증명

서로소 순환들이 교환되므로, $\mathrm{sgn}$은 다음과 같이 인수분해된다.

$$\mathrm{sgn}(\sigma )=\prod _{i=1}^r\mathrm{sgn}(\text{ki-cycle})=\prod _{i=1}^r(-1{)}^{k_i-1}=(-1{)}^{\sum (k_i-1)}=(-1{)}^{(\sum k_i)-r}=(-1{)}^{n-r}.■$$

예. 치환 $\sigma =(135)(24)\in S_5$는 순환 길이 $3,2$을 가진다(명시적으로 나열할 고정점은 없으나, $S_5$에서 생각하면 전체 순환형은 $3,2$이고 $n=5$이다). 여기서 “순환”의 개수는 약속에 따라 달라진다. 비자명한 순환만 사용하는 공식으로: $\mathrm{sgn}(\sigma )=(-1{)}^{3-1}\cdot (-1{)}^{2-1}=(+1)(-1)=-1$. 또는: 암묵적 항등치환을 포함하면 $c(\sigma )=2$개의 비자명한 순환이지만, $n-c(\sigma )$은 고정점을 세는 것을 요구한다. $S_5$에서는 고정점이 없으므로 $c(\sigma )=2$이고 $\mathrm{sgn}=(-1{)}^{5-2}=(-1{)}^3=-1$이다. 둘 다 일치한다.

§9.7 교대군 $A_n$

정의 9.16

**교대군(alternating group)**은 다음과 같다.

정리 9.17 ($A_n$의 성질)

1. $A_n$은 $S_n$의 **정규부분군(normal subgroup)**이다(준동형사상의 핵이다).
2. $n\ge 2$에 대해 $|A_n|=\frac{n!}{2}$.
3. $S_n/A_n\cong {\mathbb{Z}}_2$.

증명

(1) 임의의 군 준동형사상의 핵은 정규부분군이다. $\mathrm{sgn}:S_n\to \{+1,-1\}$이 준동형사상이므로, $A_n=\ker (\mathrm{sgn})$은 $S_n$에서 정규이다.

(2) 제1동형정리에 의해 $S_n/\ker (\mathrm{sgn})\cong \mathrm{im}(\mathrm{sgn})$이다. $n\ge 2$에 대해 $\mathrm{sgn}$은 전사이므로(정리 9.12), $\mathrm{im}(\mathrm{sgn})=\{+1,-1\}$이고, 이는 위수 $2$을 가진다. 따라서

$$[S_n:A_n]=|S_n/A_n|=2,\text{so}|A_n|=\frac{|S_n|}{2}=\frac{n!}{2}.$$

(3) $S_n/A_n\cong \mathrm{im}(\mathrm{sgn})=\{+1,-1\}\cong {\mathbb{Z}}_2$이다. 곱셈에 대한 $\{+1,-1\}$이 위수 $2$의 순환군이기 때문이다. $■$

정리 9.18 ($n\ge 3$에 대해 $A_n$은 $3$-순환으로 생성된다)

$A_n$의 모든 원소는 $3$-순환들의 곱으로 쓸 수 있다.

증명

우치환은 정의상 짝수 개의 호환의 곱이다. 따라서 임의의 두 호환의 곱이 $3$-순환들의 곱으로 쓰일 수 있음을 보이면 충분하다. 두 가지 경우가 있다.

경우 1: 두 호환이 한 원소를 공유한다. $b\ne c$일 때 $\sigma =(ab)(ac)$이라 하자. 그러면:

• $a\mapsto c\mapsto c$ (먼저 $(ac)$ 아래에서, 그 다음 $c\ne b$이면 $(ab)$가 $c$을 고정하는데, 실제로 그렇다). 잠깐, 신중하게 계산해 보자.
• 먼저 $(ac)$를 적용: $a\mapsto c$. 그 다음 $(ab)$: $c\mapsto c$ ($c\ne a,b$이므로). 따라서 $a\mapsto c$.
• 먼저 $(ac)$을 적용: $c\mapsto a$. 그 다음 $(ab)$: $a\mapsto b$. 따라서 $c\mapsto b$.
• 먼저 $(ac)$을 적용: $b\mapsto b$. 그 다음 $(ab)$: $b\mapsto a$. 따라서 $b\mapsto a$.

따라서 $(ab)(ac)=(acb)$이며, 이는 $3$-순환이다.

경우 2: 두 호환이 서로소이다. $\{a,b\}\cap \{c,d\}=\varnothing$일 때 $\sigma =(ab)(cd)$이라 하자. “다리(bridge)” 원소를 도입한다. 다음을 검증할 수 있다.

$$(ab)(cd)=(acb)(acd).$$

확인: 먼저 $(acd)$를 적용하고, 그 다음 $(acb)$을 적용한다.

• $a$: $(acd)$이 $a\mapsto c$을 보내고, $(acb)$이 $c\mapsto b$을 보낸다. 따라서 $a\mapsto b$. $✓$
• $b$: $(acd)$가 $b$을 고정하고, $(acb)$이 $b\mapsto a$을 보낸다. 따라서 $b\mapsto a$. $✓$
• $c$: $(acd)$가 $c\mapsto d$을 보내고, $(acb)$이 $d$을 고정한다. 따라서 $c\mapsto d$. $✓$
• $d$: $(acd)$가 $d\mapsto a$을 보내고, $(acb)$이 $a\mapsto c$를 보낸다. 따라서 $d\mapsto c$. $✓$

두 경우 모두 $3$-순환들의 곱을 만든다. 호환 쌍의 개수에 대한 귀납법에 의해, 모든 우치환은 $3$-순환들의 곱이다. $■$

§9.8 명시적인 작은 경우들

$A_3$

$|A_3|=3!/2=3$. $S_3$의 원소들과 그 부호:

따라서

이는 순환군이며, 어느 $3$-순환으로든 생성된다: $(123{)}^2=(132)$이고 $(123{)}^3=e$이다.

$A_4$

$|A_4|=24/2=12$. 우치환을 순환형으로 분류하면:

항등치환 (원소 1개):

$3$-순환 (원소 8개): $3$-순환은 부호 $(-1{)}^2=+1$을 가지므로, $S_4$의 모든 $3$-순환은 $A_4$에 속한다. $\{1,2,3,4\}$에서 $3$개의 원소를 골라 순환을 만든다: $\left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot 2=8$개의 3-순환(각 $3$개 원소 집합이 $2$개의 서로 다른 순환을 준다).

서로소인 두 호환의 곱 (원소 3개): 단일 호환은 기치환이지만, 서로소인 두 호환의 곱은 부호 $(-1)(-1)=+1$을 가진다.

총합: $1+8+3=12=|A_4|$. $✓$

클라인 4원군 $V_4⊴A_4$

집합

은 $A_4$의 부분군으로 ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$(클라인 4원군, Klein four-group)과 동형이다. 닫힘을 검증할 수 있다.

모든 비항등 원소는 위수 $2$를 가지며, 이 군은 가환이다. 이것이 클라인 4원군이다.

$V_4$은 $A_4$에서 정규이다(그리고 사실 $S_4$에서도): 이중 호환들의 집합은 $S_4$에서 켤레변환에 대해 닫혀 있는데, 켤레변환은 순환형을 보존하기 때문이다. $V_4$이 항등치환과 $S_4$에서 순환형 $(2,2)$인 모든 원소의 합집합이므로, 켤레변환에 대해 불변이다. 특히 $A_4$에서 정규이다.

이는 주목할 만하다: $A_4$은 위수 $12$인 군으로, $6\mid 12$임에도 불구하고 위수 $6$인 부분군을 갖지 않는다. 라그랑주 정리의 역은 이미 $A_4$에서 성립하지 않는다. 그림: $A_4$의 정규부분군 격자.

$V_4$은 위수 $4$인 유일한 정규부분군이며, 위수 $3$인 순환부분군이 네 개 있다(그 중 어느 것도 정규가 아니다).

§9.9 순환의 거듭제곱과 과제와의 연결

정리 9.19 (순환의 거듭제곱의 구조)

$\sigma =(a_1{a}_2\cdots a_k)$를 $k$-순환이라 하고, $m$를 양의 정수라 하자. $d=\gcd (m,k)$로 두자. 그러면 ${\sigma }^m$은 각각 길이 $k/d$인 $d$개의 서로소 순환으로 이루어진다.

증명

원소 $\{a_1,a_2,\dots ,a_k\}$(첨자는 $k$을 법으로 함) 위에서의 ${\sigma }^m$의 작용을 생각하자. ${\sigma }^m(a_i)=a_{i+m}$이다(첨자는 $k$을 법으로 함). ${\sigma }^m$ 아래 $a_i$의 궤도는

$$\{a_i,a_{i+m},a_{i+2m},\dots \}$$

이며, 여기서 첨자는 $k$을 법으로 한다. 이 궤도의 크기는 $tm\equiv 0(\mathrm{mod}k)$을 만족하는 가장 작은 양의 정수 $t$과 같다. 즉 $t=k/\gcd (m,k)=k/d$이다.

각 궤도는 크기 $k/d$을 가지며, 총 $k$개의 원소가 있으므로 궤도의 개수는 $k/(k/d)=d$이다.

따라서 ${\sigma }^m$은 각각 길이 $k/d$인 $d=\gcd (m,k)$개의 서로소 순환으로 분해된다. $■$

따름정리. ${\sigma }^m$이 그 자체로 순환(즉 단일 순환에 고정점을 더한 것)일 필요충분조건은 $\gcd (m,k)=1$이다.

응용: 과제 1 문제 2 --- ${\sigma }^2$도 순환인 $S_5$의 순환

문제 (과제 1, 문제 2). ${\sigma }^2$도 순환이 되는 $S_5$의 순환 $\sigma$의 개수를 세라. (항등치환도 순환으로 간주한다.)

풀이. 핵심 제약은 $\sigma$가 그 자체로 단일 순환이어야 한다는 것이다(서로소 순환들의 곱이 아니라). $S_5$에서 단일 순환의 가능한 순환 길이는 $k=1,2,3,4,5$이다.

정리 9.19에 의해, $k$-순환 $\sigma$에 대해 치환 ${\sigma }^2$는 길이 $k/\gcd (2,k)$인 $\gcd (2,k)$개의 서로소 순환으로 이루어진다. 따라서 ${\sigma }^2$가 단일 순환일 필요충분조건은 $\gcd (2,k)=1$이거나(즉 $k$가 홀수) 또는 $k\le 2$인 것이다(여기서 ${\sigma }^2=e$이며, 이를 순환으로 센다).

총합: $1+10+20+0+24=\boxed{55}$.

이 문제의 흔한 오독

솔깃한 실수는 “${\sigma }^2$이 순환이 되는 $S_5$의 순환 $\sigma$“을 “${\sigma }^2$이 순환이 되는 $S_5$의 치환 $\sigma$“로 해석하는 것이다. 이들은 서로 다른 문제이다.

만약 $\sigma$이 (단일 순환이 아니라) 임의의 치환이 될 수 있다면, 다음도 고려해야 한다:

• $\sigma =(abc)(de)$ (3-순환과 서로소인 호환의 곱). 여기서 ${\sigma }^2=(acb)$은 순환이다. 이러한 치환은 $\left(\genfrac{}{}{0ex}{}{5}{3}\right)\cdot 2\cdot 1=20$개 있다. 그러나 $\sigma$ 자체는 순환이 아니다 — 두 서로소 순환의 곱이다. 따라서 이들은 세지 말아야 한다.

• $\sigma =(ab)(cd)$ (서로소인 두 호환). 여기서 ${\sigma }^2=e$이고, 항등치환은 순환이다. 그러나 다시, $\sigma$은 단일 순환이 아니다.

두 번째 실수는 반대 방향이다: “${\sigma }^2=e$이 자명하다”는 이유로 항등치환과 호환을 제외하는 것이다. 그러나 문제는 항등치환이 순환으로 간주된다고 명시하므로, ${\sigma }^2=e$은 자격이 있다.

올바른 독법은: $\sigma$은 단일 순환이어야 하며(항등치환을 1-순환으로 포함), ${\sigma }^2$도 단일 순환이어야 한다는 것이다.

오산	오류	효과
$(abc)(de)$ 유형 포함	$\sigma$는 순환이 아님	$20$만큼 과다 계수
$e$과 호환 제외	${\sigma }^2=e$은 여전히 순환	$11$만큼 과소 계수
두 오류 동시	$55+20-11=64$	틀린 답 $64$

교훈: 대수학에서는 한정사를 신중히 읽어라. “순환 $\sigma$“은 정의역을 제한하고, “${\sigma }^2$가 순환이 되는”은 공역을 제한한다.

오각형/오각성 그림

그림: 오각형 위의 $5$-순환과 오각성 위의 그 제곱.

$5$-순환 $\sigma =(12345)$는 정오각형의 꼭짓점을 회전시킨다(파란색). 그러면 ${\sigma }^2=(13524)$은 “한 꼭짓점씩 건너뛰어” **오각성(pentagram)**을 그린다(빨간색, 점선). 이는 $\gcd (2,5)=1$이기 때문이다: $5$-순환의 제곱은 여전히 $5$개의 꼭짓점을 모두 방문하지만, 다른 순서로 방문한다.

대조적으로, $4$-순환 $(1234)$에 대해 ${\sigma }^2$은 $(13)(24)$을 준다: 서로소인 두 $2$-순환인데, $\gcd (2,4)=2$이기 때문이다. 제곱한 회전의 제곱은 마주 보는 꼭짓점을 맞바꾼다 --- 단일 순환을 그리지 않는다.

§9.10 풀이 계산

예제 1: $\sigma =(1352)(46)\in S_6$의 패리티 결정

순환 길이: $4$과 $2$. 부호:

따라서 $\sigma$는 우치환이고, $\sigma \in A_6$이다.

공식 $\mathrm{sgn}(\sigma )=(-1{)}^{n-c(\sigma )}$을 통한 대안: 여기서 $n=6$이고, $c(\sigma )=2$(비자명한 순환)에 고정점을 더한다. 그러나 고정점이 없다($\{1,2,3,4,5,6\}$가 모두 움직인다). 따라서 $c(\sigma )=2$이고 $\mathrm{sgn}=(-1{)}^{6-2}=(-1{)}^4=+1$이다. $✓$

예제 2: $\sigma =(143)(25)\in S_5$을 호환으로 표현하고 패리티 결정

따라서

이며, 이는 $3$개의 호환(홀수)이다. 그러므로 $\mathrm{sgn}(\sigma )=-1$이고 $\sigma \notin A_5$이다.

부호 공식으로 확인: $(-1{)}^{3-1}\cdot (-1{)}^{2-1}=(+1)(-1)=-1$. $✓$

예제 3: sgn이 곱셈적임을 검증

$S_4$에서 $\alpha =(123)$와 $\beta =(12)(34)$라 하자.

• $\mathrm{sgn}(\alpha )=(-1{)}^{3-1}=+1$.
• $\mathrm{sgn}(\beta )=(-1{)}^1\cdot (-1{)}^1=+1$.

$\alpha \beta$를 계산: 먼저 $\beta$을 적용하고, 그 다음 $\alpha$을 적용한다.

• $1\stackrel{\beta }{\to }2\stackrel{\alpha }{\to }3$.
• $2\stackrel{\beta }{\to }1\stackrel{\alpha }{\to }2$. (고정!)
• $3\stackrel{\beta }{\to }4\stackrel{\alpha }{\to }4$. (고정!)
• $4\stackrel{\beta }{\to }3\stackrel{\alpha }{\to }1$.

매우 흔한 첫 시도의 실수는 너무 일찍 멈추고 이것이 그저 $(13)$이라고 생각하는 것이다. 많은 사람이 빠지는 지점은 $3$과 $4$을 신중하게 계속 추적하는 것을 잊는 것이다:

• $1\mapsto 3$.
• $3\stackrel{\beta }{\to }4\stackrel{\alpha }{\to }4$, 따라서 $3\mapsto 4$.
• $4\stackrel{\beta }{\to }3\stackrel{\alpha }{\to }1$, 따라서 $4\mapsto 1$.
• $2$는 고정된다.

따라서

$\mathrm{sgn}(\alpha \beta )=(-1{)}^{3-1}=+1=(+1)(+1)=\mathrm{sgn}(\alpha )\mathrm{sgn}(\beta )$. $✓$

예제 4: 두 줄 표기로 주어진 $S_6$의 치환의 패리티

서로소 순환 분해: $1\to 2\to 4\to 1$은 $(124)$를 준다. 그 다음 $3\to 6\to 5\to 3$은 $(365)$을 준다. 따라서 $\sigma =(124)(365)$이다.

부호: $(-1{)}^{3-1}\cdot (-1{)}^{3-1}=(+1)(+1)=+1$. 따라서 $\sigma \in A_6$이다.

호환 분해: $(124)=(14)(12)$이고 $(365)=(35)(36)$이다. 따라서 $\sigma =(14)(12)(35)(36)$이며, 네 개의 호환(짝수)이다. $✓$

예제 5: $(12)(34)(56)\in A_6$을 다시 쓰기?

$\mathrm{sgn}=(-1{)}^3=-1$. 따라서 $(12)(34)(56)$은 기치환이며 $A_6$에 속하지 않는다.

예제 6: $(13)(24)\in A_4$을 $3$-순환들의 곱으로 표현

정리 9.18의 서로소-호환 공식을 사용하면:

검증: 먼저 $(124)$를 적용하고, 그 다음 $(123)$을 적용한다:

• $1\stackrel{(124)}{\to }2\stackrel{(123)}{\to }3$. 따라서 $1\mapsto 3$. $✓$
• $3\stackrel{(124)}{\to }3\stackrel{(123)}{\to }1$. 따라서 $3\mapsto 1$. $✓$
• $2\stackrel{(124)}{\to }4\stackrel{(123)}{\to }4$. 따라서 $2\mapsto 4$. $✓$
• $4\stackrel{(124)}{\to }1\stackrel{(123)}{\to }2$. 따라서 $4\mapsto 2$. $✓$

따라서 $(13)(24)=(123)(124)$이다. $✓$

§9.11 표준적인 함정

1. $k$-순환은 $k$개가 아니라 $k-1$개의 호환을 필요로 한다. 순환 $(123)=(13)(12)$는 세 개가 아니라 두 개의 호환을 사용한다.

2. 홀수 길이의 순환은 우치환이다. 이것이 이 장에서 가장 헷갈리는 명칭 충돌이다. $3$-순환은 우치환이다. $5$-순환은 우치환이다. “홀수 길이”에서 “홀수”는 순환의 길이를 가리키는 반면, “우(even)“는 호환 개수의 패리티($k-1$)를 가리킨다. $3-1=2$이 짝수이므로, $3$-순환은 우치환이다.

3. 호환 분해는 유일하지 않지만, 패리티는 유일하다. 동일한 호환 쌍 $(\tau \tau =e)$을 언제든지 끼워 넣어 치환을 바꾸지 않으면서 호환 개수를 $2$만큼 바꿀 수 있다. 할 수 없는 것은 패리티를 바꾸는 것이다.

4. 서로소 순환은 교환되지만, 겹치는 순환은 그렇지 않다. 부호를 계산할 때 서로소 순환들을 자유롭게 재배열할 수 있다. 그러나 $(12)(13)\ne (13)(12)$이다: 좌변은 $(132)$을 주고 우변은 $(123)$를 준다.

5. 항등치환은 우치환이다. 이는 0개의 호환의 곱이다($0$은 짝수이다). 모든 고정점은 $0$개의 호환을 갖는 $1$-순환에 기여한다.

§9.12 랑의 구조적 관점

랑(Lang)이라면 이 장을 짧은 완전열(short exact sequence)을 통해 구성할 것이다.

여기서 곱셈에 대해 ${\mathbb{Z}}_2=\{+1,-1\}$이다(동치로, 덧셈에 대해 $\mathbb{Z}/2\mathbb{Z}$). 이 열이 완전한 이유는:

• $A_n=\ker (\mathrm{sgn})$이므로, $A_n\hookrightarrow S_n$의 상은 $\mathrm{sgn}$의 핵과 같다.
• $n\ge 2$에 대해 $\mathrm{sgn}$은 전사이다.

완전열이 우리에게 말해주는 것:

• $A_n$은 $S_n$의 지수(index) $2$인 정규부분군이다.
• 몫 $S_n/A_n\cong {\mathbb{Z}}_2$은 가능한 가장 단순한 비자명 몫이다.
• 이것은 (강제가 아니라) 유기적으로 발생하는 몫군의 첫 번째 자연스러운 예이다. 몫군의 이전 예들은 $G/G\cong \{e\}$이거나 $G/\{e\}\cong G$이었다. 이제 우리는 진정으로 흥미로운 핵을 가진다.

지수 $2$인 부분군이 항상 정규인 이유. $[G:H]=2$이면, 정확히 두 개의 잉여류가 있다: $H$과 $G\setminus H$. 임의의 $g\in G$에 대해, $g\in H$이거나(따라서 $gH=H=Hg$) $g\notin H$이다(따라서 $gH=G\setminus H=Hg$). 따라서 모든 $g$에 대해 $gH=Hg$이고, $H⊴G$이다. 부호 준동형사상은 $[S_n:A_n]=2$임을 보이는 깔끔한 증명이지만, 그것 없이도 지수를 아는 것만으로 정규성을 보이기에 충분하다.

행렬식과의 연결. 선형대수학에서 치환 행렬의 행렬식은 $\mathrm{sgn}(\sigma )$와 같다. 이는 우연이 아니다: $\det :G{L}_n\to {\mathbb{R}}^{\ast }$은 $G{L}_n$에 매장된 치환 행렬들 위에서 $\mathrm{sgn}$으로 제한된다. 교대군은 $S{L}_n(\mathbb{R})$(행렬식 $1$인 행렬)과 대칭군의 교집합이다. 이것이 $\mathrm{sgn}$이 곱셈적인 구조적 이유이다.

§9.14 플래시카드용 요약

$\sigma$ 아래 $x$의 궤도: ${\mathrm{Orb}}_{\sigma }(x)=\{x,\sigma (x),{\sigma }^2(x),\dots \}$. 궤도는 $\{1,\dots ,n\}$를 분할한다.

궤도 $\leftrightarrow$ 순환: $\sigma$의 비자명한 궤도는 서로소 순환 분해의 순환들에 대응한다.

호환 분해: 모든 치환은 호환들의 곱이다. $k$-순환은 $k-1$개의 호환을 사용한다.

패리티 정리: $\sigma$의 어떤 분해에서든 호환의 개수는 항상 동일한 패리티를 가진다. 역위 세기를 통해 증명된다.

우/기: $\sigma$는 짝수 개의 호환으로 분해되면 우치환이고, 그렇지 않으면 기치환이다.

부호 준동형사상: $\mathrm{sgn}:S_n\to \{+1,-1\}$, \operatorname{sgn}(\sigma) = (-1)^{\text{# transpositions}}. 이는 전사 군 준동형사상이다.

$k$-순환의 부호: $(-1{)}^{k-1}$. $k$-순환은 $k$이 홀수일 필요충분조건으로 우치환이다.

일반 부호 공식: $\mathrm{sgn}(\sigma )=(-1{)}^{n-c(\sigma )}$, 여기서 $c(\sigma )$ = 고정점을 포함한 순환의 개수.

교대군: $A_n=\ker (\mathrm{sgn})$, $|A_n|=n!/2$, $A_n⊴S_n$, $S_n/A_n\cong {\mathbb{Z}}_2$.

$A_n$은 $3$-순환으로 생성됨 ($n\ge 3$): $(ab)(ac)=(acb)$이고 $(ab)(cd)=(acb)(acd)$.

작은 경우들: $A_3\cong {\mathbb{Z}}_3$. $|A_4|=12$; 원소는 $e$, 여덟 개의 $3$-순환, 세 개의 이중 호환이다. $V_4=\{e,(12)(34),(13)(24),(14)(23)\}⊴A_4$.

순환의 거듭제곱: $k$-순환에 대한 ${\sigma }^m$은 길이 $k/\gcd (m,k)$인 $\gcd (m,k)$개의 서로소 순환으로 이루어진다.

완전열: $1\to A_n\to S_n\stackrel{\mathrm{sgn}}{\to }{\mathbb{Z}}_2\to 1$.

§9.15 9장을 떠나기 전에 숙달해야 할 것

• 치환의 궤도를 계산하고 서로소 순환 분해와 관련짓기.
• 임의의 치환을 호환으로 분해하기.
• 패리티가 잘 정의되는 이유를 설명하기(역위 세기 논증을 진술하기).
• 순환형으로부터 $\mathrm{sgn}(\sigma )$을 빠르게 계산하기.
• 공식을 진술하고 사용하기: $k$-순환은 $k$이 홀수일 필요충분조건으로 우치환이다($k-1$개의 호환을 요구함).
• 일반 공식 $\mathrm{sgn}(\sigma )=(-1{)}^{n-c(\sigma )}$을 적용하기.
• $A_n$의 정의를 알고, $|A_n|=n!/2$을 증명하며, $A_n⊴S_n$인 이유를 설명하기.
• 임의의 우치환을 $3$-순환들의 곱으로 쓰기(두 경우 모두 다루기: 공유 원소와 서로소).
• $A_3$과 $A_4$의 원소를 순환형으로 나열하고, $V_4⊴A_4$을 식별하기.
• 순환-거듭제곱 정리를 사용하기: $k$-순환에 대한 ${\sigma }^m$은 길이 $k/\gcd (m,k)$인 $\gcd (m,k)$개의 순환을 준다.
• 짧은 완전열 $1\to A_n\to S_n\to {\mathbb{Z}}_2\to 1$과 그것이 중요한 이유를 설명하기.
• 표준적인 함정을 피하기: $k-1$개의 호환($k$개가 아니라), 홀수 길이 $=$ 우 패리티, 분해는 유일하지 않지만 패리티는 유일하다.