Eigenvalues and Eigenvectors

Section 4.1 Eigenvalues and Eigenvectors

We jump right into the definition, which you have probably seen previously in your first course in linear algebra.

Definition 4.1.1.

Let

A

be an

n \times n

matrix. A number

λ

is called an eigenvalue of

A

if there exists a nonzero vector

x

such that

A x = λ x .

🔗

Any such vector

x

is called an eigenvector associated to the eigenvalue

λ .

🔗

Remark 4.1.2.

🔗

You might reasonably wonder: where does this definition come from? And why should I care? We are assuming that you saw at least a basic introduction to eigenvalues in your first course on linear algebra, but that course probably focused on mechanics. Possibly you learned that diagonalizing a matrix lets you compute powers of that matrix.

🔗

But why should we be interested in computing powers (in particular, large powers) of a matrix? An important context comes from the study of discrete linear dynamical systems ¹, as well as Markov chains ², where the evolution of a state is modelled by repeated multiplication of a vector by a matrix.

🔗

When we’re able to diagonalize our matrix using eigenvalues and eigenvectors, not only does it become easy to compute powers of a matrix, it also enables us to see that the entire process is just a linear combination of geometric sequences! If you have completed Worksheet 2.5, you probably will not be surprised to learn that the polynomial roots you found are, in fact, eigenvalues of a suitable matrix.

🔗

Remark 4.1.3.

🔗

Eigenvalues and eigenvectors can just as easily be defined for a general linear operator

T : V \to V .

In this context, an eigenvector

x

is sometimes referred to as a characteristic vector (or characteristic direction) for

T,

since the property

T (x) = λ x

simply states that the transformed vector

T (x)

is parallel to the original vector

x .

Some linear algebra textbooks that focus more on general linear transformations frame this topic in the context of invariant subspaces for a linear operator.

🔗

A subspace

U \subseteq V

is invariant with respect to

T

T (u) \in U

for all

u \in U .

Note that if

x

is an eigenvector of

T,

then

span {x}

is an invariant subspace. To see this, note that if

T (x) = λ x

and

y = k x,

then

T (y) = T (k x) = k T (x) = k (λ x) = λ (k x) = λ y .

🔗

Exercise 4.1.4.

🔗

For the matrix

A = [\begin{matrix} - 1 & 0 & 3 \\ 1 & - 1 & 0 \\ 1 & 0 & 1 \end{matrix}],

match each vector on the left with the corresponding eigenvalue on the right. (For typographical reasons, column vectors have been transposed.)

${[\begin{matrix} - 3 & 3 & 1 \end{matrix}]}^{T}$
$- 2$
${[\begin{matrix} 0 & 1 & 0 \end{matrix}]}^{T}$
$- 1$
${[\begin{matrix} 3 & 1 & 3 \end{matrix}]}^{T}$
$2$
${[\begin{matrix} 1 & 1 & 1 \end{matrix}]}^{T}$
Not an eigenvector

Hint.

Use Definition 4.1.1.

🔗

Note that if

x

is an eigenvector of the matrix

A,

then we have

\begin{matrix} (4.1.1) & (A - λ I_{n}) x = 0, \end{matrix}

🔗

where

I_{n}

denotes the

n \times n

identity matrix. Thus, if

λ

is an eigenvalue of

A,

any corresponding eigenvector is an element of

null (A - λ I_{n}) .

🔗

Definition 4.1.5.

🔗

For any real number

λ

and

n \times n

matrix

A,

we define the eigenspace

E_{λ} (A)

E_{λ} (A) = null (A - λ I_{n}) .

🔗

Since we know that the null space of any matrix is a subspace, it follows that eigenspaces are subspaces of

R^{n} .

🔗

Note that

E_{λ} (A)

can be defined for any real number

λ,

whether or not

λ

is an eigenvalue. However, the eigenvalues of

A

are distinguished by the property that there is a nonzero solution to (4.1.1). Furthermore, we know that (4.1.1) can only have nontrivial solutions if the matrix

A - λ I_{n}

is not invertible. We also know that

A - λ I_{n}

is non-invertible if and only if

det (A - λ I_{n}) = 0 .

This gives us the following theorem.

🔗

Theorem 4.1.6.

🔗

The following are equivalent for any

n \times n

matrix

A

and real number

λ :

