2020-07-24

東京大学大学院情報理工学研究科数理情報学 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.

2020-07-23

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

院試

入試案内 | 東京大学大学院情報理工学系研究科

(1)

$C = (C_1, \dots , C_n), A = (A_1, \dots , A_n)$ とおくと, $BC + CB = A$ はクロネッカー積 $\otimes$ を用いて,
\begin{align}
(I_n \otimes B + B \otimes I_n) \begin{pmatrix}
C_1 \\
\vdots \\
C_n
\end{pmatrix}
=
\begin{pmatrix}
A_1 \\
\vdots \\
A_n
\end{pmatrix}
\end{align}と変形できる.
$B$ の固有値を $\lambda_1, \dots , \lambda_n$ とおくと, $I_n \otimes B + B \otimes I_n$ の固有値は $\lambda_i + \lambda_j, (1 \leq i, j \leq n)$ である.
$B$ は正定値より, $\lambda_i > 0, ^\forall i$ であるから, $\lambda_i + \lambda_j > 0, ^\forall i, j$ である.
したがって, $I_n \otimes B + B \otimes I_n$ は正則行列だから, $BC + CB = A$ を満たす $C$ はただ一つ存在する. Q.E.D.

(2)

(i) $BC_{A,B}=C_{A,B}B \Rightarrow AB=BA$ を示す.
\begin{align}
AB &= (BC_{A,B}+C_{A,B}B)B \\
&= BC_{A,B}B+C_{A,B}B^2 \\
&= B^2C_{A,B}+BC_{A,B}B \quad (\because BC_{A,B}=C_{A,B}B) \\
&= B(BC_{A,B}+C_{A,B}B) \\
&= BA
\end{align}Q.E.D
(ii) $BC_{A,B}=C_{A,B}B \Leftarrow AB=BA$ を示す.
$B$ は正定値より正則行列であることに注意すると,
\begin{align}
BC_{A,B}+C_{A,B}B=A &\Leftrightarrow BC_{A,B}B+C_{A,B}B^2 = AB \\
&\Leftrightarrow BC_{A,B}B+C_{A,B}B^2 = BA \quad (\because AB=BA)\\
&\Leftrightarrow C_{A,B}B+B^{-1}C_{A,B}B^2 = A \\
& \Leftrightarrow B(B^{-1}C_{A,B}B)+(B^{-1}C_{A,B}B)B = A\\
\end{align} $BC_{A,B}+C_{A,B}B=A$ の $C_{A,B}$ の一意性より,
\begin{align}
C_{A,B}=B^{-1}C_{A,B}B \Leftrightarrow BC_{A,B}=C_{A,B}B
\end{align}Q.E.D

2020-07-23

ABとBAの固有値

命題1
命題2

命題1

$K$ を体, $A, B \in M_n(K)$ とする.
このとき, $AB$ と $BA$ の固有値は(代数的)重複度も込めて等しい.

(証明)
$x \in K$ として,
\begin{align}
C = \begin{bmatrix} xI_n & A \\ B & I_n \end{bmatrix} , \quad D = \begin{bmatrix} I_n & 0 \\ -B & xI_n \end{bmatrix}
\end{align}
とおくと,
\begin{align}
CD = \begin{bmatrix} xI_n-AB & xA \\ 0 & xI_n \end{bmatrix} , \quad DC = \begin{bmatrix} xI_n & A \\ 0 & xI_n - BA \end{bmatrix}
\end{align}
$\Phi_{AB}(x), \Phi_{BA}(x)$ を $AB, BA$ の固有多項式とすると,
\begin{align}
x^n \Phi_{AB}(x) &= \text{det}(xI_n)\text{det}(xI_n-AB) \\
&= \text{det}(CD) \\
&= \text{det}(DC) \\
&= \text{det}(xI_n)\text{det}(xI_n-BA) \\
&=x^n \Phi_{BA}(x)
\end{align}
$x \neq 0$ として, $\Phi_{AB}(x) = \Phi_{BA}(x)$ であり, 明らかに $\Phi_{AB}(0) = \Phi_{BA}(0)$ だから,
したがって, $\Phi_{AB}(x) = \Phi_{BA}(x)$ が成り立つ. Q.E.D.

