1

Given the eigenvalue of a matrix of large dimensions, I want to know if there is a fast way of finding the corresponded eigenvectors?

user133834
  • 361
  • 1
    Solving the linear system $(A-\lambda I) x=0$ is too slow? – lhf Jul 06 '14 at 19:35
  • Yes it is, and not always possible. Generally solving linear systems is a difficult and time consuming task. I would suggest you look up "Inverse Power Method". http://en.wikipedia.org/wiki/Inverse_iteration – Oria Gruber Jul 06 '14 at 19:36
  • since $A-\lambda I$ is singular and the dimension of A is very large, I do not know if there is any better numerical methods except for Gaussian elimination. – user133834 Jul 06 '14 at 19:39
  • @oria what is meant by "not always possible" ? – Peter Jul 06 '14 at 19:40
  • 1
    Usually you get the eigenvalue with the eigenvector, or get the eigenvector first and then estimate the eigenvalue (e.g. with a Rayleigh quotient). If you really did get the eigenvalue first, then you are trying to solve $(A-\lambda I)x=0$ one way or another. In large dimensions this would typically be done with an iterative method, but as I said initially, such iterative methods can usually be adjusted to become simultaneous eigenvalue-eigenvector solvers. – Ian Jul 06 '14 at 19:41
  • There are iterative methods, such as the elegant jacobi-method. If the solution is needed exactly (not numerically), there is barely something better than gauss-elimination – Peter Jul 06 '14 at 19:43
  • @OriaGruber Thanks. Actually the context of my problem is that I do not know what A is but only the similar matrix of A which is easier to obtain the eigenvalues. But since the eigenvectors of A and its similar matrix corresponding to the same eigenvalue might not be the same, I cannot simply apply the power method. – user133834 Jul 06 '14 at 19:43
  • 2
    If $A=PBP^{-1}$ and $x$ is an eigenvector of $B$ with eigenvalue $\lambda$ then $Px$ is an eigenvector of $A$ with eigenvalue $\lambda$. – Ian Jul 06 '14 at 19:51
  • 1
    As an aside, this technique is very useful. For example, suppose $A$ is self-adjoint with respect to $(x,y)_Q \equiv (x,Qy)$ for a positive definite $Q$. Then $QA$ is symmetric. $QA$ is of course not similar to $A$, but because $QA$ is symmetric, $Q^{1/2} A Q^{-1/2}$ is also symmetric, and is similar to $A$. Thus self-adjoint eigenproblems are equivalent to symmetric eigenproblems, once you have identified $Q$ and calculated $Q^{1/2}$. – Ian Jul 06 '14 at 20:08
  • @Ian I see it now. Thanks a lot – user133834 Jul 06 '14 at 20:12

2 Answers2

1

I don't know if it's the fastest way but recently Denton et al. showed that (https://arxiv.org/abs/1908.03795, Lemma 2)

$$ |v_{i,j}|^2\prod_{k=1;k\ne i}^n(\lambda_i(A)-\lambda_k(A))=\prod_{k=1}^{n-1}(\lambda_i(A)-\lambda_k(M_j)) $$

where

  • A is an $n \times n$ Hermitian matrix with eigenvalues $\lambda_i(A)$ and normed eigenvectors $v_i$,
  • and the elements of each eigenvector are $v_{i,j}$,
  • and $M_j$ is the $n − 1 \times n − 1$ submatrix of A that results from deleting the jth column and the jth row, with eigenvalues $\lambda_k(M_j)$.
gkcn
  • 113
1

Please refer to Finding Eigenvectors: Fast & Nontraditional way or the arXiv preprint for fast and Nontraditional approach without using the Gaussian-Jordan elimination process.

When the matrix is diagonalizable (There is a way to check that) and has a spectrum of two, there is no need to evaluate eigenvectors at all since they already appear as nonzero column vectors of certain matrices that we would like to call The eigenmatrix. We have given a general theory for diagonalizable and nondiagonalizable matrices as well.

You have access to the part of the preprint under the same link.

Udita
  • 39