[Linear Algebra] Lecture 2, 소거법, 후방 대입법 그리고 소거 행렬

지난 Lecture 1에선 선형 시스템에 관한 식을 만들고 이를 Row와 Column picture 두 가지 방법으로 해석해 보았다. 

이번 시간에 배울 내용은 시스템 A의 해를 구하기 위한 방법들을 배울 것이다. 상세한 내용은 아래와 같다. 

 

1. Elimination(소거법) -Success

                  - Failure

2. Back-substitution (후방 대입법)

3. Elimination matrices (소거 행렬)

4. Matrix multiplication (행렬 곱)

 

 

우리는 주어진 어떤 선형 시스템 A에 대한 해(solution)를 구해야 한다. 시스템의 해를 구하는 방법이 바로 소거법(Elimination)이다. 선형 대수를 다루는 모든 소프트웨어는 해를 구할 때 이 Elimination방법을 사용한다. Ex) MATLAB, Mathematica 등등

 

소거법 성공하면 우리는 그 시스템의 해를 구할 수 있고 대부분의 경우엔 성공한다. 

그렇다면 여기서 이러한 의문이 생길 수 있다. 

실패하는 경우는 언제일까? 또한 이 Elimination은 그 과정에서 어떻게 성공할 행렬과 실패할 행렬을 구분할까? 

우리는 이번 포스팅에서 위 물음에 대한 경우를 살펴볼 것이다. 

 

소거법을 적용한 이후 우리는 해의 실제 값을 구하기 위해 후방대입법(Back-substitution)을 공부할 것이다. 이건 사실 간단한 연산이다. 

 

사실 시스템의 해를 구하기 위한 소거법(Elimination)에 대한 아이디어는 위대한 천재 수학자 가우스(Gauss)님께서 아주 자연스럽게 생각해 낸 것이다...(미천한 중생들을 구제해 주신건지 아님 시련을 주신건지 ㅋㅋ)

 

이러한 소거과정은 행렬형태(Matrix form)로 표현이 되며 이 부분을 유심히 살펴봐야 한다. 즉 소거법 연산이 행렬형태로 이루어 지는데 이때 사용되는 것이 바로 소거행렬(Elimination matrices)이다. 

선형대수는 기본적으로 행렬 연산을 통해 이루어 지며 또한 컴퓨터를 이용해서 연산을 수행해야 하기 때문에 어떤 식으로 소거과정이 행렬 형태로 표현되고 또 행렬 연산이 어떤 형태로 이루어지는지를 잘 살펴봐야 한다. 

 

 

 

1. 소거법(Elimination)

 - Success case

 

아래의 식은 3개의 방정식과 3개의 미지수로 구성된 시스템 식이다. 

 

 

(2)의 행렬 A는 위 시스템식에서 방정식의 계수들만 나열하여 만든 시스템 행렬(System matrix)이다. 해를 구하는 과정은 모두 시스템 행렬 A를 이용하여 이루어진다. 

참고로 행렬 요소들의 index는 식(3)과 같은데, 각 요소의 아래 첨자 숫자에서 첫 번째 숫자는 Row의 index를, 두 번째 숫자는 Column의 index를 의미한다. 즉 $e_{12}$라고 하면 첫 번째 행(Row1), 두 번째 열(Column2)의 요소인 2를 의미한다. 

 

 

 

자 그럼 이제 행렬 A에 대한 해를 구하기 위해 소거를 진행해야 할 텐데.. 어디서 부터 어떻게 소거를 해야할까? 

기본적으로 소거는 왼쪽에서 오른쪽으로, 위에서 아래 방향으로 진행한다. 즉 Row1 -> Row3방향, Col1 -> Col3방향으로 소거가 진행이 된다. 

 

소거는 기본적으로 다음의 방식을 따른다. 

 

기준이 되는 식에 적당한 상수를 곱하고, 제거하고자 하는 항이 있는 식에서 이를 빼준다. 

 

글로는 잘 이해가 안 될 것이다. 우선 식(1)을 살펴보자. 

총 3개의 식 중에 우선 첫 번째식 x+2y+z=2는 항상 소거에서 제외한다. 2번째 식부터 소거 대상이 되는데, 위의 말대로 식을 쓰자면 두 번째 식 3x+8y+z=12에서 첫 번째 식 x+2y+z=2에 어떤 상수를 곱한 다음 빼주는 것이다. 즉,

 

 

식(4)의 결과값은 소거하려는 Row, 즉 여기에선 두 번째 Row에 대입한다. 

 

