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)]
