Triangle Factors and Row exchanges

아래와 같은 연립 방적식인 $Ax=b$가 있다고 하자.

$$Ax = \begin{bmatrix}
2 & 1 & 1\\ 
4 & -6 & 0\\ 
-2 & 7 & 2
\end{bmatrix} \begin{bmatrix}
u\\ 
v\\ 
w
\end{bmatrix} = \begin{bmatrix}
5\\ 
-2\\ 
9
\end{bmatrix}=b$$

이 행렬에서는 3번의 소거 단계가 있다.

1. 1st equation의 2배를 2nd equation에서 뺀다.

2. 2nd equation의 -1배를 3rd equation에서 뺀다.

3. 1st equation의 -1배를 3rd equation에서 뺀다.

위의 단계를 수행하게 되면 if and only if인 연립 방정식 $Ux=c$가 나오는데, $U$는 coefficient matrix이다.

$$upper \ triangular \ \ \ \ \ Ux = \begin{bmatrix}
2 & 1 & 1\\ 
0 & -8 & 2\\ 
0 &  0& 1
\end{bmatrix}\begin{bmatrix}
u\\ 
v\\ 
w
\end{bmatrix}=\begin{bmatrix}
5\\ 
-12\\ 
2
\end{bmatrix}=c$$

이 이후의 소거는 아래의 3가지 행 연산과 같다.

1. $A$와 $b$에서 출발한다.

2. 위의 단계 1, 2, 3을 순서대로 적용한다.

3. $U$와 $c$로 끝난다.

 

소거 단계의 1을 위한 행렬을 $E$, 2를 위한 행렬 $F$, 3을 위한 행렬 $G$라고 사용한다. (elementary matrix라고 한다.)

만약 $j$째 방정식의 $l$배를 $i$째 방정식에서 빼려면, $(i, j)$ 성분에 $-l$을 넣으면 된다.

소거의 3가지 단계의 결과는 $GFEA=U$이다. $A$에 $E$를 처음으로 곱하고 다음에 $F$, 마지막에 $G$를 곱한다. $GFE$는 아래와 같이 lower triangular matrix이다.

$$From \ A \ to \ U \ \ \ \ GFE=\begin{bmatrix}
1 &  & \\ 
 & 1 & \\ 
 &  1& 1
\end{bmatrix}\begin{bmatrix}
1 &  & \\ 
 & 1 & \\ 
1 &  &1 
\end{bmatrix}\begin{bmatrix}
1 &  & \\ 
-2 & 1 & \\ 
 &  & 1
\end{bmatrix}=\begin{bmatrix}
1 &  & \\ 
-2 & 1 & \\ 
-1 & 1 & 1
\end{bmatrix}$$

 

그렇다면 어떻게 하면 $U$로부터 $A$를 얻을 수 있을까?

단계 1을 되돌리는 방법은, 빼지 않고, 첫째 행의 2배를 둘째 행에 더하면 된다. 그 과정을 모두 시행하면 아래와 같이 identity matrix로 되돌리는 결과를 얻는다.

$$Inverse \ of \ subtraction \ is \ addition \ \ \ \ \begin{bmatrix}
1 & 0 & 0\\ 
2 & 1 & 0\\ 
0 & 0 & 1
\end{bmatrix}\begin{bmatrix}
1 & 0 & 0\\ 
-2 & 1 & 0\\ 
0 & 0 & 1
\end{bmatrix}=\begin{bmatrix}
1 & 0 & 0\\ 
0 & 1 & 0\\ 
0 & 0 & 1
\end{bmatrix}$$