Shawn Zhong

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Home / 2018 / March

Math 541 - 3/21

  • Mar 23, 2018
  • Shawn
  • Math 541
  • No comments yet
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
Read More >>

5.4 Recursive Algorithms

  • Mar 23, 2018
  • Shawn
  • Math 240
  • No comments yet
Read More >>

Math 541 - 3/19

  • Mar 19, 2018
  • Shawn
  • Math 541
  • No comments yet
Recall • ϵ:S_n→Z\/2Z σ↦{■8(0 ̅&σ is a product of even number of transposition@1 ̅&σ is a product of odd number of transposition)┤ • ϵ^′:S_n→Z\/2Z σ↦{■8(0 ̅&σ(Δ)=Δ@1 ̅&σ(Δ)=−Δ)┤ • Δ≔∏_(1≤i j≤n)▒(x_i−x_j ) , σ(Δ)≔∏_(1≤i j≤n)▒(x_σ(i) −x_σ(j) ) Proposition 40 • Statement ○ Let n∈Z( 0) ○ If τ∈S_n is transposition, then ϵ^′ (τ)=1 ̅ • Example ○ When n=4, τ=(1 2) ○ Δ=(x_1−x_2 )(x_1−x_3 )(x_1−x_4 )(x_2−x_3 )(x_2−x_4 )(x_3−x_4 ) ○ τ(Δ)=(x_2−x_1 )(x_2−x_3 )(x_2−x_4 )(x_1−x_3 )(x_1−x_4 )(x_3−x_4 ) ○ τ(Δ)=−Δ⇒ϵ^′ (τ)=1 ̅ • Proof: Suppose τ=(1 2) ○ Say (x_i−x_j ) is a factor of Δ ○ Then τ(i) τ(j)⟺i=1,j=2 ○ Thus τ(Δ)=−Δ ○ So ϵ^′ (τ)=1 ̅ • Proof: Suppose τ=(i j), 1≤i j≤n ○ Let λ∈S_n denote the following permutation § λ(1)=i § λ(2)=j § λ(i)=1 § λ(j)=2 § λ(k)=k,k∉{1,2,i,j} ○ (i j)=λ(1 2)λ § [λ(1 2)λ](i)=[λ(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^α
Read More >>

Math 541 - 3/16

  • Mar 19, 2018
  • Shawn
  • Math 541
  • No comments yet
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 ker⁡f § Let h∈ker⁡f § ⟺f(h=(1_(H\/A),1_(H\/B) )=(A,B) § ⟺h∈A and h∈B § ⟺h∈A∩B § Therefore ker⁡f=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⁄ker⁡f →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
Read More >>

Math 541 - 3/14

  • Mar 19, 2018
  • Shawn
  • Math 541
  • No comments yet
Proposition 38 • Definition ○ Fix n to be a positive integer ○ A 2\-cycle (i j) in S_n is a transposition • Statement ○ Every σ∈S_n can be written as a product of transposition • Example ○ (1 5 3 2 4)=(1 4)(1 2)(1 3)(1 5) ○ (3 5)=(1 5)(1 3)(1 5) • Proof ○ Fix σ∈S_n ○ We may assume σ is a cycle σ=(a_1 a_2… a_t ) ○ By induction on t, we claim § (a_1 a_2… a_t )=(a_1 a_t )(a_1 a_(t−1) )…(a_1 a_2 ) ○ Base case: t=2 § (a_1 a_2 )=(a_1 a_2 ) ○ Inductive step: t 2 § (a_1 a_t )(a_1 a_(t−1) )…(a_1 a_2 ) § =(a_1 a_t )(a_1 a_2… a_(t−1) ) § =(a_1 a_2… a_(t−1) a_t ) • Note ○ S_n is generated by {(1 2),(1 3),…,(1 n)} Sign of Permutation • Intuition ○ The numbers of transposition used to write some σ∈S_n ○ is not well-defined, but it is always either even or odd • Definition ○ Let ϵ:S_n→Z\/2Z σ↦{■8(0 ̅&σ is a product of even number of transposition@1 ̅&σ is a product of odd number of transposition)┤ ○ Then ϵ is a group homomorphism ○ A_n≔ker⁡ϵ is the alternating group of degree n • Auxiliary Polynomial Δ ○ Δ≔∏_(1≤i j≤n)▒(x_i−x_j ) ○ For σ∈S_n, define σ(Δ)≔∏_(1≤i j≤n)▒(x_σ(i) −x_σ(j) ) ○ Then σ(Δ) is always either Δ or −Δ • Example ○ Let n=4 and σ=(1 2 3 4) ○ Δ=(x_1−x_2 )(x_1−x_3 )(x_1−x_4 )(x_2−x_3 )(x_2−x_4 )(x_3−x_4 ) ○ σ(Δ)=(x_2−x_3 )(x_2−x_4 )(x_2−x_1 )(x_3−x_4 )(x_3−x_1 )(x_4−x_1 )=−Δ • Definition ○ Let ϵ^′:S_n→Z\/2Z σ↦{■8(0 ̅&σ(Δ)=Δ@1 ̅&σ(Δ)=−Δ)┤ ○ ϵ^′ (σ) is the sign of σ, often denoted as sgn⁡σ ○ σ is even if ϵ^′ (σ)=0 ̅ ○ σ is odd if ϵ^′ (σ)=1 ̅ Proposition 39 • Statement ○ ϵ′ is a group homomorphism • Example ○ Let σ=(1 2), τ=(1 2 3) ○ Let Δ=(x_1−x_2 )(x_1−x_3 )(x_2−x_3 ) § σ(Δ)=(x_2−x_1 )(x_1−x_3 )(x_2−x_3 )=−Δ § τ(Δ)=(x_2−x_3 )(x_2−x_1 )(x_3−x_1 )=(−1)^2 Δ=Δ ○ σ=(1 2), τ=(1 2 3)⇒τσ=(1 3) § (τσ)(Δ)=(x_3−x_2 )(x_3−x_1 )(x_2−x_1 )=(−1)^3 Δ=−Δ ○ ϵ^′ (τσ)=ϵ^′ (τ) ϵ^′ (σ), since § ϵ^′ (τσ)=1 ̅ § ϵ^′ (τ) ϵ^′ (σ)=0 ̅+1 ̅=1 ̅ • Proof ○ Fix σ,τ∈S_n ○ Let Δ≔∏_(1≤i j≤n)▒(x_i−x_j ) , then § τ(Δ)=∏_(1≤i j≤n)▒(x_τ(i) −x_τ(j) ) § σ(Δ)=∏_(1≤i j≤n)▒(x_σ(i) −x_σ(j) ) § (τσ)(Δ)=∏_(1≤i j≤n)▒(x_(τσ)(i) −x_(τσ)(j) ) ○ Suppose σ(Δ) has k "reversed factor" i.e. factors (x_j−x_i ) where i j § (τσ)(Δ)=∏_(1≤i j≤n)▒(x_τ(σ(i)) −x_τ(σ(j)) ) § =(−1)^k ∏_(1≤i j≤n)▒(x_τ(i) −x_τ(j) ) § =(−1)^k τ(Δ) § =σ(Δ)τ(Δ) ○ Therefore ϵ^′ (τσ)=ϵ^′ (τ) ϵ^′ (σ)
Read More >>
  • 1
  • 2
  • 3
  • …
  • 5

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 - Discrete Math
    • Math 375 - Linear Algebra
    • Math 431 - Intro to Probability
    • Math 514 - Numerical Analysis
    • Math 521 - Analysis I
    • Math 541 - Abstract Algebra
    • Math 632 - Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 - Intro to Computer Engr.
    • CS/ECE 352 - Digital System Fund.
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E&M
    • AP Physics C: Mechanics
    • CLEP Psychology

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E&M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (4)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP