[Linear Algebra] Lecture 8, 선형방정식 Ax=b의 완전해(complete solution)와 Rank

Introduction

이번에 선형대수를 공부하면서 내용을 정리해보았습니다.

강의 영상 : https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/

Video Lectures | Linear Algebra | Mathematics | MIT OpenCourseWare

스터디 github : https://github.com/jwkweon/study-linear-algebra

GitHub - jwkweon/study-linear-algebra

참고한 블로그 :

https://blog.naver.com/PostView.naver?blogId=skkong89&logNo=221390714301&categoryNo=48&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postList&userTopListOpen=true&userTopListCount=30&userTopListManageOpen=false&userTopListCurrentPage=1 

Lecture 8: Solving Ax = b: row reduced form R

 

https://twlab.tistory.com/22

[Linear Algebra] Lecture 8 선형방정식 Ax=b의 완전해(complete solution)와 Rank

(주로 https://twlab.tistory.com/22블로그의 사진과 내용을 보면서 공부했고 추가로 나머지 블로그를 참고하였습니다.)

(저는 제가 이해하기 쉽게 요약해서 적었으므로 좀더 자세히 공부하고싶다면 위 블로그를 참고하시면 됩니다.)

---

Ax=b의 해(solution)

지난 강의에서는 Ax=0의 해인 Null space를 계산하는 법을 배웠다. 이번에는 Ax=b의 해를 구해보자.

Ax=b에 대한 해는 존재할 수도 있고 존재하지 않을 수도 있다. 해의 존재여부를 소거법을 통해 판별할 수 있으며,

만약 해가 존재한다면 식의 유일해(unique solution)나 해의 전체 집합을 알아내는 것이 목적이다.

다음과 같은 연립방정식이 있다고 해보자.

$$ \begin{align} x_1 + 2x_2 + 2x_3 + 2x_4  & = b_1 \\ 2x_1 + 4x_2 + 6x_3 +8 x_4 &= b_2 \\ 3x_1 + 6 x_2 + 8x_3 + 10x_4 &= b_3 \end{align} $$

위의 식을 보면 row1+row2 = row3임을 알 수 있다. 따라서, 해가 존재하려면 우변도 $b_1 + b_2 = b_3$이어야 한다.

결국, 좌변의 어떤 선형 결합의 결과가 0이 된다면(row1+row2-row3=0), 우변의 같은 선형 결합도 0이 되어야 해가 존재한다.

 

이제 위 방정식을 행렬로 소거를 진행해보자. 이제는 우변이 영벡터가아니므로 Augmented matrix를 만들어 소거하자.

이제부터는 소거할때 b벡터도 같은 row에 포함시켜서 소거하면된다. 자세한 방법은 이전강의를 참고하자.

$$ \begin{bmatrix} (1) & 2 & 2 & 2 & | & b_1 \\ 2 & 4 & 6 & 8 & | & b_2 \\ 3 & 6 & 8 & 10 & | & b_3 \end{bmatrix} $$

소거를 진행하면 다음과 같고, 2개의 pivot column과 2개의 free column이 생긴다.

$$ \begin{bmatrix} (1) & 2 & 2 & 2 & | & b_1 \\ 0 & 0 & (2) & 4 & | & b_2 - 2b_1 \\ 0 & 0 & 0 & 0 & | & b_3 - b_2 - b_1 \\ p.c & f.c & p.c & f.c & & \end{bmatrix} $$

위의 소거를 통해 알 수있는 점이 있다. 바로 row3의 미지수의 계수들이 전부 0이다. 그러므로 당연히 row3 방정식의 결과는 0일 수 밖에 없으므로  $b_3 - b_2 -b_1 = 0$이 될 수 밖에 없다는 것을 알 수 있다.

이것을 우리는 해가 존재하기 위해 필요한 조건인 가해 조건(solvability condition)이라 한다.

이 가해 조건이 만족되어야만 이 선형방정식의 해가 존재하는 것이다.

즉, 맨처음에 row3=row2+row1에서 유추했듯이 소거를 통해서도 $b_3 = b_2 + b_1 $임을 찾아낼 수 있다.

따라서, Ax=b의 방정식이 해가 존재하려면 b에 대한 가해조건(solvability condition)을 만족해야한다.

하지만, 이 조건은 일반적인 조건이 아니다. 위 방정식의 대한 조건이다. 따러서, 좀더 일반화를 하면 다음과 같다.

 

b에 대한 가해조건(Solvability Condition on b):

• 우변의 b벡터가 행렬 A의 column space안에 존재할 때, 선형방정식 Ax=b는 해가 존재한다.
• 행렬 A의 row의 어떤 선형 결합이 zero row를 만들어낸다면, b에 대한 똑같은 선형 결합도 반드시 0이 되어야한다.
  (zero row의 의미는 어느 한 row가 다른 row에 dependent하다는 의미)

---

Ax=b의 완전해(complete solution)

이제 Ax=b의 해가 존재하는지 확인했으니 해를 구해보자.

Ax=b의 완전해(complete solution)을 구하는 단계에는 두 단계가 있다.

• $x_{particular}$ : 특수해(particular solution) x를 찾는다. 모든 free variable을 0으로 설정한 뒤, pivot variable에 대해
  Ax=b를 푼다.
• $x_{nullspace}$ : Null space해(Null space solution)를 찾은 뒤 특수해와 더해주어야 완전해(complete solution)가 된다. 즉, 완전해(x)는 $x= x_p + x_n$이다.

1) 특수해(particular solution)

