Past exam of the linear algebra course of the University of Oxford

Solutions to all three questions of the University of Oxford Part A linear algebra paper, sat on 20 June 2023. Source: released examination PDF, parent PDF pages 258–260; paper pages 1–3. Question labels follow the paper; the solutions supply their own reasoning. Part 2(c) includes the exceptional case of characteristic of a field three because that part does not specify its field separately.

The primary decomposition theorem for linear maps starts with a linear map $T:V\to V$ on a finite-dimensional vector space over a field $F$. Factor its minimal polynomial aswhere the $p_j$ are distinct monic polynomials that are irreducible polynomials and $a_j\ge 1$. Define $V_j=\ker p_j(T{)}^{a_j}$. ThenThus the direct sum separates the irreducible polynomial factors into uniquely determined invariant subspaces. The statement works even when the minimal polynomial does not split into linear polynomials over $F$.

All calculations here take place in the finite field $F={\mathbb{F}}_3$. For the given matrix $S$, its characteristic polynomial isThe values $q(0),q(1),q(2)$ are $2,2,1$, so this quadratic polynomial has no polynomial root in $F$ and is an irreducible polynomial. Direct calculation givesNeither $S$ nor $q(S)$ is zero. The Cayley-Hamilton theorem says that the minimal polynomial divides $xq(x)$; its proper monic polynomial divisors cannot annihilate $S$, so $m_S=xq$.

The two kernels give the required primary decomposition theorem for linear maps explicitly:The determinant of the matrix with these three basis vectors as columns is $1$ in $F$, proving $W=W_1\oplus W_2$. To check these are invariant subspaces, writing $u=(1,2,0{)}^T$ and $z=(0,0,1{)}^T$ gives $Su=u+2z$ and $Sz=2u$. Hence the matrix of the restriction to $W_2$ in the basis $(u,z)$ iswith minimal polynomial $q$; the nonzero vector space $W_1$ has zero restriction and minimal polynomial $x$.

The dual space is the vector space of all linear functionals on $V$:Addition and scalar multiplication are defined pointwise. The dual map sends an output measurement back along $T$:The function composition of these linear maps is linear, and $T^{\prime }$ is linear in $\phi$. This is the algebraic dual map, so its definition involves no complex conjugation or inner product.

For a vector subspace $U\subseteq V$, its annihilator of a vector subspace isLet $\dim U=k$ and $\dim V=n$. Extend a basis $u_1,\dots ,u_k$ of $U$ to a basis $u_1,\dots ,u_n$ of $V$, and let ${\epsilon }^1,\dots ,{\epsilon }^n$ be the dual basis. Every linear functional has the unique expression $\phi ={\sum }_{j=1}^n\phi (u_j){\epsilon }^j$. It belongs to $U^0$ precisely when its first $k$ coefficients vanish. ConsequentlyThe listed dual basis elements are linearly independent, so counting them proves the formula, including $U=0$ and $U=V$.

Suppose $U$ is an invariant subspace for $T$. For $\phi \in U^0$ and $u\in U$, the dual map satisfiesbecause $Tu\in U$ and the annihilator of a vector subspace consists of the linear functionals vanishing there. ThusThis is the correspondence between invariant subspaces and annihilators.

We prove by mathematical induction on $n=\dim V$ that every linear map on an $n$-dimensional complex vector space admits both triangular forms. For $n=0$ or $1$ this is immediate. When $n>1$, the fundamental theorem of algebra supplies an eigenvector $v$; its span $U=⟨v⟩$ is an invariant subspace.

By parts (ii) and (iii), $U^0$ has dimension $n-1$ and is an invariant subspace of the dual map $T^{\prime }$. Apply the induction hypothesis to $T^{\prime }{|}_{U^0}$ to choose a basis ${\phi }_1,\dots ,{\phi }_{n-1}$ with an upper triangular matrix. Extend it by a linear functional ${\phi }_n$ satisfying ${\phi }_n(v)=1$. Such a functional exists by basis extension, and cannot belong to $U^0$. In this basis of $V^{\prime }$, the matrix of $T^{\prime }$ has the formwhere $B$ is an upper triangular matrix; here the last diagonal entry follows by evaluating $T^{\prime }{\phi }_n$ at $v$, where $Tv=\lambda v$.

