Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 5

False. In the real vector space $\mathbb{R}$, both $\{1\}$ and $\{2\}$ are bases: each is linearly independent and spans the whole space. A basis need not be a unique set. What is fixed for a finite-dimensional vector space is the number of basis elements, its dimension.

True. Existence follows because the basis spans $V$. If $v={\sum }_i{a}_i{s}_i={\sum }_i{b}_i{s}_i$, subtract to get ${\sum }_i(a_i-b_i)s_i=0$. The basis vectors' linear independence forces every $a_i-b_i=0$, proving uniqueness. For an infinite basis, both representations have finite support, so the same argument applies to their finite union. These coefficients are the coordinates relative to a basis.

Transpose both inverse identities, using reversal of multiplication under matrix transposition:Thus $(A^T{)}^{-1}=(A^{-1}{)}^T$, by uniqueness of the matrix inverse.

Let column $j$ of $A^{-1}$ be $x$, so $Ax=e_j$. Every diagonal entry of the invertible lower triangular matrix $A$ is nonzero, since its determinant is the product of those entries. In row one through row $j-1$, the right-hand side is zero. Forward substitution first gives $x_1=0$, then $x_2=0$, and successively $x_i=0$ for all $i<j$. These are precisely the entries above the diagonal in column $j$ of $A^{-1}$. Every column satisfies this, proving that $A^{-1}$ is lower triangular. This is triangularity of an inverse matrix.

If $B$ is an invertible upper triangular matrix, $B^T$ is invertible and lower triangular. Part (ii) makes $(B^T{)}^{-1}$ lower triangular, while part (i) identifies it with $(B^{-1}{)}^T$. Transposing gives that $B^{-1}$ is upper triangular. This deduction uses both the inverse-transpose identity and the lower-triangular result.

Gaussian elimination givesThe first two original columns form an image basis:Their independence follows already from their third and first coordinates. The third column is twice the first plus the second, and the fourth is the first plus twice the second, so they span every output of $T$.

The rank-nullity theorem states $\dim V=\dim \ker T+\dim \mathrm{im}T$ for a linear map from a finite-dimensional vector space $V$. Here the domain has dimension four and the image has dimension two. Thus $\dim \ker T=4-2=2$. For example, a kernel basis is $\{(-2,-1,1,0),(-1,-2,0,1)\}$, as follows from the reduced equations.

A linear map $T:V\to W$ is onto, or surjective, when every $w\in W$ equals $T(v)$ for some $v\in V$; equivalently its image is all of $W$. Here $T$ is not onto, because its image has dimension two while its declared codomain ${\mathbb{R}}^3$ has dimension three. Indeed every image vector satisfies $x+y-3z=0$, so, for example, $(0,0,1)$ is not attained.

A linear map is one-to-one, or injective, when equal outputs imply equal inputs. Equivalently its kernel is $\{0\}$: subtracting inputs converts equality of outputs to a zero output. Here $T$ is not one-to-one, since its kernel has dimension two. Concretely, $T(-2,-1,1,0)=T(0)=0$ for distinct inputs.