Eigenvalues and Eigenvectors

Let V be a finite dimensional vector space over a field F and let L:V\to V be a linear map.

As we’ve seen, if we choose a basis E of V, we can represent L by a matrix [L]_{E}^{E}, which is useful for many computations. However, the matrix depends on the choice of E. It would be useful if we could find a basis in which the matrix [L]_{E}^{E} has a particularly simple form.

The simplest possible form would be if [L]_{E}^{E} were diagonal. If we find such a basis E=\{e_1,\ldots, e_n\}, then Le_{i} = a_{i}e_{i} for some scalars a_{i} and i=1,\ldots, n.

Definition: The map L is diagonalizable if there exists a basis E such that [L]_{E}^{E} is a diagonal matrix.

A matrix A\in M_{n}(F) is diagonalizable if the linear map L_A:F^{n}\to F^{n} is diagonalizable.

Let E' be the standard basis of F^{n}. If A is diagonalizable, there is a basis E for F^{n} such that [L_A]_{E}^{E} is diagonal. Since [L_A]_{E}^{E} = [1]_{E'}^{E} [L_{A}]_{E'}^{E'}[1]_{E}^{E'} this means that A is diagonalizable if there is an invertible matrix P (corresponding to [1]_{E'}^{E} above) such that PAP^{-1} is diagonal.

In other words, A is diagonalizable if it is similar to a diagonal matrix.

We will devote a considerable amount of time and effort to exploring the question of which matrices are diagonalizable.

The characteristic polynomial

Our discussion of diagonalizability focuses our attention on vectors x such that Ax = \lambda x

for some scalar \lambda. If A were diagonalizable, vectors like this would make up the diagonal basis.

A nonzero vector with this property (for some \lambda) is called an eigenvector for A. The scalar \lambda is called the associated eigenvalue.

Similarly if L is a linear map, a non-zero vector such that Lx=\lambda x is an eigenvector for L with eigenvalue \lambda.

A (resp. L) is diagonalizable if and only if there is a basis for F^{n} (resp. V) consisting of eigenvectors for A (resp. L).

The equation Ax=\lambda x has a nonzero solution x if and only if the matrix \lambda I - A has a non-zero null space. This happens if and only if this matrix has zero determinant.

Proposition: \lambda is an eigenvalue for A if and only if \det(\lambda I - A) = 0. If the determinant is zero, any nonzero vector in the null space of \lambda I - A is an eigenvector for A with eigenvalue \lambda.

Notice that this proposition can be stated entirely in terms of linear maps.

If we treat x as a variable, we obtain the “characteristic polynomial” P_{A}(x)=\det(xI-A) of A (or of a linear map L, where we use any matrix representation of L to compute the polynomial and we call the result P_{L}(x)).

Proposition: If x is a variable, then \det(xI-A) is a monic polynomial in x of degree n.

This follows from what we know about the computation of the determinant; only one term in the expansion of the determinant has degree n, namely the product of the diagonals \prod_i(x-a_{ii}), which contributes the leading term x^n. All other terms contribute lower powers of x.

A scalar \lambda is a root of P_{A}(x) if and only if \lambda is an eigenvalue of A.

Definition: A field F is algebraically closed if every non-constant polynomial over F has a root in F.

Proposition: Let F be an algebraically closed field. Then every linear map/matrix over F has an eigenvalue (and associated eigenvector).

Proposition: The complex numbers are algebraically closed.

This famous result is called “The Fundamental Theorem of Algebra.” Many mathematicians worked toward proving this theorem, including many famous 17th and 18th century names. The first rigorous proof by modern standards was published by an amateur mathematician, Argand, in 1814. See the Wikipedia Entry for more information and various proofs.

Corollary: Every complex square matrix has an eigenvector.

Notice that this is false for real matrices. The characteristic polynomial of A = \left[\begin{matrix} 0 & 1 \\ -1 & 0 \end{matrix}\right] is x^2+1 which has no real roots.

Proposition: Not every matrix is diagonalizable.

Proof: Let V=\mathbf{C}^{2} and consider A = \left[\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}\right]

corresponding to the linear map L:V\to V given by L(x)=Ax.

The characteristic polynomial P_{L}(x)=(x-1)^2=x^2-2x+1 so the only eigenvalue of L is 1.

The equation L(x) = Ax=x has a one-dimensional solution space spanned by \left[\begin{matrix} 1 \\ 0 \end{matrix}\right].

Therefore L has only a one-dimensional subspace of eigenvectors and V has no basis of eigenvectors.

Proposition: Suppose L:V\to V is a linear map where V is n-dimensional. If L has n distinct eigenvalues, then L is diagonalizable.

