##### Document Text Contents

Page 2

Linear Algebra and Its Applications

Fourth Edition

Gilbert Strang

y

x y z

z

Ax b

b

0

Ay b

0Az

0

Page 272

262 Chapter 5 Eigenvalues and Eigenvectors

Now we have the fundamental equation of this chapter. It involves two unknowns

λ and x. It is an algebra problem, and differential equations can be forgotten! The

number λ (lambda) is an eigenvalue of the matrix A, and the vector x is the associated

eigenvector. Our goal is to find the eigenvalues and eigenvectors, λ ’s and x’s, and to use

them.

The Solution of Ax = λx

Notice that Ax = λx is a nonlinear equation; λ multiplies x. If we could discover λ , then

the equation for x would be linear. In fact we could write λ Ix in place of λx, and bring

this term over to the left side:

(A−λ I)x = 0. (9)

The identity matrix keeps matrices and vectors straight; the equation (A− λ )x = 0 is

shorter, but mixed up. This is the key to the problem:

The vector x is in the nullspace of A−λ I.

The number λ is chosen so that A−λ I has a nullspace.

Of course every matrix has a nullspace. It was ridiculous to suggest otherwise, but you

see the point. We want a nonzero eigenvector x, The vector x = 0 always satisfies

Ax = λx, but it is useless in solving differential equations. The goal is to build u(t) out

of exponentials eλ tx, and we are interested only in those particular values λ for which

there is a nonzero eigenvector x. To be of any use, the nullspace of A−λ I must contain

vectors other than zero. In short, A−λ I must be singular.

For this, the determinant gives a conclusive test.

5A The number λ is an eigenvalue of A if and only if A−λ I is singular:

det(A−λ I) = 0. (10)

This is the characteristic equation. Each λ is associated with eigenvectors x:

(A−λ I)x = 0 or Ax = λx. (11)

In our example, we shift A by λ I to make it singular:

Subtract λ I A−λ I =

[

4−λ −5

2 −3−λ

]

.

Note that λ is subtracted only from the main diagonal (because it multiplies I).

Determinant |A−λ I|= (4−λ )(−3−λ )+10 or λ 2−λ −2.

This is the characteristic polynomial. Its roots, where the determinant is zero, are the

eigenvalues. They come from the general formula for the roots of a quadratic, or from

Page 273

5.1 Introduction 263

factoring into λ 2− λ − 2 = (λ + 1)(λ − 2). That is zero if λ = −1 or λ = 2, as the

general formula confirms:

Eigenvalues λ =

−b±

√

b2−4ac

2a

=

1±

√

9

2

=−1 and 2.

There are two eigenvalues, because a quadratic has two roots. Every 2 by 2 matrix

A−λ I has λ 2 (and no higher power of λ ) in its determinant.

The values λ =−1 and λ = 2 lead to a solution of Ax = λx or (A−λ I)x = 0. A matrix

with zero determinant is singular, so there must be nonzero vectors x in its nullspace. In

fact the nullspace contains a whole line of eigenvectors; it is a subspace!

λ1 =−1 : (A−λ1I)x =

[

5 −5

2 −2

][

y

z

]

=

[

0

0

]

.

The solution (the first eigenvector) is any nonzero multiple of x1:

Eigenvector for λ1 x1 =

[

1

1

]

.

The computation for λ2 is done separately:

λ2 = 2 : (A−λ2I)x =

[

2 −5

2 −5

][

y

z

]

=

[

0

0

]

.

The second eigenvector is any nonzero multiple of x2:

Eigenvector for λ2 x2 =

[

5

2

]

.

You might notice that the columns of A−λ1I give x2, and the columns of A−λ2I are

multiples of x1. This is special (and useful) for 2 by 2 matrices.

In the 3 by 3 case, I often set a component of x equal to 1 and solve (A−λ I)x = 0 for

the other components. Of course if x is an eigenvector then so is 7x and so is −x. All

vectors in the nullspace of A−λ I (which we call the eigenspace) will satisfy Ax = λx.

In our example the eigenspaces are the lines through x1 = (1,1) and x2 = (5,2).

Before going back to the application (the differential equation), we emphasize the

steps in solving Ax = λx:

1. Compute the determinant of A− λ I. With λ subtracted along the diagonal, this

determinant is a polynomial of degree n. It starts with (−λ )n.

2. Find the roots of this polynomial. The n roots are the eigenvalues of A.

