이산수학(Discrete Mathematics) - 행렬(Matrices)

이산수학(Discrete Mathematics) 행렬(Matrices) 이산수학(Discrete Mathematics) 행렬(Matrices) Introduction Introduction Matrices A matrix (say MAY-trix) is a rectangular array of objects (usually numbers). (행렬은 수의 사각형 배열이다 .) An m.n (“m by n”) matrix has exactly m horizontal rows, and n vertical columns. (m개의 행과 n개의 열을 갖는 행렬 ) Plural of matrix = matrices An n.n matrix is called a square matrix, whose order is n. (행과 열의 개수가 같은 행렬을 정방행렬이라 한다 .) Tons of applications: . Models within Computational Science & Engineering . Computer Graphics, Image Processing, Network Modeling . Many, many more … Page 2 Matrix Equality Matrix Equality Matrices Two matrices A and B are equal iff they have the same number of rows, the same number of columns, and all corresponding elements are equal. (두 행렬이 같은 수의 행과 열을 가지며 각 위치의 해당 원소의 값이 같으 면 “두 행렬은 같다”고 정의한다 .) Example .. . .. . . ... . .. . . ... . .. . .06102361236123 Page 3 Row and Column Order (1/2) Row and Column Order (1/2) Matrices The rows in a matrix are usually indexed 1 to m from top to bottom. (행은위에서아래로1~m의색인값을갖는다.) The columns are usually indexed 1 to n from left to right. (열은왼쪽에서오른쪽으로1~n의색인값을갖는다.) Elements are indexed by row, then column. (각 원소는 행 색인 , 열 색인의 순으로 표현한다 .) .. . . . . . . . . . . . . .. n,m,m,mn,,, n,,, j,iaaaaaaaaaa . .... . . 212221212111A Page 4 Matrices Row and Column Order (2/2) Let A be m.n matrix [ai,j], ith row = 1.n matrix [ai,1 ai,2 … jth column = m.1 matrix 1,2, , ... jjmjaaa .. .. .. .. .. .. .. .... ai,n], Page 5 Matrix Sums Matrices The sum A+B of two m.n matrices A, B is the m.n matrix given by adding corresponding elements. (A+B는 (i,j)번째 원소로서 ai,j+bi,j 를 갖는 행렬이다 .) A+B = C = [ci,j] = [ai,j+bi,j] where A = [ai,j] and B = [bi,j] Example . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252313244211031143043322101 Page 6 Matrix Products (1/2) Matrix Products (1/2) Matrices For an m.k matrix A and a k.n matrix B, the product AB is the m.n matrix: .... . .. . ..... kj,,ij,ibac1. ..CAB I.e., element (i,j) of AB is given by the vector dot product of the ith row of A and the jth column of B (considered as vectors). (AB의원소(i,j)는A의i번째열과B의j번째행의곱이다.) 1,11,21,1,11,21,1,2,12,22,1,11,21,2,12,22,2,2,12,22, ,1,2, ,1,2,, ,1,2, ... ............ ......... ... ...... ... kjnknjniiikkkkjknmmmkaaabbbbaaacccbbbbcccaaabbbbaaa .. .. .... .... ..... .... .......... .... , ,1,2,... nijmmmncccc .. .. .. .. .. .... Page 7 Matrix Products (2/2) Matrix Products (2/2) Matrices Example .. . .. . . .. . . . . . . . . . . . . . .. . .. .. 311231501130102020110302110 Matrix multiplication is not commutative! (교환법칙 성립 안 함 ) . A= m.n matrix, B = r.s matrix . AB can be defined when n = r . BA can be defined when s = m BAABBA ... . .. . ... . .. . . .. . .. . ... . .. . . 2334352311121211, . Both AB and BA can be defined when m = n = r = s Page 8 Matrices Matrix Multiplication Algorithm procedure matmul(matrices A: m.k, B: k.n) for i := 1 to m for j := 1 to n begin ci,j := 0 for q := 1 to k ci,j := ci,j + ai,qbq,j end {C=[ci,j] is the product of A and B} .(m)· .(n)· ( .(1)+ .(k) · .(1) ) What’s the .of its time complexity? Answer: .(mnk) .... . .. . ..... kj,,ij,ibac1. ..CAB Page 9 Identity Matrices ( 항등행렬) Identity Matrices ( 항등행렬) Matrices The identity matrix of order n, In, is the order-n matrix with 1’s along the upper-left to lower-right diagonal and 0’s everywhere else. ((i,i)번째 원소가 1이고, 나머지는 모두 0인 행렬 ) . . . . . . . . . . . . ... . .. . .... . . 100010001if 0if 1 . .... . . jijinI AIn = InA = A Page 10 Matrix Inverses ( 역행렬) Matrix Inverses ( 역행렬) Matrices 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. (정방 행렬 A에 대해서 하나의 유일한 역행렬 A-1 이 존재한다 .) If the inverse exists, it is unique, and A-1A = AA-1 . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. . 100010001111354587 311121132 A A-1 I3 Page 11 Matrix Transposition ( 전치행렬) Matrix Transposition ( 전치행렬) Matrices If A=[ai,j] is an m.n matrix, the transpose of A (often written At or AT) is the n.m matrix given by At = B = [bi,j] = [aj,i] (1.i.n,1.j.m) Flip across diagonal . . . . . . . . . . . .... . .. . .. 231102210312t Page 12 Symmetric Matrices ( 대칭행렬) Symmetric Matrices ( 대칭행렬) Matrices A square matrix A is symmetric iff A=At. I.e., .i,j.n: aij = aji . Which is symmetric? . . . . . . . . . . . . 211120103 . . . . . . . . . . . . . 213101312 . . . . . . . . . . 111111 Page 13 Powers of Matrices ( 멱행렬) Powers of Matrices ( 멱행렬) Matrices If A is an n.n square matrix and p.0, then: Ap . AAA···A (A0 . In) p times Example: Page 14 Zero-One Matrices (0-1 행렬) Zero-One Matrices (0-1 행렬) Matrices Useful for representing other structures. . E.g., relations, directed graphs (later in course) All elements of a zero-one matrix are 0 or 1 . Representing False & True respectively. The meet of A, B (both m.n zero-one matrices): A.B :. [aij.bij] (= [aij bij]) The join of A, B: A.B :. [aij.bij] .. . .. . .... . .. . .. .. . .. . ... . .. . . 010000 011111011010 010101BABABA, , Page 15 Boolean Products ( 부울곱) (1/2) Boolean Products ( 부울곱) (1/2) Matrices 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 B is like normal matrix multiplication, but . using “.” instead “+” . using “.” instead of “.” A⊙B .... . .. . ...... jikijbac.. .1C Page 16 Boolean Products ( 부울곱) (2/2) Boolean Products ( 부울곱) (2/2) Matrices Example: 1011001, 01110110011011001110011001110011 011110011011001110 .. .... ...... ...... ............. .... ............... ................. ABAB()()()()()() ()()()()()() ()()()()()() ⊙ Algorithm of Boolean Product procedure Boolean product(A,B: zero-one matrices) for i := 1 to m for j := 1 to n begin cij := 0 for q := 1 to k cij := cij .(aiq .bqj) end {C = [cij] is the Boolean product of A and B.} Page 17 Boolean Powers ( 부울거듭제곱) Boolean Powers ( 부울거듭제곱) Matrices For a square zero-one matrix A, and any k.0, the kth Boolean power of A is simply the Boolean product of k copies of A. (A의 k 부울린 거듭제곱 ) A[k] . A⊙A⊙…⊙A, A[0] . In k times Example: 110111111001, 100, 110100110111111 111, 111 ...... ...... ........... ............ .. .. ...... .... [2][3][2] [4][3][n][5][4] AAAAAAAAAAAAA⊙⊙ ⊙ Page 18