0
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.