東京大学 情報理工学研究科 数理情報学 2018年8月実施 第1問

标签：

• 东京大学
• PageRank

Author

hari64boli64, 祭音Myyura

Description

$n$ 次実正方行列 $A = (a_{ij}) \in \mathbb{R}^{n \times n}$, $B = (b_{ij}) \in \mathbb{R}^{n \times n}$ は

$$a_{ij} \geq 0 \quad (i, j = 1, 2, \ldots, n), \quad \sum_{i=1}^{n} a_{ij} = 1 \quad (j = 1, 2, \ldots, n), \quad B = \alpha A + \frac{1 - \alpha}{n} \boldsymbol{1} \boldsymbol{1}^\top$$

を満たすものとする。 ただし、$\top$ は転置を表し、$\alpha$ は $0 < \alpha < 1$ を満たす実数、$\boldsymbol{1}$ はすべての成分が $1$ であるベクトル $\boldsymbol{1} = (1, \ldots, 1)^\top \in \mathbb{R}^n$ とする。 また、$v = (v_1, \ldots, v_n)^\top \in \mathbb{R}^n$ について $\lVert v \rVert_1 := \sum_{i=1}^{n} |v_i|$ とする。以下の設問に答えよ。

(1) 行列 $A$ の固有値の絶対値で最大となるものを求めよ。

(2) 各成分が非負のベクトル $x \in \mathbb{R}^n$ で、

$$Bx = x, \quad \boldsymbol{1}^\top x = 1$$

となるものが存在することを示せ。なお、次の事実を用いてよい：

「$\mathbb{R}^n$ の非空なコンパクト凸集合からそれ自身への連続写像には不動点が存在する。」

(3) $\boldsymbol{1}^\top q = 0$ を満たすベクトル $q = (q_1, \ldots, q_n)^\top \in \mathbb{R}^n$ に対して、

$$\left| \sum_{j=1}^{n} b_{ij} q_j \right| \leq \sum_{j=1}^{n} b_{ij} |q_j| - \frac{1 - \alpha}{n} \|q\|_1 \qquad (i = 1, 2, \ldots, n)$$

となることを示せ。

(4) (2) の条件を満たすベクトル $x \in \mathbb{R}^n$ は、正の整数 $N$ に対して、

$$\left \lVert B^N \frac{\boldsymbol{1}}{n} - x \right \rVert_1 \leq \alpha^N \left \lVert \frac{\boldsymbol{1}}{n} - x \right \rVert_1$$

を満たすことを示せ。

题目描述

设实矩阵 $A=(a_{ij}),B=(b_{ij})\in\mathbb R^{n\times n}$ 满足

$$a_{ij}\ge0,\qquad \sum_{i=1}^na_{ij}=1\quad(j=1,\ldots,n),$$

$$B=\alpha A+\frac{1-\alpha}{n}\mathbf1\mathbf1^\top, \qquad0<\alpha<1,$$

其中 $\mathbf1=(1,\ldots,1)^\top$。向量的 1-范数定义为

$$\|v\|_1=\sum_{i=1}^n|v_i|.$$

1. 求 $A$ 的特征值模的最大值。

2. 证明存在分量非负的概率向量 $x$ 满足

   $$Bx=x,\qquad\mathbf1^\top x=1.$$

   可使用“非空紧凸集到自身的连续映射存在不动点”这一事实。

3. 对任意满足 $\mathbf1^\top q=0$ 的向量 $q=(q_1,\ldots,q_n)^\top$，证明对每个 $i$，

   $$\left|\sum_{j=1}^nb_{ij}q_j\right| \le\sum_{j=1}^nb_{ij}|q_j| -\frac{1-\alpha}{n}\|q\|_1.$$

4. 对第 2 问的任一不动点 $x$ 和任意正整数 $N$，证明

   $$\left\|B^N\frac{\mathbf1}{n}-x\right\|_1 \le\alpha^N\left\|\frac{\mathbf1}{n}-x\right\|_1.$$

