# Gram Matrices Rank

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

-
$(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
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

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.

-
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

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?

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