Todai Entrance Exam: Math 2017 – Problem 1

(1)

    \[ \begin{pmatrix} x_{n+1}\\  y_{n+1}\\  z_{n+1} \end{pmatrix} = A\begin{pmatrix} x_{n}\\  y_{n}\\  z_{n} \end{pmatrix} = \begin{pmatrix} (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} \end{pmatrix} \]

    \[ x_{n + 1} + y_{n + 1} + z_{n + 1} = x_{n} + y_{n} + z_{n} \]

Therefore:

    \[ x_{n} + y_{n} + z_{n} = x_{0} + y_{0} + z_{0} \]

(2)

    \[ \det(A - \lambda I) = (1 - \alpha - \lambda)(1 - \lambda)(1 - \lambda - 3\alpha) = 0 \Leftrightarrow \begin{Bmatrix} \lambda_{1} = 1\\  \lambda_{2} = 1 - \alpha\\  \lambda_{3} = 1 - 3\alpha \end{matrix} \]

Then we solve the equation (A - \lambda I)v = 0 for each \lambda, we then arrive:

    \[ \begin{Bmatrix} v_{1} = (1, 1, 1)\\  v_{2} = (0, 1, -1)\\  v_{3} = (-2, 1, 1) \end{matrix} \]

(3)

    \[ A = \begin{pmatrix} v_{1} & v_{2} & v_{3} \end{pmatrix}\begin{pmatrix} \lambda_{1} & 0 & 0 \\  0 & \lambda_{2} & 0 \\  0 & 0 & \lambda_{3} \end{pmatrix}\begin{pmatrix} v_{1} & v_{2} & v_{3} \end{pmatrix}^{-1} = \begin{pmatrix} 1 & 0 & -2 \\  1 & 1 & 1 \\  1 & -1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 \\  0 & 1 - \alpha & 0 \\  0 & 0 & 1 - 3\alpha \end{pmatrix}\begin{pmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\  0 & \frac{1}{2} & -\frac{1}{2} \\  -\frac{1}{3} & \frac{1}{6} & \frac{1}{6} \end{pmatrix} \]

(4)

As:

    \[ A^{2} = \begin{pmatrix} v_{1} & v_{2} & v_{3} \end{pmatrix}\begin{pmatrix} \lambda_{1} & 0 & 0 \\  0 & \lambda_{2} & 0 \\  0 & 0 & \lambda_{3} \end{pmatrix}\begin{pmatrix} v_{1} & v_{2} & v_{3} \end{pmatrix}^{-1}\begin{pmatrix} v_{1} & v_{2} & v_{3} \end{pmatrix}\begin{pmatrix} \lambda_{1} & 0 & 0 \\  0 & \lambda_{2} & 0 \\  0 & 0 & \lambda_{3} \end{pmatrix}\begin{pmatrix} v_{1} & v_{2} & v_{3} \end{pmatrix}^{-1} \]

    \[ A^{2} = \begin{pmatrix} v_{1} & v_{2} & v_{3} \end{pmatrix}\begin{pmatrix} \lambda_{1}^{2} & 0 & 0 \\  0 & \lambda_{2}^{2} & 0 \\  0 & 0 & \lambda_{3}^{2} \end{pmatrix}\begin{pmatrix} v_{1} & v_{2} & v_{3} \end{pmatrix}^{-1} \]

Therefore:

    \[ A^{n} =  \begin{pmatrix} v_{1} & v_{2} & v_{3} \end{pmatrix}\begin{pmatrix} \lambda_{1}^{n} & 0 & 0 \\  0 & \lambda_{2}^{n} & 0 \\  0 & 0 & \lambda_{3}^{n} \end{pmatrix}\begin{pmatrix} v_{1} & v_{2} & v_{3} \end{pmatrix}^{-1} \]

So:

    \[ \begin{pmatrix} x_{n}\\  y_{n}\\  z_{n} \end{pmatrix} = A^{n}\begin{pmatrix} x_{0}\\  y_{0}\\  z_{0} \end{pmatrix} =  \begin{pmatrix}  1 & 0 & -2 \\   1 & 1 & 1 \\   1 & -1 & 1  \end{pmatrix}\begin{pmatrix}  1 & 0 & 0 \\   0 & (1 - \alpha)^{n} & 0 \\  0 & 0 & (1 - 3\alpha)^{n}  \end{pmatrix}\begin{pmatrix}  \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\   0 & \frac{1}{2} & -\frac{1}{2} \\   -\frac{1}{3} & \frac{1}{6} & \frac{1}{6}  \end{pmatrix}\begin{pmatrix} x_{0}\\  y_{0}\\  z_{0} \end{pmatrix} \]

(5)

    \[ \lim_{n \rightarrow \infty}\begin{pmatrix}  x_{n}\\   y_{n}\\   z_{n}  \end{pmatrix} = \begin{pmatrix}   1 & 0 & -2 \\    1 & 1 & 1 \\   1 & -1 & 1   \end{pmatrix}\begin{pmatrix}   1 & 0 & 0 \\    0 & \lim_{n \rightarrow \infty}(1 - \alpha)^{n} & 0 \\   0 & 0 & \lim_{n \rightarrow \infty}(1 - 3\alpha)^{n}   \end{pmatrix}\begin{pmatrix}   \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\    0 & \frac{1}{2} & -\frac{1}{2} \\    -\frac{1}{3} & \frac{1}{6} & \frac{1}{6}   \end{pmatrix}\begin{pmatrix}  x_{0}\\   y_{0}\\   z_{0}  \end{pmatrix} \]

Notice:

    \[ 0 < \alpha < \frac{1}{3} \Leftrightarrow \begin{Bmatrix} \frac{2}{3} < 1 - \alpha < 1 \\  0 < 1 - 3\alpha < 1 \end{matrix} \]

Therefore \lim_{n \rightarrow \infty}(1 - \alpha)^{n} = 0 and \lim_{n \rightarrow \infty}(1 - 3\alpha)^{n} = 0.

    \[ \lim_{n \rightarrow \infty}\begin{pmatrix}  x_{n}\\   y_{n}\\  z_{n}  \end{pmatrix} = \frac{1}{3}\begin{pmatrix}  x_{0} + y_{0} + z_{0}\\  x_{0} + y_{0} + z_{0}\\   x_{0} + y_{0} + z_{0}  \end{pmatrix} \]

(6)

    \[ f(x_0, y_0, z_0) = \frac{(x_n, y_n, z_n)\begin{pmatrix}  x_{n+1}\\   y_{n+1}\\   z_{n+1}  \end{pmatrix}}{(x_n, y_n, z_n)\begin{pmatrix}  x_{n}\\   y_{n}\\   z_{n}  \end{pmatrix}} = \frac{(x_n, y_n, z_n)A\begin{pmatrix} x_n\\  y_n\\  z_n \end{pmatrix}}{(x_n, y_n, z_n)\begin{pmatrix} x_n\\  y_n\\  z_n \end{pmatrix}} \]

Rayleigh quotient? See page 2 of this document for the proof of maximum and minimum. So (x_n, y_n, z_n) must be an eigenvector of A. We also have:

    \[ \begin{pmatrix}  x_{n}\\   y_{n}\\   z_{n}  \end{pmatrix} = A\begin{pmatrix}  x_{n-1}\\   y_{n-1}\\   z_{n-1}  \end{pmatrix} \]

So if (x_n, y_n, z_n) is an eigenvector of A then (x_{n-1}, y_{n-1}, z_{n-1}) must also be the same eigenvector of A. If we keep do this recursion, we will finally arrive the conclusion that (x_0, y_0, z_0) must also be the same eigenvector of A.

\forall k \in \mathbb{Z}, f attains the maximum value \lambda_{1} = 1 at (x_0, y_0, z_0) = k(1, 1, 1) and attains the minimum value \lambda_{3} = 1 - 3\alpha at (x_0, y_0, z_0) = k(-2, 1, 1).


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *