WIXLIB

Preface xiVisualization and geometrical interpretation are emphasized extensivelythroughout.The reader will find an abundance of thought-provoking (and occasionallydelightful) problems and exercises.Abstract concepts are introduced gradually throughout the text. The majorideas are carefully developed at various levels of generality before the studentis introduced to abstract vector spaces.Discrete and continuous dynamical systems are used as a motivation foreigenvectors, and as a unifying theme thereafter.New Features in the Fifth EditionStudents and instructors generally found the fourth edition to be accurate and wellstructured. While preserving the overall organization and character of the text, somechanges seemed in order: A large number of exercises have been added to the problem sets, from theelementary to the challenging and from the abstract to the applied. For example, there are quite a few new exercises on “Fibonacci matrices” and theireigenvectors and eigenvalues.Throughout the text, we have added an ongoing discussion of the mathematical principles behind search engines and the notion of PageRank in particular,with dozens of examples and exercises. Besides being an interesting and important contemporary application of linear algebra, this topic allows for anearly and meaningful introduction to dynamical systems, one of the mainthemes of this text, naturally leading up to a discussion of diagonalizationand eigenvectors.In a new appendix, we offer a brief discussion of the proof techniques ofinduction and contraposition.There have been hundreds of small editorial improvements – offering a hintin a challenging problem for example, or choosing a more sensible notationin a definition.Outline of the TextChapter 1 This chapter provides a careful introduction to the solution of systemsof linear equations by Gauss–Jordan elimination. Once the concrete problem issolved, we restate it in terms of matrix formalism and discuss the geometric properties of the solutions.Chapter 2 Here we raise the abstraction a notch and reinterpret matrices as linear transformations. The reader is introduced to the modern notion of a function, as an arbitrary association between an input and an output, which leads intoa discussion of inverses. The traditional method for finding the inverse of a matrixis explained: It fits in naturally as a sort of automated algorithm for Gauss–Jordanelimination.

xiiPrefaceChapters 1 to 3:Linear Algebra inChapter 4n5.1, 5.2, 5.3Linear Spaces(Vector Spaces)Orthogonality in6.1, 6.2nDeterminants5.55.4Chapter 86.3Inner ProductSpacesLeastSquaresSymmetricMatricesGeometry ofDeterminants7.1, 7.2, 7.3, 7.4Real EigenvaluesChapter 9Linear DifferentialEquations7.5, 7.6ComplexEigenvalues, StabilityWe define linear transformations primarily in terms of matrices, since that ishow they are used; the abstract concept of linearity is presented as an auxiliary notion. Rotations, reflections, and orthogonal projections in R2 are emphasized, bothas archetypal, easily visualized examples, and as preparation for future applications.Chapter 3 We introduce the central concepts of linear algebra: subspaces, imageand kernel, linear independence, bases, coordinates, and dimension, still firmlyfixed in Rn .Chapter 4 Generalizing the ideas of the preceding chapter and using an abundanceof examples, we introduce abstract vector spaces (which are called linear spaceshere, to prevent the confusion some students experience with the term “vector”).Chapter 5 This chapter includes some of the most basic applications of linearalgebra to geometry and statistics. We introduce orthonormal bases and the Gram–Schmidt process, along with the QR factorization. The calculation of correlationcoefficients is discussed, and the important technique of least-squares approximations is explained, in a number of different contexts.Chapter 6 Our discussion of determinants is algorithmic, based on the countingof patterns (a transparent way to deal with permutations). We derive the propertiesof the determinant from careful analysis of this procedure, tying it together withGauss–Jordan elimination. The goal is to prepare for the main application of determinants: the computation of characteristic polynomials.Chapter 7 This chapter introduces the central application of the latter halfof the text: linear dynamical systems. We begin with discrete systems and arenaturally led to seek eigenvectors, which characterize the long-term behavior of thesystem. Qualitative behavior is emphasized, particularly stability conditions. Complex eigenvalues are explained, without apology, and tied into earlier discussions oftwo-dimensional rotation matrices.

