Vector Space Vector space : 모든 n 차원컬럼벡터의집합 : {, :, } (, 2), (2, 5), (-2.4, 3), (2.7, -3.77), (,), 이차원공간을모두채움 : {,, :,, } (2,3,4), (3,2,-5), Vector spa

Size: px

Start display at page:

Download "Vector Space Vector space : 모든 n 차원컬럼벡터의집합 : {, :, } (, 2), (2, 5), (-2.4, 3), (2.7, -3.77), (,), 이차원공간을모두채움 : {,, :,, } (2,3,4), (3,2,-5), Vector spa"

은우 현
6 years ago
Views:

1 Seoul National University Vector Space & Subspace Date Name: 김종권

2 Vector Space Vector space : 모든 n 차원컬럼벡터의집합 : {, :, } (, 2), (2, 5), (-2.4, 3), (2.7, -3.77), (,), 이차원공간을모두채움 : {,, :,, } (2,3,4), (3,2,-5), Vector space 의성질 u, v è cu + dv closed to linear combination

3 Vector Space & Subspace Ax m by n A 컬럼벡터의 Linear combination (:, ) + (:, 2) + (:, ) m 차원컬럼벡터 n 개의 linear combination A의성질에따라 A의컬럼벡터가 space를정의할수있고일부 Subspace를정의할수있음 특수케이스 : n by n matrix A A is invertible 어떤 n 차원벡터 b 에대해서도 Ax=b 를만족하는 x를구할수있음 èx를조정해서 Ax는어떤 b 가될수있게함 è A 컬럼벡터의 linear combination이 space를차지함 A is singular è b 를만족못할수있음 Ax 는의일부스페이스를정의

4 Column Space & Subspace Column space: C(A) 행렬 A 의컬럼벡터의 linear combination 으로형성된 space 컬럼벡터가 n 차원벡터라면 C(A) Subspace 벡터 space 의일부 Subspace 는 linear combination 에 closed 되어야함 u, v è cu + dv S 는 벡터를포함해야함

5 Vector Space & Subspace Example = 모든 b 에대한 x 해가있음 è 가모든를만들지못함 = 특정한 b 에대한 x 해가있음 è 가모든를만들지못함

6 Vector Space & Subspace Example

7 Vector Space & Subspace 컬럼스페이스 : C(A) A 의컬럼벡터의 linear combination

8 Independent Vectors n 차원벡터,,, 만약,,, 가서로 independent ( 독립적 ) 이면,,, 의 linear combination 은을전부채움 = 로표현할수없음 A = [ ] 은 invertible C(A) = 만약 n 개중 m 개벡터만 independent 하다면,,, : independent vector = for k > m A = [ ] 은singular C(A)

9 Examples Independent,, =, 2 2, 3 Dependent,, =, 2 3, 3 4 3,, = 2, 2 2 4,

10 Exercises Subspace 가아닌것은? 제로벡터, Z (x, y, z) that satisfies 2x + 5y + z =5 (x, y, z) that satisfies 2x + 5y + z = = 2, = 2, = 2 2 Ax=, Ax= 의해는있으나 Ax= 의해는없는 3 by 3 matrix A 를구하시오 일반적인 m 차원벡터,, 가있다. Ax=, Ax= 의해는있으나 Ax= 의해는없는 m by n matrix A 를구하시오

11 Null Space Ax = 만약 n by n 향렬 A 가 invertible 하다면 è x= 은 Ax = 을만족하는유일한해 만약 n by n 향렬 A 가 singular 하다면 è Ax = 을만족하는해가무수히많음, 가 Ax = 을만족하는해라고하면 è, 의 linear combination + 역시해가됨 N(A): Null space of A Ax = 의해의집합 Null space 를어떻게구할까?

