Rank-Nullity Theorem과 그 이면의 구조에 대하여

https://en.wikipedia.org/wiki/Rank%E2%80%93nullity_theorem

 

 

 

자연과학에서 이론의 근거는 관찰과 실험이다.

수리과학에서는 그것을 '계산'이라고 부른다.

─ 조건희

 

 

몸풀기

 

아래 선형 연립 방정식을 풀어보자.

 

 

 3개의 식 사이에 더하기/빼기를 할 수 있다. $x_1$을 하나만 남기기 위해 1번 식의 2배를 2번 식에서 뺀다.

 

 

$x_2$와 $x_5$는 이제 바꿀 방법이 없다. 이번엔 $x_3$을 하나만 남기기 위해 2번 식의 2배를 1번 식에 더하고, 2번 식의 4배를 3번 식에 더한다.

 

 

마지막으로 $x_4$는 마지막 식에서만 남긴다. 계수는 1로 맞춘다. 

 

 

여기까지의 과정을 elementary row operation이라고 부르며 최종 형태를 reduced-row echelon form이라고 부른다. 미지수가 5개인데 식이 3개이므로 해가 유일하지 않으며, 2개의 자유변수가 필요함을 우리는 경험적으로 알고 있다. 위의 경우 $x_3=x_4=0$은 고정이고, $x_1$은 $x_2$와 $x_5$에 의존되어 결정된다. $x_2$와 $x_5$가 자유변수가 되며, reduced-row echelon form에서 각 행의 leading term을 뺀 나머지가 자유변수가 됨을 관찰할 수 있다. 이 연립 방정식의 일반해를 아래와 같이 쓸 수 있다.

 

 

또는 벡터 표현을 이용하여 아래와 같이 쓸 수도 있다.

 

 

선형 연립 방정식 중 상수항(등호 뒤)이 모두 0인 것을 homogeneous linear system이라고 부른다. 모든 homogeneous linear system은 적어도 하나의 해를 갖는다. 모든 미지수가 0이면 된다. 상수항이 하나라도 0이 아닌 것을 inhomogeneous linear system이라고 부른다. 

 

 

방식은 앞과 똑같다. Reduced-row echelon form은 아래와 같으며,

 

 

$x_2$와 $x_5$가 자유변수임은 변함이 없다. 해는 아래와 같이 구할 수 있다.

 

 

일반해의 형태를 보면 homogeneous인 경우와 상수항 부분만 다름을 알 수 있다. 

 

 

특수해와 일반해

 

Homogeneous linear system과 inhomogeneous linear system은 각각 아래의 형태를 갖는다.

 

 

$Ax = b$가 해를 갖는다(consistent)고 가정하자. 만약 $x_p$가 $Ax = b$의 해라면, 여기에 $Ax = 0$의 임의의 해를 더해도 여전히 $Ax = b$의 해가 된다. 왜냐하면, $Ax = 0$의 임의의 해 $x_h$에 대해서

 

 

이기 때문이다. 앞의 예시에서도 아래 방정식의 해는

 

 

$x_1 = 6$, $x_2 = 0$, $x_3 = 2$, $x_4=3$, $x_5 = 0$으로 특정할 수 있고, 여기에 $Ax = 0$의 해를 더한 것이 정확히 위 방정식의 해가 되었다. Homogeneous linear system $Ax=0$의 해를 일반해, inhomogeneous linear system $Ax = b$의 하나의 해를 특수해라고 부른다. 하지만 궁금증이 하나 생긴다. $Ax  = b$를 풀었는데 일반해 파트가 $Ax = 0$의 해와 형태가 다를 수도 있지 않은가? 예를 들어 아래 방정식에서

 

 

내 마음대로 $x_1$과 $x_2$를 자유변수로 두어도 방정식의 해는 구할 수 있다.

 

 

다르게 표현된 두 해는 사실상 같은 해여야 한다. 그걸 어떻게 알 수 있는가? 이 계산의 이면에는 무엇이 숨어있을까?

 

 

Nullity

 

행렬은 선형 사상이다. 앞에서 보았던 문제에서 $A$는 3 x 5 실수 행렬이므로 $\mathbb{R}^5$가 정의역, $\mathbb{R}^3$가 공역이 된다. 정의역의 부분집합 중 $Ax = 0$을 만족하는 집합을 solution space 또는 nullspace라고 부른다. 벡터공간은 덧셈에 대한 아벨군이고 행렬은 두 벡터공간 간의 homomorphism이므로 nullspace는 kernel이기도 하다. 앞으로는 nullspace 대신 kernel이라는 단어를 쓰도록 하겠다. 임의의 m x n 행렬에 대해서 kernel은 $\mathbb{F}^n$의 부분공간(subspace)이 된다. $Ax = 0$을 만족하는 두 해를 더해도 $Ax = 0$의 해가 되고, 하나의 해에 스칼라배를 해도 $Ax = 0$의 해이기 때문이다. 벡터공간의 부분공간도 벡터공간이므로 차원이 정의되고 기저를 잡을 수 있다. 사실 앞에서 풀었던 아래 방정식의 해에서

 

 

이미 kernel의 차원과 기저가 드러나 있다. 차원은 자유변수의 개수와 같으며, 기저는 위에 적혀있는 두 벡터이다. Kernel의 차원을 nullity라고 부른다. 앞에서 $Ax = b$의 해를 두 가지 방법으로 표현했었다. ($Ax = b$의 해집합은 부분공간이 아니다.)

 

 

 

이 둘은 같은 해의 다른 표현에 불과하다. 따라서 아래 둘은 같은 공간이어야 한다.

 

 

일반적으로 $Ax = b$의 해를 아래와 같이 두 가지 표현으로 쓴다면,

 

 

$\text{span}\{u_i\}$와 $\text{span}\{v_i\}$는 같은 공간이어야 하며, $u_i$는 $v_i$들의 선형결합으로 나타낼 수 있고 반대도 가능하다. 또한 $Au_p = Av_p$으로부터 $u_p - v_p$가 $\ker A$의 원소임도 알 수 있다. 즉, $Ax = b$의 모든 해는 서로 $\ker A$만큼 차이가 난다. 이것은 $Ax = b$의 해집합이 $\ker A$를 평행이동한 것임을 암시한다. (스포일러: 이것은 추상대수학에서 어떤 구조에 대응될까?)

 

 

Rank

 

앞에서 풀었던 선형 연립 방정식을 $Ax = 0$ 또는 $Ax = b$로 놓는다면, 행렬 $A$는 아래와 같다.

 

 

여기에 5x1 벡터를 곱하는 것은 행렬 $A$의 각 column들을 선형결합하는 것과 같다. 따라서 $\text{Im}\, A$은 절대 3차원을 넘을 수 없다. 행렬의 rank는 아래와 같이 정의된다.

 

 

즉, rank는 행렬의 row 중 선형독립인 것의 최대 개수이다. Elementary row operation은 row끼리 더하고 빼는 것에 불과하므로 row space의 차원을 바꾸지 않는다.(column space는 바꾼다.) 그리고 행렬의 row space와 column space의 차원은 같으므로 (증명은 연습문제로 남긴다.) 행렬의 rank는 column space의 차원이기도 하다. 위 행렬 $A$의 reduced-row echelon form은 아래와 같으므로,

 

 

이 행렬의 rank는 3이고 $\text{Im}\, A$는 3차원이다. 행렬의 모든 row가 선형독립이면 full row rank, 행렬의 모든 column이 선형독립이면 full column rank라고 부른다. 위 행렬 $A$는 3 x 5이므로 full row rank는 될 수 있지만 full column rank는 절대 될 수 없다. 이 행렬이 rank가 3인 것은 각 row의 leading 1이 3개인 것과 같은 뜻이며, 자유변수가 2개임을 의미한다. 따라서 kernel은 2차원이고 $\text{Im}\, A$는 3차원이다.

 

 

