Lecture 11. 행렬공간, 랭크 1 행렬, 그래프

지난 강의에서 네 부분공간의 지도를 완성했다. 이번에는 그 지도에서 가장 단순한 지형을 본다. 랭크가 1인 행렬이다.

랭크가 1이라는 것은 열공간이 직선 하나라는 뜻이다. 아무리 큰 행렬이어도, 어떤 벡터를 넣어도 결과는 전부 하나의 직선 위에 놓인다. 정보를 거의 다 버리는 셈이다.

그런데 이렇게 빈약한 행렬이 왜 중요한가. 모든 행렬이 랭크 1 행렬들의 합으로 쓰이기 때문이다. L3에서 곱셈의 네 번째 관점으로 잠깐 본 형태가 여기서 이름을 얻는다.

시작하기 전에 관점을 하나 넓혀 둔다. 지금까지 벡터공간의 원소는 언제나 수를 나열한 벡터였는데, 사실 그럴 필요가 없다.

1. 행렬도 벡터공간을 이룬다¶

$3 \times 3$ 실행렬 전체의 집합을 생각해 보자. 행렬 두 개를 더하면 행렬이고, 상수배해도 행렬이다. L5의 Definition 3에서 요구한 두 조건이 그대로 성립하므로 이것은 벡터공간이다.

차원은 얼마인가. $(i,j)$ 자리만 1이고 나머지가 0인 행렬을 $E_{ij}$ 라 하면, 어떤 행렬이든

M = \sum_{i=1}^{3}\sum_{j=1}^{3} m_{ij}\,E_{ij}

(1)

로 쓸 수 있다. 그리고 이 결합이 영행렬이 되려면 $(i,j)$ 자리를 보았을 때 $m_{ij} = 0$ 이어야 하므로 $E_{ij}$ 들은 독립이다. 따라서 이 아홉 개가 기저이고

\dim(3 \times 3 \text{ 행렬 전체}) = 9

(2)

이다. $3 \times 3$ 행렬은 3차원이 아니라 9차원 공간의 원소이다.

부분공간들¶

몇 가지 부분집합이 부분공간을 이룬다. 세는 방법은 자유롭게 정할 수 있는 성분의 개수를 세는 것이다.

부분공간	자유로운 성분	차원
대칭행렬 $S^{\mathsf{T}} = S$	대각 3개 + 위쪽 3개	6
위삼각행렬	대각 3개 + 위쪽 3개	6
대각행렬	대각 3개	3

대칭행렬이 부분공간인 것은 확인이 쉽다. $S_1^{\mathsf{T}} = S_1$ 이고 $S_2^{\mathsf{T}} = S_2$ 이면

(c_1S_1 + c_2S_2)^{\mathsf{T}} = c_1S_1^{\mathsf{T}} + c_2S_2^{\mathsf{T}} = c_1S_1 + c_2S_2

(3)

이므로 결합도 대칭이다. 위삼각도 마찬가지이다.

교집합과 합¶

L5에서 두 부분공간의 교집합은 부분공간이라고 했다. 대칭이면서 위삼각인 행렬은 무엇인가. 대칭이므로 $m_{ij} = m_{ji}$ 이고, 위삼각이므로 $i > j$ 일 때 $m_{ij} = 0$ 이다. 두 조건을 합치면 $i \neq j$ 인 모든 자리가 0이므로 대각행렬이다. 차원은 3이다.

합은 어떤가. 임의의 행렬 $M$ 을 대칭행렬과 위삼각행렬의 합으로 쓸 수 있을까. 쓸 수 있다. 대각선 아래 성분만 맞추면 되기 때문이다. $S$ 를 다음과 같이 잡자.

s_{ij} = s_{ji} = m_{ij} \quad (i > j), \qquad s_{ii} = \text{아무 값}

(4)

그러면 $U = M - S$ 는 대각선 아래에서 $u_{ij} = m_{ij} - m_{ij} = 0$ 이므로 위삼각이다. 따라서 두 부분공간의 합은 $3 \times 3$ 행렬 전체이다. 차원을 세어 보면

\dim(S + U) = \dim S + \dim U - \dim(S \cap U) = 6 + 6 - 3 = 9

(5)