12 Example = x + y + z = x + 2y + 2z = x + 2y + 3z = Pivot 컬럼 Forward elimination Row Echelon Form Back substitution Reduced Row Echelon Form (RREF

13 Example A 의컬럼스페이스와 Null 스페이스는? 3 개의 3 차원 pivot 컬럼벡터 è Independent C(A) = X = 은 Ax = 의유일한해 N(A) = Z, 영벡터의집합

14 Example = è 2 2 è 의 C(A), N(A) 를구하시오 è Pivot 컬럼 Free 컬럼 Free 컬럼은 pivot 컬럼의 Linear combination 으로표현될수있음 C(A): Pivot 컬럼,, 의 linear combination è 2 차원 subspace N(A): + + = Pivot variable:, Free variable: Free variable에임의값을넣은다음, 구함 ( 특수해, special solution) Independent 한특수해들의 = è =-, = N(A) = Linear combination

15 Exercise 다음 matrix 의 C(A), N(A) 를구하시오 A= =

16 Column and Null- Space m by n matrix A m 차원컬럼벡터 n 개의 linear combination Independent 한컬럼벡터의수, p C(A): p 개 independent vector (m 차원 ) 의 linear combination N(A): n-p 개 independent 한 n 차원특수해 (special solution) 의 linear combination

17 Example A: 3 by 4 matrix è è è è P F P F P F P F = Free variable,, 에임의의값대입해서특수해구함 =, = è =-, = è (-,., ) =, = è =-, = è (-,, -, )

18 Example N(A) Linear combination of, C(A) =?

19 Exercise Null space of A= Null space of A= Null space of A= A: 3 by 4 matrix, Ax = 의 special solution 은다음과같다 = 3, = 2 6. N(A) 를구하시오. 2. 이런 N(A) 를구성하는행렬 A 를구하시오

20 Rank Rank of A Independent 컬럼 (row) 벡터의수 Pivot 컬럼 (row) 의수 Rank 가 인행렬 A = è 3 컬럼 2 3, 3 6 9, 2 3 = [ 3 ] A= è = è = è, 는서로직교 은모두라인 u = 2 3 상에있음 3 차원공간에서 = [ 3 ] 에직교하는벡터들의 linear combination 이 null space 형성 =,, =, = è (-3,, ) =, = è (-,,

21 Examples Rank 행렬 A= , 3 5, 5 2, [6] RREF(A)

22 Row Space Independent row 벡터의 linear combination Example 3 è Row space: -dimensional 선 [ 3 ] è Null space 는? 3 2 합 è Row space: 로우벡터 [ 3 ], [ 2] 의선형조 è Null space 는?? Column space 의 dimension Row space 의 dimension

23 Special Solutions A= è R = E=, = Ax =, Rx= = =

24 Special Solutions = Free variable (,, ) 에 (,, ), (,, ), (,, ) 대입해 서 special solution 3개구함 = 3, = 2 4, = 3 m by n 행렬 A Rank(A) = r 이라면 Independent column(row) 의수는? Free variable 의수는? N(A) 의 dimension 은?

25 Special Solutions R = r pivot rows m-r zero rows r pivot columns n-r free columns Null space Linear combination of special solutions =, =,, = Null space matrix, N =,

26 Exercises R=[ 2 3] 의 N(A) 를구하시오 A= 2 시오. 2 의 rank 및 special solution 을구하

27 Exercises 다음 rank matrix 를 A= 형태로 factorization 하시오 다음 rank 2 matrix 를 R을이용하여 (3 by 2) times (2 by 4) 형태인 + 형태로 factorization 하시오 A= = = R

28 Complete Solution n by n matrix A, Ax=b: 만약 A 가 invertible 하면 x의 unique 해는 b Ax=: 만약 A 가 singular 하고 rank 가 r 이면 n-r 차원 null space 가짐 A 의 rank 가 r ( n) 인경우, Ax = b 의해는 해가없는경우 b 가 C(A) 에속하지않음 해가있는경우 b 가 C(A) 에속함 : A 의컬럼벡터들의 linear combination 으로 b 를만들수있음 Ax = b 의해가있는경우무한개있음 Ax = b 의해를 particular solution 이라고함 ( ) Particular b 를만드는벡터 linear combination Ax = 의해를 special solution 이라고함 ( ) Complete solution of Ax = b + + ( )

29 Example A: 3 by 4 matrix = è Special solutions, = Let =, = è =, =6 =(, 6,, ): particular solution =, Consistent 2 6, = 2 Complete solution,

30 Example = 6 7à = -2 No solution to Ax = b Only special solutions

31 Ax = b, A: m by n matric Assume n > m Rank of A is r ( m) [A b] will be reduced to R = r I n-r F d g r m-r C(A) 의차원수는? 만약 g =, Ax = b 의 n 차원 particular solution = n-r 개 n 차원 special solutions 가짐 만약 g, Ax = b 는해가없음 n-r 개 n 차원 special solution 만존재 Full row rank, r=m m n-m I F d C(A) 의차원수는?

32 Ax = b, A: m by n matric Assume n < m Rank of A is r ( n) [A b] will be reduced to R = r I n-r F d r g m-r 만약 g =, Ax = b 의 n 차원 particular solution = n-r 개 n 차원 special solutions 가짐 만약 g, Ax = b 는해가없음 n-r 개 n 차원 special solution 만존재 n Full column rank, r=n No special solutions g? I d g n m-n

33 Example A: 4 by 3 matrix , = è è , = è è

34 Full Row/Column Rank Full Column Rank (r=n) A 의모든컬럼벡터는 pivot 컬럼 Free 컬럼 (variable) 및 special solution 없음 è N(A) = Ax=b 는해가없거나있으면유일함 Full Row Rank (r=m) A 의모든로우벡터는 pivot row 임 (R 에 zero row 없음 ) N-m 개 free 컬럼 (variable) 및 special solution 있음 è N(A) 는 n-r 차원공간 C(A) = Ax=b 의항상해를가지며무한개가질수있음

35 Exercises. Linear equation system = = = A) [A b] 를 elimination 하여 [U c] 형태그리고 [R d] 형태로변환하시오 B) Ax = b 가해를가질수있는 b, b2, b3 의조건을구하시오 C) 컬럼스페이스 C(A) 를구하시오 D) Special solution을구하고 N(A) 를구하시오 E) b=(, 6, -6) 일때의 particular solution 및 complete solution을구하시오

