Linear Algebra with Applications

This page intentionally left blank

Linear Algebra with ApplicationsFifth EditionOtto BretscherColby College

Editor in Chief: Christine HoagSenior Acquisitions Editor: William HoffmanExecutive Marketing Manager: Jeff WeidenaarMarketing Assistant: Caitlin CrainSenior Production Project Manager:Beth HoustonManager, Cover VisualResearch and Permissions: Jayne ConteCover Designer: Suzanne DudaCover Art: Colorization by JorgensenFernandez/NASAFull-Service Project Management:Integra Software Services, Ltd.Composition: Integra Software Services, Ltd.Printer/Binder: Edwards Brothers MalloyCover Printer: Lehigh/PhoenixThe cover shows the Mars rover Curiosity, casting a long shadow onto Gale crater, facing Aeolis Mons. LinearAlgebra plays a central role in many aspects of the planning, design, and control of a space mission. For example,data compression is used for interplanetary communication (see Page 411), and error-correction codes increase thereliability of data transmission (see Page 121).Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appearon the appropriate page within text.Copyright 2013, 2009, 2005 by Pearson Education, Inc. All rights reserved. Manufactured in the United States ofAmerica. This publication is protected by Copyright, and permission should be obtained from the publisher prior toany prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic,mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, pleasesubmit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River,New Jersey 07458, or you may fax your request to 201-236-3290.Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks.Where those designations appear in this book, and the publisher was aware of a trademark claim, the designationshave been printed in initial caps or all caps.Library of Congress Cataloging-in-Publication DataBretscher, Otto.Linear algebra with applications / Otto Bretscher. – 5th ed.p. cm.Includes index.ISBN-13: 978-0-321-79697-4ISBN-10: 0-321-79697-71. Algebras, Linear–Textbooks. I. Title.QA184.2.B73 2013512’.5–dc23201201755110 98 76 54 32 1EBM16 1514 1312ISBN-10:0-321-79697-7ISBN-13: 978-0-321-79697-4

To my parentsOtto and Margrit Bretscher-Zwickywith love and gratitude

This page intentionally left blank

ContentsPreface ix1Linear Equations1.11.21.32Linear Transformations2. and Kernel of a Linear TransformationSubspaces of Rn ; Bases and Linear IndependenceThe Dimension of a Subspace of RnCoordinatesLinear Spaces4.14.24.35Introduction to Linear Transformations and TheirInversesLinear Transformations in GeometryMatrix ProductsThe Inverse of a Linear TransformationSubspaces of Rn and Their Dimensions3. to Linear SystemsMatrices, Vectors, and Gauss–Jordan EliminationOn the Solutions of Linear Systems; Matrix AlgebraIntroduction to Linear SpacesLinear Transformations and IsomorphismsThe Matrix of a Linear TransformationOrthogonality and Least Squares5. Projections and Orthonormal BasesGram–Schmidt Process and QR FactorizationOrthogonal Transformations and Orthogonal MatricesLeast Squares and Data FittingInner Product 2202218225236249vii

viiiContents6Determinants6.16.26.37Eigenvalues and ing the Eigenvalues of a MatrixFinding the Eigenvectors of a MatrixMore on Dynamical SystemsComplex EigenvaluesStabilitySymmetric Matrices and Quadratic Forms8.18.28.39Introduction to DeterminantsProperties of the DeterminantGeometrical Interpretations of the Determinant;Cramer’s RuleSymmetric MatricesQuadratic FormsSingular ValuesLinear Differential Equations9.19.29.3An Introduction to Continuous Dynamical SystemsThe Complex Case: Euler’s FormulaLinear Differential Operators and Linear DifferentialEquationsAppendix A Vectors 457Appendix B Techniques of Proof 467Answers to Odd-Numbered Exercises 471Subject Index 499Name Index 5415429442

Preface (with David Steinsaltz)Apolice officer on patrol at midnight, so runs an old joke, notices a mancrawling about on his hands and knees under a streetlamp. He walks overto investigate, whereupon the man explains in a tired and somewhat slurredvoice that he has lost his housekeys. The policeman offers to help, and for the nextfive minutes he too is searching on his hands and knees. At last he exclaims, “Areyou absolutely certain that this is where you dropped the keys?”“Here? Absolutely not. I dropped them a block down, in the middle of thestreet.”“Then why the devil have you got me hunting around this lamppost?”“Because this is where the light is.”It is mathematics, and not just (as Bismarck claimed) politics, that consists in “theart of the possible.” Rather than search in the darkness for solutions to problems ofpressing interest, we contrive a realm of problems whose interest lies above all inthe fact that solutions can conceivably be found.Perhaps the largest patch of light surrounds the techniques of matrix arithmeticand algebra, and in particular matrix multiplication and row reduction. Here wemight begin with Descartes, since it was he who discovered the conceptual meetingpoint of geometry and algebra in the identification of Euclidean space with R3 ; thetechniques and applications proliferated since his day. To organize and clarify thoseis the role of a modern linear algebra course.Computers and ComputationAn essential issue that needs to be addressed in establishing a mathematical methodology is the role of computation and of computing technology. Are the proper subjects of mathematics algorithms and calculations, or are they grand theories andabstractions that evade the need for computation? If the former, is it important thatthe students learn to carry out the computations with pencil and paper, or should thealgorithm “press the calculator’s x 1 button” be allowed to substitute for the traditional method of finding an inverse? If the latter, should the abstractions be taughtthrough elaborate notational mechanisms or through computational examples andgraphs?We seek to take a consistent approach to these questions: Algorithms and computations are primary, and precisely for this reason computers are not. Again andagain we examine the nitty-gritty of row reduction or matrix multiplication in order to derive new insights. Most of the proofs, whether of rank-nullity theorem, thevolume-change formula for determinants, or the spectral theorem for symmetricmatrices, are in this way tied to hands-on procedures.The aim is not just to know how to compute the solution to a problem, but toimagine the computations. The student needs to perform enough row reductions byhand to be equipped to follow a line of argument of the form: “If we calculate thereduced row-echelon form of such a matrix . . . ,” and to appreciate in advance thepossible outcomes of a particular computation.ix

xPrefaceIn applications, the solution to a problem is hardly more important than recognizing its range of validity and appreciating how sensitive it is to perturbations of theinput. We emphasize the geometric and qualitative nature of the solutions, notionsof approximation, stability, and “typical” matrices. The discussion of Cramer’s rule,for instance, underscores the value of closed-form solutions for visualizing a system’s behavior and understanding its dependence on initial conditions.The availability of computers is, however, neither to be ignored nor regretted.Each student and instructor will have to decide how much practice is needed to besufficiently familiar with the inner workings of the algorithm. As the explicit computations are being replaced gradually by a theoretical overview of how the algorithm works, the burden of calculation will be taken up by technology, particularlyfor those wishing to carry out the more numerical and applied exercises.Examples, Exercises, Applications, and HistoryThe exercises and examples are the heart of this book. Our objective is not just toshow our readers a “patch of light” where questions may be posed and solved, butto convince them that there is indeed a great deal of useful, interesting material tobe found in this area if they take the time to look around. Consequently, we haveincluded genuine applications of the ideas and methods under discussion to a broadrange of sciences: physics, computer science, chemistry, biology, economics, and,of course, mathematics itself. Often we have simplified them to sharpen the point,but they use the methods and models of contemporary scientists.With such a large and varied set of exercises in each section, instructors shouldhave little difficulty in designing a course that is suited to their aims and to the needsof their students. Quite a few straightforward computation problems are offered,of course. Simple (and, in a few cases, not so simple) proofs and derivations arerequired in some exercises. In many cases, theoretical principles that are discussedat length in more abstract linear algebra courses are here found broken up in bitesize exercises.The examples make up a significant portion of the text; we have kept abstractexposition to a minimum. It is a matter of taste whether general theories shouldgive rise to specific examples or be pasted together from them. In a text such as thisone, attempting to keep an eye on applications, the latter is clearly preferable: Theexamples always precede the theorems in this book.Scattered throughout the mathematical exposition are quite a few names anddates, some historical accounts, and anecdotes. Students of mathematics are toorarely shown that the seemingly strange and arbitrary concepts they study are theresults of long and hard struggles. It will encourage the readers to know that amere two centuries ago some of the most brilliant mathematicians were wrestlingwith problems such as the meaning of dimension or the interpretation of eit , andto realize that the advance of time and understanding actually enables them, withsome effort of their own, to see farther than those great minds.Continuing Text Features Linear transformations are introduced early on in the text to make the discussion of matrix operations more meaningful and easier to visualize.

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