Linear Algebra

This page intentionally left blank

Linear AlgebraAn IntroductionSecond EditionRICHARD BRONSONProfessor of MathematicsSchool of Computer Sciences and EngineeringFairleigh Dickinson UniversityTeaneck, New JerseyGABRIEL B. COSTAAssociate Professor of Mathematical SciencesUnited States Military AcademyWest Point, New YorkAssociate Professor of Mathematics and Computer ScienceSeton Hall UniversitySouth Orange, New JerseyAMSTERDAM BOSTON HEIDELBERG LONDONNEW YORK OXFORD PARIS SAN DIEGOSAN FRANCISCO SINGAPORE SYDNEY TOKYOAcademic Press is an imprint of Elsevier

Acquisitions EditorProject ManagerMarketing ManagerCover DesignCompositionCover PrinterInterior PrinterTom SingerA.B. McGeeLeah AckersonEric DeCiccoSPi Publication ServicesPhoenix Color Corp.Sheridan Books, Inc.Academic Press in an imprint of Elsevier30 Corporate Drive, Suite 400, Burlington, MA 01803, USA525 B Street, Suite 1900, San Diego, California 92101-4495, USA84 Theobald’s Road, London WCIX 8RR, UKThis book is printed on acid-free paper.Copyright ß 2007, Elsevier Inc. All rights reserved.No part of this publication may be reproduced or transmitted in any form or by anymeans, electronic or mechanical, including photocopy, recording, or any informationstorage and retrieval system, without permission in writing from the publisher.Permissions may be sought directly from Elsevier’s Science & Technology RightsDepartment in Oxford, UK: phone: ( 44) 1865 843830, fax: ( 44) 1865 853333,E-mail: [email protected] You may also complete your request on-linevia the Elsevier homepage (, by selecting ‘‘Support & Contact’’then ‘‘Copyright and Permission’’ and then ‘‘Obtaining Permissions.’’Library of Congress Cataloging-in Publication DataApplication submittedBritish Library Cataloguing in Publication DataA catalogue record for this book is available from the British LibraryISBN 13: 978-0-12-088784-2ISBN 10: 0-12-088784-3For information on all Academic Press Publicationsvisit our Web site at www.books.elsevier.comPrinted in the United States of America07 08 09 10 11 9 8 7 6 5 43 2 1

To Evy – R.B.To my teaching colleagues at West Point and Seton Hall,especially to the Godfather, Dr. John J. Saccoman – G.B.C.

This page intentionally left blank

c Concepts1Matrix Multiplication11Special Matrices22Linear Systems of EquationsThe Inverse48LU Decomposition63nProperties of R72Chapter 1 Review8231VECTOR SPACESVectors85Subspaces99Linear Independence110Basis and Dimension119Row Space of a Matrix134Rank of a Matrix144Chapter 2 Review155LINEAR TRANSFORMATIONSFunctions157Linear Transformations163Matrix Representations173Change of Basis187Properties of Linear TransformationsChapter 3 Review217201EIGENVALUES, EIGENVECTORS, ANDDIFFERENTIAL EQUATIONSEigenvectors and Eigenvalues219Properties of Eigenvalues and EigenvectorsDiagonalization of Matrices237232vii

viii.Contents4. Exponential Matrix246Power Methods259Differential Equations in Fundamental Form270Solving Differential Equations in Fundamental FormA Modeling Problem288Chapter 4 Review291EUCLIDEAN INNER 07The QR Algorithm323Least Squares331Orthogonal ComplementsChapter 5 Review349341APPENDIX ADETERMINANTS353APPENDIX BJORDAN CANONICAL FORMSAPPENDIX CMARKOV CHAINSAPPENDIX DTHE SIMPLEX METHOD: AN EXAMPLEAPPENDIX EA WORD ON NUMERICAL TECHNIQUESAND TECHNOLOGY429377413ANSWERS AND HINTS TO SELECTED PROBLEMSChapter 1Chapter 2Chapter 3Chapter 4Chapter 5Appendix AAppendix BAppendix CAppendix DINDEX431448453463478488490497498499425431278

PrefaceAs technology advances, so does our need to understand and characterize it.This is one of the traditional roles of mathematics, and in the latter half ofthe twentieth century no area of mathematics has been more successful in thisendeavor than that of linear algebra. The elements of linear algebra are theessential underpinnings of a wide range of modern applications, from mathematical modeling in economics to optimization procedures in airline scheduling andinventory control. Linear algebra furnishes today’s analysts in business, engineering, and the social sciences with the tools they need to describe and define thetheories that drive their disciplines. It also provides mathematicians with compact constructs for presenting central ideas in probability, differential equations,and operations research.The second edition of this book presents the fundamental structures of linearalgebra and develops the foundation for using those structures. Many of theconcepts in linear algebra are abstract; indeed, linear algebra introduces studentsto formal deductive analysis. Formulating proofs and logical reasoning are skillsthat require nurturing, and it has been our aim to provide this.Much care has been taken in presenting the concepts of linear algebra in anorderly and logical progression. Similar care has been taken in proving resultswith mathematical rigor. In the early sections, the proofs are relatively simple,not more than a few lines in length, and deal with concrete structures, such asmatrices. Complexity builds as the book progresses. For example, we introducemathematical induction in Appendix A.A number of learning aides are included to assist readers. New concepts arecarefully introduced and tied to the reader’s experience. In the beginning, thebasic concepts of matrix algebra are made concrete by relating them to a store’sinventory. Linear transformations are tied to more familiar functions, and vectorspaces are introduced in the context of column matrices. Illustrations givegeometrical insight on the number of solutions to simultaneous linear equations,vector arithmetic, determinants, and projections to list just a few.Highlighted material emphasizes important ideas throughout the text. Computational methods—for calculating the inverse of a matrix, performing a GramSchmidt orthonormalization process, or the like—are presented as a sequence ofoperational steps. Theorems are clearly marked, and there is a summary ofimportant terms and concepts at the end of each chapter. Each section endswith numerous exercises of progressive difficulty, allowing readers to gainproficiency in the techniques presented and expand their understanding of theunderlying theory.ix

x.PrefaceChapter 1 begins with matrices and simultaneous linear equations. The matrix isperhaps the most concrete and readily accessible structure in linear algebra, andit provides a nonthreatening introduction to the subject. Theorems dealing withmatrices are generally intuitive, and their proofs are straightforward. Theprogression from matrices to column matrices and on to general vector spacesis natural and seamless.Separate chapters on vector spaces and linear transformations follow the material on matrices and lay the foundation of linear algebra. Our fourth chapter dealswith eigenvalues, eigenvectors, and differential equations. We end this chapterwith a modeling problem, which applies previously covered material. With theexception of mentioning partial derivatives in Section 5.2, Chapter 4 is the onlychapter for which a knowledge of calculus is required. The last chapter deals withthe Euclidean inner product; here the concept of least-squares fit is developed inthe context of inner products.We have streamlined this edition in that we have redistributed such topics as theJordan Canonical Form and Markov Chains, placing them in appendices. Ourgoal has been to provide both the instructor and the student with opportunitiesfor further study and reference, considering these topics as additional modules.We have also provided an appendix dedicated to the exposition of determinants,a topic which many, but certainly not all, students have studied.We have two new inclusions: an appendix dealing with the simplex method andan appendix touching upon numerical techniques and the use of technology.Regarding numerical methods, calculations and computations are essential tolinear algebra. Advances in numerical techniques have profoundly altered theway mathematicians approach this subject. This book pays heed to theseadvances. Partial pivoting, elementary row operations, and an entire section onLU decomposition are part of Chapter 1. The QR algorithm is covered inChapter 5.With the exception of Chapter 4, the only prerequisite for understanding thismaterial is a facility with high-school algebra. These topics can be covered in anycourse of 10 weeks or more in duration. Depending on the background of thereaders, selected applications and numerical methods may also be considered in aquarter system.We would like to thank the many people who helped shape the focus and contentof this book; in particular, Dean John Snyder and Dr. Alfredo Tan, both ofFairleigh Dickinson University.We are also grateful for the continued support of the Most Reverend JohnJ. Myers, J.C.D., D.D., Archbishop of Newark, N.J. At Seton Hall Universitywe acknowledge the Priest Community, ministered to by Monsignor James M.Cafone, Monsignor Robert Sheeran, President of Seton Hall University,Dr. Fredrick Travis, Acting Provost, Dr. Joseph Marbach, Acting Dean of theCollege of Arts and Sciences, Dr. Parviz Ansari, Acting Associate Dean ofthe College of Arts and Sciences, and Dr. Joan Guetti, Acting Chair of the

Preface.xiDepartment of Mathematics and Computer Science and all members of thatdepartment. We also thank the faculty of the Department of MathematicalSciences at the United States Military Academy, headed by Colonel MichaelPhillips, Ph.D., with a special thank you to Dr. Brian Winkel.Lastly, our heartfelt gratitude is given to Anne McGee, Alan Palmer, and TomSinger at Academic Press. They provided valuable suggestions and technicalexpertise throughout this endeavor.

This page intentionally left blank

Chapter 1Matrices1.1 BASIC CONCEPTSWe live in a complex world of finite resources, competing demands, and information streams that must be analyzed before resources can be allocated fairly tothe demands for those resources. Any mechanism that makes the processing ofinformation more manageable is a mechanism to be valued.Consider an inventory of T-shirts for one department of a large store. TheT-shirt comes in three different sizes and five colors, and each evening, thedepartment’s supervisor prepares an inventory report for management. A paragraph from such a report dealing with the T-shirts is reproduced in Figure 1.1.Figure 1.1T-shirtsNine teal small and five teal medium; eightplum small and six plum medium; large sizesare nearly depleted with only three sand, onerose, and two peach still available; we alsohave three medium rose, five medium sand,one peach medium, and seven peach small.Figure 1.22Rose0S ¼4 31Teal950Plum860Sand053Peach 37small1 5 medium2large1

2.MatricesThis report is not easy to analyze. In particular, one must read the entireparagraph to determine the number of sand-colored, small T-shirts in currentstock. In contrast, the rectangular array of data presented in Figure 1.2 summarizes the same information better. Using Figure 1.2, we see at a glance that nosmall, sand-colored T-shirts are in stock.A matrix is arectangular array ofelements arrangedin horizontal rowsand verticalcolumns.A matrix is a rectangular array of elements arranged in horizontal rows andvertical columns. The array in Figure 1.1 is a matrix, as are21L ¼ 45024M ¼ 430332 5, 1124311 5;2(1:1)(1:2)and2319:567N ¼ 4 p 5:pffiffiffi2(1:3)The rows and columns of a matrix may be labeled, as in Figure 1.1, or notlabeled, as in matrices (1.1) through (1.3).The matrix in (1.1) has three rows and two columns; it is said to have order (orsize) 3 2 (read three by two). By convention, the row index is always givenbefore the column index. The matrix in (1.2) has order 3 3, whereas that in(1.3) has order 3 1. The order of the stock matrix in Figure 1.2 is 3 5.The entries of a matrix are called elements. We use uppercase boldface letters todenote matrices and lowercase letters for elements. The letter identifier for anelement is generally the same letter as its host matrix. Two subscripts areattached to element labels to identify their location in a matrix; the first subscriptspecifies the row position and the second subscript the column position. Thus, l12denotes the element in the first row and second column of a matrix L; for thematrix L in (1.2), l12 ¼ 3. Similarly, m32 denotes the element in the third row andsecond column of a matrix M; for the matrix M in (1.3), m32 ¼ 4. In general,a matrix A of order p n has the form2a116 a2166A ¼ 6 a316 .4 .a12a22a32.a13a23a33.ap1ap2ap33. . . a1n. . . a2n 77. . . a3n 77. 7. 5. . . apn(1:4)

1.1Basic Concepts.3which is often abbreviated to [aij ]p n or just [aij ], where aij denotes an element inthe ith row and jth column.Any element having its row index equal to its column index is a diagonal element.Diagonal elements of a matrix are the elements in the 1-1 position, 2-2 position,3-3 position, and so on, for as many elements of this type that exist in a particularmatrix. Matrix (1.1) has 1 and 2 as its diagonal elements, whereas matrix (1.2)has 4, 2, and 2 as its diagonal elements. Matrix (1.3) has only 19.5 as a diagonalelement.A matrix is square if it has the same number of rows as columns. In general,a square matrix has the form2a1n3a11a12a13.6a6 2166 a3166 .6 .4 .a22a23.a32.a33.a2n 777a3n 77. 77. 5an1an2an3.annwith the elements a11 , a22 , a33 , . . . , ann forming the main (or principal)diagonal.The elements of a matrix need not be numbers; they can be functions or, as weshall see later, matrices themselves. Hence"R12(t þ 1)dttpffiffiffiffiffi3t3#2 ,0"sin u cos u cos usin ux2x#,and26 x4e5ddx37ln x 5xþ2are all good examples of matrices.A row matrix is a matrix having a single row; a col