9. 행렬의 Rank

행렬의 Rank

열공간과 행공간

• $m\times n$ 행렬 $A$의 열벡터들이 생성하는 공간을 열공간(column space) 이라 하고 $\text{Col}(A)$로 쓴다.

$$A=\left[\begin{array}{cccc}{\mathbf{a}}_1& {\mathbf{a}}_2& \cdots & {\mathbf{a}}_n\end{array}\right],\text{Col}(A)=\text{span}\{{\mathbf{a}}_1,\cdots ,{\mathbf{a}}_n\}\subseteq {\mathbb{R}}^m$$

• 행벡터들이 생성하는 공간을 행공간(row space) 이라 하고 $\text{Row}(A)$로 쓴다. ($\text{Row}(A)=\text{Col}(A^T)\subseteq {\mathbb{R}}^n$)
• $A\mathbf{x}$는 $A$의 열벡터들의 일차결합이므로, $\text{Col}(A)$는 $A$가 만들어낼 수 있는 모든 출력 벡터 $A\mathbf{x}$의 집합(치역)이기도 하다.

$$A\mathbf{x}=x_1{\mathbf{a}}_1+x_2{\mathbf{a}}_2+\cdots +x_n{\mathbf{a}}_n$$

• 열공간과 행공간은 8. 기저와 차원에서 본 것처럼 span이므로 부분공간이다.

랭크의 정의

• 행렬 $A$의 랭크(rank, 계수) 는 열공간의 차원, 즉 선형독립인 열벡터의 최대 개수이다.

$$\text{rank}(A)=\dim \text{Col}(A)$$

• 마찬가지로 행공간의 차원은 선형독립인 행벡터의 최대 개수이며, 두 값은 항상 같다. (행 랭크 = 열 랭크의 증명 참고)

$$\dim \text{Col}(A)=\dim \text{Row}(A)=\text{rank}(A)$$

• 즉, 열 기준(column rank)과 행 기준(row rank)으로 세어도 같으므로 단순히 rank라 부른다.
• 직관적으로 랭크는 행렬이 가진 독립적인 정보의 양, 또는 행렬이 입력 공간을 얼마나 큰 차원의 공간으로 보내는지를 나타낸다.

---

랭크 구하기

기약 행 사다리꼴(RREF)로 구하기

• 5. 초등행렬의 기본 행 연산은 행공간을 바꾸지 않으며, 랭크도 바꾸지 않는다. (행 연산은 행벡터들의 일차결합을 만들 뿐이고, 가역이므로 되돌릴 수 있다. 열 기준의 랭크도 변하지 않음은 아래 행 랭크 = 열 랭크의 증명에서 보인다.)
• 따라서 4. 가우스-조던 소거법으로 (기약) 행 사다리꼴로 만든 뒤, 0이 아닌 행의 개수 = 피벗(pivot)의 개수를 세면 그것이 랭크이다.

$$\text{rank}(A)=\text{(RREF에서 피벗의 개수)}=\text{(0이 아닌 행의 개수)}$$

예시 1

$$A=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right]⟶\left[\begin{array}{ccc}1& 0& -1\\ 0& 1& 2\\ 0& 0& 0\end{array}\right]$$

• 피벗이 2개이므로 $\text{rank}(A)=2$ 이다.
• 3×3 정방행렬이지만 랭크가 3이 아니므로 가역이 아니다. ($\det (A)=0$, 7. 선형독립과 선형종속의 예시 3)
• 피벗이 있는 열은 1열, 2열이므로 원래 행렬의 1열과 2열이 열공간의 기저이다. 3열은 ${\mathbf{a}}_3=2{\mathbf{a}}_2-{\mathbf{a}}_1$ 이다.

예시 2

$$B=\left[\begin{array}{cccc}1& 2& 1& 0\\ 2& 4& 3& 1\\ 3& 6& 4& 1\end{array}\right]⟶\left[\begin{array}{cccc}1& 2& 0& -1\\ 0& 0& 1& 1\\ 0& 0& 0& 0\end{array}\right]$$

• 피벗이 2개(1열, 3열)이므로 $\text{rank}(B)=2$ 이다.
• 열공간의 기저는 원래 행렬 $B$의 1열과 3열, 즉 $\{(1,2,3),(1,3,4)\}$ 이다. (주의: RREF의 열이 아니라 원래 행렬의 열을 써야 한다. 행 연산은 열공간을 바꾸기 때문이다.)
• 행공간의 기저는 RREF의 0이 아닌 행 $\{(1,2,0,-1),(0,0,1,1)\}$ 이다. (행 연산은 행공간을 바꾸지 않는다.)