3. For each eigenvalue solve the equation (A−λ I)x = 0. Since the determinant is

zero, there are solutions other than x = 0. Those are the eigenvectors.

Page 543

Appendix E MATLAB Teaching Codes 485

plot2d Two-dimensional plot for the house figures.

plu Rectangular PA = LU factorization with row exchanges.

poly2str Express a polynomial as a string.

project Project a vector b onto the column space of A.

projmat Construct the projection matrix onto the column space of A.

randperm Construct a random permutation.

rowbasis Compute a basis for the row space from the pivot rows of R.

samespan Test whether two matrices have the same column space.

signperm Determinant of the permutation matrix with rows ordered by p.

slu LU factorization of a square matrix using no row exchanges.

slv Apply slu to solve the system Ax = b allowing no row exchanges.

splu Square PA = LU factorization with row exchanges.

splv The solution to a square, invertible system Ax = b.

symmeig Compute the eigenvalues and eigenvectors of a symmetric matrix.

tridiag Construct a tridiagonal matrix with constant diagonals a, b, c.

These Teaching Codes are directly available from the Linear Algebra Home Page:

http://web.mit.edu/18.06/www.

They were written in MATLAB , and translated into Maple and Mathematica.

Page 544

Appendix F

Linear Algebra in a Nutshell

(A is n by n)

Nonsingular Singular

A is invertible. A is not invertible.

The columns are independent. The columns are dependent.

The rows are independent. The rows are dependent.

The determinant is not zero. The determinant is zero.

Ax = 0 has one solution x = 0. Ax = 0 has infinitely many solutions.

Ax = b has one solution x = A−1b. Ax = b has no solution or infinitely many.

A has n (nonzero) pivots. A has r < n pivots.

A has full rank r = n. A has rank r < n.

The reduced row echelon form is R = I. R has at least one zero row.

The column space is all of Rn. The column space has dimension r < n.

The row space is all of Rn. The row space has dimension r < n.

All eigenvalues are nonzero. Zero is an eigenvalue of A.

ATA is symmetric positive definite. ATA is only semidefinite.

A has n (positive) singular values. A has r < n singular values.

Each line of the singular column can be made quantitative using r.

Linear Algebra and Its Applications

Fourth Edition

Gilbert Strang

y

x y z

z

Ax b

b

0

Ay b

0Az

0

Page 272

262 Chapter 5 Eigenvalues and Eigenvectors

Now we have the fundamental equation of this chapter. It involves two unknowns

λ and x. It is an algebra problem, and differential equations can be forgotten! The

number λ (lambda) is an eigenvalue of the matrix A, and the vector x is the associated

eigenvector. Our goal is to find the eigenvalues and eigenvectors, λ ’s and x’s, and to use

them.

The Solution of Ax = λx

Notice that Ax = λx is a nonlinear equation; λ multiplies x. If we could discover λ , then

the equation for x would be linear. In fact we could write λ Ix in place of λx, and bring

this term over to the left side:

(A−λ I)x = 0. (9)

The identity matrix keeps matrices and vectors straight; the equation (A− λ )x = 0 is

shorter, but mixed up. This is the key to the problem:

The vector x is in the nullspace of A−λ I.

The number λ is chosen so that A−λ I has a nullspace.

Of course every matrix has a nullspace. It was ridiculous to suggest otherwise, but you

see the point. We want a nonzero eigenvector x, The vector x = 0 always satisfies

Ax = λx, but it is useless in solving differential equations. The goal is to build u(t) out

of exponentials eλ tx, and we are interested only in those particular values λ for which

there is a nonzero eigenvector x. To be of any use, the nullspace of A−λ I must contain

vectors other than zero. In short, A−λ I must be singular.

For this, the determinant gives a conclusive test.

5A The number λ is an eigenvalue of A if and only if A−λ I is singular:

det(A−λ I) = 0. (10)

This is the characteristic equation. Each λ is associated with eigenvectors x:

(A−λ I)x = 0 or Ax = λx. (11)

In our example, we shift A by λ I to make it singular:

Subtract λ I A−λ I =

[

4−λ −5

2 −3−λ

]

.

Note that λ is subtracted only from the main diagonal (because it multiplies I).

Determinant |A−λ I|= (4−λ )(−3−λ )+10 or λ 2−λ −2.

This is the characteristic polynomial. Its roots, where the determinant is zero, are the

