Efficient method for determining to the most positive eigenvalue of a matrix

Question

I am trying to implement an algorithm that requires knowing the largest $\textbf{positive}$ eigenvalue of a $\textbf{real symmetric, non-sparse}$ matrix and the corresponding eigenvector. The actual value of the most positive eigenvalue is not required, I only really require the corresponding eigenvector. Moreover, the accuracy of the elements in the eigenvector is not of great importance, I only need the signs of the elements in said eigenvector to be correct.

My current best idea for a solution is to use the Power Iteration method repeatedly until I find the first positive eigenvalue (and hence the most dominant positive). However, since the rows and columns of the matrices I am working with sum to zero, zero is always an eigenvalue. So, if all of the eigenvalues are negative except for the zero eigenvalue, this is as inefficient as calculating all of the eigenvalues (for which there are much faster methods than the Power Iteration method).

More succinctly, I would like some incite on the most efficient method for determining the signs of the elements of the eigenvector that correspond to the most $\textbf{positive}$ eigenvalue of a matrix.

Any suggestions would be greatly appreciated, and if anymore information would be helpful please let me know.

$\textbf{UPDATE:}$ I am working with matrices described by Eq. 2 in this paper.

The values of the matrices are determined by taking each entry of the adjacency matrix and subtracting the probable number of edges between those two nodes (given as $\frac{\operatorname{deg}(u)\operatorname{deg}(v)}{2m}$ where $u,v \in G$ and $m$ is the size of $G$).

-nem

Answer 1

Use power iteration once to find the largest magnitude eigenvalue $\lambda$. If $\lambda >0$, you're done. Otherwise, add $\lambda I$ to your matrix and perform power iteration again to get the new largest magnitude eigenvalue $\mu$. This $\mu$ must be positive and the most positive eigenvalue of your original matrix is $\mu-\lambda$.

Answer 2

Just making a slight correction to @user7530's idea.

Use power iteration once to find the largest magnitude eigenvalue . If $\lambda > 0$, you're done.

Otherwise, subtract $\lambda I$ from your matrix $M$ (remember here $\lambda$ is negative) to get a new matrix $A = M - \lambda I$ which has exclusively non-negative eigenvalues and whose largest eigenvalue is $\mu = \gamma - \lambda$ (where $\gamma$ is the largest positive eigenvalue of the original matrix $M$.

Therefore after applying power iteration on matrix $A$ we have that the largest positive eigenvalue of the original matrix $M$ is $\gamma = \mu + \lambda$.