이산수학(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