36 Exercises 2. Ax=b 의해가다음과같을때행렬 A 의형태에대해설명하시오 A) 유일한해를가짐 B) 모든해는다음과같은형태임 : = 2 + C) 해가없음 D) 모든해는다음과같은형태임 : = E) 무한개의해를가짐

37 Exercises 3. = 오 , b= 4 2 의 complete solution 을구하시

38 Independent n 차원벡터,,, 이 (Linearly) Independent 를,,,, 의 linear combination 으로표현할수 없음 [,,, ] = 을만족하는유일한해는 x= 임 Example 3 개의 3 차원벡터,,,,, 가 independent 하면이들의 linear combination 은를형성 è C([,, ]) =,, 가 independent 하지않으면이들의 linear combination 은를형성하지못함

39 Exercise 다음중 independent 벡터는 (, ) & (, ) (, ) & (,.) (, ) & (-, -) (, ) & (, )

40 Space Spanning 컬럼벡터는컴럼스페이스 C(A) 를 span 함 어떤공간 (space) 에대해서벡터의 linear combination 이공간을다채우면공간을 span 한다고함 (,, ), (,, ), (,, ) 은를 span 함 (,, ), (,, ), (,, ) 은의 subspace 인 (a, b, ) plane 을 span함 (,, ), (-, -, ) 은의 subspace 인 (a, a, ) line을 span함

