Math 541 – 2/21 Feb 21, 2018 Shawn Math 541 No comments yet Math 521 – 2/21 Feb 21, 2018 Shawn Math 521 No comments yet Math 541 – 2/19 Feb 21, 2018 Shawn Math 541 No comments yet Math 541 – 2/16 Feb 21, 2018 Shawn Math 541 No comments yet 2.6 Matrices Feb 21, 2018 Shawn Math 240 No comments yet 1 2
![Cyclic Group • Definition ○ A group G is cyclic if ∃g∈G s.t. ⟨g⟩=G • Note ○ A finite group G of order n is cyclic iff ∃g∈G s.t. |g|=n • Example 1: Z is cyclic ○ Z=⟨1⟩ ○ Z=⟨−1⟩ • Example 2: Z\/nZ is cyclic ○ If (a,n)=1, Z\/nZ=⟨a ̅ ⟩ ○ (We will prove this later) • Example 3: S_3 is not cyclic ○ Note: If (a_1,…,a_t )∈S_n is a t-cycle, then |(a_1,…,a_t )|=t ○ S_3={(1),(1 2),(1 3),(2 3),(1 2 3),(1 3 2)} ○ Every element in S_3 have order 1,2, or 3 ○ So S_3 cannot be cyclic Proposition 18 • Let G be a cyclic group • If |G|=∞, then G≅Z ○ Choose g∈G s.t. G=⟨g⟩ ○ Define a map f:Z→G by n↦g^n ○ Check homomorphism § If n_1,n_2∈Z § then f(n_1+n_2 )=g^(n_1+n_2 )=g^(n_1 ) g^(n_2 )=f(n_1 )f(n_2 ) § Thus, f is a homomorphism ○ Check surjectivity § Surjectivity is clear ○ Check injectivity § Suppose f(n_1 )=f(n_2 ) § Then g^(n_1 )=g^(n_2 ) § Without loss of generality, assume n_1≥n_2 § Then g^(n_1−n_2 )=1 § Since |g|=∞ § n_1−n_2=0 § i.e. n_1=n_2 § Thus f is injective • If |G|=n ∞, then G≅Z\/nZ ○ Choose g∈G s.t. G=⟨g⟩ ○ Define a map f:Z\/nZ→G by a ̅↦g^a ○ Check well-definedness § We need to check that f is well-defined. § That is we must show that if a ̅=b ̅ in Z\/nZ, then f(a ̅ )=f(b ̅ ) § Let a,b∈Z, suppose a ̅=b ̅ in Z\/nZ § Choose q∈Z s,t, nq=a−b § f(a ̅ )=g^a=g^(nq+b)=g^nq g^b=g^b=f(b ̅ ) § Thus, f is well-defined ○ Check homomorphism § f(a ̅+b ̅ )=g^(a+b)=g^a g^b=f(a ̅ )f(b ̅ ) § Thus, f is a homomorphism ○ Check surjectivity § Surjectivity is clear ○ Check injectivity § If f(a ̅ )=f(b ̅ ) § g^a=g^b § g^(a−b)=1 § ├ |g|┤|├ (a−b)┤ § n|(a−b) § a ̅=b ̅ § Thus f is injective Least Common Multiple • Definition ○ Let a,b∈Z where one of a,b is nonzero. ○ A least common multiple of a and b is a positive integer m s.t. § a|m and b|m § If a|m′ and b|m′, then m|m^′ ○ We denote the lcm of a and b by [a,b] ○ Define [0,0]≔0 • Uniqueness ○ Similar to the proof of uniqueness of gcd • Existence: If a,b∈Z, and one of a,b is nonzero, then ab/((a,b) ) is the lcm of a,b ○ ab/((a,b) ) is a multiple of a and b ○ Suppose m^′∈Z s.t. a|m′ and b|m′ ○ We must show ├ ab/((a,b) )┤|├ m′┤ ○ Choose q,q^′∈Z s,t, aq=m′ and bq^′=m′ ○ Choose x,y∈Z s.t. ax+by=(a,b) ○ m^′ (a,b)=m^′ (ax+by)=m^′ ax+m^′ by=bq^′ ax+aqby=ab(q^′ x+qy) ○ Thus ab|(m^′ (a,b)) ○ i.e. ab/((a,b) )=m^′ Proposition 19 • Statement ○ If G=⟨g⟩ is cyclic, and |G|=n ∞, then |g^a |=n/((a,n) ) • Proof ○ Let a∈Z ○ If a=0, this is clear ○ So, assume a≠0 ○ (g^a )^(n/((a,n) ))=g^(an/((a,n) ))=g^[a,n] =g^kn for some integer k ○ Thus, (g^a )^(n/((a,n) ))=(g^n )^k=1 since n=|g| ○ Suppose t∈Z( 0) and (g^a )^t=1 ○ By HW3, g^at=1⇒n|at ○ Thus, at is a common multiple of n and a ○ ├ [a,n]┤|├ at┤ ○ ⇒├ an/((a,n) )┤|├ at┤ ○ ⇒├ n/((a,n) )┤|├ t┤ ○ In particular, n/((a,b) )≤t Theorem 20 • Let G=⟨g⟩ be a cyclic group • Statement (1) ○ Every subgroup of G is cyclic ○ More precisely, if H≤G, then either H={1} or ○ H=⟨g^d ⟩, where d is the smallest positive integer s.t. g^d∈H • Statement (2) ○ If G is finite, then for all positive integers a dividing n ○ ∃! subgroup H≤G of order a. ○ Moreover, this subgroup is ⟨g^d ⟩, where d=n/a](https://shawnzhong.com/wp-content/uploads/2018/04/img_5ac5434f6845a.png)
![Definitions 2.18 • Let X be a metric space. All points/elements below are in X • Neighborhood ○ Definition § A neighborhood of p is a set N_r (p) § consisting of all points q such that d(p,q)r for some r∈R § r is the radius of N_r (p) ○ Example: R2 ○ Example: Taxicab metric • Limit point ○ Definition § A point p is a limit point of the set E⊂X if § every neighborhood of p contains a point q∈E and p≠q ○ Example: R2 ○ Example: (0,1)∈R § For (0,1)∈R, the limit points is [0,1] • Isolated point ○ Definition § If p∈E and p is not a limit point of E § then p is an isolated point of E ○ Example: Z in R § Every integers is an isolated point in R • Closed set ○ Definition § A set E is closed if every limit point of E is in E ○ Example: [0,1]∈R § In R, neighborhood of p∈R are open intevals cenerted about p § All of [0,1] is a limit point since § If x∈[0,1] □ The neighborhood about x is (x−r,x+r) □ (x−r,x+r)∩[0,1] is non-empty □ If x=0, then take q=min(x+r/2,1) □ Otherwise take q=max(x−r/2,0) □ So every point in [0,1] is a limit point § If x∉[0,1] □ i.e. x0 or x1 □ Take r={■8(|x|&if x0@|x−1|&if x1)┤ □ Then N_r (x)∩[0,1]=∅ □ So nothing outside of [0,1] is a limit point of [0,1] § So [0,1] contains all its limit points § Thus [0,1] is closed • Interior point ○ Definition § A point p is an interior point of a set E if § there exists a neighborhood N_r (p) that is a subset of E ○ Example: R2 § For the closed set S § The point x is an interior point of S § The point y is not an interior point of S (on the boundary of S) • Open set ○ Definition § E is an open set if every point of E is an interior point ○ Example: R2 § U is an open set, since ∀x∈U, ∃B_ϵ (x)⊂U ○ Example: (0,1)∈R § For x∈(0,1) § Take r=min(x,1−x) § N_r (x)⊂(0,1) § Thus every point in (0,1) is an interior point • Complement ○ Definition § The complement of E (denoted E^c) is {p∈X│p∉E} • Perfect ○ Definition § E is perfect if E is closed and every point of E is limit point of E • Bounded ○ Definition § E is bounded if there is a real number M and a point p∈E s.t. § d(p,q)M for all p∈E • Dense ○ Definition § E us dense in X if every point of X § is a limit point of E or a point of E (or both)](https://shawnzhong.com/wp-content/uploads/2018/03/img_5aa0d67746662.png)
![Matrices • Matrices are useful discrete structures that can be used in many ways. • For example, they are used to: ○ describe certain types of functions known as linear transformations. ○ Express which vertices of a graph are connected by edges (see Chapter 10). • Here we cover the aspect of matrix arithmetic that will be needed later. • Definition ○ A matrix is a rectangular array of numbers. ○ A matrix with m rows and n columns is called an m×n matrix. ○ The plural of matrix is matrices. ○ A matrix with the same number of rows as columns is called square. ○ Two matrices are equal if they have the same number of rows and the same number of columns and the corresponding entries in every position are equal. • Example: 3×2 matrix ○ [■8(1&1@0&2@1&3)] • Notation ○ Let m and n be positive integers and let § A=[■8(a_11&a_12&…&a_1n@a_21&a_22&…&a_2n@⋮&⋮&⋱&⋮@a_m1&a_m2&…&a_mn )] ○ The ith row of A is the 1×n matrix § [a_i1, a_i2,…,a_in]. ○ The jth column of A is the m×1 matrix: § [█(a_1j@a_2j@⋮@a_mj )] ○ The (i,j)th element or entry of A is the element a_ij ○ We can use A = [a_ij] to denote the matrix with its (i,j)th element equal to a_ij Matrix Arithmetic: Addition • Let A = [a_ij] and B = [b_ij] be m×n matrices. • The sum of A and B, denoted by A + B, is the m×n matrix that has a_ij + b_ij as its (i,j)th element. • In other words, A + B = [a_ij + bij]. • Example ○ [■8(1&0&−1@2&2&−3@3&4&0)]+[■8(3&4&−1@1&−3&0@−1&1&2)]=[■8(4&4&−2@3&−1&−3@2&5&2)] • Note that matrices of different sizes cannot be added. Matrix Multiplication • Let A be an m×k matrix and B be a k×n matrix. • The product of A and B, denoted by AB, is the m×n matrix that has its (i,j)th element equal to the sum of the products of the corresponding elements from the ith row of A and the jth column of B. • In other words, if AB = [c_ij] then c_ij=a_i1 b_1j+a_i2 b_2j+⋯+a_kj b_kj. • Example ○ [■8(1&0&4@2&1&1@3&1&0@0&2&2)][■8(2&4@1&1@3&0)]=[■8(14&4@8&9@7&13@8&2)] Matrix Multiplication is not Commutative • Let A=[■8(1&1@2&1)],B=[■8(2&1@1&1)], then • AB=[■8(3&2@5&3)],BA=[■8(4&3@3&2)] • Thus AB≠BA Identity Matrix and Powers of Matrices • The identity matrix of order n is the m×n matrix I_n=[δ_ij ], where ○ δ_ij = 1 if i = j ○ δ_ij = 0 if i≠j • I_n=[■(1&&@&⋱&@&&1)] • AI_n=I_m A=A when A is an m×n matrix • Powers of square matrices can be defined. When A is an n×n matrix, we have: ○ A^0=I_n ○ A^r=⏟(AA⋯A)┬(r times) Transposes of Matrices • Let A = [a_ij] be an m×n matrix. • The transpose of A, denoted by A^t ,is • the n×n matrix obtained by interchanging the rows and columns of A. • If A^t = [b_ij], then b_ij=a_ji for i =1,2,…,n and j = 1,2, …,m • The transpose of the matrix [■8(1&2&3@4&5&6)] is the matrix [■8(1&4@2&5@3&6)] Symmetric Matrices • A square matrix A is called symmetric if A=A^t. • Thus A = [a_ij] is symmetric if a_ij=a_ji for i and j with 1≤i≤n and 1≤j≤n. • The matrix [■8(1&1&0@1&0&0@0&1&0)] is square • Symmetric matrices do not change when their rows and columns are interchanged Zero-One Matrices • A matrix all of whose entries are either 0 or 1 is called a zero-one matrix. • Algorithms operating on discrete structures represented by zero-one matrices are based on Boolean arithmetic defined by the following Boolean operations: ○ b_1∧b_2={■8(1&if b_1=b_2=1@0&otherwise)┤ ○ b_1∨b_2={■8(1&if b_1=1 or b_2=1@0&otherwise)┤ Joint and Meet of Zero-One Matrices • Definition: Let A = [a_ij] and B = [b_ij] be an m×n zero-one matrices. • The join of A and B is the zero-one matrix with (i,j)th entry a_ij∨b_ij. • The join of A and B is denoted by A ∨ B. • The meet of of A and B is the zero-one matrix with (i,j)th entry a_ij∧b_ij. • The meet of A and B is denoted by A ∧ B. • Example ○ Find the join and meet of the zero-one matrices § A=[■8(1&0&1@0&1&0)] § B=[■8(0&1&0@1&1&0)] ○ The joint of A and B is § A∨B=[■8(1&1&1@1&1&0)] ○ The meet of A and B is § A∧B=[■8(0&0&0@0&1&0)] Boolean Product of Zero-One Matrices • Definition: ○ Let A = [a_ij] be an m×k zero-one matrix and B = [b_ij] be a k×n zero-one matrix. ○ The Boolean product of A and B, denoted by A⨀B, is the m×n zero-one matrix with (i,j)th entry c_ij=(a_i1∧b_1j )∨(a_i2∧b_2j )∨⋯∨(a_ik∧b_kj ). • Example: Find the Boolean product of A and B, where ○ A=[■8(1&0@0&1@1&0)],B=[■8(1&1&0@0&1&1)] ○ A⨀B=[■8(1&1&0@0&1&1@1&1&0)] Boolean Powers of Zero-One Matrices • Let A be a square zero-one matrix and let r be a positive integer. • The rth Boolean power of A is the Boolean product of r factors of A, denoted by A^[r] . • Hence, A^[r] =⏟(A⨀A⨀⋯⨀A)┬(r times) • We define A^[0] =I_n • The Boolean product is well defined because the Boolean product of matrices is associative • Example ○ Let A=[■8(0&0&1@1&0&0@1&1&0)] ○ Find A^[n] for all positive integers n ○ A^[2] =[■8(1&1&0@0&0&1@1&0&1)] ○ A^[3] =[■8(1&0&1@1&1&0@1&1&1)] ○ A^[4] =[■8(1&1&1@1&0&1@1&1&1)] ○ A^[5] =[■8(1&1&1@1&1&1@1&1&1)]](https://shawnzhong.com/wp-content/uploads/2018/02/img_5a8d89b6a92f7.png)
