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
  • AP 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
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Home / 2018 / April / 4

Math 541 – 4/4

  • Apr 04, 2018
  • Shawn
  • Math 541
  • No comments yet
Theorem 54: Cauchy s Theorem • Statement ○ If G is a finite group, and p is a prime divisor of |G|, then ∃H≤G of order p • Proof ○ Write |G|=mp. We argue by strong induction on m ○ When m=1, this is trivial, since any non-identity element of G has order p ○ Suppose m 1, and ∀n∈{1,…,m−1} if |G^′ |=np, then ∃H^′≤G^′ of order p ○ If G is abelian § Let x∈G∖{1} § If ⟨x⟩=G □ By the Fundamental Theorem of Cyclic Groups, □ G=⟨x⟩ contains a (unique) subgroup of order p § If ⟨x⟩≠G □ Set H≔⟨x⟩⊴G □ By the Lagrange s Theorem, |G|=|H|[G:H]=|H|⋅|G/H| □ Since ├ p┤ ||G|┤,either ├ p┤ ||H|┤ or ├ p┤ ||G/H|┤ □ If ├ p┤ ||H|┤ ® Since H is cyclic, H contains a (unique) subgroup of order p ® It follows that G contains a subgroup of order p □ If ├ p┤ ||G/H|┤ ® |G/H| |G|, so, by induction, ∃gH∈G\/H s.t. |gH|=p ® So we only need to prove ├ |gH|┤ ||g|┤ ◊ If K ⟶┴f K′ is a group homomorphism, ├ |f(k)|┤ ||k|┤,∀k∈K ◊ Now, take K=G, K^′=G\/H, f the usual surjection g↦gH ® Therefore ├ p┤ ||g|┤ ® Since ⟨g⟩ is cyclic, ⟨g⟩ contains a (unique) subgroup of order p ® It follows that G contains a subgroup of order p ○ If G is not abelian § By the Lagrange s Theorem, |G|=|C_G (g_i )|⋅[G:C_G (g_i )], ∀i∈{1,…,r} § Since ├ p┤ ||G|┤,either ├ p┤ ||C_G (g_i )|┤ or ├ p┤ |[G:C_G (g_i )]┤ § If ├ p┤ ||C_G (g_i )|┤ for some i □ Since G is not abelian, C_G (g_i )≨G for all i □ Apply the induction hypothesis, C_G (g_i ) contains a subgroup of order p □ It follows that G contains a subgroup of order p § If ├ p┤ |[G:C_G (g_i )]┤,∀i □ By the Class Equation, |G|=|Z(G)|+∑_(i=1)^r▒[G:C_G (g_i )] where g_1,…,g_r∈G □ are the representatives of the conjugate classes not contained in Z(G) □ It follows that ├ p┤ |(|G|−∑_(i=1)^r▒[G:C_G (g_i )] )┤=|Z(G)| □ G is not abelian, so Z(G)≨G □ Apply the induction hypothesis, Z(G) contains a subgroup of order p □ It follows that G contains a subgroup of order p Lemma 55: Recognizing Direct Products • Statement ○ Let G be a group with normal subgroups N_1,N_2 ○ The map α:N_1×N_2→G given by (n_1,n_2 )↦n_1 n_2 is an isomorphism ○ if and only if N_1 N_2=G and N_1∩N_2={1} • Proof (⟹) ○ Since α is surjective, N_1 N_2=G ○ Suppose n∈N_1∩N_2 ○ Then α(n,1)=n=α(1,n) ○ Since α is injective, (1,n)=(n,1)⇒n=1 ○ So N_1∩N_2={1} • Proof (⟸) ○ α is surjective § This is true since N_1 N_2=G ○ α is a homomorphism § α((n_1,n_2 ),(n_1^′,n_2^′ ))=α((n_1 n_1^′,n_2 n_2^′ ))=n_1 n_1^′ n_2 n_2^′ § α(n_1,n_2 )α(n_1^′,n_2^′ )=n_1 n_2 n_1^′ n_2^′ § We want show that α((n_1,n_2 ),(n_1^′,n_2^′ )) (α(n_1,n_2 )α(n_1^′,n_2^′ ))^(−1)=1 § (n_1 n_1^′ n_2 n_2^′ ) (n_1 n_2 n_1^′ n_2^′ )^(−1)=n_1 n_1^′ n_2 n_2^′ (n_2^′ )^(−1) (n_1^′ )^(−1) n_2^(−1) n_1^(−1) § =n_1 ⏟(n_1^′ n_2 (n_1^′ )^(−1) )┬(∈N_2 ) n_2^(−1) n_1^(−1)=n_1 ⏟(n_1^′ n_2 (n_1^′ )^(−1) n_2^(−1) )┬(∈N_2 ) n_1^(−1)∈N_2 § =n_1 n_1^′ ⏟(n_2 (n_1^′ )^(−1) n_2^(−1) )┬(∈N_1 ) n_1^(−1)=n_1 ⏟(n_1^′ n_2 (n_1^′ )^(−1) n_2^(−1) )┬(∈N_1 ) n_1^(−1)∈N_1 § Thus (n_1 n_1^′ n_2 n_2^′ ) (n_1 n_2 n_1^′ n_2^′ )^(−1)∈N_1∩N_2={1} § Therefore α((n_1,n_2 ),(n_1^′,n_2^′ ))=α((n_1,n_2 ),(n_1^′,n_2^′ )) ○ α is injective § If (n_1,n_2 )=1 § ⇒n_1 n_2=1 § ⇒n_1=n_2^(−1) § ⇒n_1∈N_2,n_2∈N_1 § ⇒n_1=n_2=1 § ⇒(n_1,n_2 )=(1,1) § ⇒α is injective
Read More >>

