1
$\begingroup$

Suppose $A$ is the matrix of the size $m\times n$.

My book gives the following definition of the row rank of $A$: we say that $A$ has row rank equal to $r$ if there are $r$ linearly independent rows that are maximal in the following sense: no collection of rows with more that $r$ elements will be linearly independent. Denote the row rank of $A$ by $r_1(A)$.

I am trying to prove that $r_1(A)$ is invariant under elementary operations over rows and columns.

The case of elementary operations over columns is trivial one. But I have some difficulties with elementary operations over rows. The case when elementary operation is just multiplication of some row by $\lambda\neq 0$ was easy. Let's consider the elementary operation when $i$th row is switched by the sum of $i$th and $j$th. More precisely:

Let $A$ be the $m\times n$ matrix with $r_1(A)=r$ and $0<r<m$. Let $\mathbf{a}^1,\dots,\mathbf{a}^m$ its rows and WLOG assume that the first $r$ of them are maximal linearly independent rows. Let $B$ the matrix which is obtained from $A$ by the following elementary operation:

$$A=\begin{bmatrix} \mathbf{a}^1 \\ \mathbf{a}^2 \\ \vdots \\ \mathbf{a}^m \\ \end{bmatrix} \ \longrightarrow \begin{bmatrix} \mathbf{a}^1+\mathbf{a}^{r+1} \\ \mathbf{a}^2 \\ \vdots \\ \mathbf{a}^r \\ \vdots \\ \mathbf{a}^m \\ \end{bmatrix}=B$$ In other words, I've just switched the row $\mathbf{a}^1$ by $\mathbf{a}^1+\mathbf{a}^{r+1}$, where $\mathbf{a}^{r+1}$ is not in the collection of maximal linearly independent vectors $\{\mathbf{a}^1,\dots, \mathbf{a}^r\}$.

Can anyone explain to me how to show that $r_1(B)=r$? I am trying to prove that in $A$ the rows $\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r$ are linearly independent but I failed.

Would be very grateful for the help. And please give the answer just using these definitions.

BTW this is not a duplicate of the question.

$\endgroup$
  • 2
    $\begingroup$ The row rank is the dimension of the row space, which is invariant under elementary row operations. $\endgroup$ – Angina Seng Nov 23 '19 at 20:42
  • $\begingroup$ @LordSharktheUnknown, the book which I am reading didn't use the row space yet. Could you show the proof of the case which I had trouble from the scratch? $\endgroup$ – ZFR Nov 23 '19 at 20:45
  • 1
    $\begingroup$ Possible duplicate of Proof of elementary row operations for matrices? $\endgroup$ – Jorge Barrios Nov 23 '19 at 22:59
  • $\begingroup$ @JorgeBarrios, this is not a duplicate of the link which you have provided. In your link there is nothing about rank of matrix. So be careful with that when you are doing this! $\endgroup$ – ZFR Nov 23 '19 at 23:19
1
$\begingroup$

The vectors $\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r$ in general will not be linearly independent because it might be that $\mathbf{a}^{r+1}=-\mathbf{a}^1$, so you get the zero vector in the set, making it automatically dependent.

However, if it is the case that $\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r$ are dependent, then the vectors $\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r$ will be independent. The proof is below, I tried hiding it with the spoiler tag so that you can try it out by yourself first, but the tag doesn't seem to work when MathJax is involved.


Suppose that both sets $\{\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r\}$ and $\{\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r\}$ are dependent. Then there are two groups of coefficients, $\alpha_1,\dots,\alpha_r$ and $\beta_1,\dots,\beta_r$ such that in each group not all coefficients are zero and the following holds:

$$\alpha_1(\mathbf{a}^1+\mathbf{a}^{r+1})+\alpha_2\mathbf{a}^2+\cdots+\alpha_r\mathbf{a}^r=0,\\ \beta_1\mathbf{a}^{r+1}+\beta_2\mathbf{a}^2+\cdots+\beta_r\mathbf{a}^r=0. $$

If $\beta_1=0$, then all other betas are zero because any subset of $\{\mathbf{a}^1,\mathbf{a}^2, \dots,\mathbf{a}^r\}$ is independent, so we have $\beta_1\neq0$ and we divide the second equation by $\beta_1$. To reduce clutter, I'll write it as $$\mathbf{a}^{r+1}=\gamma_2\mathbf{a}^2+\cdots+\gamma_r\mathbf{a}^r.$$ Now plug that into the first equation and regroup to obtain: $$\alpha_1\mathbf{a}^1+(\alpha_1\gamma_2+\alpha_2)\mathbf{a}^2+\cdots+(\alpha_1\gamma_r+\alpha_r)\mathbf{a}^r=0.$$ The independence of $\{\mathbf{a}^1,\mathbf{a}^2, \dots,\mathbf{a}^r\}$ forces all these coefficients to be zero, so $\alpha_1=0$ and $$0=\alpha_1\gamma_j+\alpha_j=\alpha_j,\text{ for }j=2,\dots,r.$$ But this contradicts that at least one of the alphas must be nonzero. Therefore, at least one of $\{\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r\}$ and $\{\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r\}$ is independent.

This proves that the row-rank of the matrix $B$ is at least $r$. We now prove that it is exactly $r$


