Problem 1 (yau-contest 2015)

Let $r$ and $s$ be relatively prime positive integers. Prove that the number of lattice paths from $(0,0)$ to $(r,s)$, which consists of steps $(1,0)$ and $(0,1)$ and never go above the line $ry = sx$ is given by

$$\frac{1}{r+s}\binom{r+s}{s}.$$

Problem 2 (yau-contest 2015)

The following $2\times2$ block matrix

$$C(\alpha)=\begin{bmatrix} \alpha I & A \\ A^T & 0 \end{bmatrix}$$

plays a key role in an augmented system method to solve linear least squares problem, a fundamental numerical linear algebra problem for fitting a linear model to observations subject to errors in science, where $A\in\mathbb{R}^{m\times n}$ is of full rank $n\le m$, $I$ is a $m\times m$ identity matrix, and $\alpha\ge0$. Prove the following results which address the question of optimal choice of scaling $\alpha$ for stability of the augmented system method.

(a) The eigenvalues of $C(\alpha)$ are
$$\frac{\alpha}{2}\pm\left(\frac{\alpha^2}{4}+\sigma_i^2\right)^{1/2}\quad\text{for } i=1,2,\ldots,n,\quad\text{and }\alpha\; (m-n\text{ times}),$$
where $\sigma_i$ for $i=1,2,\ldots,n$ are the singular values of $A$, arranged in the decreasing order, i.e., $\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_n$.

(b) The condition number $\kappa_2(C(\alpha))=\lVert C(\alpha)\rVert_2\,\lVert C(\alpha)^{-1}\rVert_2$ has the following bounds:
$$\sqrt{2}\,\kappa_2(A)\le\min_{\alpha}\kappa_2\big(C(\alpha)\big)\le 2\,\kappa_2(A),$$
with $\min_{\alpha}\kappa_2(C(\alpha))$ being achieved for $\alpha=\sigma_n/\sqrt{2}$, and
$$\max_{\alpha}\kappa_2\big(C(\alpha)\big) > \kappa_2(A)^2,$$
where $\lVert\cdot\rVert$ is the spectral norm of a matrix.

Recall that any matrix $A\in\mathbb{R}^{m\times n}$ has a singular value decomposition (SVD):
$$A=U\Sigma V^T,\qquad \Sigma=\operatorname{diag}(\sigma_1,\sigma_2,\ldots,\sigma_p)\in\mathbb{R}^{m\times n},\quad p=\min(m,n),$$
where $\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_p\ge0$, and $U\in\mathbb{R}^{m\times m},\ V\in\mathbb{R}^{n\times n}$ are both orthogonal. The $\sigma_i$ are the singular values of $A$ and the columns of $U$ and $V$ are the left and right singular vectors of $A$, respectively.

Problem 3 (yau-contest 2015)

Solve the following linear hyperbolic partial differential equation

(1) $$u_t + a u_x = 0, \quad t \ge 0,$$

where $a$ is a constant. Using the finite difference approximation, we can obtain the forward-time central-space scheme as follows,

(2) $$\frac{u_m^{n+1}-u_m^{n}}{k} + a\,\frac{u_{m+1}^{n}-u_{m-1}^{n}}{2h}=0,$$

where $k$ and $h$ are temporal and spatial mesh sizes.

(a) Show that when we fix $\lambda = k/h$ as a positive constant, the forward-time central-space scheme (2) is consistent with equation (1).

(b) Analyze the stability of this method. Is the method stable with $\lambda=k/h$ being fixed as a constant?

(c) How would the answer change if you are allowed to make $\lambda=k/h$ small?

(d) Would this be a good scheme to use even if you can make it stable by making $\lambda$ small? If not, please provide a simple modification to make this scheme stable by keeping $\lambda$ fixed.

Problem 4 (yau-contest 2015)

Let $A,H,Q\in\mathbb{C}^{n\times n}$ and $Q$ is non-singular. Assume that $H=Q^{-1}AQ$ and $H$ is properly upper Hessenberg. Show that

$$\operatorname{span}\{q_1,q_2,\ldots,q_j\}=\mathcal{K}_j(A,q_1),\qquad j=1,2,\ldots,n,$$

where $q_j$ is the $j$-th column of $Q$, and $\mathcal{K}_j(A,q_1)=\operatorname{span}\{q_1, A q_1, \ldots, A^{j-1} q_1\}.$

Problem 5 (yau-contest 2015)

Minkowski Problem.

Assume $P$ is a convex polyhedron embedded in $\mathbb{R}^3$, the faces are $\{F_1, F_2, \cdots, F_k\}$, the unit normal vector to the face $F_i$ is $\mathbf{n}_i$, the area of $F_i$ is $A_i$, $1\le i\le k$.

- Show that

(3) $$A_1\mathbf{n}_1 + A_2\mathbf{n}_2 + \cdots + A_k\mathbf{n}_k = 0.$$

- Given $k$ unit vectors $\{\mathbf{n}_1, \mathbf{n}_2, \ldots, \mathbf{n}_k\}$ which can not be contained in any half space, and $k$ real positive numbers $\{A_1, A_2, \cdots, A_k\}$, $A_i>0$, and satisfying the condition (3), show that there exists a convex polyhedron $P$, whose face normals are $\mathbf{n}_i$'s, face areas are $A_i$'s.