跳到主要内容

東京大学 新領域創成科学研究科 メディカル情報生命専攻 2023年8月実施 問題8

Author​

zephyr

Description​

Answer the following questions regarding the transition matrix

,

.

(1) Show that the vector

is an eigenvector of .

(2) Find the -th order transition matrix .

(3) Find .

The trace of an real-valued matrix is defined as . Answer the following questions.

(4) Prove that where the eigenvalues of are described as .

(5) Prove the following: If there exists a natural number such that ( is the zero matrix), then .

回答以下关于转移矩阵

Misplaced &1 - p & p \\ q & 1 - q \end{pmatrix}$$ 的问题， $0 < p < 1, 0 < q < 1, p + q \neq 1$。 (1) 证明向量 $$\begin{pmatrix} p \\ -q \end{pmatrix}$$ 是 $\mathbf{P}$ 的一个特征向量。 (2) 求 $n$ 阶转移矩阵 $\mathbf{P}^n$。 (3) 求 $\lim_{n \to \infty} \mathbf{P}^n$。 一个 $n \times n$ 实数值矩阵 $\mathbf{A} = (a_{ij})_{1 \leq i, j \leq n}$ 的迹定义为 $\mathrm{tr}\, \mathbf{A} = \sum_{i=1}^{n} a_{ii}$。回答以下问题。 (4) 证明 $\mathrm{tr}\, \mathbf{A} = \sum_{i=1}^{n} \lambda_i$，其中 $\mathbf{A}$ 的特征值为 $\lambda_1, \dots, \lambda_n$。 (5) 证明以下命题：如果存在自然数 $m$ 使得 $\mathbf{A}^m = \mathbf{O}$（$\mathbf{O}$ 是零矩阵），则 $\mathrm{tr}\, \mathbf{A} = 0$。 ## **Kai** Written by [zephyr](https://inshi-notes.zephyr-zdz.space/) ## 解题思路 这道题目涉及马尔可夫链的转移矩阵、特征向量、矩阵幂运算、极限计算以及矩阵迹的性质。我们需要运用线性代数的知识来分析转移矩阵的特征值和特征向量，利用这些来计算矩阵的幂和极限。最后，我们还需要证明关于矩阵迹的一些性质。 ## Solution ### 1. Eigenvector Proof To show that $\begin{pmatrix} p \\ -q \end{pmatrix}$ is an eigenvector of $\mathbf{P}$, we need to find a scalar $\lambda$ such that $\mathbf{P}\begin{pmatrix} p \\ -q \end{pmatrix} = \lambda\begin{pmatrix} p \\ -q \end{pmatrix}$. Let's compute:

\begin{aligned} \mathbf{P}\begin{pmatrix} p \ -q \end{pmatrix} &= \begin{pmatrix} 1 - p & p \ q & 1 - q \end{pmatrix}\begin{pmatrix} p \ -q \end{pmatrix} \ &= \begin{pmatrix} (1-p)p + p(-q) \ qp + (1-q)(-q) \end{pmatrix} \ &= \begin{pmatrix} p - p^2 - pq \ qp - q + q^2 \end{pmatrix} \ &= \begin{pmatrix} p(1 - p - q) \ -q(1 - p - q) \end{pmatrix} \ &= (1 - p - q)\begin{pmatrix} p \ -q \end{pmatrix} \end{aligned}

You can't use 'macro parameter character #' in math mode Therefore, $\begin{pmatrix} p \\ -q \end{pmatrix}$ is indeed an eigenvector of $\mathbf{P}$ with eigenvalue $\lambda = 1 - p - q$. ### 2. n-th Order Transition Matrix To find $\mathbf{P}^n$, we'll use the eigen-decomposition of $\mathbf{P}$. We already found one eigenpair. Let's find the other: The characteristic equation is: $\det(\mathbf{P} - \lambda\mathbf{I}) = (1-p-\lambda)(1-q-\lambda) - pq = 0$ Solving this, we get: $\lambda_1 = 1$ and $\lambda_2 = 1 - p - q$ The eigenvector corresponding to $\lambda_1 = 1$ is $\mathbf{v}_1 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$ Now we can write $\mathbf{P} = \mathbf{S}\mathbf{\Lambda}\mathbf{S}^{-1}$, where:

\mathbf{S} = \begin{pmatrix} 1 & p \ 1 & -q \end{pmatrix}, \quad \mathbf{\Lambda} = \begin{pmatrix} 1 & 0 \ 0 & 1-p-q \end{pmatrix}

