F I F T H E D I T I O N Linear Algebra and Its Applications David C. Lay University of Maryland—College Park with Steven R. Lay Lee University and Judi J. McDonald Washington State University Boston Columbus Indianapolis New York San Francisco Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto Delhi Mexico City Sao Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo REVISEDPAGES Editorial Director:Chris Hoag Editor in Chief:Deirdre Lynch Acquisitions Editor:William Hoffman Editorial Assistant:Salena Casha Program Manager:Tatiana Anacki Project Manager:Kerri Consalvo Program Management Team Lead:Marianne Stepanian Project Management Team Lead:Christina Lepre Media Producer:Jonathan Wooding TestGen Content Manager:Marty Wright MathXLContent Developer:Kristina Evans Marketing Manager:Jeff Weidenaar Marketing Assistant:Brooke Smith Senior Author Support/Technology Specialist:Joe Vetere Rights and Permissions Project Manager:Diahanne Lucas Dowridge Procurement Specialist:Carol Melville Associate Director of Design Andrea Nix Program Design Lead:Beth Paquin Composition:Aptara®,Inc. Cover Design:Cenveo Cover Image:PhotoTalk/E+/Getty Images Copyright © 2016,2012,2006 by Pearson Education,Inc.All Rights Reserved.Printed in the United States of America.This publication is protected by copyright,and permission should be obtained from the publisher prior to any prohibited reproduction,storage in a retrieval system,or transmission in any form or by any means,electronic, mechanical,photocopying,recording,or otherwise.For information regarding permissions,request forms and the appropriate contacts within the Pearson Education Global Rights & Permissions department,please visit www.pearsoned.com/permissions/. Acknowledgements of third party content appear on page P1,which constitutes an extension of this copyright page. PEARSON, ALWAYSLEARNING, is an exclusive trademark in the U.S. and/or other countries owned by Pearson Education,Inc.or its affiliates. Unless otherwise indicated herein,any third-party trademarks that may appear in this work are the property of their respective owners and any references to third-party trademarks,logos or other trade dress are for demonstrative or descriptive purposes only.Such references are not intended to imply any sponsorship,endorsement,authorization,or promotion of Pearson’s products by the owners of such marks,or any relationship between the owner and Pearson Education,Inc.or its affiliates,authors,licensees or distributors. This work is solely for the use of instructors and administrators for the purpose of teaching courses and assessing student learning.Unauthorized dissemination,publication or sale of the work,in whole or in part (including posting on the internet) will destroy the integrity of the work and is strictly prohibited. Library of Congress Cataloging-in-Publication Data Lay,David C. Linear algebra and its applications / David C. Lay,University of Maryland,College Park,Steven R. Lay,Lee University, Judi J. McDonald,Washington State University.– Fifth edition. pages cm Includes index. ISBN978-0-321-98238-4 ISBN0-321-98238-X 1.Algebras,Linear–Textbooks.I. Lay,Steven R.,1944- II. McDonald,Judi.III. Title. QA184.2.L39 2016 512.5–dc23 0 2014011617 REVISEDPAGES About the Author David C. Lay holds a B.A. from Aurora University (Illinois), and an M.A. and Ph.D. from the University of California at Los Angeles. David Lay has been an educator and research mathematician since 1966,mostly at the University of Maryland,College Park. He has also served as a visiting professor at the University of Amsterdam, the Free University in Amsterdam,and the University of Kaiserslautern,Germany.He has published more than 30 research articles on functional analysis and linear algebra. As a founding member of the NSF-sponsored Linear Algebra Curriculum Study Group, David Lay has been a leader in the current movement to modernize the linear algebra curriculum.Lay is also a coauthor of several mathematics texts,includingIn- troduction to Functional Analysiswith Angus E. Taylor,Calculus and Its Applications, with L.J.Goldstein and D.I.Schneider,andLinear Algebra Gems—Assets for Under- graduate Mathematics,with D. Carlson,C.R.Johnson,and A.D.Porter. David Lay has received four university awards for teaching excellence,including, in 1996, the title of Distinguished Scholar–Teacher of the University of Maryland. In 1994, he was given one of the Mathematical Association of America’s Awards for Distinguished College or University Teaching of Mathematics. He has been elected by the university students to membership in Alpha Lambda Delta National Scholastic Honor Society and Golden Key National Honor Society. In 1989, Aurora University conferred on him the Outstanding Alumnus award.David Lay is a member of the Ameri- can Mathematical Society,the Canadian Mathematical Society,the International Linear Algebra Society,the Mathematical Association of America,Sigma Xi,and the Society for Industrial and Applied Mathematics.Since 1992,he has served several terms on the national board of the Association of Christians in the Mathematical Sciences. To my wife, Lillian, and our children, Christina, Deborah, and Melissa, whose support, encouragement, and faithful prayers made this book possible. David C. Lay REVISEDPAGES Joining the Authorship on the Fifth Edition Steven R. Lay Steven R. Lay began his teaching career at Aurora University (Illinois) in 1971, after earning an M.A. and a Ph.D. in mathematics from the University of California at Los Angeles.His career in mathematics was interrupted for eight years while serving as a missionary in Japan.Upon his return to the States in 1998,he joined the mathematics faculty at LeeUniversity (Tennessee) and has been there ever since.Since then he has supported his brother David in refining and expanding the scope of this popular linear algebra text, including writing most of Chapters 8 and 9. Steven is also the author of three college-level mathematics texts: Convex Sets and Their Applications, Analysis with an Introduction to Proof,andPrinciples of Algebra. In 1985, Steven received the Excellence in Teaching Award at Aurora University. He and David, and their father, Dr. L. Clark Lay, are all distinguished mathematicians, and in 1989 they jointly received the Outstanding Alumnus award from their alma mater, Aurora University. In 2006, Steven was honored to receive the Excellence in Scholarship Award at Lee University. He is a member of the American Mathematical Society,the Mathematics Association of America,and the Association of Christians in the Mathematical Sciences. Judi J. McDonald Judi J. McDonald joins the authorship team after working closely with David on the fourth edition. She holds a B.Sc. in Mathematics from the University of Alberta, and an M.A. and Ph.D. from the University of Wisconsin. She is currently a professor at Washington State University. She has been an educator and research mathematician since the early 90s.She has more than 35 publications in linear algebra research journals. Several undergraduate and graduate students have written projects or theses on linear algebra under Judi’s supervision. She has also worked with the mathematics outreach project Math Central http://mathcentral.uregina.ca/ and continues to be passionate about mathematics education and outreach. Judi has received three teaching awards:two Inspiring Teaching awards at theUniversity of Regina, and the Thomas Lutz College of Arts and Sciences Teaching Award at Washington State University.She has been an active member of the International Linear Algebra Society and the Association for Women in Mathematics throughout her ca- reer and has also been a member of the Canadian Mathematical Society,the American Mathematical Society, the Mathematical Association of America, and the Society for Industrial and Applied Mathematics. iv REVISEDPAGES Contents Preface viii ANote to Students xv Chapter 1 Linear Equations in Linear Algebra 1 INTRODUCTORYEXAMPLE:LinearModelsinEconomicsandEngineering 1 1.1 Systems of Linear Equations 2 1.2 Row Reduction and Echelon Forms 12 1.3 Vector Equations 24 1.4 The Matrix EquationAx b 35 D 1.5 Solution Sets of Linear Systems 43 1.6 Applications of Linear Systems 50 1.7 Linear Independence 56 1.8 Introduction to Linear Transformations 63 1.9 The Matrix of a Linear Transformation 71 1.10 Linear Models in Business,Science,and Engineering 81 Supplementary Exercises 89 Chapter 2 Matrix Algebra 93 INTRODUCTORYEXAMPLE:ComputerModelsinAircraftDesign 93 2.1 Matrix Operations 94 2.2 The Inverse of a Matrix 104 2.3 Characterizations of Invertible Matrices 113 2.4 Partitioned Matrices 119 2.5 Matrix Factorizations 125 2.6 The Leontief Input–Output Model 134 2.7 Applications to Computer Graphics 140 2.8 Subspaces ofRn 148 2.9 Dimension and Rank 155 Supplementary Exercises 162 Chapter 3 Determinants 165 INTRODUCTORYEXAMPLE:RandomPathsandDistortion 165 3.1 Introduction to Determinants 166 3.2 Properties of Determinants 171 3.3 Cramer’s Rule,Volume,and Linear Transformations 179 Supplementary Exercises 188 v REVISEDPAGES vi Contents Chapter 4 Vector Spaces 191 INTRODUCTORYEXAMPLE:SpaceFlightandControlSystems 191 4.1 Vector Spaces and Subspaces 192 4.2 Null Spaces,Column Spaces,and Linear Transformations 200 4.3 Linearly Independent Sets;Bases 210 4.4 Coordinate Systems 218 4.5 The Dimension of a Vector Space 227 4.6 Rank 232 4.7 Change of Basis 241 4.8 Applications to Difference Equations 246 4.9 Applications to Markov Chains 255 Supplementary Exercises 264 Chapter 5 Eigenvalues and Eigenvectors 267 INTRODUCTORYEXAMPLE:DynamicalSystemsandSpottedOwls 267 5.1 Eigenvectors and Eigenvalues 268 5.2 The Characteristic Equation 276 5.3 Diagonalization 283 5.4 Eigenvectors and Linear Transformations 290 5.5 Complex Eigenvalues 297 5.6 Discrete Dynamical Systems 303 5.7 Applications to Differential Equations 313 5.8 Iterative Estimates for Eigenvalues 321 Supplementary Exercises 328 Chapter 6 Orthogonality and Least Squares 331 INTRODUCTORYEXAMPLE:TheNorthAmericanDatum andGPSNavigation 331 6.1 Inner Product,Length,and Orthogonality 332 6.2 Orthogonal Sets 340 6.3 Orthogonal Projections 349 6.4 The Gram–Schmidt Process 356 6.5 Least-Squares Problems 362 6.6 Applications to Linear Models 370 6.7 Inner Product Spaces 378 6.8 Applications of Inner Product Spaces 385 Supplementary Exercises 392 REVISEDPAGES Contents vii Chapter 7 Symmetric Matrices and Quadratic Forms 395 INTRODUCTORYEXAMPLE:MultichannelImageProcessing 395 7.1 Diagonalization of Symmetric Matrices 397 7.2 Quadratic Forms 403 7.3 Constrained Optimization 410 7.4 The Singular Value Decomposition 416 7.5 Applications to Image Processing and Statistics 426 Supplementary Exercises 434 Chapter 8 The Geometry of Vector Spaces 437 INTRODUCTORYEXAMPLE:ThePlatonicSolids 437 8.1 Affine Combinations 438 8.2 Affine Independence 446 8.3 Convex Combinations 456 8.4 Hyperplanes 463 8.5 Polytopes 471 8.6 Curves and Surfaces 483 Chapter 9 Optimization (Online) INTRODUCTORYEXAMPLE:TheBerlinAirlift 9.1 Matrix Games 9.2 Linear Programming—Geometric Method 9.3 Linear Programming—Simplex Method 9.4 Duality Chapter 10 Finite-State Markov Chains (Online) INTRODUCTORYEXAMPLE:GooglingMarkovChains 10.1 Introduction and Examples 10.2 The Steady-State Vector and Google’s PageRank 10.3 Communication Classes 10.4 Classification of States and Periodicity 10.5 The Fundamental Matrix 10.6 Markov Chains and Baseball Statistics Appendixes A Uniqueness of the Reduced Echelon Form A1 B Complex Numbers A2 Glossary A7 Answers to Odd-Numbered Exercises A17 Index I1 Photo Credits P1 REVISEDPAGES Preface The response of students and teachers to the first four editions ofLinear Algebra and Its Applicationshas been most gratifying.ThisFifth Editionprovides substantial support both for teaching and for using technology in the course. As before, the text provides a modern elementary introduction to linear algebra and a broad selection of interest- ing applications. The material is accessible to students with the maturity that should come from successful completion of two semesters of college-level mathematics,usu- ally calculus. The main goal of the text is to help students master the basic concepts and skills they will use later in their careers.The topics here follow the recommendations of the Linear Algebra Curriculum Study Group, which were based on a careful investigation of the real needs of the students and a consensus among professionals in many disciplines that use linear algebra. We hope this course will be one of the most useful and interesting mathematics classes taken by undergraduates. WHAT'S NEW IN THIS EDITION The main goals of this revision were to update the exercises,take advantage of improve- ments in technology,and provide more support for conceptual learning. 1. Support for the Fifth Edition is offered through MyMathLab. MyMathLab, from Pearson,is the world’s leading online resource in mathematics,integrating interac- tive homework, assessment, and media in a flexible, easy-to-use format. Students submit homework online for instantaneous feedback,support,and assessment.This system works particularly well for computation-based skills. Many additional re- sources are also provided through the MyMathLab web site. 2. The Fifth Editionof the text is available in an interactive electronic format.Using the CDF player, a free Mathematica player available from Wolfram, students can interact with figures and experiment with matrices by looking at numerous examples with just the click of a button.The geometry of linear algebra comes alive through these interactive figures. Students are encouraged to develop conjectures through experimentation and then verify that their observations are correct by examining the relevant theorems and their proofs. The resources in the interactive version of the text give students the opportunity to play with mathematical objects and ideas much as we do with our own research.Files for Wolfram CDFPlayer are also available for classroom presentations. 3. TheFifth Editionincludes additional support for concept- and proof-based learning. Conceptual Practice Problems and their solutions have been added so that most sec- tions now have a proof- or concept-based example for students to review.Additional guidance has also been added to some of the proofs of theorems in the body of the textbook. viii REVISEDPAGES Preface ix 4. More than 25 percent of the exercises are new or updated,especially the computa- tional exercises.The exercise sets remain one of the most important features of this book,and these new exercises follow the same high standard of the exercise sets from the past four editions.They are crafted in a way that reflects the substance of each of the sections they follow, developing the students’ confidence while challenging them to practice and generalize the new ideas they have encountered. DISTINCTIVE FEATURES Early Introduction of Key Concepts Many fundamental ideas of linear algebra are introduced within the first seven lectures, in the concrete setting ofRn,and then gradually examined from different points of view. Later generalizations of these concepts appear as natural extensions of familiar ideas, visualized through the geometric intuition developed in Chapter 1.Amajor achievement of this text is that the level of difficulty is fairly even throughout the course. A Modern View of Matrix Multiplication Good notation is crucial,and the text reflects the way scientists and engineers actually use linear algebra in practice.The definitions and proofs focus on the columns of a ma- trix rather than on the matrix entries.Acentral theme is to view a matrix–vector product Axas a linear combination of the columns ofA.This modern approach simplifies many arguments,and it ties vector space ideas into the study of linear systems. Linear Transformations Linear transformations form a “thread” that is woven into the fabric of the text.Their use enhances the geometric flavor of the text.In Chapter 1,for instance,linear transfor- mations provide a dynamic and graphical view of matrix–vector multiplication. Eigenvalues and Dynamical Systems Eigenvalues appear fairly early in the text,in Chapters 5 and 7.Because this material is spread over several weeks,students have more time than usual to absorb and review these critical concepts.Eigenvalues are motivated by and applied to discrete and con- tinuous dynamical systems, which appear in Sections 1.10, 4.8, and 4.9, and in five sections of Chapter5.Some courses reach Chapter5 after about five weeks by covering Sections 2.8 and 2.9 instead of Chapter 4. These two optional sections present all the vector space concepts from Chapter4 needed for Chapter5. Orthogonality and Least-Squares Problems These topics receive a more comprehensive treatment than is commonly found in begin- ning texts.The Linear Algebra Curriculum Study Group has emphasized the need for a substantial unit on orthogonality and least-squares problems, because orthogonality plays such an important role in computer calculations and numerical linear algebra and because inconsistent linear systems arise so often in practical work. REVISEDPAGES