Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof (resit) / 6

For an $m\times n$ matrix, its row space is the span of its rows, a subspace of ${\mathbb{R}}^n$; its column space is the span of its columns, a subspace of ${\mathbb{R}}^m$. Its null space is $\ker A=\{x\in {\mathbb{R}}^n:Ax=0\}$. The rank of a matrix is the dimension of its column space, equal to the dimension of its row space. The rank-nullity theorem gives $\dim \ker A=n-\mathrm{rank}A$.

Let the original rows be $r_1,\dots ,r_5$. Begin with rows $r_2$, $r_3-r_2$ and $r_4$:Subtract the third from the second, then subtract that new second row from the first. The resulting rows areThey are linearly independent because their first three coordinates form the identity matrix. All original rows lie in their span: $r_1=2r_2+r_4$ and $r_5=r_2-(r_3-r_2)+r_4$. Thus they form a basis of the row space, and $\mathrm{rank}A=3$. Equivalently, these are the nonzero rows of the reduced row echelon form, with two further zero rows.

The pivot columns are columns 1, 2 and 3 of the original matrix. A basis for its column space is thereforeUse the original columns, rather than the columns of the row-reduced matrix: elementary row operations preserve column dependence relations, but can change the column space as a subspace of ${\mathbb{R}}^5$.

The reduced homogeneous system is $x_1+x_4=0$, $x_2-x_4=0$, $x_3+x_4=0$. Set $x_4=t$ to obtainThe rank-nullity theorem confirms $3+1=4$, and substitution verifies that the displayed vector is annihilated by $A$.

A particular solution is $x_p=(1,0,-1,0{)}^T$, as direct substitution into all five equations verifies. Add any vector in the null space to obtain every solution:Conversely, the difference of any two solutions is annihilated by $A$, so there are no further solutions. This is the affine solution space of a consistent linear system.