0
$\begingroup$

Given a matrix $A \in \mathbb{R}^{n \times m}$, how can I find a matrix $B \in \mathbb{R}^{k \times n}$ such that $\ker(B) = \text{im}(A)$?

This method would probably work, applying a transformation matrix to change to the standard basis, afterwards. However, if $m < n$ and $\ker(A) = \{ 0 \}$, this approach shouldn't work. Is there any alternative?

$\endgroup$
1
$\begingroup$

Say $A$ is rank $r$. Taking the SVD with singular values ordered from largest to smallest write $A=U \Sigma_A V^T$. Here I am taking the convention that $\Sigma_A$ is a $n \times m$ diagonal matrix.

The first $r$ columns of $U$ form a basis for the range of $A$. Write $U= (U_1 \ U_2)$ where $U_1 \in \mathbb{R}^{n \times r}$ so that the columns of $U_1$ form a basis for the range of $A$. Then set $$ B= W \Sigma_B \begin{pmatrix} U_2^T\\ U_1^T \end{pmatrix} $$ where $\Sigma_B$ is an $n \times n$ and diagonal and its last $r$ diagonal entries are equal to zero, and the other diagonal entries are nonzero and where $W$ is any one-to-one matrix. Then the kernel of $B$ is equal to the kernel of $$\Sigma_B \begin{pmatrix} U_2^T\\ U_1^T \end{pmatrix} $$ which you can show is equal to the range of $A$. In particular, any column of $U_1$ is in the kernel of $B$, and any column of $U_2$ is orthogonal to the kernel of $B$.

$\endgroup$
  • $\begingroup$ Thank you. I think this is similar to the approach I just used, using the complete QR decomposition. $\endgroup$ – McLawrence Oct 7 '19 at 14:24
  • $\begingroup$ Surely one can do this without invoking any (singular value or other) decomposition, just by using Gaussian elimination. $\endgroup$ – Marc van Leeuwen Oct 10 '19 at 10:06
2
$\begingroup$

This is impossible in general.

Consider any $3 \times 1$ matrix $A$. Now you are asking for an $1 \times 3$ matrix $B$ such that ker$(B)$ = im$(A)$. In particular, the kernel of $B$ should be 1-dimensional. But that is impossible, since the rank of $B$ is at most 1, and therefore due to the rank-nullity theorem, the kernel of $B$ has dimension at least 2.

$\endgroup$
  • $\begingroup$ In my counterexample $m < n$ holds. Do you mean you are interested in $n < m$? In that case Eric's answer works. Note that if $A$ has full rank $n$, then it is simple: $B = 0$. $\endgroup$ – Guus B Oct 7 '19 at 14:42
  • $\begingroup$ Okay, now I think I found the error in my thinking. The matrix $B$ does not have to be confined to $m \times n$. I just need a matrix for which the kernel equals the image of a given one. $\endgroup$ – McLawrence Oct 7 '19 at 14:50
1
$\begingroup$

This is easy, provided that $\def\rk{\operatorname{rk}}k\geq n-\rk A$ (but if $k<n-\rk A$ it is impossible , since $\rk B\leq k$ and by rank nullity $n=\dim(\ker(B))+\rk B=\rk A+\rk B$ which can be at most $\rk A+k<n$).

Assuming that, we want to find $B$ such that $BA=0$, in other words, each of the $k$ rows of $B$ describes a linear form $\def\R{\Bbb R}\R^n\to\R$ that vanishes on $\def\Im{\operatorname{Im}}\Im A$, and which rows span the space of all such linear forms. Transposing the equation $BA=0$ gives $A^t B^t=0$, so the columns of $B^t$ lie in the kernel of (the linear map with matrix) $A^t$, and span that kernel. So one just needs to find a basis of the space of solutions of the homogeneous system $A^t x=0$ for $x\in\R^n$ (which basis has $n-\rk A^t=n-\rk A$ elements, by rank nullity), and take their transposes as rows of $B$. In case $k>n-\rk A$, one can just complete with null rows to attain the required number $k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.