Mathematics Tripos Papers

Paper 3, Section I, $2 \mathrm{E}$

Part IB, 2011

Suppose $f$ is a uniformly continuous mapping from a metric space $X$ to a metric space $Y$ . Prove that $f\left(x_{n}\right)$ is a Cauchy sequence in $Y$ for every Cauchy sequence $x_{n}$ in $X$ .

Let $f$ be a continuous mapping between metric spaces and suppose that $f$ has the property that $f\left(x_{n}\right)$ is a Cauchy sequence whenever $x_{n}$ is a Cauchy sequence. Is it true that $f$ must be uniformly continuous? Justify your answer.

Complex Analysis or Complex Methods

Paper 1, Section II, A

Part IB, 2011

(i) Let $-1<\alpha<0$ and let

\begin{aligned} &f(z)=\frac{\log (z-\alpha)}{z} \text { where }-\pi \leqslant \arg (z-\alpha)<\pi \\ &g(z)=\frac{\log z}{z} \quad \text { where }-\pi \leqslant \arg (z)<\pi \end{aligned}

Here the logarithms take their principal values. Give a sketch to indicate the positions of the branch cuts implied by the definitions of $f(z)$ and $g(z)$ .

(ii) Let $h(z)=f(z)-g(z)$ . Explain why $h(z)$ is analytic in the annulus $1 \leqslant|z| \leqslant R$ for any $R>1$ . Obtain the first three terms of the Laurent expansion for $h(z)$ around $z=0$ in this annulus and hence evaluate

\oint_{|z|=2} h(z) d z

Complex Analysis or Complex Methods

Paper 2, Section II, A

Part IB, 2011

(i) Let $C$ be an anticlockwise contour defined by a square with vertices at $z=x+i y$ where

|x|=|y|=\left(2 N+\frac{1}{2}\right) \pi

for large integer $N$ . Let

I=\oint_{C} \frac{\pi \cot z}{(z+\pi a)^{4}} d z

Assuming that $I \rightarrow 0$ as $N \rightarrow \infty$ , prove that, if $a$ is not an integer, then

\sum_{n=-\infty}^{\infty} \frac{1}{(n+a)^{4}}=\frac{\pi^{4}}{3 \sin ^{2}(\pi a)}\left(\frac{3}{\sin ^{2}(\pi a)}-2\right) .

(ii) Deduce the value of

\sum_{n=-\infty}^{\infty} \frac{1}{\left(n+\frac{1}{2}\right)^{4}}

(iii) Briefly justify the assumption that $I \rightarrow 0$ as $N \rightarrow \infty$ .

[Hint: For part (iii) it is sufficient to consider, at most, one vertical side of the square and one horizontal side and to use a symmetry argument for the remaining sides.]

Paper 3, Section I, D

Complex Methods

Part IB, 2011

Write down the function $\psi(u, v)$ that satisfies

\frac{\partial^{2} \psi}{\partial u^{2}}+\frac{\partial^{2} \psi}{\partial v^{2}}=0, \quad \psi\left(-\frac{1}{2}, v\right)=-1, \quad \psi\left(\frac{1}{2}, v\right)=1

The circular arcs $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ in the complex $z$ -plane are defined by

|z+1|=1, z \neq 0 \text { and }|z-1|=1, z \neq 0,

respectively. You may assume without proof that the mapping from the complex $z$ -plane to the complex $\zeta$ -plane defined by

\zeta=\frac{1}{z}

takes $\mathcal{C}_{1}$ to the line $u=-\frac{1}{2}$ and $\mathcal{C}_{2}$ to the line $u=\frac{1}{2}$ , where $\zeta=u+i v$ , and that the region $\mathcal{D}$ in the $z$ -plane exterior to both the circles $|z+1|=1$ and $|z-1|=1$ maps to the region in the $\zeta$ -plane given by $-\frac{1}{2}<u<\frac{1}{2}$ .

Use the above mapping to solve the problem

\nabla^{2} \phi=0 \quad \text { in } \mathcal{D}, \quad \phi=-1 \text { on } \mathcal{C}_{1} \text { and } \phi=1 \text { on } \mathcal{C}_{2}

Paper 4, Section II, D

Complex Methods

Part IB, 2011

State and prove the convolution theorem for Laplace transforms.

Use Laplace transforms to solve

2 f^{\prime}(t)-\int_{0}^{t}(t-\tau)^{2} f(\tau) d \tau=4 t H(t)

with $f(0)=0$ , where $H(t)$ is the Heaviside function. You may assume that the Laplace transform, $\widehat{f}(s)$ , of $f(t)$ exists for Re $s$ sufficiently large.

Paper 2, Section I, $\mathbf{6 C}$

Part IB, 2011

Maxwell's equations are

\begin{gathered} \boldsymbol{\nabla} \cdot \mathbf{E}=\frac{\rho}{\epsilon_{0}}, \quad \boldsymbol{\nabla} \times \mathbf{E}=-\frac{\partial \mathbf{B}}{\partial t} \\ \nabla \cdot \mathbf{B}=0, \quad \nabla \times \mathbf{B}=\mu_{0} \mathbf{J}+\epsilon_{0} \mu_{0} \frac{\partial \mathbf{E}}{\partial t} \end{gathered}

Find the equation relating $\rho$ and $\mathbf{J}$ that must be satisfied for consistency, and give the interpretation of this equation.

Now consider the "magnetic limit" where $\rho=0$ and the term $\epsilon_{0} \mu_{0} \frac{\partial \mathbf{E}}{\partial t}$ is neglected. Let $\mathbf{A}$ be a vector potential satisfying the gauge condition $\boldsymbol{\nabla} \cdot \mathbf{A}=0$ , and assume the scalar potential vanishes. Find expressions for $\mathbf{E}$ and $\mathbf{B}$ in terms of $\mathbf{A}$ and show that Maxwell's equations are all satisfied provided $\mathbf{A}$ satisfies the appropriate Poisson equation.

Paper 4, Section I, C

Part IB, 2011

A plane electromagnetic wave in a vacuum has electric field

\mathbf{E}=\left(E_{0} \sin k(z-c t), 0,0\right)

What are the wavevector, polarization vector and speed of the wave? Using Maxwell's equations, find the magnetic field B. Assuming the scalar potential vanishes, find a possible vector potential $\mathbf{A}$ for this wave, and verify that it gives the correct $\mathbf{E}$ and $\mathbf{B}$ .

Paper 1, Section II, D

Part IB, 2011

Starting from the relevant Maxwell equation, derive Gauss's law in integral form.

Use Gauss's law to obtain the potential at a distance $r$ from an infinite straight wire with charge $\lambda$ per unit length.

Write down the potential due to two infinite wires parallel to the $z$ -axis, one at $x=y=0$ with charge $\lambda$ per unit length and the other at $x=0, y=d$ with charge $-\lambda$ per unit length.

Find the potential and the electric field in the limit $d \rightarrow 0$ with $\lambda d=p$ where $p$ is fixed. Sketch the equipotentials and the electric field lines.

Paper 2, Section II, C

Part IB, 2011

(i) Consider an infinitely long solenoid parallel to the $z$ -axis whose cross section is a simple closed curve of arbitrary shape. A current $I$ , per unit length of the solenoid, flows around the solenoid parallel to the $x-y$ plane. Show using the relevant Maxwell equation that the magnetic field $\mathbf{B}$ inside the solenoid is uniform, and calculate its magnitude.

(ii) A wire loop in the shape of a regular hexagon of side length $a$ carries a current $I$ . Use the Biot-Savart law to calculate $\mathbf{B}$ at the centre of the loop.

Paper 3, Section II, C

Part IB, 2011

Show, using the vacuum Maxwell equations, that for any volume $V$ with surface $S$ ,

\frac{d}{d t} \int_{V}\left(\frac{\epsilon_{0}}{2} \mathbf{E} \cdot \mathbf{E}+\frac{1}{2 \mu_{0}} \mathbf{B} \cdot \mathbf{B}\right) d V=\int_{S}\left(-\frac{1}{\mu_{0}} \mathbf{E} \times \mathbf{B}\right) \cdot \mathbf{d} \mathbf{S}

What is the interpretation of this equation?

