浙江大学：《离散数学》课程教学资源（PPT课件讲稿）第二章 算法（2.4）矩阵

DEFINITION 1 Matrices 矩阵 A matrix is a rectangular array of numbers. A matrix with m rows and n columns is called an m x n matrix The plural of matrix is matrices A matrix with the same number of rows as columns is called equal if they have the same number of rows and the same number of columns and the corresponding entries in every position are equal

M a t r i c e s 矩 阵 DEFINITION 1. 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 equal if they have the same number of rows and the same number of columns and the corresponding entries in every position are equal

DEFINITION 2 Matrices 矩阵 The ith row ofa is the 1 x n R 12 Let A= matrix ail, aj,., ain. The a. a.a. jth column of a is then X1 matrix The (i, j)th element or entry of A is the element aii that is, the number in the ith row and jth column ofA. A convenient shorthand notation for expressing the matrix A is to write A=ail, which indicates that a is the matrix with its (i, j)th element equal to a i

M a t r i c e s 矩 阵 DEFINITION 2. Let The (i, j)th element or entry of A is the element aij, that is, the number in the ith row and jth column of A. A convenient shorthand notation for expressing the matrix A is to write A = [aij], which indicates that A is the matrix with its (i, j)th element equal to aij. The ith row of A is the 1 × n matrix [ai1, ai2, …, ain]. The jth column of A is the n × 1 matrix

DEFINTION3 Matrices 矩阵 Leta=ai and b=bi be m X n matrices. The sum of A and b, denoted by a+ B, is the m x n matrix that has ai t bi as its (i,j)th element. In other words,A+ b ai +bil

M a t r i c e s 矩 阵 DEFINITION 3. Let A = [aij] and B = [bij] be m × n matrices. The sum of A and B, denoted by A + B, is the m × n matrix that has aij + bij as its (i, j)th element. In other words, A + B = [aij +bij]

DEFINITION4 Matrices 矩阵 Let a be an m x k matrix and b be a k x n matrix The product of A and B, denoted by ab, is the m X n matrix with (i, jth entry equal to the sum of the products of the corresponding elements from the ith row of a and the jth column of B In ab=cil, then 可=a1b1+ab2+…,+akbk

M a t r i c e s 矩 阵 DEFINITION 4. 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 with (i, j)th entry equal to the sum of the products of the corresponding elements from the ith row of A and the jth column of B. In AB = [cij], then Cij = ai1b1j + ai2b2j + … + aikbkj =

DEFINITION 5 Matrices 矩阵 The identity matrix of order n is the n X n matrix I i &,I, where al if i=j and 8-0 if j. Hence 01 了 00

M a t r i c e s 矩 阵 DEFINITION 5. The identity matrix of order n is the n × n matrix In = [ ], where =1 if i = j and = 0 if i ≠ j. Hence

DEFINITIONG Matrices 矩阵 Leta=ai be an m X n matrix. The transgose of A, denoted by a, is the n x m matrix obtained by interchanging the rows and columns ofA. In other words, ifa '=[bil, then bi=ai for I=1, 2,..., n and 1,2,…,,m

M a t r i c e s 矩 阵 DEFINITION 6. Let A = [aij] be an m × n matrix. The transqose of A, denoted by At , is the n × m matrix obtained by interchanging the rows and columns of A. In other words, if At = [bij], then bij = aji for I = 1, 2, … , n and j = 1, 2, … , m

DEFINITON7。 Matrices 矩阵 A square matrix A is called symmetric ifA=A. Thus A=[ail is symmetric if ai=ai forall i and i with 1≤ i<n and1≤j≤n

M a t r i c e s 矩 阵 DEFINITION 7. A square matrix A is called symmetric if A = At . Thus A = [aij] is symmetric if aij = aji for all i and j with 1≤i≤n and 1≤j≤n

DEFINITION 8 Matrices 矩阵 Let a=ail and b= bil be m X n zero-one matrices. Then the join ofA and B is the zero-one matrix with (i, jth entry aibi the join of A and b is denoted by AVB. The meet of A and B is the zero-one matrix with (i, j)th entry a i A bir The meet of A and B is denoted by A∧B

M a t r i c e s 矩 阵 DEFINITION 8. Let A = [aij] and B = [bij] be m × n zero-one matrices. Then the join of A and B is the zero-one matrix with (i, j)th entry aij∨bij. The join of A and B is denoted by A∨B. The meet of A and B is the zero-one matrix with (i, j)th entry aij∧bij. The meet of A and B is denoted by A∧B

DEFINITION 9 Matrices 矩阵 Leta=ai be an m x k zero-one matrix and b=[bil be a k x n zero-one matrix. Then the boolean product ofa and e, denoted by a⊙B, is the m× n matrix with (i,jth entry Icil where C=(an∧b)V(a2^b2)V…V(a∧b3)

M a t r i c e s 矩 阵 DEFINITION 9. Let A = [aij] be an m × k zero-one matrix and B = [bij] be a k × n zero-one matrix. Then the Boolean product of A and B, denoted by A⊙B, is the m × n matrix with (i, j)th entry [cij] where cij = (ai1∧b1j)∨(ai2∧b2j)∨…∨(aik∧bkj)

DEFINITION 10 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 ofr A. The rth Boolean product of a is denoted by ar. Hence A=A⊙A⊙A⊙A⊙AA⊙A⊙A R times (This is well defined since the Boolean product of matrices is associative. We also define a lol to be I

M a t r i c e s 矩 阵 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 A. The rth Boolean product of A is denoted by A[r]. Hence A[r] = A⊙A⊙A⊙A⊙A⊙A⊙A⊙A (This is well defined since the Boolean product of matrices is associative.) We also define A[0] to be In . DEFINITION 10. R times