Examples of Orders • Example 1 ○ A≔(■8(0&−1@1&−1))∈GL_2 (R ○ A3=(■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)
