1
$\begingroup$

I'm currently working through the proof that the column and row rank of a matrix $A$ over a field $F$ are equal, using the concept of linear combinations (more specifically I'm following the proof sketch given on wikipedia). There seems to be several posts on this forum handling this proof, but none of them seem to answer a confusion I have at a certain step in the proof:

Assuming we have an $m \times n$ matrix $A$ over a field $F$, the beginning of the proof shows that we can find an $m \times r$ matrix $C$ and an $r \times n$ matrix $R$, such that $A=CR$ (where $r$ is the column rank of $A$). I assume you are familiar with the proof, because I won't explain the details here. The proof then proceeds to show that the rows of $R$ span the row space of $A$, which is the step I'm confused at:

so if $R_1,\ldots R_r$ are the rows of $R$, it is shown that Span$(R_1,\ldots , R_r)= $rowsp$(A)$. At this point I'm only able to show that each element of rowsp$(A$) is a linear combination of the rows of $R$, and thus Span$(R_1,\ldots , R_r)\supseteq$ rowsp$(A)$. But I'm having difficulty understanding why the other inclusion holds. At least I'm assuming that it should hold, because that is the meaning of the rows of R span the row space of A.

I hope someone could shed some light on this.

$\endgroup$
5
  • $\begingroup$ Do you know the fact that if $U$ is a finite dimensional vector space and $V$ is a proper subspace then $\dim U > \dim V$? If so then the result follows. $\endgroup$
    – Mor A.
    Commented May 11, 2021 at 23:46
  • $\begingroup$ Yes, I know that. Could you elaborate on why this implies the other inclusion? $\endgroup$ Commented May 11, 2021 at 23:49
  • $\begingroup$ essentially, what the proof in wikipedia that you follow does is use that fact to deduce that the row rank of $A$ is less than or equal to $r$ (what they mean by spanning set is that it spans at least the row space of $A$). Since this is true for any matrix it's true for the transpose of $A$, but the column rank of the transpose of $A$ is the row rank of $A$ and vice versa, so we get that $r$ is at most the row rank of $A$, from the two inequalities we get that the two ranks are equal (and then get equality for the spans in question) $\endgroup$
    – Mor A.
    Commented May 12, 2021 at 0:11
  • $\begingroup$ Yes, that is true. To be more precise, if that fact, i.e. span$(R)=$rowspan$(A)$ is true, then it follows that the row rank of $A$ is less than or equal to $r$, by the Steinitz exchange lemma. But according to my understanding, that lemma can only be used whenever span$(R)=$rowspan$(A)$, which is why I'm trying to show this equality before proceeding with the proof. Do you understand my problem? The rest of the proof, as you wrote, is clear to me. It's possible, however, that I'm misunderstanding what you're writing. $\endgroup$ Commented May 12, 2021 at 1:26
  • $\begingroup$ And also, in my previous post on here before this one, I asked what was meant by "spanning set or that a set $U$ spans a set $W$, and was informed that it meant that span$(U)=W$, meaning that $W \subseteq$ span$(U)$ is not enough. That's why I find this a bit confusing. $\endgroup$ Commented May 12, 2021 at 1:32

1 Answer 1

1
$\begingroup$

We'll denote by $r_c, r_r$ the column rank and row rank of an $m\times n$ matrix $A$ (respectively), and we decompose $A=CR$ with $C$ an $m\times r_c$ matrix and $R$ an $r_c\times n$ matrix.

You've shown that $\operatorname{rowspan}(A)\subseteq\operatorname{rowspan}(R)$, therefore $\dim(\operatorname{rowspan}(A))\leq\dim(\operatorname{rowspan}(R))$.

Notice that $R$ has $r_c$ rows, therefore $\dim(\operatorname{rowspan}(R))\leq r_c$, so in total we get $$\dim(\operatorname{rowspan}(A))\leq\dim(\operatorname{rowspan}(R))\leq r_c \tag{$*$}$$ but from the definition of the row-rank of a matrix, $r_r=\dim(\operatorname{rowspan}(A))$, therefore $r_r\leq r_c$.

Applying this same argument to $A^T$ gives us that $r_c\leq r_r$, so in total we get $r_c=r_r$ as we wanted.

Furthermore, once we have this equality, we get that the inequalities in $(*)$ are equalities, that is we have $\dim(\operatorname{rowspan}(A))=\dim(\operatorname{rowspan}(R))$, combining this with $\operatorname{rowspan}(A)\subseteq\operatorname{rowspan}(R)$ we get $\operatorname{rowspan}(A)=\operatorname{rowspan}(R)$.

So after we've shown $r_r=r_c$ we can say that indeed the rows of $R$ span the row-space of $A$ (before that we could only say they span a vector space which has the row-space of $A$ as a subspace)

$\endgroup$
1
  • $\begingroup$ Thank you very much for your elaborate answer. This makes much more sense now, I think I was trying to apply the Steinitz exchange lemma to the wrong subspaces. In the end, all I wanted to prove was the inequality $r_r \leq r_c$. I think the crucial point I forgot was the fact that from rowspan$(A) \subseteq$ rowspan$(R)$ follows $r_r \leq$ dim(rowspan$(R)$), and then, applying the Steinitz exchange lemma, we get dim(rowspan$(R)$)$ \leq r_c$, which then yields the desired inequality. Your answer really clarified all my confusion! $\endgroup$ Commented May 13, 2021 at 19:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .