Apprentice Linear Algebra, 4th lecture, 07/08/05

REU 2005

Instructor: László Babai Scribe: Wei Ren

4 Eigenvalues and Eigenvectors

4.1 System of Linear Equations

Recall that a system of k linear equations in ℓ unknowns can be represented concisely as

Ax = b,  (1)

where A is a k×ℓ matrix. We say the system is homogeneous if b = 0, and we have proven that for a homogeneous system of linear equations, the set of solutions U is a subspace of ℝ^{ℓ}, and in fact the basic fact on systems of linear equations tells us dim(U) = ℓ−rk(A). Consequently, we have the following theorem:

Theorem 4.1. A system of homogeneous linear equations has a non-trivial solution iff rk(A) < ℓ; i.e., the matrix A does not have full column-rank (its rank is less than the number fo columns).

Proof: By the basic fact, if rk(A) < ℓ, then dim(U) > 0. This means U has a non-zero vector, i.e., a non-trivial solution.

Since the row rank is equal to the column rank for any matrix, it immediately follows that

Corollary 4.2. If k < ℓ (there are fewer equations than unknowns), then the system has a nontrivial solution.

Now we consider non-homogeneous systems, where b ≠ 0. We want to know when such

a system has a solution. Recall that if x = [ x_{1} ; ⋮ ; x_{ℓ} ], and the matrix A is written as A =

[ a_{1} … a_{ℓ} ], where a_{i} is the i^{th} column of the matrix, then Ax = ∑_{i=1}^{i=ℓ} x_{i}a_{i} is simply a linear combination of the columns. Therefore if Ax = b holds, then b ∈ Span{a_{1}, …, a_{ℓ}}. Recall that the span of the a_{i} is called the column space of the matrix A. It follows that rk(A) = rk ([A|b]), where the augmented matrix [A|b] is defined as [ a_{1} … a_{ℓ} b ]. Conversely, if we know rk(A) = rk ([A|b]), then b is in the column space of A. We have thus shown the following:

Theorem 4.3. The system of linear equations Ax = b has a solution iff rk(A) = rk ([A|b]).

Using the above theorem, we can determine whether or not a given system has a solution. To completely describe the set of solutions for Ax = b, we consider the related homogeneous system, Ax = 0, and let U be the its set of the solutions. We have the following description:

Theorem 4.4. If Ax = b has a solution w, then the solution set for the system is

U + w := {x + w | x ∈ U}.

Proof: We have Ax = b ⟺ Ax = Aw ⟺ A(x − w) = 0 ⟺ x − w ∈ U.

Note that the theorem states the solution set for any system of linear equations is either empty or it is a translate of a subspace (the solution space for the corresponding homogeneous system).

4.2 Eigenvectors

Let M_{n}(𝔽) denote the set of all n×n matrices. First note that it is a ring, because we have the 3 usual arithmetic operations (addition, subtraction and multiplication). In addition, M_{n}(𝔽) is a vector space over 𝔽, of dimension n^{2}. To see this, define E_{ij} to be the matrix whose only nonzero entry is the ij^{th} entry, and its value is 1. For any matrix A = (a_{ij}), we have A = ∑ a_{ij}E_{ij}. The representation is unique and this shows the set {E_{ij}}_{j=1...n^{i=1...n}} form a basis

for M_{n}(𝔽).

Definition 4.5. A ring A is an algebra over 𝔽 if A is also a vector space over 𝔽 and it satisfies the identity

(∀λ ∈ 𝔽)(∀a, b ∈ A)((λa)b = λ(ab)).

Examples 4.6. The field of complex numbers ℂ is a field extension of ℚ, so it is a vector space over ℚ. It also has a ring structure. Therefore ℂ is an (infinitely dimensional) algebra over ℚ. It is also a 2−dimensional algebra over ℝ.

The next definition is one of the most important in all of linear algebra.

Definition 4.7. Let A ∈ M_{n}(𝔽). A vector x ∈ 𝔽^{n} is an eigenvector of A if

(i) x ≠ 0,

(ii) Ax = λx for some λ ∈ 𝔽.

Eigenvectors can also be defined for linear transformations.

