Past exam of the mathematics course of the University of Cambridge / 2013 / ia / Paper 1

De Moivre's theorem states that $(\cos \theta +i\sin \theta {)}^n=\cos (n\theta )+i\sin (n\theta )$ for integer $n$. For $z\ne 0$, write its polar form as $z=r{e}^{i\theta }$, where $r=|z|>0$. If $w=s{e}^{i\phi }$ and $w^n=z$, equality of moduli gives $s=r^{1/n}$ and equality of arguments gives $n\phi =\theta +2\pi k$. Thus the distinct roots of a complex number areChanging the chosen argument of $z$ only permutes these roots. For $z=0$ the only root is zero. Taking $r=8$ and $\theta =\pi$ gives the cube rootsCubing any of them returns $-8$; geometrically they are equally spaced on the circle of radius two.

Put $z=x+iy$. Squaring the two nonnegative moduli and expanding gives $x^2+(y+3{)}^2=9(x^2+y^2)$. Completing the square yieldsThus the locus is an Apollonius circle with center $3i/8$ and radius $9/8$. No extraneous points were introduced by squaring, because both original sides are nonnegative. Its intersections with the imaginary axis are $-3i/4$ and $3i/2$, useful landmarks for the sketch. It surrounds zero but does not pass through zero:

Left multiplication by the given Givens rotation mixes rows two and three, so $b_{31}=a_{21}\sin {\theta }_1+a_{31}\cos {\theta }_1$. If $r_1=\sqrt{a_{21}^2+a_{31}^2}>0$, chooseEquivalently ${\theta }_1=atan2(-a_{31},a_{21})$ modulo $2\pi$. Substitution gives $b_{31}=0$ and $b_{21}=r_1$. If $a_{21}=a_{31}=0$, take ${\theta }_1=0$; the desired zero is already present. This also covers singular matrices without division by zero.

The second Givens rotation leaves row three unchanged, so $\boxed{c_{31}=b_{31}=0}$. Its other relevant entry is $c_{21}=b_{11}\sin {\theta }_2+b_{21}\cos {\theta }_2$. For $r_2=\sqrt{b_{11}^2+b_{21}^2}>0$, takeThen $c_{21}=0$ and $c_{11}=r_2$. If both entries vanish, choose ${\theta }_2=0$. The first column now has zeros below its diagonal.

Rows two and three of $C$ both have zero in column one. Any rotation of these rows therefore preserves those zeros, so $\boxed{d_{21}=d_{31}=0}$. In column two, $d_{32}=c_{22}\sin {\theta }_3+c_{32}\cos {\theta }_3$. For $r_3=\sqrt{c_{22}^2+c_{32}^2}>0$, chooseThis gives $d_{32}=0$. Again choose ${\theta }_3=0$ if both relevant entries are zero. Thus the successive Givens rotations have eliminated all entries below the diagonal without recreating earlier ones.

Each plane rotation satisfies $R_j^T{R}_j=I$. Hence $U=R_3{R}_2{R}_1$ is an orthogonal matrix and $D=UA$ is an upper triangular matrix. Multiplication by $U^T$ gives the QR decompositionThe zero-pair cases already handled make this construction valid for every real $3\times 3$ matrix, including rank-deficient matrices. Orthogonality follows from the product identity, not from any invertibility assumption on $A$.

For $x\ge 0$, the function $h(x)=e^x-1-x$ has $h(0)=0$ and $h^{\prime }(x)=e^x-1\ge 0$, because the exponential function is increasing and $e^0=1$. Therefore $\boxed{e^x\ge 1+x}$.

Write $S_n={\sum }_{j=1}^n{a}_j$ and $P_n={\prod }_{j=1}^n(1+a_j)$. Expanding the product produces $1+S_n$ and additional nonnegative terms, giving $P_n\ge 1+S_n\ge S_n$. Applying the exponential inequality to every factor givesBoth sequences are increasing, since the terms $a_j$ are positive. If $S_n$ converges to a finite value $S$, then $P_n\le e^S$, so the convergence theorem for monotone bounded sequences makes $P_n$ converge. Conversely, if $P_n$ has a finite limit, then $S_n\le P_n$ is bounded and increasing, hence converges by the same theorem. Thus the positive series and the product both converge to finite limits, or both diverge to $+\infty$. This proves the positive sum-product convergence criterion. The word limit here means a finite real limit; allowing extended infinite limits would make the conclusion vacuous for these monotone sequences.