A uniform straight wire, with a circular cross section of radius $r$ , has conductivity $\sigma$ and carries a current $I$ . Calculate $\frac{1}{\mu_{0}} \mathbf{E} \times \mathbf{B}$ at the surface of the wire, and hence find the flux of $\frac{1}{\mu_{0}} \mathbf{E} \times \mathbf{B}$ into unit length of the wire. Relate your result to the resistance of the wire, and the rate of energy dissipation.

Paper 1, Section I, B

Part IB, 2011

Inviscid fluid is contained in a square vessel with sides of length $\pi L$ lying between $x=0, \pi L, y=0, \pi L$ . The base of the container is at $z=-H$ where $H \gg L$ and the horizontal surface is at $z=0$ when the fluid is at rest. The variation of pressure of the air above the fluid may be neglected.

Small amplitude surface waves are excited in the vessel.

(i) Now let $H \rightarrow \infty$ . Explain why on dimensional grounds the frequencies $\omega$ of such waves are of the form

\omega=\left(\frac{\gamma g}{L}\right)^{\frac{1}{2}}

for some positive dimensionless constants $\gamma$ , where $g$ is the gravitational acceleration.

It is given that the velocity potential $\phi$ is of the form

\phi(x, y, z) \approx C \cos (m x / L) \cos (n y / L) \mathrm{e}^{\gamma z / L}

where $m$ and $n$ are integers and $C$ is a constant.

(ii) Why do cosines, rather than sines, appear in this expression?

(iii) Give an expression for $\gamma$ in terms of $m$ and $n$ .

(iv) Give all possible values that $\gamma^{2}$ can take between 1 and 10 inclusive. How many different solutions for $\phi$ correspond to each of these values of $\gamma^{2} ?$

Paper 4, Section I, E

Part IB, 2011

Let $B[0,1]$ denote the set of bounded real-valued functions on $[0,1]$ . A distance $d$ on $B[0,1]$ is defined by

d(f, g)=\sup _{x \in[0,1]}|f(x)-g(x)| .

Given that $(B[0,1], d)$ is a metric space, show that it is complete. Show that the subset $C[0,1] \subset B[0,1]$ of continuous functions is a closed set.

Paper 2, Section I, D

Part IB, 2011

A body of volume $V$ lies totally submerged in a motionless fluid of uniform density $\rho$ . Show that the force $\mathbf{F}$ on the body is given by

\mathbf{F}=-\int_{S}\left(p-p_{0}\right) \mathbf{n} d S

where $p$ is the pressure in the fluid and $p_{0}$ is atmospheric pressure. You may use without proof the generalised divergence theorem in the form

\int_{S} \phi \mathbf{n} d S=\int_{V} \boldsymbol{\nabla} \phi d V

Deduce that

\mathbf{F}=\rho g V \hat{\mathbf{z}},

where $\hat{\mathbf{z}}$ is the vertically upward unit vector. Interpret this result.

Paper 1, Section II, B

Part IB, 2011

A spherical bubble in an incompressible fluid of density $\rho$ has radius $a(t)$ . Write down an expression for the velocity field at a radius $R \geqslant a$ .

The pressure far from the bubble is $p_{\infty}$ . What is the pressure at radius $R$ ?

Find conditions on $a$ and its time derivatives that ensure that the maximum pressure in the fluid is reached at a radius $R_{\max }$ where $a<R_{\max }<\infty$ . Give an expression for this maximum pressure when the conditions hold.

Give the most general form of $a(t)$ that ensures that the pressure at $R=a(t)$ is $p_{\infty}$ for all time.

Paper 3, Section II, $18 \mathrm{D}$

Part IB, 2011

Water of constant density $\rho$ flows steadily through a long cylindrical tube, the wall of which is elastic. The exterior radius of the tube at a distance $z$ along the tube, $r(z)$ , is determined by the pressure in the tube, $p(z)$ , according to

r(z)=r_{0}+b\left(p(z)-p_{0}\right)

where $r_{0}$ and $p_{0}$ are the radius and pressure far upstream $(z \rightarrow-\infty)$ , and $b$ is a positive constant.

The interior radius of the tube is $r(z)-h(z)$ , where $h(z)$ , the thickness of the wall, is a given slowly varying function of $z$ which is zero at both ends of the pipe. The velocity of the water in the pipe is $u(z)$ and the water enters the pipe at velocity $V$ .

Show that $u(z)$ satisfies

H=1-v^{-\frac{1}{2}}+\frac{1}{4} k\left(1-v^{2}\right)

where $H=\frac{h}{r_{0}}, v=\frac{u}{V}$ and $k=\frac{2 b \rho V^{2}}{r_{0}}$ . Sketch the graph of $H$ against $v$ .

Let $H_{m}$ be the maximum value of $H$ in the tube. Show that the flow is only possible if $H_{m}$ does not exceed a certain critical value $H_{c}$ . Find $H_{c}$ in terms of $k$ .

Show that, under conditions to be determined (which include a condition on the value of $k)$ , the water can leave the pipe with speed less than $V$ .

Paper 4, Section II, D

Part IB, 2011

Show that an irrotational incompressible flow can be determined from a velocity potential $\phi$ that satisfies $\nabla^{2} \phi=0$ .

Given that the general solution of $\nabla^{2} \phi=0$ in plane polar coordinates is

\phi=\sum_{n=-\infty}^{\infty}\left(a_{n} \cos n \theta+b_{n} \sin n \theta\right) r^{n}+c \log r+b \theta

obtain the corresponding fluid velocity.

A two-dimensional irrotational incompressible fluid flows past the circular disc with boundary $r=a$ . For large $r$ , the flow is uniform and parallel to the $x$ -axis $(x=r \cos \theta)$ . Write down the boundary conditions for large $r$ and on $r=a$ , and hence derive the velocity potential in the form

\phi=U\left(r+\frac{a^{2}}{r}\right) \cos \theta+\frac{\kappa \theta}{2 \pi}

where $\kappa$ is the circulation.

Show that the acceleration of the fluid at $r=a$ and $\theta=0$ is

\frac{\kappa}{2 \pi a^{2}}\left(-\frac{\kappa}{2 \pi a} \mathbf{e}_{r}-2 U \mathbf{e}_{\theta}\right)

Paper 1, Section I, F

Part IB, 2011

Suppose that $H \subseteq \mathbb{C}$ is the upper half-plane, $H=\{x+i y \mid x, y \in \mathbb{R}, y>0\}$ . Using the Riemannian metric $d s^{2}=\frac{d x^{2}+d y^{2}}{y^{2}}$ , define the length of a curve $\gamma$ and the area of a region $\Omega$ in $H$ .

Find the area of

\Omega=\left\{x+i y|| x \mid \leqslant \frac{1}{2}, x^{2}+y^{2} \geqslant 1\right\}

Paper 3, Section I, F

Part IB, 2011

Let $R(x, \theta)$ denote anti-clockwise rotation of the Euclidean plane $\mathbb{R}^{2}$ through an angle $\theta$ about a point $x$ .

Show that $R(x, \theta)$ is a composite of two reflexions.

Assume $\theta, \phi \in(0, \pi)$ . Show that the composite $R(y, \phi) \cdot R(x, \theta)$ is also a rotation $R(z, \psi)$ . Find $z$ and $\psi$ .

Paper 2, Section II, F

Part IB, 2011

Suppose that $\pi: S^{2} \rightarrow \mathbb{C}_{\infty}$ is stereographic projection. Show that, via $\pi$ , every rotation of $S^{2}$ corresponds to a Möbius transformation in $P S U(2)$ .

Paper 3, Section II, F

Part IB, 2011

Suppose that $\eta(u)=(f(u), 0, g(u))$ is a unit speed curve in $\mathbb{R}^{3}$ . Show that the corresponding surface of revolution $S$ obtained by rotating this curve about the $z$ -axis has Gaussian curvature $K=-\left(d^{2} f / d u^{2}\right) / f$ .

Paper 4, Section II, F

Part IB, 2011

Suppose that $P$ is a point on a Riemannian surface $S$ . Explain the notion of geodesic polar co-ordinates on $S$ in a neighbourhood of $P$ , and prove that if $C$ is a geodesic circle centred at $P$ of small positive radius, then the geodesics through $P$ meet $C$ at right angles.

Paper 2, Section I, F

Part IB, 2011

