연결 강의: MIT 18.06 Linear Algebra - Lecture 24: Markov Matrices; Fourier Series

1. 이번 강의의 위치

이번 강의는 고유값과 고유벡터의 응용을 다루는 강의이다.

이전까지는 행렬의 거듭제곱 $A^k$, 미분방정식의 행렬지수 $e^{At}$를 고유값으로 분석했다. 이번에는 그 흐름을 Markov matrix에 적용한다.

Markov matrix는 확률, 인구 이동, 경제 모델처럼 전체 양은 보존되지만 내부 분포가 시간에 따라 바뀌는 상황에서 자주 등장한다.

핵심 질문은 다음과 같다.

$$u_{k+1}=Au_k$$

이 반복을 계속하면 $u_k$는 어디로 가는가?

즉, 시간이 충분히 지난 뒤의 steady state를 알고 싶은 것이다. 이 질문은 결국 $A$의 고유값과 고유벡터 문제로 바뀐다.

---

2. Markov Matrix의 정의

Markov matrix는 다음 두 조건을 만족하는 행렬이다.

1. 모든 성분이 0 이상이다.
2. 각 열의 합이 1이다.

예를 들어 다음 행렬을 생각할 수 있다.

$$A= \begin{bmatrix} 0.1 & 0.01 & 0.3 \\ 0.2 & 0.99 & 0.3 \\ 0.7 & 0 & 0.4 \end{bmatrix}$$

각 성분은 모두 0 이상이다.

또 각 열의 합을 보면 다음과 같다.

$$0.1+0.2+0.7=1$$ $$0.01+0.99+0=1$$ $$0.3+0.3+0.4=1$$

따라서 이 행렬은 Markov matrix이다.

여기서 열의 합이 1이라는 것은 각 상태에서 다음 상태들로 이동하는 비율의 총합이 1이라는 뜻이다. 확률로 보면 전체 확률이 보존된다는 의미이다.

---

3. Markov Matrix의 성질

Markov matrix의 중요한 성질은 다음과 같다.

1. $A$의 모든 성분은 0 이상이다.
2. $A$의 각 열의 합은 1이다.
3. $A^2, A^3, \dots$도 Markov matrix이다.
4. $1$은 항상 고유값이다.
5. 다른 고유값들은 보통 절댓값이 1보다 작다.

마지막 성질은 정확히 말하면 예외가 있을 수 있다. 특수한 Markov matrix에서는 다른 고유값의 절댓값도 1이 될 수 있다. 하지만 일반적으로 steady state로 수렴하는 좋은 경우에는 $1$을 제외한 고유값들의 절댓값이 1보다 작다.

Markov matrix에서 중요한 고유값은 $0$이 아니라 $1$이다.

미분방정식 $u'(t)=Au(t)$에서는 $\lambda=0$이 steady state를 만들었다. 왜냐하면 $e^{0t}=1$이기 때문이다.

반면 반복식 $u_{k+1}=Au_k$에서는 $\lambda=1$이 steady state를 만든다. 왜냐하면 $1^k=1$이기 때문이다.

---

4. 왜 $\lambda=1$이 항상 고유값인가

Markov matrix의 각 열의 합은 1이다.

따라서 $A-I$의 각 열의 합은 0이다. 예를 들어 위의 행렬에서 $A-I$는 다음과 같다.

$$A-I= \begin{bmatrix} -0.9 & 0.01 & 0.3 \\ 0.2 & -0.01 & 0.3 \\ 0.7 & 0 & -0.6 \end{bmatrix}$$

각 열의 합은 다음처럼 모두 0이다.

$$-0.9+0.2+0.7=0$$ $$0.01-0.01+0=0$$ $$0.3+0.3-0.6=0$$

이 말은 모든 행을 더하면 0행이 된다는 뜻이다.

즉, $A-I$의 행들은 선형종속이다. 행들이 선형종속이면 행렬은 singular이다.

따라서,

$$\det(A-I)=0$$

이다.

그런데 고유값은 다음 식을 만족하는 $\lambda$이다.

$$\det(A-\lambda I)=0$$

$\lambda=1$을 넣었을 때 $\det(A-I)=0$이므로, $1$은 $A$의 고유값이다.

