Past exam of the mathematics course of the University of Cambridge / 2001 / ib / Paper 2

The contraction mapping theorem states that a self-map $f$ of a nonempty complete metric space $(X,d)$ satisfying $d(fu,fv)\le qd(u,v)$ for a fixed $0\le q<1$ has a unique fixed point. Its iterates converge to that point from every starting point.

To prove it, set $u_{n+1}=f(u_n)$. Induction gives $d(u_{n+1},u_n)\le q^{n}d(u_1,u_0)$. Hence for $m>n$, the triangle inequality yieldsThus the iterates are a Cauchy sequence, with limit $u$ by completeness. The contraction inequality gives $d(fu,u)\le qd(u,u_n)+d(u_{n+1},u)\to 0$, so $f(u)=u$. For any two fixed points $u,v$, $d(u,v)\le qd(u,v)$ forces equality of the points. This proves existence, uniqueness and convergence; passing $m\to \infty$ also gives the displayed error bound.

For the three-point example, positivity and symmetry of $d^{\prime }$ are immediate. For three distinct points, the largest side has length two, no more than the sum of the other two; repeated-point triangle inequalities are trivial. Thus $d^{\prime }$ is a metric. The discrete metric satisfieswhich proves bilipschitz equivalence of the two metrics. DefineThe ratios of output to input distances for the three distinct pairs are $1/2,1/2,0$ in $d^{\prime }$, so it is a contraction with $q=1/2$. In $d$, the pair $(x,y)$ has input and output distance one, precluding any $q<1$. This illustrates the contraction property under equivalent metrics.

For a Cartesian second-rank tensor, write $S_{ij}=(A_{ij}+A_{ji})/2$ and $W_{ij}=(A_{ij}-A_{ji})/2$. Under an orthogonal change of frame,where the last two equalities follow by interchanging the dummy indices in $A_{ji}^{\prime }$. Thus the symmetric and antisymmetric parts obey the same tensor transformation law. If $A=S+W$ with $S^T=S$, $W^T=-W$, adding or subtracting its transpose forces $S=(A+A^T)/2$ and $W=(A-A^T)/2$. This also proves uniqueness.

For the given matrix, the scalar part is $a=\mathrm{Tr}(A)/3=3$. The symmetric part is $S=\left(\begin{array}{ccc}1& 3& 2\\ 3& 5& 4\\ 2& 4& 3\end{array}\right)$, so the traceless second-rank tensor is $B=S-3I$. The skew part is $W=\left(\begin{array}{ccc}0& -1& 1\\ 1& 0& 2\\ -1& -2& 0\end{array}\right)$. Comparing with the cross product matrix $[p{]}_{\times }=\left(\begin{array}{ccc}0& -p_3& p_2\\ p_3& 0& -p_1\\ -p_2& p_1& 0\end{array}\right)$ givesThen $A=aI+[p{]}_{\times }+B$ proves the decomposition for every vector. The vector dual to the antisymmetric tensor is an axial vector under reflections, and an ordinary vector under proper rotations.

For an observed $x\ge 0$, the continuous uniform distribution likelihood is $p(x\mid \theta )={\theta }^{-1}{1}_{\{\theta \ge x\}}$, with $\theta >0$. Multiplying by the stated prior cancels the factor $\theta$, giving $e^{-\theta }{1}_{\{\theta \ge x\}}$. Its integral over the permitted parameter values is $e^{-x}$. Hence the posterior distribution isThis is the exponential posterior for a uniform endpoint. Its posterior mean is $x+1$ and its variance is one. The posterior expected squared-error loss decomposes asSince $c>0$, its unique minimum occurs at the Bayes estimate $\boxed{{\hat{\theta }}_B=x+1}$. The positive loss multiplier changes the risk, not the optimizing action.

A connected space admits no separation into two disjoint nonempty open subsets whose union is the space. A path-connected space has, for every pair of points, a continuous path from $[0,1]$ joining them. If a path-connected space had a separation $U,V$, choose its endpoints in different pieces. Their inverse images under the path would separate the connected interval $[0,1]$, a contradiction. Thus path connectedness implies connectedness.

