공사 중인 페이지입니다! 가독성이 떨어질 수 있습니다.
이번 장은 diagonalization 문제를 다룬다. 즉, 유한 차원의 벡터 공간 $V$에서 정의된 linear operator $T$에 대해, 그 행렬 표현인 $[T]_{\beta}$이 diagonal 인 basis $\beta$가 존재하는지 알아내고, 또 그것을 찾는 문제를 다룬다. 이러한 diagonal 행렬로의 표현은 해당 linear operator에 대한 보다 직관적인 이해를 가능하게 한다.
Diagonalization 문제를 다루기 위해 먼저 eigenvalue와 eigenvector에 대한 개념을 소개한다.
5.1. Eigenvalues and Eigenvectors
먼저 위에서 언급한 것과 같은 basis가 있는 선형 연산자(linear operator, 벡터를 자기 자신(벡터 공간)의 벡터로 변환하는 선형 사상)를 대각화 가능(diagonalizable)하다고 한다.
(Def: Diagonalizability) A linear operator $T$ on a finite-dimensional vector space $V$ is called diagonalizable if there is an ordered basis $\beta$ for $V$ such that $[T]_{\beta}$ is a diagonal matrix. A square matrix $A$ is called diagonalizable if $L_A$ is diagonalizable.
만약 선형 연산자 $T$가 대각화 가능하고, $D = [T]{\beta}$가 대각 행렬이라 하자. 그러면 임의의 $v_i \in \beta$에 대해 $T(v_i) = D{ii} v_i = \lambda_i v_i$이다. 즉
$$
[T]_{\beta} = \begin{pmatrix}
\lambda_1 & 0 & 0 & ... & 0\\
0 & \lambda_2 & 0 & ... & 0\\
... \\
0 & 0 & 0 & ... & \lambda_n
\end{pmatrix}
$$
와 같이 표현할 수 있는데, 여기서의 $\lambda$들을 eigenvalue라 한다. 또 $T(v) = \lambda v$인 $v \in V$를 eigenvector라 한다.
(Def: Eigenvector, Eigenvalue) Let $T$ be a linear operator on a vector space $V$. A nonzero vector $v \in V$ is called an eigenvector of $T$ if there exists a scalar $\lambda$ such that $T(v) = \lambda v$. The scalar $\lambda$ is called the eigenvalue corresponding to the eigenvector $v$.
당연히 이러한 정의는 행렬에 대해서도 똑같이 적용된다. 이제 이러한 정의를 이용해 위의 논의를 다음과 같이 정리할 수 있다.
(Thm 5.1) A linear operator $T$ on a finite-dimensional vector space $V$ is diagonalizable if and only if there exists an ordered basis $\beta$ for $V$ consisting of eigenvectors of $T$. Furthermore, if $T$ is diagonalizable, $\beta = {v_1, v_2, ... , v_n}$ is an ordered basis of eigenvectors of $T$, and $D = [T]{\beta}$, then $D$ is a diagonal matrix and $D{jj}$ is the eigenvalue corresponding to $v_j$ for $1 ≤ j ≤ n$.
위와 같은 행렬은 사실상 선형 연산자를 eigenvector로 이루어진 basis에 대해 행렬로 표현한 것에 불과하는데, 따라서 standard ordered basis를 $\gamma$라고 한다면 $Q = [I_V]{\beta}^{\gamma}$에 대해 $D = [T]{\beta} = Q^{-1} [T]_{\gamma} Q$이다. (2.5. The Change of Coordinate Matrix 참조)
그렇다면 위와 같은 eigenvalue와 그에 대응하는 eigenvector를 어떻게 찾아낼 수 있을까?
$\lambda$가 eigenvalue라면 nonzero vector $v \in V$에 대해 $Av = \lambda v$인 $v$가 존재하며, $(A - \lambda I_n)v = 0$이다. 즉 $v \in N(L_{A - \lambda I_n})$. $L_A$는 linear operator이므로 이와 같은 조건을 만족할 필요충분조건은 $A - \lambda I_n$이 not invertible matrix인 것이고, 다시 이 조건을 만족할 필요충분조건은 $det(A - \lambda I_n) = 0$이다. 따라서 다음과 같은 정리를 얻는다.
(Thm 5.2) Let $A \in M_{n \times n}(F)$. Then a scalar $\lambda$ is an eigenvalue of $A$ if and only if $det(A - \lambda I_n) = 0$.
즉 $f(t) = det(A - t I_n) = 0$인 $t \in F$를 찾음으로써 eigenvalue를 구할 수 있다. 이를 다음과 같이 정의한다.
(Def: Characteristic Polynomial) Let $A \in M_{n \times n}(F)$. The polynomial $f(t) = det(A - t l_n)$ is called the characteristic polynomial of A.
두 행렬 $A$와 $B$ 서로 simliar matrix라고 하고, $B = Q^{-1} A Q$라 하자. 그러면 $I = Q^{-1} I Q$이므로 $det(B - tI) = det(Q^{-1} (A - tI) Q) = det(A - tI)$이다. 즉 두 행렬의 characteristic polynomial이 같다. 따라서 선형 연산자의 characteristic polynomial을 그 basis에 관계 없이 다음과 같이 정의할 수 있다.
(Def: Characteristic Polynomial) Let $T$ be a linear operator on an $n$-dimensional vector space $V$ with ordered basis $\beta$. We define the characteristic polynomial $f(t)$ of $T$ to be the characteristic polynomial of $A = [T]_{\beta}$. That is, $f(t) = det(A - t I_n)$.
즉 선형 연산자와 그 행렬 표현은 basis와 무관하게 eigenvalue를 공유한다. (그렇다면 두 행렬의 eigenvalue가 같다면, 그 두 행렬은 서로 닮음일까?)
또한 characteristic polynomial의 모습을 생각해보면, 다음의 정리를 (귀납법을 이용해) 쉽게 증명할 수 있다.
(Thm 5.3) Let $A \in M_{n \times n}(F)$.
•
The characteristic polynomial of $A$ is a polynomial of degree $n$ with leading coefficient $(-1)^n$.
•
$A$ has at most $n$ distinct eigenvalues.
이제 characteristic polynomial을 계산함으로써 행렬 혹은 선형 연산자의 eigenvalue를 모두 찾아낼 수 있다. 그렇다면 이에 상응하는 각각의 eigenvector는 다음과 같이 구할 수 있다. 증명은 trivial하다.
(Thm 5.4) Let $T$ be a linear operator on a vector space $V$, and let $\lambda$ be an eigenvalue of $T$. A vector $v \in V$ is an eigenvector of $T$ corresponding to $\lambda$ if and only if $v ≠ 0$ and $v \in N(T - \lambda I)$.
즉 eigenvalue $\lambda$에 대해 $(A - \lambda I)v = 0$인 $v$를 찾으면 된다. 이는 이전 장에서 공부했던 방식대로 linear system의 해를 구함으로써 가능하다.
2장의 마지막에서 했던 논의를 떠올려보자. 임의의 ordered basis $\beta$에 대해, $v \in V$가 $T$의 $\lambda$에 대응되는 eigenvector일 필요충분조건은 $\phi_{\beta}(v)$가 $A = [T]_{\beta}$의 $\lambda$에 대응되는 eigenvector라는 것이다. 다음의 수식을 참고하자.
$$
A \phi_{\beta}(v) = L_A \phi_{\beta}(v) = \phi_{\beta} T(v) = \phi_{\beta}(\lambda v) = \lambda \phi_{\beta}(v)
$$
어쨌거나 다시 말해 $v$가 $\lambda$에 관한 행렬 $A$의 eigenvector일 필요충분조건은 $\phi_{\beta}^{-1}(v)$가 $\lambda$에 관한 선형 연산자 $T$의 eigenvector라는 것이며, 이에 따라 선형 연산자의 eigenvector를 찾는 문제는 행렬의 eigenvector를 찾는 문제로 대체될 수 있다. 물론 그 반대도 마찬가지이다.
5.2. Diagonalizability
이번 절에서는 행렬의 대각화 가능성을 테스트하는 방법을 살펴보고, 그 방법에 기반하여 eigenvector들로 이루어진 basis를 찾는 방법을 공부한다.
먼저 다음의 정리는 귀납법에 의해 비교적 쉽게 증명되는데, 이는 eigenvector들로 이루어진 basis를 찾아내는 방법의 기초를 제공한다.
(Thm 5.5) Let $T$ be a linear operator on a vector space $V$, and let $\lambda_1, \lambda_2, ..., \lambda_k$ be distinct eigenvalues of $T$. If $v_1, v_2, ..., v_k$ are eigenvectors of $T$ such that $\lambda_i$ corresponds to $v_i (I ≤ i ≤ k)$, then ${v_1,v_2, ..., v_k}$ is linearly independent.
그러면 dimension theorem에 의해 당연히 다음의 정리가 따른다.
(Cor) Let $T$ be a linear operator on an $n$-dimensional vector space $V$. If $T$ has $n$ distinct eigenvalues, then $T$ is diagonalizable.
그런데 정리 5.5의 역은 성립하지 않는다는 사실에 주의하자. 즉 어떤 선형 연산자 $T$가 대각화 가능하다고 해서 $n$ 개의 서로 다른 eigenvalue를 가진 것은 아니다. 예컨대 identity operator의 eigenvalue는 1뿐이다. 이러한 문제는 characteristic polynomial의 모양새를 보면 보다 깊게 이해할 수 있다.
(Def: Splits Over) A polynomial $f(t)$ in $P(F)$ splits over $F$ if there are scalars $c, a_1, ..., a_n$ (not necessarily distinct) in $F$ such that $f(t) = c(t - a_1)(t - a_2) ... (t - a_n)$.
선형 연산자의 고유 다항식은 그 basis와는 독립적이다. 따라서 eigenvector로 이루어진 기저를 택하여 고유 다항식을 전개하면 다음의 정리는 당연하다.
(Thm 5.6) The characteristic polynomial of any diagonalizable linear operator splits.
하지만 슬프게도 위의 정리 5.6 역시 역이 성립하지 않는다. 즉 고유 다항식이 split한다 해도 대각화 불가능한 경우가 있다. 다음의 정의는 고유 다항식이 split하는 선형 연산자가 대각화 가능한지에 대한 논의를 돕는다.
(Def: Algebraic Multiplicity) Let $\lambda$ be an eigenvalue of a linear operator or matrix with characteristic polynomial $f(t)$. The (algebraic) multiplicity of $\lambda$ is the largest positive integer $k$ for which $(t - \lambda)^k$ is a factor of $f(t)$.
결과적으로 말하자면 대각화된 행렬에서는 eigenvalue가 그 multiplicity만큼 등장하며, 더욱이 해당 eigenvalue에 대응하는 eigenvector는 multiplicity를 dimension으로 가지는 벡터 공간을 이룬다. 우선 다음의 정의를 보자.
(Def: Eigenspace) Let $T$ be a linear operator on a vector space $V$, and let $\lambda$ be an eigenvalue of $T$. Define $E_{\lambda} = \{ x \in V: T(x) = \lambda x \} = N(T - \lambda I_V)$. The set $E_{\lambda}$ is called the eigenspace of $T$ corresponding to the eigenvalue $\lambda$. Analogously, we define the eigenspace of a square matrix $A$ to be the eigenspace of $L_A$.
이제 $E_{\lambda}$의 ordered basis를 $\{ v_1, v_2, ..., v_p \}$라 두고, 이를 확장하여 $V$의 ordered basis $\beta = \{
v_1, v_2, ..., v_p, v_{p +1}, ..., v_n \}$을 구성했다고 하자. 그러면 $A = [T]_{\beta}$는 다음과 같은 형태가 된다.
$$
A = \begin{pmatrix}
\lambda I_p & B \\
O & C
\end{pmatrix}
$$
따라서 선형 연산자 $T$의 고유 다항식은 $f(t) = det((\lambda - t) I_p) det(C - t I_{n - p}) = (\lambda - t)^p g(t)$이다. 즉 $\lambda$의 multiplicity는 최소 $p$이다. 즉 $p ≤ m$. 그런데 $p$는 $E_{\lambda}$의 dimension이기 때문에 다음의 정리가 증명된다.
(Thm 5.7) Let $T$ be a linear operator on a finite-dimensional vector space $V$, and let $\lambda$ be an eigenvalue of $T$ having multiplicity $m$. Then $1 ≤ dim(E_{\lambda}) ≤ m$.
사실 고유 다항식이 split하는 선형 연산자가 대각화 가능할 필요충분조건은 각 eigenspace의 dimension이 그 multiplicity와 일치하는 것이다. 이를 증명하기 위해 먼저 다음의 준비정리를 증명한다. 정리 5.5에 의해 쉽게 증명된다.
(Lem) Let $T$ be a linear operator, and let $\lambda_1, \lambda_2, ..., \lambda_k$ be distinct eigenvalues of $T$. For each $i = 1, 2, ..., k$, let $v_i \in E_{\lambda}$, the eigenspace corresponding to $\lambda_i$. If $v_1 + v_2 + ... + v_k = 0$, then $v_i = 0$ for all $i$.
이제 다음의 정리도 쉽게 증명 가능하다.
(Thm 5.8) Let $T$ be a linear operator on a vector space $V$, and let $\lambda_1, \lambda_2, ..., \lambda_k$ be distinct eigenvalues of $T$. For each $i = 1, 2, ..., k$, let $S_i$ be a finite linearly independent subset of the eigenspace $E_{\lambda_i}$. Then $S = S_1 \cup S_2 \cup ... \cup S_k$ is a linearly independent subset of $V$.
즉 각 eigenspace의 linearly independent set을 모음으로써 eigenvector들로 구성된 independent set을 만들어낼 수 있다. 이제 $m_i$를 multiplicity, $d_i = dim(E_{\lambda_i})$, $n = dim(V)$라 하자. 먼저 $T$가 대각화 가능하다고 하고, eigenvector들로 이루어진 basis $\beta$에 대해 $\beta_i = E_{\lambda_i} \cap \beta$, 그리고 $\beta_i$에 속한 원소의 수를 $n_i$라 하자. 그러면 $n_i ≤ d_i$이고, 정리 5.7에 의해 $d_i ≤ m_i$인데, $\sum{n_i} = \sum{m_i} = n$이므로 $m_i = d_i$이다. 반대로 $m_i = d_i$라 하자. 그러면 $E_{\lambda_i}$의 basis $\beta_i$에 대해 $\beta = \cup{\beta_i}$의 원소 수는 $n$개이며, 정리 5.8에 의해 linearly independent set이므로 $T$는 eigenvector들로 구성된 basis를 가지고, 따라서 대각화 가능하다. 즉 다음의 정리가 증명된다.
(Thm 5.9) Let $T$ be a linear operator on a finite-dimensional vector space $V$ such that the characteristic polynomial of $T$ splits. Let $\lambda_1, \lambda_2, ..., \lambda_k$ be the distinct eigenvalues of $T$. Then
•
$T$ is diagonalizable if and only if the multiplicity of $\lambda_i$ is equal to $dim(E_{\lambda_i})$ for all $i$.
•
If $T$ is diagonalizable and $\beta_i$ is an ordered basis for $E_{\lambda_i}$, for each $i$, then $\beta = \beta_1 \cup \beta_2 \cup ... \cup \beta_k$ is an ordered basis for $V$ consisting of eigenvectors of $T$.
즉 $n$-dimensional 벡터 공간 $V$에서 정의된 선형 연산자(혹은 행렬)가 대각화 가능할 필요충분조건은 다음의 두 조건을 만족하는 것이다.
•
$T$의 고유 다항식이 split하다.
•
각 eigenvalue $\lambda$의 multiplicity $m$에 대해 $m = dim(E_{\lambda}) = nullity(T - \lambda I) = n - rank(T - \lambda I)$이다.
위와 같은 조건을 만족한다면 각 eigenspace의 basis의 합집합이 바로 우리가 찾던 그 basis가 되는 것이다. 예컨대 선형 연산자 $T$의 eigenvector들로 이루어진 basis를 찾고자 한다면 아무 편한 basis $\alpha$를 통해 각 eigenvalue를 구한 후, linear system의 해를 구함으로써 각 eigenspace의 basis를 찾을 수 있다. 이 basis의 원소들을 합치면 $[T]_{\beta}$의 basis를 찾은 것이고, 다시 말하자면 $T$의 basis의 $\alpha$에 대한 coordinate vector를 찾은 것이다.
더욱이 위에서 언급했듯, standard orderd basis $\beta$와 대각화 가능한 행렬 $A$에 대해 우리가 찾던 대각화된 행렬은 $T = \Phi_{\beta}^{-1}(A)$를 eigenvector들로 이루어진 basis에 대해 행렬 표현한 것이므로, 그 eigenvector들을 column으로 가지는 coordinate change matrix $Q$에 대해 $D = Q^{-1} A Q$이다.
Systems of Differential Equations
이러한 대각화는 미분 방정식의 해를 구하는데 요긴하게 쓰일 수 있다. 예컨대 다음과 같은 형태의 미분 방정식을 상정하자.
$$
x' = Ax
$$
만약 $A$가 대각화 가능하다면 $D = Q^{-1} A Q$인 대각 행렬 $D$가 존재한다. 즉 $A = Q D Q^{-1}$이며, 이를 원 식에 대입하면 $x' = Q D Q^{-1} x \rightarrow Q^{-1} x' = D Q^{-1} x$를 얻는다.
이제 $Q^{-1} x = y$로 치환하면 같은 미분 방정식은 $y' = Dy$가 되는데, $D$는 대각 행렬이기 때문에 쉽게 $y$에 대한 일반해를 구할 수 있다. 그 해에 $Q$를 곱함으로써 $x$에 대한 일반해를 얻어낼 수 있다. 보통은 exponential function의 형태로 나타난다.
Direct Sums
이제 이번 "절"의 마지막으로 벡터 공간 $V$를 비슷한 벡터 공간의 direct sum으로 decomposition하는 방법을 공부한다. 이러한 decomposition은 선형 연산자 $T$의 행동을 이해하는 데 도움이 된다. 특히 $T$가 대각화 가능할 경우 $V$가 $T$의 각 eigenspace의 direct sum으로 표현될 수 있는데, 사실 그 역도 성립함을 알아낼 수 있다.
먼저 집합의 합과 direct sum을 연이어 정의해보자.
(Def: Sum of Sets) Let $W_1, W_2, ..., W_k$ be subspaces of a vector space $V$. We define the sum of these subspaces to be the set $\{ v_1 + v_2 + ... + v_k: v_i \in W_i for 1 ≤ i ≤ k \}$, which we denote by $W_1 + W_2 + ... + W_k = \sum{W_i}$.
두 벡터 공간의 합이 또 다른 벡터 공간을 형성한다는 것은 쉽게 증명이 가능하다.
(Def: Direct Sum) Let $W_1, W_2, ..., W_k$ be subspaces of a vector space $V$. We call $V$ the direct sum of the subspaces $W_1, W_2, ..., W_k$ and write $V = W_1 \oplus W_2 \oplus ... \oplus W_k$, if $V = \sum{W_i}$ and $W_j \cap \sum_{i ≠ j}{W_i} = \{ 0 \}$ for each $j (1 ≤ j ≤ k)$.
이제 여태까지 배운 내용들을 통해 다음의 정리를 증명할 수 있다. 증명이 매우 길고 지루해 생략하지만, $1 \rightarrow 2 \rightarrow ... \rightarrow 5 \rightarrow 1$ 순서대로 바로 이전 조건을 가정함으로써 다음 가정을 증명할 수 있다.
(Thm 5.10) Let $W_1, W_2, ..., W_k$ be subspaces of a finite-dimensional vector space $V$. The following conditions are equivalent.
•
$V = W_1 \oplus W_2 \oplus ... \oplus W_k$.
•
$V = \sum{W_i}$ and, for any vectors $v_1, v_2, ..., v_k$ such that $v_i \in W_i$, if $v_1 + v_2 + ... + v_k = 0$, then $v_i = 0$ for all $i$.
•
Each vector $v \in V$ can be uniquely written as $v = v_1 + v_2 + ... + v_k$, where $v_i \in W_i$.
•
If $\gamma$ is an ordered basis for $W_i (1 ≤ i ≤ k)$, then $\gamma_1 \cup ... \cup \gamma_k$ is an ordered basis for $V$.
•
For each $i = 1, 2, ..., k$, there exists an ordered basis $\gamma_i$, for $W_i$ such that $\gamma_1 \cup ... \cup \gamma_k$ is an ordered basis for $V$.
이제 만약 $T$가 대각화 가능하다고 하면, 정리 5.9에 의해 각 eigenspace의 basis의 합집합이 $V$의 basis가 된다. 따라서 $V$는 각 eigenspace의 direct sum이다. 또 반대로 $V$가 eigenspace의 direct sum이라면, 각 eigenspace의 basis의 합집합이 $V$의 basis가 된다. 다음의 정리를 증명했다.
(Thm 5.11) A linear operator $T$ on a finite-dimensional vector space $V$ is diagonalizable if and only if $V$ is the direct sum of the eigenspaces of $T$.
5.3. Matrix Limits and Markov Chains
이번 절에서는 complex field에서 정의된 행렬의 극한에 대해 공부하고, 이를 이용하여 Markov chain 문제를 푸는 방법을 공부한다.
먼저 복소수의 극한은 실수부와 허수부로 나누어 생각할 수 있다. 즉 수열 $z_n = r_n + i s_n$의 극한은 (각각의 극한이 존재한다면) $\lim{z_n} = \lim{r_n} + i \lim{s_n}$과 같이 생각할 수 있다. 이에 기반하여 행렬열의 극한을 정의할 수 있다.
(Def: Limit of Sequence of Matrix) Let $L, A_1, A_2, ...$ be $n \times p$ matrices having complex entries. The sequence $A_1, A_2, ...$ is said to converge to the $n \times p$ matrix $L$, called the limit of the sequence, if $\lim{ (A_m){ij} } = L{ij}$. We write $\lim{ A_m } = L$.
수열의 극한이 선형성을 가짐을 기억하자. 이러한 성질은 행렬열의 극한에서도 마찬가지로 성립한다.
(Thm 5.12) Let $A_1, A_2, ...$ be a sequence of $n \times p$ matrices with complex entries that converges to the matrix $L$. Then for any $P \in M_{r \times n}(C)$ and $Q \in M_{p \times s}(C)$, $\lim{PA_m} = PL$ and $\lim{A_m Q} = LQ$.
따라서 다음의 따름정리가 당연히 성립하는데, 이는 행렬의 거듭제곱열을 계산하는 데 아주 큰 용이함을 준다.
(Cor) Let $A \in M_{n \times n}(C)$ be such that $\lim{A^m} = L$. Then for any invertible matrix $Q \in M_{n \times n}(C)$, $\lim{(QAQ^{-1})^m} = QLQ^{-1}$.
또 다음의 집합에 속한다는 것은 임의의 복소수의 거듭제곱수열이 수렴하는 것의 필요충분조건이 된다. 이는 복소수뿐 아니라 행렬의 거듭제곱열의 수렴성을 판단하는 데도 매우 중요한 역할을 하기 때문에 알아두자.
$$
S = \{ \lambda \in C: |\lambda| < 1 or \lambda = 1 \}
$$
그러면, 지금 증명할 수는 없지만, 다음의 정리가 성립한다.
(Thm 5.13) Let $A$ be a square matrix with complex entries. Then $\lim{A^m}$ exists if and only if both of the following conditions hold.
•
Every eigenvalue of $A$ is contained in $S$.
•
If 1 is an eigenvalue of $A$, then the dimension of the eigenspace $E_1$ equals the multiplicity of 1 as an eigenvalue of $A$.
그런데 두 번째 조건은 $A$가 diagonalizable일 경우 당연히 성립한다. 따라서 다음의 정리로 조건을 축소할 수 있다.
(Thm 5.14) Let $A \in M_{n \times n}(C)$ satisfy the following two conditions. Then $\lim{A^m}$ exists.
•
Every eigenvalue of $A$ is contained in $S$.
•
$A$ is diagonalizable.
위의 정리는 증명하기 보다 쉽다. $A$가 대각화 가능하기 때문에 $Q^{-1}AQ = D$인 $Q$와 대각 행렬 $D$가 존재하는데, 정리 5.12의 따름정리에 따라 $A^m$의 극한은 $D^m$의 극한이 존재할 때 존재한다. 그런데 첫 번째 조건에 의해 $\lim{D^m}$이 존재한다.
이제 지금까지 배운 내용을 이용해 Marchov chain 문제를 풀어낼 수 있다. 먼저 다음의 개념을 숙지하자.
(Def: Transition Matrix) Any square matrix that has nonnegative entries and columns that sum to 1. Also called Stochastic Matrix.
(Def: Probability Vector) Any column vector that has nonnegative entries that sum to 1.
Transition matrix $A$를 가정하자. 간단히 말해, $(A^m)_{ij}$는 $m$번째 stage를 걸쳐 class $j$에서 class $i$로 분류된 개체의 비율로 해석될 수 있다. 또 probability vector $P$는 각 class에 속한 개체들의 비율로 해석될 수 있다. 즉 현재 $P$의 비율로 object가 분류되어 있다면, $m$ stage 이후의 비율은 $A^m P$로 구할 수 있다.
그렇다면 이러한 stage가 무한히 계속되면 어떨까? 이제 위에서 배운 행렬의 거듭제곱열의 극한을 써먹을 수 있다. 만약 $\lim{A^m} = L$이라 하면, 각 class에 속한 개체들의 비율은 결국 $LP$로 수렴할 것이다. 이 때 당연히 $A(LP) = LP$이기 때문에, $LP$는 $A$의 eigenvalue 1에 대응되는 eigenvector이다. 그런데 eigenvalue 1에 대한 eigenspace는 1-dimensional이고(왜?: 정리 5.13에 의해서), 그렇기 때문에 1에 대한 eigenvector인 probability vector는 유일하기 때문에 $LP$는 $P$의 선택과는 무관하다. 즉 어떠한 $P$를 택하더라도 $LP$는 같은 값으로 계산된다.
또 다음의 정리와 이어지는 따름정리는 쉽게 증명할 수 있다.
(Thm 5.15) Let $M$ be an $n \times n$ matrix having real nonnegative entries, let $v$ be a column vector in $R^n$ having nonnegative coordinates, and let $u \in R^n$ be the column vector in which each coordinate equals 1. Then
•
$M$ is a transition matrix if and only if $M^t u = u$.
•
$v$ is a probability vector if and only if $v^t u = 1$.
(Cor)
•
The product of two $n \times n$ transition matrices is an $n \times n$ transition matrix. In particular, any power of a transition matrix is a transition matrix.
•
The product of a transition matrix and a probability vector is a probability vector.
이제 Marchov chain 문제를 정의해보자. 우선 복수의 class가 존재하고, 개체가 각각의 class로 분류되어 있으며, 시간이 지남에 따라 이러한 분류가 변화하는 문제를 stochastic process라 한다. 한편 stochastic process에서는 일반적으로 class가 변하는 확률이 시간, class, class에 분류된 개체의 수 등에 의해 복잡하게 결정된다. 이러한 stochastic process 중에서도 한 interval에서의 개체의 분류 확률이 오로지 두 class에 달려 있는 경우의 문제를 Markov process라 한다. 또 그 중에서도 class의 수가 유한한 문제를 Markov chain이라 한다.
그런데 보통은 $\lim{A^m}$를 구하는 것은 쉬운 일이 아니다. 하지만 다행히도, 어떤 특수한 성질을 가진 행렬에 한해서는 이를 구하는 것이 그리 어렵지 않다. 먼저 그 특수한 행렬을 정의한다.
(Def: Regular Matrix) A transition matrix is called regular if some power of the matrix contains only positive(not zero) entries.
결과적으로 말하자면, regular matrix의 거듭제곱열의 극한은 존재하며, 그 극한은 동일한 column들로 이루어져 있다. 이것을 증명하는 과정에서 eigenvalue의 bound를 찾아내는 방법을 알아낼 수 있는데, 먼저 다음의 정의가 필요하다.
(Def: Row Sum, Column Sum) Let $A \in M+{n \times n}(C)$. For $1 ≤ i, j ≤ n$, define $\rho_i(A)$ to be the sum of the absolute values of the entries of row $i$ of $A$, and define $\nu_j(A)$ to be equal to the sum of the absolute values of the entries of column $j$ of $A$. The row sum of $A$, denoted $\rho(A)$, and the column sum of $A$, denoted $\nu(A)$, are defined as $\rho(A) = max \{ \rho_i(A): 1 ≤ i ≤ n \}$ and $\nu(A) = max \{ \nu_j(A): 1 ≤ j ≤ n \}$.
이러한 row(column) sum이 바로 eigenvalue의 upper bound가 된다. 특히, eigenvalue는 다음과 같이 정의되는 Gerschgorin disk에 포함된다.
(Def: Gerschgorin Disk) We define the $i$th Gerschgorin disk $C_i$ to be the disk in the complex plane with center $A_{ii}$ and radius $r_i = \rho_i(A) - |A_{ii}|$; that is, $C_i = \{ z \in C: |z - A_{ii}| < r_i \}$.
그러면 다음의 정리가 성립한다.
(Thm 5.16: Gerschgorin's Disk Theorem) Let $A \in M_{n \times n}(C)$. Then every eigenvalue of $A$ is contained in a Gerschgorin disk.
그러면 삼각부등식 $|\lambda| = |\lambda - A_{kk} + A_{kk}| ≤ |\lambda - A_{kk}| + |A_{kk}| ≤ r_k + |A_{kk}| = \rho_k(A)$에 의해 다음의 정리가 따른다.
(Cor 1) Let $A$ be any eigenvalue of $A \in M_{n \times n}(C)$. Then $|\lambda| < \rho(A)$.
행렬과 그 전치행렬의 eigenvalue는 같다. 따라서 다음의 정리 역시 따른다.
(Cor 2) Let $A$ be any eigenvalue of $A \in M_{n \times n}(C)$. Then $|\lambda| ≤ min \{ \rho(A), \nu(A) \}$.
Transition matrix의 column sum은 1이다. 따라서 다음의 정리는 당연하다.
(Cor 3) If $\lambda$ is an eigenvalue of a transition matrix, then $|\lambda| ≤1$.
정리 5.15에 의해 임의의 transition matrix $A$에 대해 $A^t u = u$이다. 즉 $u$는 $A^t$의 eigenvalue 1에 대응되는 eigenvector이다. 그런데 행렬과 그 전치행렬의 eigenvalue는 같으므로 다음의 정리가 증명된다.
(Thm 5.17) Every transition matrix has 1 as an eigenvalue.
또 다음의 정리를 어찌저찌 증명해낼 수 있다.
(Thm 5.18) Let $A \in M_{n \times n}(C)$ be a matrix in which each entry is positive, and let $\lambda$ be an eigenvalue of $A$ such that $|\lambda| = \rho(A)$. Then $\lambda = \rho(A)$ and $\{ u \}$ is a basis for $E_{\lambda}$, where $u \in C^n$ is the column vector in which each coordinate equals 1.
그러면 다음의 따름정리가 이어서 따른다.
(Cor 1) Let $A \in M_{n \times n}(C)$ be a matrix in which each entry is positive, and let $\lambda$ be an eigenvalue of $A$ such that $|\lambda| = \nu(A)$. Then $\lambda = \nu(A)$, and the dimension of $E_{\lambda} = 1$.
(Cor 2) Let $A \in M_{n \times n}(C)$ be a transition matrix in which each entry is positive, and let $\lambda$ be any eigenvalue of $A$ other than 1. Then $|\lambda| < 1$. Moreover, the eigenspace corresponding to the eigenvalue 1 has dimension 1.
그럼 이제까지 배운 내용을 종합해 다음의 정리를 증명할 수 있다.
(Thm 5.19) Let $A$ be a regular transition matrix, and let $\lambda$ be an eigenvalue of $A$. Then
•
$|\lambda| ≤ 1$.
•
If $|\lambda| = 1$, then $\lambda = 1$, and $dim(E_{\lambda}) = 1$.
이제 정리 5.14에 의해 다음의 정리가 따른다.
(Cor) Let $A$ be a regular transition matrix that is diagonalizable. Then $\lim{A^m}$ exists.
사실 임의의 regular transition matrix에 대해 그 대각화 가능성과는 무관하게 위의 따름정리가 성립한다. 지금으로서는 증명할 수 없지만.
(Thm 5.20) Let $A$ be an $n \times n$ regular transition matrix. Then
•
The multiplicity of 1 as an eigenvalue of $A$ is 1.
•
$L = \lim{A^m}$ exists.
•
$L$ is a transition matrix.
•
$AL = LA = L$.
•
The columns of $L$ are identical. In fact, each column of $L$ is equal to the unique probability vector $v$ that is also an eigenvector of $A$ corresponding to the eigenvalue 1.
•
For any probability vector $w$, $\lim{A^m w} = v$.
위 정리에서 등장한 벡터 $v$를 다음과 같이 정의한다.
(Def: Fixed Probability Vector) The vector $v$ in Theorem 5.20 is called the fixed probability vector or stationary vector of the regular transition matrix $A$.
이제 임의의 regular transition matrix $A$에 대해, $(A - I)v = 0$인 벡터 $v$를 찾음으로써 fixed probability vector를 구할 수 있다. 또한 이러한 $v$를 column들로 가진 행렬 $L$가 바로 $L = \lim{A^m}$이다.
5.4. Invariant Subspaces and the Cayley-Hamilton Theorem
2장에서 invariant의 개념을 잠깐 소개했었다. 이번 절에서는 이러한 invariant subspace에 대해 공부한다.
예컨대 어떤 부분 공간 $W \subset V$의 벡터 $v \in W$가 선형 연산자 $T$의 eigenvector라면, $T(v) = \lambda v \in W$이다. 즉 $T$에 의해 $W$는 자기 자신인 $W$로 mapping된다. 이러한 부분 공간을 invariant subspace라고 한다.
(Def: Invariant Subspace) Let $T$ be a linear operator on a vector space $V$. A subspace $W$ of $V$ is called a T-invariant subspace of $V$ if $T(W) \subset W$. That is, if $T(v) \in W$ for all $v \in W$.
또 어떤 벡터 $v$에 거듭 선형 연산자 $T$를 적용하여 만들어진 집합의 span을 다음과 같이 정의한다. 이러한 집합은 당연히 T-invariant이다.
(Def: Cyclic Subspace) Let $T$ be a linear operator on a vector space $V$, and let $x$ be a nonzero vector in $V$. The subspace $W = span(\{ x, T(x), T^2(x), ... \})$ is called the T-cyclic subspace of $V$ generated by $x$.
사실, 이러한 T-cyclic subspace는 벡터 $x$를 포함하는 가장 작은 T-invariant subspace이다. 즉 어떤 T-invariant subspace도 위의 $W$를 포함한다는 것이다.
만약 어떤 벡터 공간 $V$의 부분 공간 $W$가 T-invariant subspace이면, $W$에서 정의된 $T_W$ 역시 선형 연산자이다. 사실 $W$의 ordered basis $\gamma$와 이를 확장한 $V$의 ordered basis $\beta$에 대해, $A = [T]{\beta}$, $B_1 = [T_W]{\gamma}$라고 하면 다음과 같은 형태가 됨을 알 수 있다.
$$
A = \begin{pmatrix}
B_1 & B_2 \\
O & B_3 \\
\end{pmatrix}
$$
따라서 다음과 같은 관계가 성립함을 알 수 있다.
(Thm 5.21) Let $T$ be a linear operator on a finite-dimensional vector space $V$, and let $W$ be a $T$-invariant subspace of $V$. Then the characteristic polynomial of $T_W$ divides the characteristic polynomial of $T$.
이런 식으로 T-invariant subspace $W$는 $V$에 대한 힌트를 준다. 이제 다음의 정리를 통해 cyclic subspace의 polynomial을 보다 쉽게 구할 수 있다.
(Thm 5.22) Let $T$ be a linear operator on a finite-dimensional vector space $V$, and let $W$ denote the $T$-cyclic subspace of $V$ generated by a nonzero $v \in V$. Let $k = dim(W)$. Then
•
$\{ v, T(v), T^2(v), ..., T^{k - 1}(v) \}$ is a basis for $W$.
•
If $a_0v + a_1T(v) + ... + a_{k - 1}T^{k - 1}(v) + T^k(v) = 0$, then the characteristic polynomial of $T_W$ is $f(t) = (-1)^k(a_0 + a_1t + ... + a_{k - 1}t^{k - 1} + t^k)$.
The Cayley-Hamilton Theorem
정리 5.22를 이용하여 다음과 같은 유명한 정리를 증명해낼 수 있게 된다. 예컨대 $W$가 임의의 벡터 $v \in V$에 의한 T-cyclic subspace라고 하면, 정리 5.22의 첫 번째와 같은 ordered basis가 존재할 것이고, 따라서 두 번째의 등식을 만족하는 스칼라들이 있을 것이다. 그러면 $T_W$ 고유 다항식 $g(t)$를 구할 수 있는데, 이로부터 $g(T)(v) = 0$임은 쉽게 보일 수 있다. Cyclic subspace는 invariant subspace이므로 $g(t)$는 $T$의 고유 다항식 $f(t)$를 split한다. 따라서 $f(T) = T_0$이다.
(Thm 5.23: Cayley-Hamilton) Let $T$ be a linear operator on a finite-dimensional vector space $V$, and let $f(t)$ be the characteristic polynomial of $T$. Then $f(T) = T_0$, the zero transformation. That is, $T$ "satisfies" its characteristic equation.
이는 행렬에 대해서도 마찬가지로 성립한다.
(Cor: Cayley-Hamilton Theorem for Matrices) Let $A$ be an $n \times n$ matrix, and let $f(t)$ be the characteristic polynomial of $A$. Then $f(A) = O$, the $n \times n$ zero matrix.
Invariant Subspaces and Direct Sums
Invariant Subspace는 $T$에 대한 힌트를 주기 때문에, 벡터 공간 $V$를 가능한 많은 $T$-invariant subspace들의 direct sum으로 쪼개는 것은 대수적으로 중요하다. 특히 7장에서 이러한 decomposition을 공부할 것인데, 이번 섹션에서는 그 때 사용할 정리들을 짚고 넘어간다.
우선 귀납법을 이용해 다음 정리를 증명할 수 있다.
(Thm 5.24) Let $T$ be a linear operator on a finite-dimensional vector space $V$, and suppose that $V = W_1 \oplus W_2 \oplus ... \oplus W_k$, where $W_i$ is a $T$-invariant subspace of $V$ for each $i (1 ≤ i ≤ k)$. Suppose that $f_i(t)$ is the characteristic polynomial of $T_{W_i}$. Then $f_1(t)f_2(t)...f_k(t)$ is the characteristic polynomial of $T$.
$T$가 대각화 가능한 선형 연산자라고 한다면, 각 eigenvalue $\lambda$에 대한 eigenspace $E_{\lambda}$는 T-invariant이고, $V$는 각 eigenspace의 direct sum이므로 위의 정리를 이용해 characteristic polynomial을 쉽게 구해낼 수 있다. 즉 $f(t) = (\lambda_1 - t)^{m_1} (\lambda_2 - t)^{m_2} ... (\lambda_k - t)^{m_k}$.
이제 다음과 같이 행렬의 direct sum을 정의하면, 벡터 공간의 direct sum과 정확히 맞아떨어진다!
(Def: Direct Sum of Matrices) If $B_1, B_2, ..., B_k$ are square matrices with entries from $F$, then we define the direct sum of $B_1, B_2, ..., B_k$, denoted $B_1 \oplus ... \oplus B_k$, by
$$
\begin{pmatrix}
B_1 & O & ... & O \\
O & B_2 & ... & O \\
... \\
O & O & ... & B_k
\end{pmatrix}
$$