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 Math 541 – 2/14 Feb 15, 2018 Shawn Math 541 No comments yet 1 … 27 28 29 30 31 … 41
![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)
