[현대대수학] 8. 치환군

치환

집합 $A$가 있을 때 일대일 함수 $\sigma : A \rightarrow A$를 $A$의 치환(Permutation)이라고 한다.

 

쉽게 말해 정의역 원소의 순서가 있다고 가정할 때 그 순서를 바꾸는 함수를 치환이라고 하는 것이다.

$\{ 1 \space 2 \space 3 \} \rightarrow \{ 2 \space 3 \space 1\}$가 치환의 예이다.

위의 예시를 기호로 나타내면 다음과 같다.

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

(행렬같아보이지만 행렬이 아니다!)

 

$\sigma (1) = 2$

$\sigma (2) = 3$

$\sigma (3) = 1$

인 함수가 된다.

 

서로 다른 치환을 (곱)연산할 수 있다.

$\sigma = \begin{pmatrix} 1&2&3 \\ 2&3&1 \end{pmatrix} \space \tau = \begin{pmatrix} 1&2&3 \\ 2&1&3 \end{pmatrix}$라고 하면

$\sigma \tau = \begin{pmatrix} 1&2&3 \\ 2&3&1 \end{pmatrix} \begin{pmatrix} 1&2&3 \\ 2&1&3 \end{pmatrix} = \begin{pmatrix} 1&2&3 \\ 3&2&1 \end{pmatrix}$가 된다.

여기서 중요한점은 $\tau$부터 계산한다는 점이다.

합성함수 개념이기 때문에 변수로부터 가까운 것부터 연산을 한다.

즉 $\sigma \tau(1) = \sigma( \tau(1)) = \sigma(2) = 3$ 이다.

 

$A$가 공집합이 아닌 집합이고 $S_A$ 를 $A$의 모든 치환의 모임이라고 하면 $S_A$는 치환 곱셈 아래에서 군을 이룬다. $\langle S_A, \cdot \rangle$

1. 치환 곱셈은 합성함수로 볼 수 있으므로 결합법칙이 성립한다.

2. 치환의 항등원은 존재한다. 그 항등원은 $a \in A$에 대해 $\sigma(a) = a$인 치환 $\sigma$이다.

3. 치환의 역원은 존재한다. 그 역원은 $a \in A$에 대해 $\tau(\sigma(a)) = a$인 치환 $\tau$이다.

 

치환 일반적으로 $S_n$은 정의역이 $\{ 1, 2, 3, \cdots , n\}$인 치환이고 $S_A$는 정의역이 집합 $A$인 치환이다.

치환 $S_A, S_B$가 있고 일대일함수 $f : A \rightarrow B$가 있어 $A,B$가 같은 농도를 가진다면 $S_A, S_B$는 서로 동형이다.

 

$f:A \rightarrow B$가 함수이고 $H$가 $A$의 부분군이라 할 때 $f$아래에서 $H$의 상은 $\{ f(h) | h \in H \}$이고 $f[H]$로 나타낸다.

함수의 입력이 단일원소라면 $f(h)$같이 나타내고 군일 때 $f[H]$로 나타낸다.

 

https://www.acmicpc.net/problem/16289

16289번: Path Embedding

이 문제에 치환이 나온다.