행렬의 rank와 nullity

퇴화 공간

$A$가 singular가 아니면 역행렬 $A^{-1}$을 곱할 수 있으므로 $Ax=0$의 원소는 $0$뿐이며, 모든 $b$에 대해서 $Ax=b$의 해가 존재한다. 이는 가우스 소거법에서 알 수 있는 결과이다. 그러나 $A$가 singular이거나 $n\times m$인 직사각 행렬일 때는 $Ax=0$의 원소가 무수히 많은 경우가 흔한 일이다. 또한 이 경우에 해들은 벡터 공간을 이룬다는 사실을 관찰할 수 있다. 행렬 $A$에 대해서 $Ax=0$의 해들을 모은 것을 $A$의 null space(영 공간, 퇴화 공간) 또는 kernel(핵)이라고 한다. 벡터 표현을 열벡터로 고정할 때 $x^TA=0^T$의 해들을 모은 것을 $A$의 left null space 또는 cokernel(여핵)이라고 한다. 이는 $A^Tx=0$의 해들을 모은 것과 같으므로 $A^T$의 null space이다.

$A$가 singular이고 무수히 많은 해를 가질 때에 모든 해를 구하는 방법은 $A$를 독립인 부분과 종속인 부분으로 나누어 독립인 부분의 해가 유일하고 종속인 부분의 해가 $Ax=0$이라는 사실을 이용하는 것이다. 예를 들어 연립일차방정식 $\begin{pmatrix}1 & 2 \\ 4 & 8\end{pmatrix}\begin{pmatrix}x_1\\ x_2\end{pmatrix}=\begin{pmatrix}4\\ 16\end{pmatrix}$은 무수히 많은 해들 가운데 $(1,\ 3/2)$를 particular solution으로 잡은 다음 $x_1+2x_2=0$가 null space를 이루므로 그 원소들 $(2c,\ -c)$을 더하여 $(1+2c,\ 3/2-c)$를 complete solution으로 삼을 수 있다.

이 과정을 보다 체계화하여 모든 행렬에 적용하기 위해서 직사각 행렬의 Gaussian elimination을 생각할 수 있다.

모든 pivot이 각 행의 첫 번째 성분이 되게 하고, 모든 pivot의 왼쪽과 아래쪽은 모두 $0$이 되게 소거법을 쓴다.

위와 같이 소거한 행렬을 $A$의 echelon form(사다리 꼴)이라고 한다. 또한 Gauss–Jordan elimination을 생각할 수 있다.

모든 pivot의 위쪽을 모두 $0$이 되게 하고, 모든 pivot이 $1$이 되게 소거법을 쓴다.

위와 같이 소거한 행렬을 $A$의 reduced row echelon form, RREF(기약 행 사다리 꼴)라고 한다. 이는 row canonical form이 되는 유일한 행렬이다. pivot이 없는 열의 성분은 RREF로 소거되지 않는다. RREF에서 pivot이 있는 열에 대응하는 변수 $x_i$를 pivot variable이라고 한다. pivot이 없는 열에 대응하는 변수 $x_j$는 free variable(자유 변수)이다.

행렬 $A$에 대해서 RREF의 pivot variable의 개수를 $A$의 rank(계수)라 하고 $\rank A$로 쓴다. free variable의 개수는 $A$의 nullity라 한다. $A$의 rank가 $r$이고 nullity가 $m-r$이면 $Ax=b$의 모든 해는, 모든 자유 변수들을 $0$으로 놓아 particular solution $x_r$을 구한 것에, 자유 변수 $c_i$를 $1$로 놓아 $A$의 null space의 벡터 $v_i$를 구하여 $c_iv_i$들을 더한 것이다. 식으로 나타내면 $x=x_r+c_1v_1+c_2v_2+\cdots+c_{m-r}v_{m-r}$이다. 예를 들어 $Ax=b$의 RREF가

$\displaystyle \begin{bmatrix} 1 & a_{12} & 0 & a_{14} \\ 0 & 0 & 1 & a_{24} \\ 0 & 0 & 0 & 0\end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4\end{bmatrix}=\begin{bmatrix} b_1 \\ b_2 \\ 0 \end{bmatrix}$

