If $\operatorname{rank}(A)=k$, can we say something about $\operatorname{rank}(AA^t)$?

Question

Let $A$ a $n\times m$ matrix such that $\operatorname{rank}(A)=k$, can we say something about $\operatorname{rank}(AA^t)$?

It's like: If $\operatorname{rank}(A)=m$, can we say anything about $\operatorname{rank}(AA^t)$?, but $A$ is a matrix $n\times m$.

Answer 1

Basically, $\operatorname{rank}(A) = \operatorname{rank}(B)$, where $B$ is the square matrix made by padding $A$ with zero rows or zero columns. Then apply the solution in the MSE question you linked.

More explicitly, suppose that $n < m$. Let $\mathbf{0}_{i \times j}$ be the $i \times j$ zero matrix.

$$\begin{align} \operatorname{rank}(AA^t) &= \operatorname{rank}\left(\begin{bmatrix}AA^t&\mathbf{0}_{n \times (m - n)}\\\mathbf{0}_{(m - n) \times n} & \mathbf{0}_{(m - n) \times (m - n)}\end{bmatrix}\right)\\ &= \operatorname{rank}\left(\begin{bmatrix}A\\\mathbf{0}_{(m - n) \times m}\end{bmatrix}\begin{bmatrix}A\\\mathbf{0}_{(m - n) \times m}\end{bmatrix}^t\right)\\ &= \operatorname{rank}\left(\begin{bmatrix}A\\\mathbf{0}_{(m - n) \times m}\end{bmatrix}\right)\\ &= \operatorname{rank}(A). \end{align}$$

Otherwise, if $n \geq m$, then

$$\begin{align} \operatorname{rank}(AA^t) &= \operatorname{rank}\left(\begin{bmatrix}A&\mathbf{0}_{n \times (n - m)}\end{bmatrix}\begin{bmatrix}A&\mathbf{0}_{n \times (n - m)}\end{bmatrix}^t\right)\\ &= \operatorname{rank}\left(\begin{bmatrix}A&\mathbf{0}_{n \times (n - m)}\end{bmatrix}\right)\\ &= \operatorname{rank}(A). \end{align}$$

Answer 2

Basically, what we want to prove is:

For any real-valued matrix A (with dimension $n \times m$): $$\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}^\top)=\mbox{Rank}({\bf{A}}^\top {\bf{A}})=\mbox{Rank}({\bf{A}} {\bf{A}}^\top)$$

where ${\bf{A}}^\top$ is the transpose of $\bf{A}$.

To prove this, I'll use a few facts (consider all matrices real-valued):

1. If the matrices B and C are conformal for multiplication, then $\mbox{Rank}({\bf{BC}}) \leq \mbox{Rank}({\bf{B}})$ and $\mbox{Rank}({\bf{BC}}) \leq \mbox{Rank}({\bf{C}})$ (proof);

2. $\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}^\top)$ (proof);

3. If D and E are full-rank square matrices, $\mbox{Rank}({\bf{AD}})=\mbox{Rank}({\bf{EA}})=\mbox{Rank}({\bf{A}})$ (proof);

4. If A is $n\times m$ with $\mbox{Rank}({\bf{A}})=k<\min(n,m)$, then $\exists \,$ F with dimension ($n\times k$) and G with dimension ($k\times m$) such that A=FG, and $\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{F}})=\mbox{Rank}({\bf{G}})=k$ (proof in page 31, Lemma 4.9)

I'll divide the proof in two parts: i) when $\mbox{Rank}({\bf{A}})=\min(n,m)$; ii) when $\mbox{Rank}({\bf{A}})=k<\min(n,m)$

Proof of i)

WLOG, suppose that $\min(n,m)=n$, so $\mbox{Rank}({\bf{A}})=n$. Therefore, $\bf{A} \bf{A}^\top$ if a full-rank $n \times n$ square matrix. Then we can take $\mbox{Rank}({\bf{A}}^\top)$ and use fact 3 with D=$\bf{A} \bf{A}^\top$:

$$\therefore \mbox{Rank}({\bf{A}}^\top) = \mbox{Rank}({\bf{A}}^\top {\bf{D}})=\mbox{Rank}({\bf{A}}^\top {\bf{A}} {\bf{A}^\top}) \leq \mbox{Rank}({\bf{A}}^\top {\bf{A}}) \leq \mbox{Rank}({\bf{A}}^\top)$$

where the inequalities come from fact 1 using B=$\bf{A}^\top \bf{A}$ and C=$\bf{A}^\top$ for the first one, and B=$\bf{A}^\top$, and C=$\bf{A}$ for the second one.

From the above, $\mbox{Rank}({\bf{A}}^\top) \leq \mbox{Rank}({\bf{A}}^\top {\bf{A}}) \leq \mbox{Rank}({\bf{A}}^\top) \implies \mbox{Rank}({\bf{A}}^\top) = \mbox{Rank}({\bf{A}}^\top {\bf{A}})$.

Using the same argument, we get that $\mbox{Rank}({\bf{A}}) \leq \mbox{Rank}({\bf{A}} {\bf{A}}^\top) \leq \mbox{Rank}({\bf{A}}) \implies \mbox{Rank}({\bf{A}}) = \mbox{Rank}({\bf{A}} {\bf{A}}^\top )$.

From fact 2, $\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}^\top)$, so the above implies that

$$\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}^\top)=\mbox{Rank}({\bf{A}}^\top {\bf{A}})=\mbox{Rank}({\bf{A}} {\bf{A}}^\top) \quad \blacksquare$$

Proof of ii)

Now, $\mbox{Rank}({\bf{A}})=k<\min(n,m)$. From fact 4, F ($n\times k$) has rank $k$, so $\bf{F}^\top \bf{F}$ is full-rank square ($k \times k$). The same is valid for $\bf{G} \bf{G}^\top$. Thus,

$$\begin{align} \mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{F}})=\mbox{Rank}(\underbrace{{\bf{F}} {\bf{G}}}_{={\bf{A}}} {\bf{G}^\top}) = \mbox{Rank}(\bf{A}{\bf{G}^\top} \bf{F}^\top {\bf{F}})&=\mbox{Rank}(\bf{A}{\bf{A}^\top} {\bf{F}}) \\ &\leq \mbox{Rank}({\bf{A}}{\bf{A}^\top}) \\ &\leq \mbox{Rank}({\bf{A}}) \end{align}$$

$$\therefore \mbox{Rank}({\bf{A}}) \leq \mbox{Rank}({\bf{A}}{\bf{A}^\top}) \leq \mbox{Rank}({\bf{A}}) \implies \mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}{\bf{A}^\top})$$

Using a similar argument, we can show that: $$\mbox{Rank}({\bf{A}}^\top)=\mbox{Rank}({\bf{G}}^\top) \leq \mbox{Rank}({\bf{A}}^\top {\bf{A}}) \leq \mbox{Rank}({\bf{A}}^\top) \implies \mbox{Rank}({\bf{A}}^\top {\bf{A}}) = \mbox{Rank}({\bf{A}}^\top).$$

Hence,

$$\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}^\top)=\mbox{Rank}({\bf{A}}^\top {\bf{A}})=\mbox{Rank}({\bf{A}} {\bf{A}}^\top) \quad \blacksquare$$