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

No: the only solution is the zero vector. Subtract the fourth row equation from the first to get $2x_3=0$. Subtract the third from the fourth to get $2x_2=0$. With $x_2=x_3=0$, any row then gives $x_1=0$. Thus this homogeneous linear system has trivial null space.

The columns are linearly independent. A linear combination of them with coefficients $x_1,x_2,x_3$ is exactly $Ax$. Part (a) shows that this vanishes only when all three coefficients vanish, which is the definition of column independence. Hence $A$ has column rank three.

Writing the columns as $a_1,a_2,a_3$, matrix multiplication givesThe column space is the linear span of these columns, so this particular linear combination belongs to it. The assertion holds for every vector of coefficients $y$.

If $Ax=b$ has a solution, the multiplication identity from part (c) expresses $b$ as a linear combination of the columns, so $b\in \mathrm{Col}(A)$.

Conversely, if $b$ lies in that column space, its definition supplies scalars $x_1,x_2,x_3$ with $b=x_1{a}_1+x_2{a}_2+x_3{a}_3$. Put those scalars into the column vector $x$. Then $Ax=b$. This proves both directions of the claimed equivalence.

The Gram-Schmidt process first gives $u_1=a_1=(1,1,1,1{)}^T$, of norm two. Next $a_1^T{a}_2/(a_1^T{a}_1)=2$, soFor the third column, both coefficients onto $u_1,u_2$ equal one, givingThese three nonzero vectors are mutually orthogonal and each has norm two. The resulting orthonormal basis is

Collect the orthonormal vectors as columns and compute $R=Q^{T}A$. This gives the thin QR decompositionThe inner products in part (e) prove $Q^{T}Q=I_3$; the column identities $a_1=2q_1$, $a_2=4q_1+2q_2$, $a_3=2q_1+2q_2+2q_3$ prove $A=QR$.

Substitute the QR decomposition into the normal equations:The diagonal of $R$ is nonzero, so $R^T$ is invertible. Cancel it algebraically to obtainCompute the three inner products in $Q^{T}b$, then use back substitution in this upper triangular matrix. There is no need to form an inverse or explicitly construct $A^{T}A$. The orthogonal projection of $b$ onto the column space is $Q{Q}^{T}b$; its orthogonal residual proves that this solution minimizes $\Vert Ay-b{\Vert }_2$.