Past exam of the linear algebra course of the University of Oxford / 2017 (A15293W1, A0)

Source paper: earlier Computer Science release, member 2016/T/a15293w1.pdf. Its cover dates this examination to 14 June 2017, but its question pages are damaged. The complete three-page counterpart is in Mathematics Part A release, member FOI-20210708-1 - Data/a15293w1 (2).pdf.

All seventeen source subparts are answered below. Part 1(b)(iii) needs a separable polynomial hypothesis over a general field; its intended case, a counterexample to the unrestricted claim, and the corrected general result are distinguished in that solution. This paper uses the characteristic polynomial convention ${\chi }_T(x)=\det (T-xI)$, which differs by $(-1{)}^{\dim V}$ from the monic convention.

The department's solution-release policy covers even examination years and the exceptional release for 2019; it does not advertise 2017 solutions. The exact-paper check found examiner comments, but no advertised worked answers requiring any subpart to be skipped.

For a linear transformation $T$ of a finite-dimensional vector space over a field $F$, its minimal polynomial $m_T$ is the unique monic polynomial of least degree satisfying $m_T(T)=0$. There is at least one nonzero polynomial with this property because the powers $I,T,T^2,\dots$ lie in the finite-dimensional vector space of linear maps $V\to V$. Dividing any other such polynomial by $m_T$ leaves a remainder of smaller degree that also vanishes at $T$, so that remainder must be zero. This also proves uniqueness.

If $C$ represents $T$ in any basis, the paper's characteristic polynomial isIt is independent of the basis, since changing the basis replaces $C-xI$ by a similar matrix, preserving its determinant. Its degree is $\dim V$ and its leading coefficient is $(-1{)}^{\dim V}$; $m_T$ is always monic.

The Cayley-Hamilton theorem statesLet $d=\dim V$. Extend the field to an algebraically closed field and choose a basis in which the matrix of $T$ is an upper triangular matrix, as permitted. Write its diagonal entries as ${\lambda }_1,\dots ,{\lambda }_d$ and put $V_i=\mathrm{span}(e_1,\dots ,e_i)$. Each $V_i$ is an invariant subspace, andApply $T-{\lambda }_{d}I$ first, then $T-{\lambda }_{d-1}I$, and continue. The resulting product sends $V_d$ into $V_0=\{0\}$. These factors are commuting operators, soThe determinant of an upper triangular matrix gives ${\chi }_T(x)=(-1{)}^d{\prod }_i(x-{\lambda }_i)$. Thus ${\chi }_T(T)=0$ after the field extension. Its entries were in the original field, whose embedding is injective, so they were already zero there. The zero-dimensional case is immediate as well.

The displayed matrix is the transpose convention for a companion matrix. Expanding $\det (xI-A)$ along its last row givesIndeed, the last entry contributes $(x+{\alpha }_{n-1})x^{n-1}$ and the entry in column $j<n$ contributes ${\alpha }_{j-1}{x}^{j-1}$; the cofactor signs cancel those from the superdiagonal entries $-1$. ConsequentlyThe Cayley-Hamilton theorem gives $f(A)=0$, so $m_T$ divides $f$. To exclude a smaller minimal polynomial, let $e_1,\dots ,e_n$ be the standard basis. The first $n-1$ rows of $A$ showIf ${\sum }_{j=0}^{n-1}{c}_j{A}^j=0$, multiplying on the left by $e_1^{\mathsf{T}}$ gives ${\sum }_j{c}_j{e}_{j+1}^{\mathsf{T}}=0$, so every coefficient is zero. No nonzero polynomial of degree below $n$ vanishes at $A$. Since $f$ and $m_T$ are monic polynomials,

Write $B=D+K$, where $D$ has $A$ in each diagonal block and zero elsewhere, while $K$ has $I$ immediately above the diagonal and zero elsewhere. These block matrices satisfy $DK=KD$: either product has $A$ immediately above the diagonal. Also, $K^i$ has $I$ on its $i$th superdiagonal and is zero elsewhere.

