Problem 1 (yau-contest 2018)

We consider the following convection-diffusion equation
$$u_t + a u_x = b u_{xx},\quad 0 \le x < 1,$$
with an initial condition $u(x,0)=f(x)$ and periodic boundary condition, where $a$ and $b>0$ are constants. The first order IMEX (implicit-explicit) time discretization and second order central spatial discretization are used to give the following scheme:
$$\frac{u_j^{n+1}-u_j^{n}}{\Delta t} + a\,\frac{u_{j+1}^{n}-u_{j-1}^{n}}{2\Delta x} = b\,\frac{u_{j+1}^{n+1} - 2u_j^{n+1} + u_{j-1}^{n+1}}{\Delta x^2}.$$
with a uniform mesh $x_j=j\Delta x$ with spatial mesh size $\Delta x$ and time step $\Delta t$. Here $u_j^n$ is the numerical solution approximating the exact solution of (1) at $x=x_j$ and $t=n\Delta t$. Prove that the scheme is $L^2$ stable under the very mild time step restriction
$$\Delta t \le c,$$
with a constant $c$ which is independent of $\Delta x$. Can you determine the dependency of $c$ on the two constants $a$ and $b$ in (1)?

Problem 2 (yau-contest 2018)

Velocity-Verlet method.
(a) Recast the following Newtonian formula for the acceleration and potential force
$$q''(t) = -\nabla V(q),$$
into a Hamiltonian system and show that the corresponding map on the phase space is symplectic.
(b) Show that the velocity-Verlet (recovered many times: Delambre 1791, Størmer in 1907, Cowell & Crommelin 1909, Verlet 1960s) method
$$p_{n+1/2} = p_n - \frac{\Delta t}{2}\,\nabla V(q_n);$$
$$q_{n+1} = q_n + \Delta t\,p_{n+1/2};$$
$$p_{n+1} = p_{n+1/2} - \frac{\Delta t}{2}\,\nabla V(q_{n+1})$$
is symplectic and is second order accurate.

Hint: Let $u(t)=(p(t),q(t))$ be a solution of the Hamiltonian system with initial data $u_0=(p_0,q_0)$ and we view the solution $u(t)$ as a map on the phase space $\varphi_t:\,\mathbb{R}^d\times\mathbb{R}^d\to\mathbb{R}^d\times\mathbb{R}^d$, $\varphi_t(u_0)=u(t)$. We call the flow map symplectic if its Jacobian
$$\Phi_t(u_0)=\frac{\partial \varphi_t(u_0)}{\partial u_0}=\begin{pmatrix}\dfrac{\partial p(t)}{\partial p_0} & \dfrac{\partial p(t)}{\partial q_0}\\[6pt] \dfrac{\partial q(t)}{\partial p_0} & \dfrac{\partial q(t)}{\partial q_0}\end{pmatrix}$$
satisfies $\Phi_t(u_0)^T J\,\Phi_t(u_0)=J$ for any $u_0\in\mathbb{R}^d\times\mathbb{R}^d$. Here $J=\begin{pmatrix}0 & I\\ -I & 0\end{pmatrix}$. A scheme $\varphi_n(u_0)$, $n=1,2,\ldots$, is symplectic if the map $\varphi_n(u_0)$ is symplectic.

Problem 3 (yau-contest 2018)

We begin with some definitions.
(1) A graph $G$ is a pair $G=(V,E)$ where $V$ is a finite set, called the vertices of $G$, and $E$ is a subset of $P_2(V)$ (i.e., a set $E$ of (unordered) two-element subsets of $V$), called the edges of $G$. A simple graph $G$ is a graph without loops (edge that connects a vertex to itself) or multiple edges between any pair of vertices. The order of the graph is $|V|$. We often put $V=\{v_1,v_2,\cdots,v_n\}$ and $E=\{v_i v_j\mid v_i\text{ and }v_j\text{ are adjacent}\}$.
(2) Two vertices $x$ and $y$ are adjacent if $xy\in E$. The neighborhood of a vertex $x$, denoted by $N_G(x)$ or $N(x)$, is the set of vertices that is adjacent to $x$. The degree of a vertex $x$, denoted by $d_G(x)$ or $d(x)$, is $|N(x)|$ (i.e., the number of vertices that is adjacent to $x$).
(3) A path is a collection of distinct vertices $v_i, v_{i_2}\cdots v_{i_k}$ such that $v_i v_{i_{j+1}}\in E$ for all $j$, $1\le j<k$. $v_i$ and $v_{i_k}$ are the ends of the path. A Hamiltonian path $P$ is a path containing all vertices of the graph. A cycle is a closed path with $v_i=v_{i_k}$. A Hamiltonian cycle is a cycle containing all vertices of the graph. A graph is called Hamiltonian if it has a Hamiltonian cycle.
(4) A graph $G$ is (Hamilton) connected, if for every pair of vertices there is a (Hamiltonian) path between them.

