# (homework) Proving that a product of two matrices is in RREF

From Anton's Elementary Linear Algebra 8e Chapter 1.5, #14:

Prove that if $A$ is an $m\times n$ matrix, there is an invertible matrix $C$ such that $CA$ is in reduced row-echelon form.

I know that if $A$ is invertible, then $CA$ is also invertible and hence can be reduced into RREF. But... I don't think that's the case because $A$ is not a square matrix.

By using some algebra, I used the following equations:

$$C^{-1}C = I_m\\ E_1 E_2 ... E_k C = I_m$$

to get:

$$C^{-1} = E_1 E_2 \cdots E_k\\ E_1 E_2 \cdots E_k CA = I_m A$$

I guess the very last equation I got says something like... "When you apply the same row operations used to find the identity matrix from $C$ on $CA$, it gives you a matrix $A$."

I don't think this answers the question I am given, and so I need your help!

• Do you know how to perform the (manual) transformations to convert a matrix into RREF form? You then need to check that all of those transformations can be represented by an $E_i$ which is invertible. – Calvin Lin Feb 17 '14 at 7:50
• Is there a way to prove without using any manual transformation? – Brian Choi Feb 17 '14 at 7:55
• I think what Calvin means is that the usual operations you do to a matrix to bring it to rref are really matrix multiplications --- indeed, I expect that's what your unexplained matrices $E_1,\dots,E_k$ are. – Gerry Myerson Feb 17 '14 at 8:33

For any $m \times n$ matrix $A$ \begin{align} A &= IA \\ &\text{Every elementary row operation corresponds to left multiplication by an elementary matrix} \\ A' &= E_1A \\ A'' &= E_2 E_1 A \\ &\text{At the end of the process, we get }\\ rref(A) &= E_n \dots E_1 A \text{ for some finite } n \end{align}
Now $E_n \dots E_1$ is a product of invertible matrices and is hence invertible and that's the required matrix $C$.