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 2.5 Cardinality of Sets Feb 21, 2018 Shawn Math 240 No comments yet Math 521 – 2/19 Feb 19, 2018 Shawn Math 521 No comments yet Math 521 – 2/16 Feb 19, 2018 Shawn Math 521 No comments yet 1 … 27 28 29 30 31 … 84
![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)
![Metric Space • Definition ○ A set X of points is called a metric space if ○ there exists a metric or distance function d(p,q):X×X→R such that § Positivity □ d(p,q)0 if p,q∈X and p≠q □ d(p,p)=0 for all p∈X § Symmetry □ d(p,q)=d(q,p) for all p,q∈X § Triangle Inequality □ d(p,q)≤d(p,r)+d(r,q) for all p,q,r∈X • Example 1 ○ X=Rk ○ d(p ⃗,q ⃗ )=|p ⃗−q ⃗ | ○ If k=1, this is just standard numerical absolute value ○ and d is distance on the number line • Example 2 (Taxicab metric) ○ X=R2 ○ d((p_1,p_2 ),(q_1,q_2 ))=|p_1−q_1 |+|p_2−q_2 | where p_1,p_2,q_1,q_2∈R ○ Is this a true metric space? ○ Positivity § Clearly d((p_1,p_2 ),(q_1,q_2 ))≥0 since it is a sum of absolute values § Suppose d((p_1,p_2 ),(q_1,q_2 ))=0 □ |p_1−q_1 |+|p_2−q_2 |=0 □ |p_1−q_1 |=−|p_2−q_2 | □ {█(|p_1−q_1 |=0@|p_2−q_2 |=0)┤⇒{█(p_1=q_1@p_2=q_2 )┤ □ i.e. (p_1,p_2 )=(q_1,q_2 ) § Suppose (p_1,p_2 )=(q_1,q_2 ) □ d((p_1,p_2 ),(q_1,q_2 ))=|p_1−q_1 |+|p_2−q_2 |=|0|+|0|=0 § Thus d((p_1,p_2 ),(q_1,q_2 ))=0 iff (p_1,p_2 )=(q_1,q_2 ) ○ Symmetry § d((p_1,p_2 ),(q_1,q_2 ))=|p_1−q_1 |+|p_2−q_2 | § =|q_1−p_1 |+|q_2−p_2 |=d((q_1,q_2 ),(p_1,p_2 )) ○ Triangular Inequality § d((p_1,p_2 ),(r_1,r_2 ))+d((r_1,r_2 ),(q_1,q_2 )) § =|p_1−r_1 |+|p_2−r_2 |+|r_1−q_1 |+|r_2−q_2 | § =(|p_1−r_1 |+|r_1−q_1 |)+(|p_2−r_2 |+|r_2−q_2 |) § ≥|p_1−r_2+r_1−q_1 |+|p_2−r_2+r_2−q_2 | by Triangle Inequality of R § =|p_1−q_1 |+|p_2−q_2 | § =d((p_1,p_2 ),(q_1,q_2 )) Definition 2.17 • Interval ○ Segment (a,b) is {x∈Raxb} (open interval) ○ Interval [a,b] is {x∈Ra≤x≤b} (closed interval) ○ We can also have half-open intervals: (a,b] and [a,b) • k-cell ○ If a_ib_i for i=1,2,…,k ○ The set of points x ⃗=(x_1,x_2,…,x_k ) in Rk ○ that satisfy a_i≤x_i≤b_i (1≤i≤k) is called a k-cell • Ball ○ If x ⃗∈Rk and r0 ○ the open ball with center x ⃗ with radius r is {y ⃗∈Rk│|x ⃗−y ⃗ |r} ○ the closed ball with center x ⃗ with radius r is {y ⃗∈Rk│|x ⃗−y ⃗ |≤r} • Convex ○ We call a set E⊂Rk convex if ○ λx ⃗+(1−λ) y ⃗∈E, ∀x ⃗,y ⃗∈E, 0λ1 ○ i.e. All points along a straight line from x ⃗ to y ⃗ and between x ⃗ and y ⃗ is in E • Example: Balls are convex ○ Given an open ball with center x ⃗ and radius r ○ If y ⃗,z ⃗∈B, then |y ⃗−x ⃗ |r and |z ⃗−x ⃗ |r ○ |λz ⃗+(1−λ) y ⃗−x ⃗ | ○ =|λz ⃗+(1−λ) y ⃗−(λ+1−λ) x ⃗ | ○ =|λz ⃗−λx ⃗+(1−λ) y ⃗−(1−λ) x ⃗ | ○ ≤|λz ⃗−λx ⃗ |+|(1−λ) y ⃗−(1−λ) x ⃗ | by Triangle Inequality ○ =λ|z ⃗−x ⃗ |+(1−λ)|y ⃗−x ⃗ | ○ λr+(1−λ)r=r ○ Thus |λz ⃗+(1−λ) y ⃗−x ⃗ |r ○ i.e. λz ⃗+(1−λ) y ⃗∈B Definition 2.18 (a) Neighborhood (b) Limit point (c) Isolated point (d) Closed (e) Interior point (f) Open (g) Complement (h) Perfect (i) Bounded (j) Dense](https://shawnzhong.com/wp-content/uploads/2018/03/img_5aa0d2d37f657.png)