일 때 $x_2=x_4=0$이면 유일한 해 $\begin{pmatrix} b_1 & 0 & b_2 & 0 \end{pmatrix}^T$가 $a_{12},\ a_{14},\ a_{24}$에 관계없이 존재한다. 이 해에 $Ax=0$의 해를 더해도 해이다. $x_2$와 $x_4$가 정해지면 $Ax=0$의 유일한 해를 얻을 수 있다. $\begin{pmatrix} z_1 & 1 & z_2 & 0 \end{pmatrix}^T$가 $Ax=0$의 해이고 $\begin{pmatrix} z_3 & 0 & z_4 & 1 \end{pmatrix}^T$가 $Ax=0$의 해이면 상수 $c_1,\ c_2$에 대해서 $\begin{pmatrix} c_1z_1+c_2z_3 & c_1 & c_1z_2+c_2z_4 & c_2 \end{pmatrix}^T$도 $Ax=0$의 해이다. 따라서 $c_1\begin{pmatrix} -a_{12} & 1 & 0 & 0 \end{pmatrix}^T+c_2\begin{pmatrix} -a_{14} & 0 & -a_{24} & 1 \end{pmatrix}^T$가 $Ax=0$의 모든 해이다.

열 공간

행렬 $A$의 $n$개의 행을 $[A]_1,\ [A]_2,\ \cdots,\ [A]_n$, $m$개의 열을 $[A]^1,\ [A]^2,\ \cdots,\ [A]^m$와 같이 쓰겠다. 그렇다면 연립일차방정식

$\displaystyle \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23}\end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3\end{bmatrix}=\begin{bmatrix} b_1 \\ b_2 \end{bmatrix} \iff \begin{bmatrix} a_{11}x_1+a_{12}x_2+a_{13}x_3 \\ a_{21}x_1+a_{22}x_2+a_{23}x_3\end{bmatrix}=\begin{bmatrix} b_1 \\ b_2 \end{bmatrix}$

은 $x_1[A]^1+x_2[A]^2+x_3[A]^3=[b]^1$로 쓸 수 있다. 좌변과 같은 linear combination들을 모은 것은 벡터 공간을 이루며 $A$의 column space(열 공간)이라고 한다. 마찬가지로 $A^T$의 열 공간을 $A$의 row space(행 공간)라고 한다. 유의해야 할 점은 벡터 또는 행렬이 $A$인지 $A^T$인지는 $A$가 어디 있는지에 대해서 알려 주지 않는다는 것이다.

• 행렬 $A$를 함수 $y=Ax$처럼 생각할 수 있다. 예를 들어 $A:\R^m\to \R^n$이면 $Ax=b$의 해가 존재한다는 것은 $\R^n$의 부분 공간인 $A$의 열 공간의 원소 $Ax$들 중에서 $b$와 일치하는 것이 있다는 뜻이다.
• $A^T:\R^n\to \R^m$는 $X=A^T$로 볼 때, $Ax_0=b_0$라는 것은 같은 $x_0,\ b_0$에 대해서 $x^T_0X=b^T_0$라는 뜻이다. 이는 $X=A^T$의 행 공간의 원소 $x^T_0X$가 $b^T_0$와 일치한다는 뜻이다.
• 행렬 $A$를 다른 함수 $y=xA$처럼 생각할 수 있다. 예를 들어 $A':\R^n\to \R^m$이면 $xA=b$의 해가 존재한다는 것은 $\R^m$의 부분 공간인 $A$의 행 공간의 원소 $xA$들 중에서 $b$와 일치하는 것이 있다는 뜻이다. $A'$는 $A^T$로 볼 수 있으며, 같은 $x_0,\ b_0$에 대해서 $A^Tx^T=b^T$이다.
• $A$인지 $A^T$인지, 열 공간에 있는지, 열벡터인지는 서로 무관할 수 있다. $A$의 열 공간을 $A^T$의 행 공간으로 바꾸어서 서술할 때 새로운 정보를 얻을 수 없어야 한다. $x$가 열벡터이면 $x^T$는 행벡터이고 $x$가 행벡터이면 $x^T$는 열벡터이다. $x$가 열벡터이면 $Ax$처럼 곱해지고 $x$가 행벡터이면 $xA$처럼 곱해진다. 열 공간에 있는 벡터는 차원만 맞으면 열벡터일 수도 행벡터일 수도 있지만, 보통은 열 공간이든 행 공간이든 열벡터를 원소로 가지는 것으로 정해져 있다. 벡터 표현을 열벡터로 고정할 때, $x$는 열벡터이고 $x^T$는 행벡터이고, 열 공간이든 행 공간이든 $x$를 원소로 가진다.

