선형 연립일차방정식 3) 소거행렬과 치환행렬(Elimination matrix and Permutation matrix)

이제부터 연립일차방정식을 해체할 본격적인 도구를 소개하려고 합니다. 결국 연립일차방정식의 목표는 해를 구하는 것이고, 그 방법은 행렬을 사용할 때는 궁극적으로 '기본행/열연산(Elimentary Row/column operation)'이라 불리는 연산을 유한번 적용하여 보다 행렬의 특성을 판단하기 쉬운 꼴로 바꾸는 것에 있습니다. 그 꼴이란 '행사다리꼴(row-echelon form)' 또는 '기약행사다리꼴(reduced row-echelon form)'입니다. 기본행연산에 대해서는 바로 다음 시간에 포스팅 할 것인데, 3가지 연산 종류가 존재합니다. 이 중 핵심 과정이 미지수를 '소거'하는 것으로, pivot 을 구할때나 중학교때 배웠던 연립일차방정식을 소거법으로 푸는 과정에 해당합니다.

​

여태까지 공부한 바에 의하면, 소거란 한 방정식에 특정 수를 곱한 뒤 다른 방정식이랑 더하거나 빼서 한 미지수를 제거하는 것입니다. 이게 우리에게 익숙했던 방법입니다. 하지만 행렬 이론에 따르면, 이러한 소거는 '연산(operation)'의 일종이고, 이 연산은 행렬 곱셈 동치입니다. 다시말해, 소거하는 연산 과정은 단순히 어떤 행렬을 곱하는 것으로 대체할 수 있습니다! 이 엄청난 논리적 결과가 행렬이론 발달의 지평을 거대하게 늘려놓았습니다.

​

연산이 먼저냐, 행렬 곱이 먼저냐 하는 것은 닭이 먼저인지 계란이 먼저인지의 역설과 유사한 점이 많습니다. 그 때만에 소거에 대응되는 행렬인 소거행렬을 먼저 소개할 지, 소거에 대응되는 연산을 먼저 소개할지 고민을 거듭했는데, 기본행연산에 대한 전개를 하다보면 중간에 샐 길이 없이 바쁠 것 같으니 행렬을 먼저 보고 갑시다.

---

1. 소거행렬(Elimination matrix)

 

소거법은 연립일차방정식 2탄 내용에서 소개했고, 이는 승수(multiplier)을 찾아 pivot을 구하는 과정에 해당합니다. 다음 3개의 방정식을 봅시다.

 

