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

• Why did you not add your answer to an existing question, instead of writing a duplicate question? Commented Jan 8, 2016 at 6:57
• The proof in the first link is incorrect. Commented Sep 20, 2020 at 15:36

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]