Eigenvalues and Eigenvectors

Comp.145  November 1996  Dr. A.J. Mestel

(1) A column vector \underline{x} is called an eigenvector of a matrix A if, for some λ

A\underline{x} = λ\underline{x} .

Numbers λ for which this is possible are called eigenvalues of A. An n × n matrix will in general have n distinct eigenvalues and n linearly independent eigenvectors.

(2) If the matrix A corresponds to something physical, then its eigenvectors and eigenvalues will be of great significance. For example, one of the eigenvectors of a rotation matrix is the direction of the axis about which rotation takes place. Even when A has no direct interpretation, its behaviour can be best understood with reference to its eigenvalues and vectors.

(3) The above equation may be written as a set of homogeneous equations

(A − λI)\underline{x} = 0 .

For non-zero solutions of this system we must have

det(A − λI) = | \begin{matrix}a_{11} − λ & a_{12} & … & a_{1n} \\ a_{21} & a_{22} − λ & … & a_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ a_{n1} & a_{n2} & … & a_{nn} − λ \end{matrix} | = 0 .

This is an nth order polynomial equation in λ, called the characteristic (or eigenvalue) equation of A,

λ^{n} + b_{n−1}λ^{n−1} + … + b_{1}λ + b_{0} = 0 .

The n (possibly complex) roots of this equation, λ_{i} for i = 1 … n, are the eigenvalues of A. The eigenvectors, \underline{e}_{i}, may then be found by solving, for each i, the singular system (A − λ_{i}I)\underline{x} = 0. These equations have the solution \underline{x} = k\underline{e}_{i}, for an arbitrary constant k. Often, the eigenvectors are normalised by dividing by their modulus, so that \underline{e}_{i} · \underline{e}_{i} = 1.

(4) The product and sum of all the eigenvalues may be found from the theory of polynomial equations and relating the coefficients b_{i} to the matrix elements a_{ij}. We find

\begin{matrix}λ_{1} × λ_{2} × … × λ_{n} & = detA \\ λ_{1} + λ_{2} + … + λ_{n} & = T r(A) ≡ a_{11} + a_{22} + … + a_{nn} \end{matrix} \} ,

where T r(A), called the trace of A, is the sum of its diagonal elements. These relations provide a useful check when calculating eigenvalues.

(5) Since the product of the eigenvalues equals the determinant, a zero eigenvalue implies the matrix is singular. This ties in with the homogeneous equations A\underline{x} = 0 having a non-zero solution.

(6) In general, the eigenvalues and eigenvectors of a matrix may be complex. However, the eigenvalues of a symmetric matrix are all real. Furthermore, the corresponding eigenvectors are mutually perpendicular. For suppose A\underline{e}_{1} = λ_{1}\underline{e}_{1}, and A\underline{e}_{2} = λ_{2}\underline{e}_{2}. Then taking the dot product of the first equation with \underline{e}_{2} and subtracting the dot product of the second equation with \underline{e}_{1}, we find

(λ_{1} − λ_{2})(\underline{e}_{1} · \underline{e}_{2}) = \underline{e}_{2} · A\underline{e}_{1} − \underline{e}_{1} · A\underline{e}_{2} = ∑_{i,j=1}^{n} (a_{ij} − a_{ji}) (\underline{e}_{1})_{j}(\underline{e}_{2})_{i} = 0 if A is symmetric.

Thus if λ_{1} ≠ λ_{2}, we must have \underline{e}_{1} · \underline{e}_{2} = 0 and the eigenvectors are perpendicular.

(7) Since the eigenvectors of symmetric matrices are perpendicular, we may perform a sequence of rotations so that they coincide with the coordinate axes. Such a transformation can be represented by the matrix E whose columns consist of the normalised eigenvectors.

Let  E = ( \begin{matrix}↓ & ↓ & ⋮ & ↓ \\ \underline{e}_{1} & \underline{e}_{2} & : & \underline{e}_{n} \\ ↓ & ↓ & ⋮ & ↓ \end{matrix} ) ,  and E^{−1} = ( \begin{matrix}⟶ & \underline{v}_{1} & ⟶ \\ ⟶ & \underline{v}_{2} & ⟶ \\ … & … & … \\ ⟶ & \underline{v}_{n} & ⟶ \end{matrix} ) ,  say. Then

AE = ( \begin{matrix}↓ & ↓ & ⋮ & ↓ \\ λ_{1}\underline{e}_{1} & λ_{2}\underline{e}_{2} & : & λ_{n}\underline{e}_{n} \\ ↓ & ↓ & ⋮ & ↓ \end{matrix} ) = ED ,  where  D = ( \begin{matrix}λ_{1} & 0 & … & 0 \\ 0 & λ_{2} & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & λ_{n} \end{matrix} ) .

It follows that E^{−1}AE = D, and the matrix A is said to have been diagonalized by rotations. [Even non-symmetric matrices may be diagonalized by this method provided they have n linearly independent eigenvectors. However, in that case the matrix E is not a rotation matrix, and may have complex elements.] Note that for symmetric matrices, because the columns of E are normalised and mutually perpendicular, E^{−1} = E^{T} and so \underline{v}_{i} = \underline{e}_{i}.

(8) Powers of a matrix are easy to calculate in the above form. For since A = EDE^{−1},

\begin{matrix}A^{2} & = EDE^{−1}EDE^{−1} \\ & = ED^{2}E^{−1} \end{matrix} \} and A^{m} = ED^{m}E^{−1} = E ( \begin{matrix}λ_{1}^{m} & 0 & … & 0 \\ 0 & λ_{2}^{m} & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & λ_{n}^{m} \end{matrix} ) E^{−1} .

Now suppose that one of the eigenvalues, say λ_{1}, is bigger in modulus than all of the others. For large m, the matrix D^{m} will be dominated by its largest element, and so approximately

A^{m} ≈ E ( \begin{matrix}λ_{1}^{m} & 0 & … & 0 \\ 0 & 0 & … & 0 \\ ⋮ & ⋮ & 0 & ⋮ \\ 0 & 0 & … & 0 \end{matrix} ) E^{−1} ,  or  (A^{m})_{ij} ≈ λ_{1}^{m}(\underline{e}_{1})_{i}(\underline{v}_{1})_{j} .

Thus, for sufficiently large m and any vector \underline{x} (except those for which \underline{x} · \underline{v}_{1} = 0), we have A^{m}\underline{x} ≈ (\underline{x} · \underline{v}_{1})λ_{1}^{m}\underline{e}_{1} . This means that if we take a general vector, and keep multiplying it by a given matrix, eventually we will obtain a vector which is parallel to the eigenvector of A corresponding to the eigenvalue of greatest modulus. This fact enables us to understand the long-term behaviour of repetitive algorithms and networks.