8장 - 치환군

치환군은 이 강의가 계산적으로 정밀해지는 지점이다. 치환은 곱이 선언된 추상적 기호가 아니라 구체적인 전단사이며, 그 곱셈은 함수의 합성이다. 이 장이 중요한 이유는 군 계산을 명시적으로 만들어 주고, 케일리 정리(Cayley’s theorem)를 통해 모든 군이 대칭군 안에서 실현될 수 있음을 보여 주기 때문이다. 여기서 다루는 모든 것은 실제로 다룰 수 있어야 한다. 즉 이러한 계산을 손으로 빠르고 오류 없이 수행할 수 있어야 한다.

§8.1 치환과 대칭군

정의 8.1 (치환)

집합 $A$의 **치환(permutation)**은 전단사 $\sigma :A\to A$이다. $A$의 모든 치환의 집합에 합성을 부여한 것을 $S_A$로 표기하며, 이를 **$A$ 위의 대칭군(symmetric group)**이라 한다.

$A=\{1,2,\dots ,n\}$일 때 $S_n$로 쓰고, 이를 $n$개의 문자 위의 대칭군이라 한다. 이때 $|S_n|=n!$이다.

정리 8.2. $S_A$는 합성에 대하여 군이다.

증명

군 공리를 확인한다.

닫힘. $\sigma ,\tau :A\to A$가 전단사이면 $\sigma \circ \tau :A\to A$도 전단사이다 (전단사의 합성은 전단사이다).

결합법칙. 함수의 합성은 항상 결합적이다. 즉 모든 $x\in A$에 대하여

$$((\sigma \circ \tau )\circ \mu )(x)=(\sigma \circ \tau )(\mu (x))=\sigma (\tau (\mu (x)))=\sigma ((\tau \circ \mu )(x))=(\sigma \circ (\tau \circ \mu ))(x).$$

항등원. $\iota (x)=x$으로 정의된 항등함수 $\iota :A\to A$는 모든 $\sigma$에 대하여 $\sigma \circ \iota =\iota \circ \sigma =\sigma$를 만족한다.

역원. $\sigma$는 전단사이므로 역함수 ${\sigma }^{-1}$를 가지며 이 또한 전단사이고, $\sigma \circ {\sigma }^{-1}={\sigma }^{-1}\circ \sigma =\iota$이다. $■$

비고 8.3 (비가환성)

$n\ge 3$일 때 군 $S_n$는 **비가환(non-abelian)**이다. 이는 아래의 풀이 예제에서 명시적으로 보여질 것이다. 가환성의 실패는 병적인 현상이 아니라 치환군에서 일반적으로 나타나는 상황이다.

약속 (합성 순서)

이 노트 전반에 걸쳐, 프레일리(Fraleigh)와 대부분의 대수학 교재에서와 같이 오른쪽에서 왼쪽으로 합성한다.

이는 $\tau$를 먼저 적용한 뒤 $\sigma$를 적용함을 의미한다. $\sigma \tau$를 계산할 때는 각 원소를 $\tau$에 통과시킨 뒤 $\sigma$에 통과시켜 무슨 일이 일어나는지 추적한다.

§8.2 두 줄 표기법

정의 8.4 (두 줄 표기법)

치환 $\sigma \in S_n$는 $2\times n$ 배열

로 쓸 수 있는데, 여기서 윗줄은 $\{1,\dots ,n\}$의 원소들을 나열하고 아랫줄은 $\sigma$에 의한 그 상(image)을 나열한다.

직관: 왜 치환은 행렬처럼 보이는가?

치환 $\sigma$는 함수이며, 유한집합 위의 임의의 함수는 그 값들을 나열함으로써 결정된다. 두 줄 표기법은 다름 아닌 **참조표(lookup table)**이다. 각 열은 입력(위)을 출력(아래)과 짝지으므로, $k$번째 열은 "$k\mapsto \sigma (k)$"임을 말해 준다. 입력을 순서대로 배열하는 것은 순전히 편의를 위함이며, 이로써 $\sigma (k)$를 즉시 읽어 낼 수 있게 된다.

행렬과의 유사성은 우연이 아니다. 모든 $\sigma \in S_n$는 각 행과 열에 단 하나의 $1$을 배치함으로써 진정한 $n\times n$ 치환행렬(permutation matrix) $P_{\sigma }$를 정의한다. $(P_{\sigma }{)}_{ij}=\{\begin{array}{ll}1& \text{if }\sigma (j)=i,\\ 0& \text{otherwise.}\end{array}$ 두 줄 배열은 $P_{\sigma }$의 압축된 부호화이다. 즉 $n^2$개의 성분(대부분 0)을 모두 적는 대신, $1$들의 $n$개의 위치만을 기록한다. 그리고 행렬 곱셈이 선형사상의 합성을 부호화하듯이, 치환행렬을 합성하는 것은 치환을 합성하는 것에 대응하므로 대수적 구조가 그대로 옮겨진다.

예제 8.5.

로 정의된 치환 $\sigma \in S_4$는 $\sigma (1)=3$, $\sigma (2)=1$, $\sigma (3)=4$, $\sigma (4)=2$를 의미한다.

두 줄 표기법에서 치환의 합성

$\sigma \tau$를 계산하려면, $\tau$를 먼저 적용한 뒤 $\sigma$를 적용함을 기억하라.

예제 8.6. 다음과 같이 두자.

$\sigma \tau$ 계산: 각 $x$에 대하여 $\sigma (\tau (x))$를 계산한다.

따라서 $\sigma \tau =\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 2& 3& 4\end{array}\right)=\iota$로 항등원이다.

