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.

• The second "here" links to your answer below. – Gerry Myerson Nov 5 '15 at 6:04
• Why did you not add your answer to an existing question, instead of writing a duplicate question? – celtschk Jan 8 '16 at 6:57

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 = R^{-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$)

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.