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

For an $m\times n$ matrix $A$ over the real numbers, write its rows as $r_1,\dots ,r_m$ and its columns as $c_1,\dots ,c_n$. ThenThus the row space and column space consist of all linear combinations of the corresponding rows and columns; the null space is the kernel of a linear map represented by $A$. The matrix rank counts independent row or column directions, with row rank equal to column rank.

If $x\in \mathrm{Null}(A)$, the $i$th entry of $Ax=0$ says $r_i\cdot x=0$. Any $y\in \mathrm{Row}(A)$ is a linear combination $y={\sum }_i{\alpha }_i{r}_i$, so bilinearity of the dot product givesHenceThis proves the orthogonality for every pair of vectors in the two vector subspaces. In fact the null space equals the orthogonal complement of the row space, since being orthogonal to every row is exactly the system $Ax=0$.

Use Gaussian elimination. Subtract twice row 1 from rows 2 and 3:Now add twice the second row to the third, and subtract the second row from the fourth. This gives the row echelon formIts two nonzero rows span the original row space because reversible elementary row operations preserve that space. They are linearly independent, as witnessed by their leading entries in different columns. ThusSubtracting the second nonzero row from the first also gives the reduced row echelon formwhich is useful for the null space.

The pivot columns in the row echelon form are columns 1 and 2. Take the corresponding columns of the original matrix:For a direct check, call these columns $c_1,c_2$. The other columns satisfy $c_3=c_1-c_2$ and $c_4=c_1+c_2$, so they are in the same linear span. Also $c_1,c_2$ are linearly independent: their fourth entries force the coefficient of $c_2$ to vanish, then their first entries force the other coefficient to vanish. Elementary row operations preserve dependence relations among columns, but generally change the column space itself, which is why the original columns must be used.

The reduced row echelon form givesChoose the free variables $x_3=s,x_4=t$. ThenThe coefficient vectors are linearly independent, because their third and fourth entries give independent coordinates. ConsequentlySubstitution in the original matrix verifies $Ax=0$ for both basis vectors. The rank-nullity theorem supplies the independent dimension check $2+2=4$.