Past exam of the mathematics course of the University of Oxford / 2017

Source: released examination PDF, bundle pages 10–14.

The vectors are linearly independent ifThey span $V$ if every $v\in V$ is a linear combination $v={\sum }_{j=1}^n{a}_j{v}_j$ with real coefficients. They form a basis of $V$ if they are linearly independent and span $V$. Equivalently, every $v\in V$ has exactly one such representation: existence is the spanning set condition, and subtracting two representations shows that uniqueness is precisely linear independence.

The Steinitz exchange lemma states that if $u_1,\dots ,u_r$ are linearly independent and $w_1,\dots ,w_s$ span a vector space $V$, then $r\le s$ and some $r$ of the $w_j$ can be replaced by $u_1,\dots ,u_r$ while preserving the spanning set property.

Here is the exchange argument. Suppose that after $k$ replacements, a spanning set iswhere the remaining $w_j$ have been relabelled if necessary. Express $u_{k+1}$ as a linear combination of this family. At least one remaining $w_j$ has a nonzero coefficient; otherwise $u_{k+1}$ belongs to the span of $u_1,\dots ,u_k$, contradicting linear independence. Relabel this entry $w_{k+1}$. Solving for $w_{k+1}$ shows that it lies in the span ofThe new family therefore still spans $V$. Starting at $k=0$ repeats this step until all $r$ independent vectors have been inserted. If $r>s$, after $s$ steps the next $u_{s+1}$ would lie in the span of $u_1,\dots ,u_s$, a contradiction. Thus $r\le s$, and the construction proves the replacement assertion as well.

Put $w_1=v_1$ and $w_j=v_j-v_1$ for $j\ge 2$. Since $v_1=w_1$ and $v_j=w_j+w_1$, the two families have the same linear span. Moreover,If the $v_j$ are linearly independent, a vanishing expression forces $a_j=0$ for $j\ge 2$ and then $a_1=0$. Conversely,so linear independence of the $w_j$ forces all $b_j=0$. Thus both the spanning set condition and linear independence are equivalent for the two families, proving the desired equivalence of bases.

Write $u=(a,b{)}^T$, $v=(c,d{)}^T$ and $\Delta =ad-bc$. If $xu+yv=0$, thenEliminating $y$ gives $\Delta x=0$, and eliminating $x$ gives $\Delta y=0$. Hence $\Delta \ne 0$ implies linear independence.

For the converse, suppose $\Delta =0$. If $u=0$, the family already contains the zero vector and is linearly dependent. If $a\ne 0$, the equality $ad=bc$ gives $v=(c/a)u$. If $a=0$ but $u\ne 0$, then $b\ne 0$ and $bc=0$ forces $c=0$, so $v=(d/b)u$. Both cases give a nontrivial linear relation. ThereforeThis is the two-dimensional determinant criterion, proved directly without assuming that criterion.

Subtracting the first vector from each of the other two preserves the basis property by iii. The resulting family isIts last two vectors belong to the plane with first coordinate zero. By b, they are linearly independent there precisely whenIn that case their two-dimensional span is the whole plane, and adjoining $e_1$ gives a basis of ${\mathbb{R}}^3$. If the displayed expression vanishes, a nontrivial linear relation among those two vectors prevents a basis. Thus

By definition, the image of a linear map $T_A$ isConsequently $\mathbf{b}\in \mathrm{im}{T}_A$ means exactly that some $\mathbf{x}\in {\mathbb{R}}^m$ satisfies $A\mathbf{x}=\mathbf{b}$. This is precisely the existence of a solution of the linear system.

Suppose ${\mathbf{x}}_0$ is one solution. By linearity,Thus the solution set of a linear system is exactly ${\mathbf{x}}_0+\ker T_A$. It has one member if the kernel is $\{0\}$. Conversely, if there is a unique solution and $\mathbf{z}\in \ker T_A$, then ${\mathbf{x}}_0+\mathbf{z}$ is also a solution, forcing $\mathbf{z}=0$. Combining this with i gives

If $\mathbf{b}$ is outside the image of a linear map $T_A$, there is no solution. Otherwise choose ${\mathbf{x}}_0$ with $A{\mathbf{x}}_0=\mathbf{b}$. By ii, a zero kernel gives a unique solution. If the kernel contains a nonzero vector $\mathbf{z}$, allare solutions. They are distinct, since $(t-s)\mathbf{z}=0$ forces $t=s$. Hence there are infinitely many. These alternatives exhaust all possibilities.

No. Here $A$ has more rows than columns, which does not force a nonzero kernel. For example, with $m=1$, $n=2$,the linear system has the unique solution $x=0$. With the same $A$ and $\mathbf{b}=(0,1{)}^T$ it has no solution at all.

No. Take $A=I_m$ and $\mathbf{b}=0$. The homogeneous linear system then has only the solution $\mathbf{x}=0$. Homogeneity ensures existence, but infinitely many solutions would additionally require a nonzero kernel.

No. The rank-nullity theorem givesbut this guarantees infinitely many solutions only when the linear system is consistent. For a counterexample takeThere is no solution, since the left side always vanishes.

