Discrete Dynamical Systems
행렬 $A \in M_{k \times k}(\mathbb{R})$에 대해서 LdE $X_n = A X_{n-1}, n \in \mathbb{N}$을 discrete dynamical system이라고 부른다.
$A$가 대각화 가능하다면 $k$개의 선형독립인 고유벡터 $v_1, ..., v_k$과 각각에 대응되는 고유값 $\lambda_1, ..., \lambda_k$가 존재한다. 이때 해는 $$X_n = c_1 \lambda_1^nv_1 + \cdots + c_k \lambda_k^n v_k$$로 주어진다.
한편 $n$이 점점 커질수록 주어진 해 $X_n$은 각 고유값 $\lambda$의 크기에 따라 그 거동이 달라진다. 만약 모든 고유값의 크기가 1보다 작다면 $X_n$은 영벡터로 수렴할 것이고, 크기가 1보다 큰 고유값이 있다면 발산하고 말 것이다.
Definition 1. Let $X_n = A X_{n-1}, \forall n \in \mathbb{N}$ be a discrete dynamical system for $A \in M_{k \times k}(\mathbb{R})$. The process is said to be
(i) unstable if $A$ has an eigenvalue $\lambda$ with $|\lambda| > 1$,
(ii) stable if $\lambda < 1$ for all eigenvalues of $A$,
(iii) neutrally stable if $|\lambda| \le 1$ for all eigenvalues of $A$, but it is not stable.
Gershgorin Disc
Definition 2. For any square matrix \( A = [a_{ij}] \) of order \( k \), let \( D(a_{ii}, r_i) \) denote the closed disc in the (complex) plane centered at the diagonal entry \( a_{ii} \) with radius \( r_i = \sum_{j \neq i} |a_{ij}| \) for \( i = 1, 2, \dots, k \). Such a disc is called a Gershgorin (row) disc. In fact, \( r_i \) is the sum of the absolute values of the off-diagonal entries in the \( i \)-th row of \( A \).
Gershgorin Theorem
Theorem 1. Let \( A \) be any square matrix of order \( k \). Then each eigenvalue of \( A \) lies in a Gershgorin disc \( D(a_{ii}, r_i) \) for some \( 1 \leq i \leq k \).
Proof. Let $\lambda$ be an eigenvalue of $A$ with eigenvector $x = \begin{bmatrix} x_1 & \cdots & x_k \end{bmatrix}^T$. Then the $i$th coordinate of $Ax = \lambda x$ is $$\sum_{j = 1}^k a_{ij}x_j = \lambda x_i$$ for each $i = 1, ..., k$. Define $$x_{\ell} = \max \{ |x_i| \mid i = 1, ..., k \}.$$ Clearly $x_{\ell} > 0$. Then we have $$|\lambda - a_{\ell \ell}| |x_{\ell}| = |\lambda x_{\ell} - a_{\ell \ell}x_{\ell}| = \left| \sum_{j=1}^k a_{\ell j} x_j - a_{\ell \ell} x_{\ell} \right| \\ = \left| \sum_{j \neq \ell} a_{\ell j} x_j \right| \le \left( \sum_{j \neq \ell} |a_{\ell j}| \right) |x_{\ell}| \\ \Longrightarrow |\lambda - a_{\ell \ell}| \le \sum_{j \neq \ell} |a_{\ell j}| = r_{\ell} \\ \Longrightarrow \lambda \in D(a_{\ell \ell}, r_{\ell}). \blacksquare$$
Corollary 1
Corollary 2.
(i) For a diagonal matrix, the Gershgorin discs coincide with the set of the eigenvalues with multiplicity.
(ii) Every eigenvalue \( \lambda \) of a \( k \times k \) matrix \( A \) lies in a Gershgorin column disc \( D(a_{jj}, c_j) \) for some \( 1 \leq j \leq k \), where \( D(a_{jj}, c_j) \) is the closed disc centered at the diagonal entry \( a_{jj} \) with radius \( c_j = \sum_{i \neq j} |a_{ij}| \); the sum of the absolute values of the off-diagonal entries in the \( j \)-th column of \( A \).
Markov Process
Definition 3. A matrix $A$ is called a Markov matrix if $A$ satisfies the following conditions:
(i) all entries of $A$ are nonnegative,
(ii) the entries of each column of $A$ add up to 1.
A dynamical system $X_n = A X_{n-1}$ with a Markov matrix $A$ is called a Markov process.
Corollary 2
Corollary 2. If $\lambda$ is an eigenvalue of any Markov matrix $A$, then $|\lambda| \le 1$.
Equilibrium State
Definition 4. If \( \mathbf{x} \) is an eigenvector of \( A \) belonging to \( \lambda = 1 \), then \( A\mathbf{x} = \mathbf{x} \). This is called the equilibrium state in the Markov process \( \mathbf{x}_n = A\mathbf{x}_{n-1} \).
Theorem 2
Theorem 2. If $A$ is a Markov matrix, then
(i) $\lambda = 1$ is an eigenvalue of $A$,
(ii) there exists a vector $\mathbf{x}$ that remains fixed by the Markov process, that is, $A\mathbf{x} = \mathbf{x}$ is the equilibrium state.
Proof.
(i) Let $A \in M_{n \times n}(\mathbb{R})$ be a Markov matrix. Since the entries of each column of $A$ add up to $1$, the sum of each column of $A - I$ is $0$, which means that $r_1 + \cdots + r_n = \mathbf{0}$ for the row vectors $r_i$ of $A - I$. Then the row vectors are linearly dependent, which means that $\det(A - I) = 0$. Thus $\lambda = 1$ is an eigenvalue of $A$.
(ii) Clear. $\blacksquare$