There is a basis $e_1,\dots ,e_n$ of $V$ with ${\phi }_i(e_j)={\delta }_{ij}$, since the dual basis construction gives a finite-dimensional bidual evaluation map isomorphism. In particular $e_n=v$. The matrix transpose relationship for a dual map givesa lower triangular matrix. Reversing this basis turns a lower triangular matrix into an upper triangular matrix. If $R$ is the permutation matrix reversing the order, we have provedThis completes the induction by triangularization using dual spaces.

Write $K_i=\ker T^i$, with $K_0=\{0\}$. The minimal polynomial $x^m$ means $T^m=0$ and $T^{m-1}\ne 0$. Choose $w$ with $T^{m-1}w\ne 0$. For each $0\le i<m$, set $w_i=T^{m-1-i}w$. ThenThus $w_i\in K_{i+1}\setminus K_i$. Also $K_i\subseteq K_{i+1}$ because applying $T$ to zero still gives zero. Therefore the kernel dimensions of powers of a nilpotent map increase strictly until the nilpotency index:The same reasoning covers $m=1$, when the nilpotent linear map is zero on a nonzero vector space.

Put $d_i=\dim K_i$, including $d_0=0$. The restriction of $T^i$ to $K_{i+1}$ has kernel $K_i$, so the rank-nullity theorem givesLikewise $T^{i-1}{|}_{K_i}$ has kernel $K_{i-1}$ and hence image dimension $d_i-d_{i-1}$. But $T(K_{i+1})\subseteq K_i$, which impliesComparing dimensions yields the required concavity of the kernel dimensions of powers of a nilpotent map:

The increments ${\Delta }_i=d_i-d_{i-1}$ are positive integers by part (a)(i), are nonincreasing by part (a)(ii), and sum to $d_m=4$. Thus they form an integer partition of $4$. The complete list is $(4)$, $(3,1)$, $(2,2)$, $(2,1,1)$, and $(1,1,1,1)$.

To prove all five occur over every field, let $J_s(0)$ be a Nilpotent Jordan block of size $s$. It sends each standard basis vector to its predecessor, with the first sent to zero, soFor a block diagonal matrix, the nullities add. The following explicit nilpotent matrices therefore realize every possible sequence:In each row the largest Jordan block size is exactly the nilpotency index $m$, so the displayed sequence stops at the correct place.

Direct matrix multiplication gives $A^2=0$. Denote the columns by $c_1,\dots ,c_4$; they satisfyThus the matrix rank is at most two. Over the real numbers or complex numbers, the upper-left two-by-two minor is $-3\ne 0$, so the matrix rank is exactly two. Every Jordan block has size at most two because $A^2=0$, and each size-two Nilpotent Jordan block contributes one to the matrix rank. ConsequentlyEquivalently the nullities are $(2,4)$ and the minimal polynomial is $x^2$.

There is a field qualification in the source: Question 2 initially allows an arbitrary field, and part (c) does not specify a new one. The preceding answer holds over every field whose characteristic is not three. In characteristic three, the first row vanishes and the other three rows all become $(2,1,0,2)$, giving matrix rank one while $A^2=0$. Under that reading the answer is instead

Throughout Question 3, the inner product is linear in its first argument and conjugate-linear in its second. Over the real numbers, conjugation has no effect. The symbol $T^{\ast }$ now denotes the adjoint operator for this inner product.

An adjoint operator of $T:V\to V$ is a linear map $T^{\ast }:V\to V$ satisfyingThis identity transfers $T$ from the first input of the inner product to the second.

If $R$ and $S$ both satisfy the defining identity of an adjoint operator, thenfor every $u,w\in V$. Choosing $u=(R-S)w$ gives $\Vert (R-S)w{\Vert }^2=0$. The positive definiteness of the inner product forces $(R-S)w=0$ for every $w$, proving