Let $s_N={\sum }_{n=1}^N(-1{)}^{n-1}{b}_n$. Pairing consecutive terms shows $s_{2m}\ge 0$ andThe even partial sums increase and the odd partial sums decrease. They satisfy $s_{2m}\le s_{2m+1}\le b_1$, whileBoth are monotone bounded sequences and hence have limits, and the displayed difference makes their limits equal. Every partial sum belongs to one subsequence, so the alternating series converges. This is a proof of the alternating series test; the monotonicity and zero-limit hypotheses play separate roles.

The summand is positive, so it suffices to show that its partial sums are unbounded. On the block $2^k\le n<2^{k+1}$, for $k\ge 1$,There are $2^k$ terms in that block, so its sum is at least $1/[2(k+1)\log 2]$. Adding blocks gives a constant multiple of the divergent harmonic series. HenceEquivalently the integral test for convergence gives ${\int }_2^{R}dx/(x\log x)=\log \log R-\log \log 2\to \infty$. The block proof supplies the divergence without assuming the integral test.

Two nonzero vectors are linearly independent when $s\mathbf{x}+t\mathbf{y}=0$ forces $s=t=0$. Their linear span then has dimension two. If they are linearly dependent, one is a nonzero scalar multiple of the other, and their span has dimension one. Thus the two requested dimensions are $\boxed{2\text{ and }1}$.

The Euclidean scalar product and its norm are $\mathbf{x}\cdot \mathbf{y}={\sum }_{j=1}^n{x}_j{y}_j$ and $\Vert \mathbf{x}\Vert =\sqrt{\mathbf{x}\cdot \mathbf{x}}$. To prove the Cauchy-Schwarz inequality, first handle $\mathbf{y}=0$ trivially. Otherwise the squared normgivesEquality holds exactly when the residual vector is zero, meaning the vectors are linearly dependent; this includes the zero-vector cases. Expanding $\Vert \mathbf{x}+\mathbf{y}{\Vert }^2$ and applying Cauchy-Schwarz then givesTaking nonnegative square roots proves the triangle inequality.

For the unit-vector optimization, let $\mathbf{w}=\mathbf{x}+\mathbf{y}$. Independence ensures $\mathbf{w}\ne 0$. The variable part of $S$ is $\mathbf{z}\cdot \mathbf{w}$, which Cauchy-Schwarz bounds below by $-\Vert \mathbf{w}\Vert$. Equality occurs only for the antiparallel unit vector. ThusThis is minimizing a linear functional on a sphere. The two consequences follow below.

The triangle inequality gives $0<\Vert \mathbf{x}+\mathbf{y}\Vert \le \Vert \mathbf{x}\Vert +\Vert \mathbf{y}\Vert =2$. Taking its negative reciprocal givesIn fact independence excludes the equality case $\mathbf{x}=\mathbf{y}$, so the inequality is strict under the stated independence hypothesis. The weaker requested bound holds for every permitted pair.

When $\mathbf{x}\cdot \mathbf{y}=\cos (2\pi /3)=-1/2$, the squared norm of their sum is $2+2(-1/2)=1$. ThereforeThe minimizing vector is indeed a unit vector. All three pairwise scalar products then equal $-1/2$, so these three unit vectors lie in a plane, separated by $120$ degrees.

For a linear map $\alpha :{\mathbb{R}}^m\to {\mathbb{R}}^n$, its kernel and image of a linear map areThe kernel is a subspace of the domain and the image a subspace of the codomain. Given the stated bases, define the matrix of a linear map byIts $j$th column is the coordinate vector of $\alpha (e_j)$; if $v={\sum }_j{v}_j{e}_j$, the output coordinates are $(\alpha v{)}_i={\sum }_j{A}_{ij}{v}_j$.

For the change of basis, write $e_j^{\prime }={\sum }_k{P}_{kj}{e}_k$ and $f_i^{\prime }={\sum }_{\ell }{Q}_{\ell i}{f}_{\ell }$. The matrices $P,Q$ are invertible. Input coordinates change by $v_{\mathrm{old}}=P{v}_{\mathrm{new}}$ and output coordinates by $w_{\mathrm{old}}=Q{w}_{\mathrm{new}}$, soThe domain and codomain basis changes need not be the same matrix.

For $\beta$, the two input vectors form a basis of ${\mathbb{R}}^2$, so its image is the span of $v=(1,2,3{)}^T$ and $w=(6,4,2{)}^T$. The vector $n=(1,-2,1{)}^T$ is orthogonal to both, since $n\cdot v=n\cdot w=0$. Every possible output therefore satisfies $n\cdot \beta x=0$, whereas the target itself is $n$ and $n\cdot n=6$. Hence there is no $x$ with the required output. This uses an image obstruction by an annihilating functional, rather than an inconsistent guessed input.

