# 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:

1. Independence of vectors
2. The general idea of Gauss-Jordan Elimination and reduced row echelon form
3. 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)]$$