eigenvalues. They come from the general formula for the roots of a quadratic, or from

Page 273

5.1 Introduction 263

factoring into λ 2− λ − 2 = (λ + 1)(λ − 2). That is zero if λ = −1 or λ = 2, as the

general formula confirms:

Eigenvalues λ =

−b±

√

b2−4ac

2a

=

1±

√

9

2

=−1 and 2.

There are two eigenvalues, because a quadratic has two roots. Every 2 by 2 matrix

A−λ I has λ 2 (and no higher power of λ ) in its determinant.

The values λ =−1 and λ = 2 lead to a solution of Ax = λx or (A−λ I)x = 0. A matrix

with zero determinant is singular, so there must be nonzero vectors x in its nullspace. In

fact the nullspace contains a whole line of eigenvectors; it is a subspace!

λ1 =−1 : (A−λ1I)x =

[

5 −5

2 −2

][

y

z

]

=

[

0

0

]

.

The solution (the first eigenvector) is any nonzero multiple of x1:

Eigenvector for λ1 x1 =

[

1

1

]

.

The computation for λ2 is done separately:

λ2 = 2 : (A−λ2I)x =

[

2 −5

2 −5

][

y

z

]

=

[

0

0

]

.

The second eigenvector is any nonzero multiple of x2:

Eigenvector for λ2 x2 =

[

5

2

]

.

You might notice that the columns of A−λ1I give x2, and the columns of A−λ2I are

multiples of x1. This is special (and useful) for 2 by 2 matrices.

In the 3 by 3 case, I often set a component of x equal to 1 and solve (A−λ I)x = 0 for

the other components. Of course if x is an eigenvector then so is 7x and so is −x. All

vectors in the nullspace of A−λ I (which we call the eigenspace) will satisfy Ax = λx.

In our example the eigenspaces are the lines through x1 = (1,1) and x2 = (5,2).

Before going back to the application (the differential equation), we emphasize the

steps in solving Ax = λx:

1. Compute the determinant of A− λ I. With λ subtracted along the diagonal, this

determinant is a polynomial of degree n. It starts with (−λ )n.

2. Find the roots of this polynomial. The n roots are the eigenvalues of A.

3. For each eigenvalue solve the equation (A−λ I)x = 0. Since the determinant is

zero, there are solutions other than x = 0. Those are the eigenvectors.

Page 543

Appendix E MATLAB Teaching Codes 485

plot2d Two-dimensional plot for the house figures.

plu Rectangular PA = LU factorization with row exchanges.

poly2str Express a polynomial as a string.

project Project a vector b onto the column space of A.

projmat Construct the projection matrix onto the column space of A.

randperm Construct a random permutation.

rowbasis Compute a basis for the row space from the pivot rows of R.

samespan Test whether two matrices have the same column space.

signperm Determinant of the permutation matrix with rows ordered by p.

slu LU factorization of a square matrix using no row exchanges.

slv Apply slu to solve the system Ax = b allowing no row exchanges.

splu Square PA = LU factorization with row exchanges.

splv The solution to a square, invertible system Ax = b.

symmeig Compute the eigenvalues and eigenvectors of a symmetric matrix.

tridiag Construct a tridiagonal matrix with constant diagonals a, b, c.

These Teaching Codes are directly available from the Linear Algebra Home Page:

http://web.mit.edu/18.06/www.

They were written in MATLAB , and translated into Maple and Mathematica.

Page 544

Appendix F

Linear Algebra in a Nutshell

(A is n by n)

Nonsingular Singular

A is invertible. A is not invertible.

The columns are independent. The columns are dependent.

The rows are independent. The rows are dependent.

The determinant is not zero. The determinant is zero.

Ax = 0 has one solution x = 0. Ax = 0 has infinitely many solutions.

Ax = b has one solution x = A−1b. Ax = b has no solution or infinitely many.

A has n (nonzero) pivots. A has r < n pivots.

A has full rank r = n. A has rank r < n.

The reduced row echelon form is R = I. R has at least one zero row.

The column space is all of Rn. The column space has dimension r < n.

The row space is all of Rn. The row space has dimension r < n.

All eigenvalues are nonzero. Zero is an eigenvalue of A.

ATA is symmetric positive definite. ATA is only semidefinite.

A has n (positive) singular values. A has r < n singular values.

Each line of the singular column can be made quantitative using r.