Problem 1 (yau-contest 2015)

Consider the elliptic interface problem

$$(a(x)u_x)_x = f, \quad x \in (0,1)$$

with the Dirichlet boundary condition

$$u(0) = u(1) = 0.$$

Here, $f$ is a smooth function, the elliptic coefficient $a(x)$ is discontinuous across an interface point $\xi$, that is,

$$
a(x) = 
\begin{cases}
 a_0, & 0 < x < \xi,\\
 a_1, & \xi < x < 1,
\end{cases}
$$

$a_0, a_1 > 0$ are positive constants, and $0 < \xi < 1$ is an interface point. Across the interface, we need to impose two jump conditions

$$u(\xi^-) = u(\xi^+), \qquad a(\xi^-)u_x(\xi^-) = a(\xi^+)u_x(\xi^+).$$

Question:
1. (25%) Design a numerical method to solve this problem. The method should be at least first order. It is better to be high order (if your method is first order, you get 20% points).
2. (75%) Prove your accuracy and convergence arguments (if your method is first order, you get 60% points).

Problem 2 (yau-contest 2015)

Let $G$ be graph of a social network, where for each pair of members there is either no connection, or a positive or a negative one.

An unbalanced cycle in $G$ is a cycle which have odd number of negative edges. Traversing along such a cycle with social rules such as friend of enemy are enemy would result in having a negative relation of one with himself!

A resigning in $G$ at a vertex $v$ of $G$ is to switch the type (positive or negative) of all edges incident to $v$.

Question: Show that one can switch all edge of $G$ into positive edges using a sequence resigning if and only if there is no unbalanced cycle in $G$.

Problem 3 (yau-contest 2015)

We consider particles which are able to produce new particles of like kind. A single particle forms the original, or zero, generation. Every particle has probability $p_k$ ($k = 0, 1, 2, \ldots$) of creating exactly $k$ new particles; the direct descendants of the $n$th generation form the $(n+1)$st generation. The particles of each generation act independently of each other.

Assume $0 < p_0 < 1$. Let $P(x) = \sum_{k\ge 0} p_k x^k$ and $\mu = P'(1) = \sum_{k\ge 0} k p_k$ be the expected number of direct descendants of one particle. Prove that if $\mu > 1$, then the probability $x_n$ that the process terminates at or before the $n$th generation tends to the unique root $\sigma \in (0,1)$ of equation $\sigma = P(\sigma)$.

Problem 4 (yau-contest 2015)

(Isoperimetric inequality). Consider a closed plane curve described by a parametric equation $(x(t), y(t))$, $0 \le t \le T$ with parameter $t$ oriented counterclockwise and $(x(0), y(0)) = (x(T), y(T))$.

(a): Show that the total length of the curve is given by

$$L = \int_0^T \sqrt{(x'(t))^2 + (y'(t))^2}\, dt.$$

(b): Show that the total area enclosed by the curve is given by

$$A = \frac{1}{2} \int_0^T \big(x(t)y'(t) - y(t)x'(t)\big)\, dt.$$

(c): The classical iso-perimetric inequality states that for closed plane curves with a fixed length $L$, circles have the largest enclosed area $A$. Formulate this question into a variational problem.

(d): Derive the Euler–Lagrange equation for the variational problem in (c).

(e): Show that there are two constants $x_0$ and $y_0$ such that

$$(x(t) - x_0)^2 + (y(t) - y_0)^2 = r^2$$

where $r = L/(2\pi)$. Explain your result.

Problem 5 (yau-contest 2015)

Let $A \in \mathbb{R}^{n\times m}$ with rank $r < \min(m,n)$. Let $A = U \Sigma V^T$ be the SVD of $A$, with singular values $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r > 0$.

(a) Show that, for every $\epsilon > 0$, there is a full rank matrix $A_\epsilon \in \mathbb{R}^{n\times m}$ such that $\|A - A_\epsilon\|_2 = \epsilon$.

(b) Let $A_k = U \Sigma_k V^T$ where $\Sigma_k = \operatorname{diag}(\sigma_1, \ldots, \sigma_k, 0, \ldots, 0)$ and $1 \le k \le r - 1$. Show that $\operatorname{rank}(A_k) = k$ and

$$\sigma_{k+1} = \|A - A_k\|_2 = \min\{\|A - B\|_2 \mid \operatorname{rank}(B) \le k\}.$$

(c) Assume that $r = \min(m,n)$. Let $B \in \mathbb{R}^{n\times m}$ and assume that $\|A - B\|_2 < \sigma_r$. Show that $\operatorname{rank}(B) = r$.