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 (resit) / 6

For a real $m\times n$ matrix $A$, the row space is the linear span of its rows in ${\mathbb{R}}^n$. The column space is the linear span of its columns in ${\mathbb{R}}^m$, equivalently $\{A\mathbf{x}:\mathbf{x}\in {\mathbb{R}}^n\}$. The null space isThe matrix rank is the dimension of the column space, which equals the dimension of the row space. In particular,The last equality is the rank-nullity theorem.

Denote the five rows by $r_1,\dots ,r_5$. They satisfyThus $r_2,r_3,r_4$ span the row space. They are linearly independent: in a linear combination $\alpha r_2+\beta r_3+\gamma r_4=0$, coordinate 1 gives $\alpha =0$, coordinate 2 then gives $\beta =0$, and coordinate 4 gives $\gamma =0$. ThereforeAs an alternative basis, the nonzero rows of the reduced row echelon form are

Let $c_1,\dots ,c_4$ be the original columns. The first three are linearly independent: restricting them to rows 2, 3 and 4 gives the triangular matrixwhose determinant is one. Also $c_4=c_1-c_2+c_3$, so a basis for the column space isThese are columns of the original matrix. Taking columns of its reduced row echelon form would generally give the wrong column space.

The reduced row echelon form gives $x_1+x_4=0$, $x_2-x_4=0$, and $x_3+x_4=0$. With free parameter $x_4=t$,The displayed nonzero vector therefore forms a basis for the null space:This agrees with the rank-nullity theorem: there are four columns and matrix rank three.

The second, third and fourth linear equations giveSetting $x_4=t$ yields $x_3=-1-t$, $x_2=1+t$ and $x_1=1-t$. The first linear equation then gives $(1-t)+(1+t)+(-1-t)+t=1$, and the fifth gives $(1-t)+t=1$, so both remaining conditions hold for every real $t$. ConsequentlyThis is a particular solution plus the whole null space, an affine line in a vector space of solutions. The derivation both produces solutions and shows that none have been omitted.