I am looking for an intuitive explanation as to why/how row rank of a matrix = column rank. I've read the proof on Wikipedia and I understand the proof, but I don't "get it". Can someone help me out with this ?
I find it hard to wrap my head around the idea of how the column space and the row space is related at a fundamental level.
On
Maybe this helps a bit with the intuition: When you transpose a matrix you don't change the dimension of the image. But when you transpose a matrix, the column rank becomes the row rank and vice versa. As the dimension of the image is the column rank those are equal.
On
Define the rank of a matrix $A$ as the largest size of any square submatrix (minor) with non-null determinant. Then if you see the columns of $A$ as vectors, the rank of $A$ can be thought of as the maximal number of linearly independent such vectors. Finally, note that $det(M)=det(M^T)$, and if $M$ is a minor of $A$, then $M^T$ is a minor of $A^T$.
On
One way to view the rank $r$ of a $n\times m$ matrix $A$ with entries in a field $K$, is that it is the smallest number such that one can factor the linear map $f_A:K^m\to K^n$ corresponding to $A$ through an intermediate space of dimension$~r$, in other words, as a composition $K^m\to K^r\to K^n$ (taking $C$ and $B$ as the matrices corresponding to the two steps, this means that one has a decomposition $A=BC$ of $A$ as the product of a $n\times r$ and a $r\times m$ matrix). Now one can always factor $f_A$ though the image $\operatorname{Im}f_A\subseteq K^n$, as $K^m\to\operatorname{Im}f_A\hookrightarrow K^n$, and on the other hand this image can never have a dimension larger than a space through which $f_A$ factors; therefore the rank is equal to $\dim\operatorname{Im}f_A$. But that dimension is equal to the maximal number of independent columns of $A$, its column rank.
On the other hand one can view the rows of $A$ as linear functions on $K^m$ that describe the coordinates of $f_A(x)$ as a function of $x$, and the row rank $s$ is the maximum number of independent such functions; once such an independent set of $s$ independent rows is chosen, the remaining coordinates of $f_A(x)$ can each be described by a fixed linear combination of the chosen coordinates (because their rows are such linear combinations of the chosen rows). But this means that one can factor $f_A$ through $K^s$, with the map $K^s\to K^n$ reconstructing the dependent coordinates. The chosen coordinates are independent, so there is no nontrivial relation between them, and the map $K^m\to K^s$ is therefore surjective. This means that $f_A$ cannot factor through a space of smaller dimension than $s$, so the row rank $s$ is also equal to the rank of $A$.
Instead of that separate argument involving the row rank, you can also interpret the row rank of $A$ as the column rank of the transpose matrix $A^t$. Now one can factor $A=BC$ if and only if one can factor $A^t=C^tB^t$; then the minimal $r$ such that one write $A=BC$ with $B\in M_{n,r}$ and $C\in M_{r,m}$ (the column rank of $A$) obviously equals the minimal $r$ such that one write $A^t=C^tB^t$ with $C^t\in M_{m,r}$ and $B^t\in M_{r,n}$ (the column rank of $A^t$, and row rank of $A$).
On
Consider an $ m \times n $ matrix $ A = (a_{ij}) $. By row reduction, there exist elementary matrices $ E_1, \cdots ,E_p$ such that $ E_p \cdots E_1 A $ is a step matrix $ A' $.
[The first non-zero entry of a row, if exists, is called a pivot of that row. For an $ m \times n $ matrix $ A $, we'll denote it's rows by $ A_{1*}, \cdots, A_{m*} $ and columns by $ A_{*1}, \cdots, A_{*n} $. A matrix $ A $ is in step form when it's zero rows (if any) are at the bottom, and pivot indices $ j_1, \cdots, j_r $ of non-zero rows $ A_{1*}, \cdots , A_{r*} $ satisfy $ j_1 < j_2 < \cdots < j_r $ . Step matrices are also called row echelon matrices]
Say $ A' $ has $ r $ non-zero rows with pivot indices $ j_1 < \cdots < j_r $.
For any elementary matrix $ E $, $ A \mapsto EA $ preserves row space (i.e. span of matrix rows). So especially row rank (i.e. dimension of row space) of $ A $ is row rank of $ A' $, which is $ r $.
Now let's think of the column rank of $ A $. Here we'll be considering only columns, so let's take $ A_j $ to just mean column $ A_{*j} $. For any elementary matrix $ E $, $ ( A_{i_1}, \cdots, A_{i_k} ) $ is a basis of column space of $ A $ if and only if $ ( EA_{i_1}, \cdots, EA_{i_k} ) $ is a basis of column space of $ EA $, so we need only focus on the column space of $ A' $. But $ ( A'_{j_1}, \cdots, A'_{j_r} ) $ is a basis of column space of $ A' $, hence $ (A_{j_1}, \cdots, A_{j_r}) $ is a basis of column space of $ A $. Especially column rank of $ A $ is also $ r $.
To summarise, an elementary row operation on $ A $ preserves both row space and dimension of column space, so we need only look at row and column ranks of its step form $ A' $. But both of these are just the number of pivots of $ A' $.
On
Since the rows of $A$ are the columns of the transpose of $A$, denoted $A^{t}$, the row space of $A$ equals the column space of $A^{t}$. Define $\operatorname{rank}(A)$ to mean the column rank of $A$: $\operatorname{col rank}(A) = \dim \{Ax: x \in \mathbb{R}^n\}$.
First we show that $A^{t}Ax = 0$ if and only if $Ax = 0$. This is standard linear algebra: If $Ax = 0$, then multiplying both sides by $A^{t}$ shows $A^{t}Ax = 0$. To prove the other direction, argue as follows:
$$A^{t}Ax=0 \implies x^{t}A^{t}Ax=0 \implies (Ax)^{t}(Ax) = 0 \implies Ax = 0$$
Therefore, the columns of $A^{t}A$ satisfy the same linear relationships as the columns of $A$. This is a very crucial observation: If $Bx=0 \implies Ax=0$ then any linear relationship among the columns of $B$ are satisfied by the corresponding columns of $A$. If, in addition, $Ax=0 \implies Bx=0$ then the columns of the two matrices satisfy exactly the same linear relationships.
Define $B := A^{t}A$ (just for convenience of notation) and note that $B$ has the same number of columns as $A$. Suppose that $\{b_{j_1},\ldots,b_{j_r}\}$ is any collection of $r$ linearly independent columns in $B$. Now consider the corresponding columns in $A$: $\{a_{j_1},\ldots, a_{j_r}\}$. Then these must also be linearly independent. Why? Suppose, if possible, they were linearly dependent. Then one column from that set could be expressed as a linear combination of the others. But this would mean that the $\{b_{j_1},\ldots,b_{j_r}\}$ will satisfy the same linear relationship, which contradicts their linear independence. This means that $A$ must have at least as many linearly independent columns as $B$. We can now reverse the argument exactly as above by considering a collection of linearly independent columns of $A$ and showing that $B$ must have at least as many. Therefore, $A$ and $B$ have the same number of linearly independent columns; hence, $\operatorname{col rank}(A) = \operatorname{col rank}(A^{t}A)$.
Next, observe that each column of $A^{t}A$ is a linear combination of the columns of $A^{t}$ so $\operatorname{col sp}(A^{t}A)$ is a subspace of $\operatorname{col sp}(A^{t})$. Therefore, $\operatorname{col rank}(A^{t}A) \leq \operatorname{col rank}(A^{t})$ and, from what we proved above, $\operatorname{col rank}(A) \leq \operatorname{col rank}(A^{t})$. This holds for any matrix, so we can simply apply the result to $A^{t}$ to get the reverse inequality: $\operatorname{col rank}(A^t) \leq \operatorname{col rank}((A^{t})^t) = \operatorname{col rank}(A)$. This proves $\operatorname{col rank}(A) = \operatorname{col rank}(A^{t})$. Since $\operatorname{col rank}(A^{t})$ is the row rank of A, we are done.
On
Given a $\DeclareMathOperator{\row}{row} \DeclareMathOperator{\col}{col} \DeclareMathOperator{\rowrank}{rowrank} \DeclareMathOperator{\colrank}{colrank}m\times n$ matrix $A$, we can consider "factorisations" of $A$ into a product of matrices $B$ and $C$, where $B$ has dimension $m \times r$, and $C$ has dimension $r \times n$. From the definition of matrix multiplication, we can derive the following two facts (I use $\col_j$ to denote the $j$-th column of $A$, and similarly for rows): $$ \begin{align} \col_j(A) &= \sum_{i=1}^{r}c_{ij}\col_i(B) \tag1\label1 \, , \\[4pt] \row_i(A) &= \sum_{j=1}^{r}b_{ij}\row_j(C) \tag2\label2 \, . \end{align} $$ The column space of $A$ is thus a subspace of the column space of $B$, and the row space of $A$ is a subspace of the row space of $C$. Hence, $$ \DeclareMathOperator{\colrank}{colrank} \DeclareMathOperator{\rowrank}{rowrank} \begin{align} &\colrank(A) \le \colrank(B) \le \text{no. of columns in $B$} = r \, , \\[3pt] &\rowrank(A) \le \rowrank(C) \le \text{no. of rows in $C$} = r \, . \end{align} $$ Let us now consider "minimal" factorisations of $A$, where we try to make $r$ as small as possible. It is in fact always possible to find a factorisation where $r=\colrank(A)$: let $\mathbf{b}_1,\dots,\mathbf{b}_r$ be a basis of the column space of $A$, and put $\col_{j}(B)=\mathbf b_j$. Then, $\eqref1$ determines a unique $C$ such that $A=BC$. Hence, if $r$ is minimal, then $r=\colrank(A)$. Similarly, we can always find a factorisation where $r=\rowrank(A)$: let $\mathbf c_1,\dots,\mathbf c_{r}$ be a basis of the row space of $C$, and put $\row_j(C)=\mathbf c_j$. Then, $\eqref2$ determines a unique $B$ such that $A=BC$. Hence, if $r$ is minimal, then $r=\rowrank(A)$, and the result follows.
You can apply elementary row operations and elementary column operations to bring a matrix $A$ to a matrix that is in both row reduced echelon form and column reduced echelon form. In other words, there exist invertible matrices $P$ and $Q$ (which are products of elementary matrices) such that $$PAQ=E:=\begin{pmatrix}I_k\\&0_{(n-k)\times(n-k)}\end{pmatrix}.$$ As $P$ and $Q$ are invertible, the maximum number of linearly independent rows in $A$ is equal to the maximum number of linearly independent rows in $E$. That is, the row rank of $A$ is equal to the row rank of $E$. Similarly for the column ranks. Now it is evident that the row rank and column rank of $E$ are identical (to $k$). Hence the same holds for $A$.