그럼 여기서 적당한 상수라는 것은 어떤 값일까? 이를 위해선 없애려는 것이 정확히 무엇인지를 파악해야 한다. 여기서 우리의 목적은 두 번째 식 3x+8y+z=12 에서 x항인 3x를 없애는 것이다. 제거하려는 범위가 일단 x로 한정되는 것이다. 그렇다면 그 상수값 alpha는 3이 될 것이다. 

이때 없애고자 하는 텀의 중심축이 되는 원소를 우리는 피벗(Pivot)이라 부른다. 아래 식에서 피벗은 $e_{11}$가 될 것이다. 이 pivot을 기준으로 그 아래에 있는 텀을 없애는 것이다. 

 

 

위의 식에서 첫 번째 Row에 3을 곱하고 두 번째 식에서 이를 빼준 값을 두 번째 식에 대입하면 (5)의 오른쪽과 같이 될 것이다. 

다음 단계는 어디를 소거해야할까? pivot을 중심으로 그 아래쪽에 해당하는 모든 텀들을 소거해야 한다. 즉 다음으로 소거해야 할 원소는 $e_{31}$이다. 그러나 $e_{31}$은 이미 0이기 때문에 이 단계는 넘어가도 괜찮다. 그러나 MATLAB등 프로그램에서 실제로 구현될 때는 기준 값과 제거해야할 값을 보고 pivot의 식에 0을 곱한다음 마지막 방정식에서 빼주는 작업이 이루어 진다. 

 

이제 시스템 행렬 A에선 x에 관한 텀들이 모두 제거되었다. 이제 남은 것은 y와 z축에 대한 텀들이다. 

다음 pivot은 y축 column중에 결정해야 한다. 만약 첫 번째 Row와 두 번째 Column인 $e_{12}$를 pivot으로 잡는다면 애써 없앤 x텀이 되살아날 것이다. 따라서 두 번째 pivot은 $e_{22}$가 되어야 한다. 

 

 

 

 

자 이제 소거가 모두 완료 되었다. 식(6)의 소거가 완료된 행렬을 우리는 u라고 명한다. 자세히 보면 그 형태가 pivot들을 기준으로 아래쪽에는 원소값이 모두 0인 상삼각행렬(Upper triangular Matrix)이다. 

 

 

 

결국 소거법의 최종 목표는 시스템행렬 A를 u로 만드는 것에 있다. 식(7)은 우리가 찾은 모든 pivot들을 나타내었다. 마지막 원소도 pivot이다. 여기서 한 가지 짚고 넘어가야 할 중요한 점이 있다. 0인 원소는 pivot이 될 수 없다. 위의 경우 모든 pivot원소들이 0이 아니기 때문에 알고리즘의 규칙대로만 수행하면 됐지만 pivot의 값이 0인 경우엔 조금 달라진다. 자세한 사항은 후에 알아보는 시간을 갖도록 하자. 

 

 

 

 

 

 - Failure case

 

이번에는 소거법이 실패하는 경우를 살펴보자. 어떤 경우에 소거가 실패할까? 

일단 pivot이 0인 경우 소거법 적용이 불가능하다. 이유는 첫 번째 pivot의 식에 어떤 상수를 곱해도 x텀은 0이다. 따라서 두 번째 Row의 x원소가 0이 아닌 이상 소거가 불가능하다. 

또 한가지 경우는 x텀을 소거하기위해 상수를 곱하고 뺐는데 y텀까지 소거가 되는 경우가 있다. 

 

 

pivot이 0인 경우 소거가 불가능하다..

 

 

그렇다면 이러한 경우 절대로 소거법 적용이 불가능할까? 이대로 포기해야만 할까? 

방법은 있다. 바로 0이 아닌 pivot의 방정식과 식을 교환하는 것이다. 아래 식을 살펴보자. 

 

 

 

식(9)의 가운데 행렬에서 두 번째 Row의 pivot이 0이 되었다. 앞서 말했듯 이 경우는 Failure case이다. 하지만 세 번째 Row의 y텀이 0이 아니기 때문에 Row를 교환하여 소거가 가능한 형태로 만들 수 있다. 

 

결과적으로 pivot이 0이기 때문에 소거가 불가능한 경우 우리는 Row exchange를 통해 소거가 가능하도록 만들 수 있다. 단  다음 방정식의 pivot column의 값이 0이 아닐 경우에만 가능하다. 

 

