2.3 치환행렬(Permutation matrix) & 첨가행렬(Augmented matrix)

치환행렬(Permutation matrix)은 행렬의 행의 순서를 바꾸는 행렬입니다. 소거법의 일시적 실패 시 행들의 순서를 치환하여 소거를 진행할 수 있습니다. 또한, 소거 과정의 편의를 위해 $Ax = b$에서 $A$와 $b$를 합한 첨가행렬(Augmented matrix)을 이용합니다.

 

치환행렬(Permutation matrix)

보통 $i$ 번째 행과 $j$ 번째 행을 치환하는 치환행렬은 $P_{ij}$으로 씁니다. 
예를 들어, $P_{23}$은 행렬의 2번 행과 3번 행을 치환합니다.
치환행렬 역시 단위행렬에서 시작하고, 바꾸려는 행들을 치환합니다.

 

예를 들면, $P_{23}$ = $\begin{bmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array} \end{bmatrix}$ 는 단위행렬의 2번과 3번 행이 치환된 것입니다.

 

다음과 같이 치환행렬을 다른 행렬에 곱하겠습니다.

$\begin{bmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array} \end{bmatrix}$$\begin{bmatrix} \begin{array}{rrr} 2 & 4 & 1 \\ 0 & 0 & 3 \\ 0 & 6 & 5 \end{array} \end{bmatrix}$ = $\begin{bmatrix} \begin{array}{rrr} 2 & 4 & 1 \\ 0 & 6 & 5 \\ 0 & 0 & 3 \end{array} \end{bmatrix}$.

다른 예시로, 1번과 3번 행을 바꾸는 치환행렬 $P_{13}$는

 

$P_{13}$ = $\begin{bmatrix} \begin{array}{rrr} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{array} \end{bmatrix}$  입니다.

---

첨가행렬(Augmented matrix)

행렬 방정식 $Ax = b$에 소거나 치환을 하게 되면 양변에 같은 연산을 해야 합니다. 

 

예를 들면, $E_{32}E_{31}E_{21}Ax$ = $E_{32}E_{31}E_{21}b$과 같이... 

 

첨가행렬을 사용하면 연산을 좌우 변 따로 하지 않고 함께 할 수 있습니다.

첨가행렬은 $A$에 $b$를 더하여 [$A$   $b$]로 만듭니다.

 

만약, $Ax = b$가 $\begin{bmatrix} \begin{array}{rrr} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{array} \end{bmatrix}$$\begin{bmatrix} \begin{array}{r} x_{1} \\ x_{2} \\ x_{3} \end{array} \end{bmatrix}$ = $\begin{bmatrix} \begin{array}{r} 2 \\ 8 \\ 10 \end{array} \end{bmatrix}$ 이면, 

첨가행렬 [$A$   $b$] = $\begin{bmatrix} \begin{array}{rrrr} 2 & 4 & -2 & 2 \\ 4 & 9 & -3 & 8 \\ -2 & -3 & 7 & 10 \end{array} \end{bmatrix}$입니다.

소거나 치환 같은 연산은 $A$와 $b$에 각각 진행합니다.

예를 들면, [$E_{21}A$  $E_{21}b$] = $\begin{bmatrix} \begin{array}{rrr} 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 4 \\ -2 & -3 & 7 & 10 \end{array} \end{bmatrix}$.

---

다른 예를 보겠습니다.

[$A$    $b$] = $\begin{bmatrix} \begin{array}{rrrr} 1 & 2 & 2 & 1 \\ 4 & 8 & 9 & 3 \\ 0 & 3 & 2 & 1 \end{array} \end{bmatrix}$.

2번 행의 ‘4’를 제거하기 위한 multiplier는 4이므로,

소거행렬은 $E_{21}$ = $\begin{bmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ -4 & 1 & 0 \\ 0 & 0 & 1 \end{array} \end{bmatrix}$입니다.

$E_{21}$[$A$   $b$] = $\begin{bmatrix} \begin{array}{rrr} 1 & 2 & 2 & 1 \\ 0 & 0 & 1 & -1 \\ 0 & 3 & 2 & 1 \end{array} \end{bmatrix}$

상부 삼각형을 만들려면 2번과 3번 행을 치환해야 합니다. 

즉, $P_{32}E_{21}$[$A$   $b$] = $\begin{bmatrix} \begin{array}{rrr} 1 & 2 & 2 & 1 \\ 0 & 3 & 2 & 1 \\ 0 & 0 & 1 & -1 \end{array} \end{bmatrix}$.

이때, 소거와 치환 연산을 같이 할 수 있는 행렬은

 

$P_{32}E_{21}$ = $\begin{bmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 0 & 1 \\ -4 & 1 & 0 \end{array} \end{bmatrix}$입니다.