Past exam of the mathematics course of the University of Oxford / 2014 / Prelims / Mathematics I (4243, I, M1)

Solutions to all seven questions of the University of Oxford undergraduate Prelims Mathematics I examination, sat on 23 June 2014. The cover also identifies the shared mathematics and computer science paper as M1. Source: released examination archive, member FOI-20210708-1 - Data/4243.pdf, printed pages 1–4. Question statements are omitted. A bounded exact-paper availability check found no advertised full or partial answers; the published even-year policy explicitly establishes coverage back to at least 2016, rather than establishing this 2014 paper's availability.

For a finite set $S=\{s_1,\dots ,s_k\}$ of vectors in a real vector space, its span is the set of all linear combinations:The span of the empty set is $\{0\}$. The set $S$ is linearly independent if ${\sum }_i{a}_i{s}_i=0$ implies $a_i=0$ for every $i$. It is a spanning set for $V$ if $\mathrm{Sp}(S)=V$. A basis is both a linearly independent set and a spanning set.

For basis extension, start with the given linearly independent set. If it does not span $V$, choose $v\notin \mathrm{Sp}(S)$ and adjoin it. The enlarged set remains linearly independent: a relation $av+{\sum }_i{a}_i{s}_i=0$ with $a\ne 0$ would express $v$ as a linear combination of $S$, a contradiction; if $a=0$, independence of $S$ forces all other coefficients to be zero.

Repeat whenever the current span is proper. Each step increases the set's size by one, while the allowed bound says its size cannot exceed $\dim V$. Thus the process terminates with a linearly independent set spanning $V$, hence a basis containing the original set. This also covers an initially empty set and the zero-dimensional vector space.

Choose a basis $u_1,\dots ,u_r$ of $U$, extend it to a basis $u_1,\dots ,u_r,w_1,\dots ,w_s$ of $W$, and extend again to a basis of $V$ by adding $v_1,\dots ,v_t$. DefineEvery member of the full basis lies in $W$ or $W^{\prime }$, so the sum of vector subspaces is $W+W^{\prime }=V$. If $x\in W\cap W^{\prime }$, express it in both displayed bases. Uniqueness of the coordinates in the full basis forces its $w_j$ and $v_j$ coefficients to vanish. Thus $x\in U$. The reverse inclusion is built into the construction, proving $W\cap W^{\prime }=U$. This is a subspace supplement with a prescribed intersection.

For the matrix example, letThe skew-symmetric matrices are exactly $U=\mathrm{span}\{J\}$, and the traceless matrices form $W$. A suitable answer isThe matrix trace of $aI+bJ$ is $2a$, so $W\cap W^{\prime }=\mathrm{span}\{J\}=U$. Every $2\times 2$ real matrix has the decompositionwhose first term lies in $W$ and second in $W^{\prime }$. Therefore $W+W^{\prime }=M_2(\mathbb{R})$, as required.

For a linear map $T:V\to V$, its kernel of a linear map and image of a linear map areIts nullity of a linear map is $n(T)=\dim \ker T$, and its rank of a linear map is $r(T)=\dim \mathrm{im}T$.

Choose a basis $u_1,\dots ,u_k$ of $\ker T$ and extend it to a basis $u_1,\dots ,u_k,v_1,\dots ,v_m$ of $V$. The vectors $T(v_1),\dots ,T(v_m)$ span $\mathrm{im}T$, because applying $T$ to an arbitrary linear combination of the full basis eliminates the $u_i$ terms. They are also linearly independent: if ${\sum }_j{b}_{j}T(v_j)=0$, then ${\sum }_j{b}_j{v}_j\in \ker T$, so ${\sum }_j{b}_j{v}_j={\sum }_i{a}_i{u}_i$ for some coefficients. Independence of the extended basis forces all $a_i,b_j$ to vanish.

Consequently $r(T)=m$, $n(T)=k$ and $\dim V=k+m$. This proves the rank-nullity theorem:

Restrict $S$ to the vector subspace $W=\mathrm{im}T$. This restriction has kernel of a linear map $W\cap \ker S$ and image of a linear map $S(W)=\mathrm{im}(ST)$. The rank-nullity theorem on $W$ therefore givesApply the rank-nullity theorem to $T$ and $ST$ on $V$ to obtain the exact nullity of a composition identity:Since the intersection is a vector subspace of $\ker S$, its dimension is at most $n(S)$. Hence