Show that the quaternion group $Q_{8}=\{\pm 1, \pm i, \pm j, \pm k\}$ , with $i j=k=-j i$ , $i^{2}=j^{2}=k^{2}=-1$ , is not isomorphic to the symmetry group $D_{8}$ of the square.

Paper 1, Section II, E

Part IB, 2011

What is meant by saying that a sequence of functions $f_{n}$ converges uniformly to a function $f$ ?

Let $f_{n}$ be a sequence of differentiable functions on $[a, b]$ with $f_{n}^{\prime}$ continuous and such that $f_{n}\left(x_{0}\right)$ converges for some point $x_{0} \in[a, b]$ . Assume in addition that $f_{n}^{\prime}$ converges uniformly on $[a, b]$ . Prove that $f_{n}$ converges uniformly to a differentiable function $f$ on $[a, b]$ and $f^{\prime}(x)=\lim _{n \rightarrow \infty} f_{n}^{\prime}(x)$ for all $x \in[a, b]$ . [You may assume that the uniform limit of continuous functions is continuous.]

Show that the series

\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^{s}}

converges for $s>1$ and is uniformly convergent on $[1+\varepsilon, \infty)$ for any $\varepsilon>0$ . Show that $\zeta(s)$ is differentiable on $(1, \infty)$ and

\zeta^{\prime}(s)=-\sum_{n=2}^{\infty} \frac{\log n}{n^{s}}

[You may use the Weierstrass $M$ -test provided it is clearly stated.]

Paper 3, Section I, $1 F$

Part IB, 2011

Suppose that $A$ is an integral domain containing a field $K$ and that $A$ is finitedimensional as a $K$ -vector space. Prove that $A$ is a field.

Paper 4, Section I, F

Part IB, 2011

A ring $R$ satisfies the descending chain condition (DCC) on ideals if, for every sequence $I_{1} \supseteq I_{2} \supseteq I_{3} \supseteq \ldots$ of ideals in $R$ , there exists $n$ with $I_{n}=I_{n+1}=I_{n+2}=\ldots$ Show that $\mathbb{Z}$ does not satisfy the DCC on ideals.

Paper 1, Section II, F

Part IB, 2011

(i) Suppose that $G$ is a finite group of order $p^{n} r$ , where $p$ is prime and does not divide $r$ . Prove the first Sylow theorem, that $G$ has at least one subgroup of order $p^{n}$ , and state the remaining Sylow theorems without proof.

(ii) Suppose that $p, q$ are distinct primes. Show that there is no simple group of order $p q$ .

Paper 2, Section II, F

Part IB, 2011

Define the notion of a Euclidean domain and show that $\mathbb{Z}[i]$ is Euclidean.

Is $4+i$ prime in $\mathbb{Z}[i]$ ?

Paper 3, Section II, F

Part IB, 2011

Suppose that $A$ is a matrix over $\mathbb{Z}$ . What does it mean to say that $A$ can be brought to Smith normal form?

Show that the structure theorem for finitely generated modules over $\mathbb{Z}$ (which you should state) follows from the existence of Smith normal forms for matrices over $\mathbb{Z}$ .

Bring the matrix $\left(\begin{array}{cc}-4 & -6 \\ 2 & 2\end{array}\right)$ to Smith normal form.

Suppose that $M$ is the $\mathbb{Z}$ -module with generators $e_{1}, e_{2}$ , subject to the relations

-4 e_{1}+2 e_{2}=-6 e_{1}+2 e_{2}=0

Describe $M$ in terms of the structure theorem.

Paper 4, Section II, F

Part IB, 2011

State and prove the Hilbert Basis Theorem.

Is every ring Noetherian? Justify your answer.

Paper 1, Section I, G

Part IB, 2011

(i) State the rank-nullity theorem for a linear map between finite-dimensional vector spaces.

(ii) Show that a linear transformation $f: V \rightarrow V$ of a finite-dimensional vector space $V$ is bijective if it is injective or surjective.

(iii) Let $V$ be the $\mathbb{R}$ -vector space $\mathbb{R}[X]$ of all polynomials in $X$ with coefficients in $\mathbb{R}$ . Give an example of a linear transformation $f: V \rightarrow V$ which is surjective but not bijective.

Paper 2, Section $I$ , G

Part IB, 2011

Let $V$ be an $n$ -dimensional $\mathbb{R}$ -vector space with an inner product. Let $W$ be an $m$ -dimensional subspace of $V$ and $W^{\perp}$ its orthogonal complement, so that every element $v \in V$ can be uniquely written as $v=w+w^{\prime}$ for $w \in W$ and $w^{\prime} \in W^{\perp}$ .

The reflection map with respect to $W$ is defined as the linear map

f_{W}: V \ni w+w^{\prime} \longmapsto w-w^{\prime} \in V

Show that $f_{W}$ is an orthogonal transformation with respect to the inner product, and find its determinant.

Paper 4, Section I, G

Part IB, 2011

(i) Let $V$ be a vector space over a field $F$ , and $W_{1}, W_{2}$ subspaces of $V$ . Define the subset $W_{1}+W_{2}$ of $V$ , and show that $W_{1}+W_{2}$ and $W_{1} \cap W_{2}$ are subspaces of $V$ .

(ii) When $W_{1}, W_{2}$ are finite-dimensional, state a formula for $\operatorname{dim}\left(W_{1}+W_{2}\right)$ in terms of $\operatorname{dim} W_{1}, \operatorname{dim} W_{2}$ and $\operatorname{dim}\left(W_{1} \cap W_{2}\right)$ .

(iii) Let $V$ be the $\mathbb{R}$ -vector space of all $n \times n$ matrices over $\mathbb{R}$ . Let $S$ be the subspace of all symmetric matrices and $T$ the subspace of all upper triangular matrices (the matrices $\left(a_{i j}\right)$ such that $a_{i j}=0$ whenever $\left.i>j\right)$ . Find $\operatorname{dim} S, \operatorname{dim} T, \operatorname{dim}(S \cap T)$ and $\operatorname{dim}(S+T)$ . Briefly justify your answer.

Paper 1, Section II, G

Part IB, 2011

Let $V, W$ be finite-dimensional vector spaces over a field $F$ and $f: V \rightarrow W$ a linear map.

(i) Show that $f$ is injective if and only if the image of every linearly independent subset of $V$ is linearly independent in $W$ .

(ii) Define the dual space $V^{*}$ of $V$ and the dual map $f^{*}: W^{*} \rightarrow V^{*}$ .

(iii) Show that $f$ is surjective if and only if the image under $f^{*}$ of every linearly independent subset of $W^{*}$ is linearly independent in $V^{*}$ .

Paper 2, Section II, E

Part IB, 2011

What is meant by saying that two norms on a real vector space are Lipschitz equivalent?

Show that any two norms on $\mathbb{R}^{n}$ are Lipschitz equivalent. [You may assume that a continuous function on a closed bounded set in $\mathbb{R}^{n}$ has closed bounded image.]

Show that $\|f\|_{1}=\int_{-1}^{1}|f(x)| d x$ defines a norm on the space $C[-1,1]$ of continuous real-valued functions on $[-1,1]$ . Is it Lipschitz equivalent to the uniform norm? Justify your answer. Prove that the normed space $\left(C[-1,1],\|\cdot\|_{1}\right)$ is not complete.

Paper 2, Section II, G

Part IB, 2011

Let $n$ be a positive integer, and let $V$ be a $\mathbb{C}$ -vector space of complex-valued functions on $\mathbb{R}$ , generated by the set $\{\cos k x, \sin k x ; k=0,1, \ldots, n-1\}$ .

(i) Let $\langle f, g\rangle=\int_{0}^{2 \pi} f(x) \overline{g(x)} d x$ for $f, g \in V$ . Show that this is a positive definite Hermitian form on $V$ .

(ii) Let $\Delta(f)=\frac{d^{2}}{d x^{2}} f(x)$ . Show that $\Delta$ is a self-adjoint linear transformation of $V$ with respect to the form defined in (i).

(iii) Find an orthonormal basis of $V$ with respect to the form defined in (i), which consists of eigenvectors of $\Delta$ .

Paper 3, Section II, G

Part IB, 2011