For $\gamma$, use the input basis $v_1=(1,2,0{)}^T$, $v_2=(0,1,1{)}^T$, $v_3=(0,1,0{)}^T$. Its determinant is $-1$, so it is genuinely a basis. Write $x=s{v}_1+t{v}_2+w{v}_3$. ThenSubstitution back into physical coordinates givesFor a direct check, its standard matrix is $\left(\begin{array}{ccc}1& 0& -2\\ 1& 1& 0\end{array}\right)$, which annihilates exactly that line.

We prove independence of eigenvectors for distinct eigenvalues by induction on the number of vectors. A single eigenvector is nonzero and hence independent. Suppose the first $d-1$ are independent, and let ${\sum }_{j=1}^d{c}_j{v}_j=0$. Applying $A-{\lambda }_{d}I$ givesBy the induction hypothesis every coefficient in this shorter relation vanishes. The eigenvalues are distinct, so $c_j=0$ for $j<d$. The original relation becomes $c_d{v}_d=0$, and $v_d\ne 0$ gives $c_d=0$. Thus the entire family of eigenvectors is linearly independent. The argument works over either the real or complex field.

Represent the quadratic form by the symmetric matrixThe $xy$ block has characteristic polynomial $(2-\mu )(5-\mu )-4=(\mu -1)(\mu -6)$. Corresponding orthonormal eigenvectors, together with the $z$ direction, areThe eigenvalues are $1,6,-1$. To eliminate the linear term, solve $H\tilde{O}=-(0,3\sqrt{5},0{)}^T$, obtainingIndeed the first equation gives $x=y$, and the second then gives $3y=-3\sqrt{5}$. Define the new coordinates by $X=\tilde{O}+\tilde{x}{\tilde{e}}_1+\tilde{y}{\tilde{e}}_2+\tilde{z}{\tilde{e}}_3$. The original polynomial takes the value $-15$ at the center, so its translated and orthogonally diagonalized form isThusThe surface is an elliptic one-sheet hyperboloid, centered at $\tilde{O}$, with axis parallel to ${\tilde{e}}_3$. Its waist at $\tilde{z}=0$ is an ellipse with semiaxes $\sqrt{15}$ and $\sqrt{5/2}$. Every constant-$\tilde{z}$ section is a nonempty ellipse, so the two signs of $\tilde{z}$ belong to the same connected sheet. This is an application of principal-axis reduction of a quadric.

Construct the matrix of a linear map by expressing the images of the basis vectors in that same basis:Thus the $j$th column is $[L{e}_j{]}_B$. For $v=v_1{e}_1+v_2{e}_2$, linearity givesThe column $[Lv{]}_B$ is a coordinate vector; reconstructing the actual vector requires $Lv=(A[v{]}_B{)}_1{e}_1+(A[v{]}_B{)}_2{e}_2$. This distinguishes the linear map from its basis-dependent matrix.

By the given matrix similarity, $A^{\prime }=P^{-1}AP$ for an invertible $P$. HenceThe characteristic polynomials are identical. Therefore the characteristic equations and eigenvalues, including algebraic multiplicities, agree. The conclusion is independent of the choice between $\det (tI-A)$ and $\det (A-tI)$ conventions.

Rescaling the first basis vector gives the change-of-basis matrix $P=\mathrm{diag}(k,1)$, invertible because $k\ne 0$. Direct multiplication givesThus the matrices are related by matrix similarity. In terms of basis images, the coefficient along the rescaled first basis vector is divided by $k$, while the second component of its image is multiplied by $k$.

Let the repeated eigenvalue be $a$, and choose an eigenvector $v_1\ne 0$. Complete it to a basis $(v_1,v_2)$ of ${\mathbb{C}}^2$. In this basis the matrix is an upper triangular matrix, with first column $(a,0{)}^T$, say $T=\left(\begin{array}{cc}a& c\\ 0& d\end{array}\right)$. Its characteristic polynomial is $(t-a)(t-d)$. By part (a)(ii), this must equal $(t-a{)}^2$, so $d=a$.

If $c=0$, the matrix is already $aI$. If $c\ne 0$, rescale the first basis vector by $k=c$ and apply part (a)(iii); the upper-right entry becomes one. ThusThe second possibility is a size-two Jordan block. It has only one independent eigenvector, whereas $aI$ has a two-dimensional eigenspace, so the two types cannot be related by matrix similarity. This repeated-eigenvalue classification in dimension two proves the required result without assuming the general Jordan normal form theorem.

