가우스 소거법을 행렬로 표현하기

다음 선형 방정식계를 생각한다.

$$\begin{align} 2x_1 + 4x_2 -2x_3 &= 2 \\ 4x_1 + 9x_2 -3x_3 &= 8 \\ -2x_1 - 3x_2 + 7x_3 &= 10 \end{align}$$

행렬 방정식으로 쓰면 다음과 같다.

$$\begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 2 \\ 8 \\ 10 \end{bmatrix}$$

가우스 소거법의 각 단계인 제거와 행 교환을 행렬을 통해 구조화할 수 있다.

• 제거 연산은 제거 행렬 $E$로 표현한다.
• 행 교환은 순열 행렬 $P$로 표현한다.
• 즉, 제거와 행 교환이라는 절차를 행렬 곱셈으로 치환하는 것이다.

기본적으로 가우스 소거법은 행(row) 연산이다.

제거 대상 계수와 피봇 계수를 이용해 multiplier를 구하고, 다음 방식으로 소거를 수행한다.

$$\text{제거 대상 방정식} - \text{multiplier} \times \text{피봇 방정식}$$

---

가우스 소거법을 행렬로 표현하는 단계

1. 방정식 $Ax=b$의 양변에 두 번째 방정식의 $x$를 소거하는 제거 행렬 $E_{21}$을 곱한다.

$$E_{21}Ax = E_{21}b$$

2. 행렬 $E_{21}Ax$에서 $(2,1)$ 위치의 원소는 0이 된다. 즉, 두 번째 방정식에서 $x$가 소거된다.

3. $E_{21}$은 identity matrix의 2행 1열을 다음 값으로 바꾼 행렬이다.

$$-\frac{a_{21}}{a_{11}}$$

4. 행렬-행렬 곱셈은 여러 개의 행렬-벡터 곱셈으로 볼 수 있다.

$$EA = [Ea_1 \ \cdots \ Ea_n]$$

5. 좌변의 $A$뿐만 아니라 우변의 $b$에도 같은 제거 행렬 $E$를 곱해야 한다. 이를 편리하게 수행하기 위해 첨가행렬을 사용한다.

$$[A \ \ b] = [a_1 \ \cdots \ a_n \ \ b]$$

6. 제거 행렬 $E_{ij}$를 반복적으로 곱하면 위삼각행렬 $U$를 얻는다.

7. 행 교환(row exchange) 행렬은 $P_{ij}$로 표기한다. $P_{ij}$는 단위행렬의 행 $i$와 행 $j$를 교환하여 만든다.

---

제거 행렬과 $LU$ 분해

각 제거 단계를 나타내는 $E_{ij}$를 하나의 행렬 $E$로 결합할 수 있다.

최종적으로는 $E_{ij}$의 역행렬인 $(E_{ij})^{-1}$을 구하고, 전체에 대해 다음을 얻는 것이다.

$$L = E^{-1}$$

즉, 행렬 $A$는 다음처럼 분해된다.

$$A = LU$$

전체 과정은 다음과 같다.

1. 행렬곱 수행 과정을 확인한다.
2. 여러 제거 행렬 $E_{ij}$를 하나의 $E$로 통합한다.
3. 각 $E_{ij}$가 어떻게 $(E_{ij})^{-1}$로 역전되는지 확인한다.
4. 올바른 순서로 모든 역행렬 $(E_{ij})^{-1}$을 결합하여 $L$을 만든다.

---

행렬곱의 정의

열 기반 접근법에서 행렬곱 $Ax$는 $A$의 columns의 결합이다.

계산 과정에서는 row form을 사용하며, $Ax$는 $A$의 각 행과 벡터 $\vec{x}$의 내적으로 계산된다.

일반적으로 두 행렬 $A(m \times n)$과 $B(n \times p)$의 곱 $AB$는 다음과 같다.