다음과 같은 경우도 있다. 시스템 A의 세 번째 Row의 식이 4y-4z=2 일 경우 소거법을 거쳐 최종적으로는 마지막 u 행렬의 z column pivot이 0이 된다. 이 경우 시스템 A는 not-invertible 한 행렬이 된다. 

 

 

이상으로 u matrix를 만들기 위한 소거법에서 Failure case를 만들어 보았다. Failure case에는 크게 두 가지가 있다. 

첫 번째는 극복이 가능한 temporary failure이다. 소거 과정에서 pivot이 0인 경우 발생하는데 그 다음 방정식의 pivot 라인의 원소가 0이 아닌 경우 Row exchange를 통하여 해결할 수 있다. 

두 번째는 극복이 불가능한 complete failure이다. pivot=0인 상황에서 그 다음에 교체할 만한 방정식이 존재하지 않는 경우이다. 

 

 

 

2. 후방대입법(Back-substitution)

 

다음으로 알아볼 것은 후방대입법(Back-substitution)이다. 지금까지 우리는 시스템 Ax=b에서 A만을 이용해 소거법을 적용했다. 그러나 사실 b까지 고려하여 소거법을 적용해야 한다. MATLAB등과 같은 프로그램에서는 소거법을 적용할 때 시스템 행렬 A에 대한 소거를 먼저 수행하고 b는 이후에 따로 분리하여 수행한다. 

 

자 이제 후방 대입법을 이해하기 위해 b까지 함께 고려한 소거법을 살펴볼 차례이다. 행렬 (2)를 b와 함께 다시 써보자. 

 

 

 

위와 같은 행렬을 우리는 Augmented matrix라 부른다. 부가적인 column인 b를 붙였다는 의미다. 여기서 b는 extra column이다. 

이 상태에서 시스템 A에 대해 소거법을 적용할 때 우리는 양변에 똑같은 작업을 동시에 수행해야 한다. 식(11)에 소거법을 적용한 예를 살펴보자.

 

 

시스템 행렬 A에 column b를 붙여 u와 column c를 만들어낼 수 있다. b로부터 소거법을 적용해 만든 column을 우리는 c라고 부른다. 

소거하여 만든 결과식 u와 c를 다시 방정식 ux=c형태로 써보자. (13)과 같이 될 것이다. 

 

 

이제 후방대입법(back-substitution)을 적용해서 해를 구해보자. 후방대입법이란 말 그대로 아래쪽 변수, 즉 z텀만 남아있는 세 번째 Row방정식에서부터 해를 풀어나가는 것이다. 이것이 가능한 이유는 우리가 상삼각행렬(Upper triangular)의 형태로 방정식을 만들어서 마지막 방정식은 미지수가 하나이기 때문에 쉽게 답을 알 수 있기 때문이다. 

 

아래쪽부터 z=-2인 것을 쉽게 알 수 있고, 두 번째 방정식엔 앞서 구한 z=-2를 대입해 y를 구하고 그 다음 첫 번째 식에 앞서 구한 y,z를 대입해 x를 푸는 것이다. 위 시스템의 해는 x=2 y=1, z=-2 가 된다. 

 

 

 

 

 

3. 소거행렬과 행렬곱셈(Elimination matrices and Matrix multiplication)

 

우리는 앞서 소거법 과정을 시스템 행렬A와 column b에 직접 나타냈다. 이번 파트에서는 이 작업을 행렬 형태로 표현할 것이다. 

즉 소거 행렬(Elimination Matrices)을 만들고 이를 시스템 행렬 A에 곱해서 소거법을 적용하는 것이다. 이러한 행렬 곱(Matrix multiplication)의 과정을 이해하면 조금 더 큰 그림을 볼 수 있다. 소거행렬을 만들기 전에 우선 지난 강의에서 배웠던 것을 상기시켜보자. 

 

우리는 지난 강의에서 Row picture와 Column picture를 배웠다. 여기서 특히 column picture가 중요하다고 강조했고 이는 미지수벡터와 행렬의 column의 선형 결합(Linear combination)이라 배웠다. 이 내용을 기억하며 다음을 보자. 

 

 

식(14)는 행렬 A와 벡터 x와의 곱을 나타낸다. 우리가 중고등학교때 배웠던 방식으로 행렬 곱을 볼 수도 있지만, 오른쪽과 같이 행렬의 column들과 벡터 원소간의 선형결합으로 볼 수도 있다. Matrix * column = column임을 기억하라. 

 