$\tau \sigma$ 계산: 각 $x$에 대하여 $\tau (\sigma (x))$를 계산한다.

따라서 $\tau \sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 2& 3& 4\end{array}\right)=\iota$도 성립한다.

이 특정한 예제에서는 $\sigma \tau =\tau \sigma =\iota$이므로 $\tau ={\sigma }^{-1}$이다. 이는 특수한 경우이며, 일반적으로는 $\sigma \tau \ne \tau \sigma$이다.

예제 8.7. $\alpha ,\beta \in S_4$를 다음과 같이 두자.

$\alpha \beta$: $\beta$를 먼저 적용한 뒤 $\alpha$를 적용한다.

따라서 $\alpha \beta =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 1& 3& 4\end{array}\right)$이다.

$\beta \alpha$: $\alpha$를 먼저 적용한 뒤 $\beta$를 적용한다.

따라서 $\beta \alpha =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 2& 1& 4\end{array}\right)$이다.

$\alpha \beta \ne \beta \alpha$이므로 $S_4$가 비가환임이 확인된다.

§8.3 순환 표기법

정의 8.8 (순환)

$k$-순환(cycle) (또는 길이 $k$의 순환)은 서로 다른 원소 $a_1,a_2,\dots ,a_k$가 존재하여

를 만족하고 $\sigma$가 다른 모든 원소를 고정하는 치환 $\sigma$이다. 이 순환을

로 쓴다.

$2$-순환은 **전위(transposition)**라 한다. $1$-순환 $(a)$은 $\{a\}$ 위에서 항등원이며 보통 생략한다.

예제 8.9. $S_5$에서 순환 $(135)$은 다음 치환이다.

두 줄 표기법으로는

두 줄 표기법에서 순환 표기법으로 변환하기

가장 작은 원소에서 시작한다. $\sigma$에 의한 그 궤도(orbit)를 시작점으로 돌아올 때까지 따라간다. 이를 하나의 순환으로 기록한다. 그런 다음 아직 처리되지 않은 가장 작은 원소를 택하여 반복한다.

예제 8.10. 다음을 순환 표기법으로 변환하라.

• $1$에서 시작한다: $1\to 3\to 1$. 순환: $(13)$.

  잠깐 — 더 신중히 추적하자. $\sigma (1)=3$, $\sigma (3)=1$. 따라서 $1\to 3\to 1$. 이로부터 순환 $(13)$을 얻는다.

• 사용되지 않은 가장 작은 원소: $2$. $\sigma (2)=5$, $\sigma (5)=2$. 순환: $(25)$.

• 사용되지 않은 가장 작은 원소: $4$. $\sigma (4)=6$, $\sigma (6)=4$. 순환: $(46)$.

따라서 $\sigma =(13)(25)(46)$이다.

검산: $(13)(25)(46)$은 $1\to 3$, $2\to 5$, $3\to 1$, $4\to 6$, $5\to 2$, $6\to 4$로 보낸다. 이는 두 줄 표기법과 일치한다. $✓$

예제 8.11. 순환 표기법으로 변환하라.

• $1$에서 시작한다: $1\to 4\to 1$. 순환: $(14)$.
• 사용되지 않은 가장 작은 원소: $2$. $\sigma (2)=2$이므로 $2$은 고정점이다 (생략).
• 사용되지 않은 가장 작은 원소: $3$. $3\to 5\to 3$. 순환: $(35)$.

따라서 $\tau =(14)(35)$이다.

§8.4 서로소 순환 분해

정의 8.12 (서로소 순환)

두 순환 $(a_1\cdots a_j)$과 $(b_1\cdots b_k)$이 **서로소(disjoint)**라는 것은 $\{a_1,\dots ,a_j\}\cap \{b_1,\dots ,b_k\}=\varnothing$임을, 즉 어떤 원소도 두 순환 모두에 나타나지 않음을 뜻한다.

정리 8.13 (서로소 순환 분해)

모든 치환 $\sigma \in S_n$는 서로소 순환의 곱으로 쓸 수 있다. 이 분해는 순환이 나열되는 순서를 무시하면 (그리고 $1$-순환의 생략을 무시하면) 유일하다.

