Lecture 2: Elimination with matrices

 

소거법 (Elimination) 성공사례

 

$x + 2y + z = 2$ 

$3x + 8y + z = 12$ 

$4y + z = 2$

 

$A\textbf{x} = \textbf{b}$ 

 

Elimination 성공인 경우

 

$\begin{bmatrix}
1 & 2 & 1\\ 
3 & 8 & 1\\ 
0 & 4 & 1
\end{bmatrix} \rightarrow^{2,1} \begin{bmatrix}
1 & 2 & 1\\ 
0 & 2 & -2\\ 
0 & 4 & 1
\end{bmatrix} \rightarrow^{3,2} \begin{bmatrix}
1 & 2 & 1\\ 
0 & 2 & -2\\ 
0 & 0 & 5
\end{bmatrix}$

 

첫 번째 소거는 두 번째 식에서 첫 번째 식에 3을 곱한다음 빼주었습니다.

 

3을 곱해준 이유는 x항을 없애주기 위해서입니다. 

 

세 번째 식에서도 x항을 없애주기 위해 그 다음 소거를 진행해야하지만 이미 0이기 때문에 넘어갑니다. 

 

다음으로 y항과 z항에 대해 고려해야합니다.

 

pivot을 (2,2)로 잡지 않고 (1,2)로 잡는다면 앞서 없앤 x항이 다시 살아납니다. 

 

행렬의 (1,1), (2,2), (3,3) 성분은 pivot입니다. 

 

최종적으로 1은 1st pivot, 2는 2nd pivot, 5는 3th pivot이 됩니다.

 

pivot이 모두 0이 아니므로 소거는 성공입니다.

 

또한 소거가 완료된 마지막 행렬은 (U)pper triangle이라 불립니다. pivot을 기준으로 아래 원소값이 모두 0입니다. 

 

위의 Elimination은 A to U의 과정입니다. 

 

 

소거법 (Elimination) Failure?

 

$\begin{bmatrix}
1 & 2 & 1\\ 
3 & 6 & 1\\ 
0 & 4 & 1
\end{bmatrix}$

 

pivot이 0인 경우에 소거법 적용이 불가합니다. 

 

그러나 위 행렬의 경우 2nd pivot이 0이 되어서 Failure일 수도 있지만

 

행 바꿈 (row change)를 통해 계속 진행해야합니다 (가능성 존재).

 

즉, 세 번째 행의 y가 0이 아니기 때문에 행 바꿈을 해주어 소거를 가능하게 합니다. 

 

 

소거법 (Elimination) Failure

 

$x + 2y + z = 2$ 

$3x + 8y + z = 12$ 

$4y - 4z = 2$

 

방정식을 계수 행렬로 나타내고 소거법을 진행합니다. 

 

$\begin{bmatrix} 
1 & 2 & 1\\  
3 & 8 & 1\\  
0 & 4 & -4 
\end{bmatrix} \rightarrow^{2,1} \begin{bmatrix} 
1 & 2 & 1\\  
0 & 2 & -2\\  
0 & 4 & -4 
\end{bmatrix} \rightarrow^{3,2} \begin{bmatrix} 
1 & 2 & 1\\  
0 & 2 & -2\\  
0 & 0 & 0 
\end{bmatrix}$ 

 

3th pivot이 없게됩니다 (Failure).

 

바꿀 행도 있지 않기 때문에 더이상 소거를 할 방법이 없습니다. 

 

 

소거법 (Elimination) Success 경우 해 구하기

 

다시 Success 경우로 돌아옵니다. 

 

후방대입법 (Back-substitution) 개념을 도입합니다.

 

앞서 사례에서는 계수 행렬만을 이용해 소거법을 적용했습니다. $A\mathbf{x} = \mathbf{b}$에서 $A$만을 이용했습니다.

 

후방대입법에서는 $A$와 함께 $\mathbf{b}$도 같이 수행합니다. 

 

이번엔 $\textbf{b}$도 같이 해주겠습니다.

 

$\begin{bmatrix} 
1 & 2 & 1 & | & 2\\  
3 & 8 & 1 & | & 12\\  
0 & 4 & 1 & | & 2
\end{bmatrix} \rightarrow^{2,1} \begin{bmatrix} 
1 & 2 & 1  & | & 2\\  
0 & 2 & -2 & | & 6\\  
0 & 4 & 1  & | & 2
\end{bmatrix} \rightarrow^{3,2} \begin{bmatrix} 
1 & 2 & 1  & | & 2\\  
0 & 2 & -2 & | & 6\\  
0 & 0 & 5  & | & -10
\end{bmatrix}$

 

이와 같은 행렬을 첨가 행렬 (Augmented matrix)라고 부릅니다.  

 

$A$와 $\mathbf{b}$에 똑같이 동시에 소거법을 적용합니다. 

 

A는 U로 $\textbf{b}$는 $\textbf{c}$로바뀌었습니다.

 

방정식으로 쓰면 아래와 같습니다. 

 

$x + 2y + z = 2$ 

$2y + -2z = 6$ 

$5z = -10$ 

 

후방대입법의 말 그대로 아래 방정식부터 해를 풀어나갑니다. 

$x = 2$ 

$y = 1$ 

$z = -2$입니다. 

 

 

Column Operation

 

$\begin{bmatrix}
- & - & -\\ 
- & - & -\\ 
- & - & -
\end{bmatrix} \begin{bmatrix}
3\\ 4
\\5 
\end{bmatrix}$ 

 

위의 계산 결과는 다음과 같습니다. 

 

3 X col1 + 4 X col2 + 5 X col3 

 

matrix X col = col 

 

중요한 사실입니다.

 

 

Row Operation

 

