선형대수학 기본 용어 -상급자편 3-

1. gaussian elimination

 

<3가지 elementary row operation>

 

1) 주어진 행렬의 $i$번째 행과 $j$번째 행을 뒤바꾼다.

 

2) 주어진 행렬의 $i$번째 행에 0이 아닌 scalar를 곱한다.

 

3) $i$번째 행의 scalar배를 다른 $j$번째 행에 더한다. 이 때 $i$번째 행은 그대로 되고 $j$번째 행만 변하는 것이다.

 

위의 3가지 elementary row operation은 행이 아니라 column에서도 가능하다

 

elementary row operation으로 주어진 행렬을 변환시켜도 행렬의 rank는 변하지 않는다.

 

<row echelon form>

 

elementary row operation의 결과로 주어진 행렬을 변환시켰을 때 얻을 수 있는 행렬로 다음과 같은 조건을 모두 만족시킨 형태를 말한다.

 

1) 모든 원소가 0인 행은 밑에 있다.

 

2) 모든 원소가 0이 아닌 행의 가장 첫 번째 원소(leading coefficient)는 그 행보다 위에 있는 행의 가장 첫 번째 원소보다 오른쪽에 위치한다.

 

2)가 무슨 말이냐면 삼각행렬(triangular matrix)의 형태를 나타내야한다는 말입니다.

 

그림1. row echelon form의 예시

 

수학적으로 의미를 가지는 이유는 row echelon form으로 주어진 행렬을 변환시키면 0이 아닌 행의 수가 주어진 행렬의 rank와 동일합니다.

 

예를 들어서 행렬 $A=\begin{pmatrix}
1 & 2 & 1\\ 
-2 & -3 & 1\\ 
3 & 5 & 0
\end{pmatrix}$으로 주어졌다고 합시다. 1행에 2배를 2행에 더하여 2행의 첫 번째 원소를 0으로 만듭니다.

 

$$\begin{pmatrix}
1 & 2 & 1\\ 
0 & 1 & 3\\ 
3 & 5 & 0
\end{pmatrix}$$

 

다시 1행의 -3배를 3행에 더하여 3행의 첫 번째 원소를 0으로 만듭니다.

 

$$\begin{pmatrix}
1 & 2 & 1\\ 
0 & 1 & 3\\ 
0 & -1 & -3
\end{pmatrix}$$

 

여기에 2행과 3행을 더하면 $$\begin{pmatrix}
1 & 2 & 1\\ 
0 & 1 & 3\\ 
0 & 0 & 0
\end{pmatrix}$$이므로 행렬 $A=\begin{pmatrix}
1 & 2 & 1\\ 
-2 & -3 & 1\\ 
3 & 5 & 0
\end{pmatrix}$의 row echelon form은 $\begin{pmatrix}
1 & 2 & 1\\ 
0 & 1 & 3\\ 
0 & 0 & 0
\end{pmatrix}$이고 0이 아닌 행이 2개 있으므로 A의 rank가 2가 됩니다.

 

 

<reduced row echelon form>

 

elementary row operation의 결과로 주어진 행렬을 변환시켰을 때 다음과 같은 조건을 모두 만족시키는 형태를 reduced row echelon form이라고 부른다.

 

1) row echelon form의 형태를 만족함

 

하나는 모든 원소가 0인 행은 전부 아래에 존재하고

 

두 번째로 연속된 0이 아닌 행의 leading coefficient는 아래행은 바로 윗행보다 오른쪽에 위치해야함

 

2) 0이 아닌 행의 가장 첫 번째 원소인 leading coefficient는 1이어야함

 

3) leading coefficient가 1인 부분의 column은 나머지 모든 원소가 0이어야함.

 

그림2. reduced row echelon form의 예시

 

row echelon form은 주어진 행렬 A에 대해 여러 가지가 존재할 수 있지만 reduced row echelon form은 유일하게 존재합니다.

 

존재하는 개수의 차이에도 불구하고 row echelon form과 reduced row echelon form은 0인 행의 수가 동일하며 leading coefficient의 위치가 동일합니다.

 

따라서 주어진 행렬에 대한 elementary row operation을 이용하여 row echelon form이나 reduced row echelon form으로 변환시키면 주어진 행렬의 rank를 구할 수 있습니다.

 

위에서 구한 행렬 $A=\begin{pmatrix}
1 & 2 & 1\\ 
-2 & -3 & 1\\ 
3 & 5 & 0
\end{pmatrix}$의 row echelon form은 $\begin{pmatrix}
1 & 2 & 1\\ 
0 & 1 & 3\\ 
0 & 0 & 0
\end{pmatrix}$이었는데 reduced row echelon form의 조건에 맞게 leading coefficient column의 1이 아닌 원소를 0으로 만들어봅시다.

 

2행의 -2배를 1행에 더하면 $$\begin{pmatrix}
1 & 0 & -5\\ 
0 & 1 & 3\\ 
0 & 0 & 0
\end{pmatrix}$$이므로 reduced row echelon form의 모든 조건을 만족시켜서 $A=\begin{pmatrix}
1 & 2 & 1\\ 
-2 & -3 & 1\\ 
3 & 5 & 0
\end{pmatrix}$의 유일한 reduced row echelon form은 $\begin{pmatrix}
1 & 0 & -5\\ 
0 & 1 & 3\\ 
0 & 0 & 0
\end{pmatrix}$이 됩니다.