命題2

$K$ を体, $A \in M_{mn}(K), B \in M_{nm}(K)$ とする. ただし, $m \geq n$ とする.
このとき, $\Phi_{AB}(x) = x^{m-n}\Phi_{BA}(x)$ が成り立つ. すなわち,
m次行列 $AB$ と n次行列 $BA$ の非零固有値は(代数的)重複度も込めて等しい.

(証明)
$m=n$ のとき, 命題1より成り立つから, $m > n$ とする.
\begin{align}
\tilde{A} = \begin{bmatrix} A & 0_{m,m-n} \end{bmatrix} , \quad \tilde{B} = \begin{bmatrix} B \\ 0_{m-n,m} \end{bmatrix}
\end{align}
とおくと, $\tilde{A}, \tilde{B} \in M_m(K)$ であり,
\begin{align}
\tilde{A}\tilde{B} = AB , \quad \tilde{B}\tilde{A} = \begin{bmatrix} BA & 0_{n,m-n} \\ 0_{m-n,m} & 0_{m-n} \end{bmatrix}
\end{align}
である. 命題1より,
\begin{align}
\Phi_{AB}(x) &= \Phi_{\tilde{A}\tilde{B}}(x) \\
&= \Phi_{\tilde{B}\tilde{A}}(x) \\
&= \text{det}(xI_m-\tilde{B}\tilde{A}) \\
&= \text{det} \begin{bmatrix} xI_n - BA & 0_{n,m-n} \\ 0_{m-n,m} & xI_{m-n} \end{bmatrix}\\
&=x^{m-n} \Phi_{BA}(x)
\end{align}
Q.E.D.

2020-07-16

京都大学大学院理学研究科数学・数理解析専攻基礎科目 2017年度第3問解答

院試

過去の入試問題 | Department of Mathematics Kyoto University

(1)

$\lambda$ は $BA$ の固有値だから, ある $x \in \mathbb{C}^m$ が存在して, $BAx = \lambda x$ かつ $x \neq 0$ を満たす.
このとき,
\begin{align}
AB(Ax) = A(BAx)
= A(\lambda x)
= \lambda (Ax)
\end{align}
$Ax = 0$ と仮定すると, 両辺に左から $B$ を掛けると, $\lambda x = 0$ となる. このことは $\lambda \neq 0$ かつ $x \neq 0$ であることに矛盾するから, $Ax \neq 0$ である. よって, $\lambda$ は $AB$ の固有値でもある.

(2)

(1)の証明と同様の議論により, (1)の主張の逆も成り立つ. よって, $\lambda$ が $BA$ の固有値であることと $\lambda$ が $AB$ の固有値であることは同値である.(＊)
(i) $\lambda$ が $BA$ の固有値でないとき, (＊)より, $\lambda$ は $AB$ の固有値でもない.
よって, $V = \{0\} = W$ より, $\text{dim} V = \text{dim} W$ である.
(ii) $\lambda$ が $BA$ の固有値であるとき, (＊)より, $\lambda$ は $AB$ の固有値である.
このとき, $V$ は $BA$ の固有値 $\lambda$ に対応する一般固有空間であり, $W$ は $AB$ の固有値 $\lambda$ に対応する一般固有空間である.
一般に $BA$ と $AB$ の非零固有値は重複度も込めて等しいから, $\lambda \neq 0$ より, $BA$ の固有値としての $\lambda$ の重複度と $AB$ の固有値としての $\lambda$ の重複度は等しい.
また, 一般固有空間の次元は対応する固有値の重複度に一致するから, $\text{dim} V = \text{dim} W$ である.

2020-06-29

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

院試

(1)

明らかに, $A = \begin{bmatrix}1 & 1 & 1\\1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$ である.

(2)

明らかに, $A$ のランクは $\text{rank} \begin{bmatrix}1 & 1 & 1\\1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} = 3$ である.
明らかに, $A$ の特性方程式は $t^3 - t^2 - t - 1 = 0$ である.

(3)