또 다른 관점으로 보면 다음과 같다.

$$\mathbf{1}^T A=\mathbf{1}^T$$

여기서 $\mathbf{1}$은 모든 성분이 1인 벡터이다. 즉,

$$\mathbf{1}= \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}$$

이다.

따라서 $\mathbf{1}$은 $A^T$의 고유값 $1$에 대한 고유벡터이다.

$$A^T \mathbf{1}=\mathbf{1}$$

$A$와 $A^T$는 같은 고유값을 가지므로 $A$도 고유값 $1$을 가진다.

---

5. $A$와 $A^T$는 같은 고유값을 가진다

$A$와 $A^T$는 고유벡터는 달라도 고유값은 같다.

이유는 determinant의 전치 성질 때문이다.

고유값은 다음 식에서 나온다.

$$\det(A-\lambda I)=0$$

determinant는 전치해도 변하지 않는다.

$$\det M=\det(M^T)$$

따라서,

$$\det(A-\lambda I) = \det((A-\lambda I)^T)$$

전치하면 다음과 같다.

$$(A-\lambda I)^T=A^T-\lambda I$$

그러므로,

$$\det(A-\lambda I)=\det(A^T-\lambda I)$$

이다.

즉 $A$와 $A^T$는 같은 characteristic polynomial을 가지며, 따라서 같은 고유값을 가진다.

Markov matrix에서 열의 합이 1이면 $\mathbf{1}$은 $A^T$의 고유값 $1$에 대한 고유벡터이다. 이 사실로부터 $A$도 고유값 $1$을 가진다는 것을 알 수 있다.

---

6. Markov Matrix와 Steady State

반복식

$$u_{k+1}=Au_k$$

를 계속 적용하면,

$$u_k=A^k u_0$$

이다.

$A$가 대각화 가능하고 고유벡터들이 $x_1,x_2,\dots,x_n$이라고 하자. 초기 벡터 $u_0$를 고유벡터의 선형결합으로 쓰면 다음과 같다.

$$u_0=c_1x_1+c_2x_2+\cdots+c_nx_n$$

그러면 $k$번 적용한 뒤에는 다음이 된다.

$$u_k = c_1\lambda_1^k x_1 +c_2\lambda_2^k x_2 +\cdots +c_n\lambda_n^k x_n$$

Markov matrix에서는 보통 $\lambda_1=1$이고 나머지 고유값들은 절댓값이 1보다 작다.

따라서 $k$가 커지면 다음 항들은 사라진다.

$$\lambda_2^k,\lambda_3^k,\dots,\lambda_n^k \rightarrow 0$$

남는 것은 $\lambda_1=1$에 대한 항이다.

$$u_k \rightarrow c_1x_1$$

이 $c_1x_1$이 steady state이다.

즉 Markov matrix의 steady state는 고유값 $1$에 대한 고유벡터 방향으로 결정된다.

---

7. 인구 이동 모델

Markov matrix의 대표 예시는 인구 이동이다.

두 지역을 생각하자.

• California
• Massachusetts

매년 일부 사람은 같은 지역에 남고, 일부 사람은 다른 지역으로 이동한다고 하자.

예를 들어 다음과 같은 비율을 가정한다.

• California에 있던 사람 중 90%는 California에 남는다.
• California에 있던 사람 중 10%는 Massachusetts로 이동한다.
• Massachusetts에 있던 사람 중 80%는 Massachusetts에 남는다.
• Massachusetts에 있던 사람 중 20%는 California로 이동한다.

그러면 상태 벡터를 다음처럼 둘 수 있다.

$$u_k= \begin{bmatrix} u_{\text{Cal},k} \\ u_{\text{Mass},k} \end{bmatrix}$$

여기서 $u_{\text{Cal},k}$는 $k$번째 시점의 California 인구이고, $u_{\text{Mass},k}$는 $k$번째 시점의 Massachusetts 인구이다.

이동 행렬은 다음과 같다.

$$A= \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix}$$

첫 번째 열은 California에 있던 사람들이 다음 시점에 어디로 가는지를 나타낸다.

$$\begin{bmatrix} 0.9 \\ 0.1 \end{bmatrix}$$

두 번째 열은 Massachusetts에 있던 사람들이 다음 시점에 어디로 가는지를 나타낸다.