The binomial theorem for commuting matrices therefore yieldsOnly $r=i$ can contribute to block $(k,k+i)$, provided that block lies in the matrix. HenceThus ${\beta }_{i,j}=\left(\genfrac{}{}{0ex}{}{j}{i}\right)$, interpreted as an element of the field. The formula remains valid in positive field characteristic: some of these coefficients can then vanish. This possibility matters in the next part.

Write $f=m_T$. Part (ii) identifies the first superdiagonal block exactly:where $f^{\prime }$ is the formal derivative. Thus the candidate is $g=f^{\prime }$. If the irreducible polynomial $f$ has $f^{\prime }\ne 0$, its polynomial degree makes $f$ and $f^{\prime }$ coprime. Equivalently, $f$ is a separable polynomial. This includes every irreducible polynomial over a field of characteristic zero, and every irreducible polynomial over a perfect field.

Under this separability hypothesis, Bézout's identity for polynomials gives $a(x)f(x)+b(x)f^{\prime }(x)=1$. Evaluating at $A$ proves that $C=f^{\prime }(A)$ is an invertible matrix. Moreover, $f(B)$ has zero diagonal blocks, because $f(A)=0$. It is therefore a nilpotent matrix with $f(B{)}^N=0$. The only product of $N-1$ strictly upward block steps that reaches block $(1,N)$ uses the first superdiagonal every time, soFor $N=1$, the corresponding assertion is simply $f(B{)}^0=I\ne 0$. The block upper triangular matrix $B$ hasThe minimal polynomial divides this characteristic polynomial. Since $f$ is an irreducible polynomial, it must be a power of $f$; the exact nilpotency index just found forces

The arbitrary-field qualification is necessary. In the rational function field $F={\mathbb{F}}_2(t)$, take $f(x)=x^2-t$. This is an irreducible polynomial: a square of a rational function has even order of vanishing at $t=0$, while $t$ has odd order. Its formal derivative is zero. With $N=2$,The off-diagonal block in $f(B)$ is zero, and $m_U=f$, rather than $f^2$. No alternative polynomial $g$ coprime to $f$ could represent that block: $g(A)=0$ would imply $m_T=f\mid g$. Thus the printed coprimality claim fails as stated over a general field.

There is also a precise general replacement. In characteristic $p>0$, let $q=p^r$ be the largest power for which $f(x)=h(x^q)$, so that $h^{\prime }\ne 0$; set $q=1$ in characteristic zero. Irreducibility of $f$ implies that $h$ is an irreducible polynomial, so $h$ and $h^{\prime }$ are coprime. The binomial theorem in characteristic $p$ gives $B^q=D^q+K^q$. Expanding $h(D^q+K^q)$, with the coefficients equivalently supplied by the Hasse derivatives, giveswhere $H$ commutes with $K$ and is a block upper triangular matrix whose diagonal blocks are $h^{\prime }(A^q)$. These blocks are invertible by Bézout's identity for polynomials, since $h(A^q)=f(A)=0$. Thus $H$ is invertible, andThe same characteristic polynomial and divisibility argument now prove the corrected arbitrary-field answer:This is the minimal polynomial of a companion block chain; $q=1$ recovers the intended separable case.

The dual space isthe vector space of linear functionals, with pointwise operationsGiven the basis $e_1,\dots ,e_n$, its dual basis consists of the coordinate linear functionalsIn particular, $\dim V^{\prime }=\dim V=n$.

The dual map acts by function composition:The composition is a linear functional on $V$, and pointwise operations give $T^{\prime }(a\varphi +b\psi )=a{T}^{\prime }\varphi +b{T}^{\prime }\psi$. Thus this really is a linear transformation; its direction reverses that of $T$.

For $\varphi \in V^{\prime }$ and $v\in V$,so $I^{\prime }$ is the identity map on the dual space. If $S:U\to V$ and $T:V\to W$, then, for $\psi \in W^{\prime }$ and $u\in U$,Equality on all vectors provesApply this to $R{R}^{-1}=R^{-1}R=I$. It gives both $R^{\prime }(R^{-1}{)}^{\prime }=I^{\prime }$ and $(R^{-1}{)}^{\prime }{R}^{\prime }=I^{\prime }$. Consequently the dual map is invertible and

