[Linear Algebra] [2-3] Elimination Using Matrices

2.3 Elimination Using Matrices

0. Introduction

2.2에서는 소거(elimination)를 방정식 그 자체에 대한 조작으로 보았다면, 2.3에서는 이 과정을 행렬 곱셈으로 표현하는 방법을 배운다. 핵심 아이디어는 다음과 같다.

• 각 소거 단계는 하나의 행 연산(row operation)이다.
• 행 연산은 모두 어떤 행렬과의 곱, 즉 “소거 행렬(elimination matrix)”로 표현할 수 있다.
• 여러 번의 소거 과정을 모으면, 결국 $$ A = LU $$ 꼴의 LU 분해(lower × upper)로 연결된다.

즉, “소거를 반복한다”는 말을 “어떤 행렬들을 곱해서 $A$ 를 더 단순한 모양으로 만든다”로 바꿔서 생각할 수 있다.

---

1. 소거를 행렬 곱으로 표현하기

예를 들어 다음과 같은 $3 \times 3$ 연립방정식을 생각하자.

$$ A x = b, \quad A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix}, \quad x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}, \quad b = \begin{bmatrix} 2 \\ 12 \\ 2 \end{bmatrix}. $$

우리는 2행의 $3$을 없애기 위해

• “2행 ← 2행 − 3 × 1행”

이라는 소거를 수행한다. 이 행 연산을 행렬 하나로 표현하면 어떨까?

다음 행렬을 정의하자.

$$ E_1 = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}. $$

이제 $E_1 A$ 를 계산하면, 실제로 “2행에서 1행의 3배를 빼 준 결과”가 나온다.

$$ E_1 A = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}. $$

즉, “행 연산 = 행렬 $E_1$ 을 왼쪽에서 곱하는 것”이다.

[[picture : A 행렬에 왼쪽에서 E1을 곱해 2행의 첫 원소가 0이 되는 과정을 화살표로 보여주는 그림]]

---

2. 소거 행렬(Elimination matrix)의 일반 형태

일반적으로, $i$행에서 $j$행의 $m$배를 빼는 연산

$$ \text{row}_i \leftarrow \text{row}_i - m \cdot \text{row}_j $$

은 다음과 같은 $E$ 행렬로 표현된다.

• 대각선 성분은 모두 $1$
• $i$행 $j$열에만 $-m$ 이 들어감
• 그 외 성분은 모두 $0$

예를 들어 “3행에서 1행의 $2$배를 빼라”는 연산은

$$ E = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{bmatrix} $$

가 되고, $EA$ 를 계산하면 3행의 첫 번째 항이 0이 된다.

중요한 점은, 이러한 $E$ 행렬들 역시 모두 역행렬을 가진다는 것이다. (행 연산을 반대로 되돌리는 행 연산도 항상 존재하므로)

---

3. 여러 번의 소거 = 여러 개의 소거 행렬 곱

실제로 소거를 할 때는 보통 한 번만 하는 것이 아니라 여러 단계를 거친다. 예를 들어

1. $E_1$ : 2행에서 1행의 3배를 빼서, 2행의 첫 항 제거
2. $E_2$ : 3행에서 2행의 어떤 배수를 빼서, 3행의 두 번째 항 제거

이 두 소거를 모두 $A$ 에 적용하면

$$ U = E_2 E_1 A $$

와 같이 위가 삼각형 형태인 행렬 $U$를 얻게 된다. 이 $U$ 가 바로 2장에서 계속 등장하는 upper triangular matrix이다.

[[picture : A에 E1을 곱해 중간 행렬을 만들고, 다시 E2를 곱해 위삼각행렬 U가 되는 과정을 단계별로 보여주는 그림]]

---

4. LU 분해 아이디어 (A = LU)

조금만 더 나아가면, 위 과정으로부터 자연스럽게

$$ E_2 E_1 A = U $$

라는 관계를 얻는다. 양변에 $E_2^{-1}, E_1^{-1}$ 을 곱하면

$$ A = E_1^{-1} E_2^{-1} U. $$

여기서

• $L = E_1^{-1} E_2^{-1}$ 를 lower triangular matrix로
• $U$ 를 upper triangular matrix로

볼 수 있어, 결과적으로

$$ A = L U $$

라는 LU 분해(LU factorization)가 등장한다.

이 아이디어는 이후에 “한 번만 소거 과정을 수행해 $L$ 과 $U$ 를 구해두면, 서로 다른 여러 $b$ 에 대해 $Ax = b$ 를 빠르게 풀 수 있다” 라는 사실로 이어진다.

