[응용선형대수] Understanding Ax=0, Ax=b using null space matrix

1. Ax=b와 Column space&Null space 관계

 

이 column space와 null space 개념을 통해 $Ax=b$에 대해 이해해볼 수 있습니다.

 

$\text{Given }Ax=b$

$\text{(i). C(A) provides information whether it has a solution. Ax=b has a solution }\Leftrightarrow$ $\begin{bmatrix}b_{1}\\b_{2}\\b_{3}\end{bmatrix}\in C(A)$

 

만약 b matrix가 column space of A($C(A)$)에 속해있다면 A의 column들의 선형 조합으로 b를 만들 수 있다는 뜻이므로, x가 존재합니다. (x는 A의 column의 선형 조합에서 계수에 해당하기 때문입니다.) 즉, solution이 존재합니다.

 

$A^{-1}$를 구해서 solution을 구할 수도 있겠지만 더 넓은 관점에서, unique solution이 아닐 경우에도 b matrix가 $C(A)$에 속해있는지를 확인함으로써 solution 여부를 확인할 수 있습니다.

 

 

$\text{(ii). Suppose that one can find }x_{p}\text{, such that }Ax_{p}=b$

$\text{a) For any }x_{n}\in N(A)\text{ then, }x_{p}+x_{n}\text{ is a solution.}$

$A(x_{p}+x_{n})=Ax_{p}+Ax_{n}=b+0=b$

 

null space에 $x_{n}$ 벡터가 속해있을 때 $x_{p}+x_{n}$은 solution이 될 수 있습니다.

 

$\text{b) if z is a solution, then }z-x_{p}\in N(A)$

$(\because A(z-x_{p})=Az-Ax_{p}=b-b=0)$

 

어떤 solution에 대하여 column space에 속하는 벡터 $x_{p}$를 빼면 null space에 속합니다.

 

이 성질들을 정리해보면, solution은 column space에 속해있는, 조건을 만족하는 벡터를 기본으로 하고, null space에 속한 벡터들을 더해진 것까지도 solution으로 볼 수 있다는 것입니다. 물론 null space가 영벡터 밖에 없는 상황이라면 column space에 있는 벡터만이 solution이 될 것입니다.

 

unique solution을 위해서는 null space에 영벡터 이외의 벡터가 존재하면 안된다고 생각해볼 수도 있습니다.

 

$\text{Example: }$

 

$\begin{bmatrix} 1&1\\2&2\\ \end{bmatrix} \begin{bmatrix}x\\z\end{bmatrix}=\begin{bmatrix}2\\4\end{bmatrix}$

 

$C(A)=\{a\begin{bmatrix}1\\2\end{bmatrix},a\in \mathbb{R}\}$

$N(A)=\{\begin{bmatrix}c\\-c\end{bmatrix},c\in \mathbb{R}\}$

 

$\bullet\text{ Is there a solution?}$

$\begin{bmatrix}2\\4\end{bmatrix}=2\begin{bmatrix}1\\2\end{bmatrix}\in C(A)$

 

 

$\bullet \text{ decribe all solutions}$

null space에 속한 벡터

$x_{n}=\begin{bmatrix}c\\-c\end{bmatrix}$이라고 할 때,

 

$\begin{bmatrix}1&1\\2&2\end{bmatrix}\begin{bmatrix}x\\z\end{bmatrix}=\begin{bmatrix}2\\4\end{bmatrix}$의 solution을 구하면 다음과 같습니다.

 

$\begin{bmatrix}x\\z\end{bmatrix}=x_{p}+x_{n}=\begin{bmatrix}1+c\\1-c\end{bmatrix}$

 

 

---

 

2. Solving Ax=0, Ax=b

 

 

위의 내용에 이어서 $Ax=0$, $Ax=b$를 풀 때의 개념을 좀 더 다루겠습니다.

 

$Ax=0$ $\Rightarrow N(A)=\{x|Ax=0 \}\text{ is a null space.}$

$Ax+b$ $\Rightarrow \text{There is a solution if }b\in C(A) \text{ and solution is }x_{p} and x_{n}\text{ where } Ax_{p}=b, X_{n}\in N(A)$

 

$\text{Null space of }A,u,R$

 

$A=\begin{bmatrix}* & * & \cdots & * & *\\ * & * & \cdots & * & *\\ * & * & \cdots & * & *\end{bmatrix}$

 