먼저, 특수해 x를 찾아보자. 특수해라는 것은 소거를 마친 행렬 U에서 free variable을 모두 0으로 만든 다음 pivot variable에 대해서 구한 해를 의미한다. 위에서 사용하던 A행렬을 소거한 U행렬을 그대로 써보자.

여기서 $b_3 = b_2 + b_1 $의 가해조건을 만족하기위해 $b_3 = 6$, $b_2 =5$, $b_1=1$로 설정하고 풀어보자.

$$ \begin{bmatrix} (1) & 2 & 2 & 2 & | & 1 \\ 0 & 0 & (2) & 4 & | & 3 \\ 0 & 0 & 0 & 0 & | & 0 \\ p.c & f.c & p.c & f.c & & \end{bmatrix} $$

위 식을 방정식으로 표현하면

$$ \begin{align} x_1 + 2 x_2 + 2x_3 + 2x_4 &= 1  \\ 2x_3 +  4x_4 &=3 \end{align} $$

여기서 pivot column에 대응되는 $x_1$, $x_3$는 pivot variable이 될 거고

free column에 대응되는 $x_2$, $x_4$는 free variable이 될 것이다. 즉, 이들 free variable에 0을 대입하면 된다.

따라서, 방정식은 다음과 같이 바뀐다.

$$ \begin{align} x_1 + 2x_3 &= 1  \\ 2x_3  &=3 \end{align} $$

이제 후방 대입법으로 구하면 $x_1 = -2$, $x_3 = {3 \over 2}$가 될 것고, $x_2 = 0$, $x_4 = 0$일 것이다.

따라서, Ax=b의 특수해는 다음과 같다.

$$ x_{particular} = \begin{bmatrix} -2 \\ 0 \\ {3 \over 2} \\ 0 \end{bmatrix}$$

 

2) Null space 해(Null space solution)

특수해를 구했으니 2번째 단계인 Null space해를 구해보자. Null space해는 여태까지 배워왔던 Ax=0을 만족시키는 x의 해 집합이다. 참고로 위의 A행렬은 Lecture 7에서 special solution을 구한적이 있다. 자세한 풀이는 Lecture7을 사용하고 그때의 결과만을 가져오겠다.

$$ x_{nullspace} = c_1 \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + c_2 \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} $$

참고로, 위의 두개의 벡터 즉, 위 special solution이 두개의 선형 결합(Linear combination)이 Null space 전체를 표현하기 때문에 이 special solution이 아닌 Null space상에 존재하는 독립적인 아무 두 벡터를 사용해도 상관없다.

 

3) 완전해(Complete solution)

완전해는 다음과 같이 특수해와 Null space 해를 더해주면 된다.

$$ x = x_p + x_n $$

그렇다면 왜 이렇게 두개의 덧셈이 완전해가 되는걸까? 아래 식을 봐보자.

$$ \begin{align} Ax_p &=b \\ + Ax_n &=0 \\ -------&--- \\ A(x_p + x_n) &=b \end{align} $$

$Ax_p = b$에서 b가 A의 column space상에 존재한다면 이 선형방정식은 해가 존재한다.

이 해에 우리는 Null space상에 존재하는 어떤 벡터를 더해도 되는 이유는 위 식이 성립하기 때문이다.

왜냐하면 Null space에 대한 선형방정식의 우변은 0이기 때문에 b에 영향을 끼치지 않기 때문이다.

 

따라서, Ax=b에 대한 완전해는 다음과 같다.

$$ x_{complete} = \underset{x_{particular}}{\begin{bmatrix} -2 \\ 0 \\ {3 \over 2} \\ 0 \end{bmatrix}} + \underset{x_{null \ \ space \ \ special \ \ solution}}{c_1 \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + c_2 \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}} $$

Null space 해 전체는 두 개의 special solution의 선형 조합으로 표현이 되고, special solution이 2개인 이유는 free variable이 2개이기 때문이다. 또한, Null space해는 유일해가 아니기 때문에 subspace인 Null space 전체를 표현하기 위해 각각에 상수 $c_1$과 $c_2$가 곱해져 있는 것을 볼 수 있다.

 