For the specified subspace, first consider $Y=I\cup {\bigcup }_{n\ge 1}{J}_n$. Every point of a tooth $J_n$ can move vertically to its base in $I$, then horizontally to the origin; points already on $I$ use only the horizontal segment. Concatenating these paths shows that $Y$ is path-connected and hence connected.

Every point $(0,t)$ of $A$ is a limit of $(1/n,t)\in Y$. Consequently $Y$ is dense in $X=Y\cup A$ in the subspace topology. To prove $X$ connected, suppose $X=U\cup V$ were a separation. Restricting to the connected $Y$ puts all of $Y$ in one piece, say $U$. But the other nonempty relatively open piece $V$ must meet dense $Y$, a contradiction. Therefore $\boxed{X\text{ is connected}}$. This uses density, not an unproved path from the added vertical segment to the teeth.

Gaussian elimination uses first-column multipliers $-2,2,-3$, second-column multiplier $2$ in the last row, and third-column multiplier $1$ there. Recording these in a unit lower-triangular matrix gives the LU decompositionForward substitution in $Ly=b$ gives $y=(-2,-2,8,1{)}^T$. Back substitution gives $x_4=1$, $-3x_3+2x_4=8$, $x_2+2x_3+2x_4=-2$, and $2x_1-x_2+3x_3+2x_4=-2$. Hence the solution is

Right multiplication is linear because $(sX+tY)A=sXA+tYA$. In the supplied row-entry basis, write $X=\left(\begin{array}{cc}{x}_1& x_2\\ x_3& x_4\end{array}\right)$. Multiplying on the right gives coordinates $(a{x}_1+c{x}_2,b{x}_1+d{x}_2,a{x}_3+c{x}_4,b{x}_3+d{x}_4{)}^T$. ThereforeThe transpose is ordinary, with no complex conjugation. Block determinants and invariance of determinant under transpose proveFor every polynomial $p$, powers of right multiplication give $p({\rho }_A)(X)=Xp(A)$. If $p(A)=0$ then $p({\rho }_A)=0$; if $p({\rho }_A)=0$, take $X=I$ to infer $p(A)=0$. They have identical annihilating polynomials, so their unique monic least-degree annihilator, the minimal polynomial, is the same. Thus $m_{{\rho }_A}=m_A$, as in the characteristic and minimal polynomials of right multiplication result.

At a point $z_0=x+iy$, complex differentiability means thatexists and is independent of the direction of approach. Write $f=u+iv$. Restricting to real $h$ gives $f^{\prime }=u_x+i{v}_x$. Restricting to $h=it$, with real $t\to 0$, givesThese directional limits establish existence of the displayed partial derivatives. Equating their real and imaginary parts gives the Cauchy-Riemann equationsThe argument applies at every point of the given open domain; it does not assume continuity of the partial derivatives beforehand.

For a bilinear form $\varphi$, define $F_{\varphi }:V\to V^{\ast }$ by $F_{\varphi }(v)(u)=\varphi (u,v)$. Bilinearity makes $F_{\varphi }(v)$ a linear functional and makes $F_{\varphi }$ linear in $v$. Conversely, every linear $F:V\to V^{\ast }$ defines a bilinear form by ${\varphi }_F(u,v)=F(v)(u)$. These constructions undo each other, giving the desired bijective correspondence.

For a nondegenerate bilinear form, $F_{\varphi }$ has zero kernel and is an isomorphism because $V$ and its dual space have the same finite dimension. For the two forms, putIt is an isomorphism and satisfies ${\varphi }_1(u,\alpha v)=F_{{\varphi }_1}(\alpha v)(u)=F_{{\varphi }_2}(v)(u)={\varphi }_2(u,v)$ for all $u,v$. This is the representation of a bilinear form relative to a nondegenerate bilinear form.

If both forms are symmetric, thenNondegeneracy makes the adjoint with respect to ${\varphi }_1$ unique; this equality proves $\boxed{{\alpha }^{†}=\alpha }$ in that bilinear-form sense. No positivity or Hermitian conjugation is assumed over the arbitrary field.