$$\begin{bmatrix} 0.2 \\ 0.8 \end{bmatrix}$$

각 열의 합은 1이다.

$$0.9+0.1=1$$ $$0.2+0.8=1$$

따라서 이 행렬은 Markov matrix이다.

---

8. 초기 상태와 한 번의 이동

처음에는 Massachusetts에 1000명이 있고 California에는 아무도 없다고 하자.

$$u_0= \begin{bmatrix} 0 \\ 1000 \end{bmatrix}$$

한 번 이동하면 다음과 같다.

$$u_1=Au_0$$

계산하면,

$$u_1 = \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix} \begin{bmatrix} 0 \\ 1000 \end{bmatrix} = \begin{bmatrix} 200 \\ 800 \end{bmatrix}$$

즉 한 번의 이동 후 California에는 200명, Massachusetts에는 800명이 있다.

전체 인구는 여전히 1000명이다.

$$200+800=1000$$

Markov matrix는 전체 합을 보존한다. 시간이 지나도 총 인구는 1000명으로 유지된다.

---

9. 인구 이동 행렬의 고유값

행렬은 다음과 같다.

$$A= \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix}$$

Markov matrix이므로 하나의 고유값은 바로 알 수 있다.

$$\lambda_1=1$$

다른 고유값은 trace를 이용하면 빠르게 구할 수 있다.

2차 정사각행렬에서 고유값의 합은 trace와 같다.

$$\lambda_1+\lambda_2=\operatorname{tr}(A)$$

이 행렬의 trace는 다음이다.

$$\operatorname{tr}(A)=0.9+0.8=1.7$$

따라서,

$$1+\lambda_2=1.7$$

이므로,

$$\lambda_2=0.7$$

즉 고유값은 다음과 같다.

$$\lambda_1=1, \qquad \lambda_2=0.7$$

두 번째 고유값 $0.7$은 절댓값이 1보다 작으므로, $0.7^k$는 시간이 지날수록 0으로 간다.

---

10. Steady State 고유벡터

$\lambda_1=1$에 대한 고유벡터를 구한다.

$$A-I= \begin{bmatrix} -0.1 & 0.2 \\ 0.1 & -0.2 \end{bmatrix}$$

고유벡터 $x_1$은 다음을 만족한다.

$$(A-I)x_1=0$$

즉,

$$\begin{bmatrix} -0.1 & 0.2 \\ 0.1 & -0.2 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$$

첫 번째 식은 다음이다.

$$-0.1x+0.2y=0$$

따라서,

$$x=2y$$

가 된다.

가장 간단히 $y=1$로 두면,

$$x_1= \begin{bmatrix} 2 \\ 1 \end{bmatrix}$$

이다.

이 고유벡터는 steady state의 비율을 나타낸다.

즉 장기적으로 California와 Massachusetts의 인구 비율은 다음과 같다.

$$2:1$$

전체 인구가 1000명이므로 steady state는 다음이다.

$$\frac{1000}{3} \begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{2000}{3} \\ \frac{1000}{3} \end{bmatrix}$$

즉 장기적으로 California에는 약 666.7명, Massachusetts에는 약 333.3명이 남는다.

---

11. 두 번째 고유벡터와 전체 해

$\lambda_2=0.7$에 대한 고유벡터도 구할 수 있다.

$$A-0.7I= \begin{bmatrix} 0.2 & 0.2 \\ 0.1 & 0.1 \end{bmatrix}$$

따라서,

$$(A-0.7I)x_2=0$$

를 만족하는 벡터는 다음처럼 잡을 수 있다.

$$x_2= \begin{bmatrix} -1 \\ 1 \end{bmatrix}$$

초기 상태는 다음이다.

$$u_0= \begin{bmatrix} 0 \\ 1000 \end{bmatrix}$$

이를 고유벡터의 선형결합으로 쓴다.

$$u_0=c_1 \begin{bmatrix} 2 \\ 1 \end{bmatrix} +c_2 \begin{bmatrix} -1 \\ 1 \end{bmatrix}$$

$c_1,c_2$를 맞추면 다음과 같다.

$$c_1=\frac{1000}{3}, \qquad c_2=\frac{2000}{3}$$