그렇다면 특수해에도 상수 c가 곱해질 수 있을까? 정답은 아니다.

 

특수해는 Ax=b의 해를 구하는 것이고 우변 b가 특정 값으로 정해져 있다. 따라서 우리는 이 식을 만족시키는 어 떤 특수한 해를 구하는 것이기 때문에 상수를 곱해선 안된다.

반면 Null space의 해의 경우엔 space라는 말처럼 Ax=0의 해들의 집합이 공간을 이루는 형태이기 때문에 부분 공간(subspace)이기 때문에 여러 해가 존재할 수 있고 따라서 다양한 해들을 정의할 수 있도록 상수를 곱해주는게 가능하다.

 

애초에 우변 벡터 b가 0이 아닌 임의의 상수일 때 해에 대한 부분 공간을 정의할 수 없다고 배워왔다.

 

4) Plot of complete solution

이번에는 완전해를 실제 공간상에서 확인해보자. 다음은 4차원 공간 $R^4$인데 4차원 공간은 아인슈타인이 아닌 이상 그릴 수 없으니 대충 아래와 같다고 해보자.

4차원 공간의 축을 이루는 $x_1$, $x_2$, $x_3$, $x_4$가 서로 직교한다고 해보자.

우리는 $c_1$과 $c_2$가 곱해진 두 개의 벡터의 선형결합으로 Null space를 찾았었다. Null space는 반드시 원점을 지나야 하는데 Null space 해에 특수해 $x_p$가 더해져서 원점을 지나는 Null space를 $x_p$만큼 위로 들어 올렸다고 생각하면 위와같은 완전해의 집합을 볼 수 있다.

($x_n$은 Null space상에 있는 어떤 벡터이다.)

결국, 완전해의 집합은 원점을 지나지 않기 때문에 더이상 부분 공간(subspace)이 아니다.

---

Rank

위에서 구한 A행렬은 3x4크기에 pivot variable이 2개, free variable이 2개 이며, Rank=2라고 했다.

이제 좀더 Rank에 대해 배워보자. 과연 행렬의 형태와 크기 그리고 Rank에는 어떠한 상관관계가 있을까?

 

mxn크기에 rank r을 갖고 잇는 행렬 A가 있다해보자.

m : row의 수

n : column의수

r : Rank = pivot variable의 수 (단, $r \le m $, $ r \le n$을 만족)

r=m일 때, Full row Rank라 하고, r=n일 때, Full column Rank라 한다.

 

자 이제, Rank에 대한 각 case별로 해와 어떤 상관관계를 가지는지 알아보자.

 

1) Full column Rank (r=n)

Full column Rank는 Rank가 A의 column의 개수와 같으며, 모든 column이 pivot을 가지고 있다.

따라서, Full column Rank일 때는 free variable이 없다는 것이다.

free variable이 없기 때문에 A의 Null space는 오직 영 벡터(zero vector)뿐이다.

따라서, Null space가 이렇기 때문에 해는 유일한 해(unique)가 존재하게 된다.

 

Rank : n (A의 column의 수)

Free variable : 0

Null space : 오직 영 벡터

Solution : 0 or unique solution

 

한번 예시로 살펴보자. 다음과 같은 4x2의 A행렬이 있고 소거를 통해 Reduced row echelon form(rref)를 만들어보자.

$$ A = \begin{bmatrix} 1 & 3 \\ 2 & 1 \\ 6 & 1 \\ 5 & 1 \end{bmatrix} \longrightarrow U = \begin{bmatrix} (1) & 3 \\ 0 & (-5) \\ 0 & 0 \\ 0 & 0 \end{bmatrix} \longrightarrow rref(A) = \begin{bmatrix} (1) & 0 \\ 0 & (1) \\ 0 & 0 \\ 0 & 0 \end{bmatrix} $$

위 행렬을 분석해보면 row3과 row4는 0으로 소거됬는데 이는 row1과 row2에 dependent하기 때문이다.

따라서, independent한 row는 row1과 row2뿐이다.

 

또한, Ax=b의 해를 구해보자. Full column Rank일 때 해는 아예 존재하지 않거나, 혹은 유일해가 존재한다.

이는 free variable을 모두 0으로 만들어서 구한 특수해를 의미하며, A는 free variable이 없기 때문에 해가 존재할 경우 바로 특수해가 된다.

 

b는 어떤 값이어도 해가 존재할까? 정답은 존재하지 않는다.

일단 Ax=0인 Null space를 보면 영벡터인 경우를 제외하고 어떠한 column의 조합으로 우변을 0으로 만들 수 없다.