행렬 $A$가 함수 $A:\R^m\to \R^n,\ x\mapsto Ax$로 주어지면 $\R^m$의 부분 공간 row space $\{(xA)^T\mid x^T\in \R^n\}$, null space $\{x\in \R^m\mid Ax=0\}$와 $\R^n$의 부분 공간 column space $\{Ax\mid x\in \R^m\}$, left null space $\{x^T\in \R^n\mid xA=0^T\}$를 정의할 수 있다. 네 가지 공간은 어느 하나가 다른 것에 종속되지 않고 동등하게 쓰인다.

공간의 차원

벡터들의 일차 결합이 $0$인 경우가 모든 계수가 $0$인 경우밖에 없을 때 벡터들은 linear independent(일차 독립)라고 한다. $A$의 echelon form에서 $0$이 아닌 행들은 독립이고, pivot이 있는 열들은 독립이다. 독립인 벡터들의 일차 결합으로 공간의 모든 벡터를 유도할 수 있으면 벡터들이 공간의 basis(기저)라고 한다.

동일한 벡터 공간의 유한한 두 기저에 들어 있는 벡터의 개수는 일정하다. 예를 들어 $v_1,\ \cdots,\ v_n$과 $w_1,\ \cdots,\ w_m$이 동일한 벡터 공간의 두 기저이고 $n<m$이라고 가정하겠다. $v_i$는 기저이므로 $w_1$을 $v_i$들로 나타낼 수 있는데, $0$은 linear independent가 될 수 없기 때문에 $v_i$의 계수들 중에 $0$이 아닌 것이 적어도 하나가 있다. 그것을 $v_k$라 하면 $v_k$는 $w_1$과 나머지 $v_i$들로 나타낼 수 있고, 따라서 $w_1$과 $v_k$가 없는 나머지 $v_i$들의 일차 결합으로 공간의 모든 벡터를 유도할 수 있다. $w_i$가 기저이므로 각 $w_i$를 나머지 $w_i$로 나타낼 수 있어서는 안 되기 때문에 모든 $w_i$에 대해서 차례로 이 과정을 반복할 수 있고, $v_i$를 모두 $n$개의 $w_i$로 나타낼 수 있다. $n$개의 $w_i$가 기저를 이루었고 $n<m$이면 나머지 $w_i$들은 이들로 나타낼 수 있어야 한다. 따라서 linear independent가 되려면 $n=m$이어야 한다. 위 과정을 행렬로 쓰면 다음과 같다:

$\displaystyle \begin{bmatrix} w_1 & w_2 & \cdots & w_m\end{bmatrix}= \begin{bmatrix} v_1 & v_2 & \cdots & v_n\end{bmatrix}\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1m} \\ a_{21} & a_{22} & \cdots & a_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nm} \end{bmatrix}$

$n<m$이면 $Ax=0$의 해가 무수히 많기 때문에 $wx=vAx=0$의 해 또한 무수히 많고, 일차 결합이 $0$이면서 모든 계수가 $0$이 아닌 경우를 찾을 수 있다. 이 수 $n=m$을 공간의 dimension(차원)이라고 한다. 모든 행과 열에 pivot은 없거나 하나씩만 있으므로 $A$의 행 공간과 열 공간의 차원은 $\rank A$로 같다. $A$의 kernel의 차원은 nullity $m-r$, cokernel의 차원은 $n-r$이다.

