Learn Again! 러너게인

우리는 지난 포스팅에서 영공간(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이다. 

우리는 지금까지 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의 수가 된다. 조금 더 쉽게 설명하자면 다음과 같다. 

지금까지 배운 알고리즘을 통해 우리는 임의의 행렬 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를 정의하는 방법에 대해서도 알 수 있었다. 

이번 포스팅에서는 Column Space와 Null Space에 대해 설명할 것이다. 컬럼 공간, 영공간으로 각각 한글화 시킬 순 있지만 뭔가 어색하기 때문에 그냥 컬럼 스페이스, 널 스페이스로 읽도록 하겠다. Column space는 지난 포스팅에서 잠깐 배우긴 했지만, 이번에 좀 더 자세히 다뤄 보도록 하자. 

우선 지난 포스팅(Lecture 5)에서 우리는 벡터 공간(Vector Space)과 부분 공간(Subspace)에 대해 배웠다. 이번 포스팅에서 배울 내용의 이해를 돕기 위해 잠시 복습하는 시간을 가져보도록 하자. 

0. 벡터 공간(Vector Spaces) Review

벡터 공간(Vector Space)은 벡터의 집합이다. 단순한 집합이 아니라 똑같은 개수의 컴포넌트(x, y, ...)로 정의할 수 있는 무수히 많은 벡터들의 집합인데, 벡터의 공간임을 인정받기 위해선 다음의 규칙을 반드시 따라야 한다. 

예를 들어 3차원 공간 R3를 생각해보자. R3의 임의의 벡터 v=[1 7 -26]T와 w=[-999 7982 -32988]T가 있다고 가정해보자(T는 Transpose). 이때 임의의 상수 c=-33992와 d=93을 각각의 벡터에 곱한 다음 더해서 선형 결합 연산은 수행했다고 해보자. 결과는 아래와 같을 것이다. 

약간 큰 숫자로 예를 들었지만 어쨋든 결과 벡터도 여전히 3차원 공간상에 존재한다. 따라서 R3는 벡터 공간이라고 말할 수 있다. R1, R2, R4, R5, ... RN에 대해서도 마찬가지로 모두 벡터 공간이라고 할 수 있다. 

이런 것이 벡터 공간이라면 굳이 저렇게 어렵게 정의하지 않아도 직관적으로 알 수 있지 않나요? 라고 누군가 물어볼지도 모르겠다. 위와 같은 일반적인 공간을 정의하기 위해서 저렇게 복잡한 정의를 내리는 것이 수학자가 아닌 이상 무슨 필요가 있나요? 라고 묻는 사람도 있을 것이다. 그러나 이러한 일반적인 공간 말고도 부분 공간(Subspace)이라는 것이 있고, 이를 완벽하게 정의하기 위해선 위와 같은 조건이 반드시 필요하다. 

부분 공간(subspace)이라는 것은 말 그대로 어떤 공간 안에 존재하는 작은 공간(영역)이다. 3차원 공간 R3를 예를 들면 임의의 평면(Plane) 혹은 직선(Line)이 될 수 있겠다. 아래 그림을 보자. 

[x, y, z]의 3개의 컴포넌트로 구성된 3차원 공간 R3가 있다. 여기서 부분 공간이라 함은 어떤 임의의 평면 P나 임의의 직선 L이 될 수 있는데, 이때 반드시 만족시켜야 하는 조건이 한 가지 있다. 바로 모든 부분 공간은 반드시 원점(origin), 즉 [0 0 0]T을 지나야 한다. 

위 그림에서 부분 공간 P와 L도 원점을 지나간다.(왜 그래야만 하는지는 Lecture 5-(2)참조..) 평면 P에 존재하는 임의의 벡터인 녹색 벡터나 주황색 벡터는 어떠한 임의의 수를 곱하고 서로 더해도 여전히 이 평면 위에 존재한다. 라인 L도 마찬가지로 임의의 벡터인 빨간색, 파란색 벡터의 어떠한 선형 조합도 이 라인 L위에 존재할 수밖에 없다. 

자 여기까지는 지난 포스팅에서 배웠던 내용이다. 우리는 여기서 한 가지 궁금한 점이 더 생겼다. 

가령 우리가 어떤 부분 공간 2개를 얻었다고 가정해보자. 여기서 2개를 위의 P와 L로 생각해보자. 이때 우리가 P와 L을 한 번에 같이 놓는다면, 즉 P 부분 공간과 L부분 공간을 하나의 덩어리로 생각해 본다면 ,이 P와 L은 각각 혹은 둘 다가 하나의 부분 공간이 될 수 있을까? 수식으로 나타내면 P와 U의 합집합으로 생각하면 편할 것이다. 

이 경우 위의 P와 L의 합집합은 부분 공간이라고 할 수 있을까? 정답은 부분 집합이 아니다. 

왜 부분 집합이 아닐까? 바로 앞서 말했던 선형 결합의 규칙이 성립하지 않기 때문이다. 부분 집합이 되려면 집합 내의 원소들 끼리 임의의 상수를 곱하거나 공간 내 원소끼리 더해도 같은 공간에 존재해야 한다고 했다. 그러나 위의 평면 P의 주황색 벡터와 라인 L의 파란색 벡터를 더하면 어떻게 될까? 그 결과는 평면도, 라인도 아닌 R3어딘가로 향하게 될 것이다. 즉 P와 L의 합집합은 부분 공간이 될 수 없다. 

P와 L의 합집합은 부분 공간이 아님을 알았다. 그러면 이번엔 교집합은 어떠할까? P와 L의 교집합, 즉 겹쳐지는 부분은 어떠한가? 

결론적으로 P와 L의 교집합은 부분 집합이다. 위의 그림에서 P와 L의 교집합, 즉 교점은 원점이다. P와 L의 유일한 교점이다. 우리는 지난 포스팅(Lecture 5)에서 원점 그 자체도 하나의 부분 공간이 됨을 배웠다. 따라서 위의 경우는 부분 집합이 된다. 

위의 예 뿐만 아니라 어떠한 부분 집합들의 교집합은 모두 부분 공간이다. 왜냐하면 각각이 모두 부분 공간이기 때문에 겹쳐지는 공간은 반드시 부분 공간이 될 수밖에 없다. 

위 그림에서 라인 L이 평면 P에 겹쳐져 있다고 상상해보자. 이 경우 둘의 교집합은 라인 L이 된다. L은 당연히 부분 공간이다. 

정리하면

어떤 부분 공간들의 합집합은 부분 공간(subspace)이 아니다. 

어떤 부분 공간들의 교집합은 부분 공간(subspace)이다. 

1. Column Space

지난 강의에서 Column Space를 살짝 다루었다. 좀 더 자세히 알아보도록 하자. 지난 포스팅에서 예를 들었던 행렬 A를 다시 꺼내 보자. 

행렬 A는 3개의 column을 가진 행렬이다. 각 column은 4개의 원소로 이루어져 있고 4차원 공간 R4의 부분 공간이다. 이 column space를 C(A)라 표기한다. 그렇다면 행렬 A의 column 공간, 즉 부분 공간(subspace)을 어떻게 알아낼 수 있을까? 전체 공간 R4에서 A의 column이 나타내는 부분 공간을 어떻게 채워넣을 수 있을까? 바로 선형 결합(Linear Combination)을 이용하면 된다. 행렬 A의 3개의 column을 활용해 모든 선형 결합의 조합을 찾으면 A가 정의하는 column 부분 공간을 채울 수 있다. 

그렇다면 행렬 A가 정의하는 공간이 어떠한 공간일지가 궁금해진다. 이 공간은 얼마나 클까? 4차원 공간 R4 전체를 뒤덮는 부분 공간인가? 아니면 평면(Plane)이나 직선(Line)과 같이 일부분의 공간을 나타낼까? 

A의 부분 공간을 정의하기 위해선 A의 column의 선형 결합(Linear Combination)을 이용하면 된다고 배웠다. 그렇다면 A의 3개의 column의 선형 결합을 통해 R4 전체를 채울 수 있을까? 이에 대한 답은 No다. 왜 R4 공간 전체를 채울 수 없을까? 이를 위해 A의 부분 공간(subspace)인 column space가 얼마만큼의 크기인지 알아보자. 그 전에 우선 선형방정식(Linear Equation)에 대해 알아보자. 이는 column의 선형 결합과 밀접하게 연관되어 있기 때문에 먼저 알아보는 것이 좋다. 그럼 다음의 질문을 생각해보자. 

Ax=b는 모든 b에 대해서 해를 가지고 있을까? 

정답은 No다. 왜 그런지 살펴보자. 위의 식 Ax=b에서 A는 4개의 방정식(Equation)과 3개의 미지수(Unknown)를 가지고 있다. 

4개의 방정식은 A의 4개의 row vector를 계수로 하는 식들을 의미한다. 즉

3개의 Unknown은 x=[x1, x2, x3]를 의미한다. 우리가 찾아야 할 값은 위 식을 만족시키는 해 x=[x1, x2, x3]를 찾는 것이다. 

필자는 앞서 선형방정식이 A의 column의 선형 결합과 밀접하게 연관되어 있다고 했다. 위 식 (4)를 Lecture 1에서 배웠던 column picture의 형태로 다시 쓰면 아래와 같이 쓸 수 있다. 

식 (6)에서 우측의 형태는 A의 column의 선형 결합과 형태가 같다. 

자 다시 메인 질문으로 돌아가서 우리는 앞서 A의 column의 선형 결합이 R4전체를 채울 수 없다고 했다. 이 말은 식(6)의 모든 b 벡터에 대해서 해를 구할 수 없다는 말이다. 그렇다면 b가 어떤 값을 가져야 해를 구할 수 있을까? 이 질문에 대한 일반적인(General) 답을 구하기 전에 생각할 수 있는 해(solution) 몇개를 직접 구해보자.

가장 쉽게 생각할 수 있는 답은 b 벡터가 모두 0인 경우, 즉 b=[0 0 0 0]T일 때이다. 이 경우 x=[0 0 0]T이 됨을 쉽게 유추할 수 있다. 또 다른 경우는 b=[1 2 3 4]T일 때 x=[1 0 0]이 된다. 이때의 b는 A의 col1과 같다. col2, col3에 대해서도 각각 정리하면 해는 아래와 같다. 

자 이제 감이 조금 오는가? 아까의 질문에 대한 일반적인 답을 생각해보자. 

위의 말을 다시 생각해보면 A의 column의 선형 결합은 선형방정식 Ax 그 자체이다. A의 column space는 모든 Ax를 포함하고 있다는 말이다. 따라서 b 벡터가 A의 column space에 존재하지 않으면 해 x도 존재할 수 없다. 

결국 해(solution)를 구할 수 있는 b들은 A의 column의 선형 결합으로 표현된 b들이다. 

그렇다면 A의 column space는 얼마만큼의 크기를 갖는가? A의 column들은 서로에게 독립적(Independent)인가? 각 column은 하나의 새로운 차원을 만드는데에 기여하는가? 

A의 첫 번째, 두 번째 column 벡터는 상호 독립적(Independent)이다. 그러나 3 번째 column은 기존 두 개의 column에 종속적(Dependent)이다. 이는 앞의 두 개의 column의 합을 통해 col3를 정의할 수 있기 때문이다. 즉

col1과 col2를 pivot column이라 한다. col1이 4차원에서 하나의 line을 정의하고, col2가 또 다른 독립적인 line을 정의하는데 이 둘의 조합을 통해 하나의 평면(Plane)을 정의할 수 있다. 이때 col3는 이 평면위에 존재하기 때문에 새로운 차원을 정의하는데에 있어 아무런 기여를 하지 못한다. 따라서 A의 부분 공간(subspace)인 column space는 4차원 공간에서 2차원 공간인 평면을 정의하는데 그친다. 

우리는 column space를 정의하는데 있어 col3를 제외시킬 수 있다. 혹은 col1을 제외시키는 것도 가능하다. col3-col2=col1이기 때문이다. 4차원이기 때문에 그래프로 표현하긴 어렵지만 위의 내용을 잘 상상해보자. 

2. Null Space

이제 새로운 공간에 대해 알아보자. 바로 영공간(Null space)이다. (보통 널스페이라 발음한다. 앞으로는 영문 표기법을 따르겠다.)

이 Null space는 column space와는 완전히 다른 부분 공간(subspace)이다. 앞서 이용했던 행렬 A를 그대로 활용해 Null Space를 정의해 보겠다. A의 Null space의 정의는 다음과 같다. 

식(4)를 Null Space를 위한 식으로 다시 써보자. 

위 식에 대해 바로 생각할 수 있는 해(solution)은 무엇일까? 바로 0벡터 x=[0 0 0]T이다. 어떤 Null space든지 반드시 0벡터(zero vector)는 포함된다. 0벡터를 반드시 포함하기 때문에 우리는 벡터 공간(vector space)을 정의할 수 있는 기회를 갖는다. 

0벡터를 제외한 다른 해를 좀 더 정의해보자. A의 col1과 col2를 더하고 col3에 -1을 곱하여 더해주면 그 결과가 0벡터가 될 것이다. 즉 x=[1 1 -1]T이다. 또 다른 해는 없을까? 사실 방금 구한 해(solution)에 임의의 스케일 상수 c를 곱해주면 모두 해가 될 것이다. 즉 

이를 통해 A의 Null space를 정의할 수 있다. 이 Null space는 3차원 공간 R3의 부분 공간(subspace)이다. 3차원 공간에서 이 Null space가 어떻게 표현될까? 바로 직선(Line)의 형태로 표현된다. 아래 그림과 같이 zero vector(origin)와 x=[1 1 -1]T를 지나는 검은색 Line으로 정의 된다. 이것이 R3의 부분 공간인 A의 Null space이다. 

그렇다면 Null space가 벡터 공간인지 아닌지를 어떻게 확인할 수 있을까? Null space는 공간(space)이라고 정의하기 위한 조건들을 만족하는가? Ax=0의 해들은 언제나 부분 공간(subspace)을 이루는가? 이를 확인하기 위해선 다음을 확인해보면 된다. 

Ax=0의 어떤 해를 v라 하고, 도 다른 어떤 해를 w라 하자. Av=0, Aw=0이라고 할 때 v와 w가 하나의 공간에 존재한다면, A(v+w)=0이 성립해야 한다. 즉 아래의 조건이 만족하는지를 확인하면 Ax=0의 해들이 공간을 이루는지를 확인할 수 있다. 

여기서 A(v+w)=0은 분배 법칙(distributive law)에 의해 Av+Aw=0와 같이 쓸 수 있다. 이렇게 보면 사실 식(12)는 당연할 수밖에 없다. 또 한가지 확인해야 할 사항은 A(cx)=0인데, 여기서 상수 c는 앞으로 뺄 수 있으므로 당연히 성립하게 된다. 

여기서 한 가지 의문이 생긴다. 그렇다면 b=zero vector일때의 Null space 말고도 b가 임의의 값을 가질 때에도 해(solutions)에 대한 벡터 공간이 존재하는가? 아래의 예를 보자. 

위의 식 (13)은 b가 0이 아닌 임의의 값을 가지는 경우다. 여기서 해는 x=[1 0 0]T, 혹은 x=[0 -1 1]T 이다. 이에 대한 해들은 벡터 공간(vector space)를 이루는가? 정답은 당연히 No다. 왜냐하면 해 중에 zero vector는 없기 때문이다. 즉 원점을 지나지 않기 때문이다. b가 0이 아닌 임의의 벡터일 때 어떤 해(solution)들에 대한 평면(plane), 또는 직선(Line)이 있을 수 있지만 이들은 원점을 지나지 않는다. 따라서 0이 아닌 임의의 벡터 b에 대한 해의 벡터 공간은 존재하지 않는다. 

아래는 위의 Null space를 그리기 위한 MATLAB 코드이다. 

참고로 MATLAB에서 Null space를 구하기 위한 커맨드는 "null(A)" 이다. A는 임의의 rectangular 행렬이다. 

이때 계산되는 Null space는 Normalize가 된 null space가 나온다. 즉 위의 A의 Null space는 x=[1 1 -1]T인데 이 x를 x의 norm으로 나눠준 결과, 즉 x의 크기가 1이 되도록 만들어진 결과가 나온다. 아래 코드를 실제로 돌려서 확인해보자. 

3. 마치며

우리는 이번 포스팅에서 벡터 공간(vector space)과 부분 공간(subspace)에 대해 공부하였다. 이들 공간을 정의하는 법에 대해 배웠으며 임의의 행렬 A에 대한 부분 공간인 column space를 정의하는 법을 배웠다. column space를 정의하기 위해선 각 column들의 선형 결합(Linear Combination)을 통해 정의할 수 있으며, column간 독립성(Independency)의 확인을 통해 전체 공간에서 column space의 형태를 파악할 수 있었다. 

우리는 또한 임의의 선형 방정식(Linear Equation) Ax=b 에서 b=zero vector일 때, 즉 Ax=0의 해 집합인 Null space에 대해서 공부하였다. Null space는 column space와는 완전히 다른 공간이며 Ax=0을 만족시키는 모든 해들이 이루는 부분 공간(subspace)임을 배웠다. 다음 포스팅에서는 Ax=0에 대한 Null space를 계산하는 알고리즘에 대해 공부해 보도록 하겠다. 

이번에 이야기 할 주제는 벡터 공간(Vector Spaces)이다. 

벡터는 알겠는데(크기와 방향을 가지는 물리량.. 이라고 중,고등학교때 다들 배웠을 것이다) 공간이 붙으니까 뭔가 거창해보인다. 

그렇다면 이 벡터 공간이라는 놈은 어떻게 정의할 수 있을 까? 또 그 공간안에서 우리는 무엇을 할 수 있을까?

미리 이야기 하자면, 이전 포스팅(Lecture 1 참고)에서 언급했던 선형 결합(Linear Combination)을 미리 숙지하면 이번 포스팅을 이해하기 좋다.

지금부터 벡터 공간에 대해 알아보자. 

1. 벡터 공간(Vector Spaces)

- 2-dimensional vector space: 

벡터 공간에서 공간(Spaces)이란 단어에 대해 생각해보자. 공간이란 무엇인가? 

다수의 벡터가 있고, 이 벡터들이 모여 하나의 공간을 형성하는 것이다. 그러나 아무 벡터나 허용 되는 것은 아니다. 이 공간상에 존재하는 벡터들은 서로가 서로에게 더해질 수 있고, 임의의 숫자가 각각에 곱해져서 각 벡터의 길이가 늘어날 수도 있다. 즉 

선형결합(Linear Combination)연산이 같은 공간상에 존재하는 벡터들 사이에 가능해야 한다. 

예를 들어서 설명을 해보자. x축과 y축으로 이루어진 2차원의 벡터 공간을 생각해보자. 이를 아래와 같이 정의할 수 있을 것이다. 

R의 지수 부분의 숫자는 차원을 의미한다. 이 2차원 공간상에 존재하는 모든 실수(real number)벡터들의 집합을 의미한다. 여기에 포함되는 벡터들은 무수히 많을 것이다. 그 중에 몇 가지만 나열해보자. 

[3, 2]는 x축으로 3만큼, y축으로 2만큼 간 한 점을 원점으로부터 가리키고 있는 벡터이다. 

[0, 0]도 하나의 벡터가 될 수 있나? 라고 생각할 수도 있을 것이다. 그러나 어쩌면 벡터 공간을 정의하기 위해 가장 중요한 벡터가 바로 영 벡터이다. 차차 설명하겠다. 

[pi, e]는 그 값이 대략 [3.14, 2.718]가량 된다. 역시 생각할 수 있는 벡터 중 한 가지이다. 이 벡터들을 실제로 공간상에 표현해보자.

위에서 언급한 벡터들이 좌표 평면상에 표현되었다. 여기서 영벡터 [0 0]는 실제로 표현되지는 않았지만 분명히 이 평면상에 존재하는 하나의 벡터 원소이다. 

어쩌면 영벡터[0 0]는 필요 없지 않나요? 라고 생각할 수도 있다. 그러나 영벡터도 공간을 이루기 위해서 반드시 필요하다. 왜냐하면 벡터 공간내에서 존재하는 모든 벡터들은 선형 결합(Linear Combination)을 통해 만들어질 수 있어야 한다. 가령 2차원 공간에서 영벡터를 제외시킨다고 가정해보자. 이때 아래와 같은 선형결합을 할 경우엔 그 식이 성립하지 않게 된다. 

영벡터가 존재하지 않고선 위의 식이 성립할 수 없게 된다. 이와 같이 모든 차원의 벡터 공간은 반드시 영벡터를 포함해야 한다. 

- 3, and n-dimensional vector space:

3차원 벡터 공간을 살펴보자. 2차원에 비해 벡터의 컴포넌트 한 개가 더 추가된 것일 뿐 기본적인 개념은 똑같다. 3개의 실수(real number) 컴포넌트들로 구성된 벡터들로 이루어진 공간이다. 이를 조금 다르게 표현해보면...

"3 개의 실수 컴포넌트(x, y, z)로 정의할 수 있는 모든 벡터들이 존재할 수 있는 공간"이라 할 수 있겠다. 

물론 실수 뿐만 아니라 허수(imaginary number)로 이루어진 벡터 공간도 있지만 그건 나중에 다루도록 하겠다. 결국 3차원 공간은 아래와같이 정의된다. 

3차원 벡터의 원소는 당연히 아래와 같을 것이다. x, y, z의 3개의 컴포넌트로 구성되어 있다. 

좀 더 확장해서 생각해보면 벡터는 3차원 벡터 뿐만 아니라 4차원, 5차원, .. n차원 벡터가 있을 수 있다. 물론 시각적으로 표현이 가능한 차원은 3차원이 한계이다. 그러나 이론적으로 3차원 이상의 n차원 벡터는 존재할 수 있으며 2차원 및 3차원 벡터에서 보였던 선형 결합 등등의 관련된 연산도 가능하다. 따라서 우리는 이러한 벡터 공간을 n차원으로 확장하여 정의할 수 있다. 

2. 부분 공간(Subspace)

우리는 앞서 같은 공간상에 있는 벡터들은 동일한 공간에 존재하는 다른 벡터들의 선형 결합에 의해 정의될 수 있어야 한다고 했다. 즉 어떤 벡터에 일정 상수값을 곱해 scale(길이)을 늘려주거나, 다른 벡터를 더해주었을 때 그 결과가 같은 공간에 존재해야 한다. 그런데 과연 항상 이러한 경우만 존재할까? 아래의 벡터 공간이 성립하지 않는 경우의 예를 보자. 

아래의 2차원 공간에서 1사분면(x축 +방향, y축 +방향)만 취한다고 가정해보자. 

즉 우리는 2차원 공간 전체 중에서 1/4의 영역인 1사분면만 가질 수 있다고 가정해보자. 먼저 이 공간내의 다른 벡터와의 덧셈 연산에 대해서 살펴보자. 1사분면 공간내의 어떠한 벡터끼리 덧셈을 해도 그 결과가 1사분면에 위치하는가? 답은 Yes이다. 아래를 보자. 

덧셈 연산에 "닫혀"있다.

1사분면 내의 임의의 벡터 v1(Red)과 v2(Green)를 더했다. 결과 벡터(v1+v2)는 여전히 1사분면에 위치해 있다.

여기서 v1과 v2는 1사분면 공간 내의 원소들이기 때문에 무조건 x와 y컴포넌트가 양의 값을 가진다. 따라서 이 공간 내의 어떤 벡터끼리 더해도 그 결과 벡터는 여전히 1사분면에 위치할 수밖에 없다. 이러한 경우 우리는 1사분면의 벡터 공간은 덧셈 연산에 대해 "닫혀있다(closure)"라고 한다. 

선형 결합이라 함은 벡터끼리의 덧셈과, 각 벡터에 어떤 scale값을 곱해주는 곱셈연산이 있다. 이번엔 곱셈 연산이 성립하는지를 알아보자. 1사분면 벡터들에 대해 임의의 스케일 값을 곱했을 때 그 결과벡터가 여전히 1사분면에 위치해 있는가? 답은 No이다. 역시 아래 예를 보자. 

곱셈 연산에 "닫혀있지않다"

1사분면의 임의의 벡터 v에 임의의 상수 2를 곱해서 벡터의 길이를 늘렸다. 이때 2v는 여전히 1사분면에 위치해 있다. 그러나 문제는 그 스케일의 방향이다. 즉 반대 부호인 -2을 곱했을 경우 이 결과 벡터인 -2v는 1사분면을 벗어나게된다. 따라서 1사분면 공간의 벡터에 대해 곱셈 연산은 "닫혀있지않다(not closure)"

이 경우, 우리는 1사분면을 벡터 공간이라고 정의 할 수 없다. 덧셈에는 닫혀있으나, 곱셈에는 닫혀있지않기 때문이다. 

- R2안의 벡터 공간, (Subspace of R2):

위의 1사분면의 예를 다시 생각해보자. 1사분면은 분명히 2차원 공간내에 존재한다. 그러나 선형 결합에 대한 규칙이 성립하지 않기 때문에 벡터 공간, 혹은 부분 공간이라고 할 수 없다. 그렇다면 2차원 공간에 포함되면서도 선형 결합 규칙이 성립하는 작은 공간은 없을까? 이를 좀 더 일반적인 시각으로 봤을 때, 임의의 n차원 공간에 포함되면서 n차원 벡터들에 대한 선형 결합 규칙이 성립하는 작은 공간은 없을까? 

임의의 n차원 공간에 대해, n차원 공간에 포함되면서 n차원 벡터들에 대해 선형 결합 연산이 성립하는 작은 공간을 우리는 부분 공간(Subspace)라 부른다. 즉 부분 공간 안의 벡터들끼리는 안전하게 선형 결합 연산을 할 수 있어야 한다. 

결국 이 부분 공간이라는 것은 크게는 n차원 공간에 포함이 되고, 부분 공간내의 벡터들을 활용해 선형 결합 연산을 수행했을 때 그 결과 벡터가 여전히 부분 공간에 존재할 경우(정확하게는 n차원이 아닌 n차원 안의 부분 공간에 존재해야 함) 성립한다. 

글 만으로 이해하기는 좀 어려울 것이다. 아래의 부분 공간에 대한 예를 위에서와 마찬가지로 2차원 공간에서 설명해보자. 아래 그림을 보자. 

위 그림에서 벡터 v가 2차원 공간의 어떤 부분 공간(subspace)에 위치해 있다고 가정하자. 이 부분 공간이 진짜라면, 위의 벡터 v말고도 다른 벡터들이 부분 공간안에 더 존재해야 한다. 다른 벡터라고 한다면 가령 임의의 상수를 곱한 벡터들이 될 수 있겠다. 2, 3, 혹은 -1/2과 같은 상수들 말이다. 그렇게 임의의 상수들을 더한 것들을 나열해보면 아래와 같이 될 것이다. 

즉 이 부분공간에는 빨간색 벡터 v말고도 주황색 벡터 2v, 보라색 벡터 3v, 초록색 벡터 -1/2v 등이 존재한다. 심지어는 0을 곱한 영벡터(zero vector)도 있다. v에 0을 곱한 영벡터의 경우 [0 0]이 되는데 이러한 영벡터도 이 부분 공간의 원소에 포함된다. 이 외에도 수 많은 벡터들이 존재할 수 있다. 이러한 수많은 벡터들을 나열한 것이 바로 직선 l이다. 결국 이 부분 공간은 직선(Line) l 이 된다. 

곱셈 연산에 대한 성립은 확인을 했고, 이제 덧셈 연산에 대해 확인해보자. 이 부분 공간인 직선 l에 존재하는 어떠한 벡터들끼리 더해도 같은 공간에 존재하는가? 답은 YES임을 쉽게 유추할 수 있다. 따라서 이 직선은 R2의 부분 공간이 맞다.

여기서 이러한 의문이 들 수 있다. 그렇다면 R2에 존재하는 모든 직선(line)은 전부 부분 공간(subspace)이 될 수 있을까? 아래 그림을 보자. 아래 그림에서 점섬으로 표현된 직선을 생각해보자. 이 직선은 R2의 부분 공간이 될 수 있을까?

위의 직선을 실제 벡터들로 표현하면 아래 그림과 같이 된다. 

위의 직선 l'은 R2의 부분 공간인가? 정답은 No다. 결론부터 말하자면 R2에 존재하는 직선이 부분 공간이 되기 위해선 반드시 원점인 zero vector를 지나가야 한다. 왜 그런지 한 번 살펴보자. 

부분 공간이 되기 위해선 어떠한 수를 곱하거나, 같은 공간내의 어떠한 벡터들을 더해도 그 결과가 부분 공간내에 존재해야 한다. 위 그림에서 빨간 벡터에 0을 곱했을 때, 그 결과가 점선으로 표현된 직선 l'에 존재하는가? 혹은 주황색 벡터에 보라색 벡터를 더했을 때 그 결과가 직선 l'에 존재하는가? 두 경우 모두 틀리게 된다. 다른 어떠한 상수를 곱해도, 벡터를 더해도 결과는 마찬가지 이다. 따라서 위의 직선은 R2의 부분 공간이 아니다. 

결국 임의의의 부분 공간(subspace)은 "반드시 zero vector를 포함해야 한다!"

왜냐하면 어떠한 벡터도 영을 곱하면 zero vector가 되기 때문이다. 

그렇다면 2차원 평면인 R2에서 가능한 부분 공간은 어떠한 것들이 있을까? 한 번 나열해보자. 

1번은 R2 그 자체가 하나의 부분 공간이 될 수 있다는 말이다. 

2번의 경우 앞에서 언급했듯 임의의 직선(Line)인데, 원점을 반드시 지나는 경우이다. 원점만 지난다면 어떠한 직선도 2차원 평면의 부분 공간이 될 수 있다. 

마지막 3번은 전체 평면도, 특정 직선도 아닌 바로 영벡터(zero vector) 그 자체이다. 즉 한 점 공간(point space)이다. 이 zero vector자체가 부분 공간이 성립되는 이유는 부분 공간에 대한 모든 조건을 만족하기 때문이다. 

- 일단 R2에 속해있다. 

- 또한 어떤 상수를 곱해도 zero vector이다. 

- 그리고 zero vector의 원소들인 zero vector들 끼리 더해도 여전히 zero vector이다. 

따라서 임의의 Rn공간에서 zero vector 자체는 항상 Rn의 부분 공간이 된다. 

그렇다면 3차원 공간 R3의 부분 공간은 어떠한 것들이 될까? 

등이 될 것이다. 3차원 공간 그 자체, 원점을 지나는 평면, 원점을 지나는 직선, 그리고 영벡터 그 자체이다. 

3. 행렬의 부분 공간(Subspace of Matrix)

이제 실질적인 문제를 살펴보자. 우리는 앞서 어떤 공간에서 부분 공간(subspace)을 정의하는 법을 배웠다. 이러한 부분 공간은 어떤 임의의 행렬(Matrix)에서도 끄집어낼 수 있다. 지난 포스팅(Lecture 5-1)에서 정의했던 행렬을 다시 살펴보자. 

우리는 위의 행렬 A로 부터 부분 공간을 뽑아낼 수 있다. 바로 column 공간(column space)이다. 이는 매우 중요한 부분 공간이며 행렬로부터 뽑아내는 첫 번째 부분 공간이다. A의 column은 R3에서 정의될 수 있다. A의 부분 공간을 정의하기 위해선 column 요소끼리 더하고, 각 column에 임의의 상수를 곱해서 만들면 된다. 즉 A의 column원소끼리 정의할 수 있는 모든 선형 결합(Linear Combination)을 통해 A의 부분 공간을 정의한다. 

위의 정의는 이번 포스팅에서 어쩌면 가장 중요한 개념이다. 잘 기억해 두도록 하자. 

그럼 실제로 공간상에서 어떻게 표현되는지 구현해보도록 하자. 아래 그림은 위의 행렬의 column에 대한 벡터들을 3차원 공간상에 표현한 것이다. 

이제 아래와 같이 두 column 벡터들에 임의의 상수를 곱하고 이를 더해서 선형 결합을 한 결과를 그려보도록 하자. 

우선 10개의 임의의 선형 결합을 한 결과이다. 

nVec = 10

여기 저기 파란색 벡터들이 생겨나긴 했는데, 이것만 가지고는 뭐가 어떻게 되는지 파악하기 힘들 것이다. 이번에는 개수를 100개로 늘려서 그려보기로 하자. 

nVec = 100

뭔가 형상이 보이는가? 약간 평면이 나올 것만 같은데.. 개수를 좀 더 늘려보자. 이번엔 500개다. 

nVec = 500

위의 첫 번째 그림은 아까와 동일한 각도에서 바라본 것이다. 평면 같기는 한데 확인을 위해서 돌려서 봤다. 역시 평면의 형태가 보인다. 평면의 형태는 어떻게 보이는가? 평행사변형 모양이 보이지 않는가? 여기서 무엇을 알 수 있는지 아는 사람은 보일 것이다 ㅎㅎ

결론적으로 행렬 A의 column들의 선형 결합을 통해 우리는 R3의 부분 공간이 평면(plane)이라는 것을 눈으로 확인할 수 있었다. 부분 공간을 정의하기 위해선 임의의 행렬 A의 column원소들의 가능한 모든 선형 조합을 생각해보면 된다. 

아래는 위 선형 결합을 구현한 코드이다. 

4. 마치며..

이번 강좌에선 임의의 차원의 공간에서 부분 공간(subspace)을 정의하는 방법을 배웠다. 부분 공간을 정의하기 위해선 특정 조건을 만족해야 한다. 부분 공간내 모든 벡터 원소들 끼리 선형 결합 연산이 성립이 되어야하고, 모든 부분 공간은 반드시 영벡터를 포함해야 한다. 

우리는 또한 어떤 행렬로부터 column space를 정의하는 방법을 배웠다. 어떤 행렬의 부분 공간을 정의하기 위해선 row, 혹은 column원소들의 가능한 모든 선형 결합을 통해 정의할 수 있다. 이것이 이번 포스팅의 핵심 내용이다. 잘 기억하도록 하자. 

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

지난 포스팅의 마지막 부분에 우리는 치환행렬(Permutation matrix)과 전치(Transpose)에 대해 간략히 언급하였다. 이번 포스팅의 서두에선 이에 대해 좀 더 이야기해보고 마무리 짓도록 하자. 

1. Permutations

이전 포스팅에서 언급했듯이 치환 행렬(Permutation matrix)은 행 교환(row exchange)을 수행하는 행렬이다. 그렇다면 이러한 치환 행렬은 언제 필요할까? 우리는 지금까지 행렬의 소거를 하는 과정에서 행 교환이 필요없는 경우를 가정하고 소거를 진행하였다. 하지만 항상 완벽한 행렬만 존재할 수는 없기 때문에 반드시 행 교환이 필요할 때가 있다. 바로 pivot이 0인 경우다. 소거 과정에서 pivot이 0이 되는 경우에 행 교환이 필요하며 이때 사용되는 행렬이 바로 치환 행렬이다. 이러한 치환은 한 번이 될 수도, 혹은 여러 번이 필요할 수도 있다. 그때 마다 필요한 치환 행렬을 곱해서 행 교환을 해서 소거를 완료하는 것이다. 

A=LU Decomposition을 살펴보자. 우선 A=LU의 형태는 아래와 같을 것이다. 지금까지 가졌던 가정은 A는 행 교환이 필요 없는 완벽한 행렬이라는 것이다. 따라서 P행렬도 필요 없었고, 여기서의 P행렬은 단위행렬이 될 것이다. 행 교환이 필요 없기 때문에 단위 행렬을 곱해서 행을 그대로 둔 채 소거를 해 나간다.

여기서 잠깐 실질적인 이야기를 해보자. 그렇다면 실제로 MATLAB과 같은 프로그램에서 이러한 소거 연산을 어떻게 수행할까? MATLAB에선 소거 연산을 수행할 때 우리가 체크하는 것과 같이 pivot이 0인지를 체크한다. 그런데 MATLAB은 여기서 한 가지 더 체크를 하는 것이 있다. 바로 pivot의 값이 충분히 큰지를 검사한다. 만약 pivot값이 0에 가깝다면 수치적으로(numerically) 좋지 않다. 대수적으론 이러한 과정이 필요하지 않지만, 수치 정확도(numerical accuracy)가 좋지 않아서 계산 결과가 좋지 않을 수 있다. 따라서 0에 가까운 pivot이 있을 경우 MATLAB은 행 교환 연산을 수행한다.

어쨋든 A=LU Decomposition을 할 때 행 교환이 필요한 경우 식이 아래와 같이 된다. 

여기서 P는 행 교환 연산을 수행하는 치환행렬이고, 위 식은 어떤 invertible A에도 적용이 된다. 사실 대부분의 경우 행 교환이 필요하지 않는데, 가끔씩 행 교환이 필요한 경우 위와 같이 P행렬을 통해 행 교환 및 소거를 수행한다. 

지난 포스팅(lecture 4)에서 언급했듯이 P행렬은 단위행렬에서 각 행을 서로 교환한 조합이다. 이를 다시 한 번 상기시키자면 아래 식과 같다. 

단위 행렬도 하나의 치환 행렬에 포함되며 P12는 단위 행렬에서 row1과 row2를 교환한 행렬을 뜻한다. 자세한 사항은 lecture 4의 마지막 부분을 참고하자. 

이러한 치환 행렬의 조합은 n!(factorial)만큼 된다. 즉 n=3일 때, 3x2x1=6가지 조합이 나올 수 있는 것이다. 

치환 행렬은 편리한 속성이 두 가지 있다. 

첫 번째는 모든 P행렬은 invertible하다. 즉 역행렬이 존재한다. (역행렬이 존재하는 단위행렬에서 행만 바꿨으므로 당연히...)

두 번째는 P행렬의 역행렬은 전치(Transpose)행렬과 같다. 즉 아래 식을 만족한다. (이 속성은 굉장히 편리하다)

2. Transpose

전치(Transpose)는 지난 포스팅에서도 잠깐 언급했지만, 좀 더 자세히 살펴보도록 하자. 일단 무작정 전치라는 연산을 한 번 해보자. 아래 행렬을 보자. 

왼쪽의 3x2 행렬을 전치 했더니 오른쪽의 2x3형태의 행렬이 됐다. 쉽게 생각하면 행렬의 전치는 뒤집기다. 대각선을 축으로 180도 뒤집었다고 생각하면 된다. 그런데 행렬의 차원을 보니 row의 차원이 column차원으로, column의 차원이 row의 차원으로 변한 것을 볼 수 있다. 즉 row와 column이 바뀐 것으로 생각하면 된다. 이에 대한 정의를 아래와 같이 쓸 수 있다. 

i는 row의 인덱스, j는 column의 인덱스인데 전치를 하면 이 두 인덱스가 바뀌게 된다. 즉 식 (6)에서 2를 보면 전치를 하기 전엔 A(2,1)이었지만, 전치를 한 후엔 A(1,2)의 자리로 간 것을 볼 수 있다. 

3. 대칭 행렬(Symmetric Matrix)

이번에 알아볼 행렬의 형태는 특별한 형태이면서도 어떻게 보면 최고의 행렬 형태라고도 볼 수 있다. 바로 대칭 행렬(Symmetric Matrix)인데, 이 행렬이 가지고 있는 특성 때문에 다양한 곳에 응용된다. 

이름 그대로 이 행렬의 특성은 대칭이라는 것이다. 즉 전치(Transpose)를 해서 행렬을 뒤집어도 원래 행렬과 같은 특성을 가진다. 아래 예를 보자. 

식(8)의 행렬 A는 대칭 행렬이다. 일단 대각(diagonal) 원소를 보자. 대각 원소는 diag(3, 2, 4)인데, 이 대각 원소를 기준으로 상삼각(Upper triangular)과 하삼각(Lower Triangular) 부분이 같은 것을 알 수 있다. 따라서 전치를 통해 행렬을 대각 원소를 중심축으로 뒤집어도 그 결과는 같으며 차원 또한 변함이 없다. 

그렇다면 우리는 이러한 대칭 행렬을 언제, 어떻게 구할 수 있을 까? 식 (6)의 R행렬을 다시 보자. 

위의 R행렬은 대칭 행렬과는 거리가 많이 멀어보인다. R의 전치 행렬도 마찬가지다. 둘 다 직사각형 모양이다. 하지만! 우리는 이렇게 대칭 행렬과는 거리가 아주 멀어 보이는 행렬을 가지고 대칭 행렬을 얻을 수 있다. 바로 저 둘을 곱하면 된다. 실제로 한 번 해보자. 

R행렬을 R의 전치 행렬과 곱했더니 우측의 S행렬이 나왔다. S행렬을 보면 대각 원소들을 기준으로 대칭인것을 한 눈에 알 수 있다. 이렇듯 어떤 행렬을 자신의 전치 행렬과 곱한 결과가 대칭 행렬이 나오는 이유는 다음과 같다. 자신과 똑같은 행렬을 단지 뒤집어서 곱했기 때문에 똑같은 원소 끼리의 곱이 반복될 수 밖에 없다. 아래의 연산 순서를 보자. 

 식 (10)은 식 (9)의 곱셈 과정을 순차적으로 나열한 것이다. 이를 보면 두 번째 연산과 네 번째 연산이 같은 원소끼리의 곱이 반복됨을 알 수 있다. 이렇게 같은 원소끼리 반복되는 연산은 대각 원소를 제외한 모든 원소에서 발생한다. 이러한 연산은 결코 우연이 아니라 필연적으로 일어날 수 밖에 없는 것이다. 결론적으로 아래의 정의를 얻을 수 있다. 

어떤 임의의 행렬 A와 그의 전치 행렬(Transpose)을 곱하면 항상 대칭 행렬(Symmetric Matrix)을 얻는다!

위 정의를 수식으로 증명하자면 아래와 같다. 어떤 행렬이 대칭 행렬인지를 알기 위해선, 전치를 해 봤을 때 원래의 행렬과 같으면 우리는 이 행렬이 대칭 행렬인지를 알 수 있다. 

전치의 전치는? 당연히 원래의 행렬일 것이다. 결과를 보라. 전치를 하기 전의 행렬과 같은 것을 알 수 있다. 위의 중요한 정의를 잘 기억해두자. 

3. 마치며

이번 포스팅에선 치환 행렬(Permutation Matrix)과 전치(Transposes), 그리고 대칭 행렬(Symmetric Matrix)에 대해 알아보았다. 치환 행렬은 어떤 행렬의 왼쪽에 곱해져서 행 교환(row exchange)연산을 수행하고 전치는 row와 column의 index를 바꾸는 연산이다. 쉽게 말해 행렬을 대각선을 기준축으로 180도 회전시키는 것이다. 마지막으로 대칭 행렬에 대해 알아보았고, 대칭 행렬은 대각 원소를 기준으로 상삼각행렬과 하삼각행렬의 원소가 같은 행렬이며 전치 행렬이 원래 자기 자신과 같은 행렬임을 알았다. 또한 임의의 rectangular행렬 A에 대해 A의 전치 행렬에 A를 다시 곱하면 항상 대칭 행렬이 나옴을 알 수 있었다. 다음 포스팅에선 벡터 공간(Vector Spaces)에 대해 공부해 보도록 하자. 

이번 포스팅에선 A=LU 분해(LU Decomposition)에 대해 알아보겠다. (LU Factorization이라고도 불린다. 그러나 앞으로 LU Decomposition이라 표현하겠다)

쉽게 말해 어떤 행렬 A가 있을 때, 이를 하삼각 행렬(Lower triangular matrix)과 상삼각 행렬(Upper triangular matrix)의 곱으로 분해하여 나타내는 것을 의미한다. A=LU에서 L과 U는 바로 Lower와 Upper의 처음 이니셜만 따서 표현한 것이다. 

LU Decomposition은 가우스 소거(Gauss Elimination)에 의한 Elimination 행렬 형태로 볼 수 있으며, 때때로 치환행렬(permutation matrix, ※Lecture 2 참조)을 포함하기도 한다. 컴퓨터는 square 형태의 선형 방정식을 계산할 때 이 LU Decomposition을 사용하며, 역행렬(Inverse Matrix)을 계산하거나 행렬식(determinant)을 계산할 때 필요한 주요 과정이다. 

1. 행렬곱셈의 Inverse

LU Decomposition을 알아보기 전에 먼저 행렬곱셈의 Inverse에 대해 잠깐 살펴보고 가도록 하자. LU Decomposition의 이해를 돕기 위함이다.

어떤 행렬 A가 있고 그의 역행렬을 알고 있을 때, 우리는 이 역행렬을 곱하면 단위행렬이 되는 것을 알고 있다. 이때 역행렬을 A의 왼쪽, 혹은 오른쪽에 곱해도 그 결과는 같다. 

그렇다면 아래와 같이 non-singular이고 정방행렬(square matrix)인 A와 B가 있다고 가정하자. 이 두 행렬의 곱셈 AB의 뒤에 역행렬을 곱해 단위 행렬(Identity matrix)을 얻고자 할 때, 우리는 빈 칸에 들어갈 역행렬을 어떻게 곱해야 하는가? 식(1)과 같이 역행렬을 순서대로 곱해야 하는가? 

정답은 반대의 순서로 역행렬을 곱해줘야 한다. 즉 B의 역행렬을 먼저 곱해주고 그 다음 A의 역행렬을 곱해줘야 한다. 아래 식 (3)-1을 보자. B와 B의 역행렬이 먼저 곱해져서 단위 행렬이 만들어진다. 이때 단위 행렬은 어디에 곱해도 결과는 변하지 않으므로 무시해도 된다. 결국 A와 A의 역행렬과의 곱이 되고 답은 단위행렬이 만들어진다. 식 (3)-2와 같이 순서가 바뀌어도 결과는 마찬가지다. 

결국 단위행렬을 만들기위해 역행렬을 곱해줄 때에는 각 행렬의 역행렬이 본래 자신의 행렬과 붙을 수 있게, 즉 원래 행렬 곱셈의 반대 순서로 역행렬을 곱해주면 된다. 

- Transpose: 

이번엔 행렬 곱셈에 대한 전치(Transpose)에 대해 알아보자. 이후에 더 자세히 다루겠지만 transpose라는 것은 row의 원소들이 column이 되고, column의 원소들이 row의 원소가 되는 것이다. 쉽게 말해 식(4)와 같이 대각선을 중심축으로 행렬을 180도 돌려서 뒤집는 것이다. 

그렇다면 행렬 곱셈에 이러한 transpose를 적용하면 어떻게 될까? 아래와 같이 정방행렬인 A와 A의 역행렬을 곱해서 단위 행렬을 만드는 식이 있을 때, 이 식을 transpose시켰다고 했을 때 결과는 식(5)의 마지막 줄과 같이 행렬 곱셈의 순서가 뒤바뀌게 된다. 

우변의 I는 그대로 I가 되고 좌변의 A와 A inverse는 곱하는 순서가 반대로 된다.

또한 식(5)의 마지막 줄에서 A의 역행렬의 transpose는 => A의 transpose의 역행렬로 바꿔 쓸 수 있다. 단 이 규칙은 각각의 단일 행렬에 대해서만 적용된다. 식 (6)을 참고하자.

2. LU Decomposition

- What and why Decomposition?: 

Decomposition(Factorization)이라는 것은 말 그대로 분해하는 것을 의미한다. 쉽게 말해 어떤 시스템 혹은 데이터를 표현한 행렬 A를 인수분해 한다는 뜻이다. 우리가 중고등학교때 배우던 그 인수분해처럼 말이다. 위키 사전에는 이 행렬 분해(Matrix Decomposition)의 정의를 다음과 같이 정리하였다. 

선형대수에서 Matrix Decomposition은 어떤 행렬(Matrix)을 여러 행렬들의 곱으로 표현하는 것을 의미한다. 

출처: (https://en.wikipedia.org/wiki/Matrix_decomposition)

그렇다면 이러한 Matrix Decomposition은 왜 하는 것일까? 그 해답은 바로 우리가 중학교때 배웠던 인수분해를 하는 이유와 같은 맥락이다. 우리가 어떤 방정식을 인수분해 하는 이유는 바로 그 방정식의 해를 구하기 위해서다. 혹은 해를 좀 더 쉽게 구하기 위해서, 방정식을 좀 더 알아보기 쉽게 하기 위해서, 특수한 상황에서 문제를 풀기 쉽게 하도록 하기 위해서 등이다. 

Matrix Decomposition도 마찬가지이다. (http://www.ece.northwestern.edu/~mya671/files/Matrix_YM_.pdf) 에선 Matrix Decomposition의 목적을 크게 두 가지라고 하였다. 첫 번째는 계산의 편리함(computational convenience), 두 번째는 분석적 용이성(analytic simplicity)을 위함이다. 결국 Matrix Decomposition을 하는 이유는 계산을 좀 더 편리하게 하고 어려운 문제를 쉽게 풀기위해, 시스템 행렬을 단순화시켜 표현하여 분석을 용이하게 하기 위함이다. 

행렬 분해는 다양한 방법들이 존재한다. SVD(Singular Value Decomposition), QR Decomposition 등등 다양한 방법들이 존재하며, 각 방법들은 각자 고유의 분해 특성들을 가지며 다양한 문제를 푸는데 사용된다. 여기서 우리는 행렬 분해 방법들 중 가장 기본적인 형태인 LU Decomposition에 대해 알아보자. 

- LU Decomposition(Factorization):

어떤 행렬 A가 있고 이 행렬은 역행렬을 가질 수 있는 정방행렬이고, 역행렬을 구하기 위해 소거를 하는 과정에서 Row exchange도 필요 없는 아주 좋은 형태의 행렬이 있다고 가정해보자. 

우리는 A에 소거법을 적용해서 최종적으로 U행렬을 만드는 것을 지난 포스팅(Lecture 2)에서 배웠다. 여기서 우리는 A와 U사이의 연결 고리를 알아야 한다. 즉 A가 U와 어떻게 연결이 되는지 말이다. 식으로부터 짐작하신 분들도 있겠지만, 바로 L행렬이 이 연결고리가 된다. 

이 연결고리인 L행렬이 어떻게 만들어 지는지 실제 계산을 통해 알아보자. 

아래와 같이 2x2크기인 비 특이행렬(non-singular Matrix) A가 있다. 

자 이제 A행렬을 소거하여 만들어지는 상삼각행렬(Upper Triangular Matrix)인 U행렬을 만들기 위해 E21행렬을 만들어보자. (E21은 A의 row2, column1의 원소인 8을 제거하기 위한 Elementary or Elimination Matrix라는 의미다)

E21행렬은 어떻게 만드는가? 일단 A에서 pivot은 2이다. 이 pivot의 column에서 바로 아래에 있는 원소 8을 제거해야 하는데 바로 위의 pivot인 2와 딱 4배 차이가 난다. 따라서 row1[2 1]에 4를 곱한다음 row2[8 7]에서 row1을 뺀 결과값을 row2에 대입하면 될 것이다. 즉 아래 식과 같다.

그렇다면 이렇게 되기 위해선 E21행렬의 원소들이 어떻게 배치되어야 할까? 

pivot이 있는 A의 row1은 그대로 유지되어야 한다. E21의 row1은 그렇다면 1*[2 1] + 0*[8 7]이므로 [1 0]이 되어야 한다. 

E21의 row2는 어떻게 되어야 할까? -4*[2 1] + 1*[8 7] 이므로 [-4 1]이 되어야 할 것이다. 결국 식 (9)와 같이 E21이 만들어 질 것이다. 

(※소거와 관련된 내용은 Lecture 2참고)

자 이렇게 만들고 보니 처음에 구하고자 했던 A=LU와는 다른 형태지만 어떤 처리를 하면 뭔가 나올 것만 같다. 눈치 채셨는가?

그렇다. 그것은 바로 좌변과 우변의 왼쪽에 E21의 역행렬을 각각 곱해주면 될 것이다. 즉

결국 소거행렬(Elimination Matrix) E21의 역행렬이 L행렬인 것이다. 이때 L은 하삼각행렬(Lower Triangular Matrix)의 형태를 띄게 된다. 

이제 E21역행렬을 구하면 된다. E21의 역행렬은? 바로 -4의 부호만 +로 바꿔주면 된다. 역행렬이라는 것이 곱해서 단위행렬을 만들어야 하기 때문이란 것을 안다면 쉽게 유추할 수 있다. 방금 전 E21을 만들 때와 같이 -4를 소거하여 0으로 만들 방법을 생각하면 쉽게 만들 수 있다. 

이렇게 구한 E21의 역행렬은 결국 L이 되고 L과 U를 실제로 곱해보면 A가 나오는 것을 확인할 수 있다. 식 (11)은 A=LU를 나타낸 것이다. 

- LDU Decomposition:

어떤 경우에 이 Pivot들만 따로 떼어서 분해해야 하고 싶을 때도 있다. U행렬은 대각선으로 두 개의 pivot인 2와 3을 가지고 있다. 첫 번째 pivot이 2, 두 번째 pivot이 3이다. 만약 이 pivot들만 따로 분리하여 행렬을 만들고 싶을 때 우리는 다음과 같이 할 수 있다. 

U행렬에서 각 pivot이 속해있는 row를 해당 pivot으로 나누어준다. 그 결과값을 새로운 U의 각 row에 넣고 pivot들만 대각선으로 나열되어 있는 행렬을 써주면 된다. 즉 아래 그림과 같이 하면 된다. 

연산 자체가 간단하기 때문에 따로 부연설명은 하지 않겠다. 

이렇게 해서 만들어진 행렬의 조합을 우리는 LDU Decomposition Matrix라 한다. 여기서 D는 Diagonal Matrix의 뜻이며 대각선 방향의 원소만 가지고 있는 대각 행렬을 의미한다. 왼쪽엔 하삼각행렬(Lower Triangular Matrix), 가운데는 Pivot들만 있는 대각행렬(Diagonal Matrix), 우측엔 상삼각행렬(Upper Triangular Matrix)이 위치해있는 형태이다. 

- 3x3 case:

이제 3x3크기의 3차원 행렬을 생각해보자. 3x3크기의 행렬 A가 있다고 가정해보자. 이 행렬을 소거하기 위해 먼저 곱해야 할 E행렬은 E21일 것이다. 그 다음으로 E31, E32순으로 곱해서 소거를 해야 한다는 것을 이미 배웠다. 이때 Row exchange는 필요 없는 이상적인 경우로 가정한다. 이를 식으로 나타내면 아래와 같을 것이다. 

그 다음 단계는 왼쪽의 E행렬들을 없애서 A=의 꼴로 만들어야 한다. 식 (10)을 참고하여 식 (13)의 왼쪽에 E32, E31, E21순으로 역행렬들을 곱하여 아래와 같은 식으로 만들어준다. 결국 식의 우변은 E21*E31*E32의 역행렬들의 곱이 L이 된다. 

우리는 식 (13)에 각 E의 역행렬들을 곱하여 식 (14)의 A=LU형태의 식을 만들었다. 즉 행렬 A와 U간의 연결고리인 L을 만들어 낸 것인데, 사실 (13)의 앞에 곱해진 E도 A와 U의 연결고리라고 볼 수 있다. 결국 U를 만들기위한 방법은 E와 L 두 가지가 있는 셈인데, 결론적으로 보면 이 두 가지 방법중 L이 더 좋은 형태라고 볼 수 있다. 

다시말하면 

의 형태보다 

의 형태가 더 좋은 형태이다. 

지금부터 왜 두 번째 형태가 더 나은지 설명하겠다.

위에서 살펴봤던 2x2인 경우에는 E행렬이 단 한개라서 별다른 문제는 없다. 그러나 3x3은 다르다. 다음 A행렬을 보자. 

Linear Algebra Lecture 2를 참고하여 A 소거법을 적용해보자. 결과는 아래 식 (16)과 같아진다. 여기서 E31은 단위행렬이 되는데, 이렇게 되면 E31은 곱셈에서 무시해도 무방하다. 참고로 소거법의 특성상 E행렬들은 언제나 하삼각행렬의 형태이다. 이렇게 나오는 이유는 소거 과정에서 pivot의 row는 소거하지 않기 때문에 이와 같은 형태가 나오는 것이다. 

어쨋든 E행렬을 살펴보자. E32의 -5, E21의 -2는 E행렬에서 각자의 위치에 그대로 위치해있고 E행렬의 row3, column1의 자리에 10이라는 새로운 숫자가 생겨났다. 이것이 의미하는 것이 무엇일까? (-5와 -2는 소거 과정에서 pivot row에 곱해지는 multiplier임을 기억하자.) 

그 다음으로 L을 살펴보자. E21 역행렬의 2, E32 역행렬의 5가 L에서 각자 위치에 그대로 위치해 있고 따로 추가되는 숫자는 없다. 이것이 의미하는것이 무엇일까? 

행렬 E를 A에 곱하게 되면 E의 10은 A의 row1에 곱해지게 된다. 즉 10이라는 숫자가 A의 row1에 커다란 영향을 미친다는 것이다. 물론 답은 U가 그대로 나오게 된다. 그러나 그 연산 과정에서 A에 뭔가 큰 영향을 미치게 된다. 

반면 L의 경우엔 따로 추가되는 숫자 없이 2와 5가 각자의 자리에 위치한 상태로 L이 계산된다. 즉 10과 같이 뭔가 방해를 하는 숫자를 만들어내지 않는다는 것이다. EA=U와 달리 A=LU는 A를 신경쓰지 않아도 되는 것이다. 결국 A와 U의 연결고리로써 E보다는 L이 좀 더 나은 표현이다. 

A=LU Decomposition에서

만약 행 교환(row exchanges)이 없다면, 소거에 사용되는 multiplier들은 L행렬의 각자 위치에 그대로 들어간다. 

- Permutations:

지난 포스팅에서 잠깐 다룬적이 있던 치환행렬(Permutation Matrix)을 다시 살펴보자. 지금까지는 행 교환(row exchanges)이 필요 없는 경우를 가정하고 LU Decomposition을 설명했다. 그러나 행 교환이 필요한 경우가 반드시 생긴다. 이렇게 행 교환이 필요한 경우 사용하는 방법이 치환행렬을 곱해주는 것이다. 

3x3 치환행렬을 살펴보자. 

비록 아무런 변화가 없긴 하지만 단위행렬도 치환행렬의 한 종류이다. n=3인 정방행렬일 때 치환행렬의 종류는 어떤 것들이 있을까? 

먼저 P12를 생각해볼 수 있다. P는 Permutation의 P를 따온 것이고 12는 row1와 row2를 교환한다는 뜻이다. 

P13, P23을 어렵지않게 생각할 수 있는데, 이것 말고도 조합이 더 있다. 아래 식 (16)을 보자. 

P23에 P13을 곱한 행렬, 그리고 P23에 P12를 곱한 행렬을 생각할 수 있다. 각 치환 행렬을 row로 봤을 때, 각 row가 단위 행렬과 비교해서 몇 번째 줄에 위치했는지를 살펴보면 어느 row로 바뀌는지 쉽게 유추할 수 있다. 

이러한 치환 행렬의 조합의 개수는 어떻게 계산할 수 있을까? 바로 n!(factorial)로 계산한다. 즉 n=3일 경우, 3x2x1=6가지의 조합이 나오는 것이다. 

치환 행렬은 앞서 말했듯 row를 바꿔주는 역할을 하는 것이다. 그렇다면 다시 원래대로 되돌려 놓으려면 어떻게 해야 할까? 바로 역행렬을 곱해주면 되는데, 사실 원래 행렬과 역행렬은 같다. 왜냐하면 P12가 row1과 row2를 바꾸는 치환 행렬일 때 다시 원래대로 돌려 놓으려면 똑같이 row1과 row2를 바꿔주면 되기 때문에 다시 P12를 곱해주면 된다. 실제 계산해봐도 같은 결과가 나오는데, 이는 치환 행렬 자체가 대각 원소들을 기준으로 좌우가 대칭이기 때문이다. 이런 좌우 대칭인 경우 역행렬은 전치(Transpose)로 구할 수 있다. 

또한 P13P23은 P12P23과 역행렬 혹은 전치 관계인 것을 알 수 있다. 

우리는 행 교환이 필요한 A=LU Decomposition을 할 때 이러한 치환 행렬을 곱하여 PA=LU와 같은 꼴로 Decomposition을 할 수 있다.  

3. MATLAB 활용법

LU Decomposition을 MATLAB을 이용해 간단히 구할 수 있다. 아래는 위의 식 (15)를 MATLAB으로 구현한 코드이다. 

위 코드를 실행시키면 아래와 같은 결과가 나온다. 

위 결과에서 ans는 앞에서 계산한 L과 U를 곱하여 나온 결과 행렬이다. 원래의 A행렬과 똑같이 나오는 것을 볼 수 있다. 

MATLAB에서는 LU Decomposition을 위한 함수를 제공한다. 아래 코드는 MATLAB에서 제공하는 함수를 이용해 LU Decomposition을 수행하는 코드이다. 

함수 이름은 lu()이고 괄호안에 Decomposition을 할 함수를 파라미터로 넣으면 된다. 이때 좌변에 대괄호를 이용하여 출력 인수들을 정의해 줘야 한다. 첫 번째 방법은 L과 U만 출력 인수로 정의해준 것이다. 이에 대한 결과는 아래와 같다. 

결과를 보면 L의 경우 하삼각행렬 형태가 아닐 것이다. 왜 이렇게 나오는지에 대해서 이해하기 위해선 우선 다음의 정의를 이해해야 한다. 선형 시스템(Linear System)의 표현은 유일하지 않다. 아래 식을 보자. 

위의 식에서 첫 번째 식과 두 번째 식은 완전히 똑같은 시스템을 표현하고 있다. 여기서 좌변의 행렬의 행이 바뀌면 우변의 결과 벡터도 똑같은 순서로 행이 교환된다는 것을 기억하자. 

위의 개념을 생각했을 때, LU Decomposition은 사실 일반적으로 PA=LU와 같이 표현할 수 있다. 여기서 P는 치환 행렬(Permutation Matrix)를 의미한다. MATLAB에서 [L U] = lu(A)와 같이 L과 U만 출력인수로 정할 경우, L은 아래 식과 같이 정의 되어 나오는 것이다. 

(P는 대칭 행렬(Symmetric Matrix)이기에 역행렬은 전치(Transpose)와 같다)

즉 [L U] = lu(A)로 구한 L은 사실은 P'L인 것이다. 이는 L과 U를 곱했을 때 원래의 A행렬 형태가 나오도록 만들기 위해  치환 행렬을 L에 미리 곱해준 것이라 생각하면 된다. ans는 lu()함수로 구한 L과 U를 곱해서 나온 결과이고 원래의 A와 정확히 일치하는 것을 볼 수 있다. 

출력 인수를 [L U P] = lu(A)와 같이 L, U, P 세 개로 정의할 경우, L은 우리가 생각하는 하삼각행렬의 형태, 즉 P의 역행렬이 곱해지지 않은 형태로 L이 계산된다. 아래는 이에 대한 결과이다. 

L은 하삼각행렬, U는 상삼각행렬, P는 치환행렬이다. 즉 PA=LU형태로 계산 결과가 나오는 것이다. 이렇게 계산된 결과값을 이용해서 PA와 LU를 실제로 비교해보자. 정확히 같은 값이 나오는 것을 알 수 있다. 

그런데 우리가 손으로 계산한 결과들과는 실제로 값이 다르다. 이는 내부 계산과정에서 수치적으로 최적화된 계산 알고리즘을 통해 Decomposition을 하기 때문에 알고리즘마다 값이 약간씩 다르게 나올 수 있다. 어쨋든 결과적으로는 맞게 분해가 된 것이 맞다. 

MATLAB에서 제공하는 LU Decomposition함수는 이 외에도 다양한 파라미터들을 설정할 수 있다. 자세한 내용이 궁금하다면 구글에 검색을 해보거나 help명령어, 혹은 MATLAB 스크립트의 lu()함수에 마우스 커서를 놓고 Ctrl+D를 누르면 상세한 도움말을 볼 수 있다. 

4. 마치며

이번 포스팅에선 어떤 시스템 행렬 A를 L(Lower Triangular Matrix)과 U(Upper Triangular Matrix)로 분해(Decomposition)하는 방법을 배웠다. 이를 통해 A와 U사이의 관계를 이어주는 L행렬을 정의할 수 있었고 L과 소거 행렬 E와의 관계를 확인할 수 있었다. 또한 Row exchange가 필요한 경우 사용되는 치환행렬(Permutation Matrix)을 공부했고 이에 대한 전치(Transpose)도 공부하였다. 다음 포스팅에선 이 치환 행렬과 전치에 대해 좀 더 알아보도록 하자.