생성집합과 Cayley 다이그래프
(Generating sets and Cayley digraphs)
현대대수학1 <제7절>
이상준 교수
(덕성여대 수학과)
교재 : 현대대수학(제7판)
John B. Fraleigh 지음, 강영욱, 강병련 옮김 강의 슬라이드 : 이상준, 조유진(13)
지난시간: 한 개의 원소에 의해 생성되는 부분군에 대해 공부했다.
목표: 여러 개의 원소들에 의해 생성되는 부분군에 대해 생각해보자.
질문: a와 b를 포함하는 G의 가장 작은 부분군 H는 무엇인가?
답:
𝑎" ∈ 𝐻 (∀𝑛 ∈ ℤ)
𝑏" ∈ 𝐻
𝑎"+𝑏",𝑎"-𝑏".⋯ 𝑎",01,𝑏",0 (𝑛2∈ ℤ)(예를 들면, 𝑎3𝑏4, 𝑏3𝑎67𝑏63𝑎4, 𝑎3𝑏67𝑎8𝑏3𝑎7,⋯)
▶
정의: < 𝒂𝟏, 𝒂𝟐, ⋯ > ≔ 𝑥@"+𝑥7",⋯ 𝑥A"0 𝑥2 = 𝑎C, 𝑛2 ∈ ℤ, 𝑘 ∈ ℕ}
정리: G가 군이고, 𝑎2 ∈ 𝐺라고 하자.
H = < 𝑎@, 𝑎7, ⋯ >는 G의 부분군이다.
증명: (𝑥@"+𝑥7",⋯ 𝑥A"0)(𝑦@J+𝑦7J,⋯ 𝑦KJL)6@
= (𝑥@"+𝑥7",⋯ 𝑥A"0𝑦K6JL𝑦K6@6JL1+ ⋯ 𝑦@6J+) ∈ H.유한 생성군
정의1:< 𝒂
𝟏, 𝒂
𝟐, ⋯ >는 {𝑎
@, 𝑎7, ⋯ }에 의해 생성되는 G의 부분군이라 한다.
정의2: G = < 𝑎@, 𝑎7, ⋯ >이면, G는 {𝑎@, 𝑎7, ⋯ }에 의해 생성된다고 한다.
또한,{𝒂
𝟏, 𝒂
𝟐, ⋯ }가 G를
생성한다고 한다.
정의3: G = < 𝑎@, 𝑎7, ⋯ , 𝑎K >을 만족하는 유한 집합 {𝑎@, 𝑎7, ⋯ , 𝑎K} 이 있다면, G는 유한 생성군(finitely generated group)이라고 한다.
예제7.1 : 𝑉 = {𝑒, 𝑎, 𝑏, 𝑐} : Klein 4-group
① 𝑎7 = 𝑒, 𝑏7 = 𝑒, 𝑐7 = 𝑒이기 때문에 𝑎, 𝑏, 𝑐 각각은 생성원이 아니다.
② 𝑎𝑏 = 𝑐이기 때문에 {𝑎, 𝑏}는 V를 생성한다.
예제7.2 : ℤ8 = {0, 1, 2, 3, 4, 5}
① {1} 또는 {5}는 ℤ8을 생성한다.
② {2} 또는 {3}은 ℤ8을 생성하지 않는다.
③ 2 + 3 = 5는 생성원이기 때문에
2, 3 은 ℤ8을 생성한다.
④ {3, 4}는?
⑤ {2, 4}는?< 𝑎 @ , 𝑎 7 , ⋯ , 𝑎 K > 을 정의하는 다른 방법
정의7.3:⋂
𝒊∈𝑰𝑺
𝒊는 집합 𝑆2의 공통집합이라고 한다.
정리7.4: G는 군이고 𝐻2 ≤ 𝐺 (𝑖 ∈ 𝐼)라고 하자.그렇다면
⋂
𝒊∈𝑰𝑯
𝒊≤ 𝑮
이다.
증명:모든 i에 대하여 𝑎, 𝑏 ∈ ∩2∈e 𝐻2이면 𝑎𝑏6@ ∈∩2∈e 𝐻2임을 보이면 된다.
모든 i에 대해서 𝑎, 𝑏 ∈ 𝐻2 이다.
𝐻2 ≤ 𝐺 이므로 𝑎𝑏6@ ∈ 𝐻2 이다.
그러므로 𝑎𝑏6@ ∈∩2∈e 𝐻2 이다.
두번째 정의:<𝑎@, 𝑎7,⋯ >는 {𝑎@, 𝑎7,⋯}를 포함하는
가장 작은 부분군이라고 정의하자.
여기서가장 작은 부분군이라는 말은 잘 정의된다. (well-defined)
왜냐하면…
𝐻2 가 {𝑎@, 𝑎7,⋯}를 포함하는 부분군일 때, 𝐻 =∩2∈e 𝐻2이 군을 이룸을 보였기 때문이다.Cayley 다이그래프
정의: 다이그래프(Digragh)=방향성 그래프(Directed graph)
다이그래프 D=(V, A)는 꼭짓점들(vertices)의 집합 V와꼭짓점을 연결하는 호들(arcs)의 집합 A로 이루어져 있다.
예제: ①
② 트위터 그래프
③ 웹 그래프
이항연산의 그림화: xa=y ⇔
예제①: ℤ8 = 0, 1, 2, 3, 4, 5 , 𝑆 = {1}X → Y
0 → 1 1 → 2 2 → 3 3 → 4 4 → 5 5 → 0
예제②: ℤ8 = 0, 1, 2, 3, 4, 5 , 𝑆 = {2, 3}
예제: ⇔ 𝑥𝑎 = 𝑦⇔ 𝑥𝑏 = 𝑦
(a) (b)