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


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


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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