For the normal operator $T$, the adjoint operator identity and $T^{\ast }T=T{T}^{\ast }$ giveFor the last equality, $⟨T{T}^{\ast }v,v⟩=⟨T^{\ast }v,T^{\ast }v⟩$ and complex conjugation allow reversal of the two arguments. Taking the nonnegative square roots provesIn particular the two kernels coincide.

Let $w=Tv$. If $T^{2}v=0$, then $Tw=0$, and part (i) gives $\Vert T^{\ast }w\Vert =\Vert Tw\Vert =0$. Thus $T^{\ast }w=0$ andThe positive definiteness of the inner product gives $w=0$. Since the reverse kernel inclusion always holds, we obtainThis is kernel stabilization for a normal operator.

For a polynomial $f(x)={\sum }_{j=0}^d{a}_j{x}^j$, the defining identity and uniqueness of the adjoint operator giveIndeed, the adjoint operator of a sum is the sum of the adjoint operators, the adjoint of $aT$ is $\bar{a}{T}^{\ast }$, and the adjoint of a product $AB$ is $B^{\ast }{A}^{\ast }$. Since the normal operator $T$ commutes with $T^{\ast }$, each power of $T$ commutes with each power of $T^{\ast }$. Multiplying the two finite sums therefore givesHence polynomials of a normal operator are normal, including constant polynomials.

Suppose some exponent $q_j\ge 2$. DefinePart (iii) makes $N$ a normal operator. For every $v\in V$, put $w=h(T)v$. The minimal polynomial identity givesPart (ii), applied to $N$, forces $Nw=0$. As this holds for every $v$,This contradicts minimality: $m_T/f_j$ is a monic polynomial of smaller degree annihilating $T$. Therefore the minimal polynomial of a normal operator is a square-free polynomial over either of the given fields:This argument does not require the irreducible polynomials to be linear, so it also covers the real case.

Take $N=T-\lambda I$. It is a polynomial in the normal operator $T$, so part (b)(iii) makes $N$ a normal operator. Also $N^{\ast }=T^{\ast }-\bar{\lambda }I$. If $Tv=\lambda v$, part (b)(i), applied to $N$, givesThe norm vanishes only at the zero vector, soThis is the adjoint eigenvector identity for a normal matrix expressed independently of coordinates.

Let $u\in \ker (T-\lambda I)$ and $w\in \ker (T-\mu I)$, with $\lambda \ne \mu$. By part (i) and the adjoint operator identity,The last step uses conjugate-linearity in the second argument of the inner product. Therefore $(\lambda -\mu )⟨u,w⟩=0$, proving the orthogonality of the two eigenspaces:

Over the complex numbers, the fundamental theorem of algebra makes every irreducible polynomial factor $f_j(x)$ equal to $x-{\lambda }_j$. Part (b)(iv) giveswith distinct eigenvalues. The primary decomposition theorem for linear maps consequently expresses $V$ as the direct sum of the actual eigenspaces $E_{{\lambda }_j}=\ker (T-{\lambda }_{j}I)$, with no higher generalized eigenspaces needed. Part (ii) makes these summands mutually orthogonal.

Apply the Gram-Schmidt process to a basis within each eigenspace. Its linear combinations stay within that eigenspace, so all resulting vectors are still eigenvectors. Their union is orthonormal by part (ii) and spans $V$ by the primary decomposition theorem for linear maps. Thusfor an orthonormal basis $\mathcal{B}$ of eigenvectors. This proves the finite-dimensional complex spectral theorem for normal operators by the requested decomposition argument.

Solutions to all three questions of the University of Oxford Part A linear algebra paper, sat on 15 June 2021. Source: released examination PDF, parent PDF pages 253–254; paper pages 1–2. All questions and parts are covered, including both alternatives in questions asking whether an assertion is true.

The quotient vector space $V/U$ identifies two vectors $v,w$ precisely when $v-w\in U$. Since $U$ is an invariant subspace, $T(U)\subseteq U$. ThusConsequently $T(v)+U=T(w)+U$: the output does not depend on the chosen representative. This proves that the induced linear map on a quotient vector spaceis well-defined. It is a linear map because, for scalars $a,b$,

