8
$\begingroup$

Normally, I would first work out the eigenvalues of a matrix and use them to determine the eigenvectors. However, is it possible to go the other way around?

Is there any way to determine the eigenvectors of a matrix without working out the eigenvalues?

$\endgroup$
  • $\begingroup$ I think it's only possible if matrix is diagonal with all equal diagonal entries. $\endgroup$ – Subhajit Jul 3 at 14:19
5
$\begingroup$

The power method uses the fact that from an arbitrary vector, we have some decomposition

$$\vec v=v_1\vec e_1+v_2\vec e_2+\cdots v_n\vec e_n$$ in terms of the Eigenvectors, and after $m$ applications of the matrix,

$$A^m\vec v=\lambda_1^mv_1\vec e_1+\lambda_2^mv_2\vec e_2+\cdots \lambda_n^mv_n\vec e_n.$$

If the largest Eigenvalue, let $\lambda_1$, is simple,

$$A^m\vec v\approx\lambda_1^mv_1\vec e_1$$ and $A^m\vec v$ tends to an Eigenvector.

(In practice you take high powers by successive squarings of $A$ and rescale the intermediate results to avoid overflow.)


The method does not give you the Eigenvalue directly, you can compute

$$\vec u_1=\frac{A^m\vec v_1}{\|A^m\vec v_1\|}$$ and $$\lambda_1=\vec u_1^TA\vec u_1.$$


Obtaining the next Eigenvectors is possible, provided that you remove from $\vec v$ the contributions of the preceding Eigenvectors, by projection (as in a Gram-Schmidt process). You have to do this periodically, because the numerical errors will make the Eigenvectors corresponding to the large Eigenvalues resurface.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you please elaborate on how to take high powers of matrices? $\endgroup$ – inquisitor Jul 5 at 12:26
4
$\begingroup$

Most of the iterative numerical methods produce approximations to eigenvectors and eigenvalues at the same time.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Since you say you "work out the eigenvalues of the matrix" I guess you mean that you find the characteristic polynomial (for example by expanding a determinant) and then find its roots.

That is not a practical method except for very small matrices (e.g order less than about 5) for two reasons: evaluating the determinant to find the polynomial is very time consuming, and the polynomial is usually very ill conditioned so you need extremely accurate values of the coefficients.

The Power method described in another answer is probably the only practical method which computes an eigenvector completely independently of its eigenvalue.

However there are several standard numerical methods which compute (a subset of) the eigenvalues and vectors simultaneously.

One class of methods is based on the properties of a Krylov subspace of the matrix. The Krylov subspace of order $n$ corresponding to an arbitrary vector $b$ is spanned by the vectors $b, Ab, A^2b, \dots\ A^{n-1}b$. These are the same vectors computed in the Power method.

Computing the Krylov subspace is efficient if $A$ is sparse, since it only involves matrix multiplications.

You might hope that by orthogonalizing the Krylov vectors somehow, you will get an approximation to the extreme eigenvectors of the original matrix (i.e. the vectors corresponding either to the highest or the lowest eigenvalues). The efficient way to do this is not to orthogonalize the vectors completely, but partially, so that if $K$ is the rectangular matrix containing the "partially orthogonal" vectors, the product $K^T K$ is tridiagonal, not diagonal. There are efficient methods to calculate the eigenvalues and vectors of a tridiagonal matrix, and they can be used to recover the eigenpairs of the original matrix $A$.

This basic idea is known as Arnoldi iteration after its inventor. The important special case of symmetric or Hermitian matrices was invented independently, and is knowns as Lanczos iteration. Since about 1985, when some practical problems with it were overcome, this is a "goto" method for solving very large eigenproblems, where "large" might be something like "find the smallest 3,000 eigenvalues and the corresponding vectors for a matrix of order 300,000".

See https://en.wikipedia.org/wiki/Arnoldi_iteration and https://en.wikipedia.org/wiki/Lanczos_algorithm for more details

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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