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 Math 521 – 3/19 Mar 19, 2018 Shawn Math 521 No comments yet 1 … 20 21 22 23 24 … 41
=[λ(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)
