Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let A be a m x n matrix. Show that, even though they may be of different sizes, both Gram matrices $K = A^TA$ and $L = AA^T$ have the same rank.

My attempt:

We have that K and L are gram matrices so $K = A^TA = (A^TA)^T = AA^T = L$ and by definition we have that $rank(A) = A^T$.

share|improve this question
2  
$(A^TA)^T= A^T{A^T}^T=A^TA$ it is symmetric, but not the same as $AA^T$ –  adam W Oct 13 '12 at 2:12
    
But I thought if you take the transpose of a transpose you will just have its regular matrix? –  diimension Oct 13 '12 at 2:15
1  
When you take the transpose of a transpose, you do indeed get your regular matrix back. But $A^\mathrm{T}A$ is not the transpose of $AA^\mathrm{T}$. For example, note that $A^\mathrm{T}A$ is $n\times n$ while $AA^\mathrm{T}$ is $m\times m$. Even your question mentions they may have different sizes. –  EuYu Oct 13 '12 at 2:17
    
Wow, what a dumb mistake. I should go take a break and clear my head. –  diimension Oct 13 '12 at 2:20
    
Can one of you show me how to properly prove this question please? –  diimension Oct 13 '12 at 2:26
add comment

3 Answers 3

up vote 7 down vote accepted

I think there are two good ways to see this and so I will give two proofs

1) If we are given two matrices $A$ and $B$, then the columns of $AB$ are linear combinations of the columns of $A$ and the rows of $AB$ are the linear combinations of the rows of $B$. This follows immediately from block multiplication $$AB = \begin{pmatrix} A\mathbf{b_1} & \cdots & A\mathbf{b_n}\end{pmatrix} = \begin{pmatrix} \mathbf{a_1}^\mathrm{T}B \\ \vdots \\ \mathbf{a_m}^\mathrm{T}B\end{pmatrix}$$ where $\mathbf{a_i}$ and $\mathbf{b_i}$ denote the row/column vectors of $A$ and $B$ respectively. From this, we can see that the columns of $A^\mathrm{T}A$ are a linear combination of the columns of $A^\mathrm{T}$, i.e. the rows of $A$. Likewise, the columns of $AA^\mathrm{T}$ are a linear combination of the columns of $A$. The row and column rank of a matrix coincide, and from this we can immediately conclude that that the ranks of the two matrices are the same.

2) For the second solution, we use a very general and useful trick for showing that a vector is $\mathbf{0}$. Notice that $\mathbf{x} = \mathbf{0} \iff \|\mathbf{x}\| = 0$. We exploit this fact.

Lemma: $\ker(A) = \ker(A^\mathrm{T}A)$

Proof: The forward inclusion is easy. If we have $$A\mathbf{x} = \mathbf{0}$$ then we immediately have $$A^\mathrm{T}A\mathbf{x} = \mathbf{0}$$ so that we have $\ker(A) \subseteq \ker(A^\mathrm{T}A)$. For the backwards inclusion, suppose that we have $$A^\mathrm{T}A\mathbf{x} = \mathbf{0}$$ We pre-multiply by $\mathbf{x}^\mathrm{T}$ to get $$x^\mathrm{T}A^\mathrm{T}A\mathbf{x} = (A\mathbf{x})\cdot(A\mathbf{x}) = \|A\mathbf{x}\|^2 = 0$$ It must follow that $A\mathbf{x} = \mathbf{0}$. Therefore we also have $\ker(A^\mathrm{T}A) \subseteq \ker(A)$ so that the lemma follows. $\square$

From this, we have $\mathrm{nullity}(A) = \mathrm{nullity}(A^\mathrm{T}A)$ where from the rank-nullity theorem we have $\mathrm{rank}(A) = \mathrm{rank}(A^\mathrm{T}A)$. Applying the same result to $A^\mathrm{T}$ will give you $\mathrm{rank}(A^\mathrm{T}) = \mathrm{rank}(A^\mathrm{T}A)$. The final result follows by noting $\mathrm{rank}(A) = \mathrm{rank}(A^\mathrm{T})$.

If anything is unclear, or if you would like to know the logic behind any of the steps, please do not hesitate to ask me.

share|improve this answer
    
Wow, beautiful ! Thank you so very much, EuYu!! I clearly understand it because of your help!. Thank you again! –  diimension Oct 13 '12 at 2:52
    
Superb answer, not sure how you applied the same result to $A^T$ though, because surely then you'd get $AA^T$ which may not be valid –  Alec Teal Nov 24 '13 at 23:43
    
@AlecTeal Yes, you are right. There is a typo in the answer. The lemma allows us to conclude that $\ker A = \ker A^\mathrm{T}A$ as well as $\ker A^\mathrm{T} = \ker AA^\mathrm{T}$. The desired result then follows from rank-nullity and the fact that $\mathrm{rank}(A) = \mathrm{rank}(A^\mathrm{T})$ –  EuYu Nov 25 '13 at 2:34
    
Really Really nice and explicative answer! Thank you very much! –  Ale Jun 30 at 9:16
add comment

Let's say that $A$ is rank one, so it is a column vector. What then is the rank of $AA^T$? HINT: When the matrix is row reduced, what happens?

share|improve this answer
    
The rank will then be n x n since A is a linearly independent column vector? –  diimension Oct 13 '12 at 2:35
    
ONE column vector that defines an $n \times n$ Gram matrix. Each row is a multiple of... $A_i$ the element of the column $A$ at row $i$. –  adam W Oct 13 '12 at 2:38
    
I don't quite understand what you said there. –  diimension Oct 13 '12 at 2:41
    
If we are talking one vector at the moment, call it $\vec{a}$. Then the Gram matrix is the $n \times n$ Gram matrix $\vec{a}\vec{a}^T$. Each row is a multiple of the other, correct? Because row $i$ for example is $a_i\vec{a}^T$ –  adam W Oct 13 '12 at 2:44
    
Euyu gave me a detailed explanation . But still thanks for your help though! –  diimension Oct 13 '12 at 2:53
add comment

Excellent answers from @Euyu !!. I would like to add another way of proof. Assume $A=U\Sigma V^{T}$ is the Singular Value Decomposition (SVD). So $A^{T}A=V\Sigma ^{2}V^{T}$ and $AA^{T}=U\Sigma ^{2}U^{T}$ (follows from substituting the SVD). So clearly, the eigen values of the symmetric matrices $AA^{T}$ and $A^{T}A$ are the squares of singular values of $A$. Hence they have same number of non-zero eigen values and hence their rank should be the same.

share|improve this answer
    
Thank you sir ! –  diimension Oct 14 '12 at 2:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.