A가 일반 matrix라면 u는 echelon form, R은 Reduced echelon form입니다. (참고 : normal-engineer.tistory.com/60?category=964340)

 

$u=\begin{bmatrix}\bullet & * & \cdots & * & *\\ 0 & \bullet & \cdots & * & *\\ 0 & 0 & \cdots & * & *\end{bmatrix}$

$R=\begin{bmatrix}1 & 0 & * & \cdots & 0 & *\\ 0 & 1 & * & \cdots & 0 & *\\ 0 & 0 & 0 & \cdots & 1 & *\end{bmatrix}$

 

 

A matrix를 row operation을 통해 u, R 형태로 만들었다면

 

$Ax=0 \Leftrightarrow ux=0 \Leftrightarrow Rx=0 (\rightarrow \text{same null space})$

 

같은 null space을 공유하고 있습니다. row operation은 null space에 영향을 미치지 않습니다.

 

---

3. null space matrix

 

$\begin{bmatrix}1&3&0&2\\0&0&1&1\\0&0&0&0\end{bmatrix}\begin{bmatrix}u\\v\\w\\y\end{bmatrix}=0$

 

어떤 matrix $ $$\begin{bmatrix}1&3&0&2\\0&0&1&1\\0&0&0&0\end{bmatrix}$$ $의 null space를 구하고자 합니다.

이 matrix의 경우 첫 번째 row의 1과 두 번째 row의 1이 pivot이 되고, 이 pivot은 변수 u,w에 대응됩니다.

pivot이 없는 두 변수 v,y는 free variable이라고 합니다.

 

위의 식을 풀면

$u=-3v-2y$

$w=-y$

 

으로 정리할 수 있습니다.

 

$\begin{bmatrix}u\\v\\w\\y\end{bmatrix}=\begin{bmatrix}-3v-2y\\v\\-y\\y\end{bmatrix}=v\begin{bmatrix}-3\\1\\0\\0\end{bmatrix}+y\begin{bmatrix}-2\\0\\-1\\1\end{bmatrix}$

여기서 왜 v와 y가 free variable로 정해진 이유를 알 수 있습니다. v와 y는 pivot이 없어서 정해지지 않고 자유롭게 정할 수 있는 변수가 되기 때문입니다.

 

$\Rightarrow \text{N(A) is spanned by }\begin{bmatrix}=-3\\1\\0\\0\end{bmatrix}\text{ and }\begin{bmatrix}-2\\0\\-1\\1\end{bmatrix}$

 

N(A)는 두 벡터의 spanning space가 됩니다. 이를 통해 null space matrix를 정의합니다.

 

$\text{Definition : }$

$\begin{bmatrix}=-3&-2\\1&0\\0&-1\\0&1\end{bmatrix}$

$Ax=0 \text{, where }A\in \mathbb{R}^{m\times n}, x\in \mathbb{R}^{n\times 1}$

 

$\text{Theorem : }$

$\text{If n>m, there are infinite many solutions}$

$\text{cf) } Ax=0 \Leftrightarrow Rx=0$

 

$\begin{bmatrix}a_{11} & a_{12} & a_{13} &a_{14}\\ a_{21}& a_{22} & a_{23} & a_{24}\\ a_{31} & a_{32} & a_{33} & a_{34}\end{bmatrix}$

위와 같이 n이 m보다 큰 경우를 생각해봅시다. 위 matrix은 3(row)<4(column)인 경우입니다.

$\text{Number of pivots}\leq m$ 위 matrix의 경우에는 3보다 더 많은 pivot이 있을 수 없습니다.

$\text{Number of free variable }=n-\text{number of pivots}>0$

 

$n>m$일 때 free variable은 항상 1개 이상 존재합니다. 따라서 항상 solution이 무수히 많습니다. free variable은 자유롭게 변할 수 있는 변수이기 때문에 

위의 예시였던 $\begin{bmatrix}1&3&0&2\\0&0&1&1\\0&0&0&0\end{bmatrix}\begin{bmatrix}u\\v\\w\\y\end{bmatrix}=0$와 동일하게 해가 무수히 많은 것입니다.

 

또한 앞으로 $r$이라는 문자를 $\text{rank of A = number of pivots}$ 의미로 사용하겠습니다.

 

rank는 number of pivots입니다.

 

---

다음부터는  linear independence, basis, dimension 개념에 대해서 알아보겠습니다.