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

标签：

• Tokyo-University
• PageRank-Teleportation-Fixed-Point-and-Contraction

Author

hari64boli64

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

を満たすことを示せ。

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}^n a_{ji}x_j\right| \leq \sum_{j}^n |a_{ji}\|x_j| \leq \sum_{j}^n |a_{ji}\|x_i| \leq |x_i|\sum_{j}^n a_{ji} = |x_i| < |\lambda\|x_i|=|\lambda x_i| \end{aligned}$$

つまり、$\lambda$ が $1$ より大きな値を取ると、この不等式に反し矛盾。

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

(2)

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

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

ここで、$S=T$ を証明する。

$$\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$ の値域より、$T \subset \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}+\frac{1-\alpha}{n}\boldsymbol{1}^T\boldsymbol{x} \\ & =\alpha+\frac{1-\alpha}{n} \\ & =1 \end{aligned}$$

よって、$T=S$ である。

$S$ が $\mathbb{R}^n$ の非空なコンパクト集合であることは、$S$ が $\mathbb{R}^n$ の有界閉集合であることから、これはコンパクト。

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

$$\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}+\frac{1-\alpha}{n}\boldsymbol{1}^T\boldsymbol{q} \\ & =\left(\alpha+\frac{1-\alpha}{n}\right)\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})_i| & \leq \sum_{j=1}^n(\alpha a_{ij})|q_j| \\ & \leq \alpha \sum_{j=1}^n |q_j| \\ & =\alpha \|\boldsymbol{q}\|_1 \end{aligned}$$

となり、直ちに従う。

Knowledge

コンパクト集合

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

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

ブラウワーの不動点定理

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