48
$\begingroup$

How can I prove rank $A^TA$ = rank $A$ for any $A_{m \times n}$?

This is an exercise in my textbook associated with orthogonal projections and Gram–Schmidt process but I am unsure how they are relevant.

$\endgroup$
  • 26
    $\begingroup$ Obligatory remark: This holds when $A\in\mathbb R^{m\times n}$, but not (for instance) when $A\in\mathbb C^{m\times n}$. $\endgroup$ – darij grinberg Apr 3 '13 at 4:31
  • 4
    $\begingroup$ See this counter-example for the case where $A\in\mathbb C^{m\times n}$. $\endgroup$ – M.S. Dousti Jan 13 '16 at 22:43
  • $\begingroup$ Or $A^T=(1~~\mathbf i)$. $\endgroup$ – Marc van Leeuwen Apr 27 '16 at 14:52
  • 1
    $\begingroup$ The conclusion also fails for fields of nonzero characteristic (finite fields in particular). See the comment by @Member below on the Accepted Answer, identifying the crucial step that $(Ax)^T(Ax) = 0$ implies $Ax=0$. $\endgroup$ – hardmath Jun 8 '17 at 17:44
86
$\begingroup$

Let $\mathbf{x} \in N(A)$ where $N(A)$ is the null space of $A$.

So, $$\begin{align} A\mathbf{x} &=\mathbf{0} \\\implies A^TA\mathbf{x} &=\mathbf{0} \\\implies \mathbf{x} &\in N(A^TA) \end{align}$$ Hence $N(A) \subseteq N(A^TA)$.

Again let $\mathbf{x} \in N(A^TA)$

So, $$\begin{align} A^TA\mathbf{x} &=\mathbf{0} \\\implies \mathbf{x}^TA^TA\mathbf{x} &=\mathbf{0} \\\implies (A\mathbf{x})^T(A\mathbf{x})&=\mathbf{0} \\\implies A\mathbf{x}&=\mathbf{0}\\\implies \mathbf{x} &\in N(A) \end{align}$$ Hence $N(A^TA) \subseteq N(A)$.

Therefore $$\begin{align} N(A^TA) &= N(A)\\ \implies \dim(N(A^TA)) &= \dim(N(A))\\ \implies \text{rank}(A^TA) &= \text{rank}(A)\end{align}$$

$\endgroup$
  • 9
    $\begingroup$ How does $(Ax)^T (Ax)=0$ implys $Ax=0$? $\endgroup$ – user268307 Dec 20 '15 at 21:56
  • 12
    $\begingroup$ @AnuragJain note that for any vector $y$, $y^Ty = \|y\|^2$. Also, note that this question was asked two years ago, so you're unlikely to catch the attention of the original asker. $\endgroup$ – Omnomnomnom Dec 20 '15 at 21:58
  • $\begingroup$ Oh yeah, got it.Thanks. And if a question was asked several years ago and if I have a doubt in that, then what I am supposed to do ? $\endgroup$ – user268307 Dec 20 '15 at 22:02
  • 13
    $\begingroup$ Of course, try to get someone's attention first, just as you did. If that doesn't work, then post a new question. When you post a new question, you should say something like "I've seen the answer at [link to question], but I didn't understand [step in the proof]". This way, your question won't be marked as a duplicate. $\endgroup$ – Omnomnomnom Dec 20 '15 at 22:10
  • $\begingroup$ The last step $\dim(N(A^TA)) = \dim(N(A)) \implies \text{rank}(A^TA) = \text{rank}(A)$ is due to rank-nullity theorem. $\endgroup$ – chibicode Apr 2 '18 at 17:57
7
$\begingroup$

Let $r$ be the rank of $A \in \mathbb{R}^{m \times n}$. We then have the SVD of $A$ as $$A_{m \times n} = U_{m \times r} \Sigma_{r \times r} V^T_{r \times n}$$ This gives $A^TA$ as $$A^TA = V_{n \times r} \Sigma_{r \times r}^2 V^T_{r \times n}$$ which is nothing but the SVD of $A^TA$. From this it is clear that $A^TA$ also has rank $r$. In fact the singular values of $A^TA$ are nothing but the square of the singular values of $A$.

$\endgroup$
3
$\begingroup$

Since elementary operations do not change the rank of a matrix. We have $\text{rank}(A^TA) = \text{rank}(E^TA^TAE)$, where E is a multiplication of several elementary operations which make $AE = [A_1, A_2]$, where $A_1$ is a column full rank matrix with $\text{rank}(A_1) = \text{rank}(A)$.

Thus we can find a matrix $P$ such that $A_1P= A_2$ and $AE = [A_1, A_1P] = A_1[I, P]$.

Thus $\text{rank}(E^TA^TAE) = \text{rank}(A_1[I, P])^T(A_1[I, P])$. In this equation, the matrices are all of full rank and the rank equals $\text{rank}(A)$, so on a real space $\text{rank}(A^TA) = \text{rank}(A)$, completing the proof.

$\endgroup$
  • 2
    $\begingroup$ I cannot decipher what is said here, but it must be wrong since it never uses that the matrices are over $\Bbb R$ (or more generally an ordered field) rather than for instance over $\Bbb C$ where the result is not true. $\endgroup$ – Marc van Leeuwen Apr 27 '16 at 14:38
  • 1
    $\begingroup$ The last theorem actually implicitly uses they are over real space. Thank you for pointing that out. I have added that prerequisite into my answer. $\endgroup$ – Xiangru Lian Apr 30 '16 at 4:47
  • 2
    $\begingroup$ An alternative simple way to see it: Matrix $A^T$ may be reduced to its reduced row-echelon form, $R$, by $PA^T=R$, where $P$ is the product of a sequence of elementary matrices. So, $A^T=P^{-1}R$ and hence $$\mathrm{rank}(A^TA)=\mathrm{rank}(P^{-1}RR^T(P^{-1})^T)=\mathrm{rank}(RR^T).$$ The result then follows easily from this, since clearly $\mathrm{rank}(RR^T)=\mathrm{rank}(R)=\mathrm{rank}(A).$ $\endgroup$ – syeh_106 Jan 14 '17 at 2:07
  • 2
    $\begingroup$ @syeh_106 Awesome. Thanks for your contribution. $\endgroup$ – Xiangru Lian Jan 14 '17 at 10:31

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.