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 / 4

Over the underlying field $F$, the row space is the linear span of the row vectors of $A$, a vector subspace of $F^n$. The column space is the linear span of its column vectors, a vector subspace of $F^m$. The null space isa vector subspace of the domain. The column space is the image of a linear map represented by $A$; the null space is its kernel.

Gaussian elimination givesElementary row operations preserve the row space, so $\{(1,0,1),(0,1,2)\}$ is a basis. The two rows are linearly independent because their first two coordinates form the standard basis of ${\mathbb{R}}^2$.

The pivot columns of the reduced matrix in part (i) are columns one and two. Select those columns of the original matrix, giving the column-space basisThey are independent, for example their first two entries have determinant $-2\ne 0$. The remaining original column is the first plus twice the second. Taking the reduced matrix's columns instead would generally give the wrong column space.

The reduced equations are $x+z=0$ and $y+2z=0$. Thus the null space is the lineThe nonzero spanning vector gives a one-element basis, so the nullity is one.

Reducing the augmented matrix givesThere is no contradictory row. Hence the system is consistent, with affine solution spaceThe three planes intersect in this common line. Their normals span a two-dimensional row space, leaving a one-dimensional common direction, the null space. More explicitly, five times the first equation minus eleven times the second plus twice the third is the zero equation, including the right-hand side; the third plane therefore contains the intersection of the first two.

The rank of $A$ is the dimension of its column space, equivalently the dimension of its row space or the number of pivot columns in a row-echelon form. For an $n\times n$ matrix it lies between zero and $n$.

Each elementary matrix is obtained by applying one invertible elementary row operation to the identity matrix. Its inverse is the elementary matrix for the reverse operation. A product of elementary matrices is therefore invertible and has full rank $n$.

Conversely, if $\mathrm{rank}A=n$, Gaussian elimination has a pivot in every column and reduces $A$ to the identity. Writing the successive row operations as left multiplication gives $E_r\cdots E_{1}A=I$. Hence $A=E_1^{-1}\cdots E_r^{-1}$, a product of elementary matrices. This proves both directions of the elementary-matrix factorization theorem.