Information About Matrix Eigenvalue Problem

	CATEGORIES ABOUT EIGENVALUE ALGORITHM
	numerical linear algebra

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME
	MORE SHOPPING...

In Linear Algebra , one of the most important problems is designing efficient and Stable Algorithm s for finding the Eigenvalue s of a Matrix . These eigenvalue algorithms may also find Eigenvectors . CHARACTERISTIC POLYNOMIAL Given a square matrix ''A'', an eigenvalue λ and its associated eigenvector v are, by definition, a pair such that :$A\{\backslash bold\; v\}\; =\; \backslash lambda\{\backslash bold\; v\}\; \backslash ,\backslash !\; .$ Equivalently, (''A''−λ''I'')v = 0, implying det(''A''−λ''I'') = 0. This Determinant expands to a polynomial in λ, called the Characteristic Polynomial of ''A''. One common method for finding the eigenvalues of a small matrix is by finding Roots of the characteristic polynomial. This is explained in more detail in the article Symbolic Computation Of Matrix Eigenvalues . Unfortunately, this method has some limitations. A general polynomial of order ''n'' > 4 cannot be solved by a finite sequence of arithmetic operations and radicals (see Abel-Ruffini Theorem ). There do exist efficient Root-finding Algorithm s for higher order polynomials. However, finding the roots of the characteristic polynomial may be an Ill-conditioned problem even when the underlying eigenvalue problem is well-conditioned. For this reason, this method is rarely used. The above discussion implies a restriction on all eigenvalue algorithms. It can be shown that for any polynomial, there exists a matrix (see Companion Matrix ) having that polynomial as its characteristic polynomial (actually, there are infinitely many). If there did exist a finite sequence of arithmetic operations for exactly finding the eigenvalues of a general matrix, this would provide a corresponding finite sequence for general polynomials, in contradiction of the Abel-Ruffini theorem. Therefore, general eigenvalue algorithms are expected to be Iterative . POWER ITERATION

Eigenvalues of 3×3 matrices


If
:
then the characteristic polynomial of ''A'' is
:

The eigenvalues of the matrix are the roots of this polynomial, which can be found using the method for solving Cubic Equation s.

A formula for the eigenvalues of a 4x4 matrix could be derived in an analogous way, using the formulae for the solutions of the Quartic Equation .


Eigenvalues and eigenvectors of special matrices

For matrices satysfying $A^2=\backslash alpha$ one can write explicit formulas for the possible eigenvalues and the projectors on the corresponding eigenspaces.
:
:
with
:$AP\_+=\backslash sqrt\{\backslash alpha\}P\_+\; \backslash quad\; AP\_-=-\backslash sqrt\{\backslash alpha\}P\_-$
and
:$P\_+P\_+=P\_+\; \backslash quad\; P\_-P\_-=P\_-\; \backslash quad\; P\_+P\_-=P\_-P\_+=0$
This provides the following resolution of identity
:
+ rac{1}{2}\left(I-rac{A}{\sqrt{\alpha}} ight)


The multiplicity of the possible eigenvalues is given by the rank of the projectors.


Example computation

The computation of eigenvalue/eigenvector can be realized with the following algorithm.

Consider an n-square matrix ''A''
:1. Find the roots of the characteristic polynomial of ''A''. These are the eigenvalues.

• If n different roots are found, then the matrix can be diagonalized.

:2. Find a basis for the kernel of the matrix given by $B-\backslash lambda\_n\; I$. For each of the eigenvalues. These are the eigenvectors

• The eigenvectors given from different eigenvalues are linearly independent.


• The eigenvectors given from a root-multiplicity are also linearly independent.

Let us determine the eigenvalues of the matrix
:$$
A = \begin{bmatrix}
0 & 1 & -1 \
1 & 1 & 0 \
-1 & 0 & 1
\end{bmatrix}

which represents a linear operator R³ → R³.


Identifying eigenvalues

We first compute the characteristic polynomial of ''A'':
:$$
p(\lambda) = \det( A - \lambda I) =
\det \begin{bmatrix}
-\lambda & 1 & -1 \
1 & 1-\lambda & 0 \
-1 & 0 & 1-\lambda
\end{bmatrix}
= -\lambda^3 + 2\lambda^2 +\lambda - 2.

This polynomial factors to $p(\backslash lambda)\; =\; -(\backslash lambda\; -\; 2)\; (\backslash lambda\; -\; 1)\; (\backslash lambda\; +\; 1)$. Therefore, the eigenvalues of ''A'' are 2, 1 and −1.


IDENTIFYING EIGENVECTORS

With the eigenvalues in hand, we can solve sets of simultaneous linear equations to determine the corresponding eigenvectors. Since we are solving for the system $(A\; -\; \backslash lambda\; I)v\; =\; 0\backslash ,$, if $\backslash lambda\; =\; 2$ then,

:$$
\begin{bmatrix}
-2 & 1 & -1 \
1 & -1 & 0 \
-1 & 0 & -1
\end{bmatrix}
\begin{bmatrix}
v_1 \
v_2 \
v_3
\end{bmatrix} = 0.


Now, reducing $(A\; -\; 2I)\backslash ,$ to Row Echelon Form :
:$$
\begin{bmatrix}
-2 & 1 & -1 \
1 & -1 & 0 \
-1 & 0 & -1
\end{bmatrix} o
\begin{bmatrix}
1 & 0 & 1 \
0 & 1 & 1 \
0 & 0 & 0
\end{bmatrix}


allows us to solve easily for the eigenspace $E\_2$:
:$$
\begin{bmatrix}
1 & 0 & 1 \
0 & 1 & 1 \
0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
v_1 \
v_2 \
v_3
\end{bmatrix} = 0 o
\begin{cases}
v_1 + v_3 = 0 \
v_2 + v_3 = 0
\end{cases}
::$o\; E\_2\; =\; \{\; m\; span\}\backslash begin\{bmatrix\}1\; \backslash \; 1\; \backslash \; -1\backslash end\{bmatrix\}$.

We can confirm that a simple example vector chosen from eigenspace $E\_2$ is a valid eigenvector with eigenvalue $\backslash lambda\; =\; 2$:

: $A\; \backslash begin\{bmatrix\}\; \backslash ;\; 1\; \backslash \; \backslash ;\; 1\; \backslash \; -1\; \backslash end\{bmatrix\}$
= \begin{bmatrix} \; 2 \ \; 2 \ -2 \end{bmatrix}
= 2 \begin{bmatrix} \; 1 \ \; 1 \ -1 \end{bmatrix}


Note that we can determine the degrees of freedom of the solution by the number of pivots.

If ''A'' is a Real matrix, the characteristic polynomial will have real coefficients, but its roots will not necessarily all be real. The Complex eigenvalues come in pairs which are Conjugate s. For a real matrix, the eigenvectors of a non-real eigenvalue ''z'' , which are the solutions of $(A\; -\; zI)v\; =\; 0$, cannot be real.

If ''v''₁, ..., ''v''_''m'' are eigenvectors with different eigenvalues λ₁, ..., λ_''m'', then the vectors ''v''₁, ..., ''v''_''m'' are necessarily Linearly Independent .

The Spectral Theorem for symmetric matrices states that if ''A'' is a real symmetric ''n''-by-''n'' matrix, then all its eigenvalues are real, and there exist ''n'' linearly independent eigenvectors for ''A'' which are mutually Orthogonal . Symmetric matrices are commonly encountered in engineering.

Our example matrix from above is symmetric, and three mutually orthogonal eigenvectors of ''A'' are

:$v\_1\; =\; \backslash begin\{bmatrix\}\backslash ;\; 1\; \backslash \; \backslash ;1\; \backslash \; -1\; \backslash end\{bmatrix\},\backslash quad\; v\_2\; =\; \backslash begin\{bmatrix\}\backslash ;\; 0\backslash ;\backslash \; 1\; \backslash \; 1\; \backslash end\{bmatrix\},\backslash quad\; v\_3\; =\; \backslash begin\{bmatrix\}\backslash ;\; 2\; \backslash \; -1\; \backslash \; \backslash ;\; 1\; \backslash end\{bmatrix\}.$

These three vectors form a Basis of R³. With respect to this basis, the Linear Map represented by ''A'' takes a particularly simple form: every vector ''x'' in R³ can be written uniquely as
:$x\; =\; x\_1\; v\_1\; +\; x\_2\; v\_2\; +\; x\_3\; v\_3$
and then we have
:$A\; x\; =\; 2x\_1\; v\_1\; +\; x\_2\; v\_2\; -\; x\_3\; v\_3.$


ADVANCED METHODS


A popular method for finding eigenvalues is the QR Algorithm , which is based on the QR Decomposition . Other advanced methods include:

• Inverse Iteration


• Rayleigh Quotient Iteration


• Arnoldi Iteration


• Lanczos Iteration


• Jacobi Method


• Bisection


• Divide-and-conquer

Most eigenvalue algorithms rely on first reducing the matrix A to Hessenberg or Tridiagonal form. This is usually accomplished via Projections .