4

Let $A\in{\mathbb{R}^{m\times n}}$. Suppose $x_{1},\ldots,x_{k}$ are vectors in ${\mathbb{R}^{n}}$ and {${Ax_{1},\ldots,Ax_{k}}$} is a linearly independent set. this problem has three problem.
(a)Prove that{$x_{1},\ldots,x_{k}$} is linearly independent set.
(b)Prove that {$A^{T}Ax_{1},\ldots,A^{T}Ax_{k}$} is also linealy independent set.
(c) Use part (b) to show that $rank(A^{T})\ge rank(A)$.
I have finished (a) and (b), but I do not know how to use part(b) to show $rank(A^{T})\ge rank(A)$.

81235
  • 1,306

2 Answers2

2

You are almost there.

Remark: For any matrix $B$, if $\{B x_i\}_{i=1}^k$ are linearly independent, then $\operatorname{rk} B \ge k$.

You have shown that if $\{A x_i\}_{i=1}^k$ are linearly independent, then so are $\{A^TA x_i\}_{i=1}^k$, or we can write this more clearly as $\{A^T v_i\}_{i=1}^k$, with $v_i = A x_i$. Hence $\operatorname{rk} (A^T) \ge k$.

If $k=\operatorname{rk} A $, then we can find $x_1,...,x_k$ such that $\{A x_i\}_{i=1}^k$ are linearly independent (by definition of rank).

In particular, the above shows that $\operatorname{rk} A^T\ge k$, which is the desired result (ie, $\operatorname{rk} A^T\ge \operatorname{rk} A $).

As an aside, since $(A^T)^T = A$, the above actually shows that the two ranks are equal.

copper.hat
  • 172,524
  • You mean the $k$ is arbitrary ？ – 81235 Jun 07 '13 at 01:32
  • No. If the collection $B x_1,...,B x_k$ are linearly independent then blah blah blah. There is some limit on all $k$s above, explicit or implicit. – copper.hat Jun 07 '13 at 01:39
  • Hi, I thought it again. In (b), I only conclude that, if $rank(A)\ge k$, then $rank(A^{T})\ge k$. Can the the situation below happen: $rank(A)=k+2$, and $rank(A^{T})=k$ – 81235 Jun 07 '13 at 02:17
  • 1
    Choose the maximum $k$ for which $\operatorname{rk} A \ge k$, that is, $k = \operatorname{rk} A$. Then you have from the above that $\operatorname{rk} (A^TA) \ge \operatorname{rk} A$. (It is not hard to show they are equal, but that is not the goal here.) – copper.hat Jun 07 '13 at 03:48
  • Oops, I missed something completely. I need to go but will fix it later. – copper.hat Jun 07 '13 at 03:50
  • @user81235: My apologies, I had forgotten to remove the $A$ from the $A^T A$ above. I have fixed the bug, and hopefully clarified slightly. – copper.hat Jun 07 '13 at 04:26
  • I have thought it again. According what you have revised, I think you approach is that: if $rank(A)=m > k$, then we can find $m$ $x_{i}'s$, such that $Ax_{i}$ are also linearly independent, and that also follows $rank(A^{T})\ge m$. Is this what you think? – 81235 Jun 07 '13 at 14:34
  • That is correct, with the addition of the fact that if $A x_i$ are li., then so are $A^T (A x_i)$. – copper.hat Jun 07 '13 at 14:39
1

Well, $rank(M)\overset{def}=\max\{k\,:\,\exists x_1,..,x_k:(Mx_1,\dots,Mx_k)$ are linearly independent$\}$.

So, by (b) we have $rank(A^T)\ge k$. And we can choose $k:=rank(A)$.

Berci
  • 90,745
  • You mean the $k$ is arbitrary ？ – 81235 Jun 07 '13 at 01:32
  • Well, we need $x_1,..,x_k$ such that $Ax_1,..,Ax_k$ are independent. For $k=rank(A)$ such $x_i$'s exist by definition. – Berci Jun 07 '13 at 01:33
  • By the way, how did you prove (b)? – Berci Jun 07 '13 at 01:36
  • suppose $A^{T}(\alpha_{1}Ax_{1}+\cdots+\alpha_{k}Ax_{k})=0$, then$\alpha_{1}Ax_{1}+\cdots+\alpha_{k}Ax_{k} \in N(A^{T})\cap R(A)$. We know that $N(A^{T})\perp R(A)$, so $\alpha_{1}Ax_{1}+\cdots+\alpha_{k}Ax_{k}=0$, then $\alpha_{1}=\cdots=\alpha_{k}=0$. – 81235 Jun 07 '13 at 01:52
  • Ok. Good. Also, we can say that $v:=\alpha_1x_1+..+\alpha_kx_k$ and then $A^TAv=0 \implies v^TA^TAv=0$ but that is $|Av|^2=0$, so $Av=0$. – Berci Jun 07 '13 at 02:00
  • 1
    I still think about my problem, I think we just can get $rank(A)\ge k$, and $rank(A^{T})\ge k$. – 81235 Jun 07 '13 at 02:00
  • Yes, the condition of existence of such $x_1,..,x_k$ means nothing else but $rank(A)\ge k$. So we have: $ \ $ "whenever $rank(A)\ge k$, we also have $rank(A^T)\ge k$". Now apply this very statment for $k:=rank(A)$. – Berci Jun 07 '13 at 09:35
  • Can the the situation below happen: $rank(A)=k+2$, and $rank(A^{T})=k$ – 81235 Jun 07 '13 at 12:44
  • No. If $rank(A)=k+2$, then, by definition of rank, there exist some $y_1,..,y_{k+2}$ vectors such that $Ay_1,..,Ay_{k+2}$ are linearly independent. Now you can apply part (b) for these $y_1,..,y_{k+2}$ vectors, and there are $k+2$ pieces of them, so we have $rank(A^T)\ge k+2$. (Well, because of the $x_1,..,x_k$ elements, we still have $rank(A^T)\ge k$, it's not contradictory.) As a consequence of this exercise we get the theorem that $rank(A^T)=rank(A)$. – Berci Jun 07 '13 at 14:46