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

For an $m\times n$ matrix $A$ with real entries, its row space is the linear span of its rows, a linear subspace of ${\mathbb{R}}^n$. Its column space is the linear span of its columns, a linear subspace of ${\mathbb{R}}^m$ and the image of a linear map $x\mapsto Ax$. Its null space isa linear subspace of ${\mathbb{R}}^n$. Finally,Thus the rank of a matrix counts the number of linearly independent columns, equivalently rows. The nullity is $\dim \ker A=n-\mathrm{rank}A$ by the rank-nullity theorem.

Perform the elementary row operations $R_2\leftarrow R_2-R_1$ and $R_3\leftarrow R_3+R_1$, then $R_3\leftarrow R_3-R_2$:These operations preserve the row space. The two nonzero rows of this row echelon form are linearly independent: only the first has a nonzero first entry, and the second is nonzero. HenceFurther Gaussian elimination gives the reduced row echelon formwhich will also identify the free variables in the null space calculation.

The pivot columns in the row echelon form are columns 1 and 3. Use those columns of the original matrix for a basis of the original column space:For a direct spanning check, column 2 is twice column 1 and column 4 is $(17/5)$ times column 1 minus $(3/5)$ times column 3. The displayed columns are linearly independent, since the first two coordinates of $\alpha c_1+\beta c_3=0$ give $\alpha -\beta =0$ and $\alpha +4\beta =0$, so $\alpha =\beta =0$.

The reduced row echelon form givesTaking the free variables as $x_2=s$ and $x_4=5t$, the null space isThe two displayed vectors are linearly independent, as their second and fourth coordinates show, and each satisfies $Ax=0$. ThusThis also agrees with the rank-nullity theorem: $4-2=2$.

Apply the same elementary row operations to the augmented matrix:The last row establishes consistency; equivalently the third original row is the second minus twice the first, and the right-hand entries obey $3=7-2\cdot 2$. With $x_2=s$ and $x_4=5t$, the second equation gives $x_3=1+3t$ and the first gives $x_1=3-2s-17t$. All real solutions are thereforeThis affine solution space is one particular solution plus the null space. The two free variables show that there are no additional restrictions.