Proof: This follows from the following fact: eigenvectors associated to different eigenvalues are linearly independent. To see this, suppose v_1,\ldots, v_k are eigenvectors for L, with eigenvalues \lambda_{1},\ldots,\lambda_{k}, such that all the \lambda_{i} are different and the v_{i} are dependent. Choose such a set where k is minimal. Since eigenvectors are nonzero, k>1.

Write \sum_{i=1}^{k} a_{i}v_{i} = 0 where (by minimality) all a_{i} are nonzero. Applying L yields \sum_{i=1}^{k} a_{i}L(v_{i}) = \sum a_{i}\lambda_{i}v_{i} = 0. Multiply the first equation by \lambda_1 to obtain: \begin{matrix} a_1\lambda_1 v_1 + \cdots + a_k\lambda_1 v_k &= 0 \\ a_1\lambda_1 v_1 + \cdots + a_k\lambda_k v_k &= 0 \\ \end{matrix}

Subtracting yields \sum_{i=2}^{k} a_i(\lambda_1-\lambda_i)v_{i} = 0.

Since a_j\not=0, and (again by minimality) the v_{i} for i\ge 2 are independent, this means (\lambda_1-\lambda_j)=0 which contradicts the assumption that all the \lambda_i are distinct.

For the diagonalizability result, if L has n distinct eigenvalues, then the associated eigenvectors are linearly independent and thus a basis for V. In that basis, the matrix of A=[L] is diagonal with a_{ii}=\lambda_i.

Corollary: If the characteristic polynomial P_L(x) of L has n distinct roots, then L is diagonalizable.

The converse is false: the identity matrix has characteristic polynomial (x-1)^n but is obviously diagonal.

Understanding exact conditions for diagonalizability will occupy us for a time.

The Cayley-Hamilton Theorem

Observe that if P(x) is a polynomial with coefficients in the field F, and A\in M_{n}(F) is a matrix, then P(A) makes sense as a matrix as well.

If L is a linear map, then P(L) makes sense with the understanding that L^i means the i-fold composition L\circ \cdots \circ L.

Finally, given a basis E, [P(L)]_{E}^{E} = P([L]_{E}^{E}) so we can freely move back and forth between linear maps and matrices by choice of basis.

Theorem: (Cayley-Hamilton) Let P_A(x)=\det(xI-A) be the characteristic polynomial of A. Then P_A(A)=0.

Proof: Let X=xI-A. Then XX^{adj} = \det(X)I=P_{A}(x)I

Since the entries of X^{adj} are the determinants of (n-1)\times (n-1) submatrices of X, each entry is a polynomial of degree at most n-1. We can “regroup” the terms to obtain an expression: X^{adj} = B_{0} + xB_{1}+\cdots+x^{n-1}B_{n-1} for n\times n matrices B_{i}.

Notice that xIX^{adj} = xB_{0}+\cdots+x^{n}B_{n-1}.

This is because multiplying the matrix X^{adj} by x multiplies each entry by x, so it “shifts” the coefficients up by one degree.

Also AX^{adj} = AB_{0}+\cdots + x^{n-1}AB_{n-1}

since multiplication by A acts on the terms of each degree.

Since XX^{adj} = xIX^{adj}-AX^{adj}, this gives the formula P_{A}(x)I = -AB_{0}+x(B_{0}-AB_{1}) + \cdots + x^{n-1}(B_{n-2}-AB_{n-1})+x^{n}B_{n-1}.

Substituting x=A into this expression collapses to a telescoping sum that yields zero.

Cayley-Hamilton and Invariant Subspaces

Proposition: If V is finite dimensional, L:V\to V is linear, and W\subset V is an L-invariant subspace then P_{L}(x) = P_{L|W}(x)P_{\overline{L}}(x) where P_{L|W}(x) is the characteristic polynomial of L:W\to W and P_{\overline{L}}(x) is the characteristic polynomial of the induced linear map \overline{L}:V/W\to V/W.

Proof: This follows from the multiplicative property of determinants.

Definition: If V^{\cdot} is a bounded complex of finite dimensional vector spaces, and L:V^{\cdot}\to V^{\cdot} is a linear map of complexes, then the characteristic polynomial of the complex is defined as the alternating product of the characteristic polynomials on the terms: P_{L|V^{\cdot}}(x) = \prod_{i} P_{L|V^{i}}(x)^{(-1)^{i}}

An argument using the multiplicativity of the determinant shows that this characteristic polynomial can be computed from the cohomology of the complex: P_{L|V^{\cdot}}(x)=\prod_{i} P_{L|V^{i}}(x)^{(-1)^{i}} = \prod_{i} P_{\overline{L}|H^{i}(V^{\cdot})}(x)^{(-1)^{i}}