A First Course in Linear Algebra by Robert A. Beezer Department of Mathematics and Computer Science University of Puget Sound Version 0.70 January 5, 2006 (cid:13)c 2004, 2005, 2006 Copyright (cid:13)c 2004, 2005, 2006 Robert A. Beezer. 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 the Invariant Sections being “Preface”, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled “GNU Free Documentation License”. Most recent version can be found at http://linear.ups.edu/. Preface This textbook is designed to teach the university mathematics student the basics of the subject of linear algebra. There are no prerequisites other than ordinary algebra, but it is probably best used by a student who has the “mathematical maturity” of a sophomore or junior. The text has two goals: to teach the fundamental concepts and techniques of matrix algebra and abstract vector spaces, and to teach the techniques associated with under- standing the definitions and theorems forming a coherent area of mathematics. So there is an emphasis on worked examples of nontrivial size and on proving theorems carefully. This book is copyrighted. This means that governments have granted the author a monopoly — the exclusive right to control the making of copies and derivative works for many years (too many years in some cases). It also gives others limited rights, generally referred to as “fair use,” such as the right to quote sections in a review without seeking permission. However, theauthorlicensesthisbooktoanyoneunderthetermsoftheGNU Free Documentation License (GFDL), which gives you more rights than most copyrights. Loosely speaking, you may make as many copies as you like at no cost, and you may distribute these unmodified copies if you please. You may modify the book for your own use. The catch is that if you make modifications and you distribute the modified version, or make use of portions in excess of fair use in another work, then you must also license the new work with the GFDL. So the book has lots of inherent freedom, and no one is allowed to distribute a derivative work that restricts these freedoms. (See the license itself for all the exact details of the additional rights you have been given.) Notice that initially most people are struck by the notion that this book is free (the French would say gratis, at no cost). And it is. However, it is more important that the book has freedom (the French would say libert´e, liberty). It will never go “out of print” nor will there ever be trivial updates designed only to frustrate the used book market. Thoseconsideringteachingacoursewiththisbookcanexamineitthoroughlyinadvance. Adding new exercises or new sections has been purposely made very easy, and the hope is that others will contribute these modifications back for incorporation into the book, for the benefit of all. Depending on how you received your copy, you may want to check for the latest version (and other news) at http://linear.ups.edu/. Topics The first half of this text (through Chapter M [219]) is basically a course in matrix algebra, though the foundation of some more advanced ideas is also being formed in these early sections. Vectors are presented exclusively as column vectors (since we also have the typographic freedom to avoid writing a column vector inline as the transpose of a row vector), and linear combinations are presented very early. Spans, null spaces and i ii column 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. You cannot do everything early, so in particular matrix multiplication comes later than usual. However, with a definition built on linear combinations of column vectors, it should seem more natural than the usual 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 matrix multiplication, but thisdoesnotpreventnonsingularmatricesfromoccurringsooner. Vectorspaceproperties 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. Once bases and dimension have been explored in the context of vector spaces, linear transformations and their matrix representations follow. The goal of the book is to go as far as canonical forms and matrix decompositions in the Core, with less central topics collected in a section of Topics. Linear algebra is an ideal subject for the novice mathematics student to learn how to develop a topic precisely, with all the rigor mathematics requires. 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 theorems, and the expectation that they fully understand them, to say nothing of the 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 in the front of the book, and alphabetical order in the index at the back. Along the way, there are discussions of some more important ideas relating to formulating proofs (Proof Techniques), which is advice mostly. Origin and History This book is the result of the confluence of several related events and trends. • At the University of Puget Sound we teach a one-semester, post-calculus linear algebra course to students majoring in mathematics, computer science, physics, chemistry and economics. Between January 1986 and June 2002, I taught this course seventeen times. For the Spring 2003 semester, I elected to convert my course notes to an electronic form so that it would be easier to incorporate the inevitable and nearly-constant revisions. Central to my new notes was a collection of stock examples that would be used repeatedly to illustrate new concepts. (These would become the Archetypes, Chapter A [685].) It was only a short leap to then decide to distribute copies of these notes and examples to the students in the two sections of this course. As the semester wore on, the notes began to look less like notes and more like a textbook. • I used the notes again in the Fall 2003 semester for a single section of the course. Simultaneously, the textbook I was using came out in a fifth edition. A new chapter Version0.70 iii was added toward the start of the book, and a few additional exercises were added in other chapters. This demanded the annoyance of reworking my notes and list of suggested exercises to conform with the changed numbering of the chapters and exercises. I had an almost identical experience with the third course I was teaching that semester. I also learned that in the next academic year I would be teaching a course where my textbook of choice had gone out of print. I felt there had to be a better alternative to having the organization of my courses buffeted by the economics of traditional textbook publishing. • I had used TEX and the Internet for many years, so there was little to stand in the way of typesetting, distributing and “marketing” a free book. With recreational andprofessionalinterestsinsoftwaredevelopment,Ihadlongbeenfascinatedbythe open-source software movement, as exemplified by the success of GNU and Linux, though public-domain TEX might also deserve mention. Obviously, this book is an attempt to carry over that model of creative endeavor to textbook publishing. • As a sabbatical project during the Spring 2004 semester, I embarked on the current project of creating a freely-distributable linear algebra textbook. (Notice the im- plied financial support of the University of Puget Sound to this project.) Most of the material was written from scratch since changes in notation and approach made much of my notes of little use. By August 2004 I had written half the material necessary for our Math 232 course. The remaining half was written during the Fall 2004 semester as I taught another two sections of Math 232. • I taught a single section of the course in the Spring 2005 semester, while my col- league, Professor Martin Jackson, graciously taught another section from the con- stantly shifting sands that was this project (version 0.30). His many suggestions have helped immeasurably. For the Fall 2005 semester, I taught two sections of the course from version 0.50. However, 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 Math- ematical 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 the school. Since then the Sherborne collection has grown, ideas have come from many sources, and widespread interest has been shown. It seems therefore desirable to give permanent form to the lessons of experience so that others can benefit by them and be encouraged to undertake similar work. How To Use This Book Chapters, Theorems, etc. are not numbered in this book, but are instead referenced by acronyms. This means that Theorem XYZ will always be Theorem XYZ, no matter if new sections are added, or if an individual decides to remove Version0.70 iv certain other sections. Within sections, the subsections are acronyms that begin with the acronym of the section. So Subsection XYZ.AB is the subsection AB in Section XYZ. Acronyms are unique within their type, so for example there is just one Definition B, but there is also a Section B. At first, all the letters flying around may be confusing, but with time, you will begin to recognize the more important ones on sight. Furthermore, there are lists of theorems, examples, etc. in the front of the book, and an index that contains every acronym. If you are reading this in an electronic version (PDF or XML), you will see that all of the cross-references are hyperlinks, allowing you to click to a definition or example, and then use the back button to return. In printed versions, you must rely on the page numbers. However, note that page numbers are not permanent! Different editions, different margins, or different sized paper will affect what content is on each page. And in time, the addition of new material will affect the page numbering. Chapter divisions are not critical to the organization of the book, as Sections are the main organizational unit. Sections are designed to be the subject of a single lecture or classroom session, though there is frequently more material than can be discussed and illustrated in a fifty-minute session. Consequently, the instructor will need to be selective about which topics to illustrate with other examples and which topics to leave to the student’s reading. Many of the examples are meant to be large, such as using five or six variables in a system of equations, so the instructor may just want to “walk” a class through these examples. The book has been written with the idea that some may work through it independently, so the hope is that students can learn some of the more mechanical ideas on their own. The highest level division of the book is the three Parts: Core, Topics, Applications. TheCoreismeanttocarefullydescribethebasicideasrequiredofafirstexposuretolinear algebra. In the final sections of the Core, one should ask the question: which previous Sections could be removed without destroying the logical development of the subject? Hopefully, the answer is “none.” The goal of the book is to finish the Core with the most general representations of linear transformations (Jordan and rational canonical forms) and perhaps matrix decompositions (LU, QR, singular value). Of course, there will not be universal agreement on what should, or should not, constitute the Core, but the main idea will be to limit it to about forty sections. Topics is meant to contain those subjects that are important in linear algebra, and which would make profitable detours from the Core for those interested in pursuing them. Applications should illustrate the power and widespread applicability of linear algebra to as many fields as possible. The Archetypes (ChapterA[685])covermanyofthecomputationalaspectsofsystemsoflinearequations, matrices and linear transformations. The student should consult them often, and this is encouraged by exercises that simply suggest the right properties to examine at the right time. But what is more important, they are a repository that contains enough variety to provide abundant examples of key theorems, while also providing counterexamples to hypotheses or converses of theorems. IrequiremystudentstoreadeachSectionpriortotheday’sdiscussiononthatsection. For some students this is a novel idea, but at the end of the semester a few always report on the benefits, both for this course and other courses where they have adopted the habit. To make good on this requirement, each section contains three Reading Questions. These sometimes only require parroting back a key definition or theorem, or they require Version0.70 v performing a small example of a key computation, or they ask for musings on key ideas or new relationships between old ideas. Answers are emailed to me the evening before the lecture. Given the flavor and purpose of these questions, including solutions seems foolish. Formulating interesting and effective exercises is as difficult, or more so, than building a narrative. But it is the place where a student really learns the material. As such, for thestudent’sbenefit, completesolutionsshouldbegiven. Asthelistofexercisesexpands, overtimesolutionswillalsobeprovided. Exercisesandtheirsolutionsarereferencedwith a section name, followed by a dot, then a letter (C,M, or T) and a number. The letter ‘C’ indicates a problem that is mostly computational in nature, while the letter ‘T’ indicates a problem that is more theoretical in nature. A problem with a letter ‘M’ is somewhere in between (middle, mid-level, median, middling), probably a mix of computation and applications of theorems. So Solution MO.T34 is a solution to an exercise in Section MO that is theoretical in nature. The number ‘34’ has no intrinsic meaning. More on Freedom This book is freely-distributable under the terms of the GFDL, along with the underlying TEX code from which the book is built. This arrangement provides many benefits unavailable with traditional texts. • No cost, or low cost, to students. With no physical vessel (i.e. paper, binding), no transportation costs (Internet bandwidth being a negligible cost) and no marketing costs(evaluationanddeskcopiesarefreetoall),anyonewithanInternetconnection canobtainit,andateachercouldmakeavailablepapercopiesinsufficientquantities for a class. The cost to print a copy is not insignificant, but is just a fraction of the cost of a traditional textbook. Students will not feel the need to sell back their book, and in future years can even pick up a newer edition freely. • The book will not go out of print. No matter what, a teacher can maintain their own copy and use the book for as many years as they desire. Further, the naming schemes for chapters, sections, theorems, etc. is designed so that the addition of new material will not break any course syllabi or assignment list. • With many eyes reading the book and with frequent postings of updates, the relia- bility should become very high. Please report any errors you find that persist into the latest version. • For those with a working installation of the popular typesetting program TEX, the bookhasbeendesignedsothatitcanbecustomized. Pagelayouts,presenceofexer- cises, solutions, sectionsorchapterscanallbeeasilycontrolled. Furthermore, many variants of mathematical notation are achieved via TEX macros. So by changing a single macro, one’s favorite notation can be reflected throughout the text. For ex- ample, every transpose of a matrix is coded in the source as \transpose{A}, which when printed will yield At. However by changing the definition of \transpose{ }, any desired alternative notation will then appear throughout the text instead. • The book has also been designed to make it easy for others to contribute material. Would you like to see a section on symmetric bilinear forms? Consider writing Version0.70 vi one and contributing it to one of the Topics chapters. Does there need to be more exercises about the null space of a matrix? Send me some. Historical Notes? Contact me, and we will see about adding those in also. • You have no legal obligation to pay for this book. It has been licensed with no expectation that you pay for it. You do not even have a moral obligation to pay for the book. Thomas Jefferson (1743 – 1826), the author of the United States Declaration of Independence, wrote, If nature has made any one thing less susceptible than all others of exclu- sive property, it is the action of the thinking power called an idea, which anindividualmayexclusivelypossessaslongashekeepsittohimself; 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 him- self 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 been peculiarly and benev- olently 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. Letter to Isaac McPherson August 13, 1813 However, if you feel a royalty is due the author, or if you would like to encourage the author, or if you wish to show others that this approach to textbook publishing can also bring financial gains, then donations are gratefully received. Moreover, non-financial forms of help can often be even more valuable. A simple note of encouragement, submitting a report of an error, or contributing some exercises or perhaps an entire section for the Topics or Applications chapters are all important ways you can acknowledge the freedoms accorded to this work by the copyright holder and other contributors. Conclusion Foremost, I hope that students find their time spent with this book prof- itable. I hope that instructors find it flexible enough to fit the needs of their course. And I hope that everyone will send me their comments and suggestions, and also consider the myriad ways they can help (as listed on the book’s website at linear.ups.edu). Robert A. Beezer Tacoma, Washington January, 2006 Version0.70 Contents Preface i Contents vii Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv Proof Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Computation Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi GNU Free Documentation License . . . . . . . . . . . . . . . . . . . . . . . . . xxiii 1. APPLICABILITY AND DEFINITIONS . . . . . . . . . . . . . . . . . xxiii 2. VERBATIM COPYING . . . . . . . . . . . . . . . . . . . . . . . . . . xxv 3. COPYING IN QUANTITY . . . . . . . . . . . . . . . . . . . . . . . . xxv 4. MODIFICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv 5. COMBINING DOCUMENTS . . . . . . . . . . . . . . . . . . . . . . . xxvii 6. COLLECTIONS OF DOCUMENTS . . . . . . . . . . . . . . . . . . . xxviii 7. AGGREGATION WITH INDEPENDENT WORKS . . . . . . . . . . xxviii 8. TRANSLATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxviii 9. TERMINATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxix 10. FUTURE REVISIONS OF THIS LICENSE . . . . . . . . . . . . . . xxix ADDENDUM: How to use this License for your documents . . . . . . . . xxix Part C Core 3 Chapter SLE Systems of Linear Equations 3 WILA What is Linear Algebra? . . . . . . . . . . . . . . . . . . . . . . . . . . 3 LA “Linear” + “Algebra” . . . . . . . . . . . . . . . . . . . . . . . . . . 3 A An application: packaging trail mix . . . . . . . . . . . . . . . . . . . . 4 READ Reading Questions . . . . . . . . . . . . . . . . . . . . . . . . . . 8 EXC Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 SOL Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 SSLE Solving Systems of Linear Equations . . . . . . . . . . . . . . . . . . . . 15 PSS Possibilities for solution sets . . . . . . . . . . . . . . . . . . . . . . 17 vii viii Contents ESEO Equivalent systems and equation operations . . . . . . . . . . . . 18 READ Reading Questions . . . . . . . . . . . . . . . . . . . . . . . . . . 27 EXC Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 SOL Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 RREF Reduced Row-Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . 33 READ Reading Questions . . . . . . . . . . . . . . . . . . . . . . . . . . 46 EXC Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 SOL Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 TSS Types of Solution Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 READ Reading Questions . . . . . . . . . . . . . . . . . . . . . . . . . . 65 EXC Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 SOL Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 HSE Homogeneous Systems of Equations . . . . . . . . . . . . . . . . . . . . . 71 SHS Solutions of Homogeneous Systems . . . . . . . . . . . . . . . . . . 71 MVNSE Matrix and Vector Notation for Systems of Equations . . . . . . 74 NSM Null Space of a Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 77 READ Reading Questions . . . . . . . . . . . . . . . . . . . . . . . . . . 79 EXC Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 SOL Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 NSM NonSingular Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 NSM NonSingular Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 85 READ Reading Questions . . . . . . . . . . . . . . . . . . . . . . . . . . 93 EXC Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 SOL Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Chapter V Vectors 99 VO Vector Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 VEASM Vector equality, addition, scalar multiplication . . . . . . . . . . 100 VSP Vector Space Properties . . . . . . . . . . . . . . . . . . . . . . . . 104 READ Reading Questions . . . . . . . . . . . . . . . . . . . . . . . . . . 106 EXC Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 SOL Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 LC Linear Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 LC Linear Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 VFSS Vector Form of Solution Sets . . . . . . . . . . . . . . . . . . . . . 116 PSHS Particular Solutions, Homogeneous Solutions . . . . . . . . . . . . 129 URREF Uniqueness of Reduced Row-Echelon Form . . . . . . . . . . . . 131 READ Reading Questions . . . . . . . . . . . . . . . . . . . . . . . . . . 134 EXC Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 SOL Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 SS Spanning Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 SSV Span of a Set of Vectors . . . . . . . . . . . . . . . . . . . . . . . . . 141 SSNS Spanning Sets of Null Spaces . . . . . . . . . . . . . . . . . . . . . 147 READ Reading Questions . . . . . . . . . . . . . . . . . . . . . . . . . . 153 EXC Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 Version0.70