$λ$ is an eigenvalue of $A .$
$E_{λ} (A) \neq {0}$
$det (A - λ I_{n}) = 0$

Strategy.

To prove a theorem involving a “the following are equivalent” statement, a good strategy is to show that the first implies the second, the second implies the third, and the third implies the first. The ideas needed for the proof are given in the paragraph preceding the theorem. See if you can turn them into a formal proof.

🔗

The polynomial

c_{A} (x) = det (x I_{n} - A)

is called the characteristic polynomial of

A .

(Note that

det (x I_{n} - A) = (- 1)^{n} det (A - x I_{n}) .

We choose this order so that the coefficient of

x^{n}

is always 1.) The equation

\begin{matrix} (4.1.2) & det (x I_{n} - A) = 0 \end{matrix}

🔗

is called the characteristic equation of

A .

The solutions to this equation are precisely the eigenvalues of

A .

🔗

Remark 4.1.7.

🔗

A careful study of eigenvalues and eigenvectors relies heavily on polynomials. An interesting fact is that we can plug any square matrix into a polynomial! Given the polynomial

p (x) = a_{0} + a_{1} x + a_{2} x^{2} + \dots + a_{n} x^{n}

and an

n \times n

matrix

A,

we define

p (A) = a_{0} I_{n} + a_{1} A + a_{2} A^{2} + \dots + a_{n} A^{n} .

🔗

Note the use of the identity matrix in the first term, since it doesn’t make sense to add a scalar to a matrix.

🔗

One interesting aspect of this is the relationship between the eigenvalues of

A

and the eigenvalues of

p (A) .

For example, if

A

has the eigenvalue

λ,

see if you can prove that

A^{k}

has the eigenvalue

λ^{k} .

🔗

Exercise 4.1.8.

🔗

In order for certain properties of a matrix

A

to be satisfied, the eigenvalues of

A

need to have particular values. Match each property of a matrix

A

on the left with the corresponding information about the eigenvalues of

A

on the right. Be sure that you can justify your answers with a suitable proof.

$A$ is invertible
$0$ is not an eigenvalue of $A$
$A^{k} = 0$ for some integar $k \geq 2$
$0$ is the only eigenvalue of $A$
$A = A^{- 1}$
$1$ and $- 1$ are the only eigenvalues of $A$
$A^{2} = A$
$0$ and $1$ are the only eigenvalues of $A$
$A^{3} = A$
$0,$ $1,$ and $- 1$ are the eigenvalues of $A$

🔗

Recall that a matrix

B

is said to be similar to a matrix

A

if there exists an invertible matrix

P

such that

B = P^{- 1} A P .

Much of what follows concerns the question of whether or not a given

n \times n

matrix

A

is diagonalizable.

🔗

Definition 4.1.9.

🔗

n \times n

matrix

A

is said to be diagonalizable if

A

is similar to a diagonal matrix.

🔗

The following results will frequently be useful.

🔗

Theorem 4.1.10.

🔗

The relation

A \sim B

if and only if

A

is similar to

B

is an equivalence relation. Moreover, if

A \sim B,

then:

$det A = det B$
$tr A = tr B$
$c_{A} (x) = c_{B} (x)$

🔗

In other words,

A

and

B

have the same determinant, trace, and characteristic polynomial (and thus, the same eigenvalues).

Proof.

The first two follow directly from properties of the determinant and trace. For the last, note that if

B = P^{- 1} A P,

then

P^{- 1} (x I_{n} - A) P = P^{- 1} (x I_{n}) P - P^{- 1} A P = x I_{n} - B,

x I_{n} - B \sim x I_{n} - A,

and therefore

det (x I_{n} - B) = det (x I_{n} - A) .

🔗

Example 4.1.11.

🔗

Determine the eigenvalues and eigenvectors of

A = [\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}] .

Solution.

We begin with the characteristic polynomial. We have

\begin{aligned} det (x I_{n} - A) & = det [\begin{array}{c} x & - 1 & - 1 \\ - 1 & x & - 1 \\ - 1 & - 1 & x \end{array}] \\ = x | \begin{array}{c} x & - 1 \\ - 1 & x \end{array} | + 1 | \begin{array}{c} - 1 & - 1 \\ - 1 & x \end{array} | - 1 | \begin{array}{c} - 1 & x \\ - 1 & - 1 \end{array} | \\ = x (x^{2} - 1) + (- x - 1) - (1 + x) \\ x (x - 1) (x + 1) - 2 (x + 1) \\ (x + 1) [x^{2} - x - 2] \\ (x + 1)^{2} (x - 2) . \end{aligned}