로 맞아떨어진다. 빼 주는 이유는 (4)에서 $s_{ii}$ 를 아무 값으로 둘 수 있었던 것과 같다. 같은 $M$ 을 여러 가지로 쪼갤 수 있고, 그 자유도가 정확히 $\dim(S \cap U) = 3$ 이다.

2. 랭크 1 행렬¶

이제 본론이다. 열벡터 $\vv{u} \in \R^m$ 과 행벡터 $\vv{v}^{\mathsf{T}}$ ( $\vv{v} \in \R^n$ )를 곱해 보자. L3의 (2)에 따르면 $(m \times 1)(1 \times n)$ 이므로 결과는 $m \times n$ 행렬이다.

A = \vv{u}\vv{v}^{\mathsf{T}}, \qquad a_{ij} = u_i v_j

(6)

열공간도 행공간도 직선 하나¶

L3의 (11)에서 이미 계산했다. $j$ 번째 열은 $v_j\vv{u}$ 이므로 모든 열이 $\vv{u}$ 의 배수이고, 따라서

C(A) = \Span\{\vv{u}\}, \qquad \dim C(A) = 1

(7)

이다. 행에 대해서도 $i$ 번째 행이 $u_i\vv{v}^{\mathsf{T}}$ 이므로 행공간도 $\Span\{\vv{v}\}$ 로 1차원이다. L10에서 증명한 행랭크 $=$ 열랭크가 여기서 눈으로 확인된다.

위: 열 하나와 행 하나를 곱하면 모든 열이 \vv{u} 의 배수인 행렬이 나온다.
아래: 랭크 1 조각 두 개를 더하면 랭크 2가 된다. — Figure 1:위: 열 하나와 행 하나를 곱하면 모든 열이 $\vv{u}$ 의 배수인 행렬이 나온다. 아래: 랭크 1 조각 두 개를 더하면 랭크 2가 된다.

거꾸로도 성립한다¶

랭크가 1인 행렬은 반드시 이 꼴인가. 그렇다.

$\dim C(A) = 1$ 이라 하면 열공간은 직선 하나이므로, 그 직선의 방향을 $\vv{u}$ 라 하자. 모든 열이 그 직선 위에 있으므로 각 열은 $\vv{u}$ 의 배수이다.

\vv{a}_j = v_j\,\vv{u} \qquad (j = 1, \dots, n)

(8)

여기서 나온 계수들을 모아 $\vv{v} = (v_1, \dots, v_n)$ 이라 두면, 열을 나란히 세운 것이 바로 $\vv{u}\vv{v}^{\mathsf{T}}$ 이다.

A = \begin{bmatrix} v_1\vv{u} & v_2\vv{u} & \cdots & v_n\vv{u} \end{bmatrix} = \vv{u}\vv{v}^{\mathsf{T}}

(9)

랭크 1과 $\vv{u}\vv{v}^{\mathsf{T}}$ 는 같은 말이다.

무엇을 하는 행렬인가¶

$A\vv{x}$ 를 계산해 보자. 행렬 곱셈의 결합법칙을 쓰면 괄호를 옮길 수 있다.

A\vv{x} = \vv{u}\vv{v}^{\mathsf{T}}\vv{x} = \vv{u}\,(\vv{v}^{\mathsf{T}}\vv{x}) = (\vv{v} \cdot \vv{x})\,\vv{u}

(10)

가운데 $\vv{v}^{\mathsf{T}}\vv{x}$ 는 숫자 하나이다. 그러므로 어떤 $\vv{x}$ 를 넣든 결과는 $\vv{u}$ 의 배수이고, 그 배수가 얼마인지만 $\vv{x}$ 에 따라 달라진다.

Figure 2:무작위로 만든 150개의 점이 랭크 1 행렬을 지나면 전부 직선 하나 위에 놓인다.

영공간도 바로 나온다. (10)의 결과가 영벡터가 되려면 $\vv{v} \cdot \vv{x} = 0$ 이어야 하므로

N(A) = \{\, \vv{x} : \vv{v} \cdot \vv{x} = 0 \,\}

(11)

이고, 이것은 $\R^n$ 안의 $(n-1)$ 차원 부분공간이다. L7의 $\dim N(A) = n - r = n - 1$ 과 맞는다.

랭크 1 행렬은 온 공간을 직선 하나로 뭉갠다. 가장 극단적인 정보 손실이다.