행 랭크 = 열 랭크의 증명

• 행렬 $A$를 기본 행 연산으로 기약 행 사다리꼴 $R$로 만들었다고 하자. 기본 행 연산은 5. 초등행렬을 왼쪽에 곱하는 것과 같으므로, 가역행렬 $P$(초등행렬들의 곱)가 존재하여 다음이 성립한다.

$$R=PA$$

• $R$의 피벗 개수를 $r$이라 하고, $\text{(행 랭크)}=\text{(열 랭크)}=r$ 임을 보이면 된다.

1단계: 행 랭크는 $r$이다.

• 행 연산은 행공간을 바꾸지 않으므로 $\text{Row}(A)=\text{Row}(R)$ 이다. ($R$의 각 행은 $A$ 행들의 일차결합이고, $P$가 가역이라 반대도 성립한다.)
• $R$의 0이 아닌 행 $r$개는 각각 자신의 피벗 위치에만 1을 가지고 다른 행은 그 위치가 0이므로 선형독립이다. 이 $r$개가 $\text{Row}(R)$을 생성하므로 기저이고, $\dim \text{Row}(A)=r$ 이다.

2단계: 열 랭크도 $r$이다.

• (a) 행 연산은 열벡터 사이의 종속 관계를 보존한다. $R=PA$ 이고 $P$가 가역이므로, 임의의 $\mathbf{x}$에 대하여

$$A\mathbf{x}=0⟺PA\mathbf{x}=0⟺R\mathbf{x}=0$$

이다. $A\mathbf{x}$는 $A$의 열벡터들의 일차결합이므로, 이는 $A$의 열들 사이의 일차결합 관계와 $R$의 열들 사이의 일차결합 관계가 정확히 같다는 뜻이다. 따라서 $A$의 어떤 열들이 선형독립일 필요충분조건은 $R$의 같은 위치의 열들이 선형독립인 것이다. (열 자체는 달라지지만 독립성은 유지된다.)

• (b) $R$의 피벗 열 $r$개는 표준기저 벡터 ${\mathbf{e}}_1,\cdots ,{\mathbf{e}}_r$ 이므로 선형독립이다.
• (c) $R$의 피벗이 아닌 열은 0이 아닌 성분이 앞의 $r$개 행에만 있으므로 ${\mathbf{e}}_1,\cdots ,{\mathbf{e}}_r$의 일차결합이다. 따라서 피벗 열에 더 보태도 선형독립인 개수는 늘지 않고, $R$의 열 랭크는 정확히 $r$이다.
• (a)에 의해 $A$의 피벗 위치에 해당하는 열 $r$개가 선형독립이고, 나머지 열은 이들의 일차결합이다. 따라서 $\dim \text{Col}(A)=r$ 이다.

결론

$$\dim \text{Row}(A)=r=\dim \text{Col}(A)$$

• 즉, 행 랭크 = 열 랭크 = 피벗의 개수이다. $■$
• 증명 과정에서 원래 행렬 $A$의 피벗 위치 열들이 $\text{Col}(A)$의 기저라는 사실도 함께 얻는다. 예시 2에서 RREF가 아니라 원래 $B$의 1열과 3열을 기저로 썼던 이유가 이것이다.
• 예시 2에서 확인: $R$의 4열은 $(-1,1,0)=-{\mathbf{e}}_1+{\mathbf{e}}_2$ 이므로 $B$의 4열도 같은 관계 ${\mathbf{b}}_4=-{\mathbf{b}}_1+{\mathbf{b}}_3$ 을 가진다. 실제로 $-(1,2,3)+(1,3,4)=(0,1,1)$ 이다.

행렬식으로 구하기 (참고)

• $m\times n$ 행렬 $A$에서 행 $k$개와 열 $k$개를 골라 만든 $k\times k$ 부분행렬의 행렬식을 $k$차 소행렬식(minor) 이라 한다.
• 랭크는 0이 아닌 소행렬식이 존재하는 가장 큰 차수 $k$ 와 같다.

$$\text{rank}(A)=r⟺\{\begin{array}{l}\text{행렬식이 0이 아닌 }r\text{차 소행렬식이 존재한다}\\ \text{모든 }(r+1)\text{차 소행렬식은 }0\text{ 이다}\end{array}$$

• 이유: $k\times k$ 부분행렬의 행렬식이 0이 아니면 그 부분행렬은 가역이므로 선택한 $k$개의 열이 선형독립이다(6. 행렬식). 따라서 $\text{rank}(A)\ge k$ 이다. 반대로 $\text{rank}(A)=r$ 이면 독립인 열 $r$개와 독립인 행 $r$개를 골라 $r\times r$ 부분행렬을 만들 수 있고, 이것이 가역이 되어 행렬식이 0이 아니다. ($r$보다 큰 차수에서는 독립인 열이 부족하므로 항상 0이다.)

예시 1 (예시 1의 $A$)

• 3차 소행렬식(전체): $\det (A)=0$ 이므로 $\text{rank}(A)<3$ 이다.
• 2차 소행렬식 중 0이 아닌 것이 있는지 찾는다. 12행, 12열을 고르면

$$\left|\begin{array}{cc}1& 2\\ 4& 5\end{array}\right|=5-8=-3\ne 0$$

• 따라서 $\text{rank}(A)=2$ 로, 소거법으로 구한 결과와 같다.

예시 2 (예시 2의 $B$, $3\times 4$)

• $B$의 3차 소행렬식은 열 3개를 고르는 4가지 경우이다. 이들이 모두 0이면 $\text{rank}(B)\le 2$ 이다. (예: 1, 2, 3열을 고르면 2열이 1열의 2배이므로 0)
• 2차 소행렬식 중 1~2행, 1·3열을 고르면

$$\left|\begin{array}{cc}1& 1\\ 2& 3\end{array}\right|=3-2=1\ne 0$$

• 따라서 $\text{rank}(B)=2$ 이다.

언제 유용한가: 문자가 포함된 행렬

• 소거법은 문자(매개변수)가 들어가면 0으로 나누는 경우를 나눠 따져야 해서 번거롭다. 정방행렬이라면 행렬식 하나로 랭크가 줄어드는 조건을 바로 찾을 수 있다.

$$C=\left[\begin{array}{ccc}1& 1& 1\\ 1& k& 1\\ 1& 1& k\end{array}\right],\det (C)=(k-1{)}^2$$

• $k\ne 1$ 이면 $\det (C)\ne 0$ 이므로 $\text{rank}(C)=3$ 이다.
• $k=1$ 이면 $\det (C)=0$ 이고 $C$의 모든 성분이 1이므로 $\text{rank}(C)=1$ 이다.

소거법과의 비교

	소거법 (RREF)	소행렬식
계산량	적음 ($O(n^3)$)	소행렬식 개수가 조합적으로 늘어나 매우 많음
구하는 값	랭크, 피벗 위치, 기저까지	랭크만
적합한 경우	일반적인 수치 행렬	작은 크기, 정방행렬, 문자가 포함된 행렬, 이론적 증명

• 실제 계산에서는 거의 소거법을 쓰고, 소행렬식은 작은 행렬이거나 문자가 들어간 경우, 이론 전개에서 주로 쓴다.

---

랭크의 성질

$m\times n$ 행렬 $A$에 대하여 다음이 성립한다.

1. $0\le \text{rank}(A)\le \min (m,n)$
   • 열이 $n$개이므로 독립인 열은 최대 $n$개, 행이 $m$개이므로 독립인 행은 최대 $m$개이다. 영행렬의 랭크는 0이다.
2. $\text{rank}(A)=\text{rank}(A^T)$ (행 랭크 = 열 랭크)
3. $\text{rank}(A)=0⟺A=O$ (영행렬)
4. 풀랭크(Full Rank): $\text{rank}(A)=\min (m,n)$ 일 때 $A$를 풀랭크라 한다.
   • $m>n$ (세로로 긴 행렬): 풀 열랭크는 $\text{rank}=n$ (모든 열이 선형독립)
   • $m<n$ (가로로 긴 행렬): 풀 행랭크는 $\text{rank}=m$ (모든 행이 선형독립)
   • 랭크가 $\min (m,n)$보다 작으면 랭크 부족(rank-deficient) 이라 한다.
5. 곱의 랭크: $\text{rank}(AB)\le \min (\text{rank}(A),\text{rank}(B))$
   • 곱하면 랭크가 늘어나지 않는다. (정보가 새로 생기지는 않는다.)
6. 가역행렬을 곱해도 랭크는 변하지 않는다.: $P,Q$가 가역이면 $\text{rank}(PAQ)=\text{rank}(A)$
7. $\text{rank}(A^{T}A)=\text{rank}(A{A}^T)=\text{rank}(A)$
   • SVD에서 $A^{T}A$의 0이 아닌 고유값의 개수가 $A$의 랭크와 같은 이유이다.
8. 랭크 1 행렬: 0이 아닌 두 벡터의 외적 $\mathbf{u}{\mathbf{v}}^T$ 는 랭크가 1이다. (모든 열이 $\mathbf{u}$의 상수배이므로)

---

정방행렬의 랭크와 가역성

• $n\times n$ 정방행렬 $A$에 대하여 다음은 모두 동치이다.
  • $\text{rank}(A)=n$ (풀랭크)
  • $A$의 열벡터들이 선형독립이다. (행벡터들도 마찬가지)
  • 열벡터들이 ${\mathbb{R}}^n$의 기저이다.
  • $A$는 가역행렬이다. (2. 행렬 기본)
  • $\det (A)\ne 0$ 이다. (6. 행렬식)
  • RREF가 단위행렬 $I$이다.
  • $A\mathbf{x}=0$ 이 자명한 해 $\mathbf{x}=0$ 만 가진다.
• 이 중 하나라도 성립하지 않으면 모두 성립하지 않는다. 예시 1의 행렬은 $\text{rank}=2<3$ 이므로 위 조건이 모두 거짓이다.

---

연립방정식과 랭크

• 연립방정식 $A\mathbf{x}=\mathbf{b}$ ($A$는 $m\times n$)는 $\mathbf{b}$가 $A$의 열벡터들의 일차결합으로 표현되는지를 묻는 문제이다. 즉, $\mathbf{b}\in \text{Col}(A)$ 일 때 해가 존재한다.
• 확대행렬 $[A\mid \mathbf{b}]$(3. 연립방정식과 행렬)의 랭크와 비교하면 해의 존재와 유일성을 판단할 수 있다.

조건	해의 상태
$\text{rank}(A)<\text{rank}([A\mid \mathbf{b}])$	해가 없다 (불능)
$\text{rank}(A)=\text{rank}([A\mid \mathbf{b}])=n$	유일한 해
$\text{rank}(A)=\text{rank}([A\mid \mathbf{b}])<n$	무수히 많은 해 (부정)

• 여기서 $n$은 미지수의 개수이다. 해가 무수히 많을 때, 자유변수의 개수는 $n-\text{rank}(A)$ 이다.

---

랭크-영차원 정리 (Rank-Nullity Theorem)

• 동차 연립방정식 $A\mathbf{x}=0$의 모든 해의 집합을 $A$의 영공간(null space) 이라 하고 $\text{Null}(A)$로 쓴다. 영공간은 ${\mathbb{R}}^n$의 부분공간이다.
• 영공간의 차원을 영차원(nullity) 이라 한다.

$$\text{nullity}(A)=\dim \text{Null}(A)$$

• $m\times n$ 행렬 $A$에 대하여 다음이 성립한다.

$$\text{rank}(A)+\text{nullity}(A)=n$$

• 의미: 입력 공간 ${\mathbb{R}}^n$의 차원 $n$이 출력으로 살아남는 부분(rank) 과 0으로 찌그러지는 부분(nullity) 으로 나뉜다.
• 이유: RREF에서 피벗이 있는 열의 개수가 rank이고, 피벗이 없는 열(자유변수)의 개수가 nullity이다. 둘을 합치면 전체 열의 수 $n$이 된다.
• 예시 2의 $B$는 $n=4$, $\text{rank}=2$ 이므로 $\text{nullity}=2$ 이다. (자유변수 $x_2,x_4$)

---

다른 개념과의 관계

• 선형독립과 기저: 랭크는 선형독립인 열(행)벡터의 최대 개수이며, 이는 열공간의 기저의 크기이다. → 7. 선형독립과 선형종속, 8. 기저와 차원
• 고유값: $\lambda =0$ 이 고유값이면 $A\mathbf{x}=0$ 이 자명하지 않은 해를 가지므로 $\text{rank}(A)<n$ 이다. → 11. 고유값과 고유벡터
• 직교행렬: 직교행렬은 열벡터가 정규직교이므로 항상 풀랭크이다. → 10. 직교행렬
• 특이값 분해: 0이 아닌 특이값의 개수가 $\text{rank}(A)$ 이다. 큰 특이값 $r$개의 항만 남기면 $A$를 랭크 $r$ 행렬로 근사(저랭크 근사)할 수 있다. → 12. 특이값 분해 (SVD)

$$A=\sum _{i=1}^r{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T,r=\text{rank}(A)$$

- 각 항 $\sigma_i\mathbf{u}_i\mathbf{v}_i^T$는 랭크 1 행렬이고, 랭크 1 행렬 $r$개의 합은 랭크가 $r$ 이하이다.

---