PrefacexiiiChapter 8 The ideas and methods of Chapter 7 are applied to geometry. We discuss the spectral theorem for symmetric matrices and its applications to quadraticforms, conic sections, and singular values.Chapter 9 Here we apply the methods developed for discrete dynamical systemsto continuous ones, that is, to systems of first-order linear differential equations.Again, the cases of real and complex eigenvalues are discussed.Solutions Manuals Student’s Solutions Manual, with carefully worked solutions to all oddnumbered problems in the text (ISBN 0-13-600927-1)Instructor’s Solutions Manual, with solutions to all the problems in the text(ISBN 0-13-600928-X)AcknowledgmentsI first thank my students and colleagues at Harvard University, Colby College, andKoç University (Istanbul) for the key role they have played in developing this textout of a series of rough lecture notes. The following colleagues, who have taughtthe course with me, have made invaluable contributions:Attila AşkarPersi DiaconisJordan EllenbergMatthew EmertonEdward FrenkelAlexandru GhitzaFernando GouvêaJan HollyVarga KalantarovDavid KazhdanOliver KnillLeo LivshitsBen MathesBarry MazurDavid MumfordDavid SteinsaltzShlomo SternbergJustin SukiennikRichard TaylorGeorge WelchRobert WintersI am grateful to those who have taught me algebra: Peter Gabriel, VolkerStrassen, and Bartel van der Waerden at the University of Zürich; John Tate atHarvard University; Maurice Auslander at Brandeis University; and many more.I owe special thanks to John Boller, William Calder, Devon Ducharme, RobertKaplan and Philip Prosapio for their thoughtful review of the manuscript.I wish to thank Sylvie Bessette, Dennis Kletzing, Laura Lawrie for the carefulpreparation of the manuscript and Paul Nguyen for his well-drawn figures.Special thanks go to Kyle Burke, who has been my assistant at Colby Collegefor three years, having taken linear algebra with me as a first-year student. Payingclose attention to the way his students understood or failed to understand the material, Kyle came up with new ways to explain many of the more troubling concepts(such as the kernel of a matrix or the notion of an isomorphism). Many of his ideashave found their way into this text. Kyle took the time to carefully review variousiterations of the manuscript, and his suggestions and contributions have made thisa much better text.I am grateful to those who have contributed to the book in many ways: MarilynBretscher, Menoo Cung, Srdjan Divac, Devon Ducharme, Robin Gottlieb, LukeHunsberger, George Mani, Bridget Neale, Alec van Oot, Akilesh Palanisamy, RitaPang, Esther Silberstein, Radhika de Silva, Jonathan Tannenhauser, Ken WadaShiozaki, Larry Wilson, and Jingjing Zhou.

xivPrefaceI have received valuable feedback from the book’s reviewers for the variouseditions:Hirotachi Abo, University of IdahoGlenn D. Appleby, Santa Clara UniversityLoren Argabright, Drexel UniversityStephen Bean, Cornell CollegeFrank Beatrous, University of PittsburghTracy Bibelnieks, University of MinnesotaPrzemyslaw Bogacki, Old Dominion UniversityJohn Chollet, Towson UniversityDavid Dorman, Middlebury CollegeJeff D. Farmer, University of Northern ColoradoMichael Goldberg, Johns Hopkins UniversityHerman Gollwitzer, Drexel UniversityFernando Gouvêa, Colby CollegeDavid G. Handron, Jr., Carnegie Mellon UniversityChristopher Heil, Georgia Institute of TechnologyWilly Hereman, Colorado School of MinesKonrad J. Heuvers, Michigan Technological UniversityCharles Holmes, Miami UniversityMatthew Hudelson, Washington State UniversityThomas Hunter, Swarthmore CollegeMichael Kallaher, Washington State UniversityRalph Kaufmann, Purdue UniversityYoungmi Kim, Jacksonville State UniversityDaniel King, Oberlin CollegeRichard Kubelka, San Jose State UniversityGennady Lyubeznik, University of MinnesotaMichael G. Neubauer, California State University–NorthridgePeter C. Patton, University of PennsylvaniaJack Perry, University of Southern MississippiV. Rao Potluri, Reed CollegeJeffrey M. Rabin, University of California, San DiegoDaniel B. Shapiro, Ohio State UniversityJody Sorensen, Augsburg CollegeDavid Steinsaltz, Technische Universität BerlinJustin Sukiennik, Colby CollegeJames A. Wilson, Iowa State UniversityGregory A. Wisloski, Indiana University of PennsylvaniaDarryl Yong, Harvey Mudd CollegeJay Zimmerman, Towson University

PrefacexvI’m grateful to Bill Hoffman, Beth Houston, and all the other kind andwonderful people at Pearson who have helped make this book the teaching toolI wished it to be. I thank Anandakrishnan Natarajan at Integra Software Services,Ltd. for meticulously typesetting the text.The development of this text has been supported by a grant from the Instructional Innovation Fund of Harvard College.I love to hear from the users of this text. Feel free to write to obretsch@colby.eduwith any comments or concerns.Otto Bretscher

This page intentionally left blank

Linear Algebra with Applications

This page intentionally left blank

