The low-rank eigenvalue problem
This work provides a practical and efficient method for eigenvalue problems in large-scale low-rank matrices, which is relevant for applications in data science and numerical linear algebra.
The paper addresses the problem of computing eigenvalues and eigenvectors of a low-rank matrix X=AB with A,B^T in C^{N×r}, N≫r, by exploiting the identity that nonzero eigenvalues of AB equal those of BA. It proposes an efficient algorithm that forms the small r×r matrix BA and computes its eigenvalues and eigenvectors, with a characterization of Jordan block behavior for zero eigenvalues.
The nonzero eigenvalues of $AB$ are equal to those of $BA$: an identity that holds as long as the products are square, even when $A,B$ are rectangular. This fact naturally suggests an efficient algorithm for computing eigenvalues and eigenvectors of a low-rank matrix $X= AB$ with $A,B^T\in\mathbb{C}^{N\times r}, N\gg r$: form the small $r\times r$ matrix $BA$ and find its eigenvalues and eigenvectors. For nonzero eigenvalues, the eigenvectors are related by $ ABv = λv \Leftrightarrow BAw = λw $ with $w=Bv$, and the same holds for Jordan vectors. For zero eigenvalues, the Jordan blocks can change sizes between $AB$ and $BA$, and we characterize this behavior.