Kai

(1)

一般に、転置行列の固有値は、固有方程式が同じになることから、元の行列と同じ固有値を取る。

$A^T$ は、$\boldsymbol{1}$ を固有ベクトルとして、$1$ を固有値に持つ。

$$\begin{aligned} & (A^T\boldsymbol{1})_i=\sum_{j}^n A^T_{ij}\boldsymbol{1}_j=\sum_{j}^na_{ji}=1 \\ \Rightarrow & A^T\boldsymbol{1}=1\boldsymbol{1} \end{aligned}$$

そして、$1$ より絶対値が大きな固有値を持つことはない。

固有ベクトル $\boldsymbol{x}$ の、絶対値に関する最大値を $x_i$ で取るとすると、

$$\begin{aligned} & (A^T\boldsymbol{x})_i =\lambda x_i \\ \Leftrightarrow & \sum_{j}^n a_{ji}x_j =\lambda x_i \\ \end{aligned}$$

一方、

$$\begin{aligned} \left|\sum_{j=1}^n a_{ji}x_j\right| \leq \sum_{j=1}^n a_{ji}|x_j| \leq |x_i|\sum_{j=1}^n a_{ji} =|x_i|<|\lambda|\,|x_i|=|\lambda x_i| \end{aligned}$$

つまり、$|\lambda|>1$ なら、この不等式に反し矛盾。

よって、$A$ の固有値の絶対値で最大となるものは $1$ である。

(2)

関数 $f:S \to S$ を $f(\boldsymbol{x})=B\boldsymbol{x}$ で定義する。

ただし、$S=\{\boldsymbol{x}\in \mathbb{R}_{\geq 0}^n \mid \boldsymbol{1}^T\boldsymbol{x}=1 \}$ である。

まず $B\boldsymbol{x}\in S$ を示す。

$$\begin{aligned} B\boldsymbol{x}=\alpha A\boldsymbol{x}+\frac{1-\alpha}{n}\boldsymbol{1}\boldsymbol{1}^T\boldsymbol{x} \end{aligned}$$

という表式と、$a_{ij},\alpha$ の値域より、$B\boldsymbol{x}\in \mathbb{R}_{\geq 0}^n$ は明らか。

$\boldsymbol{1}^TB\boldsymbol{x}=1$ を示す。

$$\begin{aligned} \boldsymbol{1}^TB\boldsymbol{x} & =\boldsymbol{1}^T\left(\alpha A\boldsymbol{x}+\frac{1-\alpha}{n}\boldsymbol{1}\boldsymbol{1}^T\boldsymbol{x}\right) \\ & =\alpha (\boldsymbol{1}^TA)\boldsymbol{x}+\frac{1-\alpha}{n}\boldsymbol{1}^T\boldsymbol{1}\boldsymbol{1}^T\boldsymbol{x} \\ & =\alpha \boldsymbol{1}^T\boldsymbol{x}+(1-\alpha)\boldsymbol{1}^T\boldsymbol{x} \\ & =\alpha+(1-\alpha) \\ & =1 \end{aligned}$$

よって、$f(S)\subset S$ である。

線形写像 $f$ は連続である。$S$ は非空な凸集合であり、また有界閉集合なのでコンパクトである。

以上より、ヒントで与えられているブラウワーの不動点定理より、

$$\begin{aligned} \boldsymbol{x}\in \mathbb{R}^n, B\boldsymbol{x}=\boldsymbol{x}, \boldsymbol{1}^T\boldsymbol{x}=1 \end{aligned}$$

の条件を満たすような $\boldsymbol{x}$ が存在する。

(3)

