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

The $m$ columns of $L$ form a basis of $\ker A^{\top }$, so that null space has dimension $m$. The rank-nullity theorem applied to $A^{\top }:{\mathbb{R}}^n\to {\mathbb{R}}^n$ gives $\mathrm{rank}{A}^{\top }=n-m$. A matrix and its transpose have equal matrix rank, hence

If $A^{\top }x=0$, the vector $x$ belongs to the null space for which the columns of $L$ are a basis. It is therefore a linear combination of those columns, so $x=Ly$ for some $y\in {\mathbb{R}}^m$. Conversely, each column is annihilated by $A^{\top }$, hence $A^{\top }L=0$ and $x=Ly$ implies $A^{\top }x=0$. ThusThe coordinate vector $y$ is unique because the columns of $L$ are linearly independent.

The analogous null space statement isHere the rank-nullity theorem and (a) ensure that $\ker A$ also has dimension $m$.

The columnwise null space conditions say $A^{\top }L=0$ and $AR=0$. ThereforeBoth right-hand sides are the $n\times n$ zero matrix.

Both $L$ and $R$ have $m$ linearly independent columns. The Gram matrix $R^{\top }R$ is invertible becauseConsequently $R^{\top }$ is a surjective linear map: for any $y\in {\mathbb{R}}^m$, the choice $x=R(R^{\top }R{)}^{-1}y$ satisfies $R^{\top }x=y$. HenceThe latter image of a linear map has dimension $m$, giving $\mathrm{rank}B=m$. If $m=0$, $B=0$ and the conclusion is immediate. This argument explains why the product retains its full possible matrix rank; a general product of two matrices need not do so.

Expand the product and use (d) together with its transpose:Indeed $A{B}^{\top }=0$ and $B{A}^{\top }=(A{B}^{\top }{)}^{\top }=0$.

Fix one common eigenvector $v\ne 0$, and write $A{A}^{\top }v=\lambda v$ and $B{B}^{\top }v=\mu v$. By (d),so $\lambda \mu v=0$ and at least one of the two eigenvalues is zero.

To exclude both being zero, use the kernel of a Gram product identity:If both products annihilate $v$, then $A^{\top }v=B^{\top }v=0$. By (b), $v\in \mathrm{im}L$, and by (e), this is $\mathrm{im}B$. On the other hand, $B^{\top }v=0$ makes $v$ orthogonal to every vector in $\mathrm{im}B$. In particular $v$ is orthogonal to itself, so $\Vert v{\Vert }^2=0$ and $v=0$, a contradiction.

Therefore each specified common eigenvector belongs to exactly one of $\ker (A{A}^{\top })$ and $\ker (B{B}^{\top })$. Both eigenvalues are nonnegative by the displayed squared-norm identities, so the other eigenvalue is strictly positive. This is the spectral mechanism behind orthogonal null-space completion of a square matrix.