Ax=b인 경우에도 항상 해가 존재하지 않는다. 해가 존재하기 위해선 b가 A의 column들의 선형조합으로 만들어지는 column space에 존재해야한다. 즉, A의 column들의 선형조합이 b가 되어야하며 이것이 가해조건이다.

$$ b = 0 \begin{bmatrix} 1 \\ 2 \\ 6 \\ 5 \end{bmatrix} + 0 \begin{bmatrix} 3 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$

$$ b =1 \begin{bmatrix} 1 \\ 2 \\ 6 \\ 5 \end{bmatrix} + 1 \begin{bmatrix} 3 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 4 \\ 3 \\ 7 \\ 6 \end{bmatrix} $$

위는 A의 column들의 선형조합으로 만든 b가 될 수있는 가해조건의 예시이다.

위와 같이 A의 column space에 존재한느 해들의 경우엔 각 b에 대한 특수해(particular solution) 혹은 유일해(unique solution)가 존재한다.

 

2) Full row Rank (r=m)

Full row Rank는 모든 row가 pivot을 가지는 경우다.

그렇다면 모든 b에 대해 해를 가지는가? 즉 Ax=b에서 b가 어떤 값을 가지더라도 해를 가질 수 있는가?

정답은 가질 수 있다. 즉, 모든 b에 대해 항상 해가 존재한다는 것이다.

Full row Rank의 free variable은 n-r개이다. 다음과 같이 위에서 썼던 A의 Transpose 형태를 가지고 풀어보자.

$$ A= \begin{bmatrix} 1 & 2 & 6 & 5 \\ 3 & 1 & 1 & 1 \end{bmatrix} \longrightarrow U = \begin{bmatrix} (1) & 2 & 6 & 5 \\ 0 & (-5) & -17 & -14 \\ p.c & p.c & f.c & f.c \end{bmatrix} \longrightarrow rref(A) = \begin{bmatrix} (1) & 0 & - \frac{4}{5} & -  \frac{3}{5} \\ 0 & (1) & \frac{17}{5} & \frac{14}{5} \\ p.c & p.c & f.c & f.c \end{bmatrix} $$

소거를 통해 A의 Reduced row echelon form을 만들었다. 왼쪽의 pivot column들이 단위 행렬 형태를 띄는 것을 볼 수 있다.

여기서, Full row Rank, 즉 row의 숫자와 Rank의 숫자가 같기 때문에 zero rows는 없다.

결론적으로 free variable이 2개 존재하기 때문에 항상 해가 존재하며 special soultion이나 Null space해도 존재한다.

 

Rank : m (A의 row의 수)

Free variable : n-r

Null space : 존재

Solution : 모든 b에 대해 존재

 

3) Full row and column Rank (r=m=n)

마지막 case가 가장 중요한 case다. 바로 Rank가 m, n과 같은 경우이다.

즉, 정방행렬(square matrix)이면서 Full Rank인 경우를 말한다. 다음과 같은 예를 봐보자.

$$ A = \begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix} \longrightarrow U = \begin{bmatrix} (1) & 0 \\ 0 & (-5) \end{bmatrix} \longrightarrow rref(A) = \begin{bmatrix} (1) & 0 \\ 0 & (1) \end{bmatrix} = R = I $$

위 A행렬은 2x2의 정방행렬이다. A의 Reduced row echelon form이 단위 행렬과 같은 것을 알 수 있다.

이 경우엔 A는 역행렬을 가질 수 있다(invertible).

이 경우에 Null space는 오직 zero vector만 존재하며,

모든 b에 대한 Solution은 존재하지않고, b에 대한 유일해(unique solution)가 존재한다.

 

Rank : m=n (A의 column, row의 수)

Free variable : 0

Null space : 오직 영 벡터

Solution : 0 or unique solution

---

결론

이번에 선형방정식의 완전해(complete solution)을 구하는 방법에 대해 배우고, Rank에 대해 배웠다.

Rank에 따른 해와 상관관계를 요약하면 다음과 같다.

1) r=m=n

$ rref(A)=R= I $

Ax=b에 대해 오직 하나의 해만 존재

 

2) r=n (<m)

$ rref(A) = R = \begin{bmatrix} I \\ 0 \end{bmatrix} $

해가 아예 없거나, 오직 하나의 유일해(unique solution)만 존재

 

3) r=m (<n)

$ rref(A) = R = \begin{bmatrix} I & F \end{bmatrix} $ (여기서, $F$는 $I$와 섞일 수 있음)

항상 해가 존재하며, 무한대의 해가 존재.

 

4) r<m, r<n

$ rref(A) = R = \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix} $ (여기서, $F$는 $I$와 섞일 수 있음)

해가 아예 없거나, 무한대의 해가 존재

 

즉, Rank와 행, 열의 관계를 통해 해의 실제 값들을 제외한 해의 모든 것을 대표해서 설명해준다.