Math 541 Archives - Page 7 of 8 - Shawn Zhong

Math 541 – 2/12

$Proposition 15 • Statement ○ |S_n |=n! • Proof ○ First, we prove that if X and Y are sets of order n, then ○ There are n! injective functions from X to Y ○ We argue by induction on n ○ n=1 § Clear ○ n 1 § Suppose f:X→Y is injective § Let x∈X, then there are n possibilities for f(x) § f restricts to an injective function X∖{x}→Y∖{f(x)} § There are (n−1)! such functions, by induction § Thus, there are n(n−1)!=n! injective functions X→Y ○ Now, take X={1,…,n}=Y ○ Then every injection between finite sets of the same order is a bijection ○ Notice that the sets must be finite (Counterexample: f:Z→Z, n↦2n) Cycle • Definition ○ Fix n∈Z( 0). Let a_1,…,a_t∈{1,…,n} ○ The element of S_n given by § a_i↦a_(i+1) for 1≤i≤t−1 § a_t↦a_1 § j↦j if j∉{a_1,…a_t } ○ is denoted by (a_1,a_2,…,a_t ) and is called a cycle of length t • Example ○ Let σ=(1 3 2)∈S_4, then ○ (■8(i&1&2&3&4@↓&↓&↓&↓&↓@σ(i)&3&1&2&4)) ○ Notice: (1 3 2)=(3 2 1)=(2 1 3) Disjoint Cycles • Definition ○ Two cycles (a_1,…a_t ) and (b_1,…,b_k ) are disjoint if ○ {a_1,…a_t }∩{b_1,…,b_k }=∅ • Example ○ (1 2), (3 4)∈S_4 are disjoint • Fact ○ Every element of S_n can be written as a product of disjoint cycles ○ S_1={(1)} ○ S_2={(1),(1 2)} ○ S_3={(1), (1 2), (1 3), (2 3),(1 2 3), (1 3 2)} ○ S_4 = {(1), (1 2), (1 3), (1 4), (2 3), (2 4), (3 4), (1 2 3), (1 2 4), (1 3 2), (1 4 2), (1 3 4), (1 4 3), (2 3 4), (2 4 3), (1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2), (1 2)(3 4), (1 4)(2 3), (1 3)(2 4s)} ○ Note: We write the identity of S_n as (1) Cycle Decomposition for Permutations • Algorithm Method Example a≔min⁡{x∈Nx not appeared in previous cycles} (1 Begin the new cycle: (a b≔σ(a) σ(1)=12=b If b=a 12≠1 • close the cycle with a right parenthesis So write (1 12 • return to step 1 If b≠a • write b next to a in this cycle: (a b c≔σ(b) σ(12)=8 If c=a 8≠1 • close the cycle with a right parenthesis So continue the cycle as: • return to step 1 (1 12 8 If c≠a • write c next to in this cycle: (a b c b≔c and repeat this step until the cycle closes Naturally this process stops when all the numbers from {1,2, …,n} have appeared in some cycle. σ = (1 1 2 8 10 4)(2 1 3)(3)(5 1 1 7)(6 9) Remove all cycles of length 1 σ = (1 1 2 8 10 4)(2 1 3)(5 1 1 7)(6 9) • Example ○ Take σ∈S_13 to be the following ○ (■8(i&1&2&3&4&5&6&7&8&9&10&11&12&13@↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓@σ(i)&12&13&3&1&11&9&5&10&6&4&7&8&3)) ○ Start with 1, σ(1)=12, so write 12 after 1. ○ Keep going until you cycle back to 1 ○ Start with the smallest number which hasn t yet appeared, and repeat. ○ Repeat this step until 1,…,13 have all appeared. Product of Cycles • Reminder: Read from right to left • Example ○ Write σ=(1 2 3)(1 2)(3 4) as a product of disjoint cycles ○ What is σ(1)? § (3 4) maps 1 to 1 § (1 2) maps 1 to 2 § (1 2 3) maps 2 to 3 § Thus σ(1)=3 ○ Similarly σ(3)=4, σ(4)=1 ○ Thus we close the cycle (1 3 4) ○ We won t write down (2), since it is the identity ○ Thus σ=(1 3 4)(2)=(1 3 4) ○ Note: σ∈S_4, but it make sense to think of σ∈S_n for n 4 • Commutativity of S_n ○ (1 2)(1 2 3)=(2 3) ○ (1 2 3)(1 2)=(3 1) ○ In particular S_3 is not abelian ○ Therefore S_n is not abelian for n≥3$

Math 541 – 2/9

$Examples of Orders • Example 1 ○ A≔(■8(0&−1@1&−1))∈GL_2 (R ○ A^3=(■8(0&−1@1&−1))^3=(■8(−1&1@−1&0))(■8(0&−1@1&−1))=(■8(1&0@0&1))=I ○ Thus, |A|=3 • Example 2 ○ In Z,Q,R,ℂ, every nonzero element has infinite order • Example 3 ○ In Q∗ and R∗, the elements of finite order are § |1|=1 § |−1|=2 ○ In ℂ^∗, there are lots more § elements of order n in ℂ are called n^th roots of unity § i is the fourth root of unity § i.e. i^1=i, i^2=−1, i^3=−i, i^4=1 • Example 4 ○ What are the orders of the elements in Z\/6Z? Elements Order Note 0 ̅ 1 0 ̅ is the identity 1 ̅ 6 1 ̅⋅6=6 ̅=0 ̅ 2 ̅ 3 2 ̅⋅3=6 ̅=0 ̅ 3 ̅ 2 3 ̅⋅2=6 ̅=0 ̅ 4 ̅ 3 4 ̅⋅3=(12) ̅=0 ̅ 5 ̅ 6 5 ̅⋅6=(30) ̅=0 ̅ ○ In general, if a ̅∈Z\/nZ, then the "n^th power" of a ̅ is (na) ̅ ○ Note that all the orders are divisors of 6 (Lagrange Theorem) • Example 5 ○ What are the orders of the elements in Z\/5Z×? § Z\/5Z×={1 ̅,2 ̅,3 ̅,4 ̅ } § (0,5)=0≠1, so 0 ̅∉Z\/5Z× Elements Order Note 1 ̅ 1 1 ̅ is the identity 2 ̅ 4 2 ̅^4=(16) ̅=1 ̅ 3 ̅ 4 3 ̅^4=81 ̅=1 ̅ 4 ̅ 2 4 ̅^2=(16) ̅=1 ̅ Symmetric Groups (Section 1.3) • Symmetric Group of Degree n ○ n∈Z(0) ○ S_n≔{bijective functions {1,…,n}→{1,…,n}} ○ S_n is a group with operation given by composition of functions ○ Composition of functions is an operation on S_n § S_n×S_n→S_n § (σ,τ)↦σ∘τ § σ∘τ is again bijictive, so this makes sense ○ Associativity § Suppose f:X→Y, g:Y→Z,h:Z→W § ((hg)∘f)(x)=(hg)(f(x))=h(g(f(x))) § (h(g∘f))(x)=h((g∘f)(x))=h(g(f(x))) § Thus (hg)∘f=h∘(g∘f) ○ Identity § Identity map ○ Inverses § Bijective functions have inverses Proposition 15 • Statement ○ |S_n |=n! • Proof ○ First, we prove that if X and Y are sets of order n, then ○ There are n! injective functions from X to Y ○ We argue by induction on n ○ n=1 § Clear ○ n1 § Suppose f:X→Y is injective § Let x∈X. § There are n possibilities for f(x) § f restricts to an injective function X∖{x}→Y∖{f(x)} § There are (n−1)! such functions, by induction § Thus, there are n(n−1)!=n! injective functions X→Y ○ (To be continued)$

Math 541 – 2/7

$Multiplicative Group of Z\/nZ • Let n∈Z( 0) fixed, Proposition 9 implies that there is a well-defined function ○ Z\/nZ×Z\/nZ→Z\/nZ ○ (a ̅,b ̅ )→(ab) ̅ • Check group property ○ Identity: 1 ̅⋅a ̅=(1⋅a) ̅=1 ̅ ○ This operation is associative ○ And 1 ̅ is a reasonable candidate for an identity, but there is no inverse ○ Example: Z\/4Z § 2 ̅⋅0 ̅=0 ̅ § 2 ̅⋅1 ̅=2 ̅ § 2 ̅⋅2 ̅=0 ̅ § 2 ̅⋅3 ̅=2 ̅ • Definition ○ Define (ZnZ^×≔{a ̅∈ZnZ(a,n)=1} ○ By HW 2 #2, a ̅∈(ZnZ^× iff ○ ∃c ̅∈Z\/nZ s.t. (ac) ̅=1 ̅ Proposition 11: (ZnZ^× • Statement ○ (ZnZ^× is a group with opeation given by multiplication • Proof ○ Closure: If a ̅,b ̅∈(ZnZ^×, then (ab) ̅∈(ZnZ^× as well ○ Associativity: Clear, from associativity of multiplication of integers ○ Identity: 1 ̅ ○ Inverses: Built in HW 2 #2 List of Groups Set Operation Z,Q,R,ℂ + Q∗,R∗,ℂ^∗ ⋅ GL_n (R, n 0 Matrix multiplication Z\/nZ, n 0 + 〖Z/nZ^∗, n 0 ⋅ Proposition 12: Properties of Group • Let G be a group, then G has the following properties • The identity of G is unique ○ i.e. If ∃〖1,1〗^′∈G s.t. ∀g∈G,1g=g1=g and 1^′ g=g1^′=g, then 1 =1^′ ○ Proof: 1=1⋅1^′=1^′∎ • Each g∈G has a unique inverse ○ i.e. If g∈G and ∃h,h′∈G s.t. hg=gh=1 and h′ g=gh′=1 ○ Let g∈G, and suppose h,h′∈G are inverses of g ○ h=h⋅1=h(gh′ )=(h�) h′=1⋅h′=h′ • (g^(−1) )^(−1)=g, ∀g∈G ○ Let g∈G, then gg^(−1)=1=g^(−1) g ○ Since the inverse is unique, g=(g^(−1) )^(−1) • The Generalized Associative Law ○ i.e. If g_1,…,g_n∈G, then g_1…g_n is independent of how it is bracketed ○ First show the result is true for n=1,2,3 ○ Assume for any k n any bracketing of a product of k elements ○ b_1 b_2⋯b_k can be reduced to an expression of the form b_1 (b_2 (b_3⋯b_k )) ○ Then any bracketing of the product a_1 a_2⋯a_n must break into ○ 2 sub-products, say (a_1 a_2⋯a_k )(a_(k+1) a_(k+2)⋯a_n ) ○ where each sub-product is bracketed in some fashion ○ Apply the induction assumption to each of these two sub-products ○ Reduce the result to the form a_1 (a_2 (a_3…a_n )) to complete the induction. • (gh^(−1)=h(−1) g^(−1), ∀g,h∈G ○ By the generalized associative law ○ (gh(h(−1) g^(−1) )=g(h^(−1) ) g^(−1)=gg^(−1)=1 ○ (h(−1) g^(−1) )(gh=h(gg^(−1) ) h(−1)=hh(−1)=1 • Notation ○ We will apply the Generalized Associative Law without mentioning it ○ In particular, if G is a group and n∈Z( 0), we will write § g^n=⏟(g…g)┬(n copies) § g^(−n)=⏟(g^(−1)…g^(−1) )┬(n copies) § g^0=1 Proposition 13: Cancellation Law • Statement ○ Let G be a group, and let a,b,u,v∈G ○ If au=av, then u=v ○ If ua=va, then u=v • Proof ○ au=av⇒a^(−1) au=a^(−1) av⇒u=v ○ ua=va⇒uaa^(−1)=vaa^(−1)⇒u=v • Warning ○ ua=av⇏u=v ○ This holds in abelian groups, but not in general Corollary 14 • Let G be a group, and let g,h∈G • If gh=g,then h=1 ○ gh=g ○ ⇒gh=g1 ○ ⇒h=1 • If gh=1,then h=g^(−1) ○ gh=1 ○ ⇒gh=gg^(−1) ○ ⇒h=g^(−1)$

Math 541 – 2/5

$Examples of Groups • Is Z a group under multiplication? ○ No, because there is no inverses for 2 ○ Let x∈Z∖{±1} ○ The multiplicative inverse of x (i.e. 1/x) is not an integer • What about Q,R, and ℂ? ○ No, because 0 still has no multiplicative inverse • Multiplicative group of Q,R,ℂ ○ Let Q∗=Q∖{0} and R∗, ℂ^∗ similarly ○ Then Q∗,R∗,ℂ^∗ are groups with operation given by multiplication ○ We argue this for Q∗; the same proof works for R∗ and ℂ^∗ ○ Check: multiplication is an operation on Q∗ § If a,b∈Q∗, then ab∈Q∗ ○ Associativity § This is clear ○ Identity § 1∈Q∗ ○ Inverses § If a∈Q∗, then 1/a is the inverse of a, and 1/a∈Q∗ • Is Z a group with operation given by subtration? ○ No, because subtraction is not associative ○ (1−2)−3=−4 ○ 1−(2−3)=2 • GL_n (R under matrix multiplication ○ Let n∈Z( 0) ○ GL_n (R≔{invertible n×n matrices with entries in R ○ GL_n (R is a group under matrix multiplication ○ Check: matrix multiplication is an operation on GL_n (R § If A,B∈GL_n (R § AB∈GL_n (R, since (AB)^(−1)=B^(−1) A^(−1) ○ Associativity § This is clear ○ Identity § I_n, the n×n identity matrix ○ Inverses § If A∈GL_n (R, its inverse is A^(−1) ○ Notice: When n 1, the operation in GL_n (R is not commutative Abelian Group • We say a group G is abelian, if ∀a,b∈G, a⋅b=b⋅a Proposition 9 • Statement ○ Let n∈Z( 0), and let a_1,a_2,b_1,b_2∈Z ○ If (a_1 ) ̅=(b_1 ) ̅, and (a_2 ) ̅=(b_2 ) ̅ in Z\/nZ ○ Then (a_1+a_2 ) ̅=(b_1+b_2 ) ̅, and (a_1 a_2 ) ̅=(b_1 b_2 ) ̅ • Proof: (a_1+a_2 ) ̅=(b_1+b_2 ) ̅ ○ Choose c_1,c_2∈Z s.t. c_1 n=a_1−b_1 and c_2 n=a_2−b_2 ○ (c_1+c_2 )n ○ =a_1−b_1+a_2−b_2 ○ =(a_1+a_2 )−(b_1+b_2 ) ○ Thus, ├ n┤|├ ((a_1+a_2 )−(b_1+b_2 ))┤ ○ So, (a_1+a_2 ) ̅=(b_1+b_2 ) ̅ ∎ • Proof: (a_1 a_2 ) ̅=(b_1 b_2 ) ̅ ○ Choose c_1,c_2∈Z s.t. c_1 n=a_1−b_1 and c_2 n=a_2−b_2 ○ a_1 a_2−b_1 b_2 ○ =a_1 a_2+a_1 b_2−a_1 b_2−b_1 b_2 ○ =a_1 (a_2−b_2 )+(a_1−b_1 ) b_2 ○ =a_1 c_2 n+b_2 c_1 n ○ =(a_1 c_2+b_2 c_1 )n ○ Thus, n|(a_1 c_2+b_2 c_1 ) ○ So, (a_1 a_2 ) ̅=(b_1 b_2 ) ̅ ∎ Well-definedness • Example ○ Say we want to "define" a map § f:Z\/2Z→Z § f(a ̅ )=a ○ f is not a function § 1 ̅=3 ̅ in Z\/2Z § But f(1 ̅ )=1≠f(3 ̅ )=3 ○ So we say that f is not well defined • How to check well-definedness ○ To check that a purported function f:A→B is well-defined ○ (i.e. to check f is a function) ○ one needs to check that a=a^′⇒f(a)=f(a′) Corollary 10 (Integers Modulo n) • Statement ○ If n∈Z( 0), Z\/nZ is a group under the operation § Z\/nZ×Z\/nZ→Z\/nZ § (a ̅,b ̅ )↦(a+b) ̅ ○ We will denote this operation by + ○ So a ̅+b ̅=(a+b) ̅ • Proof ○ Well-definedness § By proposition 9, the operation a ̅+b ̅=(a+b) ̅ is well-defined ○ Associative § Associativity is inherited from associativity of addition for Z ○ Identity § The identity is 0 ̅ § ∀a ̅∈Z\/nZ, a ̅+0 ̅=(a+0) ̅=a ̅=(0+a) ̅=0 ̅+a ̅ ○ Inverses § ∀a ̅∈Z\/nZ, the inverse of a ̅ is (−a) ̅ § a ̅+(−a) ̅=(a−a) ̅=0 ̅=(−a+a) ̅=(−a) ̅+a ̅$

Math 541 – 2/2

$Homework 1 (a) • Let A and B be nonempty sets, and let f:A→B be a function. • Suppose f is injective, prove that f has a left inverse • Since f is injective, ∀b∈im(f),∃!a∈A s.t. f(a)=b • Define g:B→A in the following way ○ Choose a_0∈A ○ If b∈im(f) § Choose a∈A s.t. f(a)=b § Define g(b)=a ○ If b∉im(f) § Define g(b)=a_0 • Check that g is a left inverse ○ If a∈A, (g∘f)(a)=g(f(a))=a ○ Thus, g∘f=id_A Example of The Euclidean Algorithm • Let a=97, b=20 • Use the Euclidean Algorithm to find (a,b) ○ 97=20×4+17 ○ 20=17×1+3 ○ 17=3×5+2 ○ 3=2×1+1 ○ Therefore (a,b)=1 • And then find x,y∈Z s.t. (a,b)=ax+by ○ (a,b)=1 ○ =3−2×1 ○ =3−(17−3×5)×1 ○ =3×6−17×1 ○ =(20−17×1)×6−17 ○ =20×6−17×7 ○ =20×6−(97−20×4)×7 ○ =97×(−7)+20×34 ○ We can take x=−7, y=34 Equivalence Class • Let X be a set, and let ~ be an equivalence relation on X • If x∈X, then the equivalence class represented by x is the set • [x]={x^′∈X│x~x^′ }⊆X Proposition 8 • Statement ○ Let X be a set with equivalence relationship ~ ○ If x,x^′∈X, then [x] and [x′] are either equal or disjoint • Proof ○ Suppose ∃y∈[x]∩[x^′ ] ○ It suffices to show if z∈X, then x~z⟺x^′~z ○ x~z⇒x^′~z § Suppose x~z § ⇒z~x (Symmetry) § ⇒z~y (Transitivity) § ⇒y~z (Symmetry) § ⇒x^′~z (Transitivity) ○ x~z⇐x^′~z § Suppose x′~z § ⇒z~x′ (Symmetry) § ⇒z~y (Transitivity) § ⇒y~z (Symmetry) § ⇒x~z (Transitivity) Integers Modulo n • Let n∈Z( 0) • The relation on Z given by a~b⟺n|(a−b) is an equivalence relation • The set of equivalence classes under ~ is denoted as Z\/nZ • We call this set integers modulo n (or integers mod n) • We can check that there are n elements in Z\/nZ • Use a ̅ to denote the equivalence class in Z\/nZ • Then Z\/nZ={0 ̅,1 ̅,2 ̅,…,(n−1) ̅ } Group • Definition ○ If G is a set equipped with a binary operation § G×G→G § (g,h↦g⋅h ○ that satisfy § Associativity: ∀g,h,k∈G, g⋅(hk)=(g⋅h⋅k § Identity: ∃1∈G s.t. ∀g∈G,1⋅g=g⋅1=g § Inverses: ∀g∈G, ∃g^(−1)∈G s.t. gg^(−1)=g^(−1) g=1 ○ Then we say G is a group under this operation • Z,Q,R,ℂ are groups with operation + ○ If a,b∈Z, then a+b∈Z (Similarly for Q,R,ℂ) ○ + is certainly associative in all 4 sets ○ 0 is the identity in each case ○ If a∈Z (or QRℂ), then the inverse of a is −a$

Shawn Zhong

Shawn Zhong

Math 541

Math 541 – 2/12

Math 541 – 2/9

Math 541 – 2/7

Math 541 – 2/5

Math 541 – 2/2

Search

WeChat Account