[선형대수학] Row Reduction and Echelon Forms
Row Reduction and Echelon Forms
저번 포스팅에서 Linear System의 Existence와 Uniqueness에 대한 정의만 내렸었다. 이번에는 그것들을 어떻게 분석하고 조사하는지 알아볼 예정이다.
Echelon Forms
Rectangular Matrix가 Echelon Form을 만족하려면 다음 세 가지 Properties를 만족해야 한다.
- 모든 0이 아닌 row들은 0인 row 위에 존재해야 한다.
- 각 Row의 Leading Entry는 위의 Row보다 Column기준 오른쪽에 존재해야 한다.
- 모든 Leading Entry들의 아래에 존재하는 Entry들은 0이어야 한다.
- Leading Entry가 모두 1이다. (0이 아닌 Row에 대하여)
- 1인 Leading Entry가 속해 있는 Column에서 유일하게 0이 아니어야 한다.
4, 5번까지 만족한다면, Reduced Echelon Form이라고 한다.
위의 예시는 Echelon Form의 예시이다. ■은 Leading Entry를 의미하고 0이 아닌 값이다. *는 Starred Entries로 아무 값이나 가능하다.
위의 예시는 Reduce Echelon Form이다. Leading Entry가 모두 1이고 그 위의 값들은 모두 0으로 채워져 있다.
이를 통해 Matrix의 Uniqueness를 확인하려면, Matrix가 하나의 Matrix에 대해서 Row Equivalent 하고 Reduced Echelon Matrix가 한 개만 존재해야 한다.
Pivot Positions
Reduced Echelon Matrix의 경우 Uniqueness가 보장되기 때문에 Leading Entry의 위치가 변하지 않는다. Pivot Positions는 Reduced Echelon Form에서 1의 값을 가지는 Leading Entry의 위치이고, Pivot Column은 Pivot Position이 존재하는 Column을 말한다. 다음 예시를 통해서 확인해보자. A라는 Matrix가 아래와 같이 있다.
이를 1번째 row와 4번째 row를 바꾼다. 그렇다면 1번째 row의 Leading Entry가 1로 되고 Pivot Position이 정해진다. 당연히 Pivot Column도 정의된다.
이제 아래 Row들에 있는 첫번째 entry 값들을 0으로 만들어준다. 그렇게 되면 두 번째 Row의 Pivot Position과 Pivot Column이 나오게 된다. 나중에 두 번째 row를 2로 나눠주기 때문에 1이 아니라고 해서 걱정할 필요 없다. 혹시나 0으로 만들어주는 과정을 모른다면 이전 포스팅을 읽고 오자.
그리고 이제 나머지 아래 값들도 0으로 만들어준다.
마지막으로 3, 4번째 Row를 바꿔준다. 그렇게 되면 아래와 같이 3번째 Row의 Pivot Position과 Pivot Column을 구할 수 있다. 일반적인 Form에서 ■은 Pivot Position을 의미한다.
결국 이를 정리하면 원래 A Matrix에서 Pivot Position과 Pivot Column을 정리할 수 있다.
The Row Reduction Algorithm
이 알고리즘은 총 4개의 단계로 이루어져 있고, 이를 시행하면 Echelon Form의 Matrix를 얻을 수 있다. 5번째 단계까지 진행하면 Reduced Echelon Form이 된다. 예시와 함께 각 단계를 정의해보도록 하자.
Step1. 가장 왼쪽의 0이 아닌 Column은 Pivot Column이다. Pivot Position은 가장 위의 위치이다.
Step2. Pivot Column에서 0이 아닌 값을 Pivot으로 선택한다. 필요한 경우 row를 이동시켜 Pivot Position에 위치시킨다. 여기서는 1번째 Row와 3번째 Row를 바꿔주었다.
Step3. Pivot 아래에 있는 값들을 모두 0으로 만들어주기 위해 Row Operation을 사용한다. 예제의 경우 2번째 Row에서 1번째 Row를 빼주면 된다.
Step4. Pivot Position이 존재하는 Row는 이제 무시해도 된다. 1~3단계를 반복하여 수정할 Nonzero Rows가 없도록 한다.
단계를 반복하면서 새로운 Pivot의 위치를 찾아낸다.
Step5. 가장 오른쪽에 있는 Pivot에서 시작하여 왼쪽으로 진행해 올라간다. Pivot 위에 있는 값들을 모두 0으로 만든다.
이렇게 진행하면 Reduced Echelon Form이 된다. 1~4 step을 Forward Phase, 5 step을 Backward Phase라고 한다.
Solutions of Linear Systems
Row Reduction Algorithm을 통해 우리는 Solution을 쉽게 구할 수 있다. 예시로 Reduced Echelon Form으로 변형한 Augmented Matrix를 보자.
변수 3개에 대한 Augmented Matrix이다. 이를 연립방정식으로 표현하면 아래와 같다.
x1과 x2는 Pivot Column에 속해있기 때문에 Basic Variables라고 한다. x3의 경우 Free Variable이라고 한다. Solution을 갖기 위해서는 Reduced Echelon Form에서 Free Variable을 통해 Basic Variable을 정의하면 된다.
x3 is free라는 것은 어떤 값이든 우리가 줄 수 있다는 것이다.
Parametric Descriptions of Solution Sets
우리는 위에서 x1과 x2가 Free Varable인 x3를 통해 정의되는 것을 보았다. 우리는 이것을 Parametric Description이라고 부른다. x3가 Parameter와 같은 역할을 하는 것이다. 그리고 이를 표현하기 위해서는 System이 consistent하고 Free Variable을 가져야 한다.
Back-Substitution
아래와 같은 연립방정식으로 예시를 들어보자. 아래 예시는 Echelon Form이지만 Reduced Echelon Form은 아니다.
컴퓨터 프로그램의 경우 우리가 흔히 아는 Reduced Echelon Form을 만드는 방법을 사용하는 것이 아니라 Back-Substitution을 이용하여 만든다. x4를 x5를 통해서 x4 = 4 + x5로 정의한다. 그리고 위에 있는 x4에 4 + x5를 대입하여 x4에 대한 값을 없애준다. 이렇게 되면 실수할 가능성도 적고 빠르게 계산할 수 있다.
Existence and Uniqueness Questions
Echelon Form은 Reduced Echelon Form보다 Solution을 구하기 적합한 형태는 아니다. 하지만 이를 통해 우리는 Existence와 Uniqueness를 구할 수 있다. 아래 예시를 살펴보자.
이 식은 앞에서 Pivot Position을 구하는 방법에서 나왔던 예시이다. 이를 Echelon Form으로 바꾸면 아래와 같은 결과가 나온다.
먼저 우리가 확인할 것은 x1, x2, x5는 Basic Variable이고, x3, x4는 Free Variable이다. 0 = 1 같은 성립할 수 없는 식은 존재하지 않기 때문에 Back-Substitution을 통해 Solution을 찾을 수 있다. 하지만 Solution의 Uniqueness는 보장되지 못한다. Free Variable이 있기 때문이다. Free Variable이 달라지면 Basic Variable이 같이 달라지고 고유한 Solution은 존재하지 못한다. 따라서 무수히 많은 Solution이 존재하는 것이다.
정리하면 Linear System은 Augmented Matrix의 가장 오른쪽 Column이 Pivot Column이 아니라면, 즉 Echelon Form에서 아래와 같은 Row가 존재하지 않는다면 Consistent라고 할 수 있다.
Linear System이 Consistent일 때, Free Variable이 존재하지 않으면 Unique Solution이고, 적어도 한 개의 Free Variable이 존재하면 무수히 많은 Solution이 존재하게 된다.
참고 문헌: Linear Algebra and Its Applications