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?
$\begingroup$
$\endgroup$
10
3 Answers
$\begingroup$
$\endgroup$
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
(* ==> {-762.081} *)
As mentioned, you can then also get the eigenvector this way:
ev = Eigenvectors[d - nn IdentityMatrix[Dimensions[d]], 1];
Update: version 10
In Mathematica version 10, there is another way to get the largest or smallest eigenvalues: using a Method setting with non-default "Criteria":
-Eigenvalues[-d, 1, Method -> {"Arnoldi", "Criteria" -> "RealPart"}]
(* ==> {-762.081} *)
The Arnoldi method is used when only a few eigenvalues of a large matrix are needed. By default it uses the "Magnitude" as the criteria for finding these eigenvalues. But if you specify "RealPart" instead, the eigenvalue with the largest real part is found. Since we wanted the smallest real part, I simply reversed the sign of the matrix and undid that reversal in the end.
$\begingroup$
$\endgroup$
1
The function sortify[] given in this question:
Should eigenvalues be ordered?
Tells you how to sort the eigenvalues AND eigenvectors in the canonical order for real numbers.
-
8$\begingroup$ For the problem in this question, sorting the eigenvalues after the fact would be prohibitively slow. $\endgroup$– JensSep 8, 2014 at 15:42
$\begingroup$
$\endgroup$
3
You can try this code to get the eigenvector of the smallest eigenvalue:
M = Table[RandomReal[],{i,5},{j,5}];
A = Table[M[[i,j]]+M[[j,i]],{i,5},{j,5}];
Eigensystem[A]//MatrixForm
Sort[Transpose[Eigensystem[A]],Re[#1[[1]]]<Re[#2[[1]]]&]//MatrixForm
Sort[Transpose[Eigensystem[A]],Re[#1[[1]]]<Re[#2[[1]]]&][[1,2]]//MatrixForm
the result of these codes are:
And then you will get the eigenvector with smallest eigenvalue. The function Sort[list, p] is used to order the elements in list list by condition p. Here Transpose[Eigensystem[A]] is given by a list like:
{{eigenvalue1,{eigenvector1}},{eigenvalue2,{eigenvector2}},...}
so Sort[list,p] will help you to place the eigenvectors in the order you want.
hope it will be useful to you :)
-
$\begingroup$ Your method doesn't return a single value like the answer above, in fact it returns a list of unrelated values. $\endgroup$– FeyreFeb 13, 2017 at 21:21
-
$\begingroup$ sorry the brackets in the codes have some mistake. I think it is correct now. $\endgroup$– fan9x13Feb 13, 2017 at 22:19
-
1$\begingroup$ see Igor Rivin's answer and the following comment. mathematica.stackexchange.com/a/59174/2079 $\endgroup$ Feb 13, 2017 at 22:59
Eigenvectors? (I don't know if this is necessarily efficient...) $\endgroup$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$. $\endgroup$