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


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.

  • $\begingroup$ You mean the $k$ is arbitrary ? $\endgroup$ – 81235 Jun 7 '13 at 1:32
  • $\begingroup$ 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. $\endgroup$ – copper.hat Jun 7 '13 at 1:39
  • $\begingroup$ 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$ $\endgroup$ – 81235 Jun 7 '13 at 2:17
  • 1
    $\begingroup$ 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.) $\endgroup$ – copper.hat Jun 7 '13 at 3:48
  • $\begingroup$ Oops, I missed something completely. I need to go but will fix it later. $\endgroup$ – copper.hat Jun 7 '13 at 3:50

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

  • $\begingroup$ You mean the $k$ is arbitrary ? $\endgroup$ – 81235 Jun 7 '13 at 1:32
  • $\begingroup$ 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. $\endgroup$ – Berci Jun 7 '13 at 1:33
  • $\begingroup$ By the way, how did you prove (b)? $\endgroup$ – Berci Jun 7 '13 at 1:36
  • $\begingroup$ 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$. $\endgroup$ – 81235 Jun 7 '13 at 1:52
  • 1
    $\begingroup$ I still think about my problem, I think we just can get $rank(A)\ge k$, and $rank(A^{T})\ge k$. $\endgroup$ – 81235 Jun 7 '13 at 2:00

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.