Use the orthonormal right-handed basisDirect multiplication gives $B(r)u=u$, $B(r)v=rv+w/\sqrt{2}$ and $B(r)w=-v/\sqrt{2}+rw$. Thus the matrix in this basis isThe last two columns are orthogonal and both have squared norm $r^2+1/2$. Therefore $B(r)$ is an orthogonal matrix precisely when $r^2+1/2=1$, giving the unique positive valueIts determinant is $r_0^2+1/2=1$, so it is a proper rotation matrix, not a reflection. The transverse block has cosine and sine both $1/\sqrt{2}$. ConsequentlyWith the oriented axis $u$, the angle is positive by the right-hand rule, since $u\times v=w$. The axis also follows from the unit-eigenvalue eigenspace. As a check, $\mathrm{tr}B(r_0)=1+\sqrt{2}=1+2\cos (\pi /4)$.

For a nonzero $x$, the absolute successive-term ratio in the exponential series is $|x|/(n+1)\to 0$, so the first series converges for every $x$. For the factorial series the ratio is $(n+1)|x|\to \infty$, so its terms fail to tend to zero for every $x\ne 0$.

The third series is sparse: its exponent is $n^2$, as in the PDF. If $t_n=(n!{)}^2|x{|}^{n^2}$, thenFor $|x|>1$, the terms grow without bound; at $|x|=1$ their moduli are $(n!{)}^2$, so they again fail the term test. Equivalently, the Cauchy-Hadamard theorem for the sparse coefficients uses $(n!{)}^{2/n^2}\to 1$, not $(n!{)}^{2/n}\to \infty$. Thus the three radii of convergence areZeros at non-square coefficient indices do not change the relevant limsup in the last root test. This illustrates the radius of convergence of a sparse power series.

The Taylor theorem with Lagrange remainder says that, if $f$ has $N+1$ continuous derivatives on the interval joining $0$ and $x$, then for some $\xi$ strictly between them,More generally the expansion is about any base point, replacing $x$ by its displacement. The displayed regularity is a sufficient hypothesis for the theorem.

For $f(t)=(1+t{)}^{1/2}$ and $t>-1$, repeated differentiation givesTherefore the requested coefficients are $c_n=f^{(n)}(0)/n!$. For a fixed $0<x<1$, the remainder hasNow $|c_1|=1/2$ and $|c_{n+1}/c_n|=(n-1/2)/(n+1)<1$ for $n\ge 1$, so $|c_{N+1}|\le 1/2$. Hence $|R_N(x)|\le x^{N+1}/2\to 0$. Passing to the limit proves, rather than merely formally suggests, the binomial seriesThe restriction $x>0$ makes the remainder bound especially direct, since $1+\xi \ge 1$.

Suppose continuity at $y$ failed. The negation of the relative-domain epsilon-delta definition gives an ${\epsilon }_0>0$ such that for every $\delta >0$ there is an $x\in [a,b]$ with $|x-y|<\delta$ but $|f(x)-f(y)|\ge {\epsilon }_0$. Choosing $\delta =1/n$ produces a sequence $x_n\to y$ whose image does not converge to $f(y)$, contradicting the hypothesis. Thus $f$ is continuous at $y$.

This proves the sequential characterization of continuity in metric spaces. At $a$ or $b$, the same argument uses points only in $[a,b]$, giving the appropriate one-sided continuity automatically.

The intermediate value theorem states that a real-valued continuous function on a closed interval takes every value between its endpoint values. Explicitly, if $v$ lies between $f(s)$ and $f(t)$, there exists $u\in [s,t]$ with $f(u)=v$. No monotonicity is assumed.

If $f$ is a strictly increasing function and $x\ne y$, one of $x<y$ or $y<x$ holds. The corresponding strict inequality of function values shows that $f$ is injective. Conversely, if $f(x)<f(y)$, then $x=y$ is impossible and $x>y$ would imply $f(x)>f(y)$. ThusTogether with strict increase, this says that such a function preserves and reflects the ordering of points.

Fix $a<x<b$. Injectivity excludes $f(x)=c$ or $d$. If $f(x)<c$, the intermediate value theorem on $[x,b]$ gives a point other than $a$ with value $c$, contradicting injective function. If $f(x)>d$, the same theorem on $[a,x]$ gives a point other than $b$ with value $d$. ThereforeTo prove strict increase, take $x<y$. If $x=a$, the displayed endpoint ordering already gives $f(x)<f(y)$. Otherwise $f(a)<f(y)$, and the same interior-point argument on the subinterval $[a,y]$ yields $f(a)<f(x)<f(y)$. Hence $f$ is a strictly increasing function. This is the interval order theorem for continuous injections; the assumed endpoint order rules out strict decrease.