No. Over any field $F$, take $V=F^2$, let $T=I$ be the identity operator, and choose the vector subspaceBoth $U$ and the quotient vector space $V/U$ have dimension one. A one-dimensional vector space has no nonzero proper vector subspace, so neither can have a nonzero proper invariant subspace. The induced linear map on a quotient vector space is again the identity operator.

However, $L=\mathrm{span}\{e_2\}$ is another nonzero proper vector subspace of $V$, and $T(L)=L$. HenceThe hypotheses do not prevent a direct sum $V=U\oplus L$ whose two summands are invariant subspaces.

Write $K_j=\ker T^j$, where $T^0=I$ and $K_0=\{0\}$. These kernels satisfy $K_j\subseteq K_{j+1}$. Also $T(K_{i+1})\subseteq K_i$ and $T(K_i)\subseteq K_{i-1}$: for example, $T^i(Tv)=T^{i+1}v=0$ when $v\in K_{i+1}$. Thus the proposed linear map between quotient vector spaces is well-defined and has the formulaIf $v+K_i$ belongs to its kernel, then $Tv\in K_{i-1}$. Therefore $T^{i}v=T^{i-1}(Tv)=0$, so $v\in K_i$ and $v+K_i$ is zero. We have provedThese are the injections between successive kernel quotients. In finite dimension, they imply $\dim K_{i+1}-\dim K_i\le \dim K_i-\dim K_{i-1}$.

Surjectivity need not hold. Take a nonzero vector space $V$ and the zero linear map $T=0$. At $i=1$, we have $K_2=K_1=V$ and $K_0=0$, so

Subtract the identity matrix and putDirect matrix multiplication givesFor the last equality, each column of $N^2$ is a multiple of $(1,-1,0{)}^T$, and $N(1,-1,0{)}^T=0$. Thus $N$ is a nilpotent matrix. The minimal polynomial of $A_{\lambda ,\mu }$ divides $(t-1{)}^3$ and equals $(t-1{)}^s$, where $s$ is the nilpotency index of $N$.

The first row of $N$ forces $\lambda =0$ if $N=0$, and its third row then forces $\mu =0$. Conversely $\lambda =\mu =0$ gives $N=0$. If exactly one parameter is nonzero, then $N\ne 0$ but $N^2=0$. If both are nonzero, then $N^2\ne 0$ while $N^3=0$. Consequently the complete answer isNo lower power can annihilate the matrix in any of these cases, as the displayed nonvanishing matrix powers show.

Let $F$ be the common field. The dual map is $S^{\prime }(f)=f\circ S$ for $f\in W^{\prime }$, where $W^{\prime }$ and $V^{\prime }$ are the dual spaces.

First assume $S^{\prime }$ is injective. If $S$ were not surjective, its image of a linear map $\mathrm{im}S$ would be a proper vector subspace of $W$. Choose a basis $w_1,\dots ,w_r$ of $\mathrm{im}S$ and use basis extension to obtain a basis $w_1,\dots ,w_m$ of $W$, with $r<m$. There is a linear functional $f\in W^{\prime }$ withIt is nonzero and vanishes on $\mathrm{im}S$, so $S^{\prime }(f)=f\circ S=0$, contradicting injectivity. Equivalently, the annihilator of a vector subspace $\mathrm{im}S$ would give a nonzero kernel for $S^{\prime }$. Therefore

Now assume $S^{\prime }$ is surjective. If $0\ne v\in \ker S$, basis extension gives a linear functional $h\in V^{\prime }$ with $h(v)=1$: include $v$ in a basis and take its coordinate functional. By surjectivity, $h=S^{\prime }(f)$ for some $f\in W^{\prime }$. Buta contradiction. Hence $\ker S=0$, which proves

In the monomial basis $\mathcal{B}=(1,x,x^2,x^3)$ of the complex vector space $V=\mathbb{C}[x{]}_{\le 3}$, the binomial theorem givesThe characteristic polynomial of this upper triangular matrix is the product of $t$ minus its diagonal entries, so ${\chi }_T(t)=(t-1{)}^4$.