C H A P T E R1Linear Equations1.1 Introduction to Linear SystemsTraditionally, algebra was the art of solving equations and systems of equations.), which means restorationThe word algebra comes from the Arabic al-jabr ((of broken parts).1 The term was first used in a mathematical sense by Mohammedal-Khowarizmi (c. 780–850), who worked at the House of Wisdom, an academyestablished by Caliph al-Ma’mun in Baghdad. Linear algebra, then, is the art ofsolving systems of linear equations.The need to solve systems of linear equations frequently arises in mathematics,statistics, physics, astronomy, engineering, computer science, and economics.Solving systems of linear equations is not conceptually difficult. For small systems, ad hoc methods certainly suffice. Larger systems, however, require more systematic methods. The approach generally used today was beautifully explained2,000 years ago in a Chinese text, the Nine Chapters on the Mathematical Art).2 Chapter 8 of that text, called Method of Rectan(Jiuzhang Suanshu,), contains the following problem:gular Arrays (Fang Cheng,The yield of one bundle of inferior rice, two bundles of medium-grade rice,and three bundles of superior rice is 39 dou of grain.3 The yield of onebundle of inferior rice, three bundles of medium-grade rice, and two bundlesof superior rice is 34 dou. The yield of three bundles of inferior rice, twobundles of medium-grade rice, and one bundle of superior rice is 26 dou.What is the yield of one bundle of each grade of rice?In this problem the unknown quantities are the yields of one bundle of inferior,one bundle of medium-grade, and one bundle of superior rice. Let us denote thesequantities by x, y, and z, respectively. The problem can then be represented by the1At one time, it was not unusual to see the sign Algebrista y Sangrador (bone setter and blood letter)at the entrance of a Spanish barber’s shop.2Shen Kangshen et al. (ed.), The Nine Chapters on the Mathematical Art, Companion andCommentary, Oxford University Press, 1999.3The dou is a measure of volume, corresponding to about 2 liters at that time.1

2CHAPTER 1Linear Equationsfollowing system of linear equations: x 2y 3z 39 x 3y 2z 34 . 3x 2y z 26 To solve for x, x x 3xy, and z, we need to transform this system from the form x 2y 3z 39 . . . y . . . . 3y 2z 34 into the form 2y z 26 z . . . In other words, we need to eliminate the terms that are off the diagonal, those circledin the following equations, and make the coefficients of the variables along thediagonal equal to 1:n 3zn 39x 2ynn 34x 3y 2zn 2yn z 26.3xWe can accomplish these goals step by step, one variable at a time. In the past,you may have simplified systems of equations by adding equations to one anotheror subtracting them. In this system, we can eliminate the variable x from the secondequation by subtracting the first equation from the second: x 2y 3z 39 x 2y 3z 39 x 3y 2z 34 1st equation y z 5 . 3x 2y z 26 3x 2y z 26 To eliminate the variable x from the third equation, we subtract the first equationfrom the third equation three times. We multiply the first equation by 3 to get3x 6y 9z 117(3 1st equation)and then subtract this result from the third equation: x 2y 3z 39 y z 5 3x 2y z 26 3 1st equation x 2y 3z 39 .y z 5 4y 8z 91 Similarly, we eliminate the variable y above and below the diagonal: x 2y 3z 39 2 2nd equation x 5z 49 y z 5 . y z 5 4y 8z 91 4 2nd equation 12z 111 Before we eliminate the variable z above the diagonal, we make the coefficient of zon the diagonal equal to 1, by dividing the last equation by 12: x 5z x 5z 49 49 y z 5 y z 5 . 12z 111 ( 12) z 9.25 Finally, we eliminate the variable z above the diagonal: x 5z 49 5 third equation y z 5 third equation z 9.25 x 2.75 y 4.25 . z 9.25 The yields of inferior, medium-grade, and superior rice are 2.75, 4.25, and 9.25 douper bundle, respectively.

1.1 Introduction to Linear Systems3By substituting these values, we can check that x 2.75, y 4.25, z 9.25is indeed the solution of the system:2.75 2 4.25 3 9.25 392.75 3 4.25 2 9.25 343 2.75 2 4.25 9.25 26.Happily, in linear algebra, you are almost always able to check your solutions.It will help you if you get into the habit of checking now.Geometric InterpretationHow can we interpret this result geometrically? Each of the three equations of thesystem defines a plane in x–y–z-space. The solution set of the system consists ofthose points (x, y, z) that lie in all three planes (i.e., the intersection of the threeplanes). Algebraically speaking, the solution set consists of those ordered triples ofnumbers (x, y, z) that satisfy all three equations simultaneously. Our computationsshow that the system has only one solution, (x, y, z) (2.75, 4.25, 9.25). Thismeans that the planes defined by the three equations intersect at the point (x, y, z) (2.75, 4.25, 9.25), as shown in Figure 1.point ofintersectionFigure 1 Three planes in space, intersecting at a point.While three different planes in space usually intersect at a point, they may havea line in common (see Figure 2a) or may not have a common intersection at all, asshown in Figure 2b. Therefore, a system of three equations with three unknownsmay have a unique solution, infinitely many solutions, or no solutions at all.Figure 2(a) Three planes having a line incommon.Figure 2(b) Three planes with no commonintersection.

4CHAPTER 1Linear EquationsA System with Infinitely Many SolutionsNext, let’s consider a system of linear equations that has infinitely many solutions: 2x 4y 6z 0 4x 5y 6z 3 . 7x 8y 9z 6 We can solve this system using the method of elimination as previously discussed. For simplicity, we label the equations with Roman numerals. 2x 4y 6z 0 x 2y 3z 0 2 4x 5y 6z 3 4x 5y 6z 3 4 (I) 7x 8y 9z 6 7x 8y 9z 6 7 (I) x 2y 3z 0 x 2y 3z 0 2 (II) 3y 6z 3 ( 3) y 2z 1 6y 12z 6 6y 12z 6 6 (II) x z 2 y 2z 1 x z 2 y 2z 1 0 0 After omitting the trivial equation 0 0, we are left with only two equationswith three unknowns. The solution set is the intersection of two nonparallel planesin space (i.e., a line). This system has infinitely many solutions.The two foregoing equations can be written as follows: x z 2 y 2z 1 .We see that both x and y are determined by z. We can freely choose a value of z, anarbitrary real number; then the two preceding equations give us the values of x andy for this choice of z. For example, Choose z 1. Then x z 2 3 and y 2z 1 3. The solution is(x, y, z) (3, 3, 1).Choose z 7. Then x z 2 9 and y 2z 1 15. The solutionis (x, y, z) (9, 15, 7).More generally, if we choose z t, an arbitrary real number, we get x t 2and y 2t 1. Therefore, the general solution is(x, y, z) (t 2, 2t 1, t) (2, 1, 0) t (1, 2, 1).This equation represents a line in space, as shown in Figure 3.(9, 15, 7) for t 7(3, 3, 1) for t 1(2, 1, 0) for t 0Figure 3 The line (x, y, z ) (t 2, 2t 1, t ).

1.1 Introduction to Linear Systems5A System without SolutionsIn the following system,shown: x 2y 4x 5y 7x 8yperform the eliminations yourself to obtain the result 3z 0 6z 3 9z 0 x z 2 y 2z 1 . 0 6 Whatever values we choose for x, y, and z, the equation 0 6 cannot besatisfied. This system is inconsistent; that is, it has no solutions.EXERCISES 1.1GOAL Set up and solve systems with as many as threelinear equations with three unknowns, and interpret theequations and their solutions geometrically.In Exercises 1 through 10, find all solutions of the linear systems using elimination as discussed in this section.Then check your solutions. 4x 3y 2 x 2y 1 2.1. 7x 5y 3 2x 3y 1 2x 4y 3 2x 4y 2 3. 4. 3x 6y 2 3x 6y 3 x 2y 3z 8 2x 3y 0 5. 6. x 3y 3z 10 4x 5y 0 x 2y 4z 9 x 2y 3z 0 x 2y 3z 1 8. 4x 5y 6z 0 7. x 3y 4z 3 7x 8y 10z 0 x 4y 5z 4 x 2y 3z 1 x 2y 3z 1 10. 2x 4y 7z 2 9. 3x 2y z 1 3x 7y 11z 8 7x 2y 3z 1 In Exercises 11 through 13, find all solutions of the linearsystems. Represent your solutions graphically, as intersections of lines in the x– y-plane. x 2y 3 x 2y 2 12.11. 2x 4y 6 3x 5y 17 x 2y 3 13. 2x 4y 8 In Exercises 14 through 16, find all solutions of the linearsystems. Describe your solutions in terms of intersectingplanes. You need not sketch these planes. x y z 0 x 4y z 0 15. 4x y 5z 0 14. 4x 13y 7z 0 6x y 4z 0 7x 22y 13z 1 x 4y z 0 16. 4x 13y 7z 0 7x 22y 13z 0 17. Find all solutions of the linear system x 2y a 3x 5y b ,where a and b are arbitrary constants.18. Find all solutions of the linear system x 2y 3z a x 3y 8z b , x 2y 2z c where a, b, and c are arbitrar

1.3 On the Solutions of Linear Systems; Matrix Algebra 25 2 Linear Transformations 41 2.1 Introduction to Linear Transformations and Their Inverses 41 2.2 Linear Transformations in Geometry 58 2.3 Matrix Products 75 2.4 The Inverse of a Linear Transformation 88 3 Subspaces of Rn and Their Dimensions 110 3.1 Image and Kernel of a Linear .