3. 모든 행렬은 랭크 1의 합이다¶

L3의 네 번째 관점을 다시 보자. 거기서 곱셈을 다음과 같이 쓸 수 있다고 했다.

AB = \sum_{k=1}^{n} (A\text{의 } k \text{열})(B\text{의 } k \text{행})

(12)

각 항이 열 하나와 행 하나의 곱이므로 이제 이름을 붙일 수 있다. 곱은 랭크 1 행렬들의 합이다.

곱뿐 아니라 임의의 행렬에 대해서도 성립한다.

$r$ 개면 충분하다¶

L9에서 $C(A)$ 의 차원이 $r$ 이라고 했으니 기저 $\vv{u}_1, \dots, \vv{u}_r$ 을 잡을 수 있다. $A$ 의 각 열은 열공간에 있으므로 이 기저의 결합으로 쓰인다.

\vv{a}_j = c_{1j}\vv{u}_1 + c_{2j}\vv{u}_2 + \cdots + c_{rj}\vv{u}_r

(13)

계수 $c_{kj}$ 를 모아 $r \times n$ 행렬 $C$ 를 만들고 $\vv{u}$ 들을 열로 세운 $m \times r$ 행렬을 $U$ 라 하면, (13)의 식은 열마다 $\vv{a}_j = U\vv{c}_j$ 라는 뜻이므로

A = UC

(14)

이다. 여기에 (12)의 관점을 적용하면 항이 $r$ 개인 합이 된다.

A = \sum_{k=1}^{r} (U\text{의 } k \text{열})(C\text{의 } k \text{행}) = \sum_{k=1}^{r} \vv{u}_k \vv{c}_k^{\mathsf{T}}

(15)

$r$ 개보다 적을 수는 없다¶

$A$ 가 랭크 1 조각 $p$ 개의 합이라 하자.

A = \vv{u}_1\vv{v}_1^{\mathsf{T}} + \cdots + \vv{u}_p\vv{v}_p^{\mathsf{T}}

(16)

(10)에 의해 각 항이 $\vv{x}$ 에 하는 일은 $\vv{u}_k$ 의 배수를 만드는 것이므로

A\vv{x} = (\vv{v}_1 \cdot \vv{x})\vv{u}_1 + \cdots + (\vv{v}_p \cdot \vv{x})\vv{u}_p

(17)

이고, 이 값은 언제나 $\Span\{\vv{u}_1, \dots, \vv{u}_p\}$ 안에 있다. 그러므로

C(A) \subseteq \Span\{\vv{u}_1, \dots, \vv{u}_p\}

(18)

이다. 오른쪽 공간의 차원은 많아야 $p$ 이므로 $r = \dim C(A) \le p$ 이다.

두 방향을 합치면 필요한 최소 개수가 정확히 $r$ 이다. 랭크를 그 행렬을 만드는 데 필요한 랭크 1 조각의 최소 개수라고 정의해도 같은 값이 나온다는 뜻이다.

4. 함수도 벡터다¶

벡터공간의 정의에는 원소가 숫자의 나열이어야 한다는 조건이 없었다. 더할 수 있고 상수배할 수 있으면 된다. 그러므로 함수의 집합도 벡터공간이 될 수 있다.

다항식¶

차수가 2 이하인 다항식 전체를 생각하자.

p(x) = a_0 + a_1x + a_2x^2

(19)

두 다항식을 더하면 차수가 2 이하이고, 상수배해도 그렇다. 그러므로 벡터공간이다. 기저는 $1, x, x^2$ 이고 차원은 3이다. 독립인 이유는 $a_0 + a_1x + a_2x^2$ 이 모든 $x$ 에서 0이려면 계수가 전부 0이어야 하기 때문이다.

미분방정식의 해공간¶

y'' + y = 0

(20)

을 만족하는 함수들의 집합을 보자. $y_1$ 과 $y_2$ 가 해이면 미분이 선형이므로

(c_1y_1 + c_2y_2)'' + (c_1y_1 + c_2y_2) = c_1(y_1'' + y_1) + c_2(y_2'' + y_2) = 0

(21)

이 되어 결합도 해이다. 해집합은 부분공간이다. 이 방정식의 해는 $\cos x$ 와 $\sin x$ 의 결합으로 전부 쓰이므로 차원은 2이다.

