Invertibility of Mixing Matrix $M$ in $A=CMR$

I'm interested in solving the following problem from Strang's Linear Algebra and Learning from Data:

If $C$ and $R$ contain bases for the column space and row space of $A$, why does $A=CMR$ for some square invertible matrix $M$?

In this context $A$ is an arbitary rectangular $m \times n$ matrix, $C$ is $m \times r$ and $R$ is $r \times n$. As $C^TC$ and $RR^T$ are both invertible, one finds that $$M=(C^TC)^{-1} C^TAR^T(RR^T)^{-1}. $$ This $M$ is evidently $r \times r$, and I could get invertibility by showing that $C^TAR^T$ is invertible. However, I couldn't show that. The results of rank of a product I'm aware of don't hold in this case. Also the implication $C^TAR^T x=0 \implies x=0$ proved too difficult for me.

Any advice on proving $M$ is invertible? Thanks.

Solution 1:

Notation

For clarity, let's define $A = CR$ and $A = CMR^*$ to disambiguate the $R$'s.

Proof by using a property of ranks

A property of ranks states $rank(AB) \le min(rank(A),rank(B))$.

In our case,

$$ \begin{align} rank(MR^*) &\le min(rank(M),rank(R^*)) \\ rank(R) &\le min(rank(M),rank(R^*)) \\ r &\le min(rank(M),r) \\ \end{align} $$

because

• $R*$, like $R$, has $r$ independent rows, by construction
• $M$ is $r \times r$
• $rank(M) = r$ is the only value that fits the inequality above

Since $M$ is full-rank, it is invertible.