Skip to content

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

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.