이것은 비유가 아니다. 정의의 두 조건을 실제로 만족하므로 벡터공간이다. 다만 이 공간에는 좌표를 어떻게 붙일지가 아직 정해져 있지 않을 뿐이다.

5. 그래프와 인접행렬¶

이론이 여러 강의 이어졌으니 응용을 하나 보고 가자.

점들과 그 사이의 연결로 이루어진 것을 그래프(graph)라 한다. 점 $i$ 와 $j$ 가 연결되어 있으면 1, 아니면 0을 넣은 행렬을 인접행렬(adjacency matrix)이라 한다.

Figure 3:점 다섯 개짜리 그래프와 그 인접행렬, 그리고 그 제곱이다.

인접행렬을 제곱하면 무엇이 나오는가. L3의 성분 공식을 그대로 쓰면

(A^2)_{ij} = \sum_{k} a_{ik}\,a_{kj}

(22)

이다. 각 항 $a_{ik}a_{kj}$ 는 $i$ 에서 $k$ 로 가는 변이 있고 $k$ 에서 $j$ 로 가는 변도 있을 때만 1이고 그 외에는 0이다. 즉 $i \to k \to j$ 라는 두 걸음짜리 경로가 있으면 1을 보태는 것이다. $k$ 에 대해 모두 더하므로

(A^2)_{ij} = i \text{ 에서 } j \text{ 로 가는 두 걸음짜리 경로의 개수}

(23)

가 된다. 같은 논리를 반복하면 $A^k$ 의 $(i,j)$ 성분이 $k$ 걸음짜리 경로의 개수이다.

Figure 3에서 $(A^2)_{22} = 3$ 인데, 이는 2번 점에서 출발해 이웃에 갔다가 돌아오는 경로가 셋이라는 뜻이고 곧 2번 점의 이웃이 셋이라는 뜻이다. 대각 성분은 각 점의 연결 개수가 된다.

여섯 다리만 건너면 세상 누구와도 이어진다는 이야기가 있다. 인접행렬의 언어로 옮기면 $A + A^2 + \cdots + A^6$ 에 0인 성분이 거의 없다는 주장이다. 실제 사회 연결망에서 이 값을 재 보는 일이 실습에 들어 있다.

마치며...¶

이번 강의에서 다룬 것을 정리하면 다음과 같다.

대상	내용
행렬공간	$3 \times 3$ 행렬 전체는 9차원. 대칭 6, 위삼각 6, 대각 3
랭크 1 행렬	$\vv{u}\vv{v}^{\mathsf{T}}$ . 열공간과 행공간이 모두 직선 하나
랭크 1의 작용	$A\vv{x} = (\vv{v} \cdot \vv{x})\vv{u}$ , 공간 전체가 직선으로 눌린다
랭크 1의 합	랭크 $r$ 행렬은 랭크 1 조각 정확히 $r$ 개의 합
함수공간	다항식, 미분방정식의 해집합도 벡터공간
인접행렬	$(A^k)_{ij}$ 는 $k$ 걸음 경로의 개수

랭크 1 행렬은 열공간도 행공간도 직선 하나뿐인 가장 빈약한 행렬이다. 그러면서 모든 행렬을 쌓아 올리는 재료가 된다. L3에서 낯설게 보였던 곱셈의 네 번째 관점이 여기서 의미를 얻었다.

그리고 물음 하나를 남겨 두었다. 하나의 행렬을 랭크 1 조각으로 쪼개는 방법은 무수히 많은데 그중 무엇이 가장 좋은가. 조각 몇 개만 남기고 잘라 냈을 때 원래에 가장 가까운 쪼개기 말이다. 이 물음은 후반부에서 답한다.

다음 강의에서는 지금까지의 이론이 실제로 어디에 쓰이는지 본다. 전기 회로와 그래프인데, 놀랍게도 네 부분공간 전부가 거기서 물리적인 뜻을 갖는다.

이번 강의의 내용을 파이썬으로 확인해 보려면 L11 실습 노트북으로 넘어가면 된다. 랭크 1 행렬이 점들을 직선으로 뭉개는 것을 회전시켜 보고, 행렬을 랭크 1 조각으로 쪼개 하나씩 더해 가며 랭크가 늘어나는 것을 확인할 수 있다.