Math 541 – 3/21 Mar 23, 2018 Shawn Math 541 No comments yet 5.4 Recursive Algorithms Mar 23, 2018 Shawn Math 240 No comments yet Math 541 – 3/19 Mar 19, 2018 Shawn Math 541 No comments yet Math 541 – 3/16 Mar 19, 2018 Shawn Math 541 No comments yet Math 541 – 3/14 Mar 19, 2018 Shawn Math 541 No comments yet 1 … 20 21 22 23 24 … 84
![Proposition 43 • Statement ○ If G is a group, H≤G, and [G:H]=2, then H⊴G • Proof ○ If g∈H, then gH=H=Hg ○ If g∉H, then gH=G∖H=Hg ○ Therefore gH=Hg,∀g∈G ○ So H⊴G • Corollary ○ Let p be the smallest prime dividing |G| ○ If [G:H]=p, then H⊴G ○ (Not ready to prove this yet) Proposition 44 • Statement ○ If (a_1…a_t ),(a_1′…a_t′) are t-cycles in S_n ○ Then ∃σ∈S_n s.t. σ(a_1…a_t ) σ^(−1)=(a_1′…a_t′) • Proof ○ Choose σ∈S_n s.t. σ(a_i )=a_i^′, ∀i∈{1,…,t} ○ By HW 7 #1, σ(a_1…a_t ) σ^(−1)=(σ(a_1 )…σ(a_t ))=(a_1′…a_t′) Theorem 45 • Statement ○ A_4 have no subgroup of order 6 • Proof ○ By way of contradiction, suppose H≤G, and |H|=6 ○ Then [A_4:H]=2 and thus H⊴A_4 ○ A_4 contains 8 3-cycles, so H contains some 3-cycle α ○ Write α=(a b c), then § (a b d)(a b c) (a b d)^(−1)=(b d c)∈H § (b c d)(a b c) (b c d)^(−1)=(a c d)∈H § (b d c)(a b c) (b d c)^(−1)=(a d b)∈H ○ So far, we have (1), (a b c),(b d c),(a c d),(a d b)∈H ○ Also, since H is closed under inverses, (a c b),(b c d)∈H ○ Thus, |H|≥7, which makes a contradiction ○ Therefore A_4 have no subgroup of order 6 Group Action • Definition ○ An action of G on X is a function G×X→X, (g,x)↦gx where ○ 1_G x=x, ∀x∈X ○ g(h�)=(ghx,∀g,h∈G,x∈X • Examples Set Group Action Rn GL_n (R (A,v)↦Av {1,…,n} S_n (σ,i)↦σ(i) Group G Group G (g,h↦gh Group G Group G (g,h↦ghg^(−1) Set of cosets of H≤G Group G (g,g^′ H)↦gg^′ H Set of all subgroups of group G Group G (g,H)↦gHg^(−1) • Note ○ If H≤G, and g∈G, then gHg^(−1)={gh�^(−1)│hH}≤G ○ gHg^(−1)≠∅, since g1g^(−1)=1∈gHg^(−1) ○ If ghg^(−1),gh′ g^(−1)∈gHg^(−1), then ○ ghg^(−1) (gh′ g^(−1) )^(−1)=ghg^(−1) g(h′ )^(−1) g^(−1)=gh(h′ )^(−1)∈gHg^(−1) Orbit and Stabilizer • Suppose a group G acts on a set X. Let x∈X • The orbit of x, denoted orb(x), is {gx│g∈G}⊆X • The stabilizer of x, denoted stab(x), is {g∈G│gx=x}⊆G Proposition 46 • Statement ○ If G acts on X, and x∈X, then stab(x)≤G • Proof ○ stab(x) ≠∅, because 1x=x ○ Let g,h∈stab(x) ○ (ghx=g(h�)=gx=x⇒gh∈stab(x) ○ x=1⋅x=(g^(−1) g)x=g^(−1) (gx)=g^(−1) x⇒g^(−1)∈stab(x) Centralizer • Let G be a group, and let G act on itself by conjugation • If h∈G, then stab(h={g∈G│gh�^(−1)=h={g∈G│ghh�} • This set is called the centralizer of h, denoted as C_G (h Center • Intersections of subgroups are subgroup • Thus if G acts on a set X, ⋃8_(x∈X)▒stab(x) ≤G • In the example above, ⋃8_(hG)▒〖C_G (h 〗=Z(G) is called the center of G Normalizer • Let G be a group, and let X be the set of subgroups of G • G acts on X by g⋅H=gHg^(−1) • If H≤G, then • stab(H)={g∈G│gHg^(−1)=H}={g∈G│gH=Hg} • This set is called the normalizer of H in G, denoted N_G (H) • N_G (H)=G⟺H⊴G](https://shawnzhong.com/wp-content/uploads/2018/04/img_5ac3f59a5b440.png)
=[λ(1 2)](1)=λ(2)=j § [λ(1 2)λ](j)=[λ(1 2)](2)=λ(1)=i § Without loss of generality, assume i,j∉{1,2} § [λ(1 2)λ](1)=[λ(1 2)](i)=λ(i)=1 § [λ(1 2)λ](2)=[λ(1 2)](j)=λ(j)=2 § For k∉{1,2,i,j} § [λ(1 2)λ](k)=[λ(1 2)](k)=λ(k)=k ○ We know ϵ′ is a homomorphism, so § ϵ^′ (i j)=ϵ^′ (λ(1 2)λ) § =ϵ^′ (λ)+ϵ^′ (1 2)+ϵ^′ (λ) § =2ϵ^′ (λ)+1 ̅ § =0 ̅+1 ̅=1 ̅ Corollary 41 • Statement ○ ϵ is well-defined, and ϵ=ϵ^′ • Proof ○ Let σ∈S_n ○ Say σ=τ_1⋯τ_n where τ_i is a transposition, then ○ ϵ^′ (σ)=ϵ^′ (τ_1 )+…+ϵ^′ (τ_n )=⏟(1 ̅+⋯+1 ̅ )┬(n copies)=n ̅ ○ Thus if n is odd, σ cannot be written as a product of an even number of transpositions, and vice versa ○ This shows ϵ is well-defined, and ϵ=ϵ^′ Corollary 42 • Statement ○ If n≥2, ϵ is surjective • Proof ○ ϵ(1)=0 ̅, and ϵ(1 2)=1 ̅ ○ Since Z\/2Z has only 2 elements, ϵ is surjective Alternating Group • Definition ○ The alternative group, denoted as A_n is the kernel of ϵ ○ That is, A_n contains of all even permutations in S_n • Order of A_n ○ By the First Isomorphism Theorem ○ We have an isomorphism S_n \/A_n≅Z\/2Z ○ By Lagrange s Theorem, |A_n |[S_n:A_n ]=|S_n | ○ ⇒|A_n |=|S_n |/[S_n:A_n ] =n!/2 • Note ○ We showed earlier that, if (a_1…a_t )∈S_n, ○ (a_1…a_t )=⏟((a_1 a_t )(a_1 a_(t−1) )⋯(a_1 a_2 ) )┬(t−1 terms) ○ t\-cycle is even when t is odd, and vise versa ○ Thus, (a_1…a_t )∈A_n⟺t is odd • Examples ○ A_2= trivial group ○ A_3={(1), (1 2 3),(1 3 2)}=⟨(1 2 3)⟩ ○ A_4= {(1), (1 2 3), (1 3 2), (1 2 4), (1 4 2), (1 3 4), (1 4 3), (2 3 4), (2 4 3), (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)} • Subgroups of A_4 Order Subgroup 1 {(1)} 2 3 cyclic subgroups 3 4 cyclic subgroups 4 Homework 6 None 12 A_4 Converse of Lagrange s Theorem • A_4 has no subgroup of order 6 • This shows that the converse of Lagrange s Theorem is false ○ If ├ d┤|├ |G|┤, there is not necessarily a subgroup of G with order d • But the converse does hold for finite cyclic groups • Cauchy s Theorem ○ If p is a prime, and ├ p┤|├ |G|┤, then G contains a subgroup of order p • Sylow s Theorem ○ If |G|=p^α m, where p is prime and p∤m ○ Then G contains a subgroup of order p^α](https://shawnzhong.com/wp-content/uploads/2018/03/img_5ab514335870d.png)
![Homework 6 Question 1 • Statement ○ Suppose A,B⊴H, AB=H ○ Then there is an isomorphism H⁄(A∩B) →┴≅ (H⁄A)×(H⁄B) • Proof ○ Define a map § f:H→(H⁄A)×(H⁄B) h↦(h�,h�) ○ Check f is a homomorphism § f(h1 h2 ) § =(h1 h2 A,h1 h2 B) § =(h1 Ah2 A,h1 Bh2 B) § =(h1 A,h1 B)(h2 A,h2 B) § =f(h1 )f(h2 ) ○ Compute kerf § Let h∈kerf § ⟺f(h=(1_(H\/A),1_(H\/B) )=(A,B) § ⟺h∈A and h∈B § ⟺h∈A∩B § Therefore kerf=A∩B ○ Prove surjectivity § Let (h1 A,h2 B)∈(H⁄A)×(H⁄B) § Choose a_1,a_2∈A, b_1,b_2∈B s.t. □ h1=a_1 b_1 □ h2=a_2 b_2 § Then □ h1 A=Ah1=Aa_1 b_1=Ab_1 □ h2 B=a_2 b_2 B=a_2 B § f(a_2 b_1 )=(h1 A,h2 B) □ f(a_2 b_1 ) □ =(a_2 b_1 A,a_2 b_1 B) □ =(Aa_2 b_1,a_2 B) □ =(Ab_1,a_2 B) □ =(h1 A,h2 B) § Therefore f is surjective ○ By the First Isomorphism theorem § There is an isomorphism § f ̅:H⁄kerf →im f § f ̅:H⁄(A∩B)→(H⁄A)×(H⁄B) • Note ○ Given two homomorphism f_1:G→H_1, f_2:G→H_2 ○ Then their direct product given by § f:G→H_1×H_2 g→(f_1 (g),f_2 (g)) ○ is also a homomorphism Homework 6 Question 2 • Statement ○ G is abelian ⟺ G\/Z(G) is cyclic • Proof (⟹) ○ Suppose G is abelian, then ○ G=Z(G) ○ So G\/Z(G) is the trivial group ○ Therefore G\/Z(G) is cyclic • Proof (⟸) ○ Suppose G\/Z(G) is cyclic ○ Choose gZ(G)∈G\/Z(G) s.t. ⟨gZ(G)⟩=G\/Z(G) ○ Let x∈G ○ Then xZ(G)=g^k Z(G) for some k∈Z, and g^(−k) x∈Z(G) ○ Let a,b∈G ○ Choose k_1,k_2∈Z and z_1,z_2∈Z(G) s.t ○ g^(−k_1 ) a=z_1 and g^(−k_2 ) b=z_2 ○ So, a=g^(k_1 ) z_1, b=g^(k_2 ) z_2 ○ Then ab=g^(k_1 ) z_1 g^(k_2 ) z_2=g^(k_2 ) z_2 g^(k_1 ) z_1=ba Homework 6 Question 4 • Statement ○ G=⟨g⟩ is cyclic of order n, d|n, d 0 ○ Then G⁄⟨g^d ⟩ is cyclic of order d • Proof: If H is a cyclic group and A≤H, then H\/A is also cyclic ○ Choose a generator h∈H ○ Then hA is a generator of H\/A ○ If h′ A∈H\/A ○ Choose k∈Z s.t. h′=hk ○ Therefore h′ A=hk A=(h�)^k • Proof ○ |⟨g^d ⟩|=n/((n,d) )=n/d ○ By Lagrange s Theorem ○ n=|G|=|⟨g^d ⟩|⋅[G:⟨g^d ⟩]=n/d |G⁄⟨g^d ⟩ | ○ ⇒|G⁄⟨g^d ⟩ |=d Theorem 37 (The Correspondence Theorem) • Statement ○ Let G be a group, and let N⊴G, then ○ there is a bijection {subgroups of G\/N} (⇄┴F)┬F′ {subgroups of G containing N} • Proof ○ Define § F^′ (K)=K\/N≔{gN∈G\/N│g∈K} § F(H)={g∈G│gN∈H} ○ F(H) is a subgroup of G containing N § If n∈N, then nN=id_(G\/N)∈H § Thus, N⊆F(H) § This also shows that F(H)≠∅ § If g_1,g_2∈F(H), then § g_1 N,g_2 N∈H⇒g_1 N(g_2 N)^(−1)=g_1 g_2^(−1) N∈H⇒g_1 g_2^(−1)∈F(H) ○ F∘F′ and F^′∘F are the identity maps § (F∘F^′ )(K)=F(K\/N)={g∈G│gN∈K\/N}=K § (F^′∘F)(H)=F^′ ({g│gN∈H})={g│gN∈H}⁄N=H](https://shawnzhong.com/wp-content/uploads/2018/03/img_5ab00bc9ecfae.png)