Definition 4.8. Let f : V → V be a linear transformation. A vector x ∈ V is an eigenvector of f if

(i) x ≠ 0,

(ii) f(x) = λx for some λ ∈ 𝔽.

Naturally we also have the following definition:

Definition 4.9. We say λ ∈ 𝔽 is an eigenvalue of the matrix A (resp. of the linear map f) if there is an eigenvector x ∈ 𝔽^{n} (resp. x ∈ V) s.t. Ax = λx (resp. f(x) = λx).

Examples 4.10. Consider the geometric transformation that reflects vectors in 3−space in a given plane. Any nonzero vector that is orthogonal to the plane is an eigenvector, with eigenvalue −1. Any nonzero vector in the plane is also an eigenvector, with eigenvalue 1.

Examples 4.11. We now define a geometric transformation in the plane that has eigenvalues 2 and 3. Take any two nonzero vectors that are not parallel to each other, say v_{1} and v_{2}. We know the set {v_{1}, v_{2}} is a basis for the plane. We can define a linear map by specifying its actions on a basis. Define L by L(v_{1}) = 2v_{1}, L(v_{2}) = 3v_{2}, i.e., the map L stretches vectors by a factor of 2 in the direction of v_{1}, and it stretches in the direction of v_{2} by a factor of 3. Then the vector v_{1} is an eigenvector with eigenvalue 2, and v_{2} is an eigenvector with eigenvalue 3.

The following exercise puts a bound on the maximal number of eigenvalues we can have.

Exercise 4.12. Prove that if e_{1}, …, e_{k} are eigenvectors to distinct eigenvalues, then they are linearly independent.

An immediate corollary to this exercise is:

Corollary 4.13. The number of eigenvalues is ≤ n, or dim(V).

Definition 4.14. An eigenbasis is a basis consisting of eigenvectors.

A linear transformation may or may not have an eigenbasis, as the examples below illustrate.

Examples 4.15. Consider rotation of a plane by an angle of α, where α is not a multiple of π. Then this transformation has no eigenvectors at all.

Examples 4.16. Consider the shearing transformation of the plane, which in coordinates can be defined by (x, y) ↦ (x + y, y). We see geometrically that all eigenvectors lie on the line defined by (1, 0). Therefore we do not have an eigenbasis.

Examples 4.17. The transformation that reflects a vector in ℝ^{3} across a given plane does have an eigenbasis. As we have observed before, all vectors in the plane, as well as vectors orthogonal to the plane, are eigenvectors. Therefore to form a basis, we simply pick one vector that is orthogonal, and then two non-parallel vectors from the plane.

The next theorem is one of the most widely applied mathematical results not only within mathematics but in science and engineering. We will prove it later in the course.

Theorem 4.18 (The Spectral Theorem). If A is a symmetric real matrix (i.e., A^{T} = A), then A has an orthogonal eigenbasis.

An orthogonal eigenbasis means an eigenbasis where the basis vectors are pairwise orthogonal (perpendicular).

Examples 4.19. One application of the Spectral Theorem spawned a branch of Statistics called “Factor Analysis.” One can prove, using the Spectral Theorem, that for any n given random variables, there exists a set of pairwise uncorrelated random variables such that the original random variables and the new (uncorrelated) random variables have the same span, i. e., each of the original random variables can be expressed as a linear combination of the new (uncorrelated) variables (the “factors”) and each new variable can be expressed as a linear combination of the original ones.

Examples 4.20. Another example, in mechanics, is the theorem that every solid body has 3 perpendicular axes of inertia (if rotated about one of these axes and then left alone, the body will continue to rotate about the axis). In other words, from the point of view of rigid motion, each solid body, no matter how irregularly shaped, can be replaced by an ellipsoid.

Next we study the equation

Ax = λx.

We want to know what values of λ will get us nontrivial solutions for x, which will then be eigenvectors. By rearranging the terms, we get the following system:

(λI − A)x = 0.

Here I denotes the identity matrix. By theorem (4.1), we see that this system has a nontrivial solution iff the matrix (λI − A) does not have full rank.

We have the following definition:

Definition 4.21. A matrix A ∈ M_{n}(𝔽) is singular if it does not have full rank. Equivalently, it is singular if det(A) = 0.

The discussion before the definition now shows

Theorem 4.22. The value λ is an eigenvalue of A iff det(λI − A) = 0.

Examples 4.23. We consider the 2 × 2 matrices. Let A = [ \begin{matrix}a & b \\ c & d \end{matrix} ]. Then we get

det(λI − A) = | \begin{matrix}λ − a & b \\ c & λ − d \end{matrix} |
= (λ − a)(λ − d) − bc
= λ^{2} − (a + d)λ + (ad − bc).

Note that in the last equation, we have (a + d) = tr(A), (ad − bc) = det(A). Solutions to this quadratic equation (in λ) are the eigenvalues of A.

Inspired by the preceding example, we have the following definition:

Definition 4.24. The characteristic polynomial of A is defined to be

f_{A}(x) = det(xI − A).

Observe that for an n × n matrix A, its characteristic polynomial is of degree n (in x). Moreover, we can express the coefficients of this polynomial as follows:

a_{n} = 1;

a_{n−1} = −T r(A);

a_{n−2} = ∑ det(2 × 2 symmetric minors); a_{n−3} = − ∑ det(3 × 3 symmetric minors);

⋮

a_{0} = f_{A}(0) = det(−A) = (−1)^{n} det(A).

In summary, we have

a_{n−i} = (−1)^{i} ∑ det(i × i symmetric minors),  (2)

where the sum is taken over all such symmetric minors. (An i × i symmetric minor is an i × i submatrix of A that is symmetric along the diagonal.) Note that there are \binom{n}{i} terms in this sum.

Exercise 4.25. Verify equation (2).

4.3 Matrices, Bases and Linear Transformations

In the previous sectin, we defined eigenvectors and eigenvalues separately for matrices and linear maps. In this section, we will show that every linear transformation can be represented as a matrix, by choosing a basis.

Suppose φ : V → W is a linear map, where V has dimension ℓ and W has dimension k. Recall that any vector x ∈ V can be uniquely represented by its coordinates in a given basis. In other words, if \underline{e} := \{e_{1}, …, e_{ℓ}\} is a basis for V, then we have x = ∑_{i=1}^{i=ℓ} α_{i}e_{i}, for α_{i} ∈ 𝔽.

We write [x]\underline{e} = ( α_{1} ; ⋮ ; α_{ℓ} ).

Observe that map x ↦ [x]\underline{e} is a one-to-one and onto map between V and 𝔽^{n}. We thus have an isomorphism V ≈ 𝔽^{n}.

Now fix this basis \underline{e} for V, and similarly fix a basis \underline{f} for W: \underline{f} = \{f_{1}, …, f_{k}\}. Define

[φ]_{\underline{e},\underline{f}} := [ [φe_{1}]\underline{f} , … [φe_{ℓ}]\underline{f} ] .

Here each [φe_{i}]\underline{f} is a column vector of height k, and therefore [φ]_{\underline{e},\underline{f}} is a k × ℓ matrix.

The following example illustrates how to find this matrix we just defined. It is also one of the most delightful matrices.

Examples 4.26. We come back to our favorite example of linear transformation, rotation of a plane by an angle of α. Denote this transformation by φ_{α}. We think of the plane as ℝ^{2}. Let \underline{e} be the standard basis of ℝ^{2}. For simplicity, we will write [φ_{α}]\underline{e} instead of [φ_{α}]_{\underline{e},\underline{e}}. We will use this convention for all the later examples, and we always use the same basis whenever we have a map from a vector into itself.

To find the matrix [φ_{α}]\underline{e}, we must express φ_{α}(e_{1}) and φ_{α}(e_{2}) as linear combinations of e_{1} and e_{2}. By a simple geometric observation, we get φ_{α}(e_{1}) = (cos α)e_{1} + (sin α)e_{2}. For the second basis vector, note that we have the relation φ_{\frac{π}{2}} (x, y) = (−y, x). Since the composition of rotations is clearly commutative, we have

