---
title: "東京大学大学院　情報理工入試過去問（数学）解答・２０１７年　第一問"
tags: u-tokyo, exam
---

# 東京大学大学院　情報理工入試過去問（数学）<br><span style="float: right;">―解答・２０１７年　第一問</span>

<style>
.markdown-body h1 > span:last-child{
font-size: 18pt;
float: right;
width: 100%;
text-align: right;
border-bottom: 1pt #EEE solid;
padding-bottom: 5pt;
margin-bottom: 5pt
}

.markdown-body h1{
border: none;
}

.markdown-body h2{
padding-top: 8px;
padding-left: 5px;
color: black;
background-color: #F2D7D9;
z-index: 1;
}

.markdown-body h3{
padding: 5px 0 5px 5px;
background-color: #D3CEDF
}

.markdown-body h4{
position: relative;
line-height: 28pt;
padding-left: 5px;
color: #FFFFFF;
font-size: 13pt;
background-color: #9CB4CC;
}

.markdown-body strong{
color: #555555;
letter-spacing: 0.5px;
text-transform: uppercase;
position: relative;
z-index: 0;
}

.markdown-body strong:after{
content: "";
position: absolute;
left: 10%;
bottom: 0;
height: 45%;
width: 90%;
background-color: #F2D7D9;
z-index: -1;
}

.markdown-body .alert-info{
background-color: #748DA6;
border: none;
box-shadow: 4px 4px 3px #9CB4CC;
color: #FFFFFF;
}

.markdown-body .mjx-sub{
font-size: 65% !important;
}

/* Pallete #F2D7D9 #D3CEDF #9CB4CC #748DA6 */
</style>

<!-- Requiring Mathjax Packages -->
$$
\require{cancel}
$$

<!-- Probability & Statistics Related -->
$$
\newcommand{\prob}[1]{\mathrm{P}(#1)}
\newcommand{\probsub}[2]{\mathrm{P}_{#1}(#2)}
\newcommand{\func}[2]{\mathrm{#1}(#2)}
\newcommand{\funcsub}[3]{\mathrm{#1}_{#2}(#3)}
\newcommand{\excp}[1]{\mathrm{E}(#1)}
\newcommand{\cdf}[1]{\mathrm{F}(#1)}
$$

<!-- Linear Algebra Related -->
$$
\require{boldsymbol}
\newcommand{\vec}[1]{\boldsymbol{#1}}
\newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}}
\newcommand{\vmat}[1]{\begin{vmatrix} #1 \end{vmatrix}}
\newcommand{\rank}[1]{\mathrm{rank}(#1)}
\newcommand{\norm}[1]{\| #1 \|}
\newcommand{\trps}[1]{#1^{\moveleft{1.5px}{\raise{2px}{\mathrm{T}}}}}
\newcommand{\inv}[1]{#1^{-1}}
$$

<!-- General Macros -->
$$
\newcommand{\intinf}{\displaystyle\int^{\infty}_{-\infty}}
\newcommand{\intlo}[1]{\displaystyle\int^{#1}_{-\infty}}
\newcommand{\inthi}[1]{\displaystyle\int^{\infty}_{#1}}
\newcommand{\nobj}[3]{#1_1{\;#3\;} #1_2{\;#3} \;\ldots\; {#3\;} #1_#2}
\newcommand{\nobjsfx}[4]{#1_1#3{\;#4\;} #1_2#3{\;#4} \;\ldots\; {#4\;} #1_#2#3}
$$

+ こちらの解答は非公式で個人記録用に作成されており、大学院側に認められたものではありません。正確性についての保証は致しかねます。
+ 問題本文は研究科のウェブサイトから見ることができます。
+ 満足出来た解答でしたらコメントしていただけると幸いです。

## ２０１７年　第一問
Let there be $x_n, y_n, z_n$ such that:
$$
\bmat{x_{n + 1} \\ y_{n + 1} \\ z_{n + 1}} = A\bmat{x_n \\ y_n \\ z_n}
$$

With conditions:
$$
A = \bmat{
1 - 2\alpha & \alpha & \alpha \\
\alpha & 1 - \alpha & 0 \\
\alpha & 0 & 1 - \alpha
}\;, \;\;\;\;\;\;\;\;\;
\begin{cases}
0 \leq \alpha \leq \frac{1}{3} \\
x_0, y_0, z_0, \alpha \in \mathbb{R}
\end{cases}
$$

### (1) Represent $x_n + y_n + z_n$ using $x_0,\,y_0$ and $z_0$.
Expand the equation, we get:
$$
\bmat{x_{n + 1} \\ y_{n + 1} \\ z_{n + 1}} = \bmat{
(1 - 2\alpha)x_n + \alpha y_n + \alpha z_n \\
\alpha x_n + (1 - \alpha)y_n \\
\alpha x_n + (1 - \alpha)z_n
}
$$

Let $S_n = x_n + y_n + z_n$, we further get:
$$
S_n = (1 - 2\alpha + \alpha + \alpha)x_{n - 1} + (\alpha + 1 - \alpha)y_n + (\alpha + 1 - \alpha)z_n = x_{n - 1} + y_{n - 1} + z_{n - 1} = S_{n - 1}
$$

Indicating the result,
$$
x_n + y_n + z_n = S_n = S_{n - 1} = S_{n - 2} = \ldots = S_0 = x_0 + y_0 + z_0
$$

:::info
$A$ is a markov matrix, meaning the sum of each entry in $A^t\vec{x}$ keeps the same as $\vec{x}$ for any $t \in \mathbb{N}$.
:::

### (2) Find the eigenvalues $\lambda_1,\,\lambda_2,\,$ and $\lambda_3$ for $A$, and the corresponding eigenvectors.
For any eigenvalue $\lambda$, $\det{\left( A - I\lambda \right)} = 0$. So,
$$
\begin{align}
\vmat{
1 - 2\alpha - \lambda & \alpha & \alpha \\
\alpha & 1 - \alpha - \lambda & 0 \\
\alpha & 0 & 1 - \alpha - \lambda
}
&= \alpha\vmat{\alpha & \alpha \\ 1 - \alpha - \lambda & 0} +
(1 - \alpha - \lambda)\vmat{1 - 2\alpha - \lambda & \alpha \\ \alpha & 1 - \alpha - \lambda } \\[1ex]
&= -\alpha^2( 1 - \alpha - \lambda) + (1 - \alpha - \lambda)\left[ \lambda^2 + (3\alpha - 2)\lambda + \alpha^2 - 3\alpha + 1 \right] \\[1ex]
&= (1 - \alpha - \lambda)\left[ \lambda^2 + (3\alpha - 2)\lambda - 3\alpha + 1 \right] \\[1ex]
&= (-\lambda + 1 - \alpha)(\lambda + 3\alpha - 1)(\lambda - 1) = 0
\end{align}
$$

So we get
$$
\begin{cases}
\lambda_1 = 1 - \alpha \\
\lambda_2 = 1 - 3\alpha\\
\lambda_3 = 1
\end{cases}
$$

+ For $\lambda_1 = 1 - \alpha$,
$$
A - I\lambda_1 = \bmat{
-\alpha & \alpha & \alpha \\
\alpha & 0 & 0 \\
\alpha & 0 & 0
} \xrightarrow{\text{elimination }} \bmat{
-\alpha & \alpha & \alpha \\
0 & \alpha & \alpha \\
0 & 0 & 0
}
$$
So the corresponding eigenvector $v_1 = t_1\bmat{0 \\ -1 \\ 1}, t_1\in\mathbb{R}, t_1 \neq 0$.

+ For $\lambda_2 = 1 - 3\alpha$,
$$
A - I\lambda = \bmat{
\alpha & \alpha & \alpha \\
\alpha & 2\alpha & 0 \\
\alpha & 0 & 2\alpha
} \xrightarrow{\text{elimination }} \bmat{
\alpha & \alpha & \alpha \\
0 & \alpha & -\alpha \\
0 & 0 & 0
}
$$
So the corresponding eigenvector $v_2 = t_2\bmat{-2 \\ 1 \\ 1}, t_2\in\mathbb{R}, t_2 \neq 0$.

+ For $\lambda_3 = 1$,
$$
A - I\lambda = \bmat{
-2\alpha & \alpha & \alpha \\
\alpha & -\alpha & 0 \\
\alpha & 0 & -\alpha
} \xrightarrow{\text{elimination }} \bmat{
-2\alpha & \alpha & \alpha \\
0 & -\frac{\alpha}{2} & \frac{\alpha}{2} \\
0 & 0 & 0
}
$$
So the corresponding eigenvector $v_3 = t_3\bmat{1 \\ 1 \\ 1}, t_3\in\mathbb{R}, t_3 \neq 0$.

### (3) Represent matrix $A$ using $\lambda_1,\,\lambda_2,\,\lambda_3,\,v_1,\,v_2$ and $v_3$.
According to the properties of eigenvalue and eigenvectors, we know for any eigenvalue $\lambda_i$ of $A$ and its correspionding eigenvector $v_i$,
$$
Av_i = \lambda_iv_i
$$

Which induces $AU = U\Lambda$, where
$$
U = \bmat{
| & | & | \\
v_1 & v_2 & v_3 \\
| & | & | \\
}, \Lambda = \bmat{
\lambda_1 & 0 & 0 \\
0 & \lambda_2 & 0 \\
0 & 0 & \lambda_3
}
$$

Since $\det{U} = \vmat{0 & -2 & 1 \\ -1 & 1 & 1 \\ 1 & 1 & 1} = -5$, $U$ is invertible, concluding in:
$$
A = U\Lambda\inv{U}
$$

### (4) Represent $\bmat{x_n \\ y_n \\ z_n}$ using $x_0,\,y_0,\,z_0$ and $\alpha$.
$$
\bmat{x_n \\ y_n \\ z_n} = A\bmat{x_{n - 1} \\ y_{n - 1} \\ z_{n - 1}}
= A^2\bmat{x_{n - 2} \\ y_{n - 2} \\ z_{n - 2}} =
\cdots
= A^n\bmat{x_0 \\ y_0 \\ z_0}
$$

Since $A$ can be expressed as $U\Lambda\inv{U}$,
$$
A^n = (U\Lambda\inv{U})^n = U\Lambda\cancel{\inv{U}U}\Lambda\cancel{\inv{U} }\ldots \cancel{ U}\Lambda\inv{U} = U\Lambda^n\inv{U}
$$

Thus,
$$\begin{align}
\bmat{x_n \\ y_n \\ z_n} &= U\Lambda^n\inv{U}\bmat{x_0 \\ y_0 \\ z_0} \\[1ex]
&= \bmat{0 & -2 & 1 \\ -1 & 1 & 1 \\ 1 & 1 & 1}
\bmat{\lambda_1^n & 0 & 0 \\ 0 & \lambda_2^n & 0 \\ 0 & 0 & \lambda_3^n}
\frac{1}{6}\bmat{0 & -3 & 3 \\ -2 & 1 & 1 \\ 2 & 2 & 2}
\bmat{x_0 \\ y_0 \\ z_0} \\
&= \frac{1}{6}\bmat{
\left[ 2+4(1 - 3\alpha)^n \right]x_0 + \left[ 2-2(1-3\alpha)^n \right]y_0 + \left[ 2-2(1-3\alpha)^n \right]z_0 \\
\left[ 2-2(1 - 3\alpha)^n \right]x_0 + \left[ 2+3(1-\alpha)^n+(1-3\alpha)^n \right]y_0 + \left[ 2-3(1-\alpha)^n+(1-3\alpha)^n \right]z_0 \\
\left[ 2-2(1 - 3\alpha)^n \right]x_0 + \left[ 2-3(1-\alpha)^n+(1-3\alpha)^n \right]y_0 + \left[ 2+3(1-\alpha)^n+(1-3\alpha)^n \right]z_0
}
\end{align}
$$

### (5) Find $\displaystyle\lim_{n \rightarrow \infty} \bmat{x_n \\ y_n \\ z_n}$
Since $0 < \alpha < \frac{1}{3}$, we know
$$
\displaystyle\lim_{n \rightarrow \infty}(1 - \alpha)^n = 0 \\
\displaystyle\lim_{n \rightarrow \infty}(1 - 3\alpha)^n = 0 \\
$$

So:
$$
\displaystyle\lim_{n \rightarrow \infty} \bmat{x_n \\ y_n \\ z_n} =
\frac{1}{6}\bmat{
2x_0 + 2y_0 + 2z_0\\
2x_0 + 2y_0 + 2z_0\\
2x_0 + 2y_0 + 2z_0
} = \frac{1}{3}\bmat{x_0 + y_0 + z_0 \\ x_0 + y_0 + z_0 \\ x_0 + y_0 + z_0}
$$

### (6) Find min/max value of the function $f(x_0, y_0, z_0) = \frac{\bmat{x_n & y_n & z_n}\bmat{x_{n + 1} \\ y_{n + 1} \\ z_{n + 1}}}{\bmat{x_n & y_n & z_n}\bmat{x_n \\ y_n \\ z_n}}$
:::success
This question is not yet solved by be :(
:::
Let $U^*$ be the matrix whose columns are eigenvectors of $A$ with unit length, and $\vec{x} = \bmat{x_0 \\ y_0 \\ z_0}$.
+ Since $U^*$ is a orthogonal matrix, $\trps{(U^*)} = \inv{(U^*)}$.
+ Since $\Lambda^n$ is diagonal, $\trps{(\Lambda^n)} = \Lambda^n$.

Then,
$$
\begin{align}
\bmat{x_n & y_n & z_n}\bmat{x_n \\ y_n \\ z_n} &= \trps{(A^n\vec{x})}(A^n\vec{x}) = \trps{\vec{x}}\trps{(A^n)}A^n\vec{x} \\[1ex]
&= \trps{\vec{x}}\trps{((U^*)\Lambda^n\inv{(U^*)})}((U^*)\Lambda^n\inv{(U^*)})\vec{x} \\
&= \trps{\vec{x}} \trps{(\inv{(U^*)})}\trps{(\Lambda_n)}\trps{(U^*)}(U^*)\Lambda^n\inv{(U^*)} \vec{x} \\
&= \trps{\vec{x}} U^*\Lambda^{2n} \trps{(U^*)} \vec{x} \\
&= \trps{\vec{x}}A^{2n}\vec{x}
\end{align}
$$

And simularily, $\bmat{x_n & y_n & z_n}\bmat{x_{n + 1} \\ y_{n + 1} \\ z_{n + 1}} = \trps{\vec{x}}A^{2n+1}\vec{x}$

Since $\vec{x}$ is able to be represented by combinations of its eigenvectors, we can say for some $k_1, k_2, k_3 \in \mathbb{R}$ and $n \in \mathbb{N}$:
$$
A^n\vec{x} = k_1\lambda_1^n\vec{x}_1 + k_2\lambda_2^n\vec{x}_2 + k_3\lambda_3^n\vec{x}_3
$$

Thus we can instead write $f(x_0, y_0, z_0)$ as:
$$
\begin{align}
f(x_0, y_0, z_0) &= \frac{\trps{\left( k_1\lambda_1\vec{x}_1 + k_2\lambda_2\vec{x}_2 + k_3\lambda_3\vec{x}_3 \right)}\left( k_1\lambda_1^{2n+1}\vec{x}_1 + k_2\lambda_2^{2n+1}\vec{x}_2 + k_3\lambda_3^{2n+1}\vec{x}_3 \right)}{\trps{\left( k_1\lambda_1\vec{x}_1 + k_2\lambda_2\vec{x}_2 + k_3\lambda_3\vec{x}_3 \right)}\left( k_1\lambda_1^{2n}\vec{x}_1 + k_2\lambda_2^{2n}\vec{x}_2 + k_3\lambda_3^{2n}\vec{x}_3 \right)} \\[1ex]
&= \frac{k_1^2\lambda_1^{2n+2}\|\vec{x}_1\|^2+k_2^2\lambda_2^{2n+2}\|\vec{x}_2\|^2+k_3^2\lambda_3^{2n+2}\|\vec{x}_3\|^2}{k_1^2\lambda_1^{2n+1}\|\vec{x}_1\|^2+k_2^2\lambda_2^{2n+1}\|\vec{x}_2\|^2+k_3^2\lambda_3^{2n+1}\|\vec{x}_3\|^2} \\[1ex]
&= \frac{c_1(1 - \alpha) + c_2(1 - 3\alpha) + c_3}{c_1 + c_2 + c_3}
\end{align}
$$
Where
$$
c_1 = k_1^2\lambda_1^{2n+1}\|\vec{x_1}\|^2 = 2k_1^2\lambda_1^{2n+1} \geq 0\\[1ex]
c_2 = k_2^2\lambda_2^{2n+1}\|\vec{x_2}\|^2 = 6k_2^2\lambda_2^{2n+1} \geq 0\\[1ex]
c_3 = k_3^2\lambda_3^{2n+1}\|\vec{x_3}\|^2 = 3k_3^2 \geq 0
$$

+ Since $0 < 1 - \alpha < 1$ and $0 < 1 - 3\alpha < 1$,
$$
\begin{cases}
|c_1(1 - \alpha) + c_2(1 - 3\alpha)|<|c_1 + c_2| \\[1ex]
(c_1(1 - \alpha) + c_2(1 - 3\alpha) + c_3) \cdot (c_1 + c_2 + c_3) > 0
\end{cases}
$$

Implying the maximum is when $c_1(1 - \alpha) + c_2(1 - 3\alpha) = 0$, then $f(x_0, y_0, z_0) = 1$,
and the minimum when $c_3 = 0$ and ?