# If $AB=C$ and $C_{n \times m}$ has $n$ linearly independent columns, then $A$ is invertible

From Hubbard & Hubbard:

Let $$A$$ be an $$n \times n$$ matrix, let $$B$$ be an $$n \times m$$ matrix, and let $$C$$ be an $$n \times m$$ matrix. The matrices satisfy the relation $$AB=C$$. $$C$$ has $$n$$ linearly independent columns. Prove that $$A$$ is invertible.

Here is my solution for the special case when $$m=n$$: Since $$C$$ is square and its columns are linearly independent, $$C$$ is invertible. So we can write $$ABC^{-1}=I$$. So $$A$$ is invertible.

Unfortunately, this method clearly does not generalize at all to the case when $$m \neq n$$! How do you solve the problem in general? Any hints or solutions would be appreciated!

• What about $A=\pmatrix{1&0\\1&0}$, $B=\pmatrix{1\\1}=C$? – Jens Schwaiger Jun 2 '20 at 4:01
• @PrudiiArca: Not anymore! 😂 – Jens Schwaiger Jun 2 '20 at 4:05
• @JensSchwaiger whoops! The problem was supposed to require $C$ to have $n$ linearly independent columns. I have edited my post. Nice catch – Math2718 Jun 2 '20 at 4:08

Just pick $$n$$ linearly independent columns in $$C$$ and delete the other columns to get $$C'$$. Similarly delete the corresponding columns of $$B$$ to get $$B'$$. Then $$AB'=C'$$ and you have already shown this implies $$A$$ invertible.
If you know about the rank of a matrix you can use that $$C$$ has rank $$\geq n$$. Hence $$n \leq \operatorname{rk}C = \operatorname{rk} AB \leq \min\{\operatorname{rk}A,\operatorname{rk}B\}$$ shows that $$A$$ has rank $$n$$ and thus is invertible.
• $\operatorname{rk} AB =\leq\min\{\operatorname{rk}A,\operatorname{rk}B\}$? – Jens Schwaiger Jun 2 '20 at 4:19
Since, $$C$$ has $$n$$ linearly independent columns and has $$m$$ columns in total, $$m\ge n$$. Now, let $$B=[b_1,b_2,....,b_m]$$(columnwise). Then, the set $$S=\{Ab_1,Ab_2,....Ab_m\}$$ (distinct ones among them) has $$n$$ linearly independent vectors. But, since $$S\subseteq \text{image}(A)$$, we conclude that $$\text{image}(A)$$ has $$n$$ linearly independent vectors. Thus, $$\text{rank}(A)=n$$. Hence, $$A$$ also has $$n$$ linearly independent vectors. Thus, $$A$$ is invertible.