$$ \left\{\begin{matrix}
x+2y+3z=9\\ 
2x-y+z=8\\ 
3x+0y-z=3
\end{matrix}\right.\;\;\Leftrightarrow \;\;A\mathbf{x}=\mathbf{b}\;\;\Leftrightarrow \;\;
\begin{pmatrix}
1 & 2 &3 \\ 
2 & -1 &1 \\ 
3 & 0 & -1
\end{pmatrix}\begin{pmatrix}
x\\ 
y\\ 
z
\end{pmatrix}=\begin{pmatrix}
9\\ 
8\\ 
3
\end{pmatrix} $$

 

첫번째 pivot 은 1이고, 두번째 pivot 을 구하기 위해 소거를 한 단계 진행해봅시다. 1행 $\times -(2/1)=-2$ 을 하고 2행과 더한 값을 새로운 2행으로 대체합니다.

 

$$ \begin{pmatrix}
1 & 2 &3 \\ 
0 & -5 &-5 \\ 
3 & 0 & -1
\end{pmatrix}\begin{pmatrix}
x\\ 
y\\ 
z
\end{pmatrix}=\begin{pmatrix}
9\\ 
-10\\ 
3
\end{pmatrix}\;\;\Leftrightarrow \;\;A\mathbf{x}=\mathbf{b} $$

 

그런데, 놀랍게도 이 소거 과정은 다음과 같은 '소거행렬(Elimination matrix)'을 양변의 왼쪽에 곱해주는 것으로 처리하는 것이 가능합니다.

 

소거를 위해 어떤 행렬의 $i$행에서 ($j$행x승수)를 빼는 연산을 하는 경우, 대신에 항등행렬의 $i$행 $j$열 성분에 (-승수)를 추가시킨 것이라 정의되는 '소거행렬(Elimination matrix)' $E_{ij}$ 를 양변 왼쪽에 곱하면, 똑같은 결과를 얻는다.

 

그대로 위 예시에 적용해 봅시다. 소거행렬을 찾기 위해서 첫번째로 할 일은 승수(multiplier)찾기 입니다. 승수가 무엇인지는 이전 포스팅에서 설명했었죠. 일반적으로 $3 \times 3$ 행렬에선 2행 1열 성분을 0으로 만드는 것이 두번째 pivot 을 구하기 위한 첫 목표이기 때문에 소거의 첫 단추는 2행 1열 성분을 0으로 바꾸는 것입니다. 2행 1열 성분의 승수는

 

$$l_{21}=\frac{a_{21}}{\mathrm{First\;pivot}}=\frac{2}{1}=2$$

 

이고, 이 값에 음의 기호를 붙인 수 -2를 항등행렬의 2행 1열 성분에 추가시키면 소거행렬이 완성됩니다.

 

 

이 행렬을 소거연산 적용 전 오리지날 연립일차방정식에 곱해봅시다.

 

$$E_{21}A=\begin{pmatrix}
1 & 0 & 0\\ 
-2 &1  & 0\\ 
0 &0  &1 
\end{pmatrix}\begin{pmatrix}
1 & 2 & 3\\ 
2 &-1  & 1\\ 
3 &0  &-1 
\end{pmatrix}=\begin{pmatrix}
1 & 2 & 3\\ 
0 &-5 & -5\\ 
3 &0  &-1 
\end{pmatrix}$$

 

결론이 나왔습니다. 소거행렬을 양변 왼쪽에 곱하는 행위는 소거법으로 연산을 하는 행위와 똑같은 결과를 낳습니다. 실은, 동치입니다.

 

물론 이것은 하나의 예시를 든 것이지 명확한 수학적 증명을 한 것은 아닙니다. 증명은 기본행연산을 정확히 배우고 나서 소개하도록 할 것입니다. 중요한건 행렬의 몇가지 연산(기본행연산)은 어떤 행렬의 곱으로 대체할 수 있다는 것이고, 대표적인 것이 소거행렬이라는 사실입니다.

---

2. 치환행렬(Permutation matrix)

​

'Permutation' 에서 알 수 있듯이 치환행렬은 순열행렬이라고 부르기도 합니다. 확률과 통계 등에서는 'Permutation' 을 '순열'로 이해하면 되는데, 대수학에서는 '치환'의 의미를 갖는 경우가 대부분입니다. 나중에 배울 행렬식(determinant) 역시 좀 어렵게는 치환으로 정의하게 됩니다. 한국어로는 순열, 치환 둘로 용어가 다르지만 영어 단어는 하나를 쓰듯이, 대수학에서 치환의 뜻은 확률과 통계에서 배운 순열과 크게 다르진 않습니다. 특정 대상 몇가지를 순서를 바꿔 나열하는 총 가짓수를 순열이라고 부르듯이, 치환이란 똑같은 개수의 숫자들을 위치만 바꾸어 배열하는 것을 말합니다. 이 행렬이 필요한 이유는 다음과 같습니다.

 

$$ \left\{\begin{matrix}
0x+2y=9\\ 
5x-y=8
\end{matrix}\right. $$

 

위와 같은 연립방정식을 중학교 지식으로 푸는 것은 암산으로도 가능한데, 그 방법 말고 여기서는 행렬 연산으로 푸려고 합니다. pivot 도 구할 것이고요. 근데 1행의 첫 미지수 계수가 0이지 않습니까? 그러면 첫번째 pivot 은 0이고, pivot 의 개수 또한 0이라 해야 할까요? 그렇지 않습니다. 이 연립방정식의 1행과 2행을 뒤바꿔

 

$$\left\{\begin{matrix}
5x-y=8\\ 
0x+2y=9
\end{matrix}\right.$$

 

로 만들어, 첫번째 pivot 이 5가 된다는 사실을 알아야 합니다. 이것은 순서를 바꾸기 때문에 순열, 치환이라고 불리는데 간단하게는 행교환이라고 말합니다. 이 작업 역시, 치환행렬이라 불리는 행렬을 곱해버리기만 하면 알아서 마무리가 됩니다. 즉 치환행렬은 소거행렬을 구할 때 처음 pivot 자리에 0이 와있는 경우, 첫 미지수 계수가 0이 아닌 다른 행을 맨 위로 올리는 작업을 할 때 필요한 도구입니다.

 

$3\times 3$ 단위행렬을 토대로 치환행렬의 형태를 찾아봅시다.

 

$$I_3=\begin{pmatrix}
1 &0  &0 \\ 
0 & 1 & 0\\ 
 0& 0&1 
\end{pmatrix}=\begin{pmatrix}
\mathbf{r_1}\\ 
\mathbf{r_2}\\ 
\mathbf{r_3}
\end{pmatrix}$$

 

한 행을 하나의 벡터($\mathbf{r}$)로 보고, 그들끼리 행렬 내부에서 위치를 바꾸는 가짓수는 몇가지가 될까요? $3!=6$가지가 될 것입니다. 물론 열 관점에서 세 개의 열끼리 교환한다고 해도 동일한 가짓수가 나옵니다. 귀찮지만 다 써보겠습니다.

 

$$ \begin{pmatrix}
1 &0  &0 \\ 
0 & 1 & 0\\ 
 0& 0&1 
\end{pmatrix}\;,\;\begin{pmatrix}
1 &0  &0 \\ 
0 & 0 & 1\\ 
 0& 1&0
\end{pmatrix}\;,\;\begin{pmatrix}
0 &1  &0 \\ 
0 &0 & 1\\ 
 1& 0&0 
\end{pmatrix}$$
$$\begin{pmatrix}
0 &1  &0 \\ 
1 & 0 & 0\\ 
 0& 0&1 
\end{pmatrix}\;,\;\begin{pmatrix}
0 &0  &1 \\ 
1 & 0 & 0\\ 
 0& 1&0 
\end{pmatrix}\;,\;\begin{pmatrix}
0 &0  &1 \\ 
0 & 1 & 0\\ 
 1& 0&0 
\end{pmatrix}$$

 

이 6개의 행렬들이 바로 항등행렬 $I_n$의 치환행렬들입니다. 치환행렬의 정의는 다음과 같습니다.

 

'치환행렬(Permutation matrix)'은 모든 성분이 $0$ 또는 $1$ 뿐이고 각 행과 열에 단 하나의 $1$만을 포함한 행렬이다. 곧, 항등행렬의 $i$행과 $j$행을 유한번 바꾼 행렬로, $P_{ij}$ 로 표기한다.

어떤 행렬에 치환행렬을 곱하면 항등행렬에서와 같이 그 행렬의 $i$행과 $j$행이 유한번 바뀐다.

 

예를 들어 항등행렬의 1행과 3행을 바꾼 행렬은 치환행렬의 일종이고, $P_{13}$으로 표기합니다. 만약 임의의 행렬 $A$에 이를 곱하면 $A$의 1행과 3행이 뒤바뀝니다.

 

$$ P_{13}A=\;\begin{pmatrix}
0 &0  &1 \\ 
0 & 1 & 0\\ 
 1& 0&0 
\end{pmatrix}\begin{pmatrix}
1 &2  &3 \\ 
2 & -1 &1 \\ 
3 & 0 &-1 
\end{pmatrix}=\begin{pmatrix}
3 & 0 &-1 \\ 
2 &-1  &1 \\ 
1 &2  &3 
\end{pmatrix}$$