안녕하세요. 지난 포스팅의 선형대수학 - 연립선형방정식 1에서는 연립방정식을 행렬의 형태로 변환하고 동차/비동차 연립방정식이 해가 가질 수 있는 조건에 대해서 알아보았습니다. 여기서 핵심은 비동차 연립방정식의 해집합은 비동차 연립방정식을 이용해서 구할 수 있다는 점이죠. 오늘은 실질적으로 해집합을 구하는 방법에 대해서 알아보도록 하겠습니다.
정의1. 동등성 (Equivalent)
두 연립선형방정식이 동일한 해집합을 가지면 동등하다 (equivalent)고 한다.
Two systems of linear equations are equivalent if they have the same solution set.
설명
오늘 알아볼 내용 중에서는 연립선형방정식을 행렬의 형태로 변환한 뒤 적절한 변환을 거쳐서 해를 구하는 과정이 존재합니다. 이 과정에서 변환된 행렬에 대응되는 연립선형방정식이 동일한 해집합을 가지는 지 증명할 필요가 있죠. 여기서 말하는 변환이란 선형대수학 - 기본행렬연산과 기본행렬의 기본행렬연산을 의미합니다. 기본행렬연산의 특징 중 하나는 선형대수학 - 행렬의 계수의 따름정리2-1에 의해 아무리 기본행렬연산을 곱해도 행렬의 계수는 변하지 않는다는 것이죠. 오늘은 이러한 성질을 활용할 예정입니다.
정리1
$A\mathbf{x} = \mathbf{b}$를 $m$개의 선형방정식과 $n$개의 변수를 가지는 연립 방정식이라고 하자. 그리고 행렬 $C$를 $m \times m$ 크기의 가역행렬이라고 하자. 그러면 $(CA)\mathbf{x} = C\mathbf{b}$는 $A\mathbf{x} = \mathbf{b}$와 동등하다.
증명
정리1은 정의1에서 제가 증명하고자 했던 부분을 설명해주고 있습니다. 여기서 기본행렬연산은 가역행렬이기 때문에 행렬 $C$를 기본행렬연산으로 생각하면 변환을 하더라도 두 연립방정식은 동일한 해집합을 가진다는 것을 알 수 있죠. 증명하는 과정은 두 연립방정식의 해집합 $K$와 $K^{'}$를 정의하고 두 집합이 동일함을 증명하면 됩니다. 따라서, 포함관계를 이용하여 증명하면 되죠.
$K$와 $K^{'}$를 각각 연립방정식 $A\mathbf{x} = \mathbf{b}$와 $(CA)\mathbf{x} = \mathbf{b}$의 해집합이라고 하자.
1). $\mathbf{w} \in K$라고 하면 $A\mathbf{w} = \mathbf{b}$이다. 양변에 행렬 $C$를 곱하면 $(CA)\mathbf{w} = C(A\mathbf{w}) = C\mathbf{b}$이므로 $\mathbf{w} \in K^{'}$이다.
2). $\mathbf{w} \in K^{'}$라고 하면 $(CA)\mathbf{w}^{'} = C\mathbf{b}$이다. 여기서 행렬 $C$가 가역행렬이므로 양변에 행렬 $C$의 역행렬 $C^{-1}$을 곱하면 $C^{-1}(CA)\mathbf{w}^{'} = C^{-1}(C\mathbf{b})$이므로 $A\mathbf{w} = \mathbf{b}$이다. 따라서, $\mathbf{w} \in K$이다.
1)과 2)에 의해 $K = K^{'}$이다.
따름정리1-1
$A\mathbf{x} = \mathbf{b}$를 $m$개의 선형방정식과 $n$개의 변수를 가지는 연립 방정식이라고 하자. 만약, $(A^{'} | \mathbf{b}^{'})$이 첨가행렬 $(A | \mathbf{b})$에 유한번의 기본행렬연산을 적용하여 얻어졌다고 하면 $A^{'}\mathbf{x} = \mathbf{b}^{'}$는 $A\mathbf{x} = \mathbf{b}$와 동등하다.
증명
저희는 앞으로 연립선형방정식의 해를 구할 때 첨가행렬의 형태로 바꾸어 해를 구할 예정입니다. 따라서, 따름정리1-1과 같이 첨가행렬에 대한 내용으로 바꾸어 증명해보도록 하죠.
$(A^{'} | \mathbf{b}^{'})$이 첨가행렬 $(A | \mathbf{b})$에 유한번의 기본행렬연산 $E_{1}, \dots, E_{p}$을 적용하여 얻었다고 하자. 따라서, 행렬 $C = E_{p} \cdots E_{1}$이라고 정의하면 다음과 같이 쓸 수 있다.
$$(A^{'} | \mathbf{b}^{'}) = C(A | \mathbf{b}) = (CA | C\mathbf{b})$$
여기서, 각 기본행렬연산 $E_{i}$는 가역이므로 행렬 $C$ 역시 가역행렬이다. 이제, $A^{'} = CA$ 그리고 $\mathbf{b}^{'} = C\mathbf{b}$라고 하면 정리1에 의해 두 연립방정식 $A^{'}\mathbf{x} = \mathbf{b}^{'}$와 $A\mathbf{x} = \mathbf{b}$는 서로 동등하다.
정의2. 기약행 사다리꼴 행렬 (Reduced Row Echelon Form; RREF)
행렬이 다음 3가지 조건을 만족하면 기약행 사다리꼴 행렬 (Reduced Row Echelon Form; RREF)라고 한다.
1). 0이 아닌 성분이 포함된 모든 행은 모든 성분이 0인 행보다 먼저 온다.
2). 각 행에서 첫 번째로 0이 아닌 성분은 해당 성분이 포함된 열에서 유일하게 0이 아니다.
3). 각 행에서 첫 번째로 0이 아닌 성분은 1이고 이전 행의 0이 아닌 첫 번째 성분의 오른쪽에 있는 열에서 구성된다.
A matrix is said to be in reduced row echelon form precedes any rows in the following three conditions are satisfied :
1). Any row containing a nonzero entry precedes any row in which all the entries are zero.
2). The first nonzero entry in each row is the only nonzero entry in its column.
3). The first nonzero entry in each row is 1 and it occurs in a column to the right of the first nonzero entry in the preceding row.
설명
정의2의 RREF는 앞으로 연립방정식의 해를 구하는 데 필수적인 요소입니다. 간단하게 예시를 들어서 설명해보도록 하죠.
$$A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1\end{bmatrix}, B = \begin{bmatrix} 0 & 1 & 0 & 2 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}, C = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$$
자, 위의 3개의 행렬 $A, B, C$ 중에서 기약행 사다리꼴 행렬이 어떤 행렬인지 알 수 있나요? 정답은 3개의 행렬 모두 만족하지 않습니다. $A$의 경우에는 2)조건을 만족하지 않습니다. 첫번째 행의 첫번째 열 성분이 1이지만 세번째 행의 첫번째 열 성분 역시 1이기 때문이죠. 그렇다면 $B$는 어떨까요? 1)조건을 만족하지 않습니다. 두번째 행이 첫번째 행보다 1이 먼저 등장하기 때문에 두 행을 바꾸어주어야 합니다. 마지막으로 행렬 $C$는 3)조건을 만족하지 않죠. 첫번째 성분이 1이여야하기 때문이죠. 따라서, 위 행렬들은 모두 기약행 사다리꼴 행렬이 아닙니다.
$$D = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0\end{bmatrix}$$
행렬 $D$의 경우에는 3개의 조건을 모두 만족하기 때문에 기약행 사다리꼴 행렬이라고 부를 수 있습니다. 여기까지와서 다시 원래의 주제로 돌아가서 저희는 원래 연립방정식을 풀기 위한 방법에 대해서 이야기하고 있었습니다. 기약행 사다리꼴 행렬과 어떤 관계가 존재하길래 갑자기 주제가 바뀌었을까요? 왜냐하면 기존의 연립방정식 $A\mathbf{x} = \mathbf{b}$를 기본행렬연산을 통해 기약행 사다리꼴 행렬로 변환한 새로운 연립방정식 $A^{'}\mathbf{x} = \mathbf{b}^{'}$을 만들어서 해를 구하면 훨씬 쉽게 구할 수 있기 때문이죠. 이러한 과정을 가우스 소거법 (Gaussian Elimination)이라고 말합니다. 그런데, 기약행 사다리꼴 행렬로 변환하면 원래 연립방정식과 동일한 해를 가질까요? 이는 저희가 이미 따름정리1-1에서 증명되었기 때문에 상관없습니다. 그렇다면 바로 가우스 소거법을 예시와 함께 정리해보도록 하겠습니다.
$$\begin{cases} 3x_{1} + 2x_{2} + 3x_{3} - 2x_{4} &= 1 \\ x_{1} + x_{2} + x_{3} &= 3 \\ x_{1} + 2x_{2} + x_{3} - x_{4} &= 2 \end{cases}$$
가우스 소거법 (Gaussian Elimination)
STEP0. 주어진 연립방정식을 첨가행렬 $(A | \mathbf{b})$로 변형한다.
$$(A | \mathbf{b}) = \left[ \begin{array}{cccc|c} 3 & 2 & 3 & -2 & 1 \\ 1 & 1 & 1 & 0 & 3 \\ 1 & 2 & 1 & -1 & 2 \end{array} \right]$$
STEP1. 첨가행렬 $(A | \mathbf{b})$의 맨 왼쪽 상단의 성분이 1이 되도록 만든다.
$$(A | \mathbf{b}) = \left[ \begin{array}{cccc|c} 3 & 2 & 3 & -2 & 1 \\ 1 & 1 & 1 & 0 & 3 \\ 1 & 2 & 1 & -1 & 2 \end{array} \right] \xrightarrow{r_{1} \leftrightarrow r_{3}} \left[ \begin{array}{cccc|c} 1 & 2 & 1 & -1 & 2 \\ 1 & 1 & 1 & 0 & 3 \\ 3 & 2 & 3 & -2 & 1 \end{array} \right]$$
STEP2. 3번 타입의 기본행연산을 이용해서 맨 왼쪽 상단을 제외한 다른 행의 성분이 0이 되도록 만든다.
$$\left[ \begin{array}{cccc|c} 1 & 2 & 1 & -1 & 2 \\ 1 & 1 & 1 & 0 & 3 \\ 3 & 2 & 3 & -2 & 1 \end{array} \right] \xrightarrow{\begin{cases} r_{2} = r_{2} - r_{1} \\ r_{3} = r_{3} - 3r_{1} \end{cases}} \left[ \begin{array}{cccc|c} 1 & 2 & 1 & -1 & 2 \\ 0 & -1 & 0 & 1 & 1 \\ 0 & -4 & 0 & 1 & -5 \end{array} \right]$$
STEP3. 맨 왼쪽 상단의 다음 행에서 0이 아닌 첫번째 성분이 1이 되도록 만든다.
$$\left[ \begin{array}{cccc|c} 1 & 2 & 1 & -1 & 2 \\ 0 & -1 & 0 & 1 & 1 \\ 0 & -4 & 0 & 1 & -5 \end{array} \right] \xrightarrow{r_{2} = -r_{2}} \left[ \begin{array}{cccc|c} 1 & 2 & 1 & -1 & 2 \\ 0 & 1 & 0 & -1 & -1 \\ 0 & -4 & 0 & 1 & -5 \end{array} \right]$$
STEP4. 3번 타입의 기본행연산을 이용해서 이전행과 현재행을 제외한 첫번째로 1이 나오는 열의 성분이 0이 되도록 만든다.
$$\left[ \begin{array}{cccc|c} 1 & 2 & 1 & -1 & 2 \\ 0 & 1 & 0 & -1 & -1 \\ 0 & -4 & 0 & 1 & -5 \end{array} \right] \xrightarrow{r_{3} = r_{3} + 4r_{2}} \left[ \begin{array}{cccc|c} 1 & 2 & 1 & -1 & 2 \\ 0 & 1 & 0 & -1 & -1 \\ 0 & 0 & 0 & -3 & -9 \end{array} \right]$$
STEP5. STEP3와 STEP4를 나머지 행에 대해 반복수행한다.
$$\left[ \begin{array}{cccc|c} 1 & 2 & 1 & -1 & 2 \\ 0 & 1 & 0 & -1 & -1 \\ 0 & 0 & 0 & -3 & -9 \end{array} \right] \xrightarrow{r_{3} = -\frac{1}{3}r_{3}} \left[ \begin{array}{cccc|c} 1 & 2 & 1 & -1 & 2 \\ 0 & 1 & 0 & -1 & -1 \\ 0 & 0 & 0 & 1 & 3 \end{array} \right] $$
STEP6. 맨 오른쪽 하단 성분을 제외한 다른 행의 성분이 0이 되도록 만든다.
$$\left[ \begin{array}{cccc|c} 1 & 2 & 1 & -1 & 2 \\ 0 & 1 & 0 & -1 & -1 \\ 0 & 0 & 0 & 1 & 3 \end{array} \right] \xrightarrow{\begin{cases} r_{1} = r_{1} + r_{3} \\ r_{2} = r_{2} + r_{3} \end{cases}} \left[ \begin{array}{cccc|c} 1 & 2 & 1 & 0 & 5 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & 3 \end{array} \right] $$
STEP7. STEP6를 다음 행에 대해서 아래행부터 두번째 행까지 반복수행한다.
$$\left[ \begin{array}{cccc|c} 1 & 2 & 1 & 0 & 5 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & 3 \end{array} \right] \xrightarrow{r_{1} = r_{1} - 2r_{2}} \left[ \begin{array}{cccc|c} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & 3 \end{array} \right]$$
여기서 잘 보시면 STEP1-STEP5는 가장 위의 행부터 시작하여 마지막 행으로 과정이 진행되고 있습니다. 이 과정을 Forward Pass라고 하며 첨가행렬이 상삼각행렬로 변환되는 과정입니다. 다음으로 STEP6-STEP7은 가장 아래 행부터 시작하여 위의 행으로 연산을 수행하기 때문에 Forward Pass의 반대개념으로 Backward Pass라고 불립니다. 이 과정은 상삼각행렬을 기약행 사다리꼴 행렬로 변환되는 과정입니다. 즉, 가우스 소거법은 최종적으로 주어진 연립방정식을 기약행 사다리꼴 행렬로 변환해주는 작업입니다! 실질적으로 가우스 소거법을 통해 얻은 새로운 연립방정식을 다시 보면 다음과 같습니다.
$$\begin{cases} x_{1} + x_{3} &= 1 \\ x_{2} &= 2 \\ x_{4} &= 3 \end{cases}$$
엄청 간단해지지 않았나요? 이를 통해서 $x_{3} = t$라고 할 때, $(x_{1}, x{2}, x_{3}, x_{4}) = (1 - t, 2, t, 3)$이 되는 것을 알 수 있습니다. 이를 열벡터로 표현하면 다음과 같죠.
$$\begin{bmatrix} 1 - t \\ 2 \\ t \\ 3 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 0 \\ 3 \end{bmatrix} + t \begin{bmatrix} -1 \\ 0 \\ 1 \\ 0 \end{bmatrix}$$
여기서 $\left[ -1 0 1 0 \right]^{t}$는 비동차 연립방정식 $A\mathbf{x} = \mathbf{b}$에 대응되는 동차 연립방정식 $A\mathbf{x} = 0$의 해집합의 기저입니다. 이와 같이 가우스 소거법을 이용해서 연립방정식을 푼다는 것은 행렬형태를 기약행 사다리꼴 행렬로 변형하면 쉽게 해집합을 찾는 것을 의미합니다.
정리2
가우스 소거법은 모든 행렬은 기약행 사다리꼴 행렬로 변환할 수 있다.
설명
그렇다면 한 가지 궁금증이 생깁니다. 연립방정식을 행렬 형태로 변환할 수 있는 것도 알게 되었고, 이를 가우스 소거법을 이용해서 기약행 사다리꼴 행렬로 간단하게 만들어 해를 구할 수 있다는 것 역시 알게 되었습니다. 그렇다면 다음 문제는 항상 기약행 사다리꼴 행렬로 바꿀 수 있을까요? 정리2는 이를 보장해주고 있습니다.
정리3
$A\mathbf{x} = \mathbf{b}$를 $r$개의 선형방정식과 $n$개의 변수를 가지는 연립 방정식이라고 하자. $\text{rank}(A) = \text{rank}(A | \mathbf{b})$ 그리고 $\text{rank}(A | \mathbf{b})$가 기약행 사다리꼴로 주어진다고 하자. 그러면 다음 두 명제가 성립한다.
(a). $\text{rank}(A) = r$
(b). 만약 연립방정식의 일반해가 $\mathbf{s} = \mathbf{s}_{0} + t_{1}\mathbf{u}_{1} + \cdots + t_{n - r}\mathbf{u}_{n - r}$로 주어지면 $\{\mathbf{u}_{1}, \dots, \mathbf{u}_{n - r}\}$은 $A\mathbf{x} = \mathbf{b}$에 대응되는 동차 연립방정식 $A\mathbf{x} = 0$의 해집합의 기저이고 $\mathbf{s}_{0}$는 $A\mathbf{x} = \mathbf{b}$의 해 중 하나이다.
증명
(a). $\text{rank}(A) = r$
연립방정식 $A\mathbf{x} = \mathbf{b}$의 첨가행렬 $(A | \mathbf{b})$이 기약행 사다리꼴 행렬이므로 $(A | \mathbf{b})$는 $r$개의 0이 아닌 행을 가진다. 따라서, 첨가행렬 $(A | \mathbf{b})$의 0이 아닌 행들은 선형독립이다. 따라서, $\text{rank}(A | \mathbf{b}) = \text{rank}(A) = r$이다.
(b). 만약 연립방정식의 일반해가 $\mathbf{s} = \mathbf{s}_{0} + t_{1}\mathbf{u}_{1} + \cdots + t_{n - r}\mathbf{u}_{n - r}$로 주어지면 $\{\mathbf{u}_{1}, \dots, \mathbf{u}_{n - r}\}$은 $A\mathbf{x} = \mathbf{b}$에 대응되는 동차 연립방정식 $A\mathbf{x} = 0$의 해집합의 기저이고 $\mathbf{s}_{0}$는 $A\mathbf{x} = \mathbf{b}$의 해 중 하나이다.
$K$를 비동차 연립방정식 $A\mathbf{x} = \mathbf{b}$의 해집합, $K_{H}$를 연립방정식 $A\mathbf{x} = \mathbf{b}$에 대응되는 동차 연립방정식 $A\mathbf{x} = 0$의 해집합이라고 하자. 이때, $t_{1} = \cdots = t_{n - r} = 0$이라고 하면 $\mathbf{s} = \mathbf{s}_{0} \in K$이다. 여기서 선형대수학 - 정리2에 의해 $K = \{\mathbf{s}_{0}\} + K_{H}$를 만족한다. 따라서, 다음을 만족한다.
$$K_{H} = \{\mathbf{s}_{0}\} + K = \text{span}\left( \{ \mathbf{u}_{1}, \mathbf{u}_{2}, \dots, \mathbf{u}_{n - r} \} \right)$$
여기서, $\text{rank}(A) = r$이므로 $\text{dim}(K_{H}) = n - r$이다. 이는 기저의 정의에 의해 $\{\mathbf{u}_{1}, \dots, \mathbf{u}_{n - r}\}$는 $K_{H}$를 생성한다.
참고문헌
Linear Algebra (Stephan. H)
'수학 > 선형대수학' 카테고리의 다른 글
| 선형대수학 - 행렬식 2 (0) | 2023.01.16 |
|---|---|
| 선형대수학 - 행렬식 1 (1) | 2023.01.11 |
| 선형대수학 - 연립선형방정식 1 (0) | 2022.12.21 |
| 선형대수학 - 역행렬 (0) | 2022.12.19 |
| 선형대수학 - 행렬의 계수 (0) | 2022.12.17 |