41 Row Space Recall: 어느행렬 A 의 C(A) 는 A 의컬럼벡터가 span 한공간 Row space C( ) A 의로우벡터 ( 또는 의컬럼벡터 ) 가 span 한공간 n 차원벡터 m 개가 span 하는공간 Examples A= 2 3 A=

42 Basis of a Vector Space 벡터 space 를 span 하는 independent 벡터의집합 보통무한개의 basis 존재 의 basis 는 n 개의 n 차원 independent 벡터로구성 Standard basis of = (,,, ), = (,,, ),, = (,,, ), For any v, v 는의 basis 벡터의 unique 한 linear combination 으로표현됨 ( 증명?) A: n by n matrix n 개의컬럼벡터가 independent Ax = b 는 unique 한 solution 가짐, x = n 개의컬럼벡터는의 basis A: n by n matrix 가 invertible 모든 b 에대해 Ax =b 의 unique solution 있음 Ax = 의해는 임 è A의컬럼벡터를다름컬럼벡터의 linear combination 으로표현하지못함 b

43 Example A= , = 2 의컬럼스페이스및로우스페이스를구하고, 컬럼스페 이스및로우스페이스의 basis 를구하시오. 2 3 R= 4 의컬럼스페이스및로우스페이스를구하고, 컬럼스페이스및 로우스페이스의 basis 를구하시오

44 Dimension 벡터스페이스의 dimension = basis 를구성하는 vector 의수 벡터스페이스의 basis 는여러개있음 A= 어느두컬럼벡터도 C(A) 의 basis 가됨 벡터스페이스의 basis 벡터의갯수는같음 Basis 벡터의개수 = Vector space 의 dimension

45 Exercises =, 2,, = 2, 3, A) 두벡터는 linearly independent 한가? B) 두벡터는어느공간의 basis 가되는가? C) 두벡터가 span하는공간 (V) 및공간의 dimension은? D) V를컬럼스페이스로가지는행렬 A 를구하시오 E) V를 null space 로가지는행렬 A 를구하시오 F), 와더불어공간을 span 하는를구하시오

46 Exercises

47 Exercises

48 Four Subspaces Row space: C( ) Column space: C(A) Null space: N(A) Left Null space: N( )

49 Example R= 2 m=3, n=5, r=2 C( ) =? C(A) =? N(A) =? N( ) =?

50 Dimension of Four Spaces

51 Subspaces of A & R A à R after elimination R= EA A= A, R 의로우스페이스는동일 = ( ) A, R 의컬럼스페이스의 dimension 은동일 Dimension of C(A) = Dimension of C(R) C(A) C(R) A, R 의 Null space 는동일 = ( ) A, R 의 left null space 의 dimension 은동일 Dimension of N( ) = Dimension of N( ) C( ) C( )

52 Examples Four subspaces of A=[ 2 3] m=, n= 3 r=? C(A)? C( ) =? N(A) =? N( ) =? Four subspaces of A= m=2, n=3, r=? C(A)? C( ) =? N(A) =? N( ) =?

53 Exercises 다음행렬의 four subspaces 를구하시오. A= = = 위행렬 A 의 entry 중하나만변경해서 four subspace 의 dimension 을모두변경해보시오

54 Seoul National University Determinant Date Name: 김종권

55 Determinant Square 행렬 A 의특성을표현할수있는 scalar 값 기호 det A A = = ad-bc det A = : ad-bc = è (b d) = x(a c) A 는 singular 행렬 : A 는 invertible

56 Determinant det A = product of pivot entries = = = det A =?

57 Determinant 계산방법 n by n 행렬. Pivot formula Multiply n pivots 2. Big formula Sum of n! terms 3. Cofactor formula n 개의 n- by n- 행렬의 determinant 값 sum

58 Ten Properties of Determinant. Determinant of Identity matrices = =, = 2. Row( 또는컬럼 ) 두개의위치를바꾼행렬의 determinant 는원래행렬값과 ± 부호가다름 =, h = h