(i) Let $A$ be an $n \times n$ complex matrix and $f(X)$ a polynomial with complex coefficients. By considering the Jordan normal form of $A$ or otherwise, show that if the eigenvalues of $A$ are $\lambda_{1}, \ldots, \lambda_{n}$ then the eigenvalues of $f(A)$ are $f\left(\lambda_{1}\right), \ldots, f\left(\lambda_{n}\right)$ .

(ii) Let $B=\left(\begin{array}{llll}a & d & c & b \\ b & a & d & c \\ c & b & a & d \\ d & c & b & a\end{array}\right)$ . Write $B$ as $B=f(A)$ for a polynomial $f$ with $A=\left(\begin{array}{llll}0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\end{array}\right)$ , and find the eigenvalues of $B$

[Hint: compute the powers of $A$ .]

Paper 4, Section II, G

Part IB, 2011

Let $V$ be an $n$ -dimensional $\mathbb{R}$ -vector space and $f, g: V \rightarrow V$ linear transformations. Suppose $f$ is invertible and diagonalisable, and $f \circ g=t \cdot(g \circ f)$ for some real number $t>1$ .

(i) Show that $g$ is nilpotent, i.e. some positive power of $g$ is 0 .

(ii) Suppose that there is a non-zero vector $v \in V$ with $f(v)=v$ and $g^{n-1}(v) \neq 0$ . Determine the diagonal form of $f$ .

Paper 3, Section I, H

Part IB, 2011

Let $\left(X_{n}\right)_{n \geqslant 0}$ be a Markov chain with state space $S$ .

(i) What does it mean to say that $\left(X_{n}\right)_{n} \geqslant 0$ has the strong Markov property? Your answer should include the definition of the term stopping time.

(ii) Show that

\mathbb{P}\left(X_{n}=i \text { at least } k \text { times } \mid X_{0}=i\right)=\left[\mathbb{P}\left(X_{n}=i \text { at least once } \mid X_{0}=i\right)\right]^{k}

for a state $i \in S$ . You may use without proof the fact that $\left(X_{n}\right)_{n \geqslant 0}$ has the strong Markov property.

Paper 4, Section I, H

Part IB, 2011

Let $\left(X_{n}\right)_{n \geqslant 0}$ be a Markov chain on a state space $S$ , and let $p_{i j}(n)=\mathbb{P}\left(X_{n}=j \mid X_{0}=i\right)$ .

(i) What does the term communicating class mean in terms of this chain?

(ii) Show that $p_{i i}(m+n) \geqslant p_{i j}(m) p_{j i}(n)$ .

(iii) The period $d_{i}$ of a state $i$ is defined to be

d_{i}=\operatorname{gcd}\left\{n \geqslant 1: p_{i i}(n)>0\right\}

Show that if $i$ and $j$ are in the same communicating class and $p_{j j}(r)>0$ , then $d_{i}$ divides $r$ .

Paper 1, Section II, H

Part IB, 2011

Let $P=\left(p_{i j}\right)_{i, j \in S}$ be the transition matrix for an irreducible Markov chain on the finite state space $S$ .

(i) What does it mean to say $\pi$ is the invariant distribution for the chain?

(ii) What does it mean to say the chain is in detailed balance with respect to $\pi$ ?

(iii) A symmetric random walk on a connected finite graph is the Markov chain whose state space is the set of vertices of the graph and whose transition probabilities are

p_{i j}= \begin{cases}1 / D_{i} & \text { if } j \text { is adjacent to } i \\ 0 & \text { otherwise }\end{cases}

where $D_{i}$ is the number of vertices adjacent to vertex $i$ . Show that the random walk is in detailed balance with respect to its invariant distribution.

(iv) Let $\pi$ be the invariant distribution for the transition matrix $P$ , and define an inner product for vectors $x, y \in \mathbb{R}^{S}$ by the formula

\langle x, y\rangle=\sum_{i \in S} x_{i} \pi_{i} y_{i}

Show that the equation

\langle x, P y\rangle=\langle P x, y\rangle

holds for all vectors $x, y \in \mathbb{R}^{S}$ if and only if the chain is in detailed balance with respect to $\pi$ . [Here $z \in \mathbb{R}^{S}$ means $z=\left(z_{i}\right)_{i \in S}$ .]

Paper 2, Section II, H

Part IB, 2011

(i) Let $\left(X_{n}\right)_{n \geqslant 0}$ be a Markov chain on the finite state space $S$ with transition matrix $P$ . Fix a subset $A \subseteq S$ , and let

H=\inf \left\{n \geqslant 0: X_{n} \in A\right\} .

Fix a function $g$ on $S$ such that $0<g(i) \leqslant 1$ for all $i \in S$ , and let

V_{i}=\mathbb{E}\left[\prod_{n=0}^{H-1} g\left(X_{n}\right) \mid X_{0}=i\right]

where $\prod_{n=0}^{-1} a_{n}=1$ by convention. Show that

V_{i}= \begin{cases}1 & \text { if } i \in A \\ g(i) \sum_{j \in S} P_{i j} V_{j} & \text { otherwise. }\end{cases}

(ii) A flea lives on a polyhedron with $N$ vertices, labelled $1, \ldots, N$ . It hops from vertex to vertex in the following manner: if one day it is on vertex $i>1$ , the next day it hops to one of the vertices labelled $1, \ldots, i-1$ with equal probability, and it dies upon reaching vertex 1. Let $X_{n}$ be the position of the flea on day $n$ . What are the transition probabilities for the Markov chain $\left(X_{n}\right)_{n \geqslant 0}$ ?

(iii) Let $H$ be the number of days the flea is alive, and let

V_{i}=\mathbb{E}\left(s^{H} \mid X_{0}=i\right)

where $s$ is a real number such that $0<s \leqslant 1$ . Show that $V_{1}=1$ and

\frac{i}{s} V_{i+1}=V_{i}+\frac{i-1}{s} V_{i}

for $i \geqslant 1$ . Conclude that

\mathbb{E}\left(s^{H} \mid X_{0}=N\right)=\prod_{i=1}^{N-1}\left(1+\frac{s-1}{i}\right)

[Hint. Use part (i) with $A=\{1\}$ and a well-chosen function $g$ . ]

(iv) Show that

\mathbb{E}\left(H \mid X_{0}=N\right)=\sum_{i=1}^{N-1} \frac{1}{i}

Paper 2, Section I, A

Part IB, 2011

The Legendre equation is

\left(1-x^{2}\right) \frac{d^{2} y}{d x^{2}}-2 x \frac{d y}{d x}+n(n+1) y=0

for $-1 \leqslant x \leqslant 1$ and non-negative integers $n$ .

Write the Legendre equation as an eigenvalue equation for an operator $L$ in SturmLiouville form. Show that $L$ is self-adjoint and find the orthogonality relation between the eigenfunctions.

Paper 3, Section I, A

Part IB, 2011

The Fourier transform $\tilde{h}(k)$ of the function $h(x)$ is defined by

\tilde{h}(k)=\int_{-\infty}^{\infty} h(x) e^{-i k x} d x

(i) State the inverse Fourier transform formula expressing $h(x)$ in terms of $\widetilde{h}(k)$ .

(ii) State the convolution theorem for Fourier transforms.

(iii) Find the Fourier transform of the function $f(x)=e^{-|x|}$ . Hence show that the convolution of the function $f(x)=e^{-|x|}$ with itself is given by the integral expression

\frac{2}{\pi} \int_{-\infty}^{\infty} \frac{e^{i k x}}{\left(1+k^{2}\right)^{2}} d k

Paper 4, Section I, A

Part IB, 2011

Use the method of characteristics to find a continuous solution $u(x, y)$ of the equation

y \frac{\partial u}{\partial x}+x \frac{\partial u}{\partial y}=0

subject to the condition $u(0, y)=y^{4}$ .

In which region of the plane is the solution uniquely determined?

Paper 3, Section II, E

Part IB, 2011

Consider a map $f: \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ .

Assume $f$ is differentiable at $x$ and let $D_{x} f$ denote the derivative of $f$ at $x$ . Show that

D_{x} f(v)=\lim _{t \rightarrow 0} \frac{f(x+t v)-f(x)}{t}

for any $v \in \mathbb{R}^{n}$ .

Assume now that $f$ is such that for some fixed $x$ and for every $v \in \mathbb{R}^{n}$ the limit

