[Linear Algebra] Lecture 7 Null Space계산 알고리즘. Ax=0과 Pivot variable 그리고 Free variable
우리는 지난 포스팅에서 영공간(Null Space)에 대해 공부하였다. 또한 벡터 공간(Vector Space)과 임의의 행렬 A의 Column space에 대해서도 공부하였다. 이번 포스팅에선 Null space를 구하는 절차, 즉 Ax=0의 해를 구하기 위한 알고리즘(algorithm)을 공부해 보도록 하겠다. 또한 특별한 형태의 솔루션인 기약행 사다리꼴(Reduced row-echelon form)에 대해서도 공부해 보도록 하겠다.
지난 포스팅에서 배웠듯이 Null space는 Ax=b의 선형방정식(Linear equation)에서 우변의 b가 영벡터(zero vector)일 때, 즉 Ax=0의 해에 대한 집합을 의미한다. 이 Null space는 벡터 공간이며 또한 부분 공간(subspace)이기도 하다. 벡터 공간에 대한 강의(Lecture 5, 6)내용을 잘 이해하도록 하자.
1. Ax=0의 해(Null space)를 계산하기 위한 알고리즘
3x4크기의 직사각 행렬(Rectangular Matrix) A를 아래와 같이 정의하자. 행렬 A의 row와 column을 자세히 살펴보자. 뭔가 특이점이 보이는가? 앞선 포스팅의 내용을 성실히 공부했다면 특이점이 보일 것이다.
우선 A의 column을 살펴보자. column 2는 column 1의 2배에 해당하는 것을 눈치 챘는가? 즉 column 1과 column 2는 같은 방향을 나타내므로 상호 종속적이다(dependent).
다음은 row를 살펴보자. row 1과 row 2를 더하면 row 3가 된다. 따라서 row 3는 독립적이지 않다(not independent).
우리가 이렇게 눈으로 찾은 행렬 A의 특이점들은 A의 소거(Elimination) 과정에서 나타날 것이다. 우리는 지난 포스팅에서 소거법에 대해 공부했다. 지금까지의 소거법은 정방행렬(square matrix)에 대해서만 공부하였지만, 이번에는 직사각 행렬(Rectangular matrix)에 대해 진행할 것이다. 또한 소거 과정에서 pivot의 위치에 0이 나왔을 때 어떻게 진행하는지에 대해서도 알아보자.
다시 한 번 정리하자면 지금 우리의 목표는 Ax=0의 해, 즉 Null space를 구하는 것이다. 이 Null space를 구하는 방법은 행렬 A를 소거(Elimination)하는 것이다. 여기서 중요한 포인트는 소거를 하는 과정에서 우리는 Null space를 변화시키지 않는다는 것이다. 소거 과정에서 사실은 column space는 바꾸겠지만 결과적으로 봤을 때 그 과정에서 해의 집합인 Null space는 바뀌지 않는다.
Ax=0의 방정식을 봤을 때 Null space라는 것은 좌변의 A행렬과 우변의 영벡터 b에 대한 방정식을 만족시켜야만 하는 해의 집합인 것이다. 따라서 소거 과정에서 행렬 A의 column space는 변할 수 있으나 본래의 A와 영벡터 b에 대한 방정식을 만족시키는 해의 집합 자체는 변하지 않는 것이다.
지금 당장은 이 말이 잘 이해가 가지 않겠지만 앞으로의 과정을 잘 살펴보고 이 말을 다시 한 번 생각해보자.
자 이제 소거를 시작해보자.
A의 첫 번째 pivot은 1이다. pivot 바로 아래의 원소인 A(row2, col1)=2를 소거해야 하므로 row2 = row2 - 2*row1 를 계산하면 식 (2)의 step1과 같이 된다. row3도 역시 소거를 하려면 row3 = row3 - 3*row1 를 계산하면 step2와 같이 된다.
이것이 소거 과정의 첫 번째 stage다. 첫 번째 pivot의 아래에 있는 원소는 모두 0으로 만들어 소거하였다. 이제 다음 stage인 column 2를 살펴보자. 원래 같았으면 두 번째 pivot은 A(row2, col2)인데, 식(3)과 같이 값이 0이다. Lecture 2에서 배웠듯이 0인 원소는 pivot이 될 수 없다.
만약 이 두 번째 pivot의 아래의 원소 A(row3, col2)가 0이 아닌 값을 가진다면 행 교환(row exchange)을 통해 pivot값을 바꿔서 설정해주면 된다. 그러나 이 역시 0이기 때문에 결과적으로 column 2에서의 소거는 더이상 진행되지 않는다. 즉 두 번째 pivot은 column 2에 없다.
이것이 의미하는 것이 무엇일까? column 2에 원래 존재해야 할 pivot이 없는 이유는 무엇일까? 바로 A의 column 2는 column 1에 종속적(dependent)이기 때문이다. 식 (2)의 행렬 A를 보면 col1의 2배가 col2인 것을 알 수 있다. 즉 두 column이 같은 선상에 위치한다는 의미이다.
여기서 멈추지 않고 이제 세 번째 column을 보자. 세 번째 column의 두 번째 row부터는 0이 아닌 값이 존재한다. 결국 두 번째 pivot은 A(row2, col3)=2가 될 것이다. 두 번째 pivot을 기준으로 아래의 원소들을 0으로 만들자. 이때 아래의 row3와 pivot이 있는 row2는 같다. 따라서 row3=row3-1*row2가 될 것이다. 결과는 식 (4)의 step1이 된다.
이제 소거는 모두 끝났다. 결국 이 행렬이 U행렬인데, 알다시피 U행렬은 상삼각행렬(Upper triangular matrix)를 의미한다. 그러나 이 결과 행렬은 삼각형 모양이 아니라 계단 형태이다. 이를 echelon form이라 한다.
여기서 우리는 행렬 A에 대한 굉장히 중요한 숫자 한 가지를 발견했다. 바로 "pivot의 개수(number of pivots)"이다. 소거를 통해 알아낸 행렬 A의 pivot의 개수는 2이다. pivot 개수 2가 의미하는게 무엇일까? 바로 행렬 A의 Rank이다.
행렬 A의 Rank는 2이다.
임의의 행렬 A에 대해 U행렬을 얻기 위해 행렬 A를 소거(Elimination)한다. 소거 과정에서 pivot의 개수를 알아낼 수 있는데 이때 pivot의 개수가 바로 행렬 A의 Rank이다. Rank는 시스템 행렬 A의 선형 독립(Linearly independent)인 row혹은 column vector의 수를 나타낸다. 이 Rank는 소거 과정에서 나타나는 pivot의 개수와 일치한다. Rank of A = number of pivots |
우리는 지금까지 Ax=0에 대한 해를 구하고자 했다. 그런데 이번에는 위에서 계산한 식(4)의 A를 소거한 행렬인 U에 대한 해, 즉 Ux=0를 구하고자한다. 여기서 한 가지 염두해둬야 할 것은 Ax=0와 Ux=0의 해가 똑같은 Null space에 존재한다는 것이다. A를 소거하여 만든 행렬 U는 비록 A와 비교했을 때 column space는 변했겠지만 해는 동일한 Null space에 존재한다. 이것이 앞단에서 말했던 소거과정에서 Null space는 바뀌지 않는다는 것이다.
결국 Ax=0와 Ux=0의 해는 같은 Null space이다.
그렇다면 Ux=0의 해는 어떻게 기술할 수 있을까? 물론 Ax=0를 계산할때와 같이 해는 존재하겠지만 이 경우엔 조금 다른 관점으로 바라봐야한다. 이를 위해 제목에서도 나와있듯이 이번 포스팅에서 중요한 것 중 하나인 pivot variable과 free variable에 대해서 공부해보겠다. 우선 아까 계산한 U행렬을 다시 보자.
U행렬에서 우리는 pivot column과 free column을 찾아야한다. 소거 과정에서 찾았던 pivot이 있는 column이 pivot column이고, 이를 제외한 나머지 column이 free column이다.
그렇다면 여기에 왜 free라는 단어를 사용했을까? 이는 우리가 Ux=0의 해를 구할 때 free column에 대응되는 변수에 우리가 원하는 임의의 값을 자유롭게 설정할 수 있기 때문이다. 식(5)에서 free column은 2번째와 4번째이므로 solution 벡터 x에서 column2와 column4에 각각 곱해지는 x2와 x4는 우리가 원하는 값으로 설정할 수 있다. 그런 다음 x1과 x3에 대해 해를 구하면 된다. 이해가 잘 안갈테니 바로 예를 들어 설명해보자.
아래는 Ux=0에서 해(solution) x벡터를 나타낸다. 앞서 말했듯이 x2와 x4에 임의의 값을 설정해보자. 일단 계산하기 가장 편리하도록 x2=1, x4=0으로 설정해보자. 100이던 -3891이던 어떤 값을 넣어도 상관없다.
x의 free variable값을 설정했으니 이제 Ux=0에 대해서 풀어보자. 행렬로 자세히 풀어서 표현하면 아래 식 (7)과 같다.
식 (7)을 다시 방정식으로 표현해보자. U의 row3는 모두 0이기 때문에 제외하면 총 2개의 방정식을 가진다. U의 row1과 row2를 각각 방정식으로 정리하면..
x2와 x4는 1과 0으로 각각 설정해서 값을 알고 있다. 나머지 x1과 x3는 Lecture 2에서 배웠던 후방대입법(Back substitution)을 통해 값을 찾을 수 있다. 이제 값을 찾아보자.
x2=1, x4=0일 때, x3는 값이 얼마인가? 식 (8)의 두 번째 식에 후방대입법을 통해 x3=0임을 알 수 있다. 이제 x2=1, x3=0, x4=0이 되었다. 그렇다면 x1은 얼마인가? x1=-2임을 쉽게 계산할 수 있다. x를 다시 써보면..
이 x가 바로 Ux=0의 해(solution)이며 Null space이다. 또한 Ax=0의 해 이기도 하다. Ux=0와 Ax=0에서 위 x의 의미는 각 행렬에서 -2*col1 + 1*col2 = 0를 의미한다. 즉 column picture형식으로(Lecture 2) 정리하면 아래와 같다.
Ux=0에서 구한 해 x를 Ax=0에도 똑같이 적용해도 식이 성립하는것을 볼 수 있다. 따라서 맨 처음 말했던 column space는 바뀔지언정 해(solution)인 Null space이는 변하지 않는다는 말이 이제 조금 이해가 될 것이다.
- More solutions in Null space:
우리는 앞서 A와 U에 대한 해 x를 찾았다. 이 해는 Null space에 있다. 따라서 한 개가 아닐 것이다. 그렇다면 나머지 해들은 어떻게 찾을까? 바로 임의의 상수 c를 x에 곱해주면 된다. 식은 아래와 같이 될 것이다.
임의의 상수 c가 곱해진 해 x는 4차원 공간 R4에서 무한대의 2차원 line을 표현한다. 이때 x는 분명 Null space상에 존재한다. 이와 관련해 아래 물음을 한 번 생각해보자.
그렇다면 위의 식(12)에 있는 x는 A와 U에 대한 모든 Null space를 나타낼까?
정답은 No다.
우리는 이 시스템에서 2개의 free variable을 가지고 있다. 즉 x2와 x4가 free variable인데, 우리는 x2=1, x4=0으로 결정했을 때의 해를 구한 것이다. 다른 free variable을 선택했을 때의 해를 한 번 구해보자. 역시 어떠한 값을 적용해도 상관 없지만 계산을 쉽게 하기 위해 x2=0, x4=1을 대입해보도록 하겠다.
위와 같이 값을 설정하고 아까의 후방대입법(back substitution)과정을 반복하면 된다. 식 (8)에 나타난 방정식을 아래와 같이 다시 써보자.
후방대입법으로 계산하면 x3=-2, x1=2가 됨을 알 수 있다. x를 정리하면 아래와 같다.
이 x가 선형방정식에서 의미하는 것은 2*col1+0*col2-2*col3+1*col4이다. U와 A의 방정식에 각각 대입하여 계산해보면 성립하는 것을 알 수 있다.
자 이렇게 해서 우리는 Null space상에 존재하는 두 개의 해 (12)와 (15)를 구했다. 이 두 개의 해는 임의의 free variable을 설정하여 구한 해(solution)이며 이를 special solution이라 한다. 보통 special solution을 계산할 때는 첫 번재 free variable을 1로 놓고 나머지는 0, 그 다음은 두 번재 free variable만 1로 놓고 나머지는 0으로 설정하는 식으로 계산한다. 식 (15)의 x에 관련된 나머지 해들도 역시 여기에 임의의 상수를 곱해주면 구할 수 있다.
임의의 상수 d를 직접 곱했을 때에도 식이 성립하는지 각자 확인해보자.
우리는 식 (12)와 (18)에 나타난 두 개의 해를 가졌다. 각각은 Null space상에 존재하고, 이들은 임의의 free variable을 설정하여 만들어진 해들이다. 이제 우리는 이 두 개의 해의 선형 결합(Linear combination)을 통해 전체 Null space를 정의할 수 있다.
그렇다면 이 special solution은 얼마나 존재하는 걸까? 이는 각 free variable마다 존재한다. 그럼 free variable은 얼마나 존재하는 걸까?
우리는 앞서 행렬 A의 rank가 2이고 rank는 pivot variable의 수임을 배웠다. pivot variable의 수는 m(rows) x n(columns)행렬에서 column의 수인 n에 대해서 정의된다. 즉 n개의 column중에 pivot이 어느 column에 설정되는지를 보는 것이다. 그렇다면 free variable은 pivot을 뺀 나머지 column의 수가 될 것이다. 즉 column의 수에서 rank의 수를 뺀 것과 같다.
column의 수 4에서 rank의 수 2를 뺀 2가 최종적인 free variable의 수가 된다. 조금 더 쉽게 설명하자면 다음과 같다.
| 행렬 U는 두 개의 free variable을 가지고 있고 한개의 free variable이 하나의 해(solution)에 대한 line을 표현 했다고 생각하자. 이때 우리는 두 개의 free variable을 가지고 있기에 총 두 개의 line을 가지고 있으며 이 두 라인의 선형 결합으로 하나의 평면(plane)이 행렬 A의 Null space 전체를 표현하는 것이다. |
지금까지 배운 알고리즘을 통해 우리는 임의의 행렬 A의 모든 Null space를 구할 수 있다.
2. 기약행 사다리꼴 행렬(Reduced row echelon form)
우리는 앞의 section에서 행렬 A를 소거하여 U를 만들었다. 이때의 U는 계단 형태를 보였고 이를 echelon형태임을 알았다. 이번 section에선 이 U행렬에대해 좀 더 알아보고 이를 더 간소화(소거) 시킨 형태인 기약행 사다리꼴 (Reduced row echelon form)을 만드는 법을 알아보도록 하자. 이는 쉽게 말해 어떤 행렬에 가우스 소거법(Gauss Elimination)을 적용했을 때 계단 모양이 나오며, 몇 가지 조건을 만족하는 행렬을 의미한다. 우선 U행렬의 식 (5)를 다시 보자.
U행렬을 잘 보면 세 번째 row가 전부 0인 것을 알 수 있다. 왜 row3는 0이 될까? 바로 소거 전의 행렬 A의 row3가 row1과 row2의 선형 결합이기 때문이다. 식 (1)을 보면 row3=row1+row2인 것을 볼 수 있다. 결국 row3가 row1과 row2에 종속적(dependent)이기 때문에 소거를 한 행렬 U의 세 번째 row가 0이 되는 것이다. 이러한 관계를 소거(Elimination)작업이 찾아내는 것이다.
자 이제 U행렬을 다시 한 번 간소화 해보도록 하자. 어떻게 하면 될까? Lecture 3에서 배웠던 Gauss-Jordan소거법을 기억하는가? 이와 같이 이번엔 아래에서 위쪽으로 소거를 진행하는 것이다. 그럼 어느 부분을 소거해야할까? 역방향(위쪽)으로 소거를 진행할 땐 pivot원소의 위쪽에 있는 원소들을 소거하는 것이다. 즉 기약행 사다리꼴 행렬(Reduced row echelon form matrix)은 pivot 원소들의 아래, 위로 모두 0이 되어야 한다. 이제 U행렬을 한 번 소거해서 기약행 사다리꼴로 만들어보자.
바로 위의 식 (5)에서 pivot 원소가 두 개 존재한다. 첫 번째 pivot(row1, col1)은 아래 위로 모두 원소가 0이다. 그러나 두 번째 pivot(row2, col3)은 위쪽 원소(row1, col3)가 2이다. 따라서 이를 소거해줘야한다. 소거 방법은 소거할 원소가 pivot과 같기 때문에 1을 곱해서 빼주면 된다. 즉 row1 = row1 - row2 와 같이 하면 된다. 결과는 아래와 같다.
여기서 기약행 사다리꼴이 되기 위한 한 가지 과정을 더 진행해보자. 바로 pivot원소들을 모두 1로 만드는 것이다. 첫 번째 pivot은 이미 1이므로 그대로 놔두고 두 번째 pivot을 1로 만들어보자. 방법은 그냥 간단하게 pivot이 있는 row전체를 pivot으로 나눠주면된다. 결과는 아래와 같다.
식 (22)의 마지막 행렬이 바로 기약행 사다리꼴 행렬(Reduced row echelon form matrix)인 R이다.
이 행렬은 MATLAB에서 rref(A)라는 명령어를 통해 계산할 수 있다. A는 계산하고자 하는 input 행렬이다.
결국 기약행 사다리꼴 행렬(Reduced row echelon form)이 되기 위해선 다음의 조건들을 만족해야 한다.
기약행 사다리꼴 행렬이기 위한 조건:
|
기약행 사다리꼴 행렬은 많은 정보들을 담고 있다. 어떤 정보들을 담고 있을까?
바로 알아볼 수 있는 정보로는 row1과 row2인 pivot row와 col1과 col3인 pivot column을 볼 수 있다. 또한 U행렬 내에 단위 행렬(identity matrix)를 담고 있다. 아래 식을 보자.
빨간색 box는 pivot row를, 파란색 box는 pivot column을 나타낸다. 이 둘이 겹쳐지는 부분을 보자. 2x2 크기의 단위 행렬의 모습이 보일 것이다. 이 단위행렬이 나타나는 당연한 이유는 우리는 행렬 A를 소거하는 과정에서 pivot variable의 위/아래의 모든 원소를 0으로 맞추었고, 모든 pivot을 1이 되도록 만들었다. 따라서 이러한 단위 행렬이 당연히 나타나게 된다.
자 이렇게 해서 우리는 처음에 A행렬에서 가우스 소거를 통해 U행렬을 만들었고, 여기에 한 번더 가우스 소거를 적용하여 R행렬을 만들었다. 즉 A->U->R로 변화한 것이다. 이를 정리해보면 아래와 같다.
우리는 A에서 U로 행렬을 변환한 뒤에도 Ax=0와 Ux=0의 해는 동일한 Null space에 존재함을 알았다. 그렇다면 U를 소거하여 만든 Rx=0의 해도 역시 동일한 Null space에 존재할까? 정답은 Yes이다. 앞서 구한 해를 R행렬에 적용하여 이를 확인해보자.
식 (24)를 보면 역시 Rx=0해도 동일한 Null space에 존재하는 것을 알 수 있다. 우리는 행렬을 A에서 R로 변화시켰다. 그 과정에서 비록 각 행렬의 column space는 변했을지 모르나 원래의 행렬에 대한 고유한 성질은 변하지 않았다. 그렇기에 해가 동일한 공간(Null space)에 존재하는 것이다. 우리는 단지 A행렬을 줄이고 줄이고 줄여서 가장 간단한 형태인 R로 만들었다고 생각하면 좋을 것 같다.
- Another example:
다른 행렬에 대한 Null space계산을 한 번 더 풀어보자. 임의의 행렬을 만들 수도 있으나 앞서 풀었던 A행렬을 전치(transpose)시킨 행렬을 가지고 계산해 보도록 하자. 중복된 내용이 많을 테니 수식으로만 간단히 표현하겠다.
소거된 행렬 U에 대한 방정식을 쓰면..
x3=1로 설정한 뒤 후방 대입법(Back substitution)을 통해 나머지 해를 계산하면 x=[-1 -1 1]T이 된다. 여기서 전체 Null space를 표현하려면 임의의 상수 c를 곱한 x가 된다.
이 예제에선 pivot이 두 개이고 따라서 Rank=2 이다. free variable은 column의 수에서 rank를 빼주면 되므로 n-r = 3-2 = 1이 된다. free variable이 하나 밖에 없기 때문에 식 (27)의 임의의 상수만 곱한 벡터 x가 전체 Null space를 표현하게 된다.
3. 마치며
이번 포스팅에서는 지난 강의에서 배웠던 Null space를 구하는 알고리즘에 대해 공부하였다. 우리는 임의의 행렬 A를 가우스 소거를 통해 U행렬로 만드는 법을 배웠고 pivot과 free variable이 갖는 의미에 대해서 배웠다. 이 과정에서 pivot의 개수가 그 행렬의 rank를 의미한다는 중요한 사실을 알 수 있었다.
우리는 또한 A-> U -> R로 만드는 과정을 통해 처음 임의의 행렬 A가 축소된 형태인 기약행 사다리꼴(reduced row echelon form)을 만드는 방법에 대해서도 배웠다. 또한 이 행렬이 갖는 의미를 배웠고 Null space를 정의하는 방법에 대해서도 알 수 있었다.