[MIT 18.065] 1.3. The Four Fundamental Subspaces

---

💡 이 글은 MIT의 선형대수학 강의 MIT 18.065 Spring 2018 및 Gilbert Strang 교수님의 책 『Linear Algebra and Learning from Data』을 따라 정리했습니다. 강의 내용과 일부 연습문제 풀이를 포함합니다.

1. The Four Fundamental Subspaces

1.1. Definition

4개의 기본적인 부분공간(fundamental subspace)의 정의는 다음과 같다.

Column space(열공간) $\mathbf{C} (A)$ : 행렬 $A$의 열의 선형결합으로 이루어진 공간
Row space(행공간) $\mathbf{C} (A^T)$ : 행렬 $A^T$의 열의 선형결합으로 이루어진 공간
Nullspace(영공간) $\mathbf{N} (A)$ : $Ax=0$의 해 $x$의 집합으로 이루어진 공간
Left nullspace(좌영공간) $\mathbf{N} (A^T)$ : $A^Ty=0$의 해 $y$의 집합으로 이루어진 공간

예를 들어 다음과 같은 rank one matrix $A$가 있다고 하자.

\[A = \begin{bmatrix} 1 & 2 \\ 3 & 6 \end{bmatrix}\]

이때 각 부분공간을 시각화하면 다음과 같다. 앞으로의 Figure는 다음 강의노트를 참고하였다.

이와 유사한 matrix $B$를 생각해보자.

\[B = \begin{bmatrix} 1 & -2 & -2 \\ 3 & -6 & -6 \end{bmatrix}\]

이때 column space와 left nullspace는 $A$의 것과 동일하고, row space는 $v = (1,-2,-2)$의 배수일 것이다. 이제 nullspace를 구하기 위해 $Bx=0$을 풀어보면 두 해 $x_1, x_2$를 얻을 수 있는 것을 알 수 있다.

\[x_1 = \begin{bmatrix} 2 \\ 1 \\ 0 \end{bmatrix}, \quad x_2 = \begin{bmatrix} 2 \\ 0 \\ 1 \end{bmatrix}\]

혹은 $Bx=0$에는 $n=3$개의 변수가 있고, independent equation은 $r=1$개이므로 independent solution은 $3-1=2$개라는 것으로도 해가 몇 개인지를 알 수 있다. 이를 counting law라고 한다.

Counting Law: $Ax=0$에 independent equation이 $r$개 있으면 independent solution은 $n-r$개이다.

Nullspace를 $x_1$, $x_2$가 span하는 것은 맞지만 nullspace에 있어 $x_1$, $x_2$는 좋은 basis 선택이 아니다. 이는 $x_1$과 $x_2$가 직교하지 않기 때문인데, 해결하기 위해 Gram-Schmidt process를 사용할 수 있다. 이를 사용하여 각각 orthonomal basis로 만든 뒤 nullspace, row space를 3차원에 나타내면 다음과 같다.

1.2. Application to Graph

이를 그래프에 적용해볼 수도 있다.

여기에서 $A$는 근접행렬(incidence matrix)으로, 출발하는 노드(node)를 -1, 도착하는 노드를 1로 표현한 행렬이다. 먼저 $Ax=b$로 식을 나타내보면 다음과 같다.

\[\begin{bmatrix} -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \end{bmatrix}\]

그래프를 일종의 전기회로(electric circuit)라고 생각한다면 다음과 같이 해석할 수 있다. 여기서 $x_1, x_2, x_3, x_4$는 각각 node의 전압(potential)이고, $b_1, b_2, b_3, b_4, b_5$는 각 node 사이의 전위차(potential difference)라고 해석할 수 있다. (예를 들면, $b_1 = x_2 - x_1$) 이 근접행렬의 각 부분공간의 의미를 생각해보자.

먼저 nullspace $\mathbf{N} (A)$를 생각해보자. 이는 $Ax=0$의 해 $x$의 집합으로 이루어진 공간이므로, 벡터 $x = (x_1, x_2, x_3, x_4)$라고 두고 $Ax = 0$을 풀어보면 해는 $x=(1,1,1,1)$임을 알 수 있다. 이는 당연한데, 각 node 사이의 전위차가 0이기 위해서는 모든 node의 전압이 같아야 하기 때문이다. 한편 nullspace의 dimension이 $n-r=1$인 것을 알았으므로, 남은 부분공간의 dimension도 모두 구할 수 있다. 먼저 rank $r=3$이기 때문에, column space와 row space의 dimension은 3이고, left nullspace의 dimension은 $m-r=2$이다. ($m=5, n=4$이다.)

