Matrix rank inequality

Question

Let $A,B$ be some real matrices, each $n\times n$. Given that $$rank(A) + rank(B) \le n,$$ show that there exists a real $n \times n$ matrix $C$, with $rank(C) = n$, such that $ACB = 0$.

I cannot figure out how to show that such a matrix exists. So far I have tried solving the problem using Forbenius inequality but I cannot prove that such a matrix exists. How I can approach such a problem?

Answer 1

What can you say about the rank of $B$ relative to the nullity of $A$?

Note that if $U$ and $W$ are any two subspaces of the same dimension, there's a full-rank map on $n$-space that sends $U$ to $W$. Proof: Pick a basis $u_1, \ldots, u_k$ of $U$; extend it by $ a_1, \ldots, a_{n+k}$ to a basis of $n$-space. Do the same for $W$. Now send $u_i$ to $w_i$ and $a_i$ to $b_i$ for each $i$ that makes sense, and you've defined the isomorphism.

Answer 2

I find it always a tiny bit easier to reason with concrete numbers. Also keeping in mind the 4 fundamental subspaces picture helps. So suppose $n=10$.

1) the last operation is A. Let's suppose $rank(A) = 8$ so that the nullspace of A has dimension $dim(N(A)) = 2$. Because we want the result of ABC to be 0 we need that BC ends in N(A). So this implies that the column space of BC is included in N(A). Let $a_1,a_2$ be a basis of $N(A)$ and extend it with a basis of the rowspace of A $an_3,an_4,...,an_{10}$ so that $a_1,a_2,an_3,an_4,...,an_{10}$ is a basis of $R^{10}$

2) the first operation is B. Let'suppose that $rank(B) = 2$ so that applying B makes you end in a 2-D columnspace. Let $b_1, b_2$ be a basis of the column space of B, and extend it to a basis of $R^{10}$ with $bn_3,bn_4,...,bn_{10}$ (a basis of the left-nullspace of B) so that $b_1, b_2, bn_3,bn_4,...,bn_{10}$ is a basis of $R^{10}$

3)So now we need to find a full-rank C that connects two 2-D subspaces of $R^{10}$: the column space of B and the nullspace of A. For this it is enough to have a C that sends $b_1$ on $a_1$, $b_2$ on $a_2$,$bn_3$ on $an_3$...,$bn_{10}$ on $an_{10}$. Let's stack side by side the b's in a n x n matrix $U = \begin{pmatrix}|&|&|&|&|\\b_1&b_2&bn_3&\dots&bn_{10}\\|&|&|&|&|\end{pmatrix}$ and the a's in a matrix $V = \begin{pmatrix}|&|&|&|&|\\a_1&a_2&an_3&\dots&an_{10}\\|&|&|&|&|\end{pmatrix}$. We are shooting for a matrix $C$ such that $CU=V$ . U is made of 10 independent columns so it is invertible so $C = CUU^{-1}=VU^{-1}$. Because $V$ and $U^{-1}$ have zero nullspace so has C (*) and hence rank(C) = 10.

Hopefully you can easily generalize.

(*) If A and B have zero nullspace, then $ABx = 0$ implies $Bx=0$ because nullspace of A is 0; implies $x = 0$ because nullspace of B is zero: So nullspace of AB is zero.