Finding the nullspace of full column rank matrix

change-of-basislinear algebra

Given tall matrix $D \in \mathbb{R}^{m \times n}, m>n $:
$$
D = \begin{bmatrix}B \\\ C\end{bmatrix}
$$

where $B \in \mathbb{R}^{n \times n}$ is invertible and $C \in \mathbb{R}^{k \times n}$ (so $k=m-n$).

I know that $D$ is full column rank and that $D^TD$ is invertible.
How do I got about finding the basis for the nullspace of $D^T$ in terms of $B$ and $C$?

Best Answer

Because $B$ is invertible, we find that $$ DB^{-1} = \pmatrix{B\\C}B^{-1} = \pmatrix{BB^{-1}\\ CB^{-1}} = \pmatrix{I\\CB^{-1}}. $$ We note that $[DB^{-1}]^T = B^{-T}D^T$ has the same nullspace as $D^T$. Thus, it suffices to find the nullspace of $$ [DB^{-1}]^T = \pmatrix{I & [CB^{-1}]^T} = \pmatrix{I & B^{-T}C^T} $$ We note that for $x \in \Bbb R^n$ and $y \in \Bbb R^k$, the block-vector $(x,y)$ is an element of the nullspace iff $$ \pmatrix{I & B^{-T}C^T} \pmatrix{x\\y} = 0 \implies x = -B^{-T}C^T y. $$ We can now obtain the desired basis as follows:

  1. Find a basis $\{y_1,\dots,y_p\} \subset \Bbb R^k$ for the nullspace of $C^T$. For each $y_i$, the block vector $v_i = (0,y_i) \in \Bbb R^m$ is a basis element for our nullspace of $D^T$.
  2. Extend this to a basis $\{y_1,\dots,y_p,y_{p+1},\dots,y_k\}$ of $\Bbb R^k$. For each $y_i$ with $i \geq p+1$, the block vector $v_i = (-B^{-T}C^Ty_i,y_i)$ is a basis element for our nullspace of $D^T$.

With that, the vectors $v_1,\dots,v_k$ give the basis that we're looking for.


If $C$ has full row-rank, then this gets even easier: the columns of the matrix $$ \pmatrix{B^{-T}C^{T} \\ -I} $$ form a basis for the nullspace of $D^T$.

Related Question