Tiny VoltRelationship 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.
0. Singular value decompositions of matrices
We begin with writing down the SVD of A:
Here is a concatenation of a diagonal matrix of singular values and a block of zeros:
Now we can write down the SVDs of the two matrix products in terms of the SVD of A:
Similarly we have:
It is important to understand what the matrices and look like:
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 and are the same.
All these non-zero eigenvalues come from the diagonal matrix . Remember that .
2. Relationship between eigenvectors
This part is not immediately obvious. We start by asking: what does the matrix map the vector to? Here is the i-th column of i.e. it is the i-th eigenvector of .
The matrix maps the first columns of to the first columns of scaled by the singular values and the remaining columns to the zero vector.
Now we can ask the same question for : what does map the columns of to?
The matrix maps the columns of to the columns of scaled by the singular values.
3. Applications
A matrix can be seen as a table of d-dimensional features of n items. If n gets really large, the matrix 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 and using the relationships we just derived. For instance this is used in creating a dual form of sampling for determinantal point processes.