증명

존재성. $\sigma \in S_n$라 하자. $\sigma$에 의한 $x$의 궤도를

$${\mathrm{Orb}}_{\sigma }(x)=\{x,\sigma (x),{\sigma }^2(x),\dots \}.$$

로 정의한다. $\{1,\dots ,n\}$가 유한하고 $\sigma$가 단사이므로, $x$에서 시작하여 $\sigma$를 반복 적용하면 결국 어떤 값을 다시 방문하게 된다. 처음으로 반복되는 값은 반드시 $x$ 자신이어야 한다. 만약 ${\sigma }^i(x)={\sigma }^j(x)$이고 $i<j$이면 단사성에 의해 $x={\sigma }^{j-i}(x)$이기 때문이다. 따라서 $x$의 궤도는 어떤 $m\ge 1$에 대하여

$$\{x,\sigma (x),{\sigma }^2(x),\dots ,{\sigma }^{m-1}(x)\}$$

이고, $\sigma$는 이 집합 위에서 순환 $(x\sigma (x){\sigma }^2(x)\cdots {\sigma }^{m-1}(x))$로 작용한다.

$\sigma$의 궤도들은 $\{1,\dots ,n\}$을 분할한다 (이는 동치관계에 관한 일반적 사실이다: 어떤 정수 $k$에 대하여 $y={\sigma }^k(x)$일 때 $x\sim y$로 정의한다). 각 궤도 위에서 $\sigma$는 하나의 순환으로 작용한다. 이 순환들을 (어떤 순서로든 — 그것들은 서로소이다) 곱하면 $\sigma$가 복원된다.

유일성. $\sigma ={\gamma }_1{\gamma }_2\cdots {\gamma }_r={\delta }_1{\delta }_2\cdots {\delta }_s$이 두 개의 서로소 순환 분해라 하자. 임의의 $a\in \{1,\dots ,n\}$에 대하여, 왼쪽 변에서 $a$를 포함하는 순환은 오른쪽 변에서 $a$을 포함하는 순환과 같은 궤도를 만들어 내야 한다 (두 변이 모두 $\sigma$와 같으므로 모든 원소에서 일치한다). 따라서 순환들은 $\sigma$의 궤도들에 의해 결정되며, 이는 $\sigma$ 자체에 의해 결정된다. 두 분해는 같은 순환들로 이루어지며, 다만 다른 순서로 나열되었을 수 있다. $■$

§8.5 순환의 대수

정리 8.14 (순환의 역원)

$\sigma =(a_1{a}_2\cdots a_k)$이면

이다.

증명

$\tau =(a_k{a}_{k-1}\cdots a_1)$라 하자. $\sigma \tau =\iota$임을 보여야 한다. 순환에 속한 임의의 $a_i$ (여기서 $1\le i\le k$)에 대하여:

• $\tau$은 $a_i$을 수열 $a_k,a_{k-1},\dots ,a_1$에서 $a_i$의 바로 앞 원소로 보낸다. $(a_k{a}_{k-1}\cdots a_1)$에서 $a_i$의 다음 원소는 $a_{i-1}$이다 (지수는 $k$을 법으로 하며, 약속 $a_0=a_k$을 따른다). 따라서 $\tau (a_i)=a_{i-1}$이다.
• 그러면 $\sigma (a_{i-1})=a_i$이다.

따라서 $(\sigma \tau )(a_i)=\sigma (\tau (a_i))=\sigma (a_{i-1})=a_i$이다.

순환에 속하지 않는 원소에 대해서는 $\sigma$과 $\tau$ 모두 그것을 고정한다. 따라서 $\sigma \tau =\iota$이다. $■$

예제 8.15. $(1352{)}^{-1}=(2531)=(1253)$ (같은 순환, 다른 시작점).

정리 8.16 (서로소 순환은 가환이다)

$\alpha$과 $\beta$가 서로소 순환이면 $\alpha \beta =\beta \alpha$이다.

증명

$\alpha =(a_1\cdots a_j)$와 $\beta =(b_1\cdots b_k)$가 서로소라 하자. 모든 $x$에 대하여 $(\alpha \beta )(x)=(\beta \alpha )(x)$임을 확인한다.

경우 1: 어떤 $i$에 대하여 $x=a_i$ (즉 $x$가 $\alpha$의 순환 안에 있는 경우). $\alpha$와 $\beta$가 서로소이므로 $\beta$는 $a_i$을 고정하며, 따라서 $\beta (a_i)=a_i$이다. 또한 $\alpha (a_i)=a_{i+1}$이고 (지수는 $j$을 법으로 한다), $\beta$는 $a_{i+1}$도 고정한다. 그러면:

$$(\alpha \beta )(a_i)=\alpha (\beta (a_i))=\alpha (a_i)=a_{i+1},$$ $$(\beta \alpha )(a_i)=\beta (\alpha (a_i))=\beta (a_{i+1})=a_{i+1}.$$

경우 2: 어떤 $i$에 대하여 $x=b_i$ (대칭적인 논증). 양변 모두 $b_{i+1}$를 준다.

경우 3: $x$이 두 순환 중 어디에도 속하지 않는 경우. $\alpha$과 $\beta$ 모두 $x$를 고정하므로 두 합성 모두 $x$을 고정한다.

모든 경우에 $(\alpha \beta )(x)=(\beta \alpha )(x)$이다. $■$

정리 8.17 (순환의 위수)

$k$-순환의 위수는 $k$이다.

증명

$\sigma =(a_1{a}_2\cdots a_k)$라 하자. 그러면 ${\sigma }^t(a_1)=a_{1+t\mathrm{mod}k}$이다. (여기서 지수를 순환적으로 매긴다: $a_{k+1}=a_1$ 등.) 이것이 $a_1$과 같을 필요충분조건은 $k\mid t$이다. 이를 만족하는 가장 작은 양의 $t$은 $k$이다. $■$

정리 8.18 (치환의 위수)

$\sigma ={\gamma }_1{\gamma }_2\cdots {\gamma }_r$이 서로소 순환 분해이고 순환들의 길이가 $m_1,m_2,\dots ,m_r$이면

이다.

증명

${\gamma }_i$들이 서로소이므로 가환이다 (정리 8.16). 따라서

$${\sigma }^t={\gamma }_1^t{\gamma }_2^t\cdots {\gamma }_r^t.$$

이다. 이제 ${\sigma }^t=\iota$일 필요충분조건은 각 $i$에 대하여 ${\gamma }_i^t=\iota$인 것이다 (순환들이 서로소인 원소 집합 위에서 작용하기 때문이다: ${\gamma }_i^t$가 ${\gamma }_i$의 받침(support) 위에서 항등원일 필요충분조건은 치환으로서 ${\gamma }_i^t=\iota$인 것이고, ${\gamma }_i$들은 서로소인 받침을 가진다).

정리 8.17에 의해 ${\gamma }_i^t=\iota$일 필요충분조건은 $m_i\mid t$이다. 모든 $m_i$으로 나누어지는 가장 작은 양의 $t$은 $\mathrm{lcm}(m_1,\dots ,m_r)$이다. $■$

예제 8.19. 치환 $\sigma =(123)(45)(6789)\in S_9$는 서로소 순환 길이가 $3,2,4$이다. 따라서

예제 8.20. 치환 $\tau =(12)(34567)\in S_7$은 순환 길이가 $2,5$이다. 따라서

§8.6 모든 치환은 전위의 곱이다

정리 8.21 (순환의 전위 분해)

모든 $k$-순환은 전위의 곱으로 쓸 수 있다.

증명

양변이 모든 원소에서 일치함을 확인하여 이를 증명한다.

$\sigma =(a_1{a}_2\cdots a_k)$라 하고 $\rho =(a_1{a}_k)(a_1{a}_{k-1})\cdots (a_1{a}_2)$라 하자.

$a_1$에서: 가장 오른쪽 전위 $(a_1{a}_2)$은 $a_1\mapsto a_2$로 보낸다. $a_2\ne a_1$이고 $a_2$은 나머지 전위 $(a_1{a}_3),\dots ,(a_1{a}_k)$ 중 어느 것의 두 번째 성분으로도 나타나지 않으므로 (이들 각각은 $a_1$과, $j\ge 3$인 다른 원소 $a_j$만을 움직인다), 나머지 전위들은 모두 $a_2$을 고정한다. 따라서 $\rho (a_1)=a_2=\sigma (a_1)$이다. $✓$

$2\le i\le k-1$인 $a_i$에서: 가장 오른쪽 전위 $(a_1{a}_2)$은 $a_i$을 고정한다 ($i\ge 2$이고 $a_i\ne a_1$이므로). 마찬가지로 $(a_1{a}_3),\dots ,(a_1{a}_{i-1})$도 모두 $a_i$을 고정한다. 그러면 $(a_1{a}_i)$은 $a_i\mapsto a_1$로 보낸다. 그런 다음 $(a_1{a}_{i+1})$은 $a_1\mapsto a_{i+1}$로 보낸다. 나머지 전위 $(a_1{a}_{i+2}),\dots ,(a_1{a}_k)$은 모두 $a_{i+1}$을 고정한다. 따라서 $\rho (a_i)=a_{i+1}=\sigma (a_i)$이다. $✓$

$a_k$에서: 전위 $(a_1{a}_2),\dots ,(a_1{a}_{k-1})$은 모두 $a_k$을 고정한다. 그런 다음 $(a_1{a}_k)$은 $a_k\mapsto a_1$로 보낸다. 왼쪽에는 전위가 없다. 따라서 $\rho (a_k)=a_1=\sigma (a_k)$이다. $✓$

순환에 속하지 않는 원소에서: 모든 전위가 그러한 원소를 고정하므로 $\rho$도 그것들을 고정한다. $✓$

$\sigma$와 $\rho$가 모든 원소에서 일치하므로 $\sigma =\rho$이다. $■$

따름정리 8.22

$S_n$ ($n\ge 2$)의 모든 치환은 전위의 곱으로 쓸 수 있다.

증명

치환을 서로소 순환의 곱으로 쓴다 (정리 8.13). 각 순환에 정리 8.21을 적용한다. 그 결과로 얻은 전위의 곱은 원래 치환과 같다. $■$

예제 8.23. $(13524)$을 전위의 곱으로 표현하라.

정리 8.21에 의해:

검산. 각 원소에 오른쪽에서 왼쪽으로 적용한다.

전위 분해는 유일하지 않다

같은 치환을 서로 다른 전위의 곱으로 표현할 수 있다. 예를 들어 $(123)=(13)(12)=(23)(13)$이다. 유일한 것은 홀짝성(parity) (전위의 개수가 짝수인지 홀수인지)이다. 이는 9장에서 전개될 것이다.

§8.7 케일리 정리

정리 8.24 (케일리 정리)

모든 군 $G$는 어떤 대칭군의 부분군과 동형이다. 더 정확히는, $G$는 $S_G$ ($G$의 바탕집합의 모든 치환으로 이루어진 군)의 부분군과 동형이다. $G$가 $|G|=n$인 유한군이면 $G$는 $S_n$의 부분군과 동형이다.

증명 (왼쪽 정칙 표현을 통하여)

각 $g\in G$에 대하여 왼쪽 곱셈 사상(left multiplication map) ${\lambda }_g:G\to G$을

$${\lambda }_g(x)=gx.$$

로 정의한다.

1단계. ${\lambda }_g$은 $G$의 치환이다.

단사: ${\lambda }_g(x)={\lambda }_g(y)$이면 $gx=gy$이므로 왼쪽 소거에 의해 $x=y$이다.

전사: 임의의 $y\in G$에 대하여 ${\lambda }_g(g^{-1}y)=g(g^{-1}y)=y$이다.

따라서 ${\lambda }_g\in S_G$이다.

2단계. $\Phi :G\to S_G$을 $\Phi (g)={\lambda }_g$로 정의한다.

3단계. $\Phi$는 준동형사상이다. 모든 $g,h\in G$과 모든 $x\in G$에 대하여:

$${\lambda }_{gh}(x)=(gh)x=g(hx)={\lambda }_g({\lambda }_h(x))=({\lambda }_g\circ {\lambda }_h)(x).$$

따라서 $\Phi (gh)={\lambda }_{gh}={\lambda }_g\circ {\lambda }_h=\Phi (g)\circ \Phi (h)$이다.

4단계. $\Phi$는 단사이다. $\Phi (g)=\Phi (h)$, 즉 ${\lambda }_g={\lambda }_h$이라 하자. 그러면 모든 $x\in G$에 대하여 $gx=hx$이다. $x=e$로 두면 $g=h$를 얻는다.

결론. $\Phi$는 단사 준동형사상이므로 $G\cong \Phi (G)\le S_G$이다. $|G|=n$이면 $G$의 원소들을 $\{1,\dots ,n\}$로 표시하여 $\Phi (G)\le S_n$을 실현할 수 있다. $■$

예제 8.25. ${\mathbb{Z}}_3=\{0,1,2\}$의 왼쪽 정칙 표현.

따라서 $\Phi ({\mathbb{Z}}_3)=\{\iota ,(012),(021)\}\le S_3$이고, 실제로 ${\mathbb{Z}}_3\cong ⟨(012)⟩$이다.

§8.8 $S_4$과 $S_5$에서의 풀이 계산

계산 8.26 ($S_4$에서의 곱, 양쪽 순서)

$\alpha =(123)$과 $\beta =(24)$을 $S_4$에서 택하자.

$\alpha \beta$: $\beta$를 먼저 적용한 뒤 $\alpha$을 적용한다.

따라서 $\alpha \beta =(1243)$이다.

$\beta \alpha$: $\alpha$을 먼저 적용한 뒤 $\beta$를 적용한다.

따라서 $\beta \alpha =(1423)$이다.

관찰:

• $\alpha \beta \ne \beta \alpha$이며, 비가환성을 확인해 준다.
• $\mathrm{ord}(\alpha \beta )=4$ (이는 $4$-순환이다).
• $\mathrm{ord}(\beta \alpha )=4$ (역시 $4$-순환이다).
• $(\alpha \beta {)}^{-1}=(3421)=(1342)$.

계산 8.27 ($S_5$에서의 역원)

$\sigma =(135)(24)\in S_5$라 하자.