The image of a linear map $\mathrm{im}(ST)=S(\mathrm{im}T)$ lies inside $\mathrm{im}S$. Therefore $r(ST)\le r(S)$. Also $S$ restricted to $\mathrm{im}T$ cannot have rank of a linear map greater than its domain's dimension, so $r(ST)\le \dim \mathrm{im}T=r(T)$. ThusEquivalently, apply the rank-nullity theorem to that restriction: $r(ST)=r(T)-\dim (\mathrm{im}T\cap \ker S)\le r(T)$. This proof keeps track of the intermediate vector subspace, rather than assuming an invertible factor.

An elementary row operation is one of three operations: interchange two rows, multiply one row by a nonzero scalar, or add a scalar multiple of one row to a different row. Each operation is reversed by another operation of the same kind.

Performing such an operation on an $m\times n$ matrix $A$ is equivalent to left multiplication by the $m\times m$ elementary matrix obtained by applying that operation to the identity matrix. Each elementary matrix is invertible, with inverse corresponding to the reverse operation. Thus a sequence of operations givesFor square matrices, if $A$ were invertible, then $B=PA$ would have inverse $A^{-1}{P}^{-1}$. Hence if $B$ is singular, $A$ must be singular as well. In fact the two are invertible together, because $A=P^{-1}B$ gives the converse.

Solve $Ax=b$ for a general right-hand side $b=(b_1,b_2,b_3,b_4{)}^T$. Subtracting the fourth equation from the second gives $x_3=b_2-b_4$. The first and fourth then giveSubstitution into the third equation reduces the remaining condition toIf $t\ne 2$, every right-hand side therefore has a unique solution, and collecting its four coefficients yields the matrix inverseFor $t=2$, the nonzero vector $(-1,-1,0,1{)}^T$ lies in the kernel of a linear map represented by $A$, so $A$ is singular. Hence $A$ is invertible exactly when $t\ne 2$. The same calculation gives $\det A=t-2$; the formula above can also be checked by multiplying its numerator by $A$ to obtain $(t-2)I$.

A real number $\lambda$ is an eigenvalue of $A$ if there is a nonzero vector $v$ with $Av=\lambda v$; such a $v$ is an eigenvector for $\lambda$. The nonzero condition is essential.

For distinct eigenvalues ${\lambda }_1,\dots ,{\lambda }_r$, choose corresponding nonzero eigenvectors $v_1,\dots ,v_r$. Prove their linear independence by induction on $r$. The claim for one vector is immediate. Given a relation ${\sum }_{i=1}^r{a}_i{v}_i=0$, apply $A-{\lambda }_{r}I$ to getBy the induction hypothesis, every coefficient here is zero. Distinctness gives $a_i=0$ for $i<r$, and the original relation then gives $a_r=0$ since $v_r\ne 0$. Thus the eigenvectors are linearly independent.

With $n$ distinct real eigenvalues, the $n$ real eigenvectors form a basis of ${\mathbb{R}}^n$. Put them into the columns of $P$. Then $P$ is invertible andThis proves diagonalizability directly.

Suppose $A^T=A$. For eigenvectors $v_i,v_j$ with distinct real eigenvalues, symmetry givesThus $({\lambda }_i-{\lambda }_j)v_i^T{v}_j=0$, and the eigenvectors are orthogonal. Divide each by its nonzero Euclidean norm to obtain an orthonormal basis. The matrix $P$ having these normalized columns satisfies $P^{T}P=I$, so it is an orthogonal matrix and $P^{-1}=P^T$. As in part (a),This proves the needed orthogonal diagonalization from symmetry and distinct eigenvalues, without invoking an unproved spectral theorem.

For the given symmetric matrix, $(1,1{)}^T$ is an eigenvector with eigenvalue $1$, and $(1,-1{)}^T$ is an eigenvector with eigenvalue $27$. Normalize them to obtainTake the real cube roots of the two diagonal entries and transform back:It is a real symmetric matrix, and $C^3=P\mathrm{diag}(1,27)P^T=A$ because $P^{T}P=I$. Direct multiplication also gives $C^2=\left(\begin{array}{cc}5& -4\\ -4& 5\end{array}\right)$ and then $C^3=\left(\begin{array}{cc}14& -13\\ -13& 14\end{array}\right)$.

Among the $|G|+1$ powers $e,g,g^2,\dots ,g^{|G|}$ in the finite group $G$, the pigeonhole principle forces two to be equal: $g^i=g^j$ with $0\le i<j\le |G|$. Multiply by $g^{-i}$ to obtainThis proves the existence of a positive power equal to the identity element, without presupposing the order of a group element.

The order of a group element $o(g)$ is the least positive integer $n$ for which $g^n=e$, whose existence follows from part (i). If $g^k=e$, use the Euclidean division to write $k=qn+r$, where $0\le r<n$. ThenMinimality of $n$ forces $r=0$. ThusThe argument also works for negative $k$, using integer powers and the same remainder convention.

Lagrange's theorem states that for a subgroup $H$ of a finite group $G$,where $[G:H]$ is the index of a subgroup, the number of its left cosets. In particular, $|H|$ divides $|G|$.

The cyclic subgroup $⟨g⟩$ consists of the distinct elements $e,g,\dots ,g^{n-1}$, where $n=o(g)$. Every power reduces to one of these by the Euclidean division, and a repetition among them would contradict minimality of $n$. Thus $|⟨g⟩|=o(g)$. Applying Lagrange's theorem gives

Let $n=o(g)$. A group homomorphism preserves powers and the identity element, soThe preceding divisibility property givesNow assume $\varphi$ is surjective and choose $h\in H$ of order $m$. Take a preimage $g$ of $h$, and write $o(g)=mr$, as the divisibility result permits. The element $g^r$ has order exactly $m$: its $m$th power is $e$, while $(g^r{)}^s=e$ implies $mr\mid rs$, hence $m\mid s$. Therefore $G$ contains an element of order $m$, namely $g^r$.

The preimage $g$ itself need not have order $m$; taking the suitable power is the essential step. The constructed element need not map to the original $h$. This proves that element orders in a finite quotient occur in the original group.

A group homomorphism from an additive cyclic group ${\mathbb{Z}}_n$ is determined by the image $a$ of $1$, subject exactly to $a^n=e$ in multiplicative notation, or $na=0$ in an additive target.

For ${\mathbb{Z}}_{18}\to {\mathbb{Z}}_{15}$, the relation is $18a\equiv 0(\mathrm{mod}15)$, equivalently $3a\equiv 0(\mathrm{mod}15)$. The possibilities are $a=0,5,10$, and each defines a homomorphism between cyclic groups. Thus there are three such maps, an instance of the number of homomorphisms between finite cyclic groups.

For ${\mathbb{Z}}_9\to S_4$, the image of $1$ must be a permutation whose order of a group element divides $9$. A permutation on four symbols can have order $1,2,3$ or $4$, so the allowed images are the identity and the three-cycles. There are $\left(\genfrac{}{}{0ex}{}{4}{3}\right)(3-1)!=8$ three-cycles: choose their three symbols and one of the two cyclic orientations. Hence there are nine maps.

Finally, each transposition in $S_5$ has order $2$, so its image in ${\mathbb{Z}}_5$ must have order dividing both $2$ and $5$, and is therefore the identity. Every permutation is a product of transpositions, so every element must map to the identity. There is one map. In the order asked, the counts are

A subgroup $N$ of $G$ is a normal subgroup if conjugation by every element preserves it:Equivalently, $gN=Ng$ for every $g\in G$. Here equality means equality of sets; it does not require each individual element of $N$ to commute with every element of $G$.

The center of a group consists of its elements commuting with every element. First check it is a subgroup. The identity element is central. If $a,b\in Z(G)$ and $x\in G$, then $b^{-1}$ commutes with $x$ andThus $a{b}^{-1}\in Z(G)$, proving closure under the subgroup criterion. Moreover, if $z\in Z(G)$, then $xz{x}^{-1}=z$ for every $x\in G$. Hence conjugation fixes the center elementwise, soTherefore the center of a group is a normal subgroup.

If $g\in Z(G)$, it commutes with each $x\in G$, so $x^{-1}gx=g$. Its conjugacy class is therefore $C(g)=\{g\}$.

Conversely, if $C(g)=\{g\}$, then $x^{-1}gx=g$ for every $x$. Multiplication by $x$ on the left gives $gx=xg$ for every $x$, which is exactly membership in the center of a group. Thus

