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

标签：

• Tokyo-University
• Markov-Chain
• Eigenvalues-and-Eigenvectors
• Matrix-Diagonalization
• Matrix-Limit
• Matrix-Trace

Author

zephyr

Description

Answer the following questions regarding the transition matrix

$$\mathbf{P} = \begin{pmatrix} 1 - p & p \\ q & 1 - q \end{pmatrix}$$

,

$0 < p < 1, 0 < q < 1, p + q \neq 1$.

(1) Show that the vector

$$\begin{pmatrix} p \\ -q \end{pmatrix}$$

is an eigenvector of $\mathbf{P}$.

(2) Find the $n$-th order transition matrix $\mathbf{P}^n$.

(3) Find $\lim_{n \to \infty} \mathbf{P}^n$.

The trace of an $n \times n$ real-valued matrix $\mathbf{A} = (a_{ij})_{1 \leq i, j \leq n}$ is defined as $\mathrm{tr}\, \mathbf{A} = \sum_{i=1}^{n} a_{ii}$. Answer the following questions.

(4) Prove that $\mathrm{tr}\, \mathbf{A} = \sum_{i=1}^{n} \lambda_i$ where the eigenvalues of $\mathbf{A}$ are described as $\lambda_1, \dots, \lambda_n$.

(5) Prove the following: If there exists a natural number $m$ such that $\mathbf{A}^m = \mathbf{O}$ ($\mathbf{O}$ is the zero matrix), then $\mathrm{tr}\, \mathbf{A} = 0$.

---

回答以下关于转移矩阵

$$\mathbf{P} = \begin{pmatrix} 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

解题思路

这道题目涉及马尔可夫链的转移矩阵、特征向量、矩阵幂运算、极限计算以及矩阵迹的性质。我们需要运用线性代数的知识来分析转移矩阵的特征值和特征向量，利用这些来计算矩阵的幂和极限。最后，我们还需要证明关于矩阵迹的一些性质。

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}$$

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}$$

Therefore,

$$\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}$$

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}$$

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}$$

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.