$n\times m$ 행렬 $A$의 열 공간이, 부분 공간으로서 속한 벡터 공간 전체를 생성하면 해가 하나 이상이다. 그러면 $m$개의 벡터들 가운데 적어도 $n$개의 벡터가 일차 독립이며 $\rank A=n$이 되어 row가 독립이 되고, right inverse가 존재하여 $A(A^{-1}b)=b$이다. 증명은 다음과 같다: $A$의 null space는 zero가 아닌데 left null space는 zero이므로 $AA^Tx=b$의 해가 유일하게 존재한다. 따라서 $Ax=b$인 $x$들 중에서 $A$의 null space의 성분을 제거하여 row space에 존재하도록 할 때 그 해는 $AA^Tx'=b$의 해 $x'=(AA^T)^{-1}$의 앞에 $A^T$를 곱한 것이므로 $A$의 right inverse는 $A^T(AA^T)^{-1}$이다. $A^{-1}Ax$는 $x$를 $A$의 row space의 가장 가까운 원소로 보낸다.

column이 독립이면 $Ax_1=Ax_2=b$에서 $A(x_1-x_2)=0$는 $x_1-x_2=0$이므로 $Ax=b$의 해가 하나 이하이고, left inverse가 존재하여 $A^{-1}Ax=A^{-1}b$이다. 증명은 다음과 같다: $A$의 null space는 zero인데 left null space는 zero가 아니므로 $A^TAx=b$의 해가 유일하게 존재한다. 따라서 $Ax=b$에서 $b$의 $A$의 left null space의 성분을 제거하여 column space가 존재하도록 할 때 $A$의 left inverse는 $(A^TA)^{-1}A^T$이다. $A(A^{-1}b)$는 $b$를 $A$의 column space의 가장 가까운 원소로 보낸다. 연립일차방정식 $Ax=b$의 해에 관한 사실을 정리하면 다음과 같다:

• $n\times m$ 행렬이 있으면 식이 $n$개이고 미지수가 $m$개인 연립일차방정식을 뜻한다. $\rank A=n=m$이면 단 하나의 해가 있다.
• $\rank A=n<m$이면 독립인 식보다 미지수가 더 많으므로 해가 무수히 많다.
• $\rank A=m<n$이면 독립인 식만큼 미지수가 있고 식이 더 많으므로 $b$에 따라서 해가 없거나 하나만 있다.
• $\rank A<n,\ \rank A<m$이면 $b$에 따라서 해가 없거나 무수히 많다. 이는 정사각 행렬에서 pivot에 $0$이 등장하는 경우가 해당한다.

회로의 그래프

edge $[A]_i$가 vertex $[A]^j$에서 vertex $[A]^k$로 갈 때 $A_{ij}=-1,\ A_{ik}=1$이라 하고 나머지를 $0$으로 둔 것을 digraph의 incidence matrix라고 한다. 이는 회로를 묘사할 때 유용한데, 전선의 연결 상태와 전지, 전류원이 주어진 회로, 더 나아가 저항이 주어진 회로를 그래프의 행렬로 표현하여 전지와 전류원, 저항의 세기가 주어졌을 때 각 꼭짓점의 전위와 각 edge의 전류를 행렬 계산으로 구할 수 있다.

행렬 $A$가 회로의 incidence matrix이면 연립일차방정식 $Ax=b$의 vertex $x$와 edge $b$에 원하는 벡터를 대응시킬 수 있다. digraph로 생각하고 값을 주었다면 $b$의 $e$개의 값은 해당 edge가 도착하는 꼭짓점의 값에서 해당 edge가 출발하는 꼭짓점의 값을 뺀 것이다. 따라서 $x$와 $b$에 전위와 전위차를 대응시키면 각 edge에 놓여 있는 전지에 의한 전위차를 $b$에 할당할 수 있다. 이때 상수 $c$에 대해서 $(c,\ c,\ \cdots,\ c)$들이 $Ax=0$의 모든 해이므로 $A$는 1차원의 퇴화 공간을 가진다. 따라서 하나의 전위를 미리 고정시켜야 한다.

여기에서 전치 행렬을 취하면 새로운 연립일차방정식 $A^Tx'=b'$의 edge $x'$와 vertex $b'$에 원하는 벡터를 대응시킬 수 있다. 이때 $b'$의 $v$개의 값은 해당 꼭짓점에 도착하는 각 edge들의 값의 합에서 해당 꼭짓점에서 출발하는 각 edge들의 값의 합을 뺀 것이다. 따라서 $x'$와 $b'$에 전류와 알짜 전류를 대응시키면 각 vertex 사이에 놓여 있는 전류원에 의한 전류를 출발하는 꼭짓점에 양수로, 도착하는 꼭짓점에 음수로 $b'$에 할당할 수 있다. 이때 전류원만 있는 edge는 무시할 수 있다.

