Past exam of the mathematics course of the University of Oxford

Source: released examination PDF, pages 180–184.

Solutions cover all seven questions, including every optional question. The module label is I, with M1 used for Mathematics and Computer Science; the formal paper code is A10138W1. Throughout Question 4, diagonalisable matrices are understood over the real numbers.

The three elementary row operations on an $m\times n$ real matrix are:

Each operation changes whole rows, so it acts on every column by the same rule. Each can be undone by an elementary row operation.

For an $m\times n$ matrix, the corresponding elementary matrices are $m\times m$, because the operation is implemented by left matrix multiplication. Apply the desired elementary row operation to the identity matrix $I_m$. Writing $E_{ij}$ for the matrix unit with its only nonzero entry, $1$, in position $(i,j)$ gives:Indeed, these matrix products interchange rows $i,j$, scale row $i$, and add $c$ times row $j$ to row $i$, respectively. The displayed inverses undo precisely those operations. Algebraically, $E_{ij}^2=0$ when $i\ne j$, so $(I_m+c{E}_{ij})(I_m-c{E}_{ij})=I_m$; the other two inverse identities follow immediately from their row actions. Thus every elementary matrix is an invertible matrix.

Perform the elementary row operations $R_2\leftarrow R_2+2R_1$ and $R_3\leftarrow R_3-R_1$, then $R_2\leftarrow R_2/2$, $R_1\leftarrow R_1-R_2$, and finally $R_1\leftarrow R_1+R_3$, $R_2\leftarrow R_2-3R_3$:Consequently the reduced row echelon form is $I_3$. Applying the same operations to the augmented column $b=(b_1,b_2,b_3{)}^T$ givesThus every $b\in {\mathbb{R}}^3$ admits exactly one solution. This follows because the elementary row operations preserve the solution set of the augmented linear system, and the reduced coefficient matrix is the identity matrix.

If $A$ is a strictly upper triangular matrix, then $A_{ij}=0$ unless $j-i\ge 1$. We prove by mathematical induction thatThe assertion for $k=1$ is the definition. In the matrix multiplication formulaa nonzero summand would require $\ell -i\ge k$ and $j-\ell \ge 1$, hence $j-i\ge k+1$. This proves the induction step. Since $j-i\le n-1$ for all entries, $\boxed{A^n=0}$. In particular, every strictly upper triangular matrix is a nilpotent matrix.

Write $A=I_3+N$, whereThe binomial theorem for commuting matrices applies because $I_{3}N=N{I}_3$. All terms of degree at least three vanish, so for every positive integer $n$,The same expression directly gives $A$ when $n=1$, so no small exponent is excluded.

A vector space over a field $\mathbb{F}$ is a set $V$ with vector addition $V\times V\to V$ and scalar multiplication $\mathbb{F}\times V\to V$ satisfying the following vector space axioms. Under vector addition, $V$ is an abelian group: addition is associative and commutative, there is a zero vector $0_V$, and each $v$ has an additive inverse $-v$. For all $a,b\in \mathbb{F}$ and $u,v\in V$,The operations are defined for every indicated pair and take their values in $V$.

A map $T:V\to W$ between vector spaces over the same field $\mathbb{F}$ is a linear map precisely when it preserves vector addition and scalar multiplication:Equivalently, $T(au+bv)=aT(u)+bT(v)$ for all $u,v\in V$ and $a,b\in \mathbb{F}$.

Every $v\in V$ has a unique basis expansion $v={\sum }_{i=1}^n{a}_i{v}_i$. Define the linear functionalUniqueness of the coordinates makes this definition well defined. The coordinates of a sum or a scalar multiple are the corresponding sums or scalar multiples of the coordinates, so this formula defines a linear map. It has $T(v_i)={\mu }_i$. Conversely, any linear map with those values must satisfy the same formula by linearity, proving uniqueness.

If the finite field $\mathbb{F}$ has $q$ elements, each of the $n$ values ${\mu }_i$ can be chosen independently in $q$ ways. The number of linear maps $V\to \mathbb{F}$ is therefore $\boxed{q^n}$, including the zero linear map.

Use basis extension to choose a basis $(v,v_2,\dots ,v_n)$ of the vector space $V$ over the finite field ${\mathbb{F}}_p={\mathbb{Z}}_p$. The condition $T(v)=0$ fixes the first value of a linear functional; its remaining $n-1$ values are arbitrary. There are $p^{n-1}$ such linear maps, exactly one of which is zero. Hence the required number isFor $n=1$ this is zero, as it should be: vanishing at a basis vector then forces the entire linear functional to vanish.

