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 / Linear algebra

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.

Take $V={\mathbb{R}}^2$ and the linear map $h(x,y)=(x,0)$. ThenThese two vector subspaces have zero intersection and together span ${\mathbb{R}}^2$, so $V=\mathcal{R}(h)\oplus \mathcal{N}(h)$ as a direct sum of vector spaces.

Take $V={\mathbb{R}}^2$ and the linear map $h(x,y)=(y,0)$. ThenTheir intersection is nonzero and their sum is only one-dimensional. Hence $V\ne \mathcal{R}(h)\oplus \mathcal{N}(h)$. This nilpotent linear map has $h^2=0$, illustrating why taking sufficiently high powers changes the situation.

For $v\in \mathcal{R}(h^{m+k})$, choose $u$ with $v=h^{m+k}u=h^m(h^{k}u)$. Thus $v\in \mathcal{R}(h^m)$, provingThis is the decreasing-image part of stabilization of images of powers of a linear map. The convention $h^0={\mathrm{id}}_V$ includes $m=0$ and $k=0$.

Apply $h$ to both sides of $\mathcal{R}(h^m)=\mathcal{R}(h^{m+1})$. Because $h(\mathcal{R}(h^j))=\mathcal{R}(h^{j+1})$, we obtain $\mathcal{R}(h^{m+1})=\mathcal{R}(h^{m+2})$. Repeating this argument proves equality at every later step. More formally, an induction on $k$ givesThe base case is $k=0$; the induction step follows from applying the linear map $h$ and then the assumed first equality. Thus one equality permanently stabilizes the descending sequence of images of a linear map.

The dimensions of the nested images of a linear mapcan strictly decrease at most $n$ times. If all the first $n$ inclusions are strict, $\mathcal{R}(h^n)=0$ and is stable. Otherwise an earlier equality occurs and (d) makes every subsequent image equal. Thus in all casesBy the rank-nullity theorem and inclusion of the null spaces, this also gives $\ker h^n=\ker h^{2n}$. If $v\in \mathcal{R}(h^n)\cap \ker h^n$, write $v=h^{n}u$. Then $0=h^{n}v=h^{2n}u$, so $u\in \ker h^{2n}=\ker h^n$ and $v=0$. Hence the intersection is zero. Finally the rank-nullity theorem givesZero intersection and this dimension sum proveThis is the finite-dimensional Fitting decomposition. It includes the zero-dimensional case, for which $V=0$ and the assertion is immediate.

Let $E_{ij}$ denote a matrix unit, with its only nonzero entry equal to one in row $i$, column $j$. A basis for the vector space of real skew-symmetric matrices isEach upper-triangular entry is free, its reflected lower-triangular entry is its negative, and every diagonal entry is zero. This is the basis of the space of real skew-symmetric matrices.

Using linearity and involutivity of the matrix transpose,Therefore $B-B^{\top }$ is a skew-symmetric matrix.

Split $B$ into its symmetric part and skew-symmetric part:Taking the transpose gives $S^{\top }=S$ and $K^{\top }=-K$. Thus $S$ is a symmetric matrix and $K$ a skew-symmetric matrix. These formulas also show uniqueness, since a real matrix that is both symmetric and skew-symmetric is zero.

If $A^{\top }=-A$, then the dot product satisfiesConversely, the assumed dot product identity gives $x^{\top }(A^{\top }+A)y=0$ for every $x,y$. Take $x=e_i$ and $y=e_j$ from the standard basis: every entry of $A^{\top }+A$ is zero. Hence $A^{\top }=-A$, proving the equivalence.

If $A$ is a skew-symmetric matrix, the scalar $x^{\top }Ax$ equals its own transpose, soand it is zero over the real numbers.

Conversely, suppose the quadratic form $x^{\top }Ax$ vanishes for every real vector. Substituting $x=e_i$ gives $a_{ii}=0$. Substituting $x=e_i+e_j$ gives $a_{ij}+a_{ji}=0$ for $i\ne j$. Therefore $A^{\top }=-A$. This proves the quadratic-form criterion for a skew-symmetric matrix:

For a real eigenvalue $\lambda$, choose a nonzero real eigenvector $v$ with $Av=\lambda v$. By (e),Since $v^{\top }v=\Vert v{\Vert }^2>0$, $\lambda =0$. If eigenvectors were initially allowed to be complex, the real matrix $A-\lambda I$ has a nonzero real null space whenever it has a nonzero complex null space, so this choice of $v$ remains justified.

The determinant is invariant under transpose, while multiplying all $n$ rows by $-1$ multiplies it by $(-1{)}^n$. Thus, for odd integer $n$,Over the real numbers, this forces $\det A=0$, so $A$ is a singular matrix. This is the odd-dimensional skew-symmetric singularity theorem.

If $(I+A)x=0$, take its dot product with $x$ and apply (e):Hence $x=0$. A square matrix with zero null space is an invertible matrix by the rank-nullity theorem. Therefore $I+A$ is nonsingular. This proves invertibility of identity plus a real skew-symmetric matrix.