The annihilator of a vector subspace isChoose a basis $e_1,\dots ,e_r$ of $U$ and extend it to a basis $e_1,\dots ,e_d$ of $V$. In the dual basis, precisely $f_{r+1},\dots ,f_d$ span $U^{\circ }$. ThereforeThe canonical restriction linear transformationhas kernel of a linear map $U^{\circ }$. It is surjective: extend any linear functional on $U$ by assigning arbitrary values, for instance zero, to the additional basis vectors. The First isomorphism theorem for vector spaces gives the explicit linear isomorphismIt is natural because the displayed map itself makes no basis choice; a basis was used only to prove surjectivity. In particular, $U^{\prime }$ is canonically a quotient vector space of $V^{\prime }$, rather than canonically a subspace of $V^{\prime }$.

If $\varphi =T^{\prime }\psi$ and $v\in \ker T$, then $\varphi (v)=\psi (Tv)=0$. Thus $\mathrm{im}{T}^{\prime }\subseteq (\ker T{)}^{\circ }$, using the annihilator of a vector subspace.

Conversely, let $\varphi$ vanish on the kernel of a linear map $\ker T$. Define a linear functional on $\mathrm{im}T$ by ${\psi }_0(Tv)=\varphi (v)$. This is well-defined: $Tv=Tw$ implies $v-w\in \ker T$, so $\varphi (v)=\varphi (w)$. Extend ${\psi }_0$ to a linear functional $\psi$ on $W$, using the extension argument from part (i). Then $T^{\prime }\psi =\varphi$, provingThe dimension formula from part (i) and the rank-nullity theorem now giveTo deduce the eigenvalue statement, apply this equality of rank of a linear map to $T-\lambda I$. Its dual map is $T^{\prime }-\lambda I$, so their kernel of a linear map dimensions agree. Thus the same $\lambda$ are eigenvalues, with the same geometric multiplicities.

For algebraic multiplicities as well, part (a)(iii) givesso equality of rank applies to every power. HenceAfter extending to a field where the characteristic polynomials split, take $r\ge \dim V$. These kernel of a linear map spaces are the generalized eigenspaces; the primary decomposition theorem for linear maps identifies their dimensions with the algebraic multiplicities. The same proof works over the original field for every eigenvalue in it. We obtainIn fact the argument also includes the zero eigenvalue.

Use the convention that the inner product is conjugate-linear in its first argument and linear in its second, as in part (b). The adjoint operator is characterized byExistence and uniqueness follow from the finite-dimensional representation of linear functionals by the inner product. More concretely, choose an orthonormal basis $e_i$ and let $a_{ij}=⟨e_i,T{e}_j⟩$. Thenwhich defines $T^{\ast }$ uniquely and verifies the required identity by expansion in that basis. Thus its matrix is the conjugate transpose, proved here rather than assumed. A self-adjoint operator satisfies $T^{\ast }=T$, equivalently $⟨Tv,w⟩=⟨v,Tw⟩$ for every pair of vectors.

Proceed by induction on $\dim V$. The result is immediate for dimension zero. In positive dimension, the characteristic polynomial has a root over the complex numbers, so there is a nonzero eigenvector $v$ with eigenvalue $\lambda$. Normalize it to have norm one. Self-adjointness givesso $\lambda$ is real.

The orthogonal complement $v^{\perp }$ is an invariant subspace: if $w\perp v$, thenThe restriction of $T$ to $v^{\perp }$ is again self-adjoint, since the same inner product identity holds on that subspace. By induction it has an orthonormal basis of eigenvectors. Adjoining $v$ givesThe existence of the first eigenvector is the essential use of the complex numbers in this proof of the finite-dimensional spectral theorem.

