[군론](9)[치환군 & 대칭군]

 

치환(permutation)

permutation of A = σ: A -> A인 전단사함수 σ
참고) 보통 permutation을 확통에서 먼저 봐서
    순열이라고 알고 있는데
    군론에서는 치환이라는 뜻으로 사용함
$$\sigma = \begin{pmatrix} 1 & 2 & 3 \ \sigma(1) & \sigma(2) & \sigma(3) \end{pmatrix}$$

 

참고) 뭔가 행렬처럼 생겼다고 해서 행렬 연산 시도하면 안됨

 

치환군(permutation group)

A의 순열을 모은 군
연산: º
    σ𝜏 = σº𝜏 = σ(𝜏(n))

대칭군 (symmetric group)

$S_n$ = A의 n개의 원소에 대한 모든 치환을 모은 군

1. closure?
   전단사함수의 합성 또한 전단사함수
   어짜피 정의역=치역인 전단사함수이므로
   연산을 했을 때도 치환군 안에 들어간다
2. well-defined? associative?
   연산 º는 함수의 합성이므로, 항상 associative를 만족하며,
       σº(𝜏º𝛾) = (σº𝜏)º𝛾 = σ(𝜏(𝛾(x))
   전단사함수의 합성은 전단사함수이므로, well-defined이다
3. Identity element?
   $I_n(x) = x$가 존재하여
   $σ \circ I_n = I_n \circ σ = σ$
4. Inverse element?
   Sn은 모든 치환을 모은 군이므로, 임의의 σ에 대해 $σ^{-1}$도 포함한다
   따라서 $σ \circ σ^{-1} = σ^{-1} \circ σ = I_n$이므로, 임의의 원소에 대해 역원 존재

-> 따라서 $S_n$은 군이다.

 

• 대칭군의 크기: $|S_n| = n!$
  참고) 군의 위수가 6을 넘어가면 아벨군이 아닐수도 있는데
      대칭군에서는 n \ge 3, 즉, 위수가 6을 넘어가면 항상 아벨군이 아님

 

궤도와 순환

원소 x의 궤도 (orbit of x)
    ${\sigma^n(x) \ | \ n \in \mathbb{Z}}$
        $x = \sigma \circ \sigma \circ ... \circ \sigma(x)$
    만약 A가 유한집합이면 궤도는 유한하다

 

순환 (cycle)
    같은 순환 안에 있는 원소는 같은 순환을 갖는다
    A가 유한집합일때, 각 순환은 서로소집합이다
    서로소집합끼리는 교환법칙이 성립한다

• 순환의 길이
  길이가 k인 순환을 k-cycle이라 부른다
  |k-cycle| = k
      참고) 길이가 1인 순환은 fixed point라고 하며 종종 무시됨
  치환의 위수는 cycle들의 LCM이다

예) $S_n \text{의 원소 }\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\ 2 & 3 & 1 & 5 & 4 \end{pmatrix}$에서 cycle form, 위수를 구하시오
    orbit of 1 = $1 \to 2 \to 3$ = (1, 2, 3)
    orbit of 4 = $4 \to 5$ = (4, 5)
    $\sigma = (1,2,3)(4,5) = (4, 5)(1,2,3)$
    $|\sigma| = |(1,2,3)(4,5)| = LCM(3, 2) = 6$

 

cycle의 계산 팁

1. 서로소인 cycle끼리는 교환법칙이 성립
2. cycle의 역원은 숫자의 순서를 뒤집으면 됨
3. cycle의 길이만큼 제곱하면 항등치환 ι이 됨
   왜냐하면 길이만큼 연산을 하면
   다시 처음 자기 자신으로 돌아오기 때문
       $\sigma^m를 \sigma^{kp+q}$로 쪼개서 더 간단하게 푸셈
4. n제곱은 n칸씩 뛰어넘으며 읽기
   이떄, n과 k-cycle의 길이가 서로소가 아니라면, 사이클이 쪼개짐
   쪼개지는 cycle의 수 = $\gcd(n, k)$
   새롭게 만들어지는 각 cycle의 길이 = $\frac{n}{\gcd(n, k)}$
5. 켤례연산 $\tau \sigma \tau^{-1} = (\tau(\sigma_1), \ \tau(\sigma_2), \ ..., \ \tau(\sigma_k))$
   $\tau \sigma \tau^{-1}$에 $\tau(a_i)$를 넣어보면 됨
   $\tau \sigma \tau^{-1}(\tau(a_i)) = \tau \sigma(a_i) = \tau (a_{i+1})$
   즉, $\tau \sigma \tau^{-1}: \ a_i \to a_{i+1}$