5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ $(A^TA)^T= A^T{A^T}^T=A^TA$ it is symmetric, but not the same as $AA^T$ $\endgroup$ – adam W Oct 13 '12 at 2:12
  • $\begingroup$ But I thought if you take the transpose of a transpose you will just have its regular matrix? $\endgroup$ – diimension Oct 13 '12 at 2:15
  • 1
    $\begingroup$ 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. $\endgroup$ – EuYu Oct 13 '12 at 2:17
  • $\begingroup$ Wow, what a dumb mistake. I should go take a break and clear my head. $\endgroup$ – diimension Oct 13 '12 at 2:20
  • $\begingroup$ Can one of you show me how to properly prove this question please? $\endgroup$ – diimension Oct 13 '12 at 2:26
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow, beautiful ! Thank you so very much, EuYu!! I clearly understand it because of your help!. Thank you again! $\endgroup$ – diimension Oct 13 '12 at 2:52
  • $\begingroup$ 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 $\endgroup$ – Alec Teal Nov 24 '13 at 23:43
  • $\begingroup$ @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})$ $\endgroup$ – EuYu Nov 25 '13 at 2:34
  • $\begingroup$ Really Really nice and explicative answer! Thank you very much! $\endgroup$ – Bman72 Jun 30 '14 at 9:16
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The rank will then be n x n since A is a linearly independent column vector? $\endgroup$ – diimension Oct 13 '12 at 2:35
  • $\begingroup$ 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$. $\endgroup$ – adam W Oct 13 '12 at 2:38
  • $\begingroup$ I don't quite understand what you said there. $\endgroup$ – diimension Oct 13 '12 at 2:41
  • $\begingroup$ 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$ $\endgroup$ – adam W Oct 13 '12 at 2:44
  • $\begingroup$ Euyu gave me a detailed explanation . But still thanks for your help though! $\endgroup$ – diimension Oct 13 '12 at 2:53

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