$$(AB)_{ij} = \sum_{k=1}^{n} a_{ik}b_{kj}$$

즉, $AB$의 $(i,j)$ 원소는 $A$의 $i$번째 행(row)과 $B$의 $j$번째 열(column)의 내적이다.

---

제거 과정의 행렬 형태

우변 벡터 $b$와 제거 행렬 $E$를 다음과 같이 둔다.

$$b = \begin{bmatrix} 2 \\ 8 \\ 10 \end{bmatrix}, \quad E = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

$E$를 $b$에 곱하면 다음과 같다.

$$\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 \\ 8 \\ 10 \end{bmatrix} = \begin{bmatrix} 2 \\ 4 \\ 10 \end{bmatrix}$$

일반적으로는 다음과 같이 작용한다.

$$\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 - 2b_1 \\ b_3 \end{bmatrix}$$

multiplier는 다음과 같이 구한다.

$$\text{multiplier} = \frac{\text{제거 대상 계수}}{\text{pivot}}$$

$b_2$를 8에서 4로 만들기 위해, 다음 값으로 $E_{21}$을 설정한다.

$$-\frac{4}{2} = -2$$

---

$A$의 2행 1열 소거 예시

$A$의 2행 1열 원소를 0으로 만들기 위해 다음 제거 행렬을 왼쪽에서 곱한다.

$$EA = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix} = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ -2 & -3 & 7 \end{bmatrix}$$

위 과정은 1행과 3행을 바꾸지 않는다.

이때 pivot은 다음과 같다.

$$A_{11}=2$$

제거 대상은 다음 원소이다.

$$A_{21}=4$$

따라서 multiplier는 다음과 같다.

$$(-1)\left(\frac{4}{2}\right) = -2 = E_{21}$$

---

행렬곱의 결합 법칙과 교환 법칙

행렬곱에서는 결합 법칙은 성립한다.

$$A(BC) = (AB)C$$

하지만 일반적으로 교환 법칙은 성립하지 않는다.

$$AB \neq BA$$

---

왼쪽 곱셈 $EA$: 행 연산의 관점

행렬 $E$를 $A$의 왼쪽에 곱하면 $EA$가 된다.

이때 $E$의 행(row)이 $A$의 행들을 어떻게 조합할지 결정한다.

결과 행렬 $EA$의 각 행은 다음과 같이 계산된다.

• $EA$의 1행 전체 = $E$의 1행 $\times A$
• $EA$의 2행 전체 = $E$의 2행 $\times A$
• $EA$의 3행 전체 = $E$의 3행 $\times A$

즉, $E$의 $i$행 $\times A$는 $A$의 모든 행들의 선형결합이 된다.

이때 $E$의 $i$행 원소들이 그 선형결합의 계수가 된다.

따라서 왼쪽 곱셈은 행 연산을 수행한다.

---

오른쪽 곱셈 $AE$: 열 연산의 관점

행렬 $E$를 $A$의 오른쪽에 곱하면 $AE$가 된다.

이때 $E$의 열(column)이 $A$의 열들을 어떻게 조합할지 결정한다.

결과 행렬 $AE$의 각 열은 다음과 같이 계산된다.

• $AE$의 1열 전체 = $A \times E$의 1열
• $AE$의 2열 전체 = $A \times E$의 2열
• $AE$의 3열 전체 = $A \times E$의 3열

즉, $A \times (E\text{의 } k\text{열})$은 $A$의 모든 열들의 선형결합이 된다.

이때 $E$의 $k$열 원소들이 그 선형결합의 계수가 된다.

따라서 오른쪽 곱셈은 열 연산을 수행한다.

---

행렬곱의 계산: 열 단위 분리

$B$가 여러 개의 columns인 $b_1, b_2, b_3$로 이루어져 있다면, $AB$의 columns는 다음과 같이 계산된다.

$$AB = A[b_1 \ \ b_2 \ \ b_3] = [Ab_1 \ \ Ab_2 \ \ Ab_3]$$

