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

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.

$\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

• Add some positive multiple of the identity to shift the spectrum?
– p.s.
Jun 16 '14 at 0:20
• You say "However, since the rows and columns of the matrices I am working with sum to zero..." Are you working with Laplacian matrices? If so, then you can be sure that the eigenvalues of your matrix are all non-negative. Can you describe the context of where how your matrices are determined? Jun 16 '14 at 1:07
• They aren't Laplacian matrices, no. The fact that they have that property is reminiscent of Laplacian matrices as described by the paper which contains the algorithm I'm implementing. Eq. 2 and 3 of this paper describe the matrices I am working with in more detail.
– Nem
Jun 16 '14 at 1:38

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$.