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

True. The rank-nullity theorem gives $\dim \mathcal{N}(A)=n-r=0$. The only vector in this zero-dimensional kernel of a linear map is the zero vector.

False. Take $A=(1,0{)}^T$, an $m=2$, $n=1$ matrix of matrix rank one, and $b=(0,1{)}^T$. Then $Ax=(x,0{)}^T$ never equals $b$. Full column rank implies injectivity, not surjectivity onto a larger codomain.

True. A square matrix with matrix rank $n$ is invertible, and its transpose has the same rank. Applying the rank-nullity theorem to both $A$ and $A^T$ gives nullity zero in each case, so both kernels are $\{0\}$.

False. Triviality of $\mathcal{N}(A)$ gives $r=n$, while triviality of $\mathcal{N}(A^T)$ gives $r=m$ because transpose preserves matrix rank. Both conditions therefore force $m=n$, contradicting the stated unequal dimensions.

Choose $r$ independent columns of $A$ that form a basis of its column space, and put them in $B\in {\mathbb{R}}^{m\times r}$. For each column $a_j$ of $A$, let $c_j$ be its coordinate vector in that basis; put these coordinate vectors in $C\in {\mathbb{R}}^{r\times n}$. The column equations $a_j=B{c}_j$ give $A=BC$.

By construction $B$ has full column rank $r$. The columns of $C$ corresponding to the selected basis columns are the standard vectors of ${\mathbb{R}}^r$, so $C$ has full row rank $r$. This proves the requested rank factorization. When $r=0$, $A=0$ and the corresponding empty-column and empty-row factors have the required shapes and rank zero.

Not unique in general. For any invertible $r\times r$ matrix $S$,is another rank factorization, with the same full ranks. This is a change of basis in the intermediate $r$-dimensional space. For example, even $[1]=[1][1]=[2][1/2]$ has different full-rank factors. Once a particular ordered basis $B$ is fixed, its coordinate matrix $C$ is unique; it is the basis choice that creates the freedom.

For the first matrix choose its single independent column:Their product has every column equal to $B_1$, and both factors have rank one.

For the second matrix, the first and third columns are independent and the second equals the first, givingMultiplication reconstructs the stated matrix. The first factor has independent columns and the second has independent rows, so both have matrix rank two, as required for a rank factorization.

The two square products can have different sizes, but their matrix traces are both the same finite double sum:Interchanging two finite sums and commuting their scalar factors is valid over the real numbers. No commutation of the matrix products themselves is asserted. This proves the cyclic property of the trace in the rectangular-factor case.

Let $r=\mathrm{rank}(A)$. If $r=0$, the matrix is zero and the identity is immediate. Otherwise choose the rank factorization $A=BC$ from part b. The column space of $B$ is the image of $A$.

An idempotent matrix acts as the identity on its image: if $u=Av$, then $Au=A^{2}v=Av=u$. Applying this to each column of $B$ gives $AB=B$. Substituting $A=BC$ yields $B(CB-I_r)=0$. Since $B$ has full column rank, the represented map is injective, so each column of $CB-I_r$ is zero. Thus $CB=I_r$.

Now the rectangular cyclic property of the trace givesThis proves that the trace of an idempotent equals its rank using the supplied factorization method. Orthogonality of the projection is unnecessary: the argument applies to every real idempotent matrix.