그러면 ${\sigma }^{-1}=(153)(24)$이다 (각 순환을 뒤집는다; 전위의 역원은 자기 자신이다).

검산: $\sigma {\sigma }^{-1}$:

잠깐 — 신중해야 한다. $\sigma =(135)(24)$은 $(24)$을 먼저 적용한 뒤 $(135)$를 적용함을 의미한다. 따라서 ${\sigma }^{-1}=(24{)}^{-1}(135{)}^{-1}=(24)(153)$이다.

그러나 $(135)$과 $(24)$가 서로소이므로 가환이다. 따라서

위수: $\mathrm{ord}(\sigma )=\mathrm{lcm}(3,2)=6$.

계산 8.28 ($S_5$에서의 더 긴 예제)

$\sigma =(124)$과 $\tau =(13)(25)$를 $S_5$에서 택하자.

$\sigma \tau$: $\tau$를 먼저 적용한 뒤 $\sigma$을 적용한다.

따라서 $\sigma \tau =(13254)$로 $5$-순환이다.

$\mathrm{ord}(\sigma \tau )=5$.

$\tau \sigma$: $\sigma$을 먼저 적용한 뒤 $\tau$를 적용한다.

따라서 $\tau \sigma =(15243)$로 역시 $5$-순환이다. 다시 $\mathrm{ord}(\tau \sigma )=5$이다.

계산 8.29 ($S_5$에서 표기법 변환)

두 줄 형태에서 시작한다.

순환 표기법으로 변환한다.

• $1\to 2\to 5\to 1$. 순환: $(125)$.
• $3\to 4\to 3$. 순환: $(34)$.

따라서 $\sigma =(125)(34)$이다.

위수: $\mathrm{lcm}(3,2)=6$.

역원: ${\sigma }^{-1}=(152)(34)=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 5& 1& 4& 3& 2\end{array}\right)$.

§8.9 $S_n$에서의 켤레

정리 8.30 (켤레는 순환을 재표시한다)

임의의 $\tau \in S_n$와 임의의 순환 $(a_1{a}_2\cdots a_k)\in S_n$에 대하여

이다.

증명

$\sigma =(a_1{a}_2\cdots a_k)$라 하자. $\tau \sigma {\tau }^{-1}$와 $(\tau (a_1)\tau (a_2)\cdots \tau (a_k))$가 모든 원소에서 일치함을 보여야 한다.

경우 1: 어떤 $1\le i\le k$에 대하여 $x=\tau (a_i)$. 그러면

$$(\tau \sigma {\tau }^{-1})(\tau (a_i))=\tau (\sigma (a_i))=\tau (a_{i+1}),$$

이고, 여기서 지수는 $k$을 법으로 한다 (따라서 $a_{k+1}=a_1$). 한편,

$$(\tau (a_1)\cdots \tau (a_k))\text{ sends }\tau (a_i)\mapsto \tau (a_{i+1}).$$

이다. 이들은 일치한다. $✓$

경우 2: $x\notin \{\tau (a_1),\dots ,\tau (a_k)\}$. 그러면 ${\tau }^{-1}(x)\notin \{a_1,\dots ,a_k\}$이다 ($\tau$이 전단사이므로). 따라서 $\sigma$는 ${\tau }^{-1}(x)$을 고정하며, 그러므로

$$(\tau \sigma {\tau }^{-1})(x)=\tau (\sigma ({\tau }^{-1}(x)))=\tau ({\tau }^{-1}(x))=x.$$

이다. 순환 $(\tau (a_1)\cdots \tau (a_k))$도 $x$를 고정한다. $✓$

양변이 모든 $x\in \{1,\dots ,n\}$에서 일치하므로 그것들은 같다. $■$

따름정리 8.31 (켤레는 순환형을 보존한다)

$\sigma$가 서로소 순환 분해 $\sigma =(a_1\cdots a_{j_1})(b_1\cdots b_{j_2})\cdots$을 가지면

이다. 특히 $\tau \sigma {\tau }^{-1}$은 $\sigma$와 같은 순환형(cycle type)을 가진다.

증명

켤레가 곱에 대하여 분배되므로 ($\tau ({\sigma }_1{\sigma }_2){\tau }^{-1}=(\tau {\sigma }_1{\tau }^{-1})(\tau {\sigma }_2{\tau }^{-1})$), 분해의 각 순환에 정리 8.30을 적용하면 결과를 얻는다. $\tau$이 전단사이므로 순환 길이는 변하지 않는다. $■$

역 (증명 없이 서술함)

$S_n$에서 두 치환이 켤레일 필요충분조건은 그것들이 같은 순환형을 가지는 것이다. (이 역은 한 순환들의 집합을 다른 집합으로 보내는 특정한 $\tau$을 구성하는 별도의 논증을 필요로 한다.)

예제 8.32. $S_5$에서 $\sigma =(123)(45)$과 $\tau =(13425)$을 택하자.