Rank-Nullity Theorem

 

3 x 5 행렬에서 nullity와 rank를 더하여 5가 되는 것은 우연이 아니다. 이는 아래와 같은 법칙을 따른다.

 

 

이것을 Rank-Nullity Theorem이라고 부른다. 행렬을 row echelon form으로 바꿨을 때 각 row의 leading 1의 개수가 row space의 차원, 즉 rank이고 leading 1이 아닌 것의 개수가 자유변수의 개수, 즉 nullity가 된다. 따라서 행렬에 대해서 Rank-Nulltiy Theorem은 당연한 결과이다. 이것을 벡터공간 간의 선형 사상으로 일반화할 수 있다. 어떤 선형 사상 $T: V \to W$가 있다고 하자. $V$와 $W$는 각각 n차원, m차원 벡터공간이다.(n, m < $\infty$) 이제 $V$와 $W$의 적절한 기저 $\beta$와 $\gamma$를 잡아서 $T$의 행렬표현을 만들 수 있다.

 

 

선형 사상의 rank는 기저에 의존하지 않는다. 따라서 선형 사상의 rank는 $\text{Im} T$로 정의된다. Nullity는 kernel의 차원이다. 아래 그림이 Rank-Nullity Theorem을 참 잘 표현한다.

 

https://en.wikipedia.org/wiki/Rank%E2%80%93nullity_theorem

 

 

Back to abstract algebra

 

선형대수학에서 다루는 대상들은 군론의 언어로도 풀 수 있어야 한다. 아래는 군론과 선형대수학의 용어들을 매칭시킨 것이다.

 

 

군론의 몇 가지 중요한 결과들을 복습해보자.

 

 

Review: Group Theory

 

$(G, *)$가 group이고 $H \le G$라고 하자. $G$의 원소들에 아래와 같은 relation을 주면,

 

 

이것은 equivalence relation이 된다.(증명은 연습 문제로 남긴다.) Equivalence relation이 있다면 quotient set을 만들 수 있다. 이 relation으로 quotient 시키는 것을 $G/H$라고 쓰자. $G/H$를 그림으로 그리면 아래와 같은데,

 

 

$H$를 포함하여 각 조각은 coset이며, 

 

* 한 coset의 모든 원소들은 서로 relate 되어 있다. 자기 자신과도 related이다.

* 서로 다른 coset 간에는 어떤 원소도 relate 되어 있지 않다. 

 

만약 $G$의 어떤 subgroup $N$이 있고 $G/N$이 $*$에 대해 다시 군이 된다면, $N$을 normal subgroup이라고 부르고 $N\unlhd G$으로 표기한다. $G/N$이 군이 되려면 coset 간의 연산이 잘 정의되어야 하는데, 이것은 normal subgroup의 정의인

 

$$ \forall g\in G, \forall n \in N, gng^{-1} \in N$$

 

와 동치이다.(증명은 연습문제로 남긴다.) 만약 $G$가 아벨군이면 모든 subgroup은 normal이다.

 

 

Review: Group Homomorphism

 

 

군 $G$와 $H$에 대해서 어떤 group homomorphism $\varphi: G\to H$가 주어졌다고 하자. 이때 $\ker \varphi$은 normal이다.(증명은 연습문제로 남긴다.) The 1st isomorphism theorem은 아래와 같이 기술된다.

 

 

 

이것이 정말 isomorphism인지 확인하려면 아래를 모두 확인해야 한다.

 

* $\bar{\varphi}$가 잘 정의된다.

* $\bar{\varphi}$가 group homomorphism이다.

* $\bar{\varphi}$가 injective이다.

* $\bar{\varphi}$가 surjective이다.

 