Yes. A surjective $T_A$ has $\mathrm{im}{T}_A={\mathbb{R}}^n$, so every $\mathbf{b}$ is attained. Its rank of a linear map is $n$, and the rank-nullity theorem givesThe solution set of a linear system is therefore a translate of a nonzero vector subspace, containing infinitely many solutions as in iii.

The first two equations give $x_1=1-2x_3$ and $x_2=2-5x_3$. Substitution into the third givesThis equation is inconsistent exactly when its left side is identically zero and its right side is nonzero. Therefore

The elimination in i determines $x_3$ uniquely exactly when $\lambda \ne 5$. The other two coordinates are then also fixed. Explicitly,For $\lambda =5$, the reduced equation is either inconsistent or leaves $x_3$ free, so a unique solution is impossible.

By i, a free choice of $x_3$ is possible precisely when $\lambda =5$ and $\mu =2$. ThusThe complete solution set of a linear system isThe direction vector spans the kernel, and the displayed straight line is the entire solution set of a linear system.

The preimage isIt contains $0$, and if $u,v$ belong to it and $a,b\in \mathbb{R}$, then $T(au+bv)=aT(u)+bT(v)\in X$, since $X$ is a vector subspace. Thus $T^{-1}(X)$ is a vector subspace. It contains the kernel of $T$ because $0\in X$.

To establish the dimension of the preimage of a vector subspace formula without assuming the theorem to be deduced, choose a basis $k_1,\dots ,k_{n_T}$ of $\ker T$ and a basis $y_1,\dots ,y_d$ of $X\cap \mathrm{im}T$, where $d=\dim (X\cap \mathrm{im}T)$. For each $j$, choose $u_j\in U$ with $T(u_j)=y_j$. These $u_j$ lie in $T^{-1}(X)$.

The family $k_1,\dots ,k_{n_T},u_1,\dots ,u_d$ is linearly independent: applying $T$ to a vanishing linear combination forces all $u_j$ coefficients to vanish by linear independence of the $y_j$, and then all remaining coefficients vanish by linear independence of the $k_i$. It also spans $T^{-1}(X)$: for $u$ in that preimage, write $T(u)={\sum }_j{b}_j{y}_j$. Then $u-{\sum }_j{b}_j{u}_j\in \ker T$, so it is a linear combination of the $k_i$. ConsequentlySet $X=V$. Then $T^{-1}(V)=U$ and $V\cap \mathrm{im}T=\mathrm{im}T$, giving the rank-nullity theorem:

Since $S^{\prime }$ is the restriction of $S$ to $\mathrm{im}T$,This image of a linear map is contained in $\mathrm{im}S$, so $r_{ST}\le r_S$. Also, applying $S$ to a basis of $\mathrm{im}T$ gives a spanning set for $\mathrm{im}{S}^{\prime }$, of size $r_T$. Thus $r_{ST}\le r_T$, and

For $u\in U$, the vector $Tu$ already belongs to $\mathrm{im}T$, soTherefore $\ker (ST)=T^{-1}(\ker S^{\prime })$. Since $\ker S^{\prime }=\ker S\cap \mathrm{im}T$, its intersection with $\mathrm{im}T$ is itself. Applying a with $X=\ker S^{\prime }$ yieldsThe inequality follows from the inclusion $\ker S^{\prime }\subseteq \ker S$ and monotonicity of dimension for vector subspaces.

By i and ii,The domain of a function of $S^{\prime }$ is $\mathrm{im}T$. Its rank-nullity theorem gives $r_{S^{\prime }}+n_{S^{\prime }}=\dim \mathrm{im}T=r_T$. Applying the rank-nullity theorem for $T$ now giveswhich is exactly the rank-nullity theorem for the function composition $ST$.

Choose an ordered basis $\mathcal{B}$ of $V$ and let $A=[T{]}_{\mathcal{B}}$. Define the characteristic polynomial byIf a different basis gives $B=P^{-1}AP$ for an invertible matrix $P$, multiplicativity of the determinant givesThus the definition is independent of the chosen basis. The alternate convention $\det (A-xI)$ differs by the constant factor $(-1{)}^{\dim V}$ and gives the same roots.

A real number $\lambda$ is an eigenvalue of $T$ if $Tv=\lambda v$ for some nonzero vector $v\in V$. Its eigenspace isIt is a vector subspace because it contains $0$ and $T(av+bw)=aTv+bTw=\lambda (av+bw)$ whenever $v,w\in E_{\lambda }$ and $a,b\in \mathbb{R}$.

If $v\in E_{\lambda }\cap E_{\mu }$, then $\lambda v=Tv=\mu v$, so $(\lambda -\mu )v=0$. Since $\lambda \ne \mu$, this forces $v=0$. Therefore

The definition of an eigenvalue and the kernel criterion for a singular square matrix giveFor the second equivalence, a linear map from a finite-dimensional vector space to itself has zero kernel exactly when its rank of a linear map is the full dimension, by the rank-nullity theorem, and therefore exactly when it is invertible. This proves both directions.

If $T^2=I$, every $v\in V$ has the decompositionwhose first term belongs to $E_1$ and second to $E_{-1}$. Their intersection is zero by ii, so $V=E_1\oplus E_{-1}$ is a direct sum. Choosing bases of the two eigenspaces gives a diagonal matrix with entries $1$ and $-1$.