The roots of the characteristic polynomial are our eigenvalues, so we have

λ_{1} = - 1

and

λ_{2} = 2 .

Note that the first eigenvalue comes from a repeated root. This is typically where things get interesting. If an eigenvalue does not come from a repeated root, then there will only be one (independent) eigenvector that corresponds to it. (That is,

\dim E_{λ} (A) = 1 .

) If an eigenvalue is repeated, it could have more than one eigenvector, but this is not guaranteed.

We find that

A - (- 1) I_{n} = [\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}],

which has reduced row-echelon form

[\begin{matrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] .

Solving for the nullspace, we find that there are two independent eigenvectors:

x_{1, 1} = [\begin{matrix} 1 \\ - 1 \\ 0 \end{matrix}], and x_{1, 2} = [\begin{matrix} 1 \\ 0 \\ - 1 \end{matrix}],

E_{- 1} (A) = span {[\begin{matrix} 1 \\ - 1 \\ 0 \end{matrix}], [\begin{matrix} 1 \\ 0 \\ - 1 \end{matrix}]} .

For the second eigenvector, we have

A - 2 I = [\begin{matrix} - 2 & 1 & 1 \\ 1 & - 2 & 1 \\ 1 & 1 & - 2 \end{matrix}],

which has reduced row-echelon form

[\begin{matrix} 1 & 0 & - 1 \\ 0 & 1 & - 1 \\ 0 & 0 & 0 \end{matrix}] .

An eigenvector in this case is given by

x_{2} = [\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}] .

🔗

In general, if the characteristic polynomial can be factored as

c_{A} (x) = (x - λ)^{m} q (x),

🔗

where

q (x)

is not divisible by

x - λ,

then we say that

λ

is an eigenvalue of multiplicity

m .

In the example above,

λ_{1} = - 1

has multiplicty 2, and

λ_{2} = 2

has multiplicty 1.

🔗

The eigenvects command in SymPy takes a square matrix as input, and outputs a list of lists (one list for each eigenvalue). For a given eigenvalue, the corresponding list has the form (eigenvalue, multiplicity, eigenvectors). Using SymPy to solve Example 4.1.11 looks as follows:


    
        
xxxxxxxxxx
 
1
from sympy import Matrix, init_printing
2
init_printing()
3
A = Matrix([[0,1,1],[1,0,1],1,1,0])
4
A.eigenvects()

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

An important result about multiplicity is the following.

🔗

Theorem 4.1.12.

🔗

Let

λ

be an eigenvalue of

A

of multiplicity

m .

Then

\dim E_{λ} (A) \leq m .

🔗

To prove Theorem 4.1.12 we need the following lemma, which we’ve borrowed from Section 5.5 of Nicholson’s textbook.

🔗

Lemma 4.1.13.

🔗

Let

{x_{1}, \dots, x_{k}}

be a set of linearly independent eigenvectors of a matrix

A,

with corresponding eigenvalues

λ_{1}, \dots, λ_{k}

(not necessarily distinct). Extend this set to a basis

{x_{1}, \dots, x_{k}, x_{k + 1}, \dots, x_{n}},

and let

P = [\begin{matrix} x_{1} & \dots & x_{n} \end{matrix}]

be the matrix whose columns are the basis vectors. (Note that

P

is necessarily invertible.) Then

P^{- 1} A P = [\begin{matrix} diag (λ_{1}, \dots, λ_{k}) & B \\ 0 & A_{1} \end{matrix}],

🔗

where

B

has size

k \times (n - k),

and

A_{1}

has size

(n - k) \times (n - k) .

Proof.

We have

\begin{aligned} P^{- 1} A P & = P^{- 1} A [\begin{array}{c} x_{1} & \dots & x_{n} \end{array}] \\ = [\begin{array}{c} (P^{- 1} A) x_{1} & \dots & (P^{- 1} A) x_{n} \end{array}] . \end{aligned}

For

1 \leq i \leq k,

we have

(P^{- 1} A) (x_{i}) = P^{- 1} (A x_{i}) = P^{- 1} (λ_{i} x_{i}) = λ_{i} (P^{- 1} x_{i}) .

But

P^{- 1} x_{i}

