北京郵電大學--計算機學院--離散數學-2.6-matrices-2014

1、Matrices（矩陣）,,2,2024/3/18,College of Computer Science & Technology, BUPT,§2.6 Matrices,A matrix is a rectangular array of objects (usually numbers).An m?n (“m by n”) matrix has exactly m horizontal rows, and n

2、vertical columns.Plural of matrix = matrices (say MAY-trih-sees)An n?n matrix is called a square matrix,whose order or rank is n.,a 3?2 matrix,Note: The singular formof “matrices” is “matrix,”not “MAY-trih-see”!,3,

3、2024/3/18,College of Computer Science & Technology, BUPT,Applications of Matrices,Tons of applications, including:Solving systems of linear equationsComputer Graphics, Image ProcessingModels within many areas of

4、Computational Science & EngineeringQuantum Mechanics, Quantum ComputingMany, many more…,4,2024/3/18,College of Computer Science & Technology, BUPT,Matrix Equality,Two matrices A and B are considered equal iff t

5、hey have the same number of rows, the same number of columns, and all their corresponding elements are equal.,5,2024/3/18,College of Computer Science & Technology, BUPT,Row and Column Order,The rows in a matrix are u

6、sually indexed 1 to m from top to bottom. The columns are usually indexed 1 to n from left to right. Elements are indexed by row, then column.,6,2024/3/18,College of Computer Science & Technology, BUPT,Matrices as

7、Functions,An m?n matrix A = [ai,j] of members of a set S can be encoded as a partial function fA: N?N→S, such that for i<m, j<n, fA(i, j) = ai,j.By extending the domain over which fA is defined, various

8、 types of infinite and/or multidimensional matrices can be obtained.,7,2024/3/18,College of Computer Science & Technology, BUPT,Matrix Sums,The sum A+B of two matrices A, B (which must have the same number of rows, a

9、nd the same number of columns) is the matrix (also with the same shape) given by adding corresponding elements of A and B. A+B = [ai,j+bi,j],8,2024/3/18,College of Computer Science & Technology, BUPT,Matrix

10、Products,For an m?k matrix A and a k?n matrix B, the product AB is the m?n matrix:I.e., the element of AB indexed (i,j) is given by the vector dot product of the ith row of A and the jth column of B (considered as ve

11、ctors).Note: Matrix multiplication is not commutative!,9,2024/3/18,College of Computer Science & Technology, BUPT,Matrix Product Example,An example matrix multiplication to practice in class:,10,2024/3/18,College of

12、 Computer Science & Technology, BUPT,n,n,Identity Matrices,The identity matrix of order n, In, is the rank-n square matrix with 1’s along the upper-left to lower-right diagonal, and 0’s everywhere else.,Kronecker Del

13、ta,,,,?1≤i,j≤n,11,2024/3/18,College of Computer Science & Technology, BUPT,Matrix Inverses,For some (but not all) square matrices A, there exists a unique multiplicative inverse A?1 of A, a matrix such that A?1A = In

14、.If the inverse exists, it is unique, and A?1A = AA?1.We won’t go into the algorithms for matrix inversion...,12,2024/3/18,College of Computer Science & Technology, BUPT,Matrix Multiplication Algorithm,procedure m

15、atmul(matrices A: m?k, B: k?n)for i := 1 to mfor j := 1 to n begincij := 0for q := 1 to kcij := cij + aiqbqjend {C=[cij] is the product of A and B},What’s the ? of itstime complexity?,Answer:?(mnk),13,20

16、24/3/18,College of Computer Science & Technology, BUPT,Powers of Matrices,If A is an n?n square matrix and p?0, then:Ap :? AAA···A (and A0 :? In)Example:,,p times,14,2024/3/18,College of Compute

17、r Science & Technology, BUPT,If A=[aij] is an m?n matrix, the transpose of A (often written At or AT) is the n?m matrix given by At = B = [bij] = [aji] (1?i?n,1?j?m),Matrix Transposition,,,Flipacrossdiagonal,15,202

18、4/3/18,College of Computer Science & Technology, BUPT,Symmetric Matrices,A square matrix A is symmetric iff A=At. I.e., ?i,j?n: aij = aji .Which of the below matrices is symmetric?,,,16,2024/3/18,College of Computer

19、 Science & Technology, BUPT,Zero-One Matrices,Useful for representing other structures.E.g., relations, directed graphs (later in this course)All elements of a zero-one matrix are either 0 or 1Representing False &

20、amp; True respectively.The join of A, B (both m?n zero-one matrices):A?B :? [aij?bij]The meet of A, B:A?B :? [aij?bij] = [aij bij],The 1’s in A join the 1’s in Bto make up the 1’s in C.,Where the 1’s in A meet the

21、1’s in B, we find 1’s in C.,17,2024/3/18,College of Computer Science & Technology, BUPT,Boolean Products,Let A=[aij] be an m?k zero-one matrix,& let B=[bij] be a k?n zero-one matrix,The boolean product of A and

22、 B is like normal matrix ?, but using ? instead of + in the row-column “vector dot product”:,A⊙B,18,2024/3/18,College of Computer Science & Technology, BUPT,Boolean Powers,For a square zero-one matrix A, and any k?0,

23、 the kth Boolean power of A is simply the Boolean product of k copies of A.A[k] :? A⊙A⊙…⊙A A[0] :? In,,k times,19,2024/3/18,College of Computer Science & Technology, BUPT,Basic properties of the