φ_{α}(e_{2}) = φ_{α} ∘ φ_{\frac{π}{2}} (e_{1})
= φ_{\frac{π}{2}} ∘ φ_{α}(e_{1})
= φ_{\frac{π}{2}} ((cos α)e_{1} + (sin α)e_{2})
= (− sin α)e_{1} + (cos α)e_{2}.

Therefore now by definition, we get

[φ_{α}]\underline{e} = [ \begin{matrix}cos α & − sin α \\ sin α & cos α \end{matrix} ] .

The determinant of this matrix is (cos α)^{2} + (sin α)^{2} = 1.

We can try to find the eigenvalues of this matrix. Geometrically, it is clear that unless α is a multiple of π, we do not have eigenvectors. We compute the characteristic polynomial of this matrix:

f_{φ_{α}}(x) = det(xI − [φ_{α}]\underline{e})
= | \begin{matrix}x − cos α & sin α \\ − sin α & x − cos α \end{matrix} |
= x^{2} − (2 cos α)x + 1.

Over the complex numbers, we have two solutions to this equation: λ = cos α±i sin α. They are the eigenvalues of the matrix [φ_{α}]\underline{e} over ℂ, and we see that we indeed have no real eigenvalues unless sin α = 0, i.e. α is a multiple of π.

Now we carry out this computation all over again. This time we choose a different basis for ℝ^{2}. Let \underline{e}′ = \{e_{1}, e_{3}\}, where e_{1} is the same as before, and e_{3} is φ_{α}e_{1}. Assuming α is not a multiple of π, we have formed a basis. We must compute w = φ_{α}e_{3}. Using geometry, we see that e_{1} + w = γe_{3}, where γ = 2 cos α. This shows w = (2 cos α)e_{3} − e_{1}, and we get

[φ_{α}]_{\underline{e}}′ = [ \begin{matrix}0 & −1 \\ 1 & 2 cos α \end{matrix} ] .

The characteristic polynomial of this matrix is

f_{[φ_{α}]_{\underline{e}′}} = x^{2} − (2 cos α)x + 1.

This is the exact same polynomial we got previously, using the standard basis.

This example suggests that the characteristic polynomial is invariant under basis change. This is indeed the case, and we will prove the fact later. We formulate this fact in the following theorem.

Theorem 4.27. If φ : V → V is a linear transformation, then f_{[ϕ]_{B}}(x) does not depend on the choice of the basis B for V.

This theorem leads to the following definition:

Definition 4.28. The characteristic polynomial of the linear transformation φ : V → V is

f_{φ}(x) = f_{[ϕ]_{B}}(x),

where B is any basis of V.

The next exercise ensures us the representation of linear maps using matrices is consistent with the definition of the matrix multiplications.

Exercise 4.29. Suppose φ : V → W is a linear map, and we fix bases \underline{e} and \underline{f} for V and W, respectively. Prove that

[φx]\underline{f} = [φ]_{\underline{e},\underline{f}} [x]\underline{e}.

The multiplication on the right hand side is the usual matrix multiplication.

We next two exercises will show the definition of matrix multiplication is entirely natural.

Exercise 4.30. If A is a k × ℓ matrix, and Ax = 0 for all x ∈ 𝔽^{ℓ}, then A is the zero matrix.

An immediate corollary is the following:

Corollary 4.31. If Ax = Bx for all vectors x ∈ 𝔽^{ℓ}, then A = B.

Exercise 4.32. Suppose we have two maps φ : V → W, ψ : W → T. We choose bases \underline{e}, \underline{f}, \underline{g} for V, W, and T respectively. Prove that

[φψ]_{\underline{e},\underline{g}} = [ψ]_{\underline{f},\underline{g}}[φ]_{\underline{e},\underline{f}} .

(Hint: Use Corollary 4.31 and Exercise 4.29.)

We now see that the seemingly involved definition of matrix multiplication was constructed to satisfy the composition rules of linear maps. Since the composition of any maps is associative, we at once get the following result:

Corollary 4.33. Matrix multiplication is associative.

4.4 Change of Basis

Now that we can represent linear maps with matrices by choosing bases, we want to know the relations between matrix representations of the same linear map under different bases.

