Prove that row rank of a matrix equals column rank

Let $A \in \mathbb{F}^{m \times n}$. How do you prove that row rank of a matrix equals column rank ?

This question has been addressed here and here, but the explanation in one case was descriptive and somewhat involved in the other. The answer below is an introductory-linear-algebra level answer.

There is an elegant proof here, https://en.wikipedia.org/wiki/Rank_(linear_algebra)#First_proof

But developing it on an example is better for intuition.

There are 2 equivalent views of the relationship between vectors:

• The column vectors view
• The rows: which are the coefficients you use to combine the column vectors

Take: $$ A = \begin{bmatrix}1 & 2 & 3 & -2\\0 & 1 & 1 & -1\end{bmatrix} $$ Note that the first 2 columns are independent and the 2 next columns are linear combinations of the first two. Structure looks like: $$ A=\begin{bmatrix}\alpha_1 & \beta_1 & \gamma(\alpha_1,\beta_1) & \delta(\beta_1)\\\alpha_2 & \beta_2 & \gamma(\alpha_2,\beta_2) & \delta(\beta_2)\end{bmatrix} $$ where $\gamma(x,y)=x+y$ and $\delta(x,y)=-x$

The column space

The $columnspace$ $C(A)$ lives in $R^2$ and is the set of all $A\vec x$ , where $\vec x=\pmatrix{\alpha&\beta&\gamma&\delta}^T$ is a vector of 4 coefficients applied to the columns: $$ C(A) = \alpha \pmatrix{1\\0}+\beta \pmatrix{2\\1}+\gamma\pmatrix{3\\1}+\delta\pmatrix{-2\\-1}\\ C(A) = \alpha \pmatrix{1\\0}+\beta \pmatrix{2\\1}+\gamma\pmatrix{1+2\\0+1}-\delta\pmatrix{2\\1} \\ C(A) = (\alpha+\gamma) \pmatrix{1\\0}+(\beta+\delta-\gamma) \pmatrix{2\\1} $$ So $C(A)$ is a 2-dimensional space that is spanned by the first 2 rows. Notice how actually only 2 coefficients out of 4 are really needed ...

Looking at the constraints on coefficients

The vector space of the coefficients $\vec x=\pmatrix{\alpha&\beta&\gamma&\delta}^T$ lives in $R^4$ but we should ask ourselves why was it that column 3 was a linear combination of column 1 and 2 ? It is because in all rows , the 3^rd^ coefficient (the $\delta$) is the same linear combination ($\alpha+\beta$) of the coefficients of the first 2 coefficients in the row. If you add another row to $A$ where the 3^rd^ coefficient ($\delta$) is not exactly the sum of the 2 first, then column 3 would no more be a linear combination of column 1 and column 2. Likewise, column 4 is a linear combination of the 2 first column, only because on all rows the 4^th^ coefficient is the opposite of the 2^nd^ coefficient.

So now we have another strictly equivalent way to say that column 3 and column 4 are linear combinations of column 1 and 2 but in term of rows:

All rows $(\alpha,\ \beta,\ \gamma,\ \delta)$ have the same structure $(\alpha,\ \beta,\ \alpha+\beta,\ -\beta)$

The row space

Note that the sum of 2 rows with structure $(\alpha,\ \beta,\ \alpha+\beta,\ -\beta)$ has still this structure. And that multiplying by a scalar also keeps the structure. So we could say that all rows in the $rowspace$ noted $C(A^T)$ have this structure: $$ C(A^T) = \pmatrix{\alpha\\ \beta\\ \alpha+\beta \\-\beta} \\C(A^T) = \alpha\pmatrix{1\\0\\1\\0} + \beta\pmatrix{0\\1\\1\\-1} $$

The whole $rowspace$ is generated by 2 vectors and hence has maximum dimension 2. In particular,$row\ 1 = 1\cdot(1,0,1,0) + 2 \cdot (0,1,1,-1)$ and $row\ 2 = 0\cdot(1,0,1,0) + 1 \cdot (0,1,1,-1)$ . Because of the placement of the zeros (that form an identity matrix) we can see that those 2 vectors are independent.

Sum up

So let's go back to the proof that the $dim(rowspace) = dim(colspace)$ applied to our matrix $A$.

1. We start with $dim(colspace)=r=2$ in $A$ .We suppose that it is because column 3 is some linear combination $\gamma(x,y)$ of column 1 and 2, and because column 4 is some linear combination $\delta(x,y)$ of same columns 1 and 2
2. Column 3 and 4 are combinations of column 1 and 2 exactly because all rows have the structure $(\alpha,\ \beta,\ \gamma(\alpha,\beta),\ \delta(\alpha,\beta))$ where $\gamma = c_1.\alpha + c_2.\beta$ and $\delta = k_1.\alpha + k_2.\beta$
3. The $rowspace$ is precisely the set of all 4-d vectors with structure $(\alpha ,\ \beta , \ c_1.\alpha + c_2.\beta , \ k_1.\alpha + k_2.\beta)$ . which is $\alpha.(1,\ 0 , \ c_1, \ k_1) + \beta.(0,\ 1,\ c_2,\ k_2)$
4. Because the $rowspace$ can be generated by $r$ vectors, its maximum dimension is $r=2$ so that $dim(rowspace) \leq r = dim(colspace)$
5. Now you can either apply the prove to $A^T$ (to say that $dim(colspace) \leq r = dim(rowspace)$ ) or notice that the 2 $rowspace$ vectors are trivially independent because of the placement of zeros.

It's easy to generalize.

Let $A \in \mathbb{F}^{m \times n}$ and let $R = $RREF$(A)$.

The non-zero rows of $R$ are obtained by invertible row operations on $A$. This means we can go back and forth between rows of $A$ and $R$. Therefore, non-zero rows of $R$ span $A$.Also, non-zero rows of $R$ are linearly independent(any dependent rows are reduced to $0$ rows). Therefore, non-zero rows of $R$ form a basis for row space of $A$.

# of non-zero rows = # of leading $1$s in $R$ = dimension(row space of $A$) = row rank($A$)

$R = EA$, where $E$ is an invertible elementary matrix product. Let $B = E^{-1}$. Let $r_j$ be the $j$th pivot column of $R$.

$r_j$ = $E a_j \Rightarrow a_j = B r_j$. Since $r_j$ is a pivot column, $r_j=I_j$($j$ th column of identity matrix). Therefore, $a_j = B I_j$. Since columns of $I$ are independent, $a_j$s are independent(Proving this is easy -- start from definition of linear independence for $I_j$s and show that multiplication by $B$ does not affect the relationship). Therefore, pivot columns of $A$ are linearly independent.

Each non-pivot column of $R$ is linearly dependent on pivot columns of $R$(Otherwise, it would have been a pivot column). Since $a_j = B r_j$, each non-pivot column of $A$ is linearly dependent on pivot columns of $A$. Therefore, pivot columns of $A$ span the column space of $A$.

Therefore, pivot columns of $A$ form a basis for column space of $A$.

$\Rightarrow$ column rank($A$) = dimension(col space($A$)) = # of pivot columns = # of leading $1$s in $R$ = row rank ($A$)

[6chars]