is the

i

th column of

P^{- 1} P = I_{n},

which proves the result.

🔗

We can use Lemma 4.1.13 to prove that

\dim E_{λ} (A) \leq m

as follows. Suppose

{x_{1}, \dots, x_{k}}

is a basis for

E_{λ} (A) .

Then this is a linearly independent set of eigenvectors, so our lemma guarantees the existence of a matrix

P

such that

P^{- 1} A P = [\begin{matrix} λ I_{k} & B \\ 0 & A_{1} \end{matrix}] .

🔗

Let

\tilde{A} = P^{- 1} A P .

On the one hand, since

\tilde{A} \sim A,

we have

c_{A} (x) = p_{\tilde{A}} (x) .

On the other hand,

det (x I_{n} - \tilde{A}) = det [\begin{matrix} (x - λ) I_{k} & - B \\ 0 & x I_{n - k} - A_{1} \end{matrix}] = (x - λ)^{k} det (x I_{n - k} - A_{1}) .

🔗

This shows that

c_{A} (x)

is divisible by

(x - λ)^{k} .

Since

m

is the largest integer such that

c_{A} (x)

is divisible by

(x - λ)^{m},

we must have

\dim E_{λ} (A) = k \leq m .

🔗

Another important result is the following. The proof is a bit tricky: it requires mathematical induction, and a couple of clever observations.

🔗

Theorem 4.1.14.

🔗

Let

v_{1}, \dots, v_{k}

be eigenvectors corresponding to distinct eigenvalues

λ_{1}, \dots, λ_{k}

of a matrix

A .

Then

{v_{1}, \dots, v_{k}}

is linearly independent.

Proof.

The proof is by induction on the number

k

of distinct eigenvalues. Since eigenvectors are nonzero, any set consisting of a single eigenvector

v_{1}

is independent. Suppose, then, that a set of eigenvectors corresponding to

k - 1

distinct eigenvalues is independent, and let

v_{1}, \dots, v_{k}

be eigenvectors corresponding to distinct eigenvalues

λ_{1}, \dots, λ_{k} .

Consider the equation

c_{1} v_{1} + c_{2} v_{2} + \dots + c_{k} v_{k} = 0,

for scalars

c_{1}, \dots, c_{k} .

Multiplying both sides by the matrix

A,

we have

\begin{aligned} (4.1.3) & A (c_{1} v_{1} + c_{2} v_{2} + \dots + c_{k} v_{k}) & = A 0 \\ (4.1.4) & c_{1} A v_{1} + c_{2} A v_{2} + \dots + c_{k} A v_{k} & = 0 \\ (4.1.5) & c_{1} λ_{1} v_{1} + c_{2} λ_{2} v_{2} + \dots + c_{k} λ_{k} v_{k} & = 0 . \end{aligned}

On the other hand, we can also multiply both sides by the eigenvalue

λ_{1},

giving

\begin{matrix} (4.1.6) & 0 = c_{1} λ_{1} v_{1} + c_{2} λ_{1} v_{2} + \dots + c_{k} λ_{1} v_{k} . \end{matrix}

Subtracting (4.1.6) from (4.1.5), the first temrs cancel, and we get

c_{2} (λ_{2} - λ_{1}) v_{2} + \dots + c_{k} (λ_{k} - λ_{1}) v_{k} = 0 .

By hypothesis, the set

{v_{2}, \dots, v_{k}}

k - 1

eigenvectors is linearly independent. We know that

λ_{j} - λ_{1} \neq 0

for

j = 2, \dots, k,

since the eigenvalues are all distinct. Therefore, the only way this linear combination can equal zero is if

c_{2} = 0, \dots, c_{k} = 0 .

This leaves us with

c_{1} v_{1} = 0,

but

z_{1} \neq 0,

c_{1} = 0

as well.

🔗

Theorem 4.1.14 tells us that vectors from different eigenspaces are independent. In particular, a union of bases from each eigenspace will be an independent set. Therefore, Theorem 4.1.12 provides an initial criterion for diagonalization: if the dimension of each eigenspace

E_{λ} (A)

is equal to the multiplicity of

λ,

then

A

is diagonalizable.

🔗

Our focus in the next section will be on diagonalization of symmetric matrices, and soon we will see that for such matrices, eigenvectors corresponding to different eigenvalues are not just independent, but orthogonal.

🔗