Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I am trying to find the eigenvector of a $20000 \times 20000$ sparse matrix associated with the smallest eigenvalue. I realized that the smallest eigenvalue might be negative; for example, if the eigenvalues of the matrix are $ \{-3,1,2,5 \}$, I want to find the eigenvector associated with $-3$, not $1$ or $5$. Therefore the commands Eigensystem[matrix,-1] or Eigensystem[matrix,1] cannot be guaranteed to return the desired result. Furthermore, I don't have a lower bound estimate for the possible smallest eigenvalue. Is there a way to find the eigenvectors efficiently?

share|improve this question
2  
I would have suggested finding the eigenvectors of $I + \epsilon A$ for sufficiently small $\epsilon$, but since you don't have a lower bound for the smallest eigenvalue you can't be sure that $\epsilon$ is sufficiently small. And in any case this might amplify the numerical error you incur. –  Rahul Narain Mar 17 at 3:52
    
Have you looked at the second argument of Eigenvectors? (I don't know if this is necessarily efficient...) –  rm -rf Mar 17 at 3:55
    
@rm-rf, I thought of that but that's assuming the eigenvectors will be returned sorted by eigenvalue, which may not be the case. –  RunnyKine Mar 17 at 3:56
    
@rm-rf I think Eigenvectors[Matrix,-1] will give me the eigenvector associated with the smallest eigenvalue in magnitude. So in the example I gave in the question, this line of code will return the eigenvector associated with $1$, not $-10$. –  SlipStream Mar 17 at 3:58
    
@RunnyKine and SlipStream: To be on the safer side, it's better to use Eigensystem so that you can verify that the eigenvalue returned is the smallest one. I believe the Eigen* functions sort by absolute value, so -10 in the example would be Eigenvectors[matrix, {1}]. Along these lines, one could then check {1} and {-1} to figure out which is min. –  rm -rf Mar 17 at 4:01

1 Answer 1

up vote 11 down vote accepted

You can always modify the matrix so that the most negative eigenvalue is also the one with the largest absolute value, and hence corresponds to the first in the list returned by EigenVectors.

An upper bound for the largest absolute value of any eigenvalue is the Hilbert-Schmidt norm. So you can rescale your matrix by subtracting this norm times the unit matrix. The eigenvalues will then be guaranteed to be no larger than zero, and therefore the most negative eigenvalue is the one with the largest absolute value.

Here I do this with the random matrix d, nicely constructed by @belisarius to be symmetric:

d = (# + Transpose@#) &@N@RandomInteger[{-10, 10}, {2000, 2000}];

nn = Norm[Flatten[d]]; 
Eigenvalues[d - nn IdentityMatrix[Dimensions[d]], 1] + nn

{-765.515}

As mentioned, you can then also get the eigenvector this way:

ev = Eigenvectors[d - nn IdentityMatrix[Dimensions[d]], 1];
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.