Let $e_1,\dots ,e_d$ be the given orthonormal basis, with $T{e}_j={\lambda }_j{e}_j$. From the defining identity of the adjoint operator,These coordinates prove $T^{\ast }{e}_j={\overline{\lambda }}_j{e}_j$ without assuming a matrix formula. Thereforefor every basis vector. Thus $T$ is a normal operator, andThe condition of possessing an orthonormal basis of eigenvectors is already part of the hypothesis; real eigenvalues alone would not imply self-adjointness for an arbitrary linear transformation.

The integral is conjugate-linear in $f$, linear in $g$, and conjugate-symmetric, by the corresponding properties of the integral and of complex conjugation. Also,If a polynomial $f$ is not zero, there is a real point $x_0$ with $f(x_0)\ne 0$: a nonzero polynomial cannot vanish at every real point. By continuity, $|f|$ has a positive lower bound on a sufficiently small closed interval about $x_0$. The continuous function $e^{-x^2}$ also has a positive lower bound there. The integral over this interval is strictly positive. HenceTogether with the finiteness allowed in the question, these properties prove that the formula defines an inner product on $V=\mathbb{C}[x]$.

Differentiate the expression from the source before applying any finite-dimensional result. The exponential factors cancel:This is a polynomial whenever $f$ is a polynomial, and its polynomial degree is at most that of $f$. Differentiation and multiplication are linear, so $T$ is a linear transformation $V\to V$, and every $V_n$ is an invariant subspace.

For self-adjointness, put $w(x)=e^{-x^2}$. Then $w^{\prime }=-2xw$ and $wTf=(w{f}^{\prime }{)}^{\prime }-2wf$. Integration by parts therefore givesThe discarded endpoint terms are $w\overline{f^{\prime }}g$ and $w\overline{f}{g}^{\prime }$. They vanish at both infinities because exponential decay dominates every polynomial. The same decay justifies the intermediate integrals. ConsequentlyHere the question's self-adjointness is in the sense of an adjoint on an inner product space: $T$ itself represents the adjoint on the polynomial space. Each finite-dimensional restriction $T{|}_{V_n}$ is a self-adjoint operator. No choice of operator domain in a completed Hilbert space is needed for this argument. The resulting Gaussian polynomial operator will produce Hermite polynomials in part (iv).

If $f\in V_n\setminus V_{n-1}$, write $f(x)=a_n{x}^n+\cdots$ with $a_n\ne 0$. In the expression $Tf=f^{\prime \prime }-2x{f}^{\prime }-2f$, the first term has polynomial degree at most $n-2$, while the other two contributeThus, if $Tf=\lambda f$, comparison of the leading coefficients givesFor $n=0$ take $V_{-1}=\{0\}$; the same result follows from $T1=-2$. This identifies the eigenvalue conditional on the existence of the eigenvector; existence is established next.

Construct compatible choices in the nested spaces, rather than choosing unrelated orthonormal bases for different $V_n$. Set $V_{-1}=\{0\}$ and defineThe orthogonal complement is taken for the inner product from part (i). Since $\dim V_n=n+1$ and $\dim V_{n-1}=n$, the space $L_n$ has dimension one and $V_n=V_{n-1}\oplus L_n$.

It is an invariant subspace. Indeed, if $v\in L_n$ and $u\in V_{n-1}$, part (ii) givesbecause $Tu\in V_{n-1}$. Also $Tv\in V_n$. Hence $Tv\in L_n$. Any nonzero vector in this one-dimensional space is consequently an eigenvector. Choose a unit vector $g_n\in L_n$. It has polynomial degree exactly $n$: membership in $V_{n-1}$ would make it orthogonal to itself and thus zero. Part (iii) now supplies its eigenvalue.

For $m<n$, $g_m\in V_{n-1}$ and $g_n\perp V_{n-1}$, so the choices are pairwise orthogonal. We have provedAn explicit compatible construction is the Gram-Schmidt process on $1,x,x^2,\dots$:The leading term of $r_n$ is $x^n$, so it is never zero. This fixes the positive real leading coefficient and yields the normalized Hermite polynomials. For example, the Gaussian integral givesEvery polynomial is a finite linear combination of these eigenvectors, since $g_0,\dots ,g_n$ form an orthonormal basis of $V_n$ for each $n$.