다음으로 column space $\mathbf{C} (A)$를 생각해보자. 위에서 구한 대로 column space의 dimension이 $4$가 아니므로, 모든 column이 linearly independent하지 않다는 것을 알 수 있다. Column space는 $Ax=b$의 해 $x$의 집합으로 이루어진 공간이므로, 임의의 전위차 $b$가 주어졌을 때 이를 만족하는 전압 $x$를 구하는 문제라고 볼 수 있다. 그런데 column space의 dimension이 $3$이므로 $x_1, x_2, x_3, x_4$ 중 하나를 0으로 두고 계산해도 해를 구할 수 있다. 어차피 다른 column의 선형결합으로 표현될 수 있기 때문이다. 그리고 column space로부터 voltage law도 알 수 있는데, loop에 대해서 전위차의 합은 0이라는 것이다. (예를 들면, $b_1 - b_2 + b_3 = 0$)

이제 row space $\mathbf{C} (A^T)$를 생각해보자. Row space의 dimension은 $r=3$이므로 이미 dependent row가 있다는 것을 알 수 있고, 그 예시로 row 3 = row 2 - row 1이라는 것을 알 수 있다. 처음으로 서로 independent한 row 3개는 row 1, 2, 4이다. 각각이 뜻하는 것은 loop와 tree이다. Dependent row끼리는 서로 loop를 형성하고, independent row끼리는 서로 tree를 형성한다.

마지막으로 left nullspace $\mathbf{N} (A^T)$를 생각해보자. Left nullspace는 $A^Ty=0$의 해 $y$의 집합으로 이루어진 공간이다. 이를 행렬로 나타내보면 다음과 같다.

\[\begin{bmatrix} -1 & -1 & 0 & 0 & 0 \\ 1 & 0 & -1 & -1 & 0 \\ 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \end{bmatrix} = \begin{bmatrix} -y_1 - y_2 \\ y_1 - y_3 - y_4 \\ y_2 + y_3 - y_5 \\ y_4 + y_5 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}\]

이때 $y_1, y_2, y_3, y_4, y_5$는 각각 edge에 걸리는 전류(current)라고 볼 수 있고, $A^Ty$는 각 node로 들어오는 전류의 총합을 의미한다. 예를 들어 node 1에서 들어오는 전류의 총합은 (둘 다 빠져나가는 방향이므로 (-)가 붙어) $-y_1 - y_2$이다. 이것이 0이라는 것은 곧 들어가고 나가는 전류의 합이 0이라는 current law를 나타낸다고 해석할 수 있다. 그리고 left nullspace의 해를 직접 구해보면 $y^1=(1,-1,1,0,0)$과 $y^2=(0,0,-1,1,-1)$을 얻는다. 각각은 하나의 loop를 나타내며, 전체 전류는 $ay^1 + by^2$의 선형결합으로 나타낼 수 있다는 것을 알 수 있다.

1.3. Summary

지금까지 네 개의 부분공간을 알아보았고, 이를 “The big picture”로 정리하면 다음과 같다. 정말 유명한 그림이다.

2. The Ranks of $AB$ and $A + B$

여기서는 4개의 rank에 관한 statement를 다룬다.

Statement 1. Rank of $AB$ $\leq$ rank of $A$, rank of $AB$ $\leq$ rank of $B$
Statement 2. Rank of $A + B$ $\leq$ (rank of $A$) + (rank of $B$)
Statement 3. Rank of $A^T A$ = rank of $A A^T$ = rank of $A$ = rank of $A^T$
Statement 4. Let $A: m \times r$, $B: r \times n$, rank of $A$ = rank of $B$ = $r$, then rank of $AB$ = $r$

Statement 1은 자명한데, 이유는 $AB$의 column이 $A$의 column의 linear combination으로 표현될 수 있고, $AB$의 row가 $B$의 row의 linear combination으로 표현될 수 있기 때문이다. (확인하고 싶다면 1.2절을 참고하자.) Statement 2 역시 비슷한 방법으로 증명되는데, $A + B$의 column이 $A$의 column과 $B$의 column의 linear combination으로 표현될 수 있기 때문이다. Statement 3은 Problem 6에서 증명하겠다.

Statement 4는 다음과 같이 증명한다. Statement 3에 의해 $A^T A$와 $B B^T$의 rank는 $r$이고, 각각은 $r \times r$ matrix이기 때문에 invertible하다. 따라서 두 matrix의 곱 $A^T A B B^T$의 rank도 $r$이고, 동일하게 invertible하다. 이때 Statement 1에 의해 $r = \text{rank} (A^T A B B^T) \leq \text{rank} (AB)$이다. 그리고 다시 Statement 1에 의해 $\text{rank} (AB) \leq \text{rank} (A) = r$이므로, 결국 $\text{rank} (AB) = r$이다.

4. Selected Solutions to Problems

Problem 1.

Q. $\mathbf{N} (B) \subset \mathbf{N} (AB)$를 보여라.

$Bx=0$이면 $ABx=0$이므로 $\mathbf{N} (B) \subset \mathbf{N} (AB)$이다. 이로부터 $\text{rank} (AB) \leq \text{rank} (B)$인 것을 다시 한 번 알 수 있다.

그렇다면 $\mathbf{N} (A) \subset \mathbf{N} (AB)$도 성립할까? 이는 성립하지 않는다. 예를 들어 $A, B$를 다음과 같이 설정하자.

\[A = \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix}, B = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \quad \Rightarrow \quad AB = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}\]

그럼 $\mathbf{N} (A)$는 vector $u=(0,1)$의 span이고, $\mathbf{N} (AB)$는 vector $v=(1,-1)$의 span이므로 $\mathbf{N} (A) \not\subset \mathbf{N} (AB)$이다.

Problem 6.

Q. $\mathbf{N} (A^T A) = \mathbf{N} (A)$를 보여라.

먼저 $\mathbf{N} (A) \subset \mathbf{N} (A^T A)$임을 보이자. Problem 1과 같이 $Ax = 0$이면 $A^T A x = 0$이므로 $\mathbf{N} (A) \subset \mathbf{N} (A^T A)$이다.

이제 $\mathbf{N} (A^T A) \subset \mathbf{N} (A)$임을 보이자. $A^T A x = 0$이면 $x^T A^T A x = 0$이고, 이는 곧 $(Ax)^T (Ax) = \lVert Ax \rVert ^ 2 = 0$이므로 $Ax = 0$이다. 따라서 $\mathbf{N} (A^T A) \subset \mathbf{N} (A)$이다.

$\therefore \mathbf{N} (A^T A) = \mathbf{N} (A)$이다.

이제 더 나아가서 Statement 3을 증명하자. $A$가 $m \times n$ matrix라면 $A^T A$는 $n \times n$ matrix이고, 두 matrix의 nullspace가 같으므로 (즉 $n-r$이 같으므로) rank $r$도 같다. 따라서 $\text{rank} (A^T A) = \text{rank} (A) = r$이다. 그리고 Statement 1에 의해 $\text{rank} (A) = \text{rank} (A^T A) \leq \text{rank} (A^T)$이고, 이와 마찬가지로 $\text{rank} (A^T) \leq \text{rank} (A)$이므로 $\text{rank} (A) = \text{rank} (A^T)$이다.

Problem 8.

Q. $\mathbf{C} (A) = \mathbf{N} (A)$일 수 있는가? $\mathbf{C} (A) = \mathbf{N} (A^T)$일 수 있는가?

먼저, $\mathbf{C} (A) = \mathbf{N} (A)$일 수 있다. 다음과 같은 $A$에서는 $\mathbf{C} (A), \mathbf{N} (A)$ 모두 vector $u=(1,0)$의 span이다.

\[A = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}\]

그럼 $\mathbf{C} (A) = \mathbf{N} (A^T)$일 수 있을까? 이는 성립하지 않는다. $\mathbf{C} (A)$는 $Ax=b$를 만족하는 $Ax$의 집합이고, $\mathbf{N} (A^T)$는 $A^T y=0$을 만족하는 $y$의 집합이다. 이를 transpose하면 $y^T A = 0$이므로 $y^T Ax = 0$이고, 따라서 $y \perp Ax$이다. 즉, $\mathbf{C} (A) \perp \mathbf{N} (A^T)$이다. 따라서 $\mathbf{C} (A) = \mathbf{N} (A^T)$일 수 없다. 즉 다음과 같은 결론을 얻는다. (The big picture의 일부이다.)

$\mathbf{C} (A) \perp \mathbf{N} (A^T)$, $\mathbf{C} (A^T) \perp \mathbf{N} (A)$

MIT 18.065 카테고리 내 다른 글 보러가기