$$\begin{aligned} & \left|\sum_{j=1}^nb_{ij}q_j\right| \\ = & |(B\boldsymbol{q})_i| \\ = & \left|\left((\alpha A+\frac{1-\alpha}{n}\boldsymbol{1}\boldsymbol{1}^T)\boldsymbol{q}\right)_i\right| \\ = & \left|(\alpha A\boldsymbol{q})_i\right| \quad (\because \boldsymbol{1}^T\boldsymbol{q}=0) \\ = & \left|\sum_{j=1}^n\alpha a_{ij}q_j\right| \\ \leq & \sum_{j=1}^n(\alpha a_{ij})|q_j| \\ = & \sum_{j=1}^n \left(B-\frac{1-\alpha}{n}\boldsymbol{1}\boldsymbol{1}^T\right)_{ij}|q_j| \\ = & \sum_{j=1}^n \left(b_{ij}-\frac{1-\alpha}{n}\right)|q_j| \\ = & \sum_{j=1}^n b_{ij}|q_j|-\frac{1-\alpha}{n}\|\boldsymbol{q}\|_1 \\ \end{aligned}$$

(4)

まず、$\boldsymbol{q}=\frac{\boldsymbol{1}}{n}-\boldsymbol{x}$ と定義される $\boldsymbol{q}$ を用いると、題意は、

$$\begin{aligned} & \|B^N\frac{\boldsymbol{1}}{n}-\boldsymbol{x}\|_1 \leq \alpha^N \|\frac{\boldsymbol{1}}{n}-\boldsymbol{x}\|_1 \\ \Leftrightarrow & \|B^N\frac{\boldsymbol{1}}{n}-B^N\boldsymbol{x}\|_1 \leq \alpha^N \|\boldsymbol{q}\|_1 \\ \Leftrightarrow & \|B^N\boldsymbol{q}\|_1 \leq \alpha^N \|\boldsymbol{q}\|_1 \\ \end{aligned}$$

になる。

特に、$\boldsymbol{1}^T\boldsymbol{q}=\boldsymbol{1}^T\frac{\boldsymbol{1}}{n}-\boldsymbol{1}^T\boldsymbol{x}=\frac{n}{n}-1=0$ であるが、この性質は、以下に示すように、$B$ を乗じても変わらない。

$$\begin{aligned} \boldsymbol{1}^T(B\boldsymbol{q}) & =\boldsymbol{1}^T \left(\alpha A+\frac{1-\alpha}{n}\boldsymbol{1}\boldsymbol{1}^T\right)\boldsymbol{q} \\ & =\alpha \boldsymbol{1}^TA\boldsymbol{q}+\frac{1-\alpha}{n}\boldsymbol{1}^T\boldsymbol{1}\boldsymbol{1}^T\boldsymbol{q} \\ & =\alpha \boldsymbol{1}^T\boldsymbol{q}+(1-\alpha)\boldsymbol{1}^T\boldsymbol{q} \\ & =\boldsymbol{1}^T\boldsymbol{q} \\ & =0 \quad (\because \boldsymbol{1}^T\boldsymbol{q}=0) \end{aligned}$$

よって、$\boldsymbol{1}^T\boldsymbol{q}=0$ を満たす $\boldsymbol{q}$ に関して、$\|B\boldsymbol{q}\|_1\leq \alpha\|\boldsymbol{q}\|_1$ であることを示せばよい。

これは、(3) で示したことから、

$$\begin{aligned} \|B\boldsymbol{q}\|_1 &\leq \alpha\sum_{i=1}^n\sum_{j=1}^n a_{ij}|q_j| \\ &=\alpha\sum_{j=1}^n\left(\sum_{i=1}^na_{ij}\right)|q_j| \\ &=\alpha\|\boldsymbol{q}\|_1. \end{aligned}$$

となり、直ちに従う。

Knowledge

コンパクト集合

$\mathbb{R}^n$ において、有界閉集合がコンパクト集合であって、閉集合がコンパクト集合である訳では無いことに注意。

例として、$\mathbb{R} \setminus (-1,1)$ は閉集合であるが、当然コンパクト集合ではない。

ブラウワーの不動点定理

(2) のヒントは、ブラウワーの不動点定理と呼ばれている。