\mathbf{P}^n = \mathbf{S}\mathbf{\Lambda}^n\mathbf{S}^{-1} = \frac{-1}{p + q}\begin{pmatrix} 1 & p \ 1 & -q \end{pmatrix} \begin{pmatrix} 1 & 0 \ 0 & (1-p-q)^n \end{pmatrix} \begin{pmatrix} -q & -p \ -1 & 1 \end{pmatrix}

You can't use 'macro parameter character #' in math mode ### 3. Limit of $\mathbf{P}^n$ as $n \to \infty$ As $n \to \infty$, $(1-p-q)^n \to 0$ since $|1-p-q| < 1$. Therefore,

\lim_{n \to \infty} \mathbf{P}^n = \begin{pmatrix} \frac{q}{p+q} & \frac{p}{p+q} \ \frac{q}{p+q} & \frac{p}{p+q} \end{pmatrix}

You can't use 'macro parameter character #' in math mode ### 4. Proof of $\mathrm{tr}\, \mathbf{A} = \sum_{i=1}^{n} \lambda_i$ Let $\mathbf{A}$ be diagonalizable (if not, we can use the Jordan canonical form). Then $\mathbf{A} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}$, where $\mathbf{D}$ is a diagonal matrix with eigenvalues on the diagonal.

\begin{aligned} \mathrm{tr}, \mathbf{A} &= \mathrm{tr}, (\mathbf{P}\mathbf{D}\mathbf{P}^{-1}) \ &= \mathrm{tr}, (\mathbf{D}\mathbf{P}^{-1}\mathbf{P}) \quad \text{(cyclic property of trace)} \ &= \mathrm{tr}, \mathbf{D} \ &= \sum_{i=1}^{n} \lambda_i \end{aligned}

You can't use 'macro parameter character #' in math mode ### 5. Proof: If $\mathbf{A}^m = \mathbf{O}$, then $\mathrm{tr}\, \mathbf{A} = 0$ We will prove this statement using the following steps: 1) Let $\lambda_1, \lambda_2, ..., \lambda_n$ be the eigenvalues of $\mathbf{A}$ (including algebraic multiplicities). 2) From the condition $\mathbf{A}^m = \mathbf{O}$, we know that $\mathbf{A}$ is nilpotent. For a nilpotent matrix, all its eigenvalues are zero. We can prove this as follows: If $\lambda$ is an eigenvalue of $\mathbf{A}$, then $\lambda^m$ is an eigenvalue of $\mathbf{A}^m$. Since $\mathbf{A}^m = \mathbf{O}$, all eigenvalues of $\mathbf{A}^m$ must be zero. Therefore, $\lambda^m = 0$, which implies $\lambda = 0$. 3) From the result in part 4, we know that $\mathrm{tr}\, \mathbf{A} = \sum_{i=1}^{n} \lambda_i$. 4) Since all eigenvalues of $\mathbf{A}$ are zero, we have: $\mathrm{tr}\, \mathbf{A} = \sum_{i=1}^{n} \lambda_i = 0 + 0 + ... + 0 = 0$ Therefore, we have proved that if $\mathbf{A}^m = \mathbf{O}$, then $\mathrm{tr}\, \mathbf{A} = 0$. ## **Knowledge** ### 难点思路 本题的难点在于第2问和第3问，需要利用矩阵的特征分解来计算矩阵的幂。关键是要认识到可以用特征值和特征向量将矩阵对角化，从而简化矩阵幂的计算。另外，在计算矩阵的逆时要特别注意，因为这里很容易出错。 ### 解题技巧和信息 1. 在处理马尔可夫链问题时，注意转移矩阵的特征值总有一个是1。 2. 计算矩阵的高次幂时，考虑使用特征分解方法。 3. 在证明矩阵性质时，考虑使用特征值的性质。 4. 矩阵迹的性质在很多证明中都很有用，要熟练掌握。 5. 在进行矩阵运算时，要仔细检查每一步，特别是在计算逆矩阵时。 ### 重点词汇 - Markov chain 马尔可夫链 - transition matrix 转移矩阵 - eigenvalue 特征值 - eigenvector 特征向量 - matrix diagonalization 矩阵对角化 - trace of a matrix 矩阵的迹 - characteristic equation 特征方程 - steady state 稳态 ### 参考资料 1. Strang, Gilbert. "Linear Algebra and Its Applications." Chapter 5: Eigenvalues and Eigenvectors. 2. Ross, Sheldon M. "Introduction to Probability Models." Chapter 4: Markov Chains. 3. Horn, Roger A., and Charles R. Johnson. "Matrix analysis." Chapter 1: Eigenvalues, Eigenvectors, and Similarity.