Calculating left eigenvector when I know the right eigenvector

Question

I'm using power iteration to find the dominant right eigenvector of some large-ish matrices ($1000\times 1000$ to $10000\times 10000$ or so, maybe I'll need to go bigger later) with non-negative elements.

I need to know both the left and right eigenvectors corresponding to the largest eigenvalue. Obviously I can find the left eigenvector by doing power iteration on the transpose of the matrix. However, this is quite expensive, and since I already did power iteration to find the right eigenvector and the leading eigenvalue, it seems like there might be a way to use that information to compute the left eigenvector.

The matrices are real and have only non-negative elements, but beyond that they have no special properties, e.g. they are not symmetric and they are not stochastic matrices. The leading left and right eigenvectors have all positive elements, and I want to guarantee that numerical errors will not introduce negative elements. (This is why I'm using power iteration rather than any other method to find the leading eigenvector.) Thus I would like to avoid any technique that involves numerically inverting the matrix or anything similar to that, unless this guarantee can be kept.

I'm using Python/numpy but I'm not attached to it - I'd rather focus on what algorithm I should be using.

Answer 1

Keep in mind that the Perron-Frobenius theorem applies to non-negative matrices only in the special case that the matrix is irreducible (i.e. some power of $A$ has strictly positive elements.) You need to be sure that your nonnegative matrices are irreducible.

Furtheromre, in general you may have multiple complex eigenvalues with the same absolute value as the largest real eigenvalue- the power method isn't guaranteed to converge in this case. There are specialized methods for finding the right eigenvector corresponding to the dominant real eigenvalue that are guaranteed to converge- you should be using one of those methods. Some methods compute the left and right dominant eigenvectors at the same time, which would eliminate your problem.

Assuming that you do know the right eigenvector corresponding to the dominant real eigenvalue, then because you know the dominant eigenvalue, finding the left eigenvector corresponding to that eigenvalue is just a matter of solving a system of equations (the equations for a left eigenvector plus an extra equation to normalize the eigenvector to say $\| x \|_{1}=1$.

The Perron-Frobenious theorem (for irreducible nonnegative matrices) ensures that there will be a unique (up to normalization) real and positive left eigenvector corresponding to the dominant real eigenvalue. Thus you should be able to just solve that linear system of equations and be done with it.

As a practical matter, you might get slightly negative values in your left eigenvector after solving this system of equations. One option to enforce nonnegativity would be to apply an algorithm for nonnegative least squares (e.g. an active set method such as Parker and Stark's BVLS) to get a nonnegative least squares solution to that linear system. You'd want to check that this solution was still reasonably close to being a left eigenvector of the original matrix.

You haven't said anything about the sparsity of your $A$ matrix. This could have a huge impact on whether finding the left eigenvector by some iterative scheme or solving the linear system of equations is faster.