For the minimal polynomial, set $\Delta =T-I$, the forward difference with step one. For a nonconstant polynomial of polynomial degree $d$, the binomial theorem shows that $f(x+1)-f(x)$ has polynomial degree $d-1$. Constant polynomials have zero forward difference. Consequently ${\Delta }^4=0$ on $V$. To prove that the nilpotency index is exactly four, computeIt follows thatIf $T$ were diagonalizable, its only eigenvalue would be $1$, and its diagonal matrix in an eigenbasis would be $I$. This would make $T=I$, whereas $T(x)=x+1\ne x$. Thus $T$ is not diagonalizable. Equivalently, its minimal polynomial has a repeated root.

By Jordan normal form, each complex nilpotent matrix of size six can be put by matrix similarity into a block diagonal matrix whose Nilpotent Jordan blocks have sizesA Nilpotent Jordan block of size $s$ has matrix rank $s-1$ and minimal polynomial $t^s$. Therefore, for the whole matrix,Thus the given matrix rank determines the number $k$ of Jordan blocks, and the given minimal polynomial determines the largest size $s_1$. For size six these two data determine the entire integer partition. Here is the complete list, arranged by the largest size:To see that the list is exhaustive, choose the largest part $s_1$ between one and six and partition the remainder $6-s_1$ into parts at most $s_1$. The resulting rows all have distinct pairs $(s_1,k)$. Hence $A$ and $B$ have the same Jordan normal form $J$.

Explicitly, choose invertible matrices $X,Y$ such that $A=XJ{X}^{-1}$ and $B=YJ{Y}^{-1}$. ThenThis proves matrix similarity and illustrates the classification of six-dimensional nilpotent matrices by rank and nilpotency index.

We construct a cube root of a matrix on each Jordan block. Since $A$ is an invertible matrix over the complex numbers, its Jordan normal form isConsider one block $J_m(\lambda )=\lambda I+N$, where $N=J_m(0)$ is a Nilpotent Jordan block and $N^m=0$. Choose a complex cube root $\beta$ of $\lambda$, so ${\beta }^3=\lambda$.

We need a polynomial $q(z)$ with constant term one satisfyingThis can be constructed using only polynomial multiplication. Write $q(z)=1+{\sum }_{j=1}^{m-1}{c}_j{z}^j$. Once $c_1,\dots ,c_{j-1}$ have been chosen, the coefficient of $z^j$ in $q(z{)}^3$ is $3c_j$ plus an expression depending only on those earlier coefficients. Choose $c_j$ to make this coefficient one at $j=1$ and zero at $2\le j<m$. Division by three is possible over the complex numbers, so the recursion always succeeds. Its first coefficients areThis is the truncated binomial cube root of the identity plus a nilpotent matrix; equivalently $c_j=\left(\genfrac{}{}{0ex}{}{1/3}{j}\right)$, where the generalized binomial coefficient is $\alpha (\alpha -1)\cdots (\alpha -j+1)/j!$ and the empty product is one.

Substitute $z=N/\lambda$. The polynomial remainder is a multiple of $N^m$, hence zero. It follows thatFor $m=1$, take $q=1$, so the same construction covers single-entry blocks. Assemble the block diagonal matrix $C={⨁}_r{C}_{m_r}({\lambda }_r)$. Taking matrix powers respects these blocks, and conjugating back givesThus every invertible matrix over the complex numbers has at least one cube root of a matrix. The construction uses only finitely many matrix powers.

Take the Nilpotent Jordan blockThenSuppose that a complex matrix $B$ of size three satisfied $B^3=A$. We would have $B^9=A^3=0$, so $B$ would be a nilpotent matrix. Every eigenvalue of $B$ must then be zero: if $Bv=\theta v$ with $v\ne 0$, applying $B^9$ gives ${\theta }^{9}v=0$. Its characteristic polynomial is therefore $t^3$, and the Cayley-Hamilton theorem gives $B^3=0$. This contradicts $B^3=A\ne 0$. HenceThe obstruction is that a nilpotent matrix of size three cannot have nilpotency index greater than three.