固有値 $\lambda_i$ , $(i = 1, 2, 3)$ に対応する固有ベクトルを自明な方法で求めると, $\begin{bmatrix} \lambda_i^2 \\ \lambda_i \\ 1 \end{bmatrix}$ の定数倍で表せる.

(4)

写像 $f:\mathbb{R} \rightarrow \mathbb{R}$ を $f(t) = t^3 - t^2 - t - 1 = 0$ と定めると, $t$ の多項式より, 連続だから, その制限写像 $f|_{[0, 2]}$ も連続である.
$f(1) = -2 < 0$ , $f(2) = 1 > 0$ だから, 中間値の定理より, $f(c) = 0$ を満たす $c \in (1, 2)$ が存在する.
また, 高校数学より増減表を書くと, グラフ $f$ と $x$ 軸の交点は $t = c$ のみだとわかる.
よって, 主張を得る.

(5)

$\begin{bmatrix} T_{n+3} \\ T_{n+2} \\ T_{n+1} \end{bmatrix} = A \begin{bmatrix} T_{n+2} \\ T_{n+1} \\ T_n \end{bmatrix} = A^{n+1} \begin{bmatrix} T_2 \\ T_1\\ T_0 \end{bmatrix} = A^{n+1} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}$ である.
$(1)$ と $(3)$ より, $A$ は対角化可能で, $P := \begin{bmatrix} \lambda_1^2 & \lambda_2^2 & \lambda_3^2 \\ \lambda_1 & \lambda_2 & \lambda_3 \\ 1 & 1 & 1\end{bmatrix}$ とおくと,
\begin{align}
P^{-1} A P &= \begin{bmatrix} \lambda_1 & 0 & 0 \\ 0 & \lambda_2 & 0 \\ 0 & 0 & \lambda_3 \end{bmatrix} \\
A^{n+1} &= P \begin{bmatrix} \lambda_1^{n+1} & 0 & 0 \\ 0 & \lambda_2^{n+1} & 0 \\ 0 & 0 & \lambda_3^{n+1} \end{bmatrix} P^{-1}
\end{align}
$P \begin{bmatrix} \lambda_1^{n+1} & 0 & 0 \\ 0 & \lambda_2^{n+1} & 0 \\ 0 & 0 & \lambda_3^{n+1} \end{bmatrix}$ の第 $1$ 行の行ベクトルは $\begin{bmatrix} \lambda_1^{n+3} & \lambda_2^{n+3} & \lambda_3^{n+3} \end{bmatrix}$ でだから,
$P \begin{bmatrix} \lambda_1^{n+1} & 0 & 0 \\ 0 & \lambda_2^{n+1} & 0 \\ 0 & 0 & \lambda_3^{n+1} \end{bmatrix} P^{-1}$ の $(1, 1)$ 成分は, ある複素定数 $c_1, c_2, c_3$ を用いて, $c_1 \lambda_1^{n+3} + c_2 \lambda_2^{n+3} + c_3 \lambda_3^{n+3}$ と表せる.
よって, $T_{n+3} = c_1 \lambda_1^{n+3} + c_2 \lambda_2^{n+3} + c_3 \lambda_3^{n+3}$ , すなわち, $T_{n} = c_1 \lambda_1^{n} + c_2 \lambda_2^{n} + c_3 \lambda_3^{n}$ である.

(6)

