이산수학(Discrete Mathematics) 행렬(Matrices) 2016년 봄학기 강원대학교 컴퓨터과학전공 문양세

Plural of matrix = matrices 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 …

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

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. (각 원소는 행 색인, 열 색인의 순으로 표현한다.)

Row and Column Order (2/2) Matrices Let A be mn matrix [ai,j], ith row = 1n matrix [ai,1 ai,2 … ai,n], jth column = m1 matrix

A+B = C = [ci,j] = [ai,j+bi,j] where A = [ai,j] and B = [bi,j] Example 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

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: 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번째 행의 곱이다.)

Matrix multiplication is not commutative! (교환법칙 성립 안 함) Matrix Products (2/2) Matrices Example 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 Both AB and BA can be defined when m = n = r = s

What’s the  of its time complexity? Matrix Multiplication Algorithm Matrices 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)·( What’s the  of its time complexity? (1)+ Answer: (mnk) (k) · (1))

Identity 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인 행렬) AIn = InA = A

A A-1 I3 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. A A-1 I3

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

Symmetric Matrices (대칭 행렬) A square matrix A is symmetric iff A=At. I.e., i,jn: aij = aji . Which is symmetric?

Powers of Matrices (멱행렬) If A is an nn square matrix and p0, then: Ap  AAA···A (A0  In) Example: p times

Zero-One Matrices (0-1 행렬) 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]

A⊙B 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

Boolean Products (부울 곱) (2/2) Matrices Example: 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.}

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 Example: k times ⊙ ⊙ ⊙

Homework #4 Matrices