---

5. 행 교환과 치환 행렬(Permutation matrix)

만약 소거 과정에서 피벗이 0 인 상황이 나오면 어떻게 될까? 2.2에서 본 것처럼, 우리는 행 교환(row exchange)을 사용한다.

행 교환 역시 “행렬”로 표현할 수 있다. 예를 들어 1행과 2행을 교환하고 싶다면

$$ P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

와 같은 치환 행렬(permutation matrix)을 왼쪽에서 곱한다:

$$ PA $$

그러면 $A$ 의 1행과 2행이 서로 바뀐 행렬이 된다. 실제 계산에서는 필요에 따라

$$ PA = LU $$

처럼, 치환 행렬까지 포함한 더 일반적인 형태의 LU 분해를 많이 사용한다.

[[picture : A의 첫 두 행이 화살표로 서로 위치를 바꾸고, 왼쪽에는 P를 곱하는 그림]]

---

6. 2.3 요약

1. 각 소거 단계(행 연산)는 하나의 소거 행렬 $E$로 표현할 수 있다.
2. 여러 소거 단계를 모두 적용하면 $$ U = E_k \cdots E_2 E_1 A $$ 와 같은 위삼각 행렬 $U$ 를 얻게 된다.
3. 역으로 보면 $$ A = L U $$ 꼴의 LU 분해가 등장하며, 여기서 $L$ 은 소거 행렬들의 역행렬을 곱해 만든 lower triangular matrix이다.
4. 피벗이 0인 경우에는 치환 행렬 $P$을 사용해 행을 교환하고, 일반적으로는 $$ PA = LU $$ 형태로 생각한다.

---

2.3에서는 소거 과정을 행렬 형태로 표현하고, 그 결과가 LU 분해로 이어진다는 것을 배웠다. 이번 보충 예제에서는 실제로 L은 아래삼각행렬(lower triangular), U는 위삼각행렬(upper triangular)이 되는지 눈으로 확인해본다.

다음 행렬을 고려하자.

$$ A = \begin{bmatrix} 2 & 4 & 2 \\ 4 & 9 & 6 \\ 2 & 6 & 5 \end{bmatrix} $$

소거 과정을 거쳐 $A$ 를 $LU$ 로 분해하면 다음을 얻게 된다.

$$ L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 2 & 1 \end{bmatrix}, \qquad U = \begin{bmatrix} 2 & 4 & 2 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix} $$

• $L$ 은 Lower triangular — 대각선 위 성분이 모두 0
• $U$ 는 Upper triangular — 대각선 아래 성분이 모두 0

이제 두 행렬을 실제로 곱해보면 아래와 같다.

$$ LU = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 2 & 1 \end{bmatrix} \begin{bmatrix} 2 & 4 & 2 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 4 & 2 \\ 4 & 9 & 6 \\ 2 & 6 & 5 \end{bmatrix} $$

곱한 결과가 정확히 원래의 $A$ 와 동일하다. 즉,

$$ A = LU $$

가 실제로 성립함을 확인할 수 있다.

---

이 예시로 얻을 수 있는 핵심 이해 포인트

1. $L$ 은 소거 과정에서 사용된 multiplier(배수) 를 기록한 행렬이다.
2. $U$ 는 모든 소거가 끝난 후 남는 upper triangular 행렬이다.
3. 따라서 소거법을 행렬 곱의 언어로 표현하면 자연스럽게 LU 분해로 연결된다.

[[picture : Ax=b → LUx=b → Ly=b → Ux=y 해를 단계별로 푸는 두 단계 알고리즘 흐름도]]

또한 $A x = b$ 문제를 풀 때 $LU$ 를 이용하면 다음과 같은 두 단계 풀이가 가능하다.

$$ Ly = b \quad \Rightarrow \quad Ux = y $$

즉, 한 번만 소거하여 $L$ 과 $U$ 를 구해두면, 새로운 $b$ 가 들어와도 소거를 반복할 필요 없이 매우 빠르게 연립방정식을 풀 수 있다.

2.3의 핵심은 “소거를 행렬 곱으로 표현하면, 연립방정식 풀이 과정이 모두 선형대수의 언어(행렬, 부분공간, 분해)로 바뀐다”는 점이다. 이 관점이 이후의 LU 분해, 역행렬 계산, 수치해석 알고리즘의 기초가 된다.