For $H=p^2/(2m)+V(x)$ and a time-independent operator $O$, differentiate its expectation value and use the Schrödinger equation and its adjoint. Moving $H$ across the inner product by integration by parts givesWork with wavefunctions in the displayed operators' domains; the vanishing at infinity removes the associated boundary terms. This is the Ehrenfest theorem derived from time evolution.

The canonical commutation relation follows directly from differentiating $x\psi$: $[p,x]\psi =-i\hslash \psi$. Thus $[p^2,x]=p[p,x]+[p,x]p=-2i\hslash p$, while $[V(x),x]=0$. It follows thatFor the momentum equation, apply both products to a test wavefunction:The kinetic term commutes with $p$, so $[H,p]=i\hslash V^{\prime }$. ThereforeThese are the classical equations from Ehrenfest theorem for position and momentum expectations; the force expectation need not equal the force evaluated at the expected position.

A metric space is totally bounded if, for every $ϵ>0$, finitely many open balls of radius $ϵ$ cover it. The Bolzano-Weierstrass property here means that every sequence has a subsequence converging to a point of the space, namely sequential compactness.

First suppose that property holds. A Cauchy sequence has a convergent subsequence with limit $x$ in the space. Given $ϵ>0$, choose an index after which all sequence terms lie within $ϵ/2$ of each other, and a subsequence term beyond that index within $ϵ/2$ of $x$. The triangle inequality then puts every subsequent term within $ϵ$ of $x$. Thus the whole Cauchy sequence converges, proving completeness.

If total boundedness failed, some $ϵ>0$ would admit no finite ball cover. Choose points inductively outside the union of the $ϵ$-balls about previously chosen points. Distinct sequence terms then have distance at least $ϵ$. No subsequence can be Cauchy, and therefore none can converge, a contradiction. This proves total boundedness.

Conversely, suppose the space is complete and totally bounded. For any sequence, cover the space by finitely many radius-$2^{-1}$ balls and retain the infinitely many indices in one ball. Within those indices, a finite cover by radius-$2^{-2}$ balls retains an infinite subset in one smaller ball. Repeat with radii $2^{-k}$ to obtain nested infinite index sets $I_k$. Choose increasing indices $n_k\in I_k$. For $l,j\ge k$, both terms lie in the ball selected at step $k$, soThe subsequence is Cauchy and completeness makes it converge within the space. Hence the Bolzano-Weierstrass property is equivalent to completeness plus total boundedness.

An isotropic tensor has unchanged components under every rotation: for rank four, $A_{ijkl}=R_{ia}{R}_{jb}{R}_{kc}{R}_{ld}{A}_{abcd}$. Orthogonality gives $R_{ia}{R}_{ja}={\delta }_{ij}$, so each product of paired Kronecker deltas is invariant. Every linear combination of ${\delta }_{ij}{\delta }_{kl}$, ${\delta }_{ik}{\delta }_{jl}$ and ${\delta }_{il}{\delta }_{jk}$ is therefore isotropic, for arbitrary coefficients.

For the integral, differentiation away from the origin givesAfter multiplication by $x_i{x}_j$, this behaves as $O(r^{-1})$ and is locally integrable in three dimensions. Interpret the integral as the limit with a small central ball removed. A rotation preserves the integration ball and the radial kernel, so the resulting $B$ is an isotropic tensor integral. The symmetries $i\leftrightarrow j$ and $k\leftrightarrow l$ force the two cross-pair coefficients equal:Taking the trace in $k,l$ uses ${\nabla }^2(r^{-1})=0$ off the origin and gives $3A+2B=0$. For the other contraction, the displayed Hessian gives ${\sum }_{ij}{x}_i{x}_j{\partial }_i{\partial }_j(r^{-1})=2/r$. ThusSolving gives $B=2\pi a^2/5$ and $A=-4\pi a^2/15$. Therefore the requested tensor isThis is the quadratically weighted inverse-radius Hessian integral. The origin creates no extra contribution to this weighted integral; even the distributional point term in the unweighted Hessian is annihilated by $x_i{x}_j$.

For a generalized likelihood-ratio test, maximize the likelihood separately over the null parameter space and the unrestricted space. Define $\Lambda ={\sup }_{H_0}L/\sup L\le 1$, and reject for small $\Lambda$, equivalently large $T=-2\log \Lambda$. Choose the rejection threshold to achieve the desired null significance level, using an exact distribution when available or a justified asymptotic calibration; nuisance parameters are fitted under the respective restrictions.

For independent Poisson distributions, the likelihood is $L={\prod }_i{e}^{-{\lambda }_i}{\lambda }_i^{X_i}/X_i!$. The unrestricted maximizers are ${\hat{\lambda }}_i=X_i$, allowing zero as a boundary value. Under the common-mean null, maximizing $e^{-n\lambda }{\lambda }^{{\sum }_i{X}_i}$ gives $\hat{\lambda }=\bar{X}$. The exponential and factorial factors cancel in the ratio, yieldingIf all counts are zero, set $\Lambda =1$ and $T=0$; no division by $\bar{X}$ is then needed.

For positive $\bar{X}$, put $X_i=\bar{X}+{\delta }_i$, so ${\sum }_i{\delta }_i=0$. Expanding the logarithm givesConsequentlyIt is the quadratic Pearson approximation to the Poisson deviance. The approximated statistic is the logarithmic ratio $T$, not the bounded raw ratio $\Lambda$.

Under the null in the large-common-count regime, this statistic has an approximate chi-squared distribution with $n-1$ degrees of freedom: fitting the common mean removes one independent residual direction. For $n=7$, use six degrees of freedom. At $T=27.3$, the upper-tail probability in that approximation isThus reject the equal-mean null at conventional 5% or 1% significance levels, provided the expected counts justify the chi-square approximation. No particular significance level or common count was supplied, so the numerical decision is stated with those assumptions.

The Liouville theorem states that every bounded entire function is constant. Let $|f(z)|\le M$ and choose distinct $a,b$. For $R>\max (|a|,|b|)$, partial fractions and the Cauchy integral formula givewith the circle traversed anticlockwise. On that circle,The displayed difference is independent of $R$, so $f(a)=f(b)$. Since $a,b$ were arbitrary, $f$ is constant. This proves the theorem with the requested two-pole contour rather than assuming it.

Set $F(z)=\exp [-(1-i)g(z)]$. It is entire, and $\mathrm{Re}[(1-i)g]=u+v$ makes $|F|=e^{-(u+v)}\le 1$. By the just-proved Liouville theorem, $F$ is constant. Differentiation gives $0=F^{\prime }=-(1-i)g^{\prime }F$. The exponential never vanishes, so $g^{\prime }=0$ everywhere and $g$ is constant. This is the entire function confined to a half-plane is constant principle.

Set $F(z)=\exp (ig(z{)}^2)$. Since $\mathrm{Im}(g^2)=2uv$, its modulus is $e^{-2uv}\le 1$. The Liouville theorem again makes $F$ constant, and $F^{\prime }=2ig{g}^{\prime }F=0$ implies $(g^2{)}^{\prime }=0$. Hence $g^2$ is a constant $c$. If $c=0$, then $g=0$. If $c\ne 0$, then $g$ never vanishes and $g{g}^{\prime }=0$ implies $g^{\prime }=0$. In either case $g$ is constant. This is also an application of the one-sided product bound for an entire function after rotating $g$ by $i$.

For a real symmetric positive-definite matrix, the Cholesky decomposition is $B=R^{T}R$, where $R$ is upper triangular with positive diagonal; equivalently $B=L{L}^T$ with $L=R^T$ lower triangular.

Existence can be proved by induction. Write $B=\left(\begin{array}{cc}b& v^T\\ v& C\end{array}\right)$, where $b>0$. For a nonzero vector $z$, evaluate the quadratic form at $(-v^{T}z/b,z{)}^T$ to obtain $z^T(C-v{v}^T/b)z>0$. The Schur complement is therefore positive definite. By induction it has factor $R_0^T{R}_0$, andhas $R^{T}R=B$. The one-dimensional starting case is the positive square root.

For uniqueness, if $R_1^T{R}_1=R_2^T{R}_2=B$, then $U=R_2{R}_1^{-1}$ is upper triangular and satisfies $U^{T}U=I$. Since $U^{-1}$ is upper triangular and equals $U^T$, which is lower triangular, $U$ is diagonal. Orthogonality makes its diagonal entries $\pm 1$, and positivity of the diagonals of $R_1,R_2$ forces $+1$. Hence $U=I$ and $\boxed{R_1=R_2}$.

Full column rank makes $B=A^{T}A$ positive definite: for nonzero $v$, $v^{T}Bv=\Vert Av{\Vert }^2>0$. Let $B=R^{T}R$ be its unique upper-triangular Cholesky decomposition with positive diagonal. Defining $Q=A{R}^{-1}$ givesThus the skinny QR decomposition exists. If $A=\tilde{Q}\tilde{R}$ is another such decomposition, orthonormality gives $A^{T}A={\tilde{R}}^T\tilde{R}$. Cholesky uniqueness forces $\tilde{R}=R$, and then $\tilde{Q}=A{R}^{-1}=Q$. Therefore the skinny factorization with positive diagonal is unique. This is the thin QR factorization from Cholesky decomposition; no inverse of the rectangular $Q$ is assumed.

The algebraic dual space is $V^{\ast }={\mathrm{Hom}}_k(V,k)$, the vector space of linear functionals. For an ordered basis $v_1,\dots ,v_n$, define the dual basis by $v^i(v_j)={\delta }_{ij}$, equivalently $v^i({\sum }_j{x}_j{v}_j)=x_i$. Every functional satisfies $\ell ={\sum }_i\ell (v_i)v^i$, proving spanning. Evaluating a zero linear combination on each $v_j$ forces every coefficient to vanish, proving independence.

For a linear map $\alpha :V\to W$, its dual map is ${\alpha }^{\ast }:W^{\ast }\to V^{\ast }$, ${\alpha }^{\ast }(\ell )=\ell \circ \alpha$. Suppose the matrix of $\alpha$ satisfies $\alpha (v_i)={\sum }_j{A}_{ji}{w}_j$. ThenThese are the $i$th coordinates of ${\alpha }^{\ast }(w^j)$ in the dual basis, so the dual matrix is $\boxed{A^T}$. For complex vector spaces this is still an ordinary transpose, because the algebraic dual uses linear functionals, not conjugate-linear ones.

To prove equality of ranks directly, $\ker {\alpha }^{\ast }$ consists precisely of functionals on $W$ vanishing on $\mathrm{im}\alpha$, its annihilator. A basis of the image extends to a basis of $W$; such functionals have zero values on the image basis and arbitrary values on the remaining $\dim W-\mathrm{rank}\alpha$ vectors. Thus $\dim \ker {\alpha }^{\ast }=\dim W-\mathrm{rank}\alpha$. The rank-nullity theorem givesFinally, if $\alpha$ is invertible, for every $\ell \in V^{\ast }$ the two compositions give $(\ell \circ {\alpha }^{-1})\circ \alpha =\ell$ and $(\ell \circ \alpha )\circ {\alpha }^{-1}=\ell$. Hence the two dual maps are mutual inverses and

For a rational function, the stipulated decay implies $R(z)=O(|z{|}^{-2})$ at infinity, unless it vanishes identically. Thus its real-line integral converges absolutely. Close the segment $[-T,T]$ with an upper semicircle, choosing $T$ beyond all finite poles. The arc contribution has modulus at most $\pi T{\sup }_{|z|=T}|R(z)|=O(T^{-1})$, tending to zero. The residue theorem therefore givesThere are no real poles requiring indentations.

Apply this to $R(z)=1/(1+z^{2n})$. Its upper-half-plane poles are ${\zeta }_k=e^{i(2k+1)\pi /(2n)}$, $k=0,\dots ,n-1$, all simple. Since ${\zeta }_k^{2n}=-1$, their residues areFor $\theta =\pi /(2n)$, the finite geometric series givesThe full real-line integral is consequently $\pi /[n\sin (\pi /(2n))]$. Its integrand is even, so the requested half-line integral is

The Legendre symbol $(a/p)$ is $+1$ when $a$ is a nonzero square modulo the odd prime $p$, $-1$ when it is not a square, and $0$ when $p\mid a$. For the coprime case, Euler's criterion statesWrite $h=(p-1)/2$. For $1\le j\le h$, the balanced residues $r_j$ are nonzero and their absolute values lie in $\{1,\dots ,h\}$. If $|r_j|=|r_k|$, then $aj\equiv \pm ak(\mathrm{mod}p)$. Cancel $a$. The plus sign forces $j=k$; the minus sign would require $j+k=p$, impossible because $j+k\le p-1$. Thus the absolute residues form a permutation of $1,\dots ,h$. If exactly $l$ are negative, multiplying givesSince $p$ does not divide $h!$, cancellation and Euler's criterion prove Gauss's lemma:The two signs are distinct modulo the odd prime, so this congruence identifies the integer symbol itself.

For $a=2$, the balanced representative of $2j$ is negative precisely when $j>p/4$, giving $l=(p-1)/2-\lfloor p/4\rfloor$. Checking the four odd residue classes modulo eight gives even $l$ for $p\equiv 1,7$ and odd $l$ for $p\equiv 3,5$. HenceThis is the quadratic character of two obtained from the lemma.

Let $P=p_1\cdots p_m$ and $N=8P^2-1$. If a prime $q$ divides $N$, then $q$ is odd and cannot divide $P$. Moreoverso $2$ has an explicit nonzero square root modulo $q$. The criterion just proved forces every prime divisor of $N$ into the classes $1$ or $7$ modulo eight. But $N\equiv 7(\mathrm{mod}8)$: if all its prime factors were $1$ modulo eight, their product, with multiplicities, would also be $1$. Thus at least one prime divisor is $7$ modulo eight. No listed $p_i$ divides $N$, because $N\equiv -1(\mathrm{mod}{p}_i)$. This always produces another such prime, proving infinitely many primes are congruent to seven modulo eight, the Euclid proof for infinitely many primes congruent to seven modulo eight.

The orbital angular momentum operators areOn smooth wavefunctions, $[x_i,p_j]=i\hslash {\delta }_{ij}$, while position operators commute with each other and momentum operators commute with each other. Applying the product rule for commutators givesUse it on the four terms in $[L_1,L_2]$: only $[x_2{p}_3,x_3{p}_1]=-i\hslash x_2{p}_1$ and $[x_3{p}_2,x_1{p}_3]=i\hslash x_1{p}_2$ survive, with the latter entering positively from the two minus signs. ThereforeThe cyclic versions similarly give $[L_3,L_1]=i\hslash L_2$ and $[L_3,L_2]=-i\hslash L_1$. Thus, for $L_{\pm }=L_1\pm i{L}_2$,Now define $L^2=L_1^2+L_2^2+L_3^2$. For each $i$,because the Levi-Civita symbol is antisymmetric in $j,k$ and the operator pair is symmetric. Linearity then gives $\boxed{[L^2,L_{\pm }]=0}$. The PDF superscript here is the squared total angular momentum, not the component $L_2$.

Every orbital angular momentum operator annihilates a radial function: substituting ${\partial }_{i}f(r)=f^{\prime }(r)x_i/r$ makes the two terms cancel. It also annihilates $r^2$. Thus the radial factor can be carried through the angular operators. Since $x_3^2$ is independent of $x_1,x_2$, $L_3\psi =0$ for every value of $a$.

Direct differentiation givesConsequently $L^2{x}_3^2={\hslash }^2(6x_3^2-2r^2)$ and $L^2{r}^2=0$. For a nonzero admissible radial factor, comparison with $\lambda (x_3^2+a{r}^2)f(r)$ forces $\lambda =6{\hslash }^2$ and $6a=-2$. Therefore the simultaneous eigenfunction occurs atIt is the axially symmetric quadratic orbital eigenfunction, with quantum numbers $l=2$, $m=0$ and angular dependence proportional to the spherical harmonic $Y_{20}$. The subtraction of $r^2/3$ removes its rotationally invariant scalar component.