Math 521 – 4/4

  • Apr 04, 2018
  • Shawn
  • Math 521
  • No comments yet
Series • Given a sequence {a_n } • We associate a sequence of partial sums {s_n } where • s_n=∑_(k=1)^n▒a_k =a_1+a_2+…+a_n • ∑_(k=1)^∞▒a_k is called an infinite series, or simply series • If {s_n } diverges, the series is said to diverge • If {s_n } converges to s, the series is said to converge, and write ∑_(k=1)^∞▒a_k =s • s is called the sum of the series • But it is technically the limit of a sequence of sums Theorem 3.22 (Cauchy Criterion for Series) • Statement ○ ∑_(n=1)^∞▒a_n converges⟺∀ε 0, ∃N∈N s.t. |∑_(k=n)^m▒a_k | ε,∀m≥n≥N • Proof ○ This is Theorem 3.11 applied to {s_n } Theorem 3.23 • Statement ○ In the setting of Theorem 3.22, take m=n ○ We have |a_n | ε for n≥N ○ If ∑_(n=1)^∞▒a_n converges, then (lim)_(n→∞)⁡〖a_n 〗=0 • Note ○ If a_n→0, the series ∑_(n=1)^∞▒a_n might not converge • Example: ∑_(n=1)^∞▒1/n diverges ○ 1+1/2+1/3+1/4+1/5+1/6+1/7+1/8+…≥1+1/2+1/4+1/4+1/8+1/8+1/8+1/8+… ○ Therefore ∑_(n=1)^∞▒1/n diverges Theorem 3.24 • Statement ○ A series of nonnegative real numbers converges if and only if ○ its partial sum form a bounded sequence • Proof ○ See Theorem 3.14 (Monotone Convergence Theorem) Theorem 3.25 (Comparison Test) • If |a_n | c_n for n≥N_0∈N and ∑_(n=1)^∞▒c_n converges, then ∑_(n=1)^∞▒a_n converges ○ Given ε 0,∃N≥N_0 s.t. |∑_(k=n)^m▒c_k |=∑_(k=n)^m▒c_k  ε for m≥n≥N ○ By the Cauchy Criterion, |∑_(k=n)^m▒a_k |≤∑_(k=n)^m▒|a_k | ≤∑_(k=n)^m▒c_k  ε ○ Thus ∑_(n=1)^∞▒a_n converges • If a_n≥d_n≥0 for n≥N_0∈N and ∑_(n=1)^∞▒d_n diverges, then ∑_(n=1)^∞▒a_n diverges ○ If ∑_(n=1)^∞▒a_n converges, then so must ∑_(n=1)^∞▒d_n ○ This is a contradiction, so ∑_(n=1)^∞▒a_n diverges Theorem 3.26 • Statement ○ If 0 x 1, then∑_(n=0)^∞▒x^n =1/(1−x) ○ If x   1, the series diverges • Note ○ {█(S=1+x+x^2+…@xS=x+x^2+…)┤⇒S−xS=1⇒S=1/(1−x) ○ This only works if we know this series converges • Proof ○ If 0 x 1, we have ○ {█(s_n=1+x+x^2+…+x^n@xs_n=x+x^2+…+x^n+x^(n+1) )┤ ○ ⇒s_n−xs_n=1−x^(n+1) ○ ⇒s_n=(1−x^(n+1))/(1−x) ○ Since 0 x 1,lim_(n→∞)⁡〖s_n 〗=lim_(n→∞)⁡〖(1−x^(n+1))/(1−x)〗=1/(1−x) ○ Note if x=1, ∑_(n=1)^∞▒x^n =1+1+…which diverges
Read More >>

6.3 Permutations and Combinations

  • Apr 04, 2018
  • Shawn
  • Math 240
  • No comments yet
Permutations • Definition ○ A permutation of a set of distinct objects is an ordered arrangement of these objects. ○ An ordered arrangement of r elements of a set is called an r-permutation. • Example ○ Let S = {1,2,3}. ○ The ordered arrangement 3,1,2 is a permutation of S. ○ The ordered arrangement 3,2 is a 2-permutation of S. ○ The number of r-permutations of a set with n elements is denoted by P(n,r). ○ The 2-permutations of S = {1,2,3} are 1,2; 1,3; 2,1; 2,3; 3,1; and 3,2 ○ Hence, P(3,2) = 6. A Formula for the Number of Permutations • Theorem 1 ○ If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are ○ P(n,r)=n(n−1)(n−2)⋯(n−r+1) ○ r-permutations of a set with n distinct elements. • Proof ○ Use the product rule. ○ The first element can be chosen in n ways. ○ The second in n − 1 ways ○ And so on until there are (n−(r−1)) ways to choose the last element. ○ Note that P(n,0) = 1, since there is only one way to order zero elements. • Corollary 1 ○ If n and r are integers with 1 ≤ r ≤ n, then ○ P(n,r)=n!/(n−r)! • Example ○ How many ways are there to select a first-prize winner, a second prize winner, and a third-prize winner from 100 different people who have entered a contest? ○ P(100,3) = 100 ∙ 99 ∙ 98 = 970,200 Example ○ Suppose that a saleswoman has to visit eight different cities. ○ She must begin her trip in a specified city ○ But she can visit the other seven cities in any order she wishes. ○ How many possible orders can the saleswoman use when visiting these cities? ○ The first city is chosen, and the rest are ordered arbitrarily. ○ Hence the orders are: 7! = 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 5040 ○ If she wants to find the tour with the shortest path that visits all the cities, ○ she must consider 5040 paths! Example ○ How many permutations of the letters ABCDEFGH contain the string ABC ? ○ We solve this problem by counting the permutations of six objects, ABC, D, E, F, G, H. ○ 6! = 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 720 Combinations • Definition ○ An r-combination of elements of a set is an unordered selection of r elements from the set. ○ Thus, an r-combination is simply a subset of the set with r elements. ○ The number of r-combinations of a set with n distinct elements is denoted by C(n, r). ○ The notation (█(n@r)) is also used and is called a binomial coefficient. ○ (We will see the notation again in the binomial theorem in Section 6.4.) • Example: ○ Let S be the set {a, b, c, d}. ○ Then {a, c, d} is a 3-combination from S. ○ It is the same as {d, c, a} since the order listed does not matter. ○ C(4,2) = 6 because the 2-combinations of {a, b, c, d} are the six subsets ○ {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, and {c, d}. • Theorem 2 ○ The number of r-combinations of a set with n elements, where n≥r ≥ 0, equals ○ C(n,r)=n!/(n−r)!r! • Proof ○ By the product rule P(n, r)=C(n,r)⋅P(r,r). Therefore, ○ C(n,r)=P(n,r)/P(r,r) =(n!∕(n−r)!)/(r!∕(r−r)!)=n!/(n−r)!r! • Example ○ How many poker hands of five cards can be dealt from a standard deck of 52 cards? ○ Also, how many ways are there to select 47 cards from a deck of 52 cards? ○ Since the order in which the cards are dealt does not matter ○ the number of five card hands is: ○ C(52,5)=52!/5!47!=(52⋅51⋅50⋅49⋅48)/(5⋅4⋅3⋅2⋅1)=26⋅17⋅10⋅49⋅12=2,598,960 ○ The different ways to select 47 cards from 52 is ○ C(52,47)=52!/47!5!=C(52,5)=2,598,960 • Corollary 2 ○ Let n and r be nonnegative integers with r≤n. Then C(n, r) = C(n, n−r). • Proof ○ From Theorem 2, it follows that ○ C(n,n−r)=n!/(n−r)!(n−(n−r))!=n!/(n−r)!r!=C(n,r) ○ Hence, C(n, r)=C(n, n−r) Combinatorial Proofs • Definition ○ A combinatorial proof of an identity is a proof that uses one of the following methods. ○ Double Counting Proof § A double counting proof uses counting arguments to prove that § both sides of an identity count the same objects, but in different ways. ○ Bijective Proof § A bijective proof shows that there is a bijection § between the sets of objects counted by the two sides of the identity. • Example ○ Here are two combinatorial proofs that C(n, r)=C(n, n−r) ○ Bijective Proof § Suppose that S is a set with n elements. § The function that maps a subset A of S to A ̅ is a bijection between § the subsets of S with r elements and the subsets with n−r elements. § Since there is a bijection between the two sets § They must have the same number of elements. ○ Double Counting Proof § By definition the number of subsets of S with r elements is C(n, r). § Each subset A of S can also be described by § specifying which elements are not in A, i.e., those which are in A ̅. § Since the complement of a subset of S with r elements has n−r elements § There are also C(n,n−r) subsets of S with r elements. More Examples • How many words can you formed by rearranging the letters in the word: ○ Combine § 7! ○ Permutation § Pick where t s go § Arrange remaining 9 letters § (█(11@2))⋅9!=11!/2! ○ Rearrange § Pick where r s go § Pick where e s go § Pick where a s go § Arrange remaining 2 letters § (█(9@3))⋅(█(6@2))⋅(█(4@2))⋅2!=9!/3!2!2! • In a game of cards a hand consists of 13 cards. How many possible hands are there with ○ Exactly one ace § Pick which ace § Pick the rest § 4⋅(█(52−4@12)) ○ At least one ace § 1 Ace + 2 Aces + 3 Aces + 4 Aces § 4⋅(█(52−4@12))+(█(4@2))⋅(█(52−4@11))+(█(4@3))⋅(█(52−4@10))+(█(4@4))⋅(█(52−4@9)) ○ Exactly one ace and two diamonds § Case 1: We pick one diamond and a diamond ace □ 1⋅12⋅(█(52−4−12@11)) § Case 2: We pick two diamonds and a different ace □ 3⋅(█(12@2))⋅(█(52−4−12@10)) § So the total number of hands is 1⋅12⋅(█(52−4−12@11))+3⋅(█(12@2))⋅(█(52−4−12@10))
Read More >>

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
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E&M
    • AP Physics C: Mechanics
    • CLEP Psychology
  • 2048 Game
  • HiMCM 2016
  • 登峰杯 MCM

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 (2)
  • 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