First prove continuity at $b$. Given $\epsilon >0$, choose $v$ with $\max (c,d-\epsilon )<v<d$. Surjectivity gives $x_v\in [a,b]$ with $f(x_v)=v$. Strict increase implies $x_v<b$. For $b-(b-x_v)<x\le b$,Thus $\delta =b-x_v$ proves left continuity at $b$. At $a$, choose $c<v<\min (d,c+\epsilon )$ and use its preimage to prove right continuity by the same ordering argument.

For $a<x_0<b$, choose values $v_{-},v_{+}$ in the range such thatTheir preimages satisfy $x_{-}<x_0<x_{+}$. If $\delta =\min (x_0-x_{-},x_{+}-x_0)$ and $|x-x_0|<\delta$, strict increase traps $f(x)$ between $v_{-}$ and $v_{+}$, so $|f(x)-f(x_0)|<\epsilon$. Therefore $f$ is continuous on the entire closed interval. This is continuity of an increasing interval surjection: a jump would omit values, contradicting the stated surjectivity.

Rolle's theorem states that, if $f$ is continuous on $[a,b]$, differentiable on $(a,b)$, $a<b$, and $f(a)=f(b)$, thenThe endpoint equality and both regularity hypotheses are part of the assertion.

The mean value theorem states that a function continuous on $[a,b]$ and differentiable on $(a,b)$, where $a<b$, has a point $\xi \in (a,b)$ such thatTo prove it using Rolle's theorem, subtract the secant line:This function has the required continuity and differentiability, with $h(a)=h(b)=0$. Rolle's theorem gives $h^{\prime }(\xi )=0$, which is exactly the claimed equation. Thus a tangent slope somewhere in the interval equals the overall secant slope.

First $g(b)\ne g(a)$: otherwise Rolle's theorem would produce a point with $g^{\prime }=0$, contrary to the hypothesis. DefineIt is continuous on $[a,b]$, differentiable inside, and vanishes at both endpoints. Rolle's theorem gives a $\xi \in (a,b)$ withThe two denominators are nonzero, so this proves Cauchy's mean value theorem:When $f(a)=g(a)=0$, apply that theorem on $[a,x]$ for each $a<x\le b$. Rolle's theorem again ensures $g(x)\ne 0$, and some ${\xi }_x\in (a,x)$ satisfies $f(x)/g(x)=f^{\prime }({\xi }_x)/g^{\prime }({\xi }_x)$. As $x\downarrow a$, the trapped point ${\xi }_x$ also tends to $a$. ThereforeThis proves the stated endpoint case of L'Hôpital's rule. It does not assume continuity of the derivatives; only the indicated derivative-ratio limit is used. The same trapping argument also works for an extended infinite limit if that convention is allowed.

Set $F(h)=f(a+h)+f(a-h)-2f(a)$ and $G(h)=h^2$. Both vanish at zero. For $h\ne 0$, their derivative ratio isTwice differentiability at $a$ makes both quotients tend to $f^{\prime \prime }(a)$. Apply the endpoint L'Hôpital's rule proved in part (iii) for $h\downarrow 0$. For the other side use the reflected positive variable $t=-h$; $F$ and $G$ are even, so their quotient is unchanged. Thus the two-sided limit isThis is the second-order central difference limit. The proof only uses differentiability of $f^{\prime }$ at $a$ and differentiability nearby; it does not incorrectly assume $f^{\prime \prime }$ is continuous.

For a partition $D=\{a=x_0<x_1<\cdots <x_n=b\}$, put $\Delta x_k=x_k-x_{k-1}$ andBoundedness makes these finite. The lower Darboux sum and upper Darboux sum areSince $m_k\le M_k$ and the widths are positive, $s(f,D)\le S(f,D)$.

Splitting a partition interval into smaller intervals can only increase each infimum and decrease each supremum. The smaller widths sum to the original width. Its new lower contribution is therefore at least its old lower contribution, and its new upper contribution at most its old upper contribution. Repeating this for every inserted point proves Darboux sum refinement monotonicity:For arbitrary partitions, take their common partition refinement $D_{\ast }=D_1\cup D_2$. ThenNo compatibility of the original partitions is required.

Finally suppose $f\ge 0$ is Riemann integrable. Then $t_k=m_k\Delta x_k\ge 0$, so every product factor is nonnegative and the exponential inequality can be multiplied safely:A lower Darboux sum is no greater than the Riemann integral, since the integral equals the supremum of all lower sums. Monotonicity of the exponential therefore gives the exponential bound for a lower-sum productFor a degenerate interval $a=b$, the empty product and the exponential are both one.