use linearly independence prove

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.

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

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