Suppose first that $\{\mathbf{a}^2, \dots,\mathbf{a}^r,\mathbf{a}^{r+1}\}$ is independent in $B$ but not maximal. Then it is contained in some maximal independent set for $B$, say $$\{\mathbf{a}^2, \dots,\mathbf{a}^r,\mathbf{a}^{r+1},\mathbf{b}^1,\dots,\mathbf{b}^s\}.$$ Any subset of this maximal independent set is itself independent, so if any of the rows $\mathbf{b}^1,\dots,\mathbf{b}^s$ is also a row of $A$, it would mean that $A$ has rank larger than $r$. Therefore, there can be at most one row in that set, the only row which is not in $A$, i.e. $\mathbf{b}^1=\mathbf{a}^1+\mathbf{a}^{r+1}$.

So suppose that $$\{\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r,\mathbf{a}^{r+1}\}$$ is maximal independent in $B$. Then both sets $$\{\mathbf{a}^1,\mathbf{a}^2, \dots,\mathbf{a}^r\}\text{ and}\\ \{\mathbf{a}^2, \dots,\mathbf{a}^r,\mathbf{a}^{r+1}\} $$ are maximal independent in $A$, therefore from the first set we have $$\mathbf{a}^{r+1}=\alpha_1\mathbf{a}^{1}+\dots+\alpha_r\mathbf{a}^{r}$$ and from the second set we have $$\mathbf{a}^{1}=\beta_2\mathbf{a}^{2}+\dots+\beta_{r+1}\mathbf{a}^{r+1}.$$ This means that we can write $\mathbf{a}^{1}+\mathbf{a}^{r+1}$ as $$\mathbf{a}^{1}+\mathbf{a}^{r+1}=\mathbf{a}^1+\alpha_1\mathbf{a}^1+\cdots+\alpha_r\mathbf{a}^r=\\ (\text{plug in the expression for $\mathbf{a}^1$})=\\ \gamma_2\mathbf{a}^{2}+\cdots+\gamma_{r+1}\mathbf{a}^{r+1}.$$ But if we plug that into $\{\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r,\mathbf{a}^{r+1}\}$, we get a dependent set!

If $\{\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r\}$ is independent in $B$ but not maximal, then again it is contained in some maximal independent set for $B$ which, for the same reasons as previously, can contain only one additional row $\mathbf{b}$, which is also a row of $A$ and such that $\{\mathbf{a}^2, \dots,\mathbf{a}^r,\mathbf{b}\}$ is independent (in $A$). Now the same reasoning applies: if the set $$\{\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r,\mathbf{b}\}$$ is independent in $B$, then both sets $$\{\mathbf{a}^1,\mathbf{a}^2, \dots,\mathbf{a}^r\}\text{ and}\\ \{\mathbf{a}^2, \dots,\mathbf{a}^r,\mathbf{b}\} $$ are maximal independent in $A$, so we can use the first set to express $\mathbf{a}^{r+1}$ and the second set to express $\mathbf{a}^1$, and then combine the two expressions so that we get $$\mathbf{a}^1+\mathbf{a}^{r+1}=\delta_2\mathbf{a}^2+\cdots++\delta_{r}\mathbf{a}^{r}+\delta\mathbf{b},$$ implying that $\{\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2, \dots,\mathbf{a}^r,\mathbf{b}\}$ is dependent.

$\endgroup$
  • $\begingroup$ Thanks a lot for your reply and help! But I have just read the your solution very superficially and let me ask you the question: so you claim that if $\mathbf{a}^{r+1}=-\mathbf{a}^1$ then $\mathbf{a}^{r+1},\mathbf{a}^{2},\dots, \mathbf{a}^{r}$ will be maximal independent system. But what if $\mathbf{a}^{r+1}\neq -\mathbf{a}^1$? $\endgroup$ – ZFR Nov 24 '19 at 0:47
  • $\begingroup$ @ZFR It is the same for $a^{r+1}\neq -a^1$. In the proof $a^{r+1}=\gamma_2a^2+\cdots+\gamma_ra^r$ is any vector spanned by $a^2,\dots,a^r$. But I see how the wording in my second paragraph sounds as if $a^{r+1}\neq -a^1$ is the only case that I'm considering, I'll edit that. $\endgroup$ – Randy Marsh Nov 24 '19 at 0:49
  • $\begingroup$ +1 Very nice solution! I'll accept your answer as the best one! BTW, if $\{\mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2,\dots,\mathbf{a}^{r}\}$ is linearly independent, then how to show that it is maximal one i.e. any other row is linear combination of them? Namely, for $j\geq r+1$ we have to show that $\mathbf{a}^{j}\in \langle \mathbf{a}^1+\mathbf{a}^{r+1},\mathbf{a}^2,\dots,\mathbf{a}^{r}\rangle$ $\endgroup$ – ZFR Nov 24 '19 at 1:28
  • $\begingroup$ Sorry but also in the case when $\{\mathbf{a}^2,\dots, \mathbf{a}^r,\mathbf{a}^{r+1}\}$ is linearly dependent I've to show that $\mathbf{a}^1+\mathbf{a}^{r+1}$ and $\mathbf{a}^j \ (j>r+1)$ is linear combination of those rows. I was able to show it for $\mathbf{a}^1+\mathbf{a}^{r+1}$ but cannot prove it for $\mathbf{a}^j$ with $j>r+1$. Would be very grateful if you can show how to do it! $\endgroup$ – ZFR Nov 24 '19 at 1:51
  • $\begingroup$ Dear Goran. I have realized right now what i have said in the above 2 comments is not equivalent to having row rank $r$, right? I would be very grateful if you can help me, please. How to show that in each case no collection of rows with more than $r$ is linearly dependent, please? To be honest i am trying to prove it for the last few days, but.. $\endgroup$ – ZFR Nov 24 '19 at 12:17

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.