아래 셋은 연습문제로 남기고, 잘 정의됨만 확인해보자. 이것이 잘 정의되려면 한 coset의 두 원소 $g_1$과 $g_2$에 대해 $\varphi(g_1)$과 $\varphi(g_2)$가 같아야 한다. 그런데 두 원소는 $g_1^{-1}g_2 \in \ker \varphi$를 만족하므로,

 

 

를 통해 $\bar{\varphi}$가 잘 정의됨을 알 수 있다.

 

 

선형 사상, kernel, 공간의 차원

 

다시 선형 사상을 보자.

 

 

벡터공간은 덧셈에 대해 아벨군이고, 선형 사상 $T$는 group homomorphism이며 $\ker T$는 $V$의 normal subgrup이다. 따라서 the 1st isomorphism theorem에 의해 아래가 성립해야 한다.

 

 

그런데 $\ker T$가 $V$의 normal subgroup이므로 $V / \ker T$도 군, 여기서는 벡터공간이어야 한다. 벡터공간이라면 차원이 정의되어야 하고 기저도 있어야 한다. 이 경우 차원과 기저를 어떻게 정할 수 있을까? 우선 $V$의 기저를 아래와 같이 잡자.

 

 

여기서 $\{u_1, \cdots, u_k \}$는 $\ker T$의 기저이다. $G$가 군이고 $N\unlhd G$일 때 coset을 $gN$의 형태로 썼었다. 그대로 대입을 해보면, $V / \ker T$의 coset은 $v + \ker T$라고 쓰면 된다. 그리고 coset간의 연산이 그러했듯이, $v_1 + \ker T + v_2 + \ker T = v_1 + v_2 + \ker T$이다. 그런데 $\beta$에서 $n-k$개의 $v_i$들 중 서로 다른 2개를 꺼내면 아래를 만족해야 한다.

 

 

만약 두 벡터의 차가 $\ker T$의 원소이면 $\beta$의 선형독립성이 깨지기 때문이다. 따라서 $v_i + \ker T$들은 모두 독립적인 coset이 된다. 따라서 $V / \ker T$의 기저는 $\{v_i + \ker T\}$가 될 것이라 추측할 수 있다. 기저인지 확인하려면 두 가지를 확인해야 하는데, 선형독립임은 이미 확인했으므로 이 집합이 $V / \ker T$를 span 함만 보이면 된다. $V$의 임의의 원소는 $\beta$의 원소들의 선형결합으로 쓸 수 있다.

 

 

여기에서 $\{u_i, \cdots , u_k\}$로 span 되는 부분은 자연스럽게 $\ker T$에 흡수되면서, $x$는 아래 coset의 원소가 된다.

 

 

$V / \ker T$의 임의의 원소는 위와 같은 형태로 표현되므로, 결과적으로 $\{v_i + \ker T\}$는 $V / \ker T$의 기저가 된다. 기저의 원소의 개수가 그 공간의 차원이므로, $V / \ker T$은 n-k차원이다. 이것을 일반화하여, 만약 $U \le V$이면 $V/U$도 벡터공간이며 차원은 아래와 같다.

 

 

선형사상의 kernel은 정의역의 subspace이다. 그렇다면 역으로 임의의 subspace는 어떤 linear operator의 kernel일까? 조금만 생각해보면 자명함을 알 수 있다. 벡터공간 $V$의 subspace $U$에 대해, $V$의 기저를 아래와 같이 잡는다.

 

 

여기서 $\{u_1, \cdots, u_k \}$는 $U$의 기저이다. 이제 선형 사상 $T: V\to V$를 아래와 같이 잡으면 된다.

 

 

이것은 $V$의 벡터를 $\text{span} \{v_{k+1}, \cdots, v_n\}$으로 projection 한 것으로 볼 수 있다. 여기서 $b_i$를 다른 실수로 바꿀 수도 있으므로 이러한 선형 사상은 유일하지 않음도 알 수 있다.

 

 

부록

 

Proposition: 행렬의 row space의 차원과 column space의 차원은 같다.

 

증명) 행렬에 elementary row operation을 하는 것은 행렬의 앞에 어떤 elementary matrix를 곱하는 것으로 볼 수 있다. 행렬을 reduced-row echelon form으로 만들기 위해 보통은 여러 개의 elementary matrix를 필요로 하지만, 그것들을 하나로 뭉쳐서 하나의 행렬 $E$를 곱했다고 보아도 무방하다. 행렬 $A$의 reduced-row echelon form을 $R$이라고 하면 아래가 성립한다.

 

 

행렬 $R$은 아래와 같이 생겼는데,

 

 

여기서 pivot(leading 1)의 개수가 행렬 $A$의 rank이자 row space의 차원이다. 어떤 행렬 $A$의 rank가 $k$라고 하자. Pivot 위치의 column들은 서로 선형독립이다. 이 coumn들의 번호를 $j_1, \cdots, j_k$라고 하자. 행렬 $R$의 column을 $r_{j_i}$라고 표시하면 아래 집합은 선형독립이다.

 

 

이제 pivot 위치의 $A$의 column들도 선형독립임을 보일 것이다. 즉, 아래를 보이면 된다.

 

 

만약 $\xi_1 a_{j_1} + \cdots + \xi_k a_{j_k} = 0$에 nontrivial solution이 존재한다고 하자. 그런데 $Ea_{j_i} = r_{j_i}$이므로, $\xi_1 r_{j_1} + \cdots + \xi_k r_{j_k} = 0$도 nontrivial solution이 존재하게 되어 모순이다. 따라서 아래 집합도 선형독립이고

 

 

$A$의 column space의 차원은 적어도 $k$보다는 크거나 같다. 즉, 아래가 성립한다.

 

 

여기에 $A$ 대신 $A^t$를 넣어도 무방하다.

 

 

그런데 $A^t$의 row space는 $A$의 column space이고, $A^t$의 column space는 $A$의 row space이다. 따라서 아래가 성립하며

 

 

결과적으로 행렬의 column space의 차원과 row space의 차원은 같다.

 

 

Proposition: 유한차원 벡터공간 간의 선형변환에 대해 kernel의 차원과 image의 차원의 합은 정의역의 차원과 같다.

 

 

위와 같은 선형변환을 생각하자. $T$의 kernel은 $V$의 subspace이므로 기저를 잡을 수 있다. $\ker T$를 $k$차원이라 하고 $V$의 기저를 아래와 같이 잡자.

 

 

여기서 $\{u_i\}$는 $\ker T$의 기저이다. 이제 $V$의 임의의 벡터 $x$는 아래와 같이 쓸 수 있다.

 

 

이것을 $T$에 실어 보내면 $\ker T$에 해당되는 부분은 0이 되므로 아래와 같다.

 

 

이제 $T(v_i)$들이 서로 선형독립임을 보일 것이다. 아래 방정식을 생각하자.

 

 

위 식은 아래 벡터가 $\ker T$의 원소라는 의미이다. 

 

 

여기서 $v_i$들은 kernel의 원소가 아니므로 이 벡터가 kernel에 들어갈 방법은 모든 $b_i$들이 0인 것밖에 없다. 따라서 $T(v_i)$들은 선형독립이다. 이제 $\text{Im} \; T$의 임의의 원소들을 $n-k$개의 선형독립인 벡터들의 선형결합으로 나타낼 수 있으므로, $\text{Im} \; T$는 $n-k$차원이다. 따라서 선형변환 $T$의 kernel의 차원 $k$과 $\text{Im} \; T$의 차원 $n-k$을 더하면 정의역의 차원 $n$이 된다. 이 $\text{Im} \; T$의 차원을 $T$의 rank라고 정의한다.

 

 

 

끗.