Put $L=\mathrm{span}\{v\}$. Every two-dimensional vector subspace containing $v$ is $W=\mathrm{span}\{v,w\}$ for some $w\notin L$. There are $p^n-p$ choices for $w$ in $V$. Within any one such $W$, exactly $p^2-p$ choices of $w\in W\setminus L$ yield that same $W$: each forms a linearly independent pair with $v$, and that pair is a basis of $W$.

These sets of choices partition $V\setminus L$, because $w$ determines $\mathrm{span}\{v,w\}$ uniquely. Thus the number isEquivalently these vector subspaces correspond to the one-dimensional vector subspaces of the quotient vector space $V/L$. For $n=1$ there are none and the formula gives zero.

If $T^{\prime }=\lambda T$ with $\lambda \ne 0$, then $T^{\prime }(x)=0$ if and only if $T(x)=0$, so their kernels agree. Conversely, suppose both nonzero linear functionals have kernel $K$. Choose $u$ with $T(u)=1$, by scaling a vector on which $T$ is nonzero. For each $x\in V$,Therefore $T^{\prime }(x)=T(x)T^{\prime }(u)$. Moreover $T^{\prime }(u)\ne 0$, since $u\notin K$. Thus $\boxed{T^{\prime }=T^{\prime }(u)T}$, with a nonzero scalar.

Every nonzero linear functional $V\to {\mathbb{F}}_p$ is surjective, so its kernel has dimension $n-1$ by the rank-nullity theorem. Conversely, every hyperplane $K$ is such a kernel: extend a basis of $K$ by one vector $u$, and assign value zero on that basis and value one on $u$. Hence the hyperplanes containing $v$ are exactly the kernels of the $p^{n-1}-1$ nonzero linear functionals counted above. Each kernel occurs for exactly $p-1$ of them, its distinct nonzero scalar multiples. The required number is

For the linear map $T_A:x\mapsto Ax$ on the finite-dimensional vector space ${\mathbb{R}}^n$, the rank-nullity theorem implies that injectivity and surjectivity are equivalent. Consequently $T_A$ is invertible if and only if $\ker T_A=\{0\}$.

Using the permitted equivalence between invertibility and a nonzero determinant, we obtain

We use the monic polynomial convention for the characteristic polynomial of an $n\times n$ matrix:It has degree $n$, since the only contribution to the coefficient of $t^n$ in the determinant is the product of the $n$ diagonal terms $t$. The alternative convention $\det (A-t{I}_n)=(-1{)}^n{\chi }_A(t)$ has the same polynomial roots.

A scalar $\lambda$ is an eigenvalue of $A$ if and only if there is a nonzero vector $v$ with $Av=\lambda v$. By the preceding kernel criterion,The last condition is ${\chi }_A(\lambda )=0$, exactly the definition of a polynomial root. For a real matrix, this proves the assertion for real eigenvalues; the same proof over the complex numbers gives the usual complex version.

Write $B=[b_1,\dots ,b_n]$. Since $AB=[A{b}_1,\dots ,A{b}_n]$ and $b\mapsto Ab$ is a linear map, the multilinearity of the determinant gives, for any column position $j$,If $b_i=b_j$ for $i\ne j$, the corresponding columns $A{b}_i,A{b}_j$ also agree, so $D(B)=0$. Thus $D$ is an alternating multilinear map of the columns of $B$, even when $A$ is not invertible.

We have $D(I_n)=\det A$. Define a function of the columns of $B$ byIt is an alternating multilinear map, because both summands are, and $F(I_n)=\det A+1-\det A=1$. Hence $F$ is a normalized determinantal function. By the asserted uniqueness of the determinant, $F(B)=\det B$ for every $B$. Rearranging yieldsThis argument also covers $\det A=0$ without dividing by it.

Take the nonzero vector $1=(1,\dots ,1{)}^T$. Its $i$th image entry under matrix multiplication is the sum of row $i$:Thus $A1=\lambda 1$, exhibiting $1$ as an eigenvector with eigenvalue $\boxed{\lambda }$.

Yes. The sums of the columns of $A$ are the sums of the rows of its transpose $A^T$. By the previous argument, $A^{T}1=\lambda 1$, so $\det (\lambda I_n-A^T)=0$. The determinant is unchanged by transpose, givingTherefore $\boxed{\lambda \text{ is an eigenvalue of }A}$. The vector $1$ need not itself be an eigenvector of $A$ in the column-sum case.

If $A$ is an invertible matrix, thenIf instead $B$ is an invertible matrix, thenThus in either case $AB$ and $BA$ are similar matrices. Explicitly, whenever $Y=P^{-1}XP$ and $Xu=\lambda u$ with $u\ne 0$, one has $Y(P^{-1}u)=\lambda P^{-1}u$ and $P^{-1}u\ne 0$. Applying the same argument with $P^{-1}$ in place of $P$ proves equality of the sets of eigenvalues, including zero.

