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)]$$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.