$\begin{bmatrix}
1 & 2 & 7
\end{bmatrix}\begin{bmatrix}
- & - & -\\ 
- & - & -\\ 
- & - & -
\end{bmatrix} $

 

1 X row1 + 2 X row2 + 7 X row3

 

row X matirx = row

 

row operation입니다. 

 

 

Matrices Row Operation & 소거 행렬 (Elimination on Matrix)

 

전의 Elimination의 과정을 상기해봅니다,

 

row2 - 3 X row1을 처음에 해줬습니다.

 

Row operation입니다!

 

$\begin{bmatrix} 
1 & 0 & 0\\  
-3 & 1 & 0\\  
0 & 0 & 1 
\end{bmatrix}\begin{bmatrix} 
1 & 2 & 1\\  
3 & 8 & 1\\  
0 & 4 & 1 
\end{bmatrix} = \begin{bmatrix} 
1 & 2 & 1\\  
0 & 2 & -2\\  
0 & 4 & 1 
\end{bmatrix}$

 

따라서 행렬 왼쪽에서 다른 어떤 행렬을 곱해주었고 2번째 행만 바뀌었습니다.

 

row2 - 3 X row1을 그대로 2번째 행에 반영합니다.

 

$\begin{bmatrix} 
1 & 0 & 0\\  
-3 & 1 & 0\\  
0 & 0 & 1 
\end{bmatrix}$ 

 

위와 같은 소거 행렬을 $E_{21}$라고 합니다. 

 

행렬의 2행 1열을 0으로 만드는 것을 목표로 하기 때문에 $E_{21}$이라 부릅니다. 

 

소거 행렬을 생각할 때는 row operation을 떠올려야합니다. 

 

한 번더 해주겠습니다.

 

row3 - 2 X row2는

 

$\begin{bmatrix}  
1 & 0 & 0\\   
0 & 1 & 0\\   
0 & -2 & 1  
\end{bmatrix}\begin{bmatrix}  
1 & 2 & 1\\   
0 & 2 & -2\\   
0 & 4 & 1  
\end{bmatrix} = \begin{bmatrix}  
1 & 2 & 1\\   
0 & 2 & -2\\   
0 & 0 & 5  
\end{bmatrix}$이고

 

$\begin{bmatrix}   
1 & 0 & 0\\    
0 & 1 & 0\\    
0 & -2 & 1   
\end{bmatrix}$은 $E_{32}$입니다. 

 

 

$E_{32}E_{21}A = U$

 

$E_{32}(E_{21}A) = U$ 

$(E_{32}E_{21})A = U$

 

위의 두 식은 같은 표현입니다 (결합법칙 성립). 간단하게 $(E_{32}E_{21})$을 $E$라고 표현할 수 있습니다. 

 

A to Upper triangle matrix 임을 기억합니다.

 

 

Permutation Exchange Row1 and Row2

 

치환 행렬(permutation matrix)에 대해 설명드리겠습니다.

 

치환 행렬은 행렬의 행이나 열을 바꾸는 역할을 합니다. 

 

$\begin{bmatrix}
a & b\\ 
c & d
\end{bmatrix} -> \begin{bmatrix}
c & d\\ 
a & b
\end{bmatrix}$

 

어떤 행렬을 어디에 곱해 row1과 row2를 바꿀 수 있을까요?

 

중요한 것은 row operation이란 점입니다.

 

때문에 행렬 A의 왼쪽에서 곱해지는 것을 떠올리셔야 하고

 

row operation을 떠올리면

 

$\begin{bmatrix} 
0 & 1\\  
1 & 0 
\end{bmatrix}
\begin{bmatrix} 
a & b\\  
c & d 
\end{bmatrix} = \begin{bmatrix} 
c & d\\  
a & b 
\end{bmatrix}$

 

$\begin{bmatrix}  
0 & 1\\   
1 & 0  
\end{bmatrix}$는 permutation의 맨 앞글자인 P를 따옵니다. 

 

 

Permutation Exchange col1 and col2

 

$\begin{bmatrix} 
a & b\\  
c & d 
\end{bmatrix} -> \begin{bmatrix} 
b & a\\  
d & c 
\end{bmatrix}$

 

위의 경우는 어떤 operation인가요?

 

col1과 col2를 바꿔준 것을 볼 수 있습니다.

 

column operation이고 

 

따라서 행렬 A 오른쪽에 곱하게 될 것입니다.

 

column operation을 떠올리면 아래와 같습니다. 

 

$\begin{bmatrix}  
a & b\\   
c & d  
\end{bmatrix} \begin{bmatrix}  
0 & 1\\   
1 & 0  
\end{bmatrix} = \begin{bmatrix}  
b & a\\   
d & c  
\end{bmatrix}$

 

 

Inverses

 

역행렬을 간단히 살펴보겠습니다. 

 

$\begin{bmatrix}
1 & 0 & 0\\ 
-3 &  1& 0\\ 
0 & 0 & 1
\end{bmatrix} -> \begin{bmatrix}
1 & 0 & 0\\ 
0 &  1& 0\\ 
0 & 0 & 1
\end{bmatrix}$

 

E to I를 하려고 합니다.

 

위에서 익힌 Elimination을 떠올리고 row operation을 진행해 주면

 

$\begin{bmatrix}
1 & 0 & 0\\ 
3 &  1& 0\\ 
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0\\ 
-3 &  1& 0\\ 
0 & 0 & 1
\end{bmatrix} = \begin{bmatrix}
1 & 0 & 0\\ 
0 &  1& 0\\ 
0 & 0 & 1
\end{bmatrix} $이고

 

$\begin{bmatrix}
1 & 0 & 0\\ 
3 &  1& 0\\ 
0 & 0 & 1
\end{bmatrix}$은 $E^{-1}$임을 금세 알 수 있습니다.