\lim _{t \rightarrow 0} \frac{f(x+t v)-f(x)}{t}

exists. Is it true that $f$ is differentiable at $x ?$ Justify your answer.

Let $M_{k}$ denote the set of all $k \times k$ real matrices which is identified with $\mathbb{R}^{k^{2}}$ . Consider the function $f: M_{k} \rightarrow M_{k}$ given by $f(A)=A^{3}$ . Explain why $f$ is differentiable. Show that the derivative of $f$ at the matrix $A$ is given by

D_{A} f(H)=H A^{2}+A H A+A^{2} H

for any matrix $H \in M_{k}$ . State carefully the inverse function theorem and use it to prove that there exist open sets $U$ and $V$ containing the identity matrix such that given $B \in V$ there exists a unique $A \in U$ such that $A^{3}=B$ .

Paper 1, Section II, A

Part IB, 2011

Let $f(t)$ be a real function defined on an interval $(-T, T)$ with Fourier series

f(t)=\frac{a_{0}}{2}+\sum_{n=1}^{\infty}\left(a_{n} \cos \frac{n \pi t}{T}+b_{n} \sin \frac{n \pi t}{T}\right)

State and prove Parseval's theorem for $f(t)$ and its Fourier series. Write down the formulae for $a_{0}, a_{n}$ and $b_{n}$ in terms of $f(t), \cos \frac{n \pi t}{T}$ and $\sin \frac{n \pi t}{T}$ .

Find the Fourier series of the square wave function defined on $(-\pi, \pi)$ by