따라서 $k$번 이동한 뒤의 상태는 다음이다.

$$u_k= \frac{1000}{3} 1^k \begin{bmatrix} 2 \\ 1 \end{bmatrix} + \frac{2000}{3} 0.7^k \begin{bmatrix} -1 \\ 1 \end{bmatrix}$$

$1^k$는 계속 1이고, $0.7^k$는 0으로 간다.

따라서,

$$u_k \rightarrow \frac{1000}{3} \begin{bmatrix} 2 \\ 1 \end{bmatrix}$$

이다.

이것이 Markov matrix의 전형적인 흐름이다. 고유값 $1$에 해당하는 성분은 남고, 절댓값이 1보다 작은 고유값에 해당하는 성분은 시간이 지나며 사라진다.

---

12. 열 Markov Matrix와 행 Markov Matrix

이 강의에서는 열의 합이 1인 Markov matrix를 사용한다.

즉 상태 벡터를 열벡터로 두고,

$$u_{k+1}=Au_k$$

처럼 오른쪽에서 벡터를 곱한다.

이 경우 각 열이 이전 상태 하나에서 다음 상태들로 분배되는 비율을 나타낸다.

하지만 다른 책이나 분야에서는 행의 합이 1인 Markov matrix를 쓰기도 한다.

그 경우 상태를 행벡터로 두고 다음처럼 쓴다.

$$u_{k+1}=u_k A$$

이때는 각 행의 합이 1이다.

둘은 본질적으로 transpose 관계이다. 어떤 관례를 쓰는지는 상태 벡터를 열벡터로 두는지, 행벡터로 두는지에 따라 달라진다.

---

13. 직교기저와 Projection으로 넘어가기

강의 후반부는 Fourier series로 넘어가기 위한 준비로, orthonormal basis에 대한 expansion을 다시 살핀다.

$q_1,q_2,\dots,q_n$이 orthonormal basis라고 하자.

그러면 임의의 벡터 $v$는 다음처럼 쓸 수 있다.

$$v=x_1q_1+x_2q_2+\cdots+x_nq_n$$

여기서 $x_1,x_2,\dots,x_n$은 각 기저벡터가 얼마나 섞여 있는지를 나타내는 계수이다.

orthonormal basis의 좋은 점은 이 계수를 쉽게 구할 수 있다는 것이다.

양변에 $q_1^T$를 곱하면,

$$q_1^T v = x_1 q_1^T q_1 +x_2 q_1^T q_2 +\cdots +x_n q_1^T q_n$$

orthonormal basis이므로,

$$q_i^T q_j= \begin{cases} 1, & i=j \\ 0, & i\neq j \end{cases}$$

이다.

따라서 다른 항들은 모두 사라지고,

$$x_1=q_1^T v$$

가 된다.

일반적으로는 다음과 같다.

$$x_i=q_i^T v$$

즉 orthonormal basis에서는 각 계수가 단순한 dot product로 나온다.

---

14. 행렬 관점에서 본 Orthonormal Expansion

기저벡터들을 열로 모은 행렬을 $Q$라고 하자.

$$Q= \begin{bmatrix} | & | & & | \\ q_1 & q_2 & \cdots & q_n \\ | & | & & | \end{bmatrix}$$

그러면 벡터 전개는 다음처럼 쓸 수 있다.

$$Qx=v$$

일반적으로는 $x=Q^{-1}v$를 계산해야 한다.

하지만 $Q$의 열벡터들이 orthonormal이면,

$$Q^{-1}=Q^T$$

이다.

따라서,

$$x=Q^T v$$

가 된다.

이 식의 첫 번째 성분은 $q_1^T v$이고, 두 번째 성분은 $q_2^T v$이다.

즉 projection과 orthonormal basis의 핵심은 다음 한 줄로 볼 수 있다.

$$v=(q_1^T v)q_1+(q_2^T v)q_2+\cdots+(q_n^T v)q_n$$

---

15. Fourier Series로의 확장

Fourier series는 위의 orthonormal expansion을 함수 공간으로 확장한 것이다.

벡터 $v$를 기저벡터들의 선형결합으로 쓰는 것처럼, 함수 $f(x)$를 여러 기저 함수들의 조합으로 쓴다.

대표적인 Fourier series는 다음 형태이다.

$$f(x) = a_0 +a_1\cos x +b_1\sin x +a_2\cos 2x +b_2\sin 2x +\cdots$$

여기서 기저 역할을 하는 함수들은 다음이다.

$$1,\ \cos x,\ \sin x,\ \cos 2x,\ \sin 2x,\ \dots$$

이 함수들은 $0$부터 $2\pi$까지의 구간에서 서로 직교한다.

즉 Fourier series는 무한차원 함수 공간에서의 orthogonal expansion이다.

벡터 공간에서는 dot product가 다음이었다.

$$v^T w=v_1w_1+v_2w_2+\cdots+v_nw_n$$

함수 공간에서는 이 합이 적분으로 바뀐다.

두 함수 $f(x)$, $g(x)$의 inner product를 다음처럼 둔다.

$$\langle f,g\rangle = \int_0^{2\pi} f(x)g(x)\,dx$$

예를 들어 $\sin x$와 $\cos x$는 직교한다.

$$\int_0^{2\pi}\sin x\cos x\,dx=0$$

벡터에서 서로 직교하면 dot product가 0이듯, 함수에서도 inner product가 0이면 직교한다고 본다.

---

16. Fourier 계수 구하기

Fourier series에서 $a_1$을 구해 보자.

$$f(x) = a_0 +a_1\cos x +b_1\sin x +a_2\cos 2x +b_2\sin 2x +\cdots$$

$a_1$은 $\cos x$가 얼마나 섞여 있는지를 나타내는 계수이다.

orthonormal basis에서 계수를 구할 때 해당 기저벡터와 dot product를 했던 것처럼, 여기서는 양변에 $\cos x$를 곱하고 적분한다.

$$\int_0^{2\pi} f(x)\cos x\,dx$$

오른쪽의 다른 항들은 직교성 때문에 대부분 0이 된다.

남는 것은 $a_1\cos x$ 항뿐이다.

$$\int_0^{2\pi} f(x)\cos x\,dx = a_1 \int_0^{2\pi}\cos^2 x\,dx$$

그리고,

$$\int_0^{2\pi}\cos^2 x\,dx=\pi$$

이므로,

$$a_1= \frac{1}{\pi} \int_0^{2\pi} f(x)\cos x\,dx$$

이다.

이것은 벡터에서

$$x_1=q_1^T v$$

로 계수를 구하던 것과 같은 구조이다.

차이는 유한차원 벡터의 dot product가 무한차원 함수 공간에서는 적분으로 바뀐다는 점이다.

---

17. 핵심 정리

Markov matrix는 확률적 이동을 나타내는 행렬이다.

열 Markov matrix에서는 다음 두 조건이 중요하다.

1. 모든 성분이 0 이상이다.
2. 각 열의 합이 1이다.

이 두 조건은 전체 확률이나 전체 인구가 보존된다는 뜻이다.

Markov matrix는 항상 고유값 $1$을 가진다.

$$\lambda_1=1$$

좋은 경우 나머지 고유값들은 다음을 만족한다.

$$|\lambda_i|<1 \qquad (i\geq 2)$$

따라서 반복식

$$u_{k+1}=Au_k$$

의 장기 거동은 고유값 $1$에 대한 고유벡터가 결정한다.

$$u_k \rightarrow c_1x_1$$

인구 이동 예제에서는 steady state가 다음 비율로 수렴했다.

$$\begin{bmatrix} 2 \\ 1 \end{bmatrix}$$

즉 장기적으로 California와 Massachusetts의 인구 비율은 $2:1$이 된다.

강의 후반부의 Fourier series는 다른 주제로 보이지만, 사실 같은 아이디어 위에 있다. 벡터를 orthonormal basis로 전개하듯, 함수를 직교하는 삼각함수들의 조합으로 전개하는 것이다.

결국 이번 강의의 큰 흐름은 다음과 같다.

1. Markov matrix는 전체량이 보존되는 반복 시스템을 나타낸다.
2. 고유값 $1$과 그 고유벡터가 steady state를 결정한다.
3. 나머지 고유값의 절댓값이 1보다 작으면 그 성분들은 사라진다.
4. orthonormal basis의 projection 관점은 Fourier series로 확장된다.