The same matrix similarity preserves being a diagonalisable matrix. If $S^{-1}(AB)S=D$ is a diagonal matrix, thenTherefore $BA$ is a diagonalisable matrix whenever $AB$ is, and the converse follows by interchanging $A,B$. Thus they are either both diagonalisable matrices or neither is. In fact the previous part shows that one invertible factor suffices.

The real spectral theorem states that a symmetric matrix has an orthonormal basis of real eigenvectors, and hence is a diagonalisable matrix. Here is a proof in this setting.

For $n\ge 1$, the quadratic form $q(x)=x^{T}Ax$ attains a maximum on the unit sphere, by compactness and the extreme value theorem. Choose a unit maximizer $u$ and put $\lambda =u^{T}Au$. For any $w\perp u$, the Rayleigh quotient along $u+tw$ has a maximum at $t=0$, soThe last equality uses $A=A^T$ and $u^{T}w=0$. Thus $Au$ is orthogonal to every $w\perp u$, so $Au=\lambda u$.

The orthogonal complement $u^{\perp }$ is an invariant subspace, because for $x\perp u$,The restriction of $A$ to $u^{\perp }$ is again symmetric with respect to the induced inner product. By mathematical induction on dimension, it has an orthonormal basis of eigenvectors; adjoining $u$ gives one for ${\mathbb{R}}^n$. If $Q$ has those basis vectors as columns, then $Q^{T}AQ$ is a real diagonal matrix and $Q^{-1}=Q^T$.

Let $A$ be a skew-symmetric matrix. For every real vector $x$, the real scalar $x^{T}Ax$ equals its own transpose, butHence $x^{T}Ax=0$. If $Av=\lambda v$ is a real eigenvector equation with $v\ne 0$, it follows thatso $\lambda =0$. If $A$ is a diagonalisable matrix over $\mathbb{R}$, it has a real basis of eigenvectors, all with eigenvalue zero. Thus $A$ vanishes on a basis and $\boxed{A=0_n}$.

The field matters: a nonzero real skew-symmetric matrix can be a diagonalisable matrix over the complex numbers, for example $\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)$ with eigenvalues $i,-i$.

The matrix units $E_{ij}$, $1\le i,j\le n$, form a basis of $M_n(\mathbb{R})$: each matrix has the unique expression $A={\sum }_{i,j}{a}_{ij}{E}_{ij}$. There are $n^2$ of them, so

