Relationship between AAᵀ and AᵀA

We look into the relationship between eigenvalues and eigenvectors of AAᵀ and AᵀA for a real-valued matrix A of shape (r x c). Without losing generality, we can assume that the matrix is wide i.e. r < c.

A (r,c) Aᵀ (c,r) AAᵀ (r,r) AᵀA (c,c)

0. Singular value decompositions of matrices

We begin with writing down the SVD of A:

A=U⏟r×r Σ⏟r×c VT⏟c×cA = \underbrace{U}_{\textcolor{#b45309}{r \times r}} \ \underbrace{\Sigma}_{\textcolor{#b45309}{r \times c}} \ \underbrace{V^T}_{\textcolor{#b45309}{c \times c}}

Here Σ\Sigma is a concatenation of a diagonal matrix of rr singular values and a block of zeros:

Σ=[ σ⏟r×r (diagonal) ; 0⏟r×(c−r) (zeros) ]\Sigma = [\ \underbrace{\sigma}_{\textcolor{#b45309}{r \times r \text{ (diagonal)}}} \ ; \ \underbrace{0}_{\textcolor{#b45309}{r \times (c-r) \text{ (zeros)}}} \ ]

Now we can write down the SVDs of the two matrix products in terms of the SVD of A:

AAT=U ΣΣT⏟r×r UTAA^T = U \ \underbrace{\textcolor{#b45309}{\Sigma\Sigma^T}}_{\textcolor{#e11d48}{r\times r}} \ U^T

Similarly we have:

ATA=V ΣTΣ⏟c×c VTA^TA = V \ \underbrace{\textcolor{#b45309}{\Sigma^T\Sigma}}_{\textcolor{#e11d48}{c\times c}} \ V^T

It is important to understand what the matrices ΣΣT\Sigma\Sigma^T and ΣTΣ\Sigma^T\Sigma look like:

ΣΣT=σ2⏟r×rΣTΣ=[σ200T0T0]⏟c×c\Sigma\Sigma^T = \underbrace{\sigma^2}_{\textcolor{#b45309}{r \times r}} \qquad\qquad \Sigma^T\Sigma = \underbrace{\begin{bmatrix} \sigma^2 & 0 \\ 0^T & 0^T0 \end{bmatrix}}_{\textcolor{#b45309}{c \times c}}

Now we are ready to draw some insights.

1. Relationship between eigenvalues

From the singular value decompositions above, the following insight becomes clear:

The sets of non-zero eigenvalues of AATAA^T and ATAA^TA are the same.

All these non-zero eigenvalues come from the diagonal matrix σ2\sigma^2. Remember that Σ=[ σ⏟r×r ; 0⏟r×c−r ]\Sigma = [\ \underbrace{\sigma}_{\textcolor{#b45309}{r \times r}} \ ; \ \underbrace{0}_{\textcolor{#b45309}{r \times c-r}} \ ].

2. Relationship between eigenvectors

This part is not immediately obvious. We start by asking: what does the matrix AA map the vector viv_i to? Here viv_i is the i-th column of VV i.e. it is the i-th eigenvector of VV.

Avi=U Σ VTvi⏟ei=U Σ ei⏟i-th column of Σ=σiui if i<r else 0\begin{align} Av_i &= U \ \Sigma \ \underbrace{\textcolor{#b45309}{V^T v_i}}_{\textcolor{#b45309}{e_i}} \\ &= U \ \underbrace{\Sigma \ \textcolor{#b45309}{e_i}}_{\textcolor{#b45309}{\text{i-th column of } \Sigma}} \\ &= \textcolor{#b45309}{\sigma_i u_i} \ \text{if } i \lt r \ \text{else} \ \textcolor{#b45309}{0} \end{align}

The matrix AA maps the first rr columns of VV to the first rr columns of UU scaled by the singular values and the remaining columns to the zero vector.

vi→A→{σiui,1≤i≤r0,r<i≤cv_i \rightarrow A \rightarrow \begin{cases} \sigma_i u_i, & 1 \le i \le r \\ 0, & r \lt i \le c \end{cases}

Now we can ask the same question for ATA^T: what does ATA^T map the columns of UU to?

ATui=V ΣT UTui⏟ei=V ΣT ei⏟i-th column of ΣT=σivi\begin{align} A^T u_i &= V \ \Sigma^T \ \underbrace{\textcolor{#b45309}{U^T u_i}}_{\textcolor{#b45309}{e_i}} \\ &= V \ \underbrace{\Sigma^T \ \textcolor{#b45309}{e_i}}_{\textcolor{#b45309}{\text{i-th column of } \Sigma^T}} \\ &= \textcolor{#b45309}{\sigma_i v_i} \end{align}

The matrix ATA^T maps the columns of UU to the columns of VV scaled by the singular values.

ui→AT→σivi, 1≤i≤ru_i \rightarrow A^T \rightarrow \sigma_i v_i, \ 1 \le i \le r

3. Applications

A matrix A∈Rd×nA \in R^{d \times n} can be seen as a table of d-dimensional features of n items. If n gets really large, the matrix ATA∈Rn×nA^TA \in R^{n \times n} gets too large to perform operations like eigendecomposition, which are quite common in machine learning. In this case, the eigenvalues and eigenvectors of the large matrix can be calculated using AAT∈Rd×dAA^T \in R^{d \times d} and using the relationships we just derived. For instance this is used in creating a dual form of sampling for determinantal point processes.

Related articles: