東京大学大学院情報理工学研究科数理情報学 2019年度第1問解答

管理人のLatexの技術力の問題で, $\mathbb{I} := (1, \dots , 1)^T$ と書くことにする.

(1)

行列 $A$ とその転置行列 $A^T$ の固有値は代数的重複度を込めて等しいから, $A^T$ を考える.
\begin{align}
A^T\mathbb{I} = \mathbb{I}
\end{align}より, $1$ は $A^T$ の固有値である.
一方. $A^T$ のスペクトル半径 $\rho (A^T)$ について,
\begin{align}
\rho (A^T) \leq \max_{1 \leq i \leq n}\sum_{j=1}^n|a_{ji}| = \max_{1 \leq i \leq n}\sum_{j=1}^na_{ji} = 1
\end{align}よって, $\rho (A^T)=1$ だから, 行列 $A$ の固有値の絶対値で最大となるものは $1$ である.

(2)

任意の $x \in \{x \in \mathbb{R}^n_{>0}|\mathbb{I}^Tx=1\} =: V$ に対し,
\begin{align}
\mathbb{I}^TBx = \mathbb{I}^T(\alpha A + \frac{1-\alpha}{n}\mathbb{I}\mathbb{I}^T)x=1
\end{align}であり, $B$ は正行列だから, $Bx \in V$ である.
よって, 写像 $f:V \rightarrow V$ , $x \mapsto Bx$ を定められる.
写像 $f$ は行列写像より, 連続だから, $V$ が $\mathbb{R}^n$ の非空なコンパクト凸集合ならば, 問題文の事実から不動点が存在し, 主張を得る.
$V$ が $\mathbb{R}^n$ の非空なコンパクト凸集合であることを示す.

$\mathbb{I}^T\frac{\mathbb{I}}{n}=1$ より, $\frac{\mathbb{I}}{n} \in V$ .
$V$ は, $V \subset [0,1] \times \dots \times [0,1]$ より有界であり, 連続写像 $x \mapsto \mathbb{I}^Tx$ による閉集合 $\{1\}$ の逆像だから閉集合であるから, コンパクト.
$^\forall x,y \in V, ^\forall t \in [0,1]$ に対し, $(1-t)x+ty \in \mathbb{R}^n_{>0}$ かつ $\mathbb{I}^T((1-t)x+ty)=1$ より, $V$ は凸集合.

Q.E.D.

(3)

$\mathbb{I}q=0$ より, $Bq=\alpha Aq$ だから, 各 $i$ に対し,
\begin{align}
\sum_{j=1}^nb_{ij}q_{j}=\sum_{j=1}^n \alpha a_{ij}q_{j}
\end{align}よって,
\begin{align}
\left|\sum_{j=1}^nb_{ij}q_{j}\right| &= \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 (b_{ij}-\frac{1-\alpha}{n})|q_{j}| \quad (\because Bの定義) \\
&= \sum_{j=1}^n b_{ij}|q_{j}| -\frac{1-\alpha}{n}\sum_{j=1}^n|q_{j}| \\
&= \sum_{j=1}^n b_{ij}|q_{j}| -\frac{1-\alpha}{n} ||q||_1
\end{align}Q.E.D.

(4)

1のベクトルノルム $||\cdot||_1$ から誘導される1の行列ノルムを
\begin{align}
\|X\|_1 = \max_{1 \leq j \leq n}\sum_{i=1}^n|x_{ij}|
\end{align}で定める. このとき, $||B||_1 = \alpha$ である. （←は間違い. 正しくは $||B||_1 = 1$ . よって, 以下の証明は回っていない. ご指摘感謝）
(2)の条件を満たす $x \in \mathbb{R}^n$ に対し,
\begin{align}
\left|\left|B^N\frac{\mathbb{I}}{n}-x\right|\right|_1 &= \left|\left|B^N\frac{\mathbb{I}}{n}-B^Nx\right|\right|_1 \\
&= \left|\left|B^N(\frac{\mathbb{I}}{n}-x)\right|\right|_1 \\
& \leq ||B^N||_1 \left|\left|\frac{\mathbb{I}}{n}-x\right|\right|_1 \\
&\leq ||B||_1^N \left|\left|\frac{\mathbb{I}}{n}-x\right|\right|_1 \\
&= \alpha^N \left|\left|\frac{\mathbb{I}}{n}-x\right|\right|_1
\end{align}Q.E.D.

(4)の正しい証明を以下に与える.
$q := \frac{\mathbb{I}}{n} - x$ とおくと, $\mathbb{I}^Tq = 0$ が成り立つから,

\begin{align}
\left|\left|Bq\right|\right|_1 &= \sum_{i=1}^n \left|\sum_{j=1}^nb_{ij}q_{j}\right| \\
&\leq \sum_{i=1}^n \left( \sum_{j=1}^n b_{ij}|q_{j}| -\frac{1-\alpha}{n} ||q||_1 \right) \quad (\because (3)) \\
&= \sum_{i=1}^n \sum_{j=1}^n b_{ij}|q_{j}| -(1-\alpha) ||q||_1 .
\end{align}
ここで,
\begin{align}
\sum_{i=1}^n \sum_{j=1}^n b_{ij}|q_{j}| &= \sum_{i=1}^n \sum_{j=1}^n \left(\alpha a_{ij} + \frac{1 - \alpha}{n} \right)|q_{j}| \\
&= \alpha ||q||_1 + (1 - \alpha)||q||_1 \\
&= ||q||_1
\end{align}となるから,
\begin{align}
\left|\left|Bq\right|\right|_1 \leq \alpha ||q||_1
\end{align}を得る.
また, $\mathbb{I}^TB = \mathbb{I}^T$ より, 任意の $M \in \mathbb{Z}_{\geq 1}$ に対して,
\begin{align}
\mathbb{I}^TB^Mq = 0
\end{align}が成り立つ. よって, $B^Mq$ に対して同様の議論より，任意の $M \in \mathbb{Z}_{\geq 1}$ に対して,
\begin{align}
\left|\left|B^{M+1}q\right|\right|_1 \leq \alpha \left| \left|B^Mq\right|\right|_1
\end{align}を得る. 従って,
\begin{align}
\left|\left|B^N\frac{\mathbb{I}}{n}-x\right|\right|_1 &= \left|\left|B^N\frac{\mathbb{I}}{n}-B^Nx\right|\right|_1 \\
&= \left|\left|B^N(\frac{\mathbb{I}}{n}-x)\right|\right|_1 \\
& \leq \alpha \left|\left|B^{N-1}\left(\frac{\mathbb{I}}{n}-x\right)\right|\right|_1 \\
&\leq \cdots \\
&= \alpha^N \left|\left|\frac{\mathbb{I}}{n}-x\right|\right|_1
\end{align}

Q.E.D.