재표시 정리를 이용하여 $\tau \sigma {\tau }^{-1}$을 계산한다.

이는 순환형 $(3,2)$을 가지며, 이는 $\sigma$과 같다. $✓$

§8.10 $S_n$의 부분군으로서의 이면체군 $D_n$

정의 8.33 (이면체군)

이면체군(dihedral group) $D_n$은 정 $n$각형의 대칭으로 이루어진 군이다. 그 위수는 $2n$이며, 각 $2\pi /n$의 회전 $r$과 반사 $s$에 의해 생성되고, 다음 관계식을 따른다.

$D_n$의 원소들은 $\{e,r,r^2,\dots ,r^{n-1},s,sr,s{r}^2,\dots ,s{r}^{n-1}\}$이다.

$D_n$을 $S_n$으로 매장하기

정 $n$각형의 꼭짓점을 $1,2,\dots ,n$로 표시한다. $n$각형의 각 대칭은 이 꼭짓점들을 치환하며, 이는 단사 준동형사상 $D_n\hookrightarrow S_n$을 준다.

예제 8.34 ($D_3\cong S_3$)

꼭짓점이 $1,2,3$인 정삼각형 (시계 방향으로 표시)에 대하여:

이들은 정확히 $S_3$의 $3!=6$개 원소이므로 $D_3\cong S_3$이다.

$S_3\cong D_3$의 케일리 표

$e=\iota$, ${\rho }_1=(123)$, ${\rho }_2=(132)$, ${\mu }_1=(23)$, ${\mu }_2=(13)$, ${\mu }_3=(12)$의 표기를 사용하여:

표 읽기: $\alpha$ 행, $\beta$ 열의 성분은 $\alpha \beta$이다 ($\beta$을 먼저 적용).

한 성분의 검산: ${\rho }_1{\mu }_1=(123)(23)$. $(23)$를 먼저 적용한다: $1\to 1\to 2$, $2\to 3\to 1$, $3\to 2\to 3$. 잠깐: $1\stackrel{(23)}{\to }1\stackrel{(123)}{\to }2$, $2\stackrel{(23)}{\to }3\stackrel{(123)}{\to }1$, $3\stackrel{(23)}{\to }2\stackrel{(123)}{\to }3$. 따라서 ${\rho }_1{\mu }_1=(12)={\mu }_3$이다. $✓$

§8.11 $S_3$의 부분군 구조

$S_3$는 위수가 $6$이다. 라그랑주 정리(Lagrange’s theorem)에 의해 부분군의 위수는 $6$을 나누어야 하므로 $1,2,3$ 또는 $6$일 수 있다.

$S_3$의 모든 부분군:

총 6개의 부분군.

부분군 격자

그림: $S_3$의 부분군 격자.

포함 순서는 다음과 같다.

• $\{e\}\le A_3\le S_3$
• $\{e\}\le \{e,(12)\}\le S_3$
• $\{e\}\le \{e,(13)\}\le S_3$
• $\{e\}\le \{e,(23)\}\le S_3$

$A_3$은 위수 $3$의 유일한 부분군이며, $S_3$에서 **정규(normal)**임에 유의하라 (지수가 $2$이다). 위수 $2$의 세 부분군은 정규가 아니다 (그것들은 서로 켤레이다).

§8.12 표준적 함정과 흔한 실수

치환 계산에서의 함정

함정 1: 합성 순서. 곱 $\sigma \tau$은 “$\tau$를 먼저 적용한 뒤 $\sigma$를 적용함”을 의미한다. 이것이 가장 흔한 오류의 원천이다. 곱을 계산할 때마다 반사적으로 익숙해질 때까지 사슬 $x\stackrel{\tau }{\to }\cdots \stackrel{\sigma }{\to }\cdots$를 명시적으로 적어라.

함정 2: 서로소가 아닌 순환은 가환이 아니다. 순환이 한 원소를 공유하면 그 곱은 순서에 의존한다. 예를 들어:

확인: $(12)(13)$: $1\stackrel{(13)}{\to }3\stackrel{(12)}{\to }3$, $3\stackrel{(13)}{\to }1\stackrel{(12)}{\to }2$, $2\stackrel{(13)}{\to }2\stackrel{(12)}{\to }1$. 따라서 $(12)(13)=(132)$이다. 그러나 $(13)(12)$: $1\stackrel{(12)}{\to }2\stackrel{(13)}{\to }2$, $2\stackrel{(12)}{\to }1\stackrel{(13)}{\to }3$, $3\stackrel{(12)}{\to }3\stackrel{(13)}{\to }1$. 따라서 $(13)(12)=(123)$이다.

함정 3: 위수는 최소공배수이지 합이 아니다. $(123)(45)$의 위수는 $\mathrm{lcm}(3,2)=6$이지 $3+2=5$가 아니다.

