Fetching the paper…

Reading the bibliography…

2019

The low-rank eigenvalue problem

Nakatsukasa, Yuji

Original
PDF
Post on X

Understand

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 = \lambda v \Leftrightarrow BAw = \lambda 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.

The low-rank eigenvalue problem · Around

Built on

Elementary divisors of A B AB and B A BA
H. Flanders · 1951
Earlier work this paper cites.
The Algebraic Eigenvalue Problem
J. H. Wilkinson · 1965
Earlier work this paper cites.
Matrix Perturbation Theory (Computer Science and Scientific Computing)
G. W. Stewart and J.-G. Sun · 1990
Earlier work this paper cites.

Similar

Eigenvalues of matrices of low rank
S. Venit and R. Katz · 2000
Cited alongside, same era.
Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
N. Halko, P.-G. Martinsson, and J. A. Tropp · 2011
Cited alongside, same era.
Matrix Computations
G. H. Golub and C. F. Van Loan · 2012
Cited alongside, same era.

Then

Flanders’ theorem for many matrices under commutativity assumptions
F. De Terán, R. A. Lippert, Y. Nakatsukasa, and V. Noferini · 2014
Later among the works it cites.
Randomized methods for matrix computations
P.-G. Martinsson · 2016
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…