# Gram Matrices Rank [duplicate]

Let $$A$$ be an $$m \times 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 $$\mathrm{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
• 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$$ and $$\mathbf{x^Tx}=\mathbf{||x||^2}$$. We exploit these facts.

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})^T\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.

• 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
• I am seriously confused. In your second proof: We use the lemma to prove that ker($A$)=ker($A^TA$). This lemma implied that rank$(A)$=rank $(A^TA)$. Further, rank$(A)$=rank$(A^T)$. This implies that rank$(A^T)$=rank$(A^TA)$. Now, mimicking your proof of the lemma, I got ker$(A^T)$=ker$(AA^T)$. This would imply that rank$(A^T)$=rank$(AA^T$. Hence, combining the result, we conclude that rank$(A)$=rank$(A^T)$=rank$(A^TA)$=rank$(AA^T)$. Since your proof is independent of entries of the matrix. Can you explain, what is wrong with the matrix $A^T=(1\enspace i)$? Or with proof? – Kumar Oct 6 '20 at 7:46
• @Kumar With complex vectors you need to take the conjugate transpose to get the norms right, if you just take the sum of squares it can be zero. – Arnaud D. Oct 6 '20 at 9:12

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.

• Your proof only holds for $A\in\mathbb{R}^{m\times n}$. – Kumar Oct 6 '20 at 7:52

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