First we relate the coordinate vectors [x]\underline{e} and [x]_{\underline{e}}′, where \underline{e} = \{e_{1}, …, e_{ℓ}\} and \underline{e}′ = {e′_{1}, …, e′_{ℓ}} are two bases for V. We define a “basis change transformation” σ : V → V, given by

σ(e_{i}) = e′_{i}.

We know this map is unique and invertible (σ^{−1} : e′ ↦ e).

If x = ∑_{i=1}^{ℓ} α_{i}e_{i} then we have

σx = σ(∑_{i=1}^{ℓ} α_{i}e_{i}) = ∑_{i=1}^{ℓ} α_{i}σ(e_{i}) = ∑_{i=1}^{ℓ} α_{i}e′_{i}.

This shows [σ(x)]_{\underline{e}}′ = [x]\underline{e}, (as vectors of 𝔽^{ℓ}). By the relation [σ(x)]_{\underline{e}}′ = [σ]_{\underline{e}}′[x]_{\underline{e}}′, where [σ]_{\underline{e}}′ is the representation of σ as a matrix under the basis \underline{e}′, we get the following formula for basis change:

[x]_{\underline{e}}′ = [σ]_{\underline{e}′}^{−1}[x]\underline{e}.  (3)

Now suppose we have φ : V → W, a linear map. Suppose \underline{e} and \underline{e}′ are two bases for V, while \underline{f} and \underline{f}′ are two bases for W. Further suppose we have the basis change transformations, σ : V → V and τ : W → W, where σ(e_{i}) = e′_{i}, τ(f_{j}) = f′_{j}. Using the pairs of bases, \{\underline{e}, \underline{f}\} and \{\underline{e}′, \underline{f}′\}, we get two matrix representations for the map: [φ]_{\underline{e},\underline{f}} and [φ]_{\underline{e}′,\underline{f}′}. We will use the more suggestive notations [φ]_{old} for the former matrix, and [φ]_{new} for the latter. We will use the subscript “new” whenever we use the bases \underline{e}′ or \underline{f}′, and we will use “old” whenever we refer to the basis \underline{e}, \underline{f}. Using the formula we just derived, we get

[φx]_{new} = [φ]_{new}[x]_{new} = [φ]_{new}[σ]_{new}^{−1}[x]_{old};
[φx]_{new} = [τ]_{new}^{−1}[φx]_{old} = [τ]_{new}^{−1}[φ]_{old}[x]_{old}.

This implies the following equality:

[τ]_{new}^{−1}[φ]_{old}[x]_{old} = [φ]_{new}[σ]_{new}^{−1}[x]_{old}.

Since this holds for all vectors x, by Corollary 4.31, we get

[τ]_{new}^{−1}[φ]_{old} = [φ]_{new}[σ]_{new}^{−1}.

By multiplying both sides with [σ]_{new}, we get

[φ]_{new} = [τ]_{new}^{−1}[φ]_{old}[σ]_{new}.  (4)

Since σ itself is a linear map (from V to itself), we can apply this formula and conclude

[σ]_{new} = [σ]_{new}^{−1}[σ]_{old}[σ]_{new}.

The basis change matrix is invertible as the corresponding linear map has an inverse, so we can cancel the [σ]_{new} factor and derive [σ]_{new}^{−1}[σ]_{old} = I. qWe have shown

Corollary 4.34. The basis change matrices are the same in either basis; i.e. we have [σ]_{new} = [σ]_{old}.

We denote the matrix in the corollary by S. Similarly, we define T := [τ]_{new} = [τ]_{old}.

Now equation (4) has the form

[φ]_{new} = T^{−1}[φ]_{old}S.

This is the sought-after basis change formula for linear maps.

As a special case, we have:

Corollary 4.35. If we have φ : V → V a linear transformation, then [φ]_{new} = S^{−1}[φ]_{old}S.

This motivates the following definition:

Definition 4.36. Suppose A, B ∈ M_{n}(𝔽). We say A and B are similar (written A ∼ B) if there is an invertible matrix S s.t. B = S^{−1}AS.

The preceding discussions show

Theorem 4.37. The matrices associated with a linear transformation in different bases are similar.

Examples 4.38. As in example (4.26), the following two matrices are similar, because they represent the same linear transformation:

[ \begin{matrix}cos α & − sin α \\ sin α & cos α \end{matrix} ] ∼ [ \begin{matrix}0 & −1 \\ 1 & 2 cos α \end{matrix} ] .

Now we see that Theorem (4.27) is equivalent to the following statement: Theorem 4.39. Similar matrices have the same characteristic polynomial. Exercise 4.40. Prove this theorem.

We are often interested in deciding whether or not a given matrix is similar to a diagonal matrix. Exercise 4.41. Prove that [ \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ] is not similar to any diagonal matrix. (What type of linear transformation does this matrix describe? We have given it a name.) Exercise 4.42. (a) If A ∈ M_{n}(𝔽), and f_{A}(x) = (x − λ_{1}) ⋯ (x − λ_{n}) and the λ_{i} are all distinct then A ∼ diag(λ_{1}, …, λ_{n}). (b) Prove that this conclusion will fail if we omit that assumption of distinctness of the λ_{i}.

This leads to the following important definition: Definition 4.43. A matrix diagonalizable if it is similar to a diagonal matrix. Exercise 4.44. Prove: the matrix of a linear transformation φ : V → V (with respect to any basis) is diagonalizable if and only if φ has an eigenbasis.

Not every matrix is diagonalizable, as exercise (4.41) shows. We have the following useful sufficient condition, which follows from exercise (4.42): Exercise 4.45. If A ∈ M_{n}(𝔽), and A has n distinct eigenvalues, then A is diagonalizable.

Consider the triangular matrix A := [ \begin{matrix}a_{11} & a_{12} & … & a_{1n} \\ & a_{22} & ⋯ & a_{2n} \\ & & ... & ⋮ \\ & & & a_{nn} \end{matrix} ]. Its characteristic polynomial

is f_{A}(x) = (x − a_{11}) ⋯ (x − a_{nn}). Thus we now know Theorem 4.46. The eigenvalues of a triangular matrix are the diagonal entries.

We have two ways of accounting for multiple eigenvalues. Definition 4.47. The algebraic multiplicity of an eigenvalue λ is k if (x − λ)^{k} | f_{A}(x), and (x − λ)^{k+1} ∤ f_{A}(x). Definition 4.48. The geometric multiplicity of an eigenvalue λ is the number of linearly independent eigenvectors for eigenvalue λ. Examples 4.49. The central reflection in ℝ^{3} has one eigenvalue −1, with geometric multiplicity 3.

Exercise 4.50. Prove that the geometric multiplicity of λ is equal to dim(U_{λ}) where U_{λ} := ker(λI − A). We call U_{λ} the eigensubspace corresponding to λ; it consist of 0 and the eigenvectors for λ. Exercise 4.51. Prove the the geometric multiplicity of λ is ≤ its algebraic multiplicity.

The next exercise characterizes diagonalizable matrices. Note that the splitting condition is always satisfied if 𝔽 = ℂ. Exercise 4.52. If f_{A}(x) splits into linear factor over 𝔽, then the following are equivalent:

(i) A is diagonalizable; (ii) for all λ, the algebraic multiplicity of λ is equal to its geometric multiplicity.

This last series of exercises will let us prove the Cayley-Hamilton Theorem. Theorem 4.53 (Cayley-Hamilton). If A ∈ M_{n}(𝔽), then f_{A}(A) = 0.

We will prove the statement for matrices over ℂ. In particular, it holds for matrices with integer coefficients. It will then follow that the statements holds for matrices over any field. Exercise 4.54. (i) Prove: if matrices A and B are similar and the Theorem holds for A

then it holds for B. (ii) Prove the Theorem for diagonal matrices. (iii) Prove it for diagonalizable matrices. (iv) Prove that if lim_{k→∞} A_{k} = A, and the Theorem holds for all A_{k} then it also holds for A.

(v) Prove that every triangular matrix is the limit of a sequence of diagonalizable matrices. (Hint: distinct eigenvalues.)

(vi) Prove the Theorem for triangular matrices. (vii) Finally, prove that every matrix is similar to a triangular matrix.