59 Ten Properties of Determinant 3. Linearity based on single row (or column) + + = + = Examples = 4 2 2, = I 2, = 4, 2 2 =

60 Ten Properties of Determinant 4. 로우 ( 또는컬럼 ) 이같은행렬의 determinant 는 5. 행렬의 row 에서다른 row 의배수배를뺀결과의행렬은원래행렬과같은 determinant 가짐 행렬을 elimination 해도 determinant 는변동없음 = 6. Row( 또는 column) 가 인행렬의 determinant 는 =

61 Ten Properties of Determinant 7. Triangular matrix 의 determinant 는 diagonal entries 의 product = ad, = 8. Singular 행렬의 determinant 는, Invertible 한행렬의 determinant 는 이아님 A is singular çè det A =

62 Ten Properties of Determinant 9. AB = A B = det = / det From AB = A B è A = AB / B. det = det A =

63 Exercises

64 Exercises Determinant 값이 ½ 인 4 by 4 matrix A 가있다. A 를변형한 matrices 의 determinan 를구하시오 det (2A) det (-A) det ( ) det ( )

65 Exercises

66 Pivot Formula Determinant 를구하는방법중하나 Note: Triangular matrix 의 determinann 는 diagonal entry 들의 product 임 det AB = det A det B A=LU factorization 만약 row exchange 를했다면 PA = LU det P * det A = det PA = det LU = det L * det U det P 는 exchange 를몇번했는지에따라 -: 홀수번한경우 : 짝수번한경우 det L = det U = det A = ±( )

67 Pivot Formula - Example A= è PA= det A = - 4*2* =

68 Big Formula = n by n matrix è n! terms For example n=, è ~ terms = + = = + =

69 Big Formula 3 by 3 matrix = 27 개의각로우에서 entry를하나씩고르고나머지두개는 으로만든 matrix determinants 의합 같은컬럼에서 이세개나오는 matrices 의 determinant 는 = =

70 Big Formula - Example Triangular matrix, U 각 row 에서서로다른컬럼에있는 entry 를뽑는방법의수 = n! Diagonal entry 로만구성된 matrix 를제외하고모두 entry 를가지고있음 그런 matrix 의 determinant 는 det U =? =

71 Big Formula - Example det Z = = det = = =

72 Cofactor Formula = ) = ( ) + ( - ) + ( Cofactor Cofactor Cofactor = ( ) det =

73 Cofactor Formula - Example è =2 2 = 2 일반적으로 = ( ) 2 2 =(-) 2 2 det = = ( ) 2 2 è det =

74 Exercises Hessenberg matrix는 extra diagonal 이있는 triangular matrix 이다. 2 = 2 2 2, = 2, = Row 의 cofactor를사용해서 = + 임을증명하시오. Big formula를이용해서다음 matrix의 determinant를구하시오, ,,

75 Exercises Cofactor formula 를사용하여 determinant 를구하시오, Cofactor matrix C 를구하고와를비교하시오 A= 2 2 2, = /

76 Cramer s Rule Solve Ax = b Elimination 을해서 A à R 로변환 Cramer s Rule 3 by 3 matrix A, Ax = b AI = A = A A è deta ( ) = det è = det 첫번째컬럼을 x 로대체 = = / det A 를정하기위해서 j 번째컬럼을 x 로대체 = det / det A

77 Cramer s Rule - Example = = 4 det A = , det = , det = = det / det A = det / det A 2. 구하기 A = 의첫번째컬럼을 (, ) 라고하고두번째컬럼을 (, ) 라고 하자 A =, A = A=,,,,

78 Exercises

OR MS와 응용-03장

OR MS와 응용-03장 o R M s graphical solution algebraic method ellipsoid algorithm Karmarkar 97 George B Dantzig 979 Khachian Karmarkar 98 Karmarkar interior-point algorithm o R 08 gallon 000 000 00 60 g 0g X : : X : : Ms