A First Course in Linear Algebra Robert A. Beezer University of Puget Sound Version 3.50 Congruent Press Robert A. Beezer is a Professor of Mathematics at the University of Puget Sound, where he has been on the faculty since 1984. He received a B.S. in Mathematics (with an Emphasis in Computer Science) from the University of Santa Clara in 1978, a M.S. in Statistics from the University of Illinois at Urbana-Champaign in 1982 and a Ph.D. in Mathematics from the University of Illinois at Urbana-Champaign in 1984. In addition to his teaching atthe UniversityofPugetSound,he has made sabbatical visits to the University of the West Indies (Trinidad campus) and the University of Western Australia. He has also given several courses in the Master’s program at the African Institute for Mathematical Sciences, South Africa. He has been a Sage developer since 2008. He teaches calculus, linear algebra and abstract algebra regularly, while his research interests include the applications of linear algebra to graph theory. His professional website is at http://buzzard.ups.edu. Edition Version 3.50 ISBN: 978-0-9844175-5-1 Cover Design Aidan Meacham Publisher Robert A. Beezer Congruent Press Gig Harbor, Washington, USA c 2004—2015 Robert A. Beezer (cid:13) Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front- Cover Texts, and no Back-Cover Texts. A copy of the license is included in the appendix entitled “GNU Free Documentation License”. The most recent version can always be found at http://linear.pugetsound.edu. To my wife, Pat. Contents Preface v Acknowledgements xi Systems of Linear Equations 1 What is Linear Algebra? . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Solving Systems of Linear Equations . . . . . . . . . . . . . . . . . . . . 8 Reduced Row-Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . 22 Types of Solution Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Homogeneous Systems of Equations . . . . . . . . . . . . . . . . . . . . 58 Nonsingular Matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Vectors 74 Vector Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Linear Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Spanning Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 Linear Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Linear Dependence and Spans . . . . . . . . . . . . . . . . . . . . . . . . 136 Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Matrices 162 Matrix Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 Matrix Inverses and Systems of Linear Equations . . . . . . . . . . . . . 193 Matrix Inverses and Nonsingular Matrices . . . . . . . . . . . . . . . . . 207 Column and Row Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 Four Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Vector Spaces 257 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 Linear Independence and Spanning Sets . . . . . . . . . . . . . . . . . . 288 iv Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 Properties of Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 Determinants 340 Determinant of a Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 Properties of Determinants of Matrices . . . . . . . . . . . . . . . . . . . 355 Eigenvalues 367 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . 367 Properties of Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . 390 Similarity and Diagonalization . . . . . . . . . . . . . . . . . . . . . . . 403 Linear Transformations 420 Linear Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . 420 Injective Linear Transformations . . . . . . . . . . . . . . . . . . . . . . 446 Surjective Linear Transformations . . . . . . . . . . . . . . . . . . . . . 462 Invertible Linear Transformations . . . . . . . . . . . . . . . . . . . . . . 480 Representations 501 Vector Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 Matrix Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . 514 Change of Basis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542 Orthonormal Diagonalization . . . . . . . . . . . . . . . . . . . . . . . . 568 Preliminaries 581 Complex Number Operations . . . . . . . . . . . . . . . . . . . . . . . . 581 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587 Reference 591 Proof Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591 Archetypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605 Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 610 Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612 GNU Free Documentation License . . . . . . . . . . . . . . . . . . . . . 613 v Preface This text is designed to teach the concepts and techniques of basic linear algebra as a rigorous mathematical subject. Besides computational proficiency, there is an emphasis on understanding definitions and theorems, as well as reading, understand- ing and creating proofs. A strictly logical organization, complete and exceedingly detailedproofsofeverytheorem,adviceontechniquesforreadingandwritingproofs, and a selection of challenging theoretical exercises will slowly provide the novice with the tools and confidence to be able to study other mathematical topics in a rigorous fashion. Most students taking a course in linear algebra will have completed courses in differential and integral calculus, and maybe also multivariate calculus, and will typicallybesecond-yearstudentsinuniversity.Thislevelofmathematicalmaturityis expected, however there is little or no requirement to know calculus itself to use this book successfully. With complete details for every proof, for nearly every example, and for solutions to a majority of the exercises, the book is ideal for self-study, for those of any age. While there is an abundance of guidance in the use of the software system, Sage, there is no attempt to address the problems of numerical linear algebra, which are arguably continuous in nature. Similarly, there is little emphasis on a geometric approach to problems of linear algebra. While this may contradict the experience of many experienced mathematicians, the approach here is consciously algebraic. As a result, the student should be well-prepared to encounter groups, rings and fields in future courses in algebra, or other areas of discrete mathematics. How to Use This Book While the book is divided into chapters, the main organizational unit is the thirty- seven sections. Each contains a selection of definitions, theorems, and examples interspersedwithcommentary. Ifyou are enrolledin acourse,readthe section before class and then answer the section’s reading questions as preparation for class. The version available forviewingin a webbrowseristhe mostcomplete,integrat- ingallofthecomponentsofthebook.Consideracquaintingyourselfwiththisversion. vi Knowlsareindicatedbyadashedunderlinesandwillallowyoutoseamlesslyremind yourself of the content of definitions, theorems, examples, exercises, subsections and more. Use them liberally. Historically, mathematics texts have numbered definitions and theorems. We have instead adopted a strategy more appropriate to the heavy cross-referencing, linking and knowling afforded by modern media. Mimicking an approach taken by Donald Knuth, we have given items short titles and associated acronyms. You will become comfortable with this scheme after a short time, and might even come to appreciate its inherent advantages. In the web version, each chapter has a list of ten or so important items from that chapter, and you will find yourself recognizing some of these acronyms with no extra effort beyond the normal amount of study. Bruno Mello suggests that some say an acronym should be pronounceable as a word (such as “radar”), and otherwise is an abbreviation. We will not be so strict in our use of the term. Exercises come in three flavors, indicated by the first letter of their label. “C” indicates a problem that is essentially computational. “T” represents a problem that is more theoretical, usually requiring a solution that is as rigorous as a proof. “M” stands for problems that are “medium”, “moderate”, “midway”, “mediate” or “median”,butnever“mediocre.”Theirstatementscouldfeelcomputational,buttheir solutions require a more thorough understanding of the concepts or theory, while perhaps not being as rigorous as a proof. Of course, such a tripartite division will be subject to interpretation. Otherwise, larger numerical values indicate greater perceived difficulty, with gaps allowing for the contribution of new problems from readers. Many, but not all, exercises have complete solutions. These are indicated by daggers in the PDF and print versions, with solutions available in an online supplement,whileinthewebversionasolutionisindicatedbyaknowlrightafterthe problem statement. Resist the urge to peek early. Working the exercises diligently is the best way to master the material. The Archetypes are a collection of twenty-four archetypical examples. The open source lexical database, WordNet, defines an archetype as “something that serves as a model or a basis for making copies.” We employ the word in the first sense here. By carefully choosing the examples we hope to provide at least one example that is interesting and appropriate for many of the theorems and definitions, and also providecounterexamplestoconjectures(andespeciallycounterexamplestoconverses of theorems). Each archetype has numerous computational results which you could strive to duplicate as you encounter new definitions and theorems. There are some exercises which will help guide you in this quest. Supplements Print versions of the book (either a physical copy or a PDF version) have significant material available as supplements. Solutions are contained in the Exercise Manual. vii Adviceontheuseoftheopensourcemathematicalsoftwaresystem,Sage,iscontained in another supplement. (Look for a linear algebra “Quick Reference” sheet at the Sage website.) The Archetypes are available in a PDF form which could be used as a workbook. Flashcards, with the statement of every definition and theorem, in order of appearance, are also available. Freedom Thisbookiscopyrightedbyitsauthor.Somewouldsayitishis“intellectualproperty,” a distasteful phrase if there ever was one. Rather than exercise all the restrictions provided by the government-granted monopoly that is copyright, the author has granted you a license, the GNU Free Documentation License (GFDL). In summary it says you may receive an electronic copy at no cost via electronic networks and you may make copies forever. So your copy of the book never has to go “out-of-print.” You may redistribute copies and you may make changes to your copy for your own use. However, you have one major responsibility in accepting this license. If you make changes and distribute the changed version, then you must offer the same license for the new version, you must acknowledge the original author’s work, and you must indicate where you have made changes. In practice, if you see a change that needs to be made (like correcting an error, or adding a particularly nice theoretical exercise), you may just wish to donate the change to the author rather than create and maintain a new version. Such donations are highly encouraged and gratefully accepted. You may notice the large number of small mistakes that have been corrected by readers that have come before you. Pay it forward. So, in one word, the book really is “free” (as in “no cost”). But the open license employed is vastly different than “free to download, all rights reserved.” Most importantly, you know that this book, and its ideas, are not the property of anyone. Or they are the property of everyone. Either way, this book has its own inherent “freedom,” separate from those who contribute to it. Much of this philosophy is embodied in the following quote: If nature has made any one thing less susceptible than all others of exclusive property, it is the action of the thinking power called an idea, which an individual may exclusively possess as long as he keeps it to himself; but the moment it is divulged, it forces itself into the possession of every one, and the receiver cannot dispossess himself of it. Its peculiar character, too, is that no one possesses the less, because every other possesses the whole of it. He who receives an idea from me, receives instruction himself without lessening mine; as he who lights his taper at mine, receives light without darkening me. That ideas should freely spread from one to another over the globe, for the moral and mutual instruction of man, and improvement of his condition, seems to have viii been peculiarly and benevolently designed by nature, when she made them, like fire, expansible over all space, without lessening their density in any point, and like the air in which we breathe, move, and have our physical being, incapable of confinement or exclusive appropriation. Thomas Jefferson Letter to Isaac McPherson August 13, 1813 To the Instructor The first half of this text (through Chapter M) is a course in matrix algebra, though the foundation of some more advanced ideas is also being formed in these early sections (such as Theorem NMUS, which presages invertible linear transformations). Vectors are presented exclusively as column vectors (not transposes of row vectors), and linear combinations are presented very early. Spans, null spaces, column spaces and row spaces are also presented early, simply as sets, saving most of their vector space properties for later, so they are familiar objects before being scrutinized carefully. Youcannotdoeverythingearly,soinparticularmatrixmultiplicationcomeslater thanusual.However,withadefinitionbuiltonlinearcombinationsofcolumnvectors, it should seem more natural than the more frequent definition using dot products of rows with columns. And this delay emphasizes that linear algebra is built upon vector addition and scalar multiplication. Of course, matrix inverses must wait for matrixmultiplication,butthisdoesnotpreventnonsingularmatricesfromoccurring sooner. Vector space properties are hinted at when vector and matrix operations are first defined, but the notion of a vector space is saved for a more axiomatic treatment later (Chapter VS). Once bases and dimension have been explored in the context of vector spaces, linear transformations and their matrix representation follow.ThepredominantpurposeofthebookisthefoursectionsofChapterR,which introduces the student to representations of vectors and matrices, change-of-basis, and orthonormal diagonalization (the spectral theorem). This final chapter pulls together all the important ideas of the previous chapters. Our vector spaces use the complex numbers as the field of scalars. This avoids the fiction ofcomplexeigenvalues being usedto form scalarmultiples ofeigenvectors. The presence of the complex numbers in the earliest sections should not frighten students who need a review, since they will not be used heavily until much later, and Section CNO provides a quick review. Linearalgebraisanidealsubjectforthenovicemathematicsstudenttolearnhow todevelopasubjectprecisely,withalltherigormathematicsrequires.Unfortunately, much of this rigor seems to have escaped the standard calculus curriculum, so for many university students this is their first exposure to careful definitions and ix theorems,andtheexpectationthattheyfullyunderstandthem,tosaynothingofthe expectation that they become proficient in formulating their own proofs. We have tried to make this text as helpful as possible with this transition. Every definition is stated carefully, set apart from the text. Likewise, every theorem is carefully stated, and almost every one has a complete proof. Theorems usually have just one conclusion, so they can be referenced precisely later. Definitions and theorems are cataloged in order of their appearance (Definitions and Theorems in the Reference chapter at the end of the book). Along the way, there are discussions of some more important ideas relating to formulating proofs (Proof Techniques), which is partly advice and partly a primer on logic. Collecting responses to the Reading Questions prior to covering material in class will require students to learn how to read the material. Sections are designed to be covered in a fifty-minute lecture. Later sections are longer, but as students become more proficient at reading the text, it is possible to survey these longer sections at the same pace. With solutions to many of the exercises, students may be given the freedom to workhomeworkattheirown pace andstyle (individually,in groups,with an instructor’s help, etc.). To compensate and keep students from falling behind, I give an examination on each chapter. Sageisapowerfulopensourceprogramforadvancedmathematics.Itisespecially robustforlinearalgebra. Wehaveincludedanabundanceofmaterialwhichwillhelp the student (and instructor) learn how to use Sage for the study of linear algebra and how to understand linear algebra better with Sage. This material is tightly integrated with the web version of the book and will become even easier to use since the technology for interfaces to Sage continues to rapidly evolve. Sage is highly capable for mathematical research as well, and so should be a tool that students can use in subsequent courses and careers. Conclusion Linear algebra is a beautiful subject. I have enjoyed preparing this exposition and making it widely available. Much of my motivation for writing this book is captured by the sentiments expressed by H.M. Cundy and A.P. Rollet in their Preface to the First Edition of Mathematical Models (1952), especially the final sentence, This book was born in the classroom, and arose from the spontaneous interest of a Mathematical Sixth in the construction of simple models. A desire to show that even in mathematics one could have fun led to an exhibition of the results and attracted considerable attention throughout theschool.SincethentheSherbornecollectionhasgrown,ideashavecome from many sources, and widespread interest has been shown. It seems thereforedesirabletogivepermanentformtothelessonsofexperienceso that others can benefit by them and be encouraged to undertake similar work. x