https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/
이전 강의에서 nullspace에 대해서 배웠다.A x = 0 Ax=0 A x = 0
예시와 함께 살펴보자.
A = [ 1 2 2 2 2 4 6 8 3 6 8 10 ] A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix} A = ⎣ ⎢ ⎡ 1 2 3 2 4 6 2 6 8 2 8 1 0 ⎦ ⎥ ⎤ 위 행렬 A A A
r o w 1 + r o w 2 = r o w 3 row_1 + row_2 = row_3 r o w 1 + r o w 2 = r o w 3 2 c o l 1 = c o l 2 2col_1 = col_2 2 c o l 1 = c o l 2 따라서 r o w 3 row_3 r o w 3 c o l 1 col_1 c o l 1
그럼 계속해서 Elimination을 적용해보자.
[ 1 2 2 2 2 4 6 8 3 6 8 10 ] → [ 1 2 2 2 0 0 2 4 0 0 2 4 ] → [ 1 2 2 2 0 0 2 4 0 0 0 0 ] = U \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} = U ⎣ ⎢ ⎡ 1 2 3 2 4 6 2 6 8 2 8 1 0 ⎦ ⎥ ⎤ → ⎣ ⎢ ⎡ 1 0 0 2 0 0 2 2 2 2 4 4 ⎦ ⎥ ⎤ → ⎣ ⎢ ⎡ 1 0 0 2 0 0 2 2 0 2 4 0 ⎦ ⎥ ⎤ = U 위 행렬은 upper matrix(U U U U U U
위 행렬 U U U U 11 ( = 1 ) U_{11}(=1) U 1 1 ( = 1 ) U 23 ( = 2 ) U_{23}(=2) U 2 3 ( = 2 )
그리고 pivot의 개수를 rank라 부른다. "# of pivots of A = rank of A = 2 \text{\# of pivots of $A$ = rank of $A$ = $2$} # of pivots of A = rank of A = 2
위 행렬 U U U c o l 1 col_1 c o l 1 c o l 3 col_3 c o l 3
그리고 free column(variable)은 c o l 2 col_2 c o l 2 c o l 4 col_4 c o l 4
그렇다면 위에서 구한 U U U U x = 0 Ux=0 U x = 0 x x x
x = [ 1 0 ] x = \begin{bmatrix} \\ 1 \\ \\ 0 \end{bmatrix} x = ⎣ ⎢ ⎢ ⎢ ⎡ 1 0 ⎦ ⎥ ⎥ ⎥ ⎤
우선 free column에 임의의 값을 대입해보자. (편의상 1 , 0 1, 0 1 , 0
그런 다음 U x = 0 Ux=0 U x = 0
x 1 + 2 x 2 + 2 x 3 + 2 x 4 = 0 ( r o w 1 ) x_1+2x_2+2x_3+2x_4=0 \tag{$row_1$} x 1 + 2 x 2 + 2 x 3 + 2 x 4 = 0 ( r o w 1 ) 0 x 1 + 0 x 2 + 2 x 3 + 4 x 4 = 0 ( r o w 2 ) 0x_1+0x_2+2x_3+4x_4=0 \tag{$row_2$} 0 x 1 + 0 x 2 + 2 x 3 + 4 x 4 = 0 ( r o w 2 ) 에서 x 2 = 1 , x 4 = 0 x_2=1, x_4=0 x 2 = 1 , x 4 = 0
x 1 + 2 + 2 x 3 = 0 ( r o w 1 ) x_1+2+2x_3=0 \tag{$row_1$} x 1 + 2 + 2 x 3 = 0 ( r o w 1 ) 2 x 3 = 0 ( r o w 2 ) 2x_3=0 \tag{$row_2$} 2 x 3 = 0 ( r o w 2 ) 따라서 U x = 0 Ux=0 U x = 0 x x x
x = [ − 2 1 0 0 ] x = \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} x = ⎣ ⎢ ⎢ ⎢ ⎡ − 2 1 0 0 ⎦ ⎥ ⎥ ⎥ ⎤ 이를 아까 원래 행렬 A A A
A = [ 1 2 2 2 2 4 6 8 3 6 8 10 ] , x = [ − 2 1 0 0 ] A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix}, x = \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} A = ⎣ ⎢ ⎡ 1 2 3 2 4 6 2 6 8 2 8 1 0 ⎦ ⎥ ⎤ , x = ⎣ ⎢ ⎢ ⎢ ⎡ − 2 1 0 0 ⎦ ⎥ ⎥ ⎥ ⎤ 다음과 같은 특징을 알 수 있다.
행렬 A A A − 2 c o l 1 + c o l 2 + 0 c o l 3 + 0 c o l 4 = 0 -2col_1+col_2+0col_3+0col_4=0 − 2 c o l 1 + c o l 2 + 0 c o l 3 + 0 c o l 4 = 0
그리고 x x x x = c [ − 2 1 0 0 ] x = c \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} x = c ⎣ ⎢ ⎢ ⎢ ⎡ − 2 1 0 0 ⎦ ⎥ ⎥ ⎥ ⎤
그러면 혹시 모르니 또 다른 x x x x x x
x = [ 0 1 ] x = \begin{bmatrix} \\ 0 \\ \\ 1 \end{bmatrix} x = ⎣ ⎢ ⎢ ⎢ ⎡ 0 1 ⎦ ⎥ ⎥ ⎥ ⎤ 그러면 위와 같은 과정들을 거쳐서 x x x
x = [ 2 0 − 2 1 ] x = \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} x = ⎣ ⎢ ⎢ ⎢ ⎡ 2 0 − 2 1 ⎦ ⎥ ⎥ ⎥ ⎤ 마찬가지로 행렬 A A A
A = [ 1 2 2 2 2 4 6 8 3 6 8 10 ] , x = [ 2 0 − 2 1 ] A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix}, x = \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} A = ⎣ ⎢ ⎡ 1 2 3 2 4 6 2 6 8 2 8 1 0 ⎦ ⎥ ⎤ , x = ⎣ ⎢ ⎢ ⎢ ⎡ 2 0 − 2 1 ⎦ ⎥ ⎥ ⎥ ⎤ 위와 마찬가지로 다음과 같은 특징을 얻는다.
행렬 A A A 2 c o l 1 + 0 c o l 2 + − 2 c o l 3 + c o l 4 = 0 2col_1+0col_2+-2col_3+col_4=0 2 c o l 1 + 0 c o l 2 + − 2 c o l 3 + c o l 4 = 0
그리고 x x x x = d [ 2 0 − 2 1 ] x = d \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} x = d ⎣ ⎢ ⎢ ⎢ ⎡ 2 0 − 2 1 ⎦ ⎥ ⎥ ⎥ ⎤
그리고 이전 강의에서 배운 c v = 0 , d w = 0 cv=0, dw=0 c v = 0 , d w = 0 v , w v,w v , w c v + d w = 0 cv+dw=0 c v + d w = 0 x x x
x = c [ − 2 1 0 0 ] + d [ 2 0 − 2 1 ] x = c \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + d \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} x = c ⎣ ⎢ ⎢ ⎢ ⎡ − 2 1 0 0 ⎦ ⎥ ⎥ ⎥ ⎤ + d ⎣ ⎢ ⎢ ⎢ ⎡ 2 0 − 2 1 ⎦ ⎥ ⎥ ⎥ ⎤ 그러면 U x = 0 Ux=0 U x = 0 R x = 0 Rx=0 R x = 0 R R R
U = [ 1 2 2 2 0 0 2 4 0 0 0 0 ] U = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} U = ⎣ ⎢ ⎡ 1 0 0 2 0 0 2 2 0 2 4 0 ⎦ ⎥ ⎤ 아까 위에서 행렬 U U U U 23 U_{23} U 2 3
[ 1 2 2 2 0 0 2 4 0 0 0 0 ] → [ 1 2 0 − 2 0 0 2 4 0 0 0 0 ] \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} ⎣ ⎢ ⎡ 1 0 0 2 0 0 2 2 0 2 4 0 ⎦ ⎥ ⎤ → ⎣ ⎢ ⎡ 1 0 0 2 0 0 0 2 0 − 2 4 0 ⎦ ⎥ ⎤ 그리고 pivot의 값이 1이 되도록 해보자.
[ 1 2 0 − 2 0 0 2 4 0 0 0 0 ] → [ 1 2 0 − 2 0 0 1 2 0 0 0 0 ] \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} ⎣ ⎢ ⎡ 1 0 0 2 0 0 0 2 0 − 2 4 0 ⎦ ⎥ ⎤ → ⎣ ⎢ ⎡ 1 0 0 2 0 0 0 1 0 − 2 2 0 ⎦ ⎥ ⎤
그러면 이제 최종 목적인 R R R r r e f ( A ) rref(A) r r e f ( A ) A A A
우선 위 행렬에서 칼럼들을 나눠보자.
pivot columns : c o l 1 col_1 c o l 1 c o l 3 col_3 c o l 3
free columns: c o l 2 col_2 c o l 2 c o l 4 col_4 c o l 4
pivot cloumns와 free columns를 각각 따로 묶어보자.
p i v o t c o l u m n s = [ 1 0 0 1 ] = I pivot \ columns = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} =I p i v o t c o l u m n s = [ 1 0 0 1 ] = I f r e e c o l u m n s = [ 2 − 2 0 2 ] = F free \ columns = \begin{bmatrix} 2 & -2 \\ 0 & 2 \end{bmatrix} =F f r e e c o l u m n s = [ 2 0 − 2 2 ] = F
F F F U x = 0 Ux=0 U x = 0 x x x
F = [ 2 − 2 0 2 ] , x = c [ − 2 1 0 0 ] + d [ 2 0 − 2 1 ] F = \begin{bmatrix} 2 & -2 \\ 0 & 2 \end{bmatrix} , x = c \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + d \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} F = [ 2 0 − 2 2 ] , x = c ⎣ ⎢ ⎢ ⎢ ⎡ − 2 1 0 0 ⎦ ⎥ ⎥ ⎥ ⎤ + d ⎣ ⎢ ⎢ ⎢ ⎡ 2 0 − 2 1 ⎦ ⎥ ⎥ ⎥ ⎤
뭔가 유사한 점이 보이는 것 같다.
아까 pivot columns에 속했던 c o l 1 col_1 c o l 1 c o l 3 col_3 c o l 3 F F F
그리고 free columns는 I I I
[ − 2 − 0 − ] , [ 2 − − 2 − ] ≈ − [ 2 − 2 0 2 ] = − F \begin{bmatrix}-2 \\ - \\ 0 \\ -\end{bmatrix},\begin{bmatrix}2 \\ - \\ -2 \\ -\end{bmatrix} \approx -\begin{bmatrix} 2 & -2 \\ 0 & 2 \end{bmatrix}=-F ⎣ ⎢ ⎢ ⎢ ⎡ − 2 − 0 − ⎦ ⎥ ⎥ ⎥ ⎤ , ⎣ ⎢ ⎢ ⎢ ⎡ 2 − − 2 − ⎦ ⎥ ⎥ ⎥ ⎤ ≈ − [ 2 0 − 2 2 ] = − F
[ − 1 − 0 ] , [ − 0 − 1 ] ≈ [ 1 0 0 1 ] = I \begin{bmatrix}- \\ 1 \\ - \\ 0\end{bmatrix},\begin{bmatrix}- \\ 0 \\ - \\ 1\end{bmatrix} \approx \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}=I ⎣ ⎢ ⎢ ⎢ ⎡ − 1 − 0 ⎦ ⎥ ⎥ ⎥ ⎤ , ⎣ ⎢ ⎢ ⎢ ⎡ − 0 − 1 ⎦ ⎥ ⎥ ⎥ ⎤ ≈ [ 1 0 0 1 ] = I
그리고 R R R
R = [ I F 0 0 ] R= \begin{bmatrix} I & F \\0 & 0 \end{bmatrix} R = [ I 0 F 0 ]
r o w 1 row_1 r o w 1 r r r c o l 1 col_1 c o l 1 r r r c o l 2 col_2 c o l 2 n − r n-r n − r
그리고 이제 R x = 0 Rx=0 R x = 0 N N N
R N = [ I F 0 0 ] ⏟ R N = 0 RN= \underbrace{ \begin{bmatrix} I & F \\0 & 0\end{bmatrix} }_R N = 0 R N = R [ I 0 F 0 ] N = 0 N = [ − F I ] N= \begin{bmatrix} -F \\ I \end{bmatrix} N = [ − F I ] 여기서 N N N F F F I I I
따라서,
R x = [ I F ] [ x p i v o t x f r e e ] = 0 Rx= \begin{bmatrix} I & F \end{bmatrix} \begin{bmatrix} x_{pivot} \\ x_{free} \end{bmatrix} = 0 R x = [ I F ] [ x p i v o t x f r e e ] = 0 x p i v o t + F x f r e e = 0 x_{pivot} + Fx_{free} = 0 x p i v o t + F x f r e e = 0 이라는 수식을 구할 수 있다.
그런데 왜 N = [ − F I ] N= \begin{bmatrix} -F \\ I \end{bmatrix} N = [ − F I ] [ x p i v o t x f r e e ] \begin{bmatrix} x_{pivot} \\ x_{free} \end{bmatrix} [ x p i v o t x f r e e ] F F F I I I p i v o t = k × f r e e pivot = k\times free p i v o t = k × f r e e R x = 0 Rx=0 R x = 0 R = [ I F ] R=\begin{bmatrix} I & F \end{bmatrix} R = [ I F ] x = [ x p i v o t x f r e e ] x=\begin{bmatrix} x_{pivot} \\ x_{free} \end{bmatrix} x = [ x p i v o t x f r e e ] x p i v o t = − F x f r e e x_{pivot}=-Fx_{free} x p i v o t = − F x f r e e N N N x = [ x p i v o t x f r e e ] = [ − F x f r e e x f r e e ] = [ − F I ] ⏟ N x f r e e x=\begin{bmatrix} x_{pivot} \\ x_{free} \end{bmatrix}=\begin{bmatrix} -Fx_{free} \\ x_{free} \end{bmatrix}=\underbrace{\begin{bmatrix} -F \\ I \end{bmatrix}}_{N}x_{free} x = [ x p i v o t x f r e e ] = [ − F x f r e e x f r e e ] = N [ − F I ] x f r e e
이제 예시와 함께 정리해보자.
A = [ 1 2 3 2 4 6 2 6 8 2 8 10 ] A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 2 & 6 & 8 \\ 2 & 8 & 10 \end{bmatrix} A = ⎣ ⎢ ⎢ ⎢ ⎡ 1 2 2 2 2 4 6 8 3 6 8 1 0 ⎦ ⎥ ⎥ ⎥ ⎤
위 행렬에서 c o l 1 col_1 c o l 1 c o l 2 col_2 c o l 2
반면에 c o l 3 col_3 c o l 3 c o l 1 + c o l 2 col_1+col_2 c o l 1 + c o l 2
따라서 c o l 1 col_1 c o l 1 c o l 2 col_2 c o l 2 c o l 3 col_3 c o l 3
계속해서 연산을 수행해보자.
A = [ 1 2 3 2 4 6 2 6 8 2 8 10 ] → [ 1 2 3 0 0 0 0 2 2 0 4 4 ] → [ 1 2 3 0 2 2 0 0 0 0 4 4 ] → [ 1 0 1 0 1 1 0 0 0 0 0 0 ] = R A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 2 & 6 & 8 \\ 2 & 8 & 10 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 2 & 2 \\ 0 & 4 & 4 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 3 \\ 0 & 2 & 2 \\ 0 & 0 & 0 \\ 0 & 4 & 4 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} = R A = ⎣ ⎢ ⎢ ⎢ ⎡ 1 2 2 2 2 4 6 8 3 6 8 1 0 ⎦ ⎥ ⎥ ⎥ ⎤ → ⎣ ⎢ ⎢ ⎢ ⎡ 1 0 0 0 2 0 2 4 3 0 2 4 ⎦ ⎥ ⎥ ⎥ ⎤ → ⎣ ⎢ ⎢ ⎢ ⎡ 1 0 0 0 2 2 0 4 3 2 0 4 ⎦ ⎥ ⎥ ⎥ ⎤ → ⎣ ⎢ ⎢ ⎢ ⎡ 1 0 0 0 0 1 0 0 1 1 0 0 ⎦ ⎥ ⎥ ⎥ ⎤ = R 따라서 R x = 0 Rx=0 R x = 0
x = c [ − F I ] = c [ − 1 − 1 1 ] x= c\begin{bmatrix} -F \\ I \end{bmatrix} = c\begin{bmatrix} -1 \\ -1 \\ 1 \end{bmatrix} x = c [ − F I ] = c ⎣ ⎢ ⎡ − 1 − 1 1 ⎦ ⎥ ⎤ N = [ − F I ] = [ − 1 − 1 1 ] N = \begin{bmatrix} -F \\ I \end{bmatrix} = \begin{bmatrix} -1 \\ -1 \\ 1 \end{bmatrix} N = [ − F I ] = ⎣ ⎢ ⎡ − 1 − 1 1 ⎦ ⎥ ⎤ 을 알 수 있다.
예시로 free variable x 3 x_3 x 3
x 1 + x 3 = 0 x_1 + x_3 = 0 x 1 + x 3 = 0 x 2 + x 3 = 0 x_2 + x_3 = 0 x 2 + x 3 = 0 에서,
이 되어, x = [ − 1 − 1 1 ] x=\begin{bmatrix} -1 \\ -1 \\ 1 \end{bmatrix} x = ⎣ ⎢ ⎡ − 1 − 1 1 ⎦ ⎥ ⎤