An example of a simple graph: $V=\{v_1,v_2,v_3,v_4\}$ and $E=\{v_1v_2, v_2v_3, v_3v_4, v_2v_4\}$. In this graph, the order of the graph is $4$, $N(v_1)=\{v_2\}$, $N(v_4)=\{v_2,v_3\}$, $d(v_3)=2$, $d(v_2)=3$ and $v_1v_2v_4v_3$ is a Hamiltonian path with ends $v_1$ and $v_3$.

Let $G$ be a simple graph of order $n$. Suppose that the degree sum of any pair of nonadjacent vertices is at least $n+1$. Show that $G$ is Hamilton-connected (i.e. between any pair of vertices $x$ and $y$, there is a Hamiltonian path in which $x$ and $y$ are the ends).

Problem 4 (yau-contest 2018)

Define the Hermite polynomials as
$$H_n(x)=(-1)^n\exp\!\left(\frac{x^2}{2}\right)\,\frac{d^n}{dx^n}\big[\exp\!\left(-\frac{x^2}{2}\right)\big],\quad x\in(-\infty,+\infty),\quad n=0,1,2,\cdots.$$
(a) Prove the weighted orthogonality of the Hermite polynomials:
$$\langle H_n(x),H_m(x)\rangle_\rho \triangleq \int_{-\infty}^{+\infty} \rho(x) H_n(x) H_m(x)\,dx = n!\sqrt{2\pi}\,\delta_{n,m},$$
where $\rho(x)=\exp\!\left(-\frac{x^2}{2}\right)$.
(b) Prove the three recurrence formula:
$$H_{n+1}(x)=xH_n(x)-nH_{n-1}(x),\quad n\ge1,$$
and then show that for all $n\ge1$, $H_n(x)$ and $H_{n-1}(x)$ share no common roots.
(c) Use the recurrence formula and induction to prove the differential relation:
$$\frac{d}{dx}H_n(x)=nH_{n-1}(x),\quad n\ge1,$$
and then prove that $H_n$ is an eigenfunction of the following eigenvalue problem:
$$xv'(x)-u''(x)=\lambda u.$$
You need to find the eigenvalue $\lambda_n$ corresponding to $H_n(x)$.

Problem 5 (yau-contest 2018)

Take $\sigma_i(A)$ to be the $i$-th singular value of the square matrix $A \in \mathbb{R}^{n\times n}$. Define the nuclear norm of $A$ to be

$$\|A\|_* \equiv \sum_{i=1}^{n} \sigma_i(A).$$

(1) Show that $\|A\|_* = tr(\sqrt{A^T A})$.
(2) Show that $\|A\|_* = \max_{X^T X = I} tr(AX)$.
(3) Show that $\|A + B\|_* \le \|A\|_* + \|B\|_*$.
(4) Explain informally why minimizing $\|A - A_0\|_F^2 + \|A\|_*$ over $A$ for a fixed $A_0 \in \mathbb{R}^{n\times n}$ might yield a low-rank approximation of $A_0$.

Notation: The trace of a matrix $tr(A)$ is the sum $\sum_i a_{ii}$ of its diagonal elements. We define the square root of a symmetric positive semidefinite matrix $M$ to be $\sqrt{M} \equiv U D^{1/2} U^T$, where $D^{1/2}$ is the diagonal matrix containing (nonnegative) square roots of the eigenvalues of $M$ and $U$ contains the eigenvectors of $M = U D U^T$.