Math 521 – 4/4 Apr 04, 2018 Shawn Math 521 No comments yet 6.3 Permutations and Combinations Apr 04, 2018 Shawn Math 240 No comments yet Math 541 – 4/2 Apr 03, 2018 Shawn Math 541 No comments yet Math 541 – 3/23 Apr 03, 2018 Shawn Math 541 No comments yet Math 521 – 4/2 Apr 03, 2018 Shawn Math 521 No comments yet 1 … 18 19 20 21 22 … 41
![Conjugacy Class • Definition ○ If G is a group, G acts on itself by conjugation: g⋅h=ghg^(−1) ○ The orbits under this action are called conjugacy classes ○ Denote a conjugate class represented by some element g∈G by conj(g) • Example 1 ○ If g∈G, and g∈Z(G), then conj(g)={g} ○ Since hgh(−1)=hh(−1) g=g, ∀h∈G ○ The converse is also true: If conj(g)={g}, then g∈Z(G) • Example 2 ○ Let G=S_n ○ If σ∈S_n, then conj(g)={all permutations of the same cycle type as σ} ○ For instance § If σ is a t-cycle, then conj(σ)={all t-cycles} ○ More generally § Let σ=(a_1^((1) )…a_(t_1)^((1) ) )⋯(a_1^((m) )…a_(t_m)^((m) ) ) be a product of disjoint cycles § Then conj(σ)={all products of disjoint cycles of length t_1,…,t_m } Theorem 51: The Class Equation • Statement ○ Let G be a finite group ○ Let g_1,…g_r∈G be representatives of the conjugacy classes of G that ○ are not contained in the center Z(G) of G ○ Then |G|=|Z(G)|+∑_(i=1)^r▒[G:C_G (g_i )] • Recall: C_G (g_i )={g∈G│gg_i=g_i g} • Proof ○ G is the disjoint union of its disjoint conjugate classes ○ Then G=Z(G)∪⋃24_(i=1)^r▒conj(g_i ) ○ ⇒|G|=|Z(G)|+∑_(i=1)^r▒|conj(g_i )| ○ ⇒|G|=|Z(G)|+∑_(i=1)^r▒|orb(g_i )| (under conjugacy action) ○ ⇒|G|=|Z(G)|+∑_(i=1)^r▒[G:stab(g_i )] by Proposition 48 ○ ⇒|G|=|Z(G)|+∑_(i=1)^r▒[G:C_G (g_i )] Corollary 52 • Statement ○ If p is a prime, and P is a group of order p^α (α 1), then |Z(P)| 1 • Note: Group of order p^α is called a p-group • Proof ○ By the class equation, |Z(P)|=|P|−∑_(i=1)^r▒[P:C_P (p_i )] , where p_1,…p_r∈P ○ are representatives of the conjugate classes of P not contained in Z(P) ○ g_i∉Z(P)⇒C_P (g_i )≠P⇒[P:C_P (g_i )]≠1 ○ By Lagrange s Theorem, ├ [P:C_P (g_i )]┤ |p^α ┤ ○ Combing previous two results, ├ p┤|├ [P:C_P (g_i )]┤ ○ Thus, ├ p┤ |(|P|−∑_(i=1)^r▒[P:C_P (g_i )] )┤=|Z(P)|, since ├ p┤ ||P|┤ ○ ⇒|Z(P)|≠1 Corollary 53 • Statement ○ If p is a prime, and P is a group of order p^2, then P is abelian. ○ In fact, either P≅Z\/p^2 Z or P≅Z\/pZ×Z\/pZ • Proof ○ By corollary 52, |Z(P)|=p or p^2 ○ Suppose |Z(P)|=p § |P/Z(P)|=[P:Z(P)]=|P|/|Z(P)| =p^2/p=p § By Corollary 26, P\/Z(P) is cyclic § By HW6 Q2, P is abelian § In this case Z(P)=P⇒|Z(P)|=p^2, which is impossible ○ Suppose |Z(p)|=p^2 § We have |Z(p)|=|P|⇒Z(P)=P § So P is abelian ○ If P is cyclic, then clearly P≅Z\/p^2 Z ○ If P is not cyclic, we need to show P≅Z\/pZ×Z\/pZ § Let z∈P∖{1}, then |z|=p. Let y∈P∖⟨z⟩ § Set H≔⟨z⟩,K≔⟨y⟩, then H∩K={1} § Since any non-identity element of H or K is a generator § For instance, if 1≠y^k∈H for some k, then y∈H, which is impossible § |HK|=(|H|⋅|K|)/|H∩K| =|H|⋅|K|=p^2=|P|⇒HK=P § By HW6 Q1, there exists an isomorphism P ⟶┴≅ P\/H×P\/K § |P/H|=[P:H]=|P|/|H| =p^2/p=p⇒P\/H≅Z\/pZ § Similarly for P\/K § Therefore P=HK≅Z\/pZ×Z\/pZ](https://shawnzhong.com/wp-content/uploads/2018/04/img_5ad9f4a0e5217.png)
![Proposition 47 • Statement ○ Let G act on a set X ○ The relation x~x^′⟺∃g∈G s.t. gx=x′ is an equivalence relation • Proof ○ Reflexive § 1⋅x=x ○ Symmetric § Suppose x~x^′, then ∃g∈G s.t. gx=x^′⇒x=g^(−1) x^′ ○ Transitive § Suppose x~x^′ and x^′~x^′′ § Choose g,h∈G s.t. gx=x′ and hx^′=x′′ § Then ghx=hx^′=x^′′ • Note ○ The equivalence classes are the orbits of the group action ○ Thus, the orbits partition X Proposition 48 • Statement ○ If G acts on X, and x∈X, then |orb(x)|=[G:stab(x)] • Proof ○ Define a function § F:orb(x)→{left costs of stab(x)} § gx↦g stab(x) ○ F is injective § g stab(x)=g′ stab(x) § ⟺(g^′ )^(−1) g∈stab(x) § ⟺(g^′ )^(−1) gx=x § ⟺gx=g^′ x ○ F is surjective § This is clear ○ So orb(x)≅{left costs of stab(x)} ○ Therefore |orb(x)|=[G:stab(x)] Proposition 49: Lemma for Cayley s Theorem • Statement ○ Let G be a group acting on a finite set X={x_1,…,x_n } ○ Then each g∈G determines a permutation σ_g∈S_n by ○ σ_g (i)=j⟺g⋅x_i=x_j • Proof ○ The map f:X→X, given by x↦g⋅x is bijection ∀g∈G § Injectivity: g⋅x=g⋅x^′⇒(g^(−1) g)⋅x=(g^(−1) g)⋅x^′⇒x=x^′ § Surjectivity: f(g^(−1)⋅x)=(gg^(−1) )⋅x=x ○ So each g∈G determines a permutation σ_g∈S_n where § σ_g (i)=j⟺g⋅x_i=x_j • Statement ○ The map Φ:G→S_n,g↦σ_g is a homomorphism • Proof ○ Let g,h∈G,i∈{1,…,n} ○ Suppose σ_gh(i)=j for some j ○ Then (gh x_i=x_j ○ Write hx_i=x_k for some k, then σ_h(i)=k ○ (gh x_i=x_j⟺gx_k=x_j⟺σ_g (k)=j⟺σ_g (σ_h(i))=j ○ Therefore σ_gh(i)=σ_g σ_h(i),∀i∈{1,…,n} Theorem 50: Cayley s Theorem • Statement ○ Every finite group is isomorphic to a subgroup of the symmetric group • Proof ○ Let G={g_1,…,g_n } act on itself by left multiplication g⋅h=gh ○ By Proposition 49, this action determines a homomorphism § Φ:G→S_n § g↦σ_g § where σ_g (i)=j⟺g⋅g_i=g_j ○ Φ is injective § Φ(g)=Φ(h⟺σ_g=σ_ℎ⟺ggi=hgi,∀i⟺g=h ○ Thus G≅im(Φ)≤S_n • Example ○ Klein 4 group K={1,a,b,c} ○ where a^2=b^2=c^2=1⟺ab=c,bc=a,ac=b 1 a b c 1 1 a b c a a 1 c b b b c 1 a c c b a 1 ○ Label the group elements with 1, 2, 3, 4 ○ 1↦σ_1=(1) since § σ_1 (1)=1 § σ_2 (2)=2 § σ_3 (3)=3 § σ_4 (4)=5 ○ a↦σ_a=(1 2)(3 4) since § σ_a (1)=2 § σ_a (2)=1 § σ_a (3)=4 § σ_a (4)=3 ○ b↦σ_b=(1 3)(2 4) since § σ_b (1)=3 § σ_b (2)=4 § σ_b (3)=1 § σ_b (4)=2 ○ c↦σ_c=(1 4)(2 3) since § σ_c (1)=4 § σ_c (2)=3 § σ_c (3)=2 § σ_c (4)=1 ○ Therefore K≅{(1),(1 2)(3 4),(1 3)(2 4),(1 4)(2 3)}≤S_4](https://shawnzhong.com/wp-content/uploads/2018/04/img_5ac98545de957.png)
