Proof for Column Space of matrix and its reduced row echelon having the same dimension After having come across many proofs, I realized that all of them use different ways to prove the same thing. I wanted to use a proof which uses assumptions that were relatively easy, or perhaps the ones that I encountered earlier in a course on Linear Algebra. And I wanted it to rely on other proved theorems less, and be more self-contained. 
Here's my proof, I am not sure if it is correct, and all improvements are welcome (in terms of making it simpler, or using some technique which makes it more intuitive or makes one learn more while going through it):
Prerequisites to understanding it:


*

*Independence of vectors

*The general idea of Gauss-Jordan Elimination and reduced row echelon form

*The idea of the four subspaces



Let $A \in \mathbb{R}^{m\times n}$ ($m\times n$ matrix), and $R$ be
  its reduced row echelon form. Assume that $A \rightarrow R$ does
  not require any row-exchanges.
$\textbf{Claim 1: }$ For $E_{net}A = R$, $E_{net}$ is invertible.
The conversion (Gauss-Jordan elimination) can be viewed as
  performing Gaussian elimination first - finding the pivots, creating
  zeros below the pivots followed by normalizing the pivots to $1$ and
  then reducing this to the reduced-row echelon form by creating zeroes
  above the pivots.  $$(E_bDE_a)A = R$$ $E_a$ is the product
  $E_{a1}E_{a2}...$, where each of the $E$ performs one elimination
  step, i.e. produces a zero beneath a pivot by adding a multiple of an
  upper row to a lower row. $E_b = E_{b1}E_{b2}...$ does a similar
  process but aims to produce zeros above the pivots and adds a multiple
  of a lower row to an upper row. $D$ merely normalizes the pivots to
  $1$ by dividing each row by its pivot.
Each $E$ can be written as a square $I \in \mathbb{R}^{m \times
m}$ with its $ij^{th}$ element ($i \neq j$) some constant $c$. This
  $E$ then multiplies $c$ times the $j^{th}$ row of $A$ to the $i^{th}$
  row of $A$, as would be apparent from the way it is written. For every
  such matrix $E$, there is another matrix $E^{-1}$ which reverses this
  operation, i.e. subtracts $c$ times the $j^{th}$ row from the $i^{th}$
  row of $EA$ restoring $EA$ to $A$, i.e. $E^{-1}E$ is $I$. Using the
  above construction, $E^{-1}$ has the sign of the constant $c$
  reversed.
$D$ can be thought of as a diagonal matrix with non-zero entries on
  the diagonals, specifically $ii^{th}$ element is $1/\text{pivot}_i$
  ($1$ in case the pivot does not exist). $D^{-1}$ always exists, which
  is simply $D$ with all its diagonal values reciprocated, i.e.,
  $\text{pivot}_i$.
Therefore, for $E_bDE_a$ always has an inverse, namely
  $E_a^{-1}D^{-1}E_b^{-1}$
$\textbf{Claim 2: }$For any invertible square matrix $A \in
 \mathbb(R)^{m\times m}$, if $x,y \in \mathbb(R)^m$ are independent, so
  are $Ax, Ay$
Let $x,y \in \mathbb{R}^m$ be independent. Assume $Ax, Ay$ are
  dependent. Then, from the definition of independence, $cAx + dAy = 0$
  for some $c,d \neq 0$ and $c,d \in \mathbb{R}$. Multiplying both sides
  by $A^{-1}$, and using the distributive property and linearity of
  matrix multiplication, we get $cx + dy = 0$, which contradicts our
  original claim.
$\textbf{Final Proof:}$
Let $dim[C(A)]$, where $C(A)$ represents the column space of $A$, be
  $k$. Choose $x_1, x_2, ... x_k$ such that $Ax_1, Ax_2, ... Ax_k$ gives
  us the basis for $C(A)$. Since $E_{net}$ is invertible (claim 1), we
  also have $EAx_1, EAx_2... EAx_k$ independent (claim 2). 
Therefore, $C(R)$ has at least $k$ independent vectors ($Rx_1, Rx_2
 ... Rx_k$). That implies, $$dim[C(A)] \leq dim[C(R)]$$
Let $dim[C(R)]$, where $C(R)$ represents the column space of $R$, be
  $h$. Choose $x_1, x_2, ... x_h$ such that $Rx_1, Rx_2, ... Rx_h$ gives
  us the basis for $C(R)$. Since $E_{net}^{-1}$ is invertible, we also
  have $E^{-1}Rx_1, E^{-1}Rx_2... E^{-1}Rx_h$ independent (claim 2). 
Therefore, $C(A)$ has at least $h$ independent vectors ($Ax_1, Ax_2
> ... Ax_h$). That implies, $$dim[C(R)] \leq dim[C(A)]$$
Both the inequalities gives us:
$$dim[C(R)] = dim[C(A)]$$

 A: For many the "reason" row rank and column rank agree is because they both count the same thing.  I.e. the number of independent vectors in the image of a linear map.  
My point is you can summarize the idea by actually getting rid of the matrix entirely and focusing on the linear map.  That removes lots of technical notation (subscripts, and implicit ordering on the basis, notation for rows and columns, elementary matrices...).  The main idea is to see that they both count something, and that that something is the same thing, hence equal.  It is not to say one shouldn't then endeavor to connect it back to matrices, but perhaps best to hold on to a simple idea and evolve it to the more complex than the other way around.
So to connect the two...
...either you eliminate rows to produce the same image (row reduction) or you eliminate columns which are obtained as combinations of others.  (Again I'm planting a simple idea first which needs some fleshing out but takes again a simple memorable step.  One stops when the simple step seems enough to be clear to you or your audience.)  Either way you are describing a final state where the number of independent rows/columns is the same. 
With this proof approach you can even go further. E.g. you can conclude that fully row & column reducing produces a matrix of pivots only and even that has the same number. 
Said more bluntly, intuition in linear algebra seems to come through with fewest definitions and distractions when you use linear, rather than matrix.  Abstract away the parts that are mechanics and easily reproduced.  What you are left with is what essential ingredient is behind the claim.
