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

For a real $m\times n$ matrix $A$, the row space is the linear span of its rows in ${\mathbb{R}}^n$, and the column space is the linear span of its columns in ${\mathbb{R}}^m$. Its null space consists of the input vectors sent to zero:The rank of a matrix isThe equality of row and column dimensions is the row-rank/column-rank theorem. Each displayed space is a linear subspace of the indicated ambient vector space.

Write the columns of $A$ as $a_1,\dots ,a_n$ and the coordinates of the vector $x$ as $x_1,\dots ,x_n$. By the definition of matrix multiplication,Indeed, its $i$th coordinate is ${\sum }_{j=1}^n{A}_{ij}{x}_j$, exactly the $i$th coordinate of this linear combination. Since the column space contains every linear combination of the columns, the claim holds for every vector $x$.

Swap the first two rows, then perform $R_2\leftarrow R_2+R_1$ and $R_3\leftarrow R_3-2R_1$. These elementary row operations giveScale row 2 by $1/5$, subtract it from row 3, and finally subtract twice row 2 from row 1. The reduced row echelon form isElementary row operations preserve the row space. The two nonzero rows of $R$ are linearly independent, since their leading entries lie in different columns. Hence

The pivot columns of the reduced row echelon form are columns 1 and 3. Take those columns of the original matrix, since elementary row operations need not preserve the original column space:For an explicit spanning check, column 2 is $-2a_1$, column 4 is $-a_1+2a_3$, and column 5 is $3a_1-2a_3$. The first two coordinates of the displayed columns form a $2\times 2$ matrix of determinant $-5\ne 0$, proving their linear independence. They are therefore a basis of the column space.

The right-hand vector is in the column space, becauseConsequently the linear system is consistent. A concrete solution isAs a compatibility check, the original rows satisfy $r_1+11r_2-5r_3=0$, and the right-hand entries satisfy the same relation $1+11\cdot 4-5\cdot 9=0$. There are infinitely many solutions, obtained by adding any vector in the null space to the displayed solution.

The reduced row echelon form yieldsTake the free variables in a linear system to be $s=x_2$, $t=x_4$, $u=x_5$. ThenThusEach listed vector lies in the null space, and every solution has the displayed form. Their coordinates in positions 2, 4 and 5 prove linear independence. The dimension also follows from the rank-nullity theorem: $5-2=3$.