함정 4: 순환 표기법은 모군에 대해 모호하다. 순환 $(123)$은 $S_3$, $S_4$, $S_5$ 등에 속할 수 있다. 모군(ambient group)은 셈 논증에서 중요하다 (예: 주어진 순환형을 가지는 치환이 몇 개인가).

함정 5: 두 줄 표기법에서 고정점을 잊는 것. 순환 표기법으로 변환할 때 흔한 오류는 실제로는 고정되는 원소를 순환에 나열하는 것이다. 항상 확인하라: 그 원소가 한 단계 만에 자기 자신으로 돌아오는가? 그렇다면 그것은 고정점이며 순환 표기법에서 생략된다.

§8.13 랭의 구조적 관점

군 작용으로서의 치환군

랭(Lang)의 Algebra에서 치환군의 개념은 **군 작용(group action)**의 일반 이론에 포섭된다. 군 $G$이 집합 $X$ 위에 작용한다는 것은 준동형사상 $\phi :G\to S_X$가 존재함을 뜻한다. 상 $\phi (G)\le S_X$은 치환군이고, 핵 $\ker \phi$은 그 작용에서 $G$가 얼마나 “잃어버려지는지”를 측정한다.

이 관점에서:

• $X$의 치환은 $S_X$의 원소이다.
• $\sigma$에 의한 $x$의 궤도는 $⟨\sigma ⟩$가 $X$ 위에 작용할 때 $x$의 궤도이다.
• 서로소 순환 분해는 순환 부분군 $⟨\sigma ⟩$에 의한 $\{1,\dots ,n\}$의 궤도 분해이다.
• $S_n$에서의 켤레는 내부자기동형사상에 의한 $S_n$의 자기 자신 위로의 자연스러운 작용이다: $\sigma \mapsto \tau \sigma {\tau }^{-1}$. 재표시 정리(정리 8.30)는 이 작용이 단지 각 순환의 성분들을 재표시함을 말해 준다.

충실한 작용으로서의 케일리 정리

케일리 정리는 다음을 말한다: 모든 군 $G$는 왼쪽 곱셈에 의해 자기 자신 위에 충실하게(faithfully) (즉 자명한 핵을 가지고) 작용한다. 랭의 언어로 왼쪽 정칙 표현 $\lambda :G\to S_G$은 집합 $G$ 위의 $G$의 충실한 군 작용이다.

이 관점은 다음을 명확히 한다:

1. 케일리 정리의 표현 $G\hookrightarrow S_n$는 대개 결코 효율적이지 않다 (위수 $n$의 군이 위수 $n!$의 군에 매장된다). 작은 충실한 표현을 찾는 것은 별개의 문제이다.
2. 진정한 내용은 **치환 표현이 보편적(universal)**이라는 것이다: 임의의 추상적인 군론적 명제는 원리상 대칭군 안에서의 계산으로 검증될 수 있다.
3. 순환형은 켤레 불변량이며, $S_n$의 켤레류는 $n$의 분할(partition)에 의해 색인된다. 표현론과 조합론 사이의 이 연결은 이후의 강의에서 상당히 깊어진다.

§8.15 플래시카드용 요약

암기해야 할 핵심 사실

1. **$|S_n|=n!$**이고 $n\ge 3$일 때 $S_n$는 비가환이다.
2. 합성 약속: $(\sigma \tau )(x)=\sigma (\tau (x))$ — $\tau$를 먼저 적용한다.
3. 서로소 순환 분해는 존재하며 유일하다 (순환의 순서를 무시하면).
4. 순환의 역원: $(a_1{a}_2\cdots a_k{)}^{-1}=(a_k{a}_{k-1}\cdots a_1)$.
5. 서로소 순환은 가환이다. 겹치는 순환은 가환이 아니다.
6. $k$-순환의 위수는 $k$이다.
7. 치환의 위수는 서로소 순환 길이들의 $=\mathrm{lcm}$이다.
8. 전위 분해: $(a_1\cdots a_k)=(a_1{a}_k)(a_1{a}_{k-1})\cdots (a_1{a}_2)$.
9. 케일리 정리: 모든 군 $G$는 $g\mapsto {\lambda }_g$ (왼쪽 곱셈)을 통하여 $S_G$에 매장된다.
10. 켤레는 재표시한다: $\tau (a_1\cdots a_k){\tau }^{-1}=(\tau (a_1)\cdots \tau (a_k))$.
11. 켤레인 치환은 같은 순환형을 가진다 (그리고 $S_n$에서는 그 역도 성립한다).
12. $D_3\cong S_3$, $|D_n|=2n$, 그리고 $D_n\le S_n$.
13. $S_n$은 $\{(12),(13),\dots ,(1n)\}$에 의해 생성된다.
14. $S_n$에서 $k$-순환의 개수: $\frac{n!}{k(n-k)!}$.

8장을 떠나기 전에 숙달해야 할 것