[선형대수] 2. 행렬의 소거법 (Elimination with Matrices)

연립방정식을 푸는 것의 핵심은 solution set은 유지하면서 연립 방정식을 더 간단한 형태로 변형하는 elementary transformations이다.

• a) 행렬에서 두 rows의 exchange
• b) a row에 대한 0이아닌 상수 곱
• c) 두 rows의 덧셈

1. Row-Echelon Form (REF)

다음의 연립방정식을 고려해보자.

$$\begin{align} x_1 + 2x_2 + x_3 &= 2 \\ 3x_1 + 8x_2 + x_3 &=12 \\ 4x_2 + x_3 &=2 \end{align} \tag{1}$$

이를 $\mathbf{Ax}=\mathbf{b}$의 form에서 간략성을 위해 변수 $\mathbf{x}$의 노테이션을 생략한 형태를 augmented matrix라고 하며 다음과 같이 나타낸다.

$$\begin{equation} \left[ \begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 3 & 8& 1 & 12 \\ 0 & 4 & 1 & 2  \end{array} \right] \end{equation} \tag{2} $$

여기서 elementary transformations에 의해 다음과 같이 간략화 시킬 수 있다.

$$\left[ \begin{array}{ccc|c} \color{red}{1} & 2 & 1 & 2 \\ 3 & 8& 1 & 12 \\ 0 & 4 & 1 & 2  \end{array} \right] \begin{array} \\ -3R_1 \\ \end{array} \Rightarrow \left[ \begin{array}{ccc|c} \color{red}{1} & 2 & 1 & 2 \\ 0 & \color{red}{2}& -2 & 6 \\ 0 & 4 & 1 & 2  \end{array} \right] \begin{array} \, \\ \, \\ -2R_2 \end{array} \Rightarrow \left[ \begin{array}{ccc|c} \color{red}{1} & 2 & 1 & 2 \\ 0 & \color{red}{2}& -2 & 6 \\ 0 & 0 & \color{red}{5} & -10  \end{array} \right] \tag{3}$$

마지막 행렬과 같이 upper triangular matrix의 형태를 REF라고 하며 빨간색으료 표시된 요소는 pivot이라 한다.

이를 다시 연립방정식으로 바꾸면,

$$\begin{align} x_1 + 2x_2 + x_3 &= 2 \\ 2x_2 - 2x_3 &=6 \\ 5x_3 &=-10 \end{align} \tag{4}$$

이는 back substitution에 의해 밑에서부터 $x_3=-2, x_2=1, x_1=2$로 풀 수 있다.

 

2. Elimination Matrix and Elementary Matrix

이 섹션에서는 Elimination 및 elementary transformations을 컴퓨터가 처리할 수 있도록 행렬곱으로써 어떻게 나타내는지에 대해 살펴본다.

 

먼저 행렬 연산들은 다음과 같이 동작한다.

1) matrix $\times$ column $\to$ column

$$\begin{bmatrix} - & - & -\\ - & - &- \\ -&-&- \end{bmatrix} \begin{bmatrix} 3 \\ 4 \\ 5 \end{bmatrix} = \begin{matrix} 3 \times \text{col1} \\ 4 \times \text{col2} \\ 5 \times \text{col3} \end{matrix} \tag{5}$$

2) row $\times$ matrix $\to$ row

$$\begin{bmatrix} 1 & 2 & 7 \end{bmatrix} \begin{bmatrix} - & - & -\\ - & - &- \\ -&-&- \end{bmatrix} = \begin{matrix} 1 \times \text{row1} \\ 2 \times \text{row2} \\ 7 \times \text{row3} \end{matrix} \tag{6}$$

 

먼저 row $\times$ matrix $\to$ row의 동작원리를 떠올리면서 Eq. (3)의 첫번째 화살표에 대한 처리를 행렬 곱으로 나타내보자.

$$\begin{bmatrix} 1 & 0 & 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} \tag{7}$$

여기서 첫번째 row와 세번째 row는 변하지 않으므로 [1 0 0]과 [0 0 1]이 되며 두번째 row는 $-3 \times$ row1 $+ 1$ row2와 같이 계산되므로 다음과 같이 [-3 1 0]을 곱하는 것에 의해 표현될 수 있다.

$$\underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{E_{21}} \underbrace{\begin{bmatrix} 1 & 2 & 1\\ 3 & 8 &1 \\ 0&4&1 \end{bmatrix}}_{A} = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} \tag{8}$$

여기서 $E_{21}$은 A의 2번째 row, 1번째 column의 요소를 제거하기 위한 행렬을 의미한다.

Eq. (3)의 두번째 화살표도 동일하게 나타낼 수 있다.

$$\underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix}}_{E_{32}} \begin{bmatrix} 1 & 2 & 1\\ 0 & 2 &-2 \\ 0&4&1 \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}}_{U} \tag{9}$$

이것을 간단한 형태로 나타내면 결합법칙에 의해 다음과 같이 쓸 수 있다.

$$\begin{align} E_{32}(E_{21}A) &= U \\ \Rightarrow (E_{32}E_{21})A &= U \end{align} \tag{10}$$

결과적으로 $A$를 $U$로 만드는 elimination matrix는 $E_{32}$와 $E_{21}$를 곱한 하나의 행렬로 표현 가능하며 컴퓨터에 저장 및 recomputation 관점에서 효율적이다.

 

위의 elimination matrix를 도출하는 과정에서 elementary transformations중 a row에 대한 상수 곱과 두 rows의 덧셈을 행렬곱으로 나타내는 법을 보았다.

비슷하게 행렬에서 rows의 exchange는 치환행렬을 통해 수행될 수 있다.

Permutation Matrix

- Exchange rows 1 and 2

$$\underbrace{\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}}_{P} \begin{bmatrix} a & b\\ c &d \end{bmatrix} = \begin{bmatrix} c & d \\ a & b \end{bmatrix} \tag{11}$$

- Exchange columns 1 and 2

$$ \begin{bmatrix} a & b\\ c &d \end{bmatrix} \underbrace{\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}}_{P} = \begin{bmatrix} b & a \\ d & c \end{bmatrix} \tag{12}$$

 

 

Reference

1. Deisenroth, Marc Peter, A. Aldo Faisal, and Cheng Soon Ong. Mathematics for machine learning. Cambridge University Press, 2020.

2. MIT Lecture by Gilbert Strang [Link]