$Ax=b$의 해가 존재한다는 것은 $b$가 $A$의 열 공간의 원소라는 뜻이다. 그러한 $x$가 정해져 있으면 $A$의 각 행이 $b_i$를 결정하는데, 서로 연결된 edge들이 출발한 꼭짓점에 다시 도착하는 loop를 형성할 때 loop를 구성하는 각 행들을 더하면 $0$이 된다. 이때 $-1$을 곱하여 방향을 바꿀 수 있으므로 방향에 무관하게 loop를 구성할 수 있으면 독립이 아닌 행들을 얻을 수 있다. 따라서 $b$의 $e$개의 값이 이들 loop에 대해서 $0$을 만들 때 연립일차방정식 $Ax=b$의 해가 존재할 수 있다. 이를 Kirchhoff's voltage law(키르히호프의 전압 법칙)라고 한다.

$A^Tx'=b'$의 각 edge $x'_i$는 각 행에 대응하므로 각 loop에 대해서 $0$이 되도록 $1,\ -1,\ 0$을 할당한 벡터 $x'$들은 $A^Tx'=0$의 해이다. 따라서 독립인 loop들은 $A$의 left null space의 기저가 되고, $A$의 열 공간에 속하는 $b$에 대해서 $x'^Tb=0$을 얻을 수 있다. 또한 $A$의 각 행을 모두 더하면 $0$이므로 $Ax=0$의 모든 해 $x=(c,\ c,\ \cdots,\ c)$에 대해서 $b'$가 $A$의 행 공간에 속한 column vector이면 $b'^Tx=0$을 얻을 수 있다. $A$의 열 공간에서와 마찬가지로 $A^Tx'=b'$의 해가 존재한다는 것은 $b'$가 $A$의 행 공간의 원소라는 뜻이다. 따라서 $b'$의 모든 성분의 합은 $0$이며, 이를 Kirchhoff's current law(키르히호프의 전류 법칙)라고 한다.

loop를 구성하지 않는 edge들은 $A$의 행 공간의 기저이다. $A$가 connected graph일 때, 소거법을 써서 $0$이 아닌 모든 행을 독립으로 만들면 모든 loop가 사라진 spanning tree(신장 트리)이다. 또한 $e\times v$ 행렬 $A$의 rank가 $v-1$이므로 독립인 loop의 개수는 $e-(v-1)$이고, 따라서 dimension 0 - dimension 1 + dimension 2 = 1을 얻을 수 있다. 이는 Euler characteristic(오일러 지표)에 해당한다.

그래프의 각 edge에 상수를 붙인 것을 network라고 한다. $e\times e$ 행렬 $C$를 대각 행렬로 도입하면 각 edge에 저항에 해당하는 conductance를 할당할 수 있다. Ohm's law(옴의 법칙)를 사용하면 각 edge의 전류는 전도도와 전압의 곱이다. 여기에서 전류는 $A^Tx'=b$의 해 $x'$이고 전압은 전지에 의한 전위차를 제거한 $b-Ax$이다. 그러면 저항이 주어진 회로의 전류와 전위를 결정하는 연립일차방정식을 구성할 수 있다:

$\begin{cases} C^{-1}x'+Ax=b \\ A^Tx'=b'\end{cases} \iff \begin{bmatrix}C^{-1} & A \\ A^T & 0\end{bmatrix}\begin{bmatrix}x' \\ x\end{bmatrix}=\begin{bmatrix}b \\ b'\end{bmatrix}$

첫 번째 방정식의 앞에 $A^TC$를 곱하여 두 번째 방정식에서 빼면 두 번째 방정식은 $A^TCAx=A^TCb-b'$이다. 하나의 전위를 고정시켜 $A$를 $e\times (v-1)$ 행렬로 만들면 정사각 대칭 행렬 $A^TCA$의 역행렬이 존재하고, 따라서 해 $x',\ x$를 구할 수 있다.

참고 자료

• Gilbert Strang. Linear Algebra and Its Applications.