궤도, 순환치환, 교대군

궤도, 순환치환, 교대군

(Orbits, Cycles, and the alternating group)

현대대수학1 <제9절>

이상준 교수

(덕성여대 수학과)

교재 : 현대대수학(제7판)

John B. Fraleigh 지음, 강영욱, 강병련 옮김 강의 슬라이드 : 이상준, 조유진(13)

궤도 (Orbits)

„

정의9.1: 𝜎를 집합 A의 치환이라 하고, 𝑎 ∈ 𝐴 라 하자.

„

𝒐𝒓𝒃

𝒂 ≔ { 𝑎, 𝜎 𝑎 , 𝜎

𝑎 , 𝜎

𝑎 , ⋯ }

„

𝒐𝒓𝒃

𝒂 를 a를 포함하는 𝝈의 궤도(orbits)라고 한다.

„

예제 9.3: 𝜎 = 1 2 3 4 5 6 7 8 3 8 6 7 4 1 5 2

„

𝑜𝑟𝑏

1 = 1, 3, 6, 1, 3, 6, ⋯ = 𝑜𝑟𝑏

3 = 𝑜𝑟𝑏

6

„

𝑜𝑟𝑏

2 = 2, 8 = 𝑜𝑟𝑏

8

„

𝑜𝑟𝑏

4 = 4, 7, 5 = 𝑜𝑟𝑏

7 = 𝑜𝑟𝑏

5

„

예제: 𝜏 = 1 2 3 4 5 6 7

3 6 4 1 5 2 7 일 때, 𝜏의 모든 궤도를 찾아라.

„

풀이: (연습)

„

예제(답): 𝜏 = 1 2 3 4 5 6 7

3 6 4 1 5 2 7 일 때, 𝜏의 모든 궤도를 찾아라.

„

𝑜𝑟𝑏

1 = 1, 3, 4, 1, 3, 4, ⋯ = 𝑜𝑟𝑏

3 = 𝑜𝑟𝑏

4

„

𝑜𝑟𝑏

2 = 2, 6, 2, 6, ⋯ = 𝑜𝑟𝑏

6

„

𝑜𝑟𝑏

5 = 5

„

𝑜𝑟𝑏

7 = 7

„

따라서 {1, 3, 4} , {2, 6} , {5} , {7}

관찰

„

관찰: 𝐴 = 1, 2, 3, 4, 5, 6, 7, 8 를 각 궤도로 나누면…

„

= 1, 3, 6 ∪ 2, 8 ∪ 4, 7, 5

„

각각의 원소가 모두 나타나며, 한번씩만 나타난다.

„

→

순환치환 (Cycles)

„ 정의1: 치환 𝜎 ∈ 𝑆_C 이 두 원소 이상을 포함하는 궤도가 하나뿐일 때 𝜎 를 순환치환(cycle)이라 한다.

„ 예제: 𝜎 = 1 2 3 4 3 2 1 4 = (1,3) : 순환치환

„ 𝜏 = 1 2 3 4

3 4 1 2 = (1,3)(2,4) : 순환치환이 아니다.

„ 정의2: 순환치환의길이(length)는 가장 큰 궤도에 포함된 원소의 개수다.

„ 예제: 𝜎 = 1 2 3 4 5

3 2 5 1 4 = ( 1,3,5,4 ) 의 길이는?

„ 𝜎 의 길이는 4이다.

치환을 순환치환의 곱으로 표현

„ 예제 9.7: 𝜎 = 1 2 3 4 5 6 7 8

3 8 6 7 4 1 5 2 을 순환치환들로 표현하면…

„ =( 1, 3, 6 )( 2, 8 )( 4, 7, 5 )

„ 이 순환치환들은 서로 소(disjoint)이다.

„ 예제: 1 2 3 4 5 6 7 1 5 4 3 7 6 2 =

„ 예제: 1 2 3 4 5 6 3 5 4 6 2 1 =

„ 정리 9.8: 모든 치환 𝜎 ∈ 𝑆_C은 서로 소인 순환치환들의 곱으로 나타낸다.

„ 증명:

„𝐵_G, 𝐵_., ⋯ , 𝐵_H를 𝜎의 궤도라 하자.

„ 𝜇_J 𝑥 = L 𝜎 𝑥 𝑥 ∈ 𝐵_J 인 경우

𝑥 𝑥 ∉ 𝐵_J 인 경우 로 정의하자.

„ 사실:

„ 𝜇_J 는 순환치환이다.

„ 𝜇_J 는 서로 소이다.

„ 주장: 𝜎 = 𝜇_G𝜇_.⋯ 𝜇_H

„증명: 𝜇_G𝜇_.⋯ 𝜇_H 𝑥 = 𝜎(𝑥).

„ 정의9.11: 길이가 2인 순환치환을 호환(transposition)이라고 한다.

„ 예제: ( 1, 2 ) , ( 3, 5 ) : 호환

„( 1, 3, 4 ) : 호환이 아니다.

„ 보조정리: 𝑎_G, 𝑎_., ⋯ ,𝑎_C = (𝑎_G ,𝑎_C)(𝑎_G, 𝑎_COG)⋯ (𝑎_G, 𝑎_/)(𝑎_G, 𝑎_.)

„즉, 순환치환은 호환의 곱으로 쓸 수 있다.

„ 증명: (다음 페이지에)

„ 예제: ( 1 3 5 ) = ( 1 5 )( 1 3 )

„( 2 4 6 7 ) =

„ 보조정리: 𝑎_G, 𝑎_., ⋯ ,𝑎_C = (𝑎_G ,𝑎_C)(𝑎_G, 𝑎_COG)⋯ (𝑎_G, 𝑎_/)(𝑎_G, 𝑎_.)

„ 증명:

„ ① 𝑘 ∉ {𝑎_G, 𝑎_., ⋯ , 𝑎_C}

„(𝑎_G, 𝑎_., ⋯ , 𝑎_C)(𝑘) = 𝑘

„ 𝑎_G ,𝑎_C 𝑎_G, 𝑎_COG ⋯ 𝑎_G, 𝑎_/ 𝑎_G, 𝑎_. 𝑘 = 𝑘

„ ② 𝑘 = 𝑎_J ≠ 𝑎_C

„(𝑎_G, 𝑎_., ⋯ , 𝑎_C)(𝑎_J)=𝑎_JRG

„ 𝑎_G ,𝑎_C 𝑎_G, 𝑎_COG ⋯ 𝑎_G, 𝑎_/ 𝑎_G, 𝑎_. 𝑎_J

„= 𝑎_G ,𝑎_C 𝑎_G, 𝑎_COG ⋯ 𝑎_G, 𝑎_J 𝑎_J

„= 𝑎_G ,𝑎_C 𝑎_G, 𝑎_COG ⋯ 𝑎_G, 𝑎_JRG 𝑎_G

„= 𝑎_G ,𝑎_C 𝑎_G, 𝑎_COG ⋯ 𝑎_G, 𝑎_JR. 𝑎_JRG = 𝑎_JRG

„ ③ 𝑘 = 𝑎_C

„(𝑎_G, 𝑎_., ⋯ , 𝑎_C)(𝑎_C)=𝑎_G

„ 𝑎 ,𝑎 𝑎 , 𝑎 ⋯ 𝑎 , 𝑎 𝑎 , 𝑎 𝑎 = 𝑎

„

따름정리 9.12: 적어도 두 원소를 갖는 유한집합의 모든 치환은 호환의 곱이다.

„

증명: 치환 => 서로 소인 순환치환의 곱 => 각 순환치환은 호환의 곱

„

예제:

„

𝜎 = 1 6 2 5 3 = 1 6 2 3 ( 2 5 )

„

항등치환=( 1 2 )( 1 2 )

„

𝜎 = ( 1 3 6 )( 2 4 8 )( 5 7 )

„

=

„

𝜎 = ( 1 3 5 7 )( 2 4 6 8 9 )

„

=

„ 정리 9.15: 어떤 치환 𝜎 ∈ 𝑆_C이 짝수 개의 호환의 곱으로 표현되면서 동시에 홀수 개의 호환의 곱으로 표현될 수 없다.

„ 즉, n이 짝수이고 m이 홀수 일 때

„ 𝑎_G 𝑏_G 𝑎_. 𝑏_. ⋯ 𝑎_C 𝑏_C

≠

„ 증명: (생략)

짝치환(우치환)과 홀치환(기치환)

„

정의 9.18: 어떤 치환이

짝수 개의 호환의 곱으로 표현되면

짝치환,우치환(even permutation),

홀치환,기치환(odd permutation) 이라고 한다.

„

예제:

„

항등치환=( 1 2 )( 1 2 ) : 짝치환

„

( 1 4 5 6 )( 2 1 5 ) = ( 1 6 )( 1 5 )( 1 4 )( 2 5 )( 2 1 ) : 홀치환

„

( 1 3 5 7 9 )( 2 4 6 8 ) =

„

( 1 3 6 )( 2 4 8 )( 5 7 ) =

„

정의: 𝑆

에서

𝑨

이라고 하자.

„

정리: 𝐴

은 𝑆

의 부분군이다.

„

증명:

„

목표: 𝜎

,𝜎

∈ 𝐴

이면 𝜎

𝜎

∈ 𝐴

임을 보이면 된다.

„

𝜎

= 𝑡

𝑡

⋯ 𝑡

𝜎

= 𝑡

𝑡

⋯ 𝑡

„

𝜎

𝜎

= 𝑡

𝑡

⋯ 𝑡

𝑡

𝑡

⋯ 𝑡

„

= 𝑡

𝑡

⋯ 𝑡

𝑡

⋯ 𝑡

𝑡

∈ 𝐴

교대군 (Alternating group)

▶ 정의 9.21:

𝑨

▶ 질문: 𝐵_C은 𝑆_C에서 모든 홀치환들의 집합이라 하자.

▶ 𝐵_C은 𝑆_C의 부분군인가?

▶ No! (이유는?)

▶“홀수+홀수=짝수” 이므로 닫혀있지 않다.

▶항등원이 짝치환이므로 포함되지 않는다.

▶ 질문: 𝑆_C = 𝑛 𝑛 − 1 𝑛 − 2 ⋯ 1 = 𝑛!

„ 정리: 𝑨_𝒏 = ^𝑺_𝟐^𝒏 = ^C!_.

„ 증명:

„ 𝐴_C : 𝑆_C에서 모든 짝치환들의 집합

„ 𝐵_C : 𝑆_C에서 모든 홀치환들의 집합

„ 𝐴_C과 𝐵_C 사이의 사상을 정의하자.

„ 𝜙 ∶ 𝐴_C ⟶ 𝐵_C 라고 하자.

𝜎 ⟼ (1,2)𝜎

„ 잘 정의되었는가?

„( 1, 2 )𝜎 : 홀치환 ⇒ ( 1, 2 )𝜎 ∈ 𝐵_C

„일대일함수?

„ 1, 2 𝜎_G = 1, 2 𝜎_. 이라 하자.

„소거법칙에 의해 𝜎_G = 𝜎_.

„전사함수?

„각각의 𝛼 ∈ 𝐵_C에 대해서 𝜙 1, 2 𝛼 = 1, 2 1, 2 𝛼 = 𝛼

그리고 는 짝치환이다.