그러나 여기서 강조하고 싶은 것은 Column의 선형결합과 마찬가지로 유사한 Row의 선형결합이다. 지금까지 강의에서의 연산 대부분이 Row 연산이었기 때문에 Row의 선형결합을 이해하는 것은 중요하다. 

행 연산(Row operation)을 살펴보자. 

 

 

 

(※참고: 행렬과 벡터, 행렬과 행렬, 벡터와 벡터 끼리의 연산을 할 때 가운데 이어지는 차원이 반드시 같아야 하며 최종 결과는 양쪽 끝 숫자의 차원의 결과가 나온다. 위 그림 참조)

 

Row 벡터와 matrix의 곱은 Row의 선형결합으로 생각할 수 있다. Row벡터의 첫 번째 원소는 행렬의 첫 번째 Row와 곱해지고 나머지도 같은 방식으로 연산이 이루어진다. Column의 선형결합을 떠올리며 이 매커니즘을 잘 이해하자. 

 

 

- Step1: 

 

자 이제 소거를 위한 소거행렬을 만들어보자. 소거행렬이란 앞서 했던 소거과정을 행렬의 곱으로써 만들어내는 것이다. 그렇다면 아래 식 왼쪽의 소거행렬(Elimination matrix)에는 어떤 값들이 들어가야할까? 

(※참고: 식(16)의 소거행렬을 E21이라 칭한 이유는 E는 Elementary or Elimination에서 따오고, 21은 A의 Row2, Col1을 0으로 만드는 것이 목적이기 때문)

 

 

첫 번째로 소거해야할 Row는 두 번째 Row이다. 즉 $\text{Row2}=\text{Row2}-\alpha \; \text{Row1}$ 이고 $\alpha=3$이다. 이때 첫 번째와 세 번째 Row는 그대로 유지되어야 한다. 

 

앞서 배웠던 Row의 선형결합을 생각해보자. Matrix1 x Matrix2는 Row의 선형결합으로 표현할 수 있다. 

우선 식(16)의 A의 Row1을 그대로 유지시키려면 E21행렬의 Row1엔 어떤 벡터가 들어가야 할까? 정답은 [1 0 0]이다. 이를 어떻게 생각해낼 수 있을까? 바로 Row의 선형결합을 이용하면 된다. 아래 식을 보자. 

 

 

위 그림처럼 Row의 선형결합을 떠올리면 E21의 Row1의 첫 번째 원소는 A의 Row1과 곱해지고 두 번째 원소는 A의 Row2와, 그리고 나머지도 이와 같은 순서로 곱해진다. 따라서 E21의 Row1의 첫 번째 원소만 1로 설정하고 나머지 원소는 0으로 두면 될 것이라는 생각을 할 수 있다. 

 

그렇다면 A의 Row3을 그대로 유지시키려면 E21의 Row3을 어떻게 설정하면 될까? 바로 [0 0 1]이라고 생각할 수 있을 것이다. 지금까지 설정한 결과는 아래와 같을 것이다. 

 

 

자 그럼 E21의 Row2에는 어떤 값이 들어가야할까? 앞서 말했듯 A의 Row1에 3을 곱하고 Row2에서 이를 빼주면 된다. 이때 Row3은 아무런 역할을 하지 않아도 된다. 그렇다면 Row 선형결합으로부터 [-3 1 0]으로 설정하면 해당 연산을 수행할 수 있을 것이다. 최종적인 E21 행렬은 식 (19)와 같이 된다. 

 

 

 

 

 

- Step2: 

 

다음 단계는 A의 Row3의 y축 원소를 소거해야한다. 

식(19)의 결과 행렬에서 Row3, Col2의 원소인 4을 소거해야한다. 어떻게해야할까? 위의 내용을 잘 이해했다면 Row3에서 Row2에 2를 곱한 값을 빼주는 되는 것을 쉽게 알 수 있을 것이다. 즉 Row3 - 2*Row2 이다. 

 

일단 소거행렬 E를 만들어야 하는데, 아래 첨자 인덱스는 어떤 값이어야할까? 바로 $E_{32}$이다. A'행렬의 Row3과 Row2의 원소를 0으로 만드는 것이 목적이기 때문이다. 

 

그렇다면 두 번째 단계의 소거행렬인 E행렬은 어떻게 값이 설정되어야할까? 우선 Row1과 Row2는 그대로 유지되어야 한다. 그렇다면 앞서 배운것과 같이 E32행렬의 첫 번째와 두 번째 Row를 각각 [1 0 0], [0 1 0]으로 만들면 될 것이다. 

그럼 마지막 E32의 세 번째 Row는? 

 

일단 A'의 첫 번째 Row는 아무런 역할을 하지 않기에 0으로, 

두 번째는 2를 곱해서 빼줘야 하기 때문에 -2, 

마지막 세 번째 Row는 1로 설정해주면 된다. 즉 [0 -2 1]이다. 

결과적으로 식은 아래와 같이 될 것이다. 

 

 

여기서 한 가지 짚고 넘어가야 할 부분이 있다. E21과 E32등 소거 행렬은 u를 만들기위해 각 단계별로 행렬 A에 작용했다. 

지금까지의 단계를 수식으로 표현하면 아래와 같다. 

최초의 시스템 행렬 A에 E21이 곱해지고, 그 결과에 다시 E32가 왼쪽에 곱해지면 최종적으로 u행렬이 만들어지는 것이다. 참고로 행렬이 identity matrix(단위 행렬)가 아닌 이상 왼쪽에 곱해지는 것과 오른쪽에 곱해지는 것의 결과는 전혀 다르다. 

 

그렇다면 이를 좀 더 간결하게 표현할 수는 없을까? A의 왼쪽에 곱해지는 E소거행렬들을 하나로 표현할 순 없을까? 

식(21)의 오른쪽처럼 소거행렬들을 먼저 곱하고 이 결과를 A의 왼쪽에 곱해주면 결과는 같아진다. 즉 단계별로 나뉘어진 소거행렬들끼리 먼저 곱하여 하나의 소거행렬을 만들고, 이를 A에 곱해줄 경우 단번에 u행렬이 만들어지는 것이다. 

다시말하면 행렬끼리의 곱셈은 교환법칙(Commutative Law)은 성립하지 않지만, 결합법칙(Associative Law)이 성립하기 때문에 순서가 바뀌지 않는다면 어떻게 묶어서 곱하던 결과가 같다. 

결과적으로 소거행렬을 묶어서 우리는 E라고 표현한다. 

 

 

 

- Another type of matrix: Permutation Matrix

 

여기서 한 가지 다른 형태의 행렬을 소개할까 한다. 지금 당장에 필요한 것은 아니지만 사실 소거 연산 자체에는 필요한 경우가 있다. 바로 치환행렬(Permutation Matrix)이다. 이 행렬의 역할은 이름이 의미하듯 행렬의 행(row)이나 열(column)을 바꾸는 역할을 한다. 생김새는 Identity Matrix를 뒤집거나 행이나 열을 바꾼 형태이다. 

아래 행렬을 보자. 

 

식(22)처럼 A의 Row를 서로 바꾸기 위해선 P의 값이 어떻게 설정되어야할까? Row 선형결합을 생각하면 아래와 같이 설정해야한다는 것을 알 수 있다. Row 선형결합 방식으로 실제로 연산을 수행해보자. (※식(17)참조)

 

 

위 식은 Row를 교환하는 연산을 수행하는 행렬이다. 그렇다면 Column을 교환하고 싶을 땐 어떤 행렬을 곱해야할까? 

식(22)에서는 P행렬을 A의 왼쪽에 곱하여 Row exchange를 했다. Column exchange를 하기 위해선? P행렬을 A의 오른쪽에 곱해주면 된다. (※식(14)참조)

 

 

 

Column 연산을 수행하려면 행렬을 오른쪽(Right)에 곱하고

Row 연산을 수행하려면 행렬을 왼쪽(Left)에 곱해주면 된다. 

 

우리는 결론적으로 위의 Row, Column exchange연산을 통해 행렬의 곱은 곱하는 위치가 바뀌면 안된다는 것을 알 수 있다. 즉 행렬의 곱에 있어서 교환법칙(Commutative Law)은 성립하지 않는다는 것을 본 예를 통해 알 수 있었다. 

 

 

 

마치며..

 

우리는 Lecture 2에서 소거법을 통해 시스템 행렬 A를 상삼각행렬 형태의 u로 만들고 후방대입법을 통해 해를 구하는 법을 배웠다. 또한 행렬곱셈 연산에 대하여 공부하였고 치환행렬과 Row operation, Column operation등을 공부하였다. 

다음 강의에서 배울 내용은 A->u를 만드는 행렬에서 역으로 u->A를 만드는 역행렬에 관한 내용이다. 

 

이상으로 Lecture 2를 마칩니다.