Take the vector subspace of skew-symmetric matrices,It is closed under vector addition and scalar multiplication, and a basis isIndeed, its diagonal entries vanish, and its entries below the diagonal are forced by those above it. Hence $\boxed{\dim K=\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$. Part (a)(ii) proves that the only diagonalisable matrix in $K$ is $0_n$.

Let $S$ be the vector subspace of symmetric matrices. A basis consists of $E_{ii}$ for $1\le i\le n$ and $E_{ij}+E_{ji}$ for $i<j$, soThe dimension formula for a sum of subspaces now givesChoose $0\ne A\in V\cap S$. It belongs to $V$ and is a symmetric matrix, so part (a)(i) makes it a diagonalisable matrix. The preceding example shows that the strict threshold is sharp.

Write $r=(r_1,\dots ,r_n{)}^T$. The linear map represented by $A$ has the formThe image of a linear map here is contained in the one-dimensional linear span of $e_i$, so its matrix rank is at most one. The rank-nullity theorem yieldsThus the solution space of $Ax=0$, namely the zero eigenspace when zero is an eigenvalue, contains at least $n-1$ linearly independent vectors. If $r=0$ its dimension is $n$; otherwise it is $n-1$. When $n=1$ the asserted lower bound is zero, even if zero is not an eigenvalue.

Since $A{e}_i=r_i{e}_i$, the vector $e_i$ is an eigenvector with nonzero eigenvalue $r_i$. The assumption $r_i\ne 0$ also makes $r\ne 0$, so the kernel has dimension $n-1$. Choose its basis $u_1,\dots ,u_{n-1}$.

The vector $e_i$ is outside this kernel. Hence $(u_1,\dots ,u_{n-1},e_i)$ is a basis of ${\mathbb{R}}^n$ consisting of eigenvectors, with corresponding eigenvalues $0,\dots ,0,r_i$. In that basis, $A$ is the diagonal matrixThis proves that $A$ is a diagonalisable matrix, including the case $n=1$.

Yes. Consider the following $n^2$ matrices:Each has only row $i$ nonzero and has $i$th diagonal entry $1$, so part (c)(ii) proves that it is a diagonalisable matrix. The collection is a spanning set, because it contains every $E_{ii}$ andThus it spans the matrix unit basis. A spanning set of $n^2$ vectors in an $n^2$-dimensional vector space is a basis. Alternatively, in a vanishing linear combination of $\mathcal{B}$, each off-diagonal entry first forces its own coefficient to be zero, and then each diagonal entry forces the remaining coefficient to be zero.

In the finite field ${\mathbb{Z}}_3=\{0,1,2\}$, perform ordinary addition and multiplication and then take the remainder modulo $3$. The tables areThe nonzero elements have multiplicative inverses $1^{-1}=1$ and $2^{-1}=2$.

Parametrize the matrices byDirect matrix multiplication givesThis proves closure. The identity matrix is $h(0,0,0)$, and the formulagives both a left and a right inverse, as substitution in the product formula verifies. Thus each element is an invertible matrix, and the subgroup test shows that $H$ is a subgroup of ${\mathrm{GL}}_3({\mathbb{Z}}_3)$. It is the unitriangular group ${\mathrm{UT}}_3({\mathbb{F}}_3)$ and has $3^3=27$ elements.

The identity is the identity matrixLeft or right matrix multiplication by it preserves every entry, as is also immediate from the product formula above.

Take $x=h(1,0,0)=I_3+E_{12}$ and $y=h(0,0,1)=I_3+E_{23}$. Their matrix products areThey differ in the $(1,3)$ entry because $E_{12}{E}_{23}=E_{13}$ whereas $E_{23}{E}_{12}=0$. Therefore $xy\ne yx$, and $\boxed{H\text{ is a non-abelian group}}$.

If $G$ is an abelian group, its elements commute, so for all $x,y\in G$,Thus $\boxed{T\text{ is a group homomorphism}}$. Also $T(e)=e^3=e$, as required.

Use the symmetric group $S_3$, composing permutations from right to left. Set $x=(12)$ and $y=(23)$. Each is a transposition, so $x^3=x$ and $y^3=y$, whereas $xy=(123)$ has order of a group element three. ConsequentlyThus the cubing map on $S_3$ is not a group homomorphism.

Assume $T$ is a group homomorphism. For any $a,b\in G$, expanding $(ab{)}^3=a^3{b}^3$ and cancelling the initial $a$ and final $b$ gives the useful identityWe also need a consequence of compatibility with conjugation. Calculate the cube of $gz{g}^{-1}$ in two ways:Cancelling shows $g^2{z}^3=z^3{g}^2$. Thus the square of every element of $G$ commutes with every element of the image of a group homomorphism $J=T(G)$.

Now take any $x,y\in J$. In particular $x^{2}y=y{x}^2$. Applying (1) to $x,y$ and then using this commutation givesThis proves the abelian image of a cubing homomorphism property. Since the image of a group homomorphism is a subgroup, $\boxed{T(G)\text{ is an abelian group}}$.

If $T$ is a surjective group homomorphism, then $G=T(G)$, which is an abelian group by the preceding part.

If $T$ is an injective group homomorphism, then for all $a,b\in G$,because $T(a),T(b)$ lie in the abelian group $T(G)$. Injectivity gives $ab=ba$. Hence $\boxed{G\text{ is abelian in either case}}$.

Yes: use the non-abelian group $H$ from part (a). Every element is $I_3+N$ for a strictly upper triangular matrix $N$ with $N^3=0$. In the finite field ${\mathbb{Z}}_3$, the binomial theorem for commuting matrices givesThus $\boxed{T(h)=I_3\text{ for all }h\in H}$. This constant identity-valued map is a group homomorphism, since $T(xy)=I_3=T(x)T(y)$. Part (a)(iv) already proves that $H$ is not an abelian group. Here $T$ is neither injective nor surjective, consistently with the preceding part.

The set $S_n$ is nonempty because $n\in S_n$. By the well-ordering principle for the natural numbers, it has a least element $p$. In particular $p>1$ and $p$ divides $n$.

If $p$ were not a prime number, it would have a positive integer divisor $d$ with $1<d<p$. Since $d$ divides $p$ and $p$ divides $n$, divisibility is transitive and $d$ divides $n$. This would put $d$ in $S_n$, contradicting the minimality of $p$. Hence $\boxed{p\text{ is prime}}$.

Neither $1$ nor $-1$ is divisible by a prime number, so both lie outside $U$. On the other hand, $0\in 2\mathbb{Z}\subseteq U$. If an integer $z$ has $|z|>1$, part (a)(i) supplies a prime number $p$ dividing the positive integer $|z|$; the same $p$ divides $z$, so $z\in p\mathbb{Z}\subseteq U$. These cases exhaust $\mathbb{Z}$, proving