Conjugation of a permutation relabels each symbol by the inverse conjugating permutation. Specifically,To verify the direction of the inverse, apply the left side to ${\tau }^{-1}(a_j)$: $\tau$ first takes it to $a_j$, the original cycle takes it to $a_{j+1}$, and ${\tau }^{-1}$ takes it to ${\tau }^{-1}(a_{j+1})$, with cyclic indexing. Any symbols fixed by the original permutation are similarly relabelled and remain fixed. More generally, conjugate every cycle of a disjoint-cycle decomposition in this way; disjointness is preserved because ${\tau }^{-1}$ is a bijection.

By the preceding relabelling formula, every conjugate of $(123)$ is a three-cycle, and any three-cycle on four symbols can be obtained by a suitable relabelling. ThereforeThere are eight elements, agreeing with the count $\left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot 2$.

Likewise, conjugation preserves the pattern of two disjoint transpositions, and every partition of four symbols into two pairs is realized by relabelling. ThusThese have the respective cycle types $(3,1)$ and $(2,2)$ in the symmetric group $S_4$.

Suppose $\sigma \ne e$. Choose a symbol $i$ moved by $\sigma$ and write $j=\sigma (i)\ne i$. Since $n\ge 3$, choose a third symbol $k$ distinct from $i,j$. Let $\tau =(jk)$, a transposition that fixes $i$. ThenThus ${\tau }^{-1}\sigma \tau \ne \sigma$, proving that the conjugacy class of any nonidentity permutation has more than one element. By part (a)(iii), no such permutation lies in the center of a group. The identity always does, soThe restriction on $n$ is necessary: $S_2$ is an abelian group and equals its own center.

A left group action of $G$ on a set $S$ is a function $\varphi :G\times S\to S$ satisfyingfor all $s\in S$ and $g,h\in G$. Writing $g\cdot s=\varphi (g,s)$, these are $e\cdot s=s$ and $(gh)\cdot s=g\cdot (h\cdot s)$. No commutativity is assumed, so the order of composition matters.

The group action law givesThus ${\varphi }_g$ is a bijection with inverse ${\varphi }_{g^{-1}}$, hence a permutation of $S$. Also, for every $s$,Therefore the assignment $\Phi (g)={\varphi }_g$ takes values in the symmetric group $\mathrm{Sym}(S)$ and satisfiesIt is a group homomorphism, with the group product on the right interpreted as composition of permutations.

Define $g\cdot (g_{1}H)=(g{g}_1)H$ on the set of left cosets. It is well-defined: if $g_{1}H=g_{2}H$, then $g_2=g_{1}h$ for some $h\in H$, so $(g{g}_2)H=(g{g}_{1}h)H=(g{g}_1)H$. The identity fixes each coset, and associativity in $G$ givesHence this is a left group action, and part (a) supplies its group homomorphism $\Phi :G\to \mathrm{Sym}(S)$.

An element of the kernel of a group homomorphism $\Phi$ fixes every coset, in particular $H$ itself. Thus $g\in \ker \Phi$ implies $gH=H$, which implies $g\in H$. ThereforeThe subgroup symbol is justified because a kernel of a group homomorphism is a subgroup, and the argument proves containment.

By Lagrange's theorem, the index of a subgroup is $[G:H]=75/25=3$. Thus the set of left cosets has three elements, and the preceding group action yields a group homomorphism $\Phi :G\to S_3$ after labelling them.

Its image is a subgroup of $S_3$, so its order divides $6$. By the first isomorphism theorem, $|\mathrm{im}\Phi |=|G|/|\ker \Phi |$ also divides $75$. Hence its order divides $\gcd (6,75)=3$, giving possibilities $1$ and $3$. The action on cosets is transitive: $g_2{g}_1^{-1}$ sends $g_{1}H$ to $g_{2}H$. It cannot be the trivial action on a three-element set, so the image does not have order $1$. ThereforeIt follows that $|\ker \Phi |=75/3=25$. Part (b)(i) gives $\ker \Phi \le H$, and $|H|=25$; equal finite orders force equality. A kernel of a group homomorphism is a normal subgroup, soThis is an instance of the fact that a subgroup of index the smallest prime divisor is normal.