What is the most efficient way to obtain the max eigenvalue of a specific symmetric matrix via Eigen C++

Question

Suppose I have a symmetric matrix $A_{1000\times 1000}$, which can be represented by:

$A = J G J^T$

where $J$ in 1000x3 is full column rank dense matrix; $G$ in 3x3 is a nonsingular dense matrix.

What is the fastest way to obtain ONLY the maximum eigenvalue of $A$?

I know that the eigenvalue problem of symmetric matrix can be faster than that of general dense matrix, but can the following features of the problem make it even faster ?

1. only the maximum eigenvalue of $A$ is needed;

2. $A = J G J^T$, rank($A$) = 3, and $A$ has only 3 nonzero eigenvalues

Can $LDL^T$ decomposition work any good? I would prefer to implement it via Eigen C++.

Does $B=J^TJG$ has the same nonzero eigenvalues as $A$?

Answer 1

We have the matrix $A$ that can be expressed as

$A = JGJ^T$.

The first thing is to calculate the QR decomposition of matrix $J$. Because of the low rank of the matrix it can be done very fast with, for instance, modified Gram Schmidt algorithm. Now we can write $A$ as

$A = QR G R^TQ^T$,

where $Q$ is an orthonormal matrix ($Q^T Q = I$). We define $F$ as follows

$F = R G R^T$,

where $F$ is a $3\times3$ matrix. here the eigenvalues of $F$ will be the same than the ones of your original matrix $A$. But you probably want to calculate also the eigenvectors of $A$, so we continue.

Calculate the eigen decomposition of $F$:

$F = XDX^T$,

where $D$ is a diagonal matrix, and $X$ is orthonormal ($X^T X = I$). Then, inserting that expression for $F$ in the formula for $A$ we obtain

$A = QXDX^TQ^T$,

that can be rewritten as

$A = YDY^T$,.

So $Y = QX$ is a orthonormal matrix whose columns are the eigenvectors of $A$, and $D$ is the diagonal matrix with the eigenvalues of $A$. It is unique except for the ordering of the columns of $Y$ and $D$.