g(t)=\left\{\begin{array}{lr} 0 & -\pi<t \leqslant 0 \\ 1 & 0<t<\pi \end{array}\right.

Hence evaluate

\sum_{k=0}^{\infty} \frac{(-1)^{k}}{(2 k+1)}

Using some of the above results evaluate

\sum_{k=0}^{\infty} \frac{1}{(2 k+1)^{2}}

What is the sum of the Fourier series for $g(t)$ at $t=0$ ? Comment on your answer.

Paper 2, Section II, A

Part IB, 2011

Use a Green's function to find an integral expression for the solution of the equation

\frac{d^{2} \theta}{d t^{2}}+4 \frac{d \theta}{d t}+29 \theta=f(t)

for $t \geqslant 0$ subject to the initial conditions

\theta(0)=0 \quad \text { and } \quad \frac{d \theta}{d t}(0)=0

Paper 3, Section II, A

Part IB, 2011

A uniform stretched string of length $L$ , density per unit length $\mu$ and tension $T=\mu c^{2}$ is fixed at both ends. Its transverse displacement is given by $y(x, t)$ for $0 \leqslant x \leqslant L$ . The motion of the string is resisted by the surrounding medium with a resistive force per unit length of $-2 k \mu \frac{\partial y}{\partial t}$ .

(i) Show that the equation of motion of the string is

\frac{\partial^{2} y}{\partial t^{2}}+2 k \frac{\partial y}{\partial t}-c^{2} \frac{\partial^{2} y}{\partial x^{2}}=0

provided that the transverse motion can be regarded as small.

(ii) Suppose now that $k=\frac{\pi c}{L}$ . Find the displacement of the string for $t \geqslant 0$ given the initial conditions

y(x, 0)=A \sin \left(\frac{\pi x}{L}\right) \quad \text { and } \quad \frac{\partial y}{\partial t}(x, 0)=0

(iii) Sketch the transverse displacement at $x=\frac{L}{2}$ as a function of time for $t \geqslant 0$ .

Paper 4, Section II, A

Part IB, 2011

Let $D$ be a two dimensional domain with boundary $\partial D$ . Establish Green's second identity

\int_{D}\left(\phi \nabla^{2} \psi-\psi \nabla^{2} \phi\right) d A=\int_{\partial D}\left(\phi \frac{\partial \psi}{\partial n}-\psi \frac{\partial \phi}{\partial n}\right) d s

where $\frac{\partial}{\partial n}$ denotes the outward normal derivative on $\partial D$ .

State the differential equation and boundary conditions which are satisfied by a Dirichlet Green's function $G\left(\mathbf{r}, \mathbf{r}_{0}\right)$ for the Laplace operator on the domain $D$ , where $\mathbf{r}_{0}$ is a fixed point in the interior of $D$ .

Suppose that $\nabla^{2} \psi=0$ on $D$ . Show that

\psi\left(\mathbf{r}_{0}\right)=\int_{\partial D} \psi(\mathbf{r}) \frac{\partial}{\partial n} G\left(\mathbf{r}, \mathbf{r}_{\mathbf{0}}\right) d s

Consider Laplace's equation in the upper half plane,

\nabla^{2} \psi(x, y)=0, \quad-\infty<x<\infty \quad \text { and } \quad y>0

with boundary conditions $\psi(x, 0)=f(x)$ where $f(x) \rightarrow 0$ as $|x| \rightarrow \infty$ , and $\psi(x, y) \rightarrow 0$ as $\sqrt{x^{2}+y^{2}} \rightarrow \infty$ . Show that the solution is given by the integral formula

\psi\left(x_{0}, y_{0}\right)=\frac{y_{0}}{\pi} \int_{-\infty}^{\infty} \frac{f(x)}{\left(x-x_{0}\right)^{2}+y_{0}^{2}} d x

[ Hint: It might be useful to consider

G\left(\mathbf{r}, \mathbf{r}_{0}\right)=\frac{1}{2 \pi}\left(\log \left|\mathbf{r}-\mathbf{r}_{0}\right|-\log \left|\mathbf{r}-\tilde{\mathbf{r}}_{0}\right|\right)

for suitable $\tilde{\mathbf{r}}_{\mathbf{0}}$ . You may assume $\nabla^{2} \log \left|\mathbf{r}-\mathbf{r}_{0}\right|=2 \pi \delta\left(\mathbf{r}-\mathbf{r}_{0}\right)$ . ]

Paper 2, Section I, 4G

Part IB, 2011

(i) Let $t>0$ . For $\mathbf{x}=(x, y), \mathbf{x}^{\prime}=\left(x^{\prime}, y^{\prime}\right) \in \mathbb{R}^{2}$ , let

\begin{gathered} d\left(\mathbf{x}, \mathbf{x}^{\prime}\right)=\left|x^{\prime}-x\right|+t\left|y^{\prime}-y\right|, \\ \delta\left(\mathbf{x}, \mathbf{x}^{\prime}\right)=\sqrt{\left(x^{\prime}-x\right)^{2}+\left(y^{\prime}-y\right)^{2}} \end{gathered}

( $\delta$ is the usual Euclidean metric on $\mathbb{R}^{2}$ .) Show that $d$ is a metric on $\mathbb{R}^{2}$ and that the two metrics $d, \delta$ give rise to the same topology on $\mathbb{R}^{2}$ .

(ii) Give an example of a topology on $\mathbb{R}^{2}$ , different from the one in (i), whose induced topology (subspace topology) on the $x$ -axis is the usual topology (the one defined by the metric $\left.d\left(x, x^{\prime}\right)=\left|x^{\prime}-x\right|\right)$ . Justify your answer.

Paper 3, Section I, 3G

Part IB, 2011

Let $X, Y$ be topological spaces, and suppose $Y$ is Hausdorff.

(i) Let $f, g: X \rightarrow Y$ be two continuous maps. Show that the set

E(f, g):=\{x \in X \mid f(x)=g(x)\} \subset X

is a closed subset of $X$ .

(ii) Let $W$ be a dense subset of $X$ . Show that a continuous map $f: X \rightarrow Y$ is determined by its restriction $\left.f\right|_{W}$ to $W$ .

Paper 1, Section II, G

Part IB, 2011

Let $X$ be a metric space with the distance function $d: X \times X \rightarrow \mathbb{R}$ . For a subset $Y$ of $X$ , its diameter is defined as $\delta(Y):=\sup \left\{d\left(y, y^{\prime}\right) \mid y, y^{\prime} \in Y\right\}$ .

Show that, if $X$ is compact and $\left\{U_{\lambda}\right\}_{\lambda \in \Lambda}$ is an open covering of $X$ , then there exists an $\epsilon>0$ such that every subset $Y \subset X$ with $\delta(Y)<\epsilon$ is contained in some $U_{\lambda}$ .

Paper 4, Section II, 13G

Part IB, 2011

Let $X, Y$ be topological spaces and $X \times Y$ their product set. Let $p_{Y}: X \times Y \rightarrow Y$ be the projection map.

(i) Define the product topology on $X \times Y$ . Prove that if a subset $Z \subset X \times Y$ is open then $p_{Y}(Z)$ is open in $Y$ .

(ii) Give an example of $X, Y$ and a closed set $Z \subset X \times Y$ such that $p_{Y}(Z)$ is not closed.

(iii) When $X$ is compact, show that if a subset $Z \subset X \times Y$ is closed then $p_{Y}(Z)$ is closed

Paper 1, Section I, B

Part IB, 2011

Orthogonal monic polynomials $p_{0}, p_{1}, \ldots, p_{n}, \ldots$ are defined with respect to the inner product $\langle p, q\rangle=\int_{-1}^{1} w(x) p(x) q(x) d x$ , where $p_{n}$ is of degree $n$ . Show that such polynomials obey a three-term recurrence relation

p_{n+1}(x)=\left(x-\alpha_{n}\right) p_{n}(x)-\beta_{n} p_{n-1}(x)

for appropriate choices of $\alpha_{n}$ and $\beta_{n}$ .

Now suppose that $w(x)$ is an even function of $x$ . Show that the $p_{n}$ are even or odd functions of $x$ according to whether $n$ is even or odd.

Paper 4, Section I, B

Part IB, 2011

Consider the multistep method for numerical solution of the differential equation $\mathbf{y}^{\prime}=\mathbf{f}(t, \mathbf{y})$ :

\sum_{l=0}^{s} \rho_{l} \mathbf{y}_{n+l}=h \sum_{l=0}^{s} \sigma_{l} \mathbf{f}\left(t_{n+l}, \mathbf{y}_{n+l}\right), \quad n=0,1, \ldots

What does it mean to say that the method is of order $p$ , and that the method is convergent?

Show that the method is of order $p$ if

\sum_{l=0}^{s} \rho_{l}=0, \quad \sum_{l=0}^{s} l^{k} \rho_{l}=k \sum_{l=0}^{s} l^{k-1} \sigma_{l}, \quad k=1,2, \ldots, p

and give the conditions on $\rho(w)=\sum_{l=0}^{s} \rho_{l} w^{l}$ that ensure convergence.

Hence determine for what values of $\theta$ and the $\sigma_{i}$ the two-step method

\mathbf{y}_{n+2}-(1-\theta) \mathbf{y}_{n+1}-\theta \mathbf{y}_{n}=h\left[\sigma_{0} \mathbf{f}\left(t_{n}, \mathbf{y}_{n}\right)+\sigma_{1} \mathbf{f}\left(t_{n+1}, \mathbf{y}_{n+1}\right)+\sigma_{2} \mathbf{f}\left(t_{n+2}, \mathbf{y}_{n+2}\right)\right]

is (a) convergent, and (b) of order 3 .

Paper 4, Section II, E

Part IB, 2011

Define a contraction mapping and state the contraction mapping theorem.

Let $(X, d)$ be a non-empty complete metric space and let $\phi: X \rightarrow X$ be a map. Set $\phi^{1}=\phi$ and $\phi^{n+1}=\phi \circ \phi^{n}$ . Assume that for some integer $r \geqslant 1, \phi^{r}$ is a contraction mapping. Show that $\phi$ has a unique fixed point $y$ and that any $x \in X$ has the property that $\phi^{n}(x) \rightarrow y$ as $n \rightarrow \infty$ .

Let $C[0,1]$ be the set of continuous real-valued functions on $[0,1]$ with the uniform norm. Suppose $T: C[0,1] \rightarrow C[0,1]$ is defined by

T(f)(x)=\int_{0}^{x} f(t) d t

for all $x \in[0,1]$ and $f \in C[0,1]$ . Show that $T$ is not a contraction mapping but that $T^{2}$ is.

Paper 1, Section II, B

Part IB, 2011

Consider a function $f(x)$ defined on the domain $x \in[0,1]$ . Find constants $\alpha, \beta$ , so that for any fixed $\xi \in[0,1]$ ,

f^{\prime \prime}(\xi)=\alpha f(0)+\beta f^{\prime}(0)+\gamma f(1)

is exactly satisfied for polynomials of degree less than or equal to two.

By using the Peano kernel theorem, or otherwise, show that

\begin{aligned} f^{\prime}(\xi)-f^{\prime}(0)-\xi(\alpha f(0)&\left.+\beta f^{\prime}(0)+\gamma f(1)\right)=\int_{0}^{\xi}(\xi-\theta) H_{1}(\theta) f^{\prime \prime \prime}(\theta) d \theta \\ &+\int_{0}^{\xi} \theta H_{2}(\theta) f^{\prime \prime \prime}(\theta) d \theta+\int_{\xi}^{1} \xi H_{2}(\theta) f^{\prime \prime \prime}(\theta) d \theta \end{aligned}

where $H_{1}(\theta)=1-(1-\theta)^{2} \geqslant 0, H_{2}(\theta)=-(1-\theta)^{2} \leqslant 0$ . Thus show that

\left|f^{\prime}(\xi)-f^{\prime}(0)-\xi\left(\alpha f(0)+\beta f^{\prime}(0)+\gamma f(1)\right)\right| \leqslant\left.\frac{1}{6}\left(2 \xi-3 \xi^{2}+4 \xi^{3}-\xi^{4}\right)|| f^{\prime \prime \prime}\right|_{\infty} .

Paper 2, Section II, B

Part IB, 2011

What is the $Q R$ -decomposition of a matrix A? Explain how to construct the matrices $Q$ and $R$ by the Gram-Schmidt procedure, and show how the decomposition can be used to solve the matrix equation $A \mathbf{x}=\mathbf{b}$ when $A$ is a square matrix.

Why is this procedure not useful for numerical decomposition of large matrices? Give a brief description of an alternative procedure using Givens rotations.

Find a $Q R$ -decomposition for the matrix

\mathrm{A}=\left[\begin{array}{rrrr} 3 & 4 & 7 & 13 \\ -6 & -8 & -8 & -12 \\ 3 & 4 & 7 & 11 \\ 0 & 2 & 5 & 7 \end{array}\right]

Is your decomposition unique? Use the decomposition you have found to solve the equation

A x=\left[\begin{array}{c} 4 \\ 6 \\ 2 \\ 9 \end{array}\right]

Paper 3, Section II, B

Part IB, 2011

A Gaussian quadrature formula provides an approximation to the integral

\int_{-1}^{1}\left(1-x^{2}\right) f(x) d x \approx \sum_{k=1}^{\nu} b_{k} f\left(c_{k}\right)

which is exact for all $f(x)$ that are polynomials of degree $\leqslant(2 \nu-1)$ .

Write down explicit expressions for the $b_{k}$ in terms of integrals, and explain why it is necessary that the $c_{k}$ are the zeroes of a (monic) polynomial $p_{\nu}$ of degree $\nu$ that satisfies $\int_{-1}^{1}\left(1-x^{2}\right) p_{\nu}(x) q(x) d x=0$ for any polynomial $q(x)$ of degree less than $\nu .$

The first such polynomials are $p_{0}=1, p_{1}=x, p_{2}=x^{2}-1 / 5, p_{3}=x^{3}-3 x / 7$ . Show that the Gaussian quadrature formulae for $\nu=2,3$ are

\begin{array}{ll} \nu=2: & \frac{2}{3}\left[f\left(-\frac{1}{\sqrt{5}}\right)+f\left(\frac{1}{\sqrt{5}}\right)\right] \\ \nu=3: & \frac{14}{45}\left[f\left(-\sqrt{\frac{3}{7}}\right)+f\left(\sqrt{\frac{3}{7}}\right)\right]+\frac{32}{45} f(0) \end{array}

Verify the result for $\nu=3$ by considering $f(x)=1, x^{2}, x^{4}$ .

Paper 1, Section I, H

Part IB, 2011

Suppose that $A x \leqslant b$ and $x \geqslant 0$ and $A^{T} y \geqslant c$ and $y \geqslant 0$ where $x$ and $c$ are $n$ -dimensional column vectors, $y$ and $b$ are $m$ -dimensional column vectors, and $A$ is an $m \times n$ matrix. Here, the vector inequalities are interpreted component-wise.

(i) Show that $c^{T} x \leqslant b^{T} y$ .

(ii) Find the maximum value of

\begin{aligned} 6 x_{1}+8 x_{2}+3 x_{3} \quad \text { subject to } & 2 x_{1}+4 x_{2}+x_{3} \leqslant 10 \\ & 3 x_{1}+4 x_{2}+3 x_{3} \leqslant 6 \\ & x_{1}, x_{2}, x_{3} \geqslant 0 \end{aligned}

You should state any results from the course used in your solution.

Paper 2, Section I, H

Part IB, 2011

Let $N=\{1, \ldots, n\}$ be the set of nodes of a network, where 1 is the source and $n$ is the $\operatorname{sink}$ . Let $c_{i j}$ denote the capacity of the arc from node $i$ to node $j$ .

(i) In the context of maximising the flow through this network, define the following terms: feasible flow, flow value, cut, cut capacity.

(ii) State and prove the max-flow min-cut theorem for network flows.

Paper 3, Section II, H

Part IB, 2011

(i) What does it mean to say a set $C \subseteq \mathbb{R}^{n}$ is convex?

(ii) What does it mean to say $z$ is an extreme point of a convex set $C ?$

Let $A$ be an $m \times n$ matrix, where $n>m$ . Let $b$ be an $m \times 1$ vector, and let

C=\left\{x \in \mathbb{R}^{n}: A x=b, x \geqslant 0\right\}

where the inequality is interpreted component-wise.

(iii) Show that $C$ is convex.

(iv) Let $z=\left(z_{1}, \ldots, z_{n}\right)^{T}$ be a point in $C$ with the property that at least $m+1$ indices $i$ are such that $z_{i}>0$ . Show that $z$ is not an extreme point of $C$ . [Hint: If $r>m$ , then any set of $r$ vectors in $\mathbb{R}^{m}$ is linearly dependent.]

(v) Now suppose that every set of $m$ columns of $A$ is linearly independent. Let $z=\left(z_{1}, \ldots, z_{n}\right)^{T}$ be a point in $C$ with the property that at most $m$ indices $i$ are such that $z_{i}>0$ . Show that $z$ is an extreme point of $C$ .

Paper 4, Section II, H

Part IB, 2011

A company must ship coal from four mines, labelled $A, B, C, D$ , to supply three factories, labelled $a, b, c$ . The per unit transport cost, the outputs of the mines, and the requirements of the factories are given below.

\begin{tabular}{c|c|c|c|c|c} & $A$ & $B$ & $C$ & $D$ & \ \hline $a$ & 12 & 3 & 5 & 2 & 34 \ \hline $b$ & 4 & 11 & 2 & 6 & 21 \ \hline $c$ & 3 & 9 & 7 & 4 & 23 \ \hline & 20 & 32 & 15 & 11 & \end{tabular}

For instance, mine $B$ can produce 32 units of coal, factory a requires 34 units of coal, and it costs 3 units of money to ship one unit of coal from $B$ to $a$ . What is the minimal cost of transporting coal from the mines to the factories?

Now suppose increased efficiency allows factory $b$ to reduce its requirement to $20.8$ units of coal, and as a consequence, mine $B$ reduces its output to $31.8$ units. By how much does the transport cost decrease?

Paper 3, Section I, C

Part IB, 2011

A particle of mass $m$ and energy $E$ , incident from $x=-\infty$ , scatters off a delta function potential at $x=0$ . The time independent Schrödinger equation is

-\frac{\hbar^{2}}{2 m} \frac{d^{2} \psi}{d x^{2}}+U \delta(x) \psi=E \psi

where $U$ is a positive constant. Find the reflection and transmission probabilities.

Paper 4, Section $I$ , C

Part IB, 2011

Consider the 3-dimensional oscillator with Hamiltonian

H=-\frac{\hbar^{2}}{2 m} \nabla^{2}+\frac{m \omega^{2}}{2}\left(x^{2}+y^{2}+4 z^{2}\right)

Find the ground state energy and the spacing between energy levels. Find the degeneracies of the lowest three energy levels.

[You may assume that the energy levels of the 1-dimensional harmonic oscillator with Hamiltonian

H_{0}=-\frac{\hbar^{2}}{2 m} \frac{d^{2}}{d x^{2}}+\frac{m \omega^{2}}{2} x^{2}

$\left.\operatorname{are}\left(n+\frac{1}{2}\right) \hbar \omega, n=0,1,2, \ldots .\right]$

Paper 1, Section II, C

Part IB, 2011

For a quantum mechanical particle moving freely on a circle of length $2 \pi$ , the wavefunction $\psi(t, x)$ satisfies the Schrödinger equation

i \hbar \frac{\partial \psi}{\partial t}=-\frac{\hbar^{2}}{2 m} \frac{\partial^{2} \psi}{\partial x^{2}}

on the interval $0 \leqslant x \leqslant 2 \pi$ , and also the periodicity conditions $\psi(t, 2 \pi)=\psi(t, 0)$ , and $\frac{\partial \psi}{\partial x}(t, 2 \pi)=\frac{\partial \psi}{\partial x}(t, 0)$ . Find the allowed energy levels of the particle, and their degeneracies.

The current is defined as

j=\frac{i \hbar}{2 m}\left(\psi{\frac{\partial \psi^{*}}{\partial x}}^{*}-\psi^{*} \frac{\partial \psi}{\partial x}\right)

where $\psi$ is a normalized state. Write down the general normalized state of the particle when it has energy $2 \hbar^{2} / m$ , and show that in any such state the current $j$ is independent of $x$ and $t$ . Find a state with this energy for which the current has its maximum positive value, and find a state with this energy for which the current vanishes.

Paper 4, Section I, E

Complex Analysis

Part IB, 2011

Let $f(z)$ be an analytic function in an open subset $U$ of the complex plane. Prove that $f$ has derivatives of all orders at any point $z$ in $U$ . [You may assume Cauchy's integral formula provided it is clearly stated.]

Paper 2, Section II, C

Part IB, 2011

The quantum mechanical angular momentum operators are

L_{i}=-i \hbar \epsilon_{i j k} x_{j} \frac{\partial}{\partial x_{k}} \quad(i=1,2,3)

Show that each of these is hermitian.

The total angular momentum operator is defined as $\mathbf{L}^{2}=L_{1}^{2}+L_{2}^{2}+L_{3}^{2}$ . Show that $\left\langle\mathbf{L}^{2}\right\rangle \geqslant\left\langle L_{3}^{2}\right\rangle$ in any state, and show that the only states where $\left\langle\mathbf{L}^{2}\right\rangle=\left\langle L_{3}^{2}\right\rangle$ are those with no angular dependence. Verify that the eigenvalues of the operators $\mathbf{L}^{2}$ and $L_{3}^{2}$ (whose values you may quote without proof) are consistent with these results.

Paper 3, Section II, C

Part IB, 2011

For an electron in a hydrogen atom, the stationary state wavefunctions are of the form $\psi(r, \theta, \phi)=R(r) Y_{l m}(\theta, \phi)$ , where in suitable units $R$ obeys the radial equation

\frac{d^{2} R}{d r^{2}}+\frac{2}{r} \frac{d R}{d r}-\frac{l(l+1)}{r^{2}} R+2\left(E+\frac{1}{r}\right) R=0 .

Explain briefly how the terms in this equation arise.

This radial equation has bound state solutions of energy $E=E_{n}$ , where $E_{n}=-\frac{1}{2 n^{2}}(n=1,2,3, \ldots)$ . Show that when $l=n-1$ , there is a solution of the form $R(r)=r^{\alpha} e^{-r / n}$ , and determine $\alpha$ . Find the expectation value $\langle r\rangle$ in this state.

What is the total degeneracy of the energy level with energy $E_{n}$ ?

Paper 1, Section I, $\mathbf{7 H} \quad$

Part IB, 2011

Consider the experiment of tossing a coin $n$ times. Assume that the tosses are independent and the coin is biased, with unknown probability $p$ of heads and $1-p$ of tails. A total of $X$ heads is observed.

(i) What is the maximum likelihood estimator $\widehat{p}$ of $p$ ?

Now suppose that a Bayesian statistician has the $\operatorname{Beta}(M, N)$ prior distribution for $p$ .

(ii) What is the posterior distribution for $p$ ?

(iii) Assuming the loss function is $L(p, a)=(p-a)^{2}$ , show that the statistician's point estimate for $p$ is given by

\frac{M+X}{M+N+n}

[The $\operatorname{Beta}(M, N)$ distribution has density $\frac{\Gamma(M+N)}{\Gamma(M) \Gamma(N)} x^{M-1}(1-x)^{N-1}$ for $0<x<1$ and $\left.\operatorname{mean} \frac{M}{M+N} .\right]$

Paper 2, Section I, H

Part IB, 2011

Let $X_{1}, \ldots, X_{n}$ be random variables with joint density function $f\left(x_{1}, \ldots, x_{n} ; \theta\right)$ , where $\theta$ is an unknown parameter. The null hypothesis $H_{0}: \theta=\theta_{0}$ is to be tested against the alternative hypothesis $H_{1}: \theta=\theta_{1}$ .

(i) Define the following terms: critical region, Type I error, Type II error, size, power.

(ii) State and prove the Neyman-Pearson lemma.

Paper 1, Section II, H

Part IB, 2011

Let $X_{1}, \ldots, X_{n}$ be independent random variables with probability mass function $f(x ; \theta)$ , where $\theta$ is an unknown parameter.

(i) What does it mean to say that $T$ is a sufficient statistic for $\theta$ ? State, but do not prove, the factorisation criterion for sufficiency.

(ii) State and prove the Rao-Blackwell theorem.

Now consider the case where $f(x ; \theta)=\frac{1}{x !}(-\log \theta)^{x} \theta$ for non-negative integer $x$ and $0<\theta<1$ .

(iii) Find a one-dimensional sufficient statistic $T$ for $\theta$ .

(iv) Show that $\tilde{\theta}=\mathbb{\prod}_{\left\{X_{1}=0\right\}}$ is an unbiased estimator of $\theta$ .

(v) Find another unbiased estimator $\widehat{\theta}$ which is a function of the sufficient statistic $T$ and that has smaller variance than $\tilde{\theta}$ . You may use the following fact without proof: $X_{1}+\cdots+X_{n}$ has the Poisson distribution with parameter $-n \log \theta$ .

Paper 3, Section II, H

Part IB, 2011

Consider the general linear model

Y=X \beta+\epsilon

where $X$ is a known $n \times p$ matrix, $\beta$ is an unknown $p \times 1$ vector of parameters, and $\epsilon$ is an $n \times 1$ vector of independent $N\left(0, \sigma^{2}\right)$ random variables with unknown variance $\sigma^{2}$ . Assume the $p \times p$ matrix $X^{T} X$ is invertible.

(i) Derive the least squares estimator $\widehat{\beta}$ of $\beta$ .

(ii) Derive the distribution of $\widehat{\beta}$ . Is $\widehat{\beta}$ an unbiased estimator of $\beta$ ?

(iii) Show that $\frac{1}{\sigma^{2}}\|Y-X \widehat{\beta}\|^{2}$ has the $\chi^{2}$ distribution with $k$ degrees of freedom, where $k$ is to be determined.

(iv) Let $\tilde{\beta}$ be an unbiased estimator of $\beta$ of the form $\tilde{\beta}=C Y$ for some $p \times n$ matrix $C$ . By considering the matrix $\mathbb{E}\left[(\widehat{\beta}-\widetilde{\beta})(\widehat{\beta}-\beta)^{T}\right]$ or otherwise, show that $\widehat{\beta}$ and $\widehat{\beta}-\widetilde{\beta}$ are independent.

[You may use standard facts about the multivariate normal distribution as well as results from linear algebra, including the fact that $I-X\left(X^{T} X\right)^{-1} X^{T}$ is a projection matrix of rank $n-p$ , as long as they are carefully stated.]

Paper 4, Section II, H

Part IB, 2011

Consider independent random variables $X_{1}, \ldots, X_{n}$ with the $N\left(\mu_{X}, \sigma_{X}^{2}\right)$ distribution and $Y_{1}, \ldots, Y_{n}$ with the $N\left(\mu_{Y}, \sigma_{Y}^{2}\right)$ distribution, where the means $\mu_{X}, \mu_{Y}$ and variances $\sigma_{X}^{2}, \sigma_{Y}^{2}$ are unknown. Derive the generalised likelihood ratio test of size $\alpha$ of the null hypothesis $H_{0}: \sigma_{X}^{2}=\sigma_{Y}^{2}$ against the alternative $H_{1}: \sigma_{X}^{2} \neq \sigma_{Y}^{2}$ . Express the critical region in terms of the statistic $T=\frac{S_{X X}}{S_{X X}+S_{Y Y}}$ and the quantiles of a beta distribution, where

S_{X X}=\sum_{i=1}^{n} X_{i}^{2}-\frac{1}{n}\left(\sum_{i=1}^{n} X_{i}\right)^{2} \text { and } S_{Y Y}=\sum_{i=1}^{n} Y_{i}^{2}-\frac{1}{n}\left(\sum_{i=1}^{n} Y_{i}\right)^{2}

[You may use the following fact: if $U \sim \Gamma(a, \lambda)$ and $V \sim \Gamma(b, \lambda)$ are independent, then $\left.\frac{U}{U+V} \sim \operatorname{Beta}(a, b) .\right]$

Paper 1, Section I, D

Variational Principles

Part IB, 2011

(i) Write down the Euler-Lagrange equations for the volume integral

\int_{V}(\nabla u \cdot \nabla u+12 u) d V

where $V$ is the unit ball $x^{2}+y^{2}+z^{2} \leqslant 1$ , and verify that the function $u(x, y, z)=x^{2}+y^{2}+z^{2}$ gives a stationary value of the integral subject to the condition $u=1$ on the boundary.

(ii) Write down the Euler-Lagrange equations for the integral

\int_{0}^{1}\left(\dot{x}^{2}+\dot{y}^{2}+4 x+4 y\right) d t

where the dot denotes differentiation with respect to $t$ , and verify that the functions $x(t)=t^{2}, y(t)=t^{2}$ give a stationary value of the integral subject to the boundary conditions $x(0)=y(0)=0$ and $x(1)=y(1)=1$ .

Paper 3, Section I, D

Variational Principles

Part IB, 2011

Find, using a Lagrange multiplier, the four stationary points in $\mathbb{R}^{3}$ of the function $x^{2}+y^{2}+z^{2}$ subject to the constraint $x^{2}+2 y^{2}-z^{2}=1$ . By considering the situation geometrically, or otherwise, identify the nature of the constrained stationary points.

How would your answers differ if, instead, the stationary points of the function $x^{2}+2 y^{2}-z^{2}$ were calculated subject to the constraint $x^{2}+y^{2}+z^{2}=1 ?$

Paper 2, Section II, D

Variational Principles

Part IB, 2011

(i) Let $I[y]=\int_{0}^{1}\left(\left(y^{\prime}\right)^{2}-y^{2}\right) d x$ , where $y$ is twice differentiable and $y(0)=y(1)=0$ . Write down the associated Euler-Lagrange equation and show that the only solution is $y(x)=0$ .

(ii) Let $J[y]=\int_{0}^{1}\left(y^{\prime}+y \tan x\right)^{2} d x$ , where $y$ is twice differentiable and $y(0)=y(1)=$ 0 . Show that $J[y]=0$ only if $y(x)=0$ .

(iii) Show that $I[y]=J[y]$ and deduce that the extremal value of $I[y]$ is a global minimum.

(iv) Use the second variation of $I[y]$ to verify that the extremal value of $I[y]$ is a local minimum.

(v) How would your answers to part (i) differ in the case $I[y]=\int_{0}^{2 \pi}\left(\left(y^{\prime}\right)^{2}-y^{2}\right) d x$ , where $y(0)=y(2 \pi)=0$ ? Show that the solution $y(x)=0$ is not a global minimizer in this case. (You may use without proof the result $I[x(2 \pi-x)]=-\frac{8}{15}\left(2 \pi^{2}-5\right)$ .) Explain why the arguments of parts (iii) and (iv) cannot be used.