$t^3 - t^2 - t - 1 = 0$ において解と係数の関係より, $\lambda_1 \lambda_2 \lambda_3 = 1$ が成立.
$(4)$ より, $|\frac{\lambda_2}{\lambda_1}||\frac{\lambda_3}{\lambda_1}| = |\frac{1}{\lambda_1}| < 1$ だから, $|\frac{\lambda_2}{\lambda_1}| <1$ または $|\frac{\lambda_3}{\lambda_1}| <1$ である.
$\lambda_2$ と $\lambda_3$ は複素共役より, $|\frac{\lambda_2}{\lambda_1}| <1$ かつ $|\frac{\lambda_3}{\lambda_1}| <1$ である.
よって, $\lim_{n \rightarrow \infty} \left(\frac{\lambda_2}{\lambda_1}\right)^n = 0$ , $\lim_{n \rightarrow \infty} \left(\frac{\lambda_3}{\lambda_1}\right)^n = 0$ である.
したがって,
\begin{align}
\lim_{n \rightarrow \infty} \frac{T_{n+1}}{T_n} &= \lim_{n \rightarrow \infty} \frac{c_1 \lambda_1^{n+1} + c_2 \lambda_2^{n+1} + c_3 \lambda_3^{n+1}}{c_1 \lambda_1^{n} + c_2 \lambda_2^{n} + c_3 \lambda_3^{n}} \\
&= \lim_{n \rightarrow \infty} \frac{c_1 \lambda_1 + c_2 \lambda_2 (\frac{\lambda_2}{\lambda_1})^{n} + c_3 \lambda_3 (\frac{\lambda_3}{\lambda_1})^{n}}{c_1 + c_2 (\frac{\lambda_2}{\lambda_1})^{n} + c_3 (\frac{\lambda_3}{\lambda_1})^{n}} \\
& = \lambda_1
\end{align}

2020-06-29

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

院試

(1)

自明.

(2)

自明.

(3)

自明.

(4)

自明.

(5)

$\hat{x} := (I + B^2)a$ , $b_k = \exp(\frac{2k\pi}{n}B)a$ , $(k = 1, \dots , n)$ とおく.
任意の $x \in \mathbb{R}^3$ に対し,
\begin{align}
f(x) &= \sum_{k=1}^n ||x-b_k||^2 \\
&= \sum_{k=1}^n ||(x-\hat{x}) + (\hat{x}-b_k)||^2 \\
&= \sum_{k=1}^n \{ ||x-\hat{x}||^2 + ||\hat{x}-b_k||^2 + 2(x-\hat{x})^T(\hat{x}-b_k)\} \\
&= \sum_{k=1}^n ||x-\hat{x}||^2 + \sum_{k=1}^n ||\hat{x}-b_k||^2 + 2(x-\hat{x})^T (\sum_{k=1}^n (\hat{x}-b_k))
\end{align}
ここで, $\sum_{k=1}^n (\hat{x}-b_k) = 0$ である.
実際, $(4)$ より,
\begin{align}
\sum_{k=1}^n b_k &= \left[ \sum_{k=1}^n \left\{I + \left(\sin\frac{2k\pi}{n}\right)B + \left(1 - \cos\frac{2k\pi}{n}\right)B^2 \right\} \right] a \\
&= \left\{n I + n B^2 + \left( \sum_{k=1}^n \sin\frac{2k\pi}{n}\right)B - \left( \sum_{k=1}^n \cos\frac{2k\pi}{n}\right)B^2 \right\} a
\end{align}
$z_k := \cos\frac{2k\pi}{n} + i \sin\frac{2k\pi}{n}$ , $(k = 1, \dots , n)$ は方程式 $z^n - 1 = 0$ の解である.
$n \geq 2$ のとき, 解と係数の関係より, $0 = \sum_{k=1}^n z_k = \sum_{k=1}^n \cos\frac{2k\pi}{n} + i \sum_{k=1}^n \sin\frac{2k\pi}{n}$ だから,
$\sum_{k=1}^n \cos\frac{2k\pi}{n} = \sum_{k=1}^n \sin\frac{2k\pi}{n} = 0$ である.
よって, $\sum_{k=1}^n b_k = (n I + n B^2) a$ だから, $\sum_{k=1}^n (\hat{x}-b_k) = 0$ である.
さて,
\begin{align}
f(x) &= \sum_{k=1}^n ||x-\hat{x}||^2 + \sum_{k=1}^n ||\hat{x}-b_k||^2 + 2(x-\hat{x})^T (\sum_{k=1}^n (\hat{x}-b_k)) \\
&= \sum_{k=1}^n ||x-\hat{x}||^2 + \sum_{k=1}^n ||\hat{x}-b_k||^2 \\
&\geq \sum_{k=1}^n ||\hat{x}-b_k||^2 \\
&= f(\hat{x})
\end{align}
従って, $\hat{x} = (I + B^2)a$ のとき, $f$ は最小となる.