치환
집합 $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
이 문제에 치환이 나온다.
'수학 > 현대대수학' 카테고리의 다른 글
[현대대수학] Sylvester 행렬과 Resultant (0) | 2023.10.14 |
---|---|
[현대대수학] 9. 궤도, 순환치환, 교대군 (0) | 2021.12.31 |
[현대대수학] 7. 생성집합 (0) | 2021.12.20 |
[현대대수학] 6. 순환군 (0) | 2021.12.14 |
[현대대수학] 5. 부분군 (0) | 2021.12.14 |