지난 포스팅(Lecture 7)에선 선형방정식(Linear equation) Ax=0의 해(solution)인 Null space를 계산하는 법에 대해서 배웠다. 이번 포스팅에서는 우변에 값이 존재하는 형태의 선형방정식 Ax=b의 완전해(complete solution)에 대해 알아보자.
1. Ax=b의 해(solution)
어떤 선형방정식 Ax=b에 대한 해가 존재할 수도 있고 존재하지 않을 수도 있다. 해의 존재 여부를 우리는 소거법(Elimination)을 통해 판별할 수 있으며, 만약 해가 존재한다면 이 식에 대한 유일해(unique solution)나 해의 전체 집합을 알아내는 것이 우리의 목적이다.
지난 강의(Lecture 7)에서 Null space를 구할 때 사용했던 행렬을 이용하여 해를 구해보도록 하자. 이번에는 우변이 0이 아닌 어떤 값 b가 존재하는 경우다. 아래 식 (1)은 지난번에 사용했던 행렬을 방정식의 형태로 나타낸 것이다.
식 (1)의 방정식에서 좌변을 살펴보면 row3는 row1+row2와 같은 것을 알 수 있다. 그렇다면 이 선형방정식의 해가 존재하기 위해선 우변의 b1, b2, b3는 어떤 값이 와야 할까? b1=1, b2=5일 때 b3는 아무런 값이 되어도 상관없을까? b3=8인 경우엔 해가 존재하는가?
결론적으로 이 경우엔 해가 존재하지 않는다. 해가 존재하기 위해선 좌변의 경우와 마찬가지로 b3가 b1+b2이어야 한다. 즉 b3=1+5=6이 되어야 해가 존재한다.
결국 좌변의 어떤 선형 결합의 결과가 0이 된다면(row1+row2-row3=0), 우변의 같은 선형 결합도 0이 되어야 해가 존재한다.
이제 실제로 위의 선형방정식의 소거를 통해 결과를 살펴보자. 기존에 우변이 0일 때는 좌변의 계수만 행렬로 만들었지만 우변에 어떤 값 b가 존재할 경우 b를 행렬의 오른쪽에 붙여서 Augmented matrix를 만든다. 아래는 b를 붙여서 만든 Augmented matrix의 모습이다.
이제 소거를 해보자. 첫 번째 pivot을 기준으로 [row2=row2-2*row1], [row3=row3-3*row1]을 해주면 아래와 같이 된다. 오른쪽의 b도 같은 상수를 곱해서 동일한 방식으로 계산해주면 아래의 행렬과 같이 된다. 이때 pivot variable이 있는 첫 번째와 세 번째 column이 pivot column이 되고 나머지 두 번째와 네 번째 column이 free column이 된다.
아직 두 번째 pivot variable(row2, col3)의 아래 원소가 전부 0이 아니므로 [row3=row3-row2]를 통해 소거하면 row3는 모두 0이 된다. 이때 우측의 b항은 아래와 같이 계산된다.
소거를 마친 최종적인 U행렬은 아래와 같다.
위의 식(5)에서 마지막 줄(row3)의 방정식을 살펴보자. 좌변은 계수들이 전부 0이다. 이것은 무엇을 의미하는가? 바로 우변의 값은 b3-b2-b1=0 이 되어야 한다는 것을 쉽게 알 수 있다. 계수가 전부 0이기 때문에 어떤 변수를 곱해도 결과는 당연히 0이 될 수 밖에 없다. 이것을 우리는 해가 존재하기 위해 필요한 조건인 가해 조건(solvability condition)이라 한다. 이 가해 조건이 만족되어야만 이 선형방정식의 해가 존재하는 것이다.
가해 조건이 만족되려면 b가 어떤 값이 되어야만 할까? b2와 b1을 우변으로 이항하면 b3=b2+b1과 같이 될 것이다. 즉 b2와 b1의 합이 b3와 같은 크기여야 한다. 이는 앞서 행렬 A의 좌변의 계수들이 row3=row2+row1과 같기 때문이다.
그렇다면 b는 어떤 값이 오면 될까? 결과적으로 b1=1, b2=5, b3=6 일 때 식이 성립됨을 알 수 있다. 이때의 row3의 우변 값은 0이 되어서 식이 성립함을 알 수 있다.
이와 같이 b에 대한 가해 조건(solvability condition)이 만족 되었기에 해가 존재하고 우리는 4개의 미지수에 대해 2개의 식으로 해를 구할 수 있다.
그런데 식 (6)에서 나타난 가해 조건(solvability condition)은 일반적인 조건이 아니다. 이것은 식(1)의 선형방정식에 해당되는 내용에 관한 것이다. 그렇다면 이를 일반적인 b에 대한 가해 조건으로 표현하면 어떻게 될까? 이는 아래와 같다.
b에 대한 가해조건(Solvability Condition on b):
똑같은 말을 약간 다르게 표현해보자.
|
결국 Ax=b의 선형방정식에서 b에 대해 위의 가해 조건이 충족되어야만 해가 존재한다. 위의 가해 조건을 확인해보는 것은 결국 이 선형방정식이 해가 존재하는지를 확인해보는 작업이다.
2. Ax=b의 완전해(complete solution)
Ax=b의 해가 존재하는지 확인했으면 그 다음은 해를 구하는 과정을 알아내는 것이다. 즉 해를 구하는 과정인 알고리즘을 알아봐야 한다.
이제 Ax=b의 완전해(complete solution)를 구하는 알고리즘을 살펴보자. 크게 두 단계가 있는데 아래와 같다.
|
: 특수해(particular solution) x를 찾는다. 모든 free variable을 0으로 설정한 뒤, pivot variable에 대해 Ax=b를 푼다. 
: Null space해(Null space solution)를 찾은 뒤 특수해와 더해준다. 즉 
이다.
- 1) 특수해(particular solution):
첫 번째 과정은 Ax=b에 대한 특수해(particular solution) x를 찾는 것이다. 여기서 특수해라는 것은 소거를 마친 행렬 U에서 free variable을 모두 0으로 만든 다음 pivot variable에 대해서 구한 해를 의미한다. 위의 행렬 A에 대한 특수해를 실제로 구해보자. 우선 식 (7)을 선형방정식의 형태로 다시 써보면 아래 식의 오른쪽과 같다.
식 (8)에서 free variable은 식(7)에서 pivot이 없는 free column에 대응하는 x값들이다. 즉 x2와 x4가 free variable이다. 이들은 0으로 설정하면 식(8)은 (9)와 같이 되고, 후방대입법(back substitution)을 이용해 나머지 값들을 구하면 해는 x1=-2, x3=3/2가 된다.
따라서 Ax=b에 대한 특수해는 아래와 같다.
- 2) Null space solution:
첫 번째 단계인 특수해를 구했으니 이제 Null space 해를 구할 차례이다. Null space의 해는 알다시피 Ax=0을 만족시키는 x이며, 완전해를 계산하기 위한 두 번째 단계이다. 그런데 이번 포스팅에서 사용하는 행렬 A는 지난 강의 Lecture 7에서 사용했던 행렬이다. 지난 강의에서 우리는 이 행렬 A에 대한 special solution을 구한적이 있다.
special solution은 위의 행렬 A에서 두 개의 free variable중 하나를 1, 나머지 하나를 0으로 만들고 pivot에 대해 계산하고, 반대로 0, 1로 설정하여 각각 계산한 두 개의 해이다. free variable이 두 개 이기 때문에 그 개수만큼 special solution이 만들어진다. 이 special solution 두 개의 선형 결합(Linear combination)이 Null space 전체를 표현하기 때문에 이 special solution들을 그대로 사용하도록 하겠다. 사실 이 special solution이 아닌 Null space상에 존재하는 어떠한 벡터를 사용해도 상관없다!
special solution의 해를 구하는 자세한 과정은 지난 강의(Lecture 7)를 참고하고 결과적으로 해는 아래와 같다. special solution역시 Null space상에 존재하는 해이기 때문에 완전해를 구하기 위한 두 번째 해로 사용하도록 하겠다.
두 special solution의 선형 결합이기 때문에 각 해의 앞에 상수c를 각각 곱해준다.
- 3) Complete solution:
두 개의 해(particular, complete solution)를 구했으니 이제 완전해(complete solution)을 구할 차례이다. 완전해는 앞서 언급했듯이 특수해(particular solution)와 Null space해를 더해주면 된다. 이를 식으로 표현하면 아래와 같다.
xp는 particular solution을, xn은 Null space solution을 각각 의미한다.
그렇다면 완전해(complete solution)구하기 위해 이러한 조합을 사용하는 이유는 무엇일까? 아래 식을 보자.
Axp=b에서 b가 A의 column space상에 존재한다면 이 선형방정식은 해가 존재한다. 이때 이 해에 우리는 Null space상에 존재하는 어떤 벡터를 더해도 되는데 이유는 식 (13)이 성립하기 때문이다. 즉 Null space에 대한 선형방정식의 우변은 0이다. 따라서 이 두 방정식을 더한다고 해도 우변은 b가 그대로 오기 때문에 수학적으로 가능한 이야기이다.
식(1)의 Ax=b에 대한 완전해(complete solution)는 특수해와 Null space해를 더한 형태인 아래 식(14)가 된다.
다시 한 번 이야기 하지만 Null space해 전체는 두 개의 special solution의 선형 조합으로 표현이 되고, special solution이 두 개인 이유는 free variable이 두 개이기 때문이다.
여기서 Null space해는 유일해가 아니기 때문에 subspace인 Null space전체를 표현하기 위해 각각에 상수 c1, c2가 곱해져 있는 것을 볼 수 있다.
그렇다면 특수해(particular solution)에도 상수 c가 곱해질 수 있을까?
정답은 No다.
식 (13)을 보면 특수해의 경우는 Ax=b의 해를 구하는 것이고 우변의 b가 특정 값으로 정해져 있다. 따라서 우리는 이 식을 만족시키는 어떤 특수한 해를 구하는 것이기 때문에 상수를 곱해선 안된다.
반면 Null space의 해의 경우엔 space라는 말처럼 Ax=0의 해들의 집합이 공간을 이루는 형태이다. 즉 부분 공간(subspace)이기 때문에 여러 개의 해가 존재할 수 있고 따라서 다양한 해들을 정의할 수 있도록 상수를 곱해주는게 가능하다.
사실 애초에 우변 벡터 b가 0이 아닌 임의의 상수일 땐 해에 대한 부분 공간을 정의할 수 없다고 이미 Lecture 6의 후반부에서 언급하였다. 결론적으로 Ax=b의 완전해는 어떤 하나의 특정해(particular solution)와 Null space해인 부분 공간(subspace)의 합으로 표현될 수 있다.
- Plot of Complete solution:
위에서 완전해에 대한 설명은 했는데, 사실 말과 수식만으로는 잘 이해가 가지 않을 수 있다. 그림으로 이해를 돕도록 하자. 완전해를 그려야 하는데 다시 보니 4차원 공간 R4이다. 필자의 머리로는 4차원 공간을 이 포스팅 공간에 그려넣을 방법이 생각나지 않지만 아인슈타인은 4차원 공간을 그렸다고 하니 따라해보도록 하자.
이것이 x1, x2, x3, x4로 이루어진 4차원 공간의 plot이다. 왜 이렇게 그려져야 하는지는 필자도 잘 이해가 가지 않는다. 차원이라는 것은 높은 차원이 이전의 모든 차원에 직교(Orthogonal)해야 한다. 4차원에서 4번 째 벡터가 1,2,3번 째 벡터를 어떻게 직교하는지는 잘 모르겠지만 일단 넘어가도록 하자.
위 그림에서 Null space라고 하는 평면은 식 (14)에서 뒤쪽의 상수 c1, c2가 곱해진 두 개의 벡터로 형성되는 평면이다(두 벡터의 선형 결합으로 형성되기 때문에 평면의 형태가 됨). 원래 Null space만 있었다면 이는 R4의 원점을 지나는 부분 공간(subspace)이 된다. 그러나 xp가 더해졌기 때문에, 혹은 xp에 Null space가 더해진 형태이기 때문에 결과적으로 Null space가 xp만큼 shift된 형태가 된다. 즉 원점이 아닌 xp를 지나는 Null space인 것이다. 결국 원점을 지나지 않기 때문에 더이상 부분 공간(subspace)이 아니다.
위 그림에서 빨간색 벡터와 빨간색 점은 xp를 나타내고 xn은 Null space 평면에 존재하는 어떤 벡터를 나타낸다. 이 둘을 더하면 우리가 구하고자하는 완전해(녹색 벡터)인 x_complete(=xp+xn)를 구하게 된다.
3. Rank
지금까지 우리는 선형방정식 Ax=b의 완전해를 구하는 방법을 공부하였다. 여기서 예를 든 행렬 A의 형태는 3x4크기에 pivot variable이 2개, free variable이 2개 있는 형태이고, 이때의 rank는 2이다. 이제 이 예제를 넘어 좀 더 큰 그림을 생각해보자. 행렬의 형태와 크기, 그리고 rank에는 어떠한 상관관계가 있을까?
m by n 크기에 rank r을 갖고 있는 행렬 A가 있다고 가정해보자. m은 row의 수, n은 column의 수이고 r은 rank의 수이다. rank는 앞서 언급했듯이 pivot variable의 개수이다. 이때의 rank는
을 만족한다.
r=n일 때를 Full column rank라 하고, r=m일 때를 Full row rank라 한다. 이때 다음 질문을 한 번 생각해보자.
Full column or Full row rank일 때,
- 이는 해(solution)에 관해 무엇을 암시하는가?
- 이는 Null space에 대하여 무엇을 말하고 있는가?
- 이는 완전해(complete solution)에 대하여 무엇을 말하는가?
Rank에 대한 각 case별로 해(solution)와 어떤 상관관계를 가지는지 한 번 살펴보도록 하자.
- Full column rank (r=n):
Full column rank는 r=n을 의미한다. 즉 rank가 column의 개수와 같으며, 모든 column이 pivot을 가지고있다. 이때 중요한 것은 Full column rank일 때 free variable이 없다는 것이다. free variable이 없기 때문에 행렬 A의 Null space는 오직 영벡터(zero vector)뿐이다. 즉 각 column의 선형 조합으로 0을 만들 수 있는 해 x는 오직 zero vector 뿐이다.
그렇다면 해(solution)는 어떨까? 해가 존재한다면 유일한 해(unique)가 존재하게된다. 이를 정리하면 아래와 같다.
| Full column rank (r=n) | |
| Rank | =n (number of columns) |
| Free variable | No free variable |
| Null space | only zero vector |
| Solution | 0 or Unique solution |
글 만으로는 이해가 어려울 수 있으니 실제 예제를 통해 Full column rank의 형태를 살펴보도록 하자. Full column rank를 보여주기에 적절한 형태인 4x2 행렬을 보자. 소거를 통해 Reduced row echelon form으로 가기까지의 과정을 모두 나타내도록 하겠다. 혹시 소거 과정이 잘 이해가 가지 않는다면 지난 강의를 다시 보길 바란다.
식 (15)의 마지막 줄 우측의 행렬이 바로 A의 Reduced row echelon form이다. 결과적으로 row3와 row4는 소거를 통해 영벡터가 되었다. 이는 row3와 row4는 row1과 row2에 dependent하기 때문이다. 즉 row3와 row4는 row1과 row2의 선형 조합으로 만들어진다. 결국 independent한 row는 row1과 row2뿐이다.
이제 Ax=b의 해(solution)에 대해 알아보도록 하자. Full column rank일 때 해는 아예 존재하지 않거나, 혹은 유일해(unique solution)가 존재한다. 이는 free variable을 모두 0으로 만들어서 구한 특수해(particular solution)를 의미하며, 식(15)의 행렬 A는 free variable이 없기 때문에 해가 존재할 경우 바로 특수해가 된다.
그렇다면 이 행렬 A에 대해 Ax=b는 b가 어떤 값이어도 해가 존재할까? 정답은 No다.
일단 Ax=0인 Null space를 살펴보면 해가 영벡터인 경우를 제외하고 어떠한 column 조합으로도 우변을 0으로 만들 수는 없다.
Ax=b인 경우에도 역시 항상 해가 존재하지는 않는다. 해가 존재하기 위해선 b가 A의 column들의 선형조합으로 만들어지는 column space에 존재해야한다.
따라서 해가 존재하기 위해선 b가 A의 column들의 선형조합으로 만들 수 있는 값이어야 한다. 세 가지만 예를 들어보겠다.
위와 같이 A의 column space에 존재하는 해들의 경우엔 각 b에 대한 특수해(particular solution) 혹은 유일해(unique solution)가 존재한다.
이를 MATLAB으로 확인할 수 있다. 행렬 A와 b가 설정되어 있을 때 해(x)를 구하는 명령어는 x=A\b이다. 아래의 코드를 참조하여 상수값을 바꿔가며 확인해 보도록 하자.
- Full row rank (r=m):
이번에는 Full row rank를 살펴보도록 하자. r=m, 즉 rank와 row의 수가 일치하는 경우이다. 모든 row가 pivot을 가지는 경우이다.
그렇다면 모든 b에 대해 해를 가지는가? 즉 Ax=b에서 b가 어떤 값을 가지더라도 해를 가질 수 있는가? 정답은 Yes이다. 항상 해가 존재한다. 그렇다면 이때 free variable은 몇 개일까? n-r개 이다. 위에서 예를 들었던 행렬 A의 Transpose의 형태를 가지고 이해를 해보도록 하자.
소거를 통해 행렬 A의 Reduced row echelon form을 만들었다. 왼쪽의 col1과 col2가 pivot columns을 나타내며 단위 행렬(Identity)의 형태를 띄는 것을 볼 수 있다. 오른쪽의 col3과 col4는 free column을 나타낸다. 여기에선 Full row rank, 즉 row의 숫자와 rank의 숫자가 같기 때문에 zero rows는 없다.
결론적으로 free variable이 두 개가 존재하기 때문에 항상 해가 존재하며 special solution이나 Null space해도 존재한다. Full row rank에 대해 정리하면 아래와 같다.
| Full row rank (r=m) | |
| Rank | =m (number of rows) |
| Free variable | n-r or n-m |
| Null space | Exist |
| Solution | Exist for every b |
마찬가지로 MATLAB으로 확인해볼 수 있다. 아래 코드를 참고하여 constant를 바꿔가며 해가 맞는지 확인해보도록 하자.
- Full row and column rank (r=m=n):
마지막으로 살펴볼 case는 가장 중요한 case라고도 볼 수 있다. 바로 rank가 m와 n과 같은 경우다(r=m=n). 즉 정방행렬(square matrix)이면서 Full rank인 경우를 말한다. 바로 예를 들어 이해해보자.
식 (18)의 행렬 A는 2x2크기의 정방행렬이다. A대한 Reduced row echelon form은 단위 행렬과 같은 것을 알 수 있다. 이 경우엔 A는 역행렬을 가질 수 있다(Invertible).
이 경우에 Null space는 존재하는가? 오직 zero vector만 존재한다.
모든 b에 대한 Solution은 존재하는가? b에 대한 유일해(unique solution)가 존재한다.
Full row and column rank에 대해 정리하면 다음과 같다.
| Full row and column rank (r=m=n) | |
| Rank | =m=n (number of rows and columns) |
| Free variable | No free variable |
| Null space | only zero vector |
| Solutions | 1 unique solution |
아래는 Full row and column rank에 대한 MATLAB 코드이다.
4. 마치며
이번 포스팅에선 선형방정식의 완전해(complete solution)를 구하는 방법에대해 배웠다. 완전해를 구하기 위해선 어떤 행렬 A에 대한 유일해를 구하고 Null space를 구하여 이 둘을 더해줘야 한다는 것을 알았다.
또한 우리는 Rank에 따라 해(solution)가 어떻게 정의되는지, rank와 row와 column의 수가 어떠한 관계를 가지고 있는지에 대해 배웠다. 아래는 Rank에 따른 해와 상관관계를 한 번에 정리한 표다.
r : rank
m: number of rows
n : number of columns
| r=m=n | r=n<m | r=m<n | r<m, r<n |
Reduced row echelon form: - Square invertible case - Ax=b에 대해 오직 하나의 해만 존재함 |
Reduced row echelon form:  - 해가 아예 없거나 - 오직 하나의 유일해(Unique solution)만 존재 |
Reduced row echelon form:  (※ F can be mixed to the I)- 항상 해가 존재한다. - 무한대(  )의 해가 존재 |
Reduced row echelon form: (※ F can be mixed to the I)- 해가 아예 없거나 - 무한대( )의 해가 존재 |
이 말을 기억하자.
Rank는 해의 실제 값들을 제외하곤 해의 모든 것들을 말한다.