离散数学课件-第2章-6.ppt

1、12022-12-24离散数学Discrete Mathematics 汪荣贵汪荣贵 教授教授合肥工业大学软件学院专用课件合肥工业大学软件学院专用课件2010.04&学习内容学习内容引言引言矩阵运算矩阵运算矩阵乘法矩阵乘法矩阵转置和幂矩阵转置和幂0-1矩阵矩阵&矩矩 阵阵离散数学中用矩阵表示集合中元素之间的关系例如矩阵用于通信网络模型交通运输系统模型&引言引言定义1 矩阵是数的矩形数组。m行n列的矩阵称为mn阶矩阵或mn矩阵。行数和列数相同的矩阵称为方阵。DEFINITION 1.A matrix is a rectangular array of numbers.A matrix with

2、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.A的第

3、i行是1 n矩阵ai1，ai2ain。A的第i列是n 1矩阵定义2 令 A的第（i，j）或第（i，j）元素时aij，即第i行第j列上的数。方便的表示矩阵A的简写符号A=aij,表示A是第(i,j)元素为aij的矩阵 LetThe(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

4、 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&矩阵运算矩阵运算定义定义3 令A=aij和B=bij为mn矩阵。A和B的和用A+B表示，这是以aij+bij为其第（i，j）元素的矩阵。换言之，A+B=aij+bij。Let A=aij and B=bij be m n matrices.The sum of A and B,denoted

5、 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.大小相同的两个矩阵的和是将它们对应位置上的元素相加得到的。大小不同的矩阵不能相加，因为两个矩阵的和只对行数和列数都一样的两个矩阵才有定义。&矩阵运算矩阵运算定义4 令A为mk矩阵，B为kn矩阵。A和B的乘积AB是个mn矩阵，其第(i,j)元素等于A的第i行和B的第j列对应元素乘积之和。换言之，若AB=cij，则Cij=ai1b1j+ai2b2j+aikbkj=Let A be an m k matrix and

6、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=例若有定义求解解 因为A是4 3矩阵而B是3 2的矩阵，所以A和B的乘积有定义，是4 2的矩阵；A的行与B的列对应元素相

7、乘，然后再把乘积加起来；矩阵乘法是不能交换的。若A和B为矩阵，AB和BA不一定相同&矩阵乘法矩阵乘法例5 用算法1计算两个n n整数矩阵的乘积，需要做多少次整数加法和整数乘法解：在A和B的乘积中n n个元素，计算每个运算要做n次乘法和n-1次加法；所以，一共需要做n3 和n2(n-1)例6 A1、A2 和A3分别是 30*20，20*40及40*10的整数矩阵，以什么次序计算A1、A2 和A3的乘积，使用的整数乘法次数最少。解：有两种次序A1（A2 A3）（A1、A2）A3；若A2和A3先相乘，需要做20*40*10=8000次整数乘法来计算20*10矩阵A2 A3；然后需要30*20*10=

8、6000次乘法来计算A1A2 和A3的乘积；共使用了8000+6000=14000次乘法；若A1、A2先相乘，必须做30*40*20=24000次乘法来计算30*40矩阵A1A2；然后需要30*40*10=12000次乘法以计算A1A2 和A3的乘积；共做了24000+12000=36000次乘法。&矩阵的转置和幂矩阵的转置和幂定义5 n阶单位矩阵式nn矩阵In=ij,其中ij=1若ijij=0若ij。因此用大小适合的单位矩阵乘一个矩阵不改变该矩阵。换言之，若A是mn矩阵，则有AIn=ImA=A可以定义方阵的幂。若A是nn矩阵，则有定义定义6 令A=aij为mn矩阵。A的转置，用At表示，是交

9、换A的行和列得到的nm矩阵。换言之，若 At=bij，则bij=aji，i=1，2，,n，j=1，2，m。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.定义定义7 若方针A和它的转置相等，即A=At，则A称为对称矩阵，因此A=aij为对

10、称矩阵的条件是对所有i，j，lin，1j n，aij=aji。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 1in and 1jn.注意注意，矩阵对称的充分必要条件一是方阵；二是对主对角线（由第i行第i列的元素组成，i是行和列任一序数）对称。这一对称如图所示：&0-10-1矩阵矩阵元素非0即1的矩阵称为0-1矩阵。0-1矩阵通常表示离散结构。使用这些结构的算法的基础是以0-1矩阵做布尔运算。布尔运算基于由下式定义

11、的一对字位上的运算和:定义定义8 令A=aij和B=bij为mn阶0-1矩阵。A和B的并，用A B表示，是个0-1矩阵，其（i，j）元素为aij bij。A和B的交，用A B表示，是个0-1矩阵，其（i，j）元素时aij bij 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 aijbij.The join of A and B is denoted by AB.The meet of A and B is the zer

12、o-one matrix with(i,j)th entry aijbij.The meet of A and B is denoted by AB.定义定义9 令A=aij为mk阶0-1矩阵，B=bij为kn阶0-1矩阵。A和B的布尔乘积，A B表示，是mn矩阵cij，其中cij=(ai1 b1j)(ai2 b2j)(aik bkj)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

13、n matrix with(i,j)th entry cij wherecij=(ai1b1j)(ai2b2j)(aikbkj).注意注意A A和和B B的布尔乘积的计算方法的布尔乘积的计算方法类似于这两个矩阵的普通乘积，类似于这两个矩阵的普通乘积，但要用运算但要用运算代替加法，用运算代替加法，用运算代替乘法。代替乘法。定义10 令A为0-1方阵，r为正整数。A的r次布尔幂是r个A的布尔乘积。A的r次布尔幂用Ar表示，因此（由于矩阵的布尔乘积是可结合的，这一定义式合理的。）我们常把A0定义为In Let A be a square zero-one matrix and let r be a

14、positive integer.The rth Boolean power of A is the Boolean product of r A.The rth Boolean product of A is denoted by Ar.Hence Ar=A A A A A A A A (This is well defined since the Boolean product of matrices is associative.)We also define A0 to be In.DEFINITION 10.R times例例12 若A和B为nn阶0-1矩阵，计算AB需要做什么词字位运算？解：解：A B中n2个元素。用算法2，需要n次和n次 来计算A B的一个元素。因此每求一个元素需要2n次字位运算。所以用算法2计算A B需要2n3次字位运算。本节内容到此结束本节内容到此结束