Let $A$ be an $m \times n$ matrix. Show $A^TA$ and $AA^T$ have the same eigenvalues

Question

Let $A$ be an $m \times n$ matrix. Show $A^TA$ and $AA^T$ have the same eigenvalues.

I'm unsure how to approach this. I'm trying to assume that $\lambda$ is an eigenvalue of $A^TA$ with its eigenvector $\neq 0$ and use that to prove that $\lambda$ is also an eigenvalue of $AA^T$ with eigenvector $Ax \neq 0$, but I'm lost on how to actually state it with notation and build off it.

Should I be trying something else?

Answer 1

Hint:

$$ AA^Tv=\lambda v \;\Rightarrow\; A^TAA^Tv=A^T\lambda v \;\Rightarrow \;A^TA(A^Tv)=\lambda(A^Tv) $$

Answer 2

First off the statement is just not true: whenever $m \neq n$, the bigger of the two matrices will have an eigenvalue $0$ of multiplicity $|n-m|$ larger than the other. Thus $0$ could be in the spectrum of one and not the other, if $A$ has maximal rank for its shape (which is the usual situation actually).

That said, one way to see it is to observe how the eigenvectors are related. The answer turns out to be that the eigenvectors of $A^T A$ are mapped by $A$ to the eigenvectors of $A A^T$, and the eigenvectors of $A A^T$ are mapped by $A^T$ to the eigenvectors of $A^T A$.

Specifically, if $(\lambda,v)$ is an eigenpair for $A^T A$ then either $Av=0$ or $(\lambda,Av)$ is an eigenpair for $A A^T$. Dually, if $(\lambda,u)$ is an eigenpair for $A A^T$ then either $A^T u=0$ or $(\lambda,A^T u)$ is an eigenpair for $A^T A$. This funny "either/or" issue only arises because $0$ can't be an eigenvector: the equations $A A^T(Av)=\lambda (Av)$ and $A^T A(A^T u)=\lambda (A^T u)$ hold regardless.

This plus the spectral theorem is basically the construction of the SVD.

Answer 3

Not true in general. For example, if $A=\begin{pmatrix}1&1\end{pmatrix}$ then:

$$AA^T=\begin{pmatrix}1&1\end{pmatrix}\begin{pmatrix}1\\1\end{pmatrix}=\begin{pmatrix}2\end{pmatrix}$$ has eigenvalue $2$ and

$$A^TA=\begin{pmatrix}1\\1\end{pmatrix}\begin{pmatrix}1&1\end{pmatrix}=\begin{pmatrix}1&1\\1&1\end{pmatrix}$$

has eigenvalues $0$ and $2$.

It is true that they share the same non-zero eigenvalues.

More generally, if $A$ is an $m\times n$ matrix, and $B$ is an $n\times m$ matrix, then the non-zero eigenvalues of $AB$ are the same as the non-zero eigenvalues of $BA.$

A fun approach uses mimimal polynomials.

First, note that $B(AB)^k=(BA)^kB$ and $A(BA)^k=(AB)^kA$.

Thus, for any polynomial, $f$, we have $Bf(AB)=f(BA)B$ and $Af(BA)=f(AB)A.$

Let $p$ be the minimal polynomial for $AB$ and $q$ be the minimal polynomial for $BA$.

Then $ABq(AB)=Aq(BA)B=0$, so $AB$ is a root of $xq(x),$ and similarly $BA$ is a root of $xp(x).$

But this means that $p(x)\mid xq(x)$ and $q(x)\mid xp(x)$, which means that $p(x)$ and $q(x)$ share the same non-zero roots, and hence $BA$ and $AB$ share the same non-zero eigenvalues.

This actually says a little more than that they have the same non-zero eigenvalues, since it also means that the multiplicity of the non-zero roots of $p(x)$ and $q(x)$ are the same.

Answer 4

Here's a high-level approach.

Let's establish some notation. For any scalar $\lambda$ and any $n\times n$ matrix $M$, we define $$ E_M^\lambda=\operatorname{Null}(\lambda\cdot I_n-M) $$ The definition of eigenvalues tells us that $\lambda$ is an eigenvalue of $M$ if and only if $\dim(E_M^\lambda)>0$. If $\lambda$ is an eigenvalue of $M$, we call $E_M^\lambda$ the eigenspace of $M$ associated to $\lambda$. Note that $E_M^\lambda$ consists of the eigenvectors of $M$ associated to the eigenvalue $\lambda$.

Theorem. Let $A$ be an $m\times n$ matrix and let $\lambda$ be a nonzero scalar. Then $E_{A^\top A}^\lambda$ and $E_{AA^\top}^\lambda$ are isomorphic as vector spaces.

Proof. Consider the diagram of linear maps

defined by $S(v)=(1/\sqrt{\lambda})\cdot Av$ and $T(v)=(1/\sqrt{\lambda})\cdot A^\top v$. The map $S$ is well-defined since $v\in E_{A^\top A}^\lambda=\operatorname{Null}(\lambda\cdot I_n-A^\top A)$ means that $A^\top Av=\lambda\cdot v$ whence \begin{align*} (\lambda\cdot I_m-AA^\top)S(v) &= (\lambda\cdot I_m-AA^\top)\frac{1}{\sqrt{\lambda}}\cdot Av \\ &= \frac{1}{\sqrt{\lambda}}\cdot (\lambda\cdot Av- AA^\top Av) \\ &= \frac{1}{\sqrt{\lambda}}\cdot (\lambda\cdot Av- \lambda\cdot Av) \\ &= O \end{align*} Similarly, one can argue that $T$ is well-defined.

Now, note that $v\in E_{AA^\top}^\lambda$ implies that $AA^\top v=\lambda\cdot v$ whence $$ S(T(v)) = S\left(\frac{1}{\sqrt{\lambda}}\cdot A^\top v\right) = \frac{1}{\sqrt{\lambda}}\cdot\frac{1}{\sqrt{\lambda}}\cdot AA^\top v = \frac{1}{\lambda}\cdot\lambda\cdot v = v $$ Similarly, $T(S(v))=v$. This proves that $T=S^{-1}$, so $S$ is an isomorphism. Hence $E_{AA^\top}^\lambda$ and $E_{A^\top A}^\lambda$ are isomorphic as vector spaces as advertised. $\Box$

We now have the desired result as a corollary.

Corollary. Let $A$ be an $m\times n$ matrix. Then $A^\top A$ and $AA^\top$ have the same nonzero eigenvalues. Moreover, the algebraic and geometric multiplicities of $\lambda$ as an eigenvalue of $A^\top A$ and $AA^\top$ are the same.