행렬의 rank와 nullity

퇴화 공간

$A$가 singular가 아니면 역행렬 $A^{-1}$을 곱할 수 있으므로 $Ax=0$의 원소는 $0$뿐이며, 모든 $b$에 대해서 $Ax=b$의 해가 존재한다. 이는 가우스 소거법에서 알 수 있는 결과이다. 그러나 $A$가 singular이거나 $n\times m$인 직사각 행렬일 때는 $Ax=0$의 원소가 무수히 많은 경우가 흔한 일이다. 또한 이 경우에 해들은 벡터 공간을 이룬다는 사실을 관찰할 수 있다. 따라서 행렬 $A$에 대해서 다음을 정의한다:

• $Ax=0$의 해들을 모은 것을 null space(영 공간, 퇴화 공간) 또는 kernel(핵)라고 한다.
• $x^TA=0^T$ 또는 $A^Tx=0$의 해들을 모은 것을 left null space 또는 cokernel(여핵)이라고 한다. 이는 $A^T$의 kernel이다.

$A$가 singular이고 무수히 많은 해를 가질 때에 모든 해를 구하는 방법을 생각해 보겠다. 예를 들어 연립일차방정식

$\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으로 잡고 null space를 생각할 수 있다. $x_1+2x_2=0$의 해는 $(2c,\ -c)$이므로 하나의 자유 변수를 가지는 $(1,\ 3/2)+c(2,\ -1)=(1+2c,\ 3/2-c)$를 complete solution으로 삼을 수 있다. 즉 우변이 $0$인 경우의 각 해들에 우변이 $b$인 경우의 해를 하나 골라 평행 이동하여 완전해를 구한 것이다. 이 과정을 보다 체계화하여 모든 행렬에 적용하기 위해서 직사각 행렬의 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$의 해는 자유 변수들 $c_i$에 대해서 $x=x_r+c_1v_1+c_2v_2+\cdots+c_{m-r}v_{m-r}$이다. $x_r$은 모든 자유 변수들을 $0$으로 놓아 얻는 해이고, 퇴화 공간의 각 벡터 $v_i$는 대응하는 자유 변수의 성분을 제외한 나머지 자유 변수들의 성분이 모두 $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들을 모은 것은 벡터 공간을 이루며 column space(열 공간)이라고 한다. 마찬가지로 $A^T$의 열 공간을 row space(행 공간)라고 한다.

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

벡터 공간 $V$의 유한한 두 기저에 들어 있는 벡터의 개수는 일정하다. 예를 들어 $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$을 $V$의 dimension(차원)이라고 한다. 모든 행과 열에 pivot은 없거나 하나씩만 있으므로 행 공간과 열 공간의 차원은 $\rank A$로 같다. kernel의 차원은 nullity $m-r$, cokernel의 차원은 $n-r$이다.

유사 역행렬

$AA^{-1}=I$인 $A^{-1}$을 right inverse, $A^{-1}A=I$인 $A^{-1}$을 left inverse라고 한다. $n\times m$ 행렬과 $m\times r$ 행렬을 곱하면 $n\times r$ 행렬이므로 다음이 성립한다.

• $A$가 $n\times m$ 행렬일 때 right inverse는 $m\times n$ 행렬이고 $AA^{-1}=I_{n\times n}$이다. 따라서 $n\leq m$이고 $\rank A=n$이어야 한다.
• $A$가 $n\times m$ 행렬일 때 left inverse는 $m\times n$ 행렬이고 $A^{-1}A=I_{m\times m}$이다. 따라서 $m\leq n$이고 $\rank A=m$이어야 한다.

ordinary least squares를 쓸 때 right inverse는 $A^T(AA^T)^{-1}$, left inverse는 $(A^TA)^{-1}A^T$이다. 이 결과 $A^{-1}$로 모든 pseudoinverse를 나타내면 $C$가 $m\times n$ 행렬일 때 $A^{-1}+(I_m-A^{-1}A)C+(I_n-AA^{-1})C$이다. $A^{-1}$처럼 $AA^{-1}A=A,\ A^{-1}AA^{-1}=A^{-1},\ (AA^{-1})^T=AA^{-1},\ (A^{-1}A)^T=A^{-1}A$를 만족하는 pseudoinverse는 유일하며, 이를 Moore–Penrose inverse라 한다.

column space가 모든 $b$를 생성하면 $Ax=b$의 해가 하나 이상이고, $A(A^{-1}b)=b$를 할 수 있다. column이 독립이면 $Ax_1=Ax_2=b$에서 $A(x_1-x_2)=0$는 $x_1-x_2=0$이므로 $Ax=b$의 해가 하나 이하이고, $A^{-1}Ax=A^{-1}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$이 등장하는 경우가 해당한다.

그래프

행렬 $A$가 주어지면 그 column space $Ax=b$, row space $A^Tx=b$, null space $\{x\mid Ax=0\}$, left null space $\{x\mid A^Tx=0\}$를 정의할 수 있다. 네 가지 공간은 어느 하나가 다른 것에 종속되지 않고 동등하게 쓰이며, 이는 그래프를 행렬로 나타낼 때 잘 드러난다. 정의하는 방법은 조금씩 다르지만, 행이 $e$개의 edge에 대응하고 열이 $v$개의 vertex 또는 node에 대응하도록 $e\times v$ 행렬 $A$를 만들 수 있다. digraph인 경우에, edge $[A]_i$가 vertex $[A]^j$에서 vertex $[A]^k$로 갈 때 $A_{ij}=-1,\ A_{ik}=1$과 같이 값을 주면 $A$를 그래프의 incidence matrix라고 한다.

여기에서는 전선의 연결 상태와 전지, 전류원이 주어진 회로, 더 나아가 저항이 주어진 회로를 그래프의 행렬로 표현하고, 전지와 전류원, 저항의 세기가 주어졌을 때 각 꼭짓점의 전위와 각 edge의 전류를 행렬 계산으로 구하는 방법을 생각해 보겠다. 회로의 연결 상태를 incidence matrix로 나타내면 연립일차방정식 $Ax=b$을 구성하고 vertex $x$와 edge $b$에 원하는 수를 대응시킬 수 있다. 회로를 digraph로 생각하고 값을 주었다면 $b$의 $e$개의 값은 해당 edge가 도착하는 꼭짓점의 값에서 해당 edge가 출발하는 꼭짓점의 값을 뺀 것이다. 따라서 $x$와 $b$에 전위와 전위차를 대응시키면 각 edge에 놓여 있는 전지에 의한 전위차를 $b$에 할당할 수 있다. 이때 상수 $c$에 대해서 $(c,\ c,\ \cdots,\ c)$들이 $Ax=0$의 모든 해이므로 1차원의 퇴화 공간을 가진다. 따라서 하나의 전위를 미리 고정시켜야 한다.

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

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

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

그래프에 $e\times e$인 대각 행렬 $C$를 붙인 것을 network라고 한다. 각 edge에 저항에 해당하는 conductance를 붙이면 network이다. 이는 각 edge의 전류를 전도도와 전압의 곱으로 구하는 Ohm's law(옴의 법칙)를 도입하기 위해서이다. 전류는 $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.