즉, 일반적인 행렬곱 $AB$는 $B$를 열벡터의 묶음으로 보고, $A$를 각 열벡터에 곱하는 방식으로 계산할 수 있다.

이는 다음을 의미한다.

$$E(\text{column } j \text{ of } A) = \text{column } j \text{ of } EA$$

---

순열(Permutation) 행렬 $P_{ij}$

소거 과정에서 pivot에 0이 등장하면 row exchange가 필요하다.

순서를 재배치하는 연산을 순열(permutation)이라고 하며, 이를 수행하는 행렬을 permutation matrix라고 한다.

순열 행렬은 단위행렬의 행을 바꿔서 만든다.

예를 들어 2행과 3행을 바꾸는 permutation matrix는 다음과 같다.

$$P_{23} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}$$

이 행렬을 벡터에 곱하면 2번째 성분과 3번째 성분이 교환된다.

$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 3 \\ 5 \end{bmatrix} = \begin{bmatrix} 1 \\ 5 \\ 3 \end{bmatrix}$$

---

첨가행렬(Augmented Matrix)

소거, 순열 등의 연산은 $Ax=b$에서 양변에 동시에 수행되어야 한다.

이를 편리하게 처리하기 위해 첨가행렬을 구성한다.

$$G = [A \ \ b]$$

예제의 첨가행렬은 다음과 같다.

$$[A \ \ b] = \begin{bmatrix} 2 & 4 & -2 & 2 \\ 4 & 9 & -3 & 8 \\ -2 & -3 & 7 & 10 \end{bmatrix}$$

첨가행렬에 제거 행렬을 곱하면 $A$와 $b$에 동시에 같은 행 연산이 적용된다.

$$\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 4 & -2 & 2 \\ 4 & 9 & -3 & 8 \\ -2 & -3 & 7 & 10 \end{bmatrix} = \begin{bmatrix} 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 4 \\ -2 & -3 & 7 & 10 \end{bmatrix}$$

제거 연산을 통해 새롭게 도출된 두 번째 방정식은 다음과 같다.

$$x_2 + x_3 = 4$$

---

첨가행렬에서 행렬곱의 작용

행렬곱은 행과 열의 관점에서 동시에 이해할 수 있다.

Rows 관점

$E$의 각 행이 첨가행렬 $[A \ \ b]$에 작용하여 $[EA \ \ Eb]$의 행을 만든다.

즉, $E$의 해당 행이 $A$의 모든 행을 어떻게 조합할지 결정한다.

Columns 관점

$E$는 첨가행렬 $[A \ \ b]$의 각 열에 작용하여 $[EA \ \ Eb]$의 열을 만든다.

즉, $E$가 $A$의 개별 열과 $b$에 각각 작용한다.

---

정리

1. 가우스 소거법은 제거와 행 교환을 반복하여 $Ax=b$를 $Ux=c$로 바꾸는 과정이다.

2. 제거 연산은 제거 행렬 $E_{ij}$로 표현할 수 있다.

3. 행 교환은 순열 행렬 $P_{ij}$로 표현할 수 있다.

4. 제거 행렬은 단위행렬에서 소거 위치의 값을 multiplier의 음수로 바꾼 형태이다.

$$E_{ij} = I \text{에서 } (i,j) \text{ 위치를 } -l_{ij} \text{로 바꾼 행렬}$$

5. 왼쪽 곱셈 $EA$는 행 연산을 의미한다.

6. 오른쪽 곱셈 $AE$는 열 연산을 의미한다.

7. 첨가행렬 $[A \ \ b]$를 사용하면 $A$와 $b$에 같은 행 연산을 한 번에 적용할 수 있다.

8. 제거 행렬들의 역행렬을 올바른 순서로 결합하면 $L$을 얻고, 최종적으로 다음 분해를 얻는다.

$$A = LU$$