Main
Elementary Linear Algebra, Applications Version
Elementary Linear Algebra, Applications Version
Howard Anton, Chris Rorres
Elementary Linear Algebra 11th edition gives an elementary treatment of linear algebra that is suitable for a first course for undergraduate students. The aim is to present the fundamentals of linear algebra in the clearest possible way; pedagogy is the main consideration. Calculus is not a prerequisite, but there are clearly labeled exercises and examples (which can be omitted without loss of continuity) for students who have studied calculus.
Categories:
Mathematics\\Algebra: Linear Algebra
Year:
2013
Edition:
11
Publisher:
Wiley
Language:
english
Pages:
802
ISBN 10:
1118474228
ISBN 13:
9781118474228
File:
PDF, 8.08 MB
Download (pdf, 8.08 MB)
Preview
 Open in Browser
 Checking other formats...
 Please login to your account first

Need help? Please read our short guide how to send a book to Kindle.
The file will be sent to your email address. It may take up to 15 minutes before you receive it.
The file will be sent to your Kindle account. It may takes up to 15 minutes before you received it.
Please note you need to add our NEW email km@bookmail.org to approved email addresses. Read more.
Please note you need to add our NEW email km@bookmail.org to approved email addresses. Read more.
You may be interested in
Most frequently terms
matrix^{2882}
vector^{1721}
vectors^{1460}
linear^{1379}
theorem^{1046}
matrices^{931}
equation^{696}
exercises^{596}
orthogonal^{590}
equations^{525}
cos^{466}
det^{460}
invertible^{353}
formula^{349}
eigenvalues^{347}
corresponding^{344}
entries^{337}
spaces^{300}
vector space^{289}
linear system^{288}
multiplication^{264}
coordinate^{248}
axis^{239}
eigenvalue^{235}
diagonal^{232}
scalar^{227}
solutions^{221}
transformations^{220}
operator^{219}
linearly independent^{211}
symmetric^{205}
euclidean^{202}
applications^{198}
linear algebra^{190}
decomposition^{189}
nonzero^{189}
triangular^{179}
a11^{178}
vector spaces^{178}
subspace^{176}
verify^{175}
dimensional^{175}
eigenvectors^{174}
a22^{170}
determinant^{165}
rotation^{165}
polynomial^{164}
least squares^{162}
compute^{160}
row echelon^{160}
elementary^{159}
quadratic^{156}
properties^{156}
orthonormal^{155}
inverse^{150}
a12^{150}
column vectors^{148}
dimension^{147}
echelon form^{147}
eigenvector^{144}
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
1

2

WileyPLUS is a researchbased online environment for effective teaching and learning. WileyPLUS builds students’ confidence because it takes the guesswork out of studying by providing students with a clear roadmap: • • • what to do how to do it if they did it right It offers interactive resources along with a complete digital textbook that help students learn more. With WileyPLUS, students take more initiative so you’ll have greater impact on their achievement in the classroom and beyond. Now available for For more information, visit www.wileyplus.com ALL THE HELP, RESOURCES, AND PERSONAL SUPPORT YOU AND YOUR STUDENTS NEED! www.wileyplus.com/resources Student Partner Program 2Minute Tutorials and all of the resources you and your students need to get started Student support from an experienced student user Collaborate with your colleagues, find a mentor, attend virtual and live events, and view resources www.WhereFacultyConnect.com Quick Start Preloaded, readytouse assignments and presentations created by subject matter experts Technical Support 24/7 FAQs, online chat, and phone support www.wileyplus.com/support © Courtney Keating/iStockphoto Your WileyPLUS Account Manager, providing personal training and support 11 T H EDITION Elementary Linear Algebra Applications Version H OWA R D A NT O N Professor Emeritus, Drexel University C H R I S R O R R E S University of Pennsylvania VICE PRESIDENT AND PUBLISHER SENIOR ACQUISITIONS EDITOR ASSOCIATE CONTENT EDITOR FREELANCE DEVELOPMENT EDITOR MARKETING MANAGER EDITORIAL ASSISTANT SENIOR PRODUCT DESIGNER SENIOR PRODUCTION EDITOR SENIOR CONTENT MANAGER OPERATIONS MANAGER SENIOR DESIGNER MEDIA SPECIALIST PHOTO RESEARCH EDITOR COPY EDITOR PRODUCTION SERVICES COVER ART Laurie Rosatone David Dietz Jacqueline Sinacori Anne ScanlanRohrer Melanie Kurkjian Michael O’Neal Thomas Kulesa Ken Santor Karoline Luciano Melissa Edwards Maddy Lesure Laura Abrams Felicia Ruocco Lilian Brady Carol Sawyer/The Perfect Proof Norm Christiansen This book was set in Times New Roman STD by Techsetters, Inc. and printed and bound by Quad Graphics/Versailles. The cover was printed by Quad Graphics/Versailles. This book is printed on acidfree paper. Copyright 2014, 2010, 2005, 2000, 1994, 1991, 1987, 1984, 1981, 1977, 1973 by Anton Textbooks, Inc. All rights reserved. Published simultaneously in Canada. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate percopy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, website www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 070305774, (201) 7486011, fax (201) 7486008, website www.wiley.com/go/permissions. Best efforts have been made to determine whether the images of mathematicians shown in the text are in the public domain or properly licensed. If you believe that an error has been made, please contact the Permissions Department. Evaluation copies are provided to qualiﬁed academics and professionals for review purposes only, for use in their courses during the next academic year. These copies are licensed and may not be sold or transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions and a free of charge return shipping label are available at www.wiley.com/go/returnlabel. Outside of the United States, please contact your local representative. Library of Congress CataloginginPublication Data Anton, Howard, author. Elementary linear algebra : applications version / Howard Anton, Chris Rorres.  11th edition. pages cm Includes index. ISBN 9781118434413 (cloth) 1. Algebras, LinearTextbooks. I. Rorres, Chris, author. II. Title. QA184.2.A58 2013 512'.5dc23 2013033542 ISBN 9781118434413 ISBN BinderReady Version 9781118474228 Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 ABOUT THE AUTHOR Howard Anton obtained his B.A. from Lehigh University, his M.A. from the University of Illinois, and his Ph.D. from the Polytechnic University of Brooklyn, all in mathematics. In the early 1960s he worked for Burroughs Corporation and Avco Corporation at Cape Canaveral, Florida, where he was involved with the manned space program. In 1968 he joined the Mathematics Department at Drexel University, where he taught full time until 1983. Since then he has devoted the majority of his time to textbook writing and activities for mathematical associations. Dr. Anton was president of the EPADEL Section of the Mathematical Association of America (MAA), served on the Board of Governors of that organization, and guided the creation of the Student Chapters of the MAA. In addition to various pedagogical articles, he has published numerous research papers in functional analysis, approximation theory, and topology. He is best known for his textbooks in mathematics, which are among the most widely used in the world. There are currently more than 175 versions of his books, including translations into Spanish, Arabic, Portuguese, Italian, Indonesian, French, Japanese, Chinese, Hebrew, and German. For relaxation, Dr. Anton enjoys travel and photography. Chris Rorres earned his B.S. degree from Drexel University and his Ph.D. from the Courant Institute of New York University. He was a faculty member of the Department of Mathematics at Drexel University for more than 30 years where, in addition to teaching, he did applied research in solar engineering, acoustic scattering, population dynamics, computer system reliability, geometry of archaeological sites, optimal animal harvesting policies, and decision theory. He retired from Drexel in 2001 as a Professor Emeritus of Mathematics and is now a mathematical consultant. He also has a research position at the School of Veterinary Medicine at the University of Pennsylvania where he does mathematical modeling of animal epidemics. Dr. Rorres is a recognized expert on the life and work of Archimedes and has appeared in various television documentaries on that subject. His highly acclaimed website on Archimedes (http://www.math.nyu.edu/~crorres/Archimedes/contents.html) is a virtual book that has become an important teaching tool in mathematical history for students around the world. To: My wife, Pat My children, Brian, David, and Lauren My parents, Shirley and Benjamin My benefactor, Stephen Girard (1750–1831), whose philanthropy changed my life Howard Anton To: Billie Chris Rorres PREFACE Summary of Changes in This Edition vi This textbook is an expanded version of Elementary Linear Algebra, eleventh edition, by Howard Anton. The ﬁrst nine chapters of this book are identical to the ﬁrst nine chapters of that text; the tenth chapter consists of twenty applications of linear algebra drawn from business, economics, engineering, physics, computer science, approximation theory, ecology, demography, and genetics. The applications are largely independent of each other, and each includes a list of mathematical prerequisites. Thus, each instructor has the ﬂexibility to choose those applications that are suitable for his or her students and to incorporate each application anywhere in the course after the mathematical prerequisites have been satisﬁed. Chapters 1–9 include simpler treatments of some of the applications covered in more depth in Chapter 10. This edition gives an introductory treatment of linear algebra that is suitable for a ﬁrst undergraduate course. Its aim is to present the fundamentals of linear algebra in the clearest possible way—sound pedagogy is the main consideration. Although calculus is not a prerequisite, there is some optional material that is clearly marked for students with a calculus background. If desired, that material can be omitted without loss of continuity. Technology is not required to use this text, but for instructors who would like to use MATLAB, Mathematica, Maple, or calculators with linear algebra capabilities, we have posted some supporting material that can be accessed at either of the following companion websites: www.howardanton.com www.wiley.com/college/anton Many parts of the text have been revised based on an extensive set of reviews. Here are the primary changes: • Earlier Linear Transformations Linear transformations are introduced earlier (starting in Section 1.8). Many exercise sets, as well as parts of Chapters 4 and 8, have been revised in keeping with the earlier introduction of linear transformations. • New Exercises Hundreds of new exercises of all types have been added throughout the text. • Technology Exercises requiring technology such as MATLAB, Mathematica, or Maple have been added and supporting data sets have been posted on the companion websites for this text. The use of technology is not essential, and these exercises can be omitted without affecting the ﬂow of the text. • Exercise Sets Reorganized Many multiplepart exercises have been subdivided to create a better balance between odd and even exercise types. To simplify the instructor’s task of creating assignments, exercise sets have been arranged in clearly deﬁned categories. • Reorganization In addition to the earlier introduction of linear transformations, the old Section 4.12 on Dynamical Systems and Markov Chains has been moved to Chapter 5 in order to incorporate material on eigenvalues and eigenvectors. • Rewriting Section 9.3 on Internet Search Engines from the previous edition has been rewritten to reﬂect more accurately how the Google PageRank algorithm works in practice. That section is now Section 10.20 of the applications version of this text. • Appendix A Rewritten The appendix on reading and writing proofs has been expanded and revised to better support courses that focus on proving theorems. • Web Materials Supplementary web materials now include various applications modules, three modules on linear programming, and an alternative presentation of determinants based on permutations. • Applications Chapter Section 10.2 of the previous edition has been moved to the websites that accompany this text, so it is now part of a threemodule set on Linear Preface vii Programming. A new section on Internet search engines has been added that explains the PageRank algorithm used by Google. Hallmark Features • Relationships Among Concepts One of our main pedagogical goals is to convey to the student that linear algebra is a cohesive subject and not simply a collection of isolated deﬁnitions and techniques. One way in which we do this is by using a crescendo of Equivalent Statements theorems that continually revisit relationships among systems of equations, matrices, determinants, vectors, linear transformations, and eigenvalues. To get a general sense of how we use this technique see Theorems 1.5.3, 1.6.4, 2.3.8, 4.8.8, and then Theorem 5.1.5, for example. • Smooth Transition to Abstraction Because the transition from R n to general vector spaces is difﬁcult for many students, considerable effort is devoted to explaining the purpose of abstraction and helping the student to “visualize” abstract ideas by drawing analogies to familiar geometric ideas. • Mathematical Precision When reasonable, we try to be mathematically precise. In keeping with the level of student audience, proofs are presented in a patient style that is tailored for beginners. • Suitability for a Diverse Audience This text is designed to serve the needs of students in engineering, computer science, biology, physics, business, and economics as well as those majoring in mathematics. • Historical Notes To give the students a sense of mathematical history and to convey that real people created the mathematical theorems and equations they are studying, we have included numerous Historical Notes that put the topic being studied in historical perspective. About the Exercises • Graded Exercise Sets Each exercise set in the ﬁrst nine chapters begins with routine drill problems and progresses to problems with more substance. These are followed by three categories of exercises, the ﬁrst focusing on proofs, the second on true/false exercises, and the third on problems requiring technology. This compartmentalization is designed to simplify the instructor’s task of selecting exercises for homework. • Proof Exercises Linear algebra courses vary widely in their emphasis on proofs, so exercises involving proofs have been grouped and compartmentalized for easy identiﬁcation. Appendix A has been rewritten to provide students more guidance on proving theorems. • True/False Exercises The True/False exercises are designed to check conceptual understanding and logical reasoning. To avoid pure guesswork, the students are required to justify their responses in some way. • Technology Exercises Exercises that require technology have also been grouped. To avoid burdening the student with keyboarding, the relevant data ﬁles have been posted on the websites that accompany this text. • Supplementary Exercises Each of the ﬁrst nine chapters ends with a set of supplementary exercises that draw on all topics in the chapter. These tend to be more challenging. Supplementary Materials for Students • Student Solutions Manual This supplement provides detailed solutions to most oddnumbered exercises (ISBN 9781118464427). • Data Files Data ﬁles for the technology exercises are posted on the companion websites that accompany this text. • MATLAB Manual and Linear Algebra Labs This supplement contains a set of MATLAB laboratory projects written by Dan Seth of West Texas A&M University. It is designed to help students learn key linear algebra concepts by using MATLAB and is available in PDF form without charge to students at schools adopting the 11th edition of the text. • Videos A complete set of Daniel Solow’s How to Read and Do Proofs videos is available to students through WileyPLUS as well as the companion websites that accompany viii Preface this text. Those materials include a guide to help students locate the lecture videos appropriate for speciﬁc proofs in the text. Supplementary Materials for Instructors • Instructor’s Solutions Manual This supplement provides workedout solutions to most exercises in the text (ISBN 9781118434482). • PowerPoint Presentations PowerPoint slides are provided that display important definitions, examples, graphics, and theorems in the book. These can also be distributed to students as review materials or to simplify note taking. • Test Bank Test questions and sample exams are available in PDF or LATEX form. • WileyPLUS An online environment for effective teaching and learning. WileyPLUS builds student conﬁdence by taking the guesswork out of studying and by providing a clear roadmap of what to do, how to do it, and whether it was done right. Its purpose is to motivate and foster initiative so instructors can have a greater impact on classroom achievement and beyond. A Guide for the Instructor Although linear algebra courses vary widely in content and philosophy, most courses fall into two categories—those with about 40 lectures and those with about 30 lectures. Accordingly, we have created long and short templates as possible starting points for constructing a course outline. Of course, these are just guides, and you will certainly want to customize them to ﬁt your local interests and requirements. Neither of these sample templates includes applications or the numerical methods in Chapter 9. Those can be added, if desired, and as time permits. Long Template Chapter 1: Systems of Linear Equations and Matrices 8 lectures 6 lectures Chapter 2: Determinants 3 lectures 2 lectures Chapter 3: Euclidean Vector Spaces 4 lectures 3 lectures 10 lectures 9 lectures Chapter 5: Eigenvalues and Eigenvectors 3 lectures 3 lectures Chapter 6: Inner Product Spaces 3 lectures 1 lecture Chapter 7: Diagonalization and Quadratic Forms 4 lectures 3 lectures Chapter 8: General Linear Transformations 4 lectures 3 lectures 39 lectures 30 lectures Chapter 4: General Vector Spaces Total: Reviewers Short Template The following people reviewed the plans for this edition, critiqued much of the content, and provided me with insightful pedagogical advice: John Alongi, Northwestern University Jiu Ding, University of Southern Mississippi Eugene Don, City University of New York at Queens John Gilbert, University of Texas Austin Danrun Huang, St. Cloud State University Craig Jensen, University of New Orleans Steve Kahan, City University of New York at Queens Harihar Khanal, EmbryRiddle Aeronautical University Firooz Khosraviyani, Texas A&M International University Y. George Lai, Wilfred Laurier University Kouok Law, Georgia Perimeter College Mark MacLean, Seattle University Preface ix Vasileios Maroulas, University of Tennessee, Knoxville Daniel Reynolds, Southern Methodist University Qin Sheng, Baylor University Laura Smithies, Kent State University Larry Susanka, Bellevue College Cristina Tone, University of Louisville Yvonne Yaz, Milwaukee School of Engineering Ruhan Zhao, State University of New York at Brockport Exercise Contributions Special thanks are due to three talented people who worked on various aspects of the exercises: Przemyslaw Bogacki, Old Dominion University – who solved the exercises and created the solutions manuals. Roger Lipsett, Brandeis University – who proofread the manuscript and exercise solutions for mathematical accuracy. Daniel Solow, Case Western Reserve University – author of “How to Read and Do Proofs,” for providing videos on techniques of proof and a key to using those videos in coordination with this text. Sky Pelletier Waterpeace – who critiqued the technology exercises, suggested improvements, and provided the data sets. Special Contributions I would also like to express my deep appreciation to the following people with whom I worked on a daily basis: Anton Kaul – who worked closely with me at every stage of the project and helped to write some new text material and exercises. On the many occasions that I needed mathematical or pedagogical advice, he was the person I turned to. I cannot thank him enough for his guidance and the many contributions he has made to this edition. David Dietz – my editor, for his patience, sound judgment, and dedication to producing a quality book. Anne ScanlanRohrer – of Two Ravens Editorial, who coordinated the entire project and brought all of the pieces together. Jacqueline Sinacori – who managed many aspects of the content and was always there to answer my often obscure questions. Carol Sawyer – of The Perfect Proof, who managed the myriad of details in the production process and helped with proofreading. Maddy Lesure – with whom I have worked for many years and whose elegant sense of design is apparent in the pages of this book. Lilian Brady – my copy editor for almost 25 years. I feel fortunate to have been the beneﬁciary of her remarkable knowledge of typography, style, grammar, and mathematics. Pat Anton – of Anton Textbooks, Inc., who helped with the mundane chores duplicating, shipping, accuracy checking, and tasks too numerous to mention. John Rogosich – of Techsetters, Inc., who programmed the design, managed the composition, and resolved many difﬁcult technical issues. Brian Haughwout – of Techsetters, Inc., for his careful and accurate work on the illustrations. Josh Elkan – for providing valuable assistance in accuracy checking. Howard Anton Chris Rorres CONTENTS C HA PT E R 1 Systems of Linear Equations and Matrices 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 Introduction to Systems of Linear Equations 2 Gaussian Elimination 11 Matrices and Matrix Operations 25 Inverses; Algebraic Properties of Matrices 39 Elementary Matrices and a Method for Finding A−1 More on Linear Systems and Invertible Matrices 61 Diagonal, Triangular, and Symmetric Matrices 67 Matrix Transformations 75 Applications of Linear Systems 84 • Network Analysis (Trafﬁc Flow) 84 • Electrical Circuits 86 • Balancing Chemical Equations 88 • Polynomial Interpolation 91 1.10 Application: Leontief InputOutput Models 96 C HA PT E R 2 Determinants 52 105 2.1 Determinants by Cofactor Expansion 105 2.2 Evaluating Determinants by Row Reduction 113 2.3 Properties of Determinants; Cramer’s Rule 118 C HA PT E R 3 Euclidean Vector Spaces 3.1 3.2 3.3 3.4 3.5 C HA PT E R 4 131 Vectors in 2Space, 3Space, and nSpace Norm, Dot Product, and Distance in Rn Orthogonality 155 The Geometry of Linear Systems 164 Cross Product 172 General Vector Spaces 131 142 183 4.1 Real Vector Spaces 183 4.2 Subspaces 191 4.3 Linear Independence 202 4.4 Coordinates and Basis 212 4.5 Dimension 221 4.6 Change of Basis 229 4.7 Row Space, Column Space, and Null Space 237 4.8 Rank, Nullity, and the Fundamental Matrix Spaces 4.9 Basic Matrix Transformations in R2 and R3 259 4.10 Properties of Matrix Transformations 270 4.11 Application: Geometry of Matrix Operators on R2 x 248 280 1 Contents C HA PT E R 5 Eigenvalues and Eigenvectors 5.1 5.2 5.3 5.4 5.5 C HA PT E R 6 C HA PT E R 7 8 C HA PT E R 9 10 Orthogonal Matrices 401 Orthogonal Diagonalization 409 Quadratic Forms 417 Optimization Using Quadratic Forms 429 Hermitian, Unitary, and Normal Matrices 387 401 437 447 General Linear Transformations 447 Compositions and Inverse Transformations 458 Isomorphism 466 Matrices for General Linear Transformations 472 Similarity 481 Numerical Methods 9.1 9.2 9.3 9.4 9.5 C HA PT E R Inner Products 345 Angle and Orthogonality in Inner Product Spaces 355 Gram–Schmidt Process; QRDecomposition 364 Best Approximation; Least Squares 378 Application: Mathematical Modeling Using Least Squares Application: Function Approximation; Fourier Series 394 General Linear Transformations 8.1 8.2 8.3 8.4 8.5 332 345 Diagonalization and Quadratic Forms 7.1 7.2 7.3 7.4 7.5 C HA PT E R Eigenvalues and Eigenvectors 291 Diagonalization 302 Complex Vector Spaces 313 Application: Differential Equations 326 Application: Dynamical Systems and Markov Chains Inner Product Spaces 6.1 6.2 6.3 6.4 6.5 6.6 291 491 LUDecompositions 491 The Power Method 501 Comparison of Procedures for Solving Linear Systems 509 Singular Value Decomposition 514 Application: Data Compression Using Singular Value Decomposition Applications of Linear Algebra 527 10.1 Constructing Curves and Surfaces Through Speciﬁed Points 10.2 The Earliest Applications of Linear Algebra 533 10.3 Cubic Spline Interpolation 540 528 521 xi xii Contents 10.4 Markov Chains 551 10.5 Graph Theory 561 10.6 Games of Strategy 570 10.7 Leontief Economic Models 579 10.8 Forest Management 588 10.9 Computer Graphics 595 10.10 Equilibrium Temperature Distributions 603 10.11 Computed Tomography 613 10.12 Fractals 624 10.13 Chaos 639 10.14 Cryptography 652 10.15 Genetics 663 10.16 AgeSpeciﬁc Population Growth 673 10.17 Harvesting of Animal Populations 683 10.18 A Least Squares Model for Human Hearing 10.19 Warps and Morphs 697 10.20 Internet Search Engines 706 APPENDIX A Working with Proofs APPENDIX B Complex Numbers A1 A5 Answers to Exercises Index I1 A13 691 CHAPTER 1 Systems of Linear Equations and Matrices CHAPTER CONTENTS 1.1 Introduction to Systems of Linear Equations 1.2 Gaussian Elimination 1.3 Matrices and Matrix Operations 1.4 Inverses; Algebraic Properties of Matrices 1.5 Elementary Matrices and a Method for Finding A−1 1.6 More on Linear Systems and Invertible Matrices 1.7 Diagonal,Triangular, and Symmetric Matrices 11 1.8 MatrixTransformations 1.9 Applications of Linear Systems • • • • 25 39 52 61 67 75 84 Network Analysis (Trafﬁc Flow) 84 Electrical Circuits 86 Balancing Chemical Equations 88 Polynomial Interpolation 91 1.10 Leontief InputOutput Models INTRODUCTION 2 96 Information in science, business, and mathematics is often organized into rows and columns to form rectangular arrays called “matrices” (plural of “matrix”). Matrices often appear as tables of numerical data that arise from physical observations, but they occur in various mathematical contexts as well. For example, we will see in this chapter that all of the information required to solve a system of equations such as 5x + y = 3 2x − y = 4 is embodied in the matrix 5 1 2 −1 3 4 and that the solution of the system can be obtained by performing appropriate operations on this matrix. This is particularly important in developing computer programs for solving systems of equations because computers are well suited for manipulating arrays of numerical information. However, matrices are not simply a notational tool for solving systems of equations; they can be viewed as mathematical objects in their own right, and there is a rich and important theory associated with them that has a multitude of practical applications. It is the study of matrices and related topics that forms the mathematical ﬁeld that we call “linear algebra.” In this chapter we will begin our study of matrices. 1 2 Chapter 1 Systems of Linear Equations and Matrices 1.1 Introduction to Systems of Linear Equations Systems of linear equations and their solutions constitute one of the major topics that we will study in this course. In this ﬁrst section we will introduce some basic terminology and discuss a method for solving such systems. Linear Equations Recall that in two dimensions a line in a rectangular xy coordinate system can be represented by an equation of the form ax + by = c (a, b not both 0) and in three dimensions a plane in a rectangular xyzcoordinate system can be represented by an equation of the form ax + by + cz = d (a, b, c not all 0) These are examples of “linear equations,” the ﬁrst being a linear equation in the variables x and y and the second a linear equation in the variables x , y , and z. More generally, we deﬁne a linear equation in the n variables x1 , x2 , . . . , xn to be one that can be expressed in the form a1 x1 + a2 x2 + · · · + an xn = b (1) where a1 , a2 , . . . , an and b are constants, and the a ’s are not all zero. In the special cases where n = 2 or n = 3, we will often use variables without subscripts and write linear equations as a1 x + a2 y = b (a1 , a2 not both 0) a1 x + a2 y + a3 z = b (a1 , a2 , a3 not all 0) (2) (3) In the special case where b = 0, Equation (1) has the form a1 x1 + a2 x2 + · · · + an xn = 0 (4) which is called a homogeneous linear equation in the variables x1 , x2 , . . . , xn . E X A M P L E 1 Linear Equations Observe that a linear equation does not involve any products or roots of variables. All variables occur only to the ﬁrst power and do not appear, for example, as arguments of trigonometric, logarithmic, or exponential functions. The following are linear equations: x + 3y = 7 1 x − y + 3z = −1 2 x1 − 2x2 − 3x3 + x4 = 0 x1 + x2 + · · · + xn = 1 The following are not linear equations: x + 3y 2 = 4 sin x + y = 0 3x + 2y − xy = 5 √ x1 + 2x2 + x3 = 1 A ﬁnite set of linear equations is called a system of linear equations or, more brieﬂy, a linear system. The variables are called unknowns. For example, system (5) that follows has unknowns x and y , and system (6) has unknowns x1 , x2 , and x3 . 5x + y = 3 2x − y = 4 4x1 − x2 + 3x3 = −1 3x1 + x2 + 9x3 = −4 (5–6) 1.1 Introduction to Systems of Linear Equations The double subscripting on the coefﬁcients aij of the unknowns gives their location in the system—the ﬁrst subscript indicates the equation in which the coefﬁcient occurs, and the second indicates which unknown it multiplies. Thus, a12 is in the ﬁrst equation and multiplies x2 . 3 A general linear system of m equations in the n unknowns x1 , x2 , . . . , xn can be written as a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. .. .. .. . . . . am1 x1 + am2 x2 + · · · + amn xn = bm (7) A solution of a linear system in n unknowns x1 , x2 , . . . , xn is a sequence of n numbers s1 , s2 , . . . , sn for which the substitution x1 = s1 , x2 = s2 , . . . , xn = sn makes each equation a true statement. For example, the system in (5) has the solution x = 1, y = −2 and the system in (6) has the solution x1 = 1, x2 = 2, x3 = −1 These solutions can be written more succinctly as (1, −2) and (1, 2, −1) in which the names of the variables are omitted. This notation allows us to interpret these solutions geometrically as points in twodimensional and threedimensional space. More generally, a solution x1 = s1 , x2 = s2 , . . . , xn = sn of a linear system in n unknowns can be written as (s1 , s2 , . . . , sn ) which is called an ordered ntuple. With this notation it is understood that all variables appear in the same order in each equation. If n = 2, then the ntuple is called an ordered pair, and if n = 3, then it is called an ordered triple. Linear Systems inTwo and Three Unknowns Linear systems in two unknowns arise in connection with intersections of lines. For example, consider the linear system a1 x + b1 y = c1 a2 x + b2 y = c2 in which the graphs of the equations are lines in the xyplane. Each solution (x, y) of this system corresponds to a point of intersection of the lines, so there are three possibilities (Figure 1.1.1): 1. The lines may be parallel and distinct, in which case there is no intersection and consequently no solution. 2. The lines may intersect at only one point, in which case the system has exactly one solution. 3. The lines may coincide, in which case there are inﬁnitely many points of intersection (the points on the common line) and consequently inﬁnitely many solutions. In general, we say that a linear system is consistent if it has at least one solution and inconsistent if it has no solutions. Thus, a consistent linear systemof two equations in 4 Chapter 1 Systems of Linear Equations and Matrices y y y One solution No solution x x x Figure 1.1.1 Infinitely many solutions (coincident lines) two unknowns has either one solution or inﬁnitely many solutions—there are no other possibilities. The same is true for a linear system of three equations in three unknowns a1 x + b1 y + c1 z = d1 a2 x + b2 y + c2 z = d2 a3 x + b3 y + c3 z = d3 in which the graphs of the equations are planes. The solutions of the system, if any, correspond to points where all three planes intersect, so again we see that there are only three possibilities—no solutions, one solution, or inﬁnitely many solutions (Figure 1.1.2). No solutions (three parallel planes; no common intersection) No solutions (two parallel planes; no common intersection) No solutions (no common intersection) No solutions (two coincident planes parallel to the third; no common intersection) One solution (intersection is a point) Infinitely many solutions (intersection is a line) Infinitely many solutions (planes are all coincident; intersection is a plane) Infinitely many solutions (two coincident planes; intersection is a line) Figure 1.1.2 We will prove later that our observations about the number of solutions of linear systems of two equations in two unknowns and linear systems of three equations in three unknowns actually hold for all linear systems. That is: Every system of linear equations has zero, one, or inﬁnitely many solutions. There are no other possibilities. 1.1 Introduction to Systems of Linear Equations 5 E X A M P L E 2 A Linear System with One Solution Solve the linear system x−y =1 2x + y = 6 x from the second equation by adding −2 times the ﬁrst equation to the second. This yields the simpliﬁed system Solution We can eliminate x−y =1 3y = 4 From the second equation we obtain y = 43 , and on substituting this value in the ﬁrst equation we obtain x = 1 + y = 73 . Thus, the system has the unique solution x = 73 , y = 4 3 Geometrically, this means that the lines represented by the equations in the system intersect at the single point 73 , 43 . We leave it for you to check this by graphing the lines. E X A M P L E 3 A Linear System with No Solutions Solve the linear system x+ y=4 3x + 3y = 6 Solution We can eliminate x from the second equation by adding −3 times the ﬁrst equation to the second equation. This yields the simpliﬁed system x+y = 4 0 = −6 The second equation is contradictory, so the given system has no solution. Geometrically, this means that the lines corresponding to the equations in the original system are parallel and distinct. We leave it for you to check this by graphing the lines or by showing that they have the same slope but different y intercepts. E X A M P L E 4 A Linear System with Inﬁnitely Many Solutions Solve the linear system 4x − 2y = 1 16x − 8y = 4 Solution We can eliminate x from the second equation by adding −4 times the ﬁrst equation to the second. This yields the simpliﬁed system 4 x − 2y = 1 0=0 The second equation does not impose any restrictions on x and y and hence can be omitted. Thus, the solutions of the system are those values of x and y that satisfy the single equation 4x − 2y = 1 (8) Geometrically, this means the lines corresponding to the two equations in the original system coincide. One way to describe the solution set is to solve this equation for x in terms of y to obtain x = 41 + 21 y and then assign an arbitrary value t (called a parameter) 6 Chapter 1 Systems of Linear Equations and Matrices In Example 4 we could have also obtained parametric equations for the solutions by solving (8) for y in terms of x and letting x = t be the parameter. The resulting parametric equations would look different but would deﬁne the same solution set. to y . This allows us to express the solution by the pair of equations (called parametric equations) x= 1 4 + 21 t, y = t We can obtain speciﬁc numerical solutions from these equations by substituting 1 numerical values for the parameter t . For example, t = 0 yields the solution ,0 , t = 1 4 yields the solution 43 , 1 , and t = −1 yields the solution − 41 , −1 . You can conﬁrm that these are solutions by substituting their coordinates into the given equations. E X A M P L E 5 A Linear System with Inﬁnitely Many Solutions Solve the linear system x − y + 2z = 5 2x − 2y + 4z = 10 3x − 3y + 6z = 15 Solution This system can be solved by inspection, since the second and third equations are multiples of the ﬁrst. Geometrically, this means that the three planes coincide and that those values of x , y , and z that satisfy the equation x − y + 2z = 5 (9) automatically satisfy all three equations. Thus, it sufﬁces to ﬁnd the solutions of (9). We can do this by ﬁrst solving this equation for x in terms of y and z, then assigning arbitrary values r and s (parameters) to these two variables, and then expressing the solution by the three parametric equations x = 5 + r − 2s, y = r, z = s Speciﬁc solutions can be obtained by choosing numerical values for the parameters r and s . For example, taking r = 1 and s = 0 yields the solution (6, 1, 0). Augmented Matrices and Elementary Row Operations As the number of equations and unknowns in a linear system increases, so does the complexity of the algebra involved in ﬁnding solutions. The required computations can be made more manageable by simplifying notation and standardizing procedures. For example, by mentally keeping track of the location of the +’s, the x ’s, and the =’s in the linear system a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. .. .. .. . . . . am1 x1 + am2 x2 + · · · + amn xn = bm we can abbreviate the system by writing only the rectangular array of numbers ⎡ a11 As noted in the introduction to this chapter, the term “matrix” is used in mathematics to denote a rectangular array of numbers. In a later section we will study matrices in detail, but for now we will only be concerned with augmented matrices for linear systems. ⎢ ⎢a21 ⎢ . ⎣ .. am1 a12 · · · a1n a22 .. . · · · a2 n .. . am2 · · · amn b1 ⎤ ⎥ b2 ⎥ .. ⎥ . ⎦ bm This is called the augmented matrix for the system. For example, the augmented matrix for the system of equations ⎡ x1 + x2 + 2x3 = 9 2x1 + 4x2 − 3x3 = 1 3x1 + 6x2 − 5x3 = 0 is 1 ⎤ ⎢ ⎣2 1 2 9 4 −3 1⎦ 3 6 −5 0 ⎥ 1.1 Introduction to Systems of Linear Equations 7 The basic method for solving a linear system is to perform algebraic operations on the system that do not alter the solution set and that produce a succession of increasingly simpler systems, until a point is reached where it can be ascertained whether the system is consistent, and if so, what its solutions are. Typically, the algebraic operations are: 1. Multiply an equation through by a nonzero constant. 2. Interchange two equations. 3. Add a constant times one equation to another. Since the rows (horizontal lines) of an augmented matrix correspond to the equations in the associated system, these three operations correspond to the following operations on the rows of the augmented matrix: 1. Multiply a row through by a nonzero constant. 2. Interchange two rows. 3. Add a constant times one row to another. These are called elementary row operations on a matrix. In the following example we will illustrate how to use elementary row operations and an augmented matrix to solve a linear system in three unknowns. Since a systematic procedure for solving linear systems will be developed in the next section, do not worry about how the steps in the example were chosen. Your objective here should be simply to understand the computations. E X A M P L E 6 Using Elementary Row Operations In the left column we solve a system of linear equations by operating on the equations in the system, and in the right column we solve the same system by operating on the rows of the augmented matrix. ⎡ x + y + 2z = 9 1 1 2 ⎤ 9 2x + 4y − 3z = 1 ⎢ ⎣2 4 −3 1⎦ 3x + 6y − 5z = 0 3 6 −5 0 Add −2 times the ﬁrst equation to the second to obtain x + y + 2z = 9 2y − 7z = −17 3x + 6y − 5z = Maxime Bôcher (1867–1918) 0 ⎥ Add −2 times the ﬁrst row to the second to obtain ⎡ 1 ⎢ ⎣0 1 2 2 3 6 −7 −5 9 ⎤ ⎥ −17⎦ 0 Historical Note The ﬁrst known use of augmented matrices appeared between 200 B.C. and 100 B.C. in a Chinese manuscript entitled Nine Chapters of Mathematical Art. The coefﬁcients were arranged in columns rather than in rows, as today, but remarkably the system was solved by performing a succession of operations on the columns. The actual use of the term augmented matrix appears to have been introduced by the American mathematician Maxime Bôcher in his book Introduction to Higher Algebra, published in 1907. In addition to being an outstanding research mathematician and an expert in Latin, chemistry, philosophy, zoology, geography, meteorology, art, and music, Bôcher was an outstanding expositor of mathematics whose elementary textbooks were greatly appreciated by students and are still in demand today. [Image: Courtesy of the American Mathematical Society www.ams.org] 8 Chapter 1 Systems of Linear Equations and Matrices Add −3 times the ﬁrst equation to the third to obtain Add −3 times the ﬁrst row to the third to obtain ⎡ x + y + 2z = 9 2y − 7z = −17 3y − 11z = −27 Multiply the second equation by 1 2 x + y + 2z = to obtain ⎢ ⎣0 1 2 2 −7 0 3 −11 Multiply the second row by ⎡ 9 1 = − 172 ⎢ ⎣0 3y − 11z = −27 0 y− 7 z 2 Add −3 times the second equation to the third to obtain x + y + 2z = ⎡ 1 9 − 21 z = − 23 Multiply the third equation by −2 to obtain x + y + 2z = y− 11 z 2 7 z 2 = = z= 3 y −11 1 − 27 0 0 − 21 0 ⎥ −17⎦ −27 1 2 to obtain 9 ⎤ ⎥ − 172 ⎦ −27 ⎤ 9 ⎥ − 172 ⎥ ⎦ − 23 1 2 1 − 27 0 1 ⎤ 9 ⎥ − 172 ⎦ 3 Add −1 times the second row to the ﬁrst to obtain ⎡ ⎢ ⎢0 ⎣ 0 1 11 2 − 27 0 0 1 1 Add −11 times the third equation to the ﬁrst 2 and 27 times the third equation to the second to obtain x 3 ⎢ ⎢0 ⎣ ⎢ ⎣0 3 35 2 − 172 − 27 2 1 Add −1 times the second equation to the ﬁrst to obtain + 1 1 ⎡ y − 27 z = − 172 x 2 ⎤ Multiply the third row by −2 to obtain 9 z= 1 9 Add −3 times the second row to the third to obtain y − 27 z = − 172 The solution in this example can also be expressed as the ordered triple (1, 2, 3) with the understanding that the numbers in the triple are in the same order as the variables in the system, namely, x, y, z. 1 ⎤ 35 2 ⎥ − 172 ⎥ ⎦ 3 Add − 11 times the third row to the ﬁrst and 2 times the third row to the second to obtain ⎡ =1 =2 ⎤ ⎢ ⎣0 0 0 1 1 0 2⎦ 0 0 1 3 z=3 1 7 2 ⎥ The solution x = 1, y = 2, z = 3 is now evident. Exercise Set 1.1 1. In each part, determine whether the equation is linear in x1 , x2 , and x3 . (a) x1 + 5x2 − √ 2 x3 = 1 (c) x1 = −7x2 + 3x3 (e) 3/5 x1 − 2x2 + x3 = 4 2. In each part, determine whether the equation is linear in x and y . (b) x1 + 3x2 + x1 x3 = 2 (a) 21/3 x + (d) x1−2 + x2 + 8x3 = 5 (c) cos (f ) πx1 − (e) xy = 1 √ 2 x2 = 7 1/3 π 7 √ 3y = 1 x − 4y = log 3 √ (b) 2x 1/3 + 3 y = 1 (d) π 7 cos x − 4y = 0 (f ) y + 7 = x 1.1 Introduction to Systems of Linear Equations 3. Using the notation of Formula (7), write down a general linear system of (d) (a) two equations in two unknowns. (b) three equations in three unknowns. (c) two equations in four unknowns. 4. Write down the augmented matrix for each of the linear systems in Exercise 3. In each part of Exercises 5–6, ﬁnd a linear system in the unknowns x1 , x2 , x3 , . . . , that corresponds to the given augmented matrix. ⎡ 2 ⎢ 5. (a) ⎣3 0 6. (a) ⎤ 0 −4 1 0 3 −1 5 2 0 ⎡ 3 ⎢−4 ⎢ (b) ⎢ ⎣−1 0 ⎡ 0 ⎥ 0⎦ 1 0 0 3 0 3 ⎢ (b) ⎣7 0 −1 −3 −4 1 4 0 0 1 −2 −1 −1 −6 0 1 −2 −2 4 1 ⎤ 5 ⎥ −3⎦ 7 (c) x3 (d) 2 , 25 , 2 , 10 2 , 7 7 (e) 5 7 , 87 , 0 7 , 227 , 2 5 (c) (5, 8, 1) 11. In each part, solve the linear system, if possible, and use the result to determine whether the lines represented by the equations in the system have zero, one, or inﬁnitely many points of intersection. If there is a single point of intersection, give its coordinates, and if there are inﬁnitely many, ﬁnd parametric equations for them. (a) 3x − 2y = 4 6x − 4 y = 9 (b) 2x − 4y = 1 4 x − 8y = 2 (c) x − 2y = 0 x − 4y = 8 12. Under what conditions on a and b will the following linear system have no solutions, one solution, inﬁnitely many solutions? 2 x − 3y = a 4x − 6y = b (d) 3v − 8w + 2x − y + 4z = 0 14. (a) x + 10y = 2 (b) x1 + 3x2 − 12x3 = 3 (c) 4x1 + 2x2 + 3x3 + x4 = 20 (d) v + w + x − 5y + 7z = 0 In Exercises 15–16, each linear system has inﬁnitely many solutions. Use parametric equations to describe its solution set. (b) 2x1 + 2x3 = 1 3x1 − x2 + 4x3 = 7 6x1 + x2 − x3 = 0 =1 =2 =3 2x1 − 4x2 − x3 = 1 x1 − 3x2 + x3 = 1 3x1 − 5x2 − 3x3 = 1 13 7 5 (b) (c) −8x1 + 2x2 − 5x3 + 6x4 = 1 9. In each part, determine whether the given 3tuple is a solution of the linear system (a) (3, 1, 1) , 87 , 1 (b) 3x1 − 5x2 + 4x3 = 7 (b) 6x1 − x2 + 3x3 = 4 5x2 − x3 = 1 8. (a) 3x1 − 2x2 = −1 4x1 + 5x2 = 3 7x1 + 3x2 = 2 x2 7 13. (a) 7x − 5y = 3 2x2 − 3x4 + x5 = 0 −3x1 − x2 + x3 = −1 6x1 + 2x2 − x3 + 2x4 − 3x5 = 6 (c) x1 5 In each part of Exercises 13–14, use parametric equations to describe the solution set of the linear equation. ⎤ 3 −3 ⎥ ⎥ ⎥ −9 ⎦ −2 In each part of Exercises 7–8, ﬁnd the augmented matrix for the linear system. 7. (a) −2x1 = 6 3x1 = 8 9x1 = −3 (a) 9 (b) (3, −1, 1) (c) (13, 5, 2) (e) (17, 7, 5) 10. In each part, determine whether the given 3tuple is a solution of the linear system x + 2y − 2z = 3 3x − y + z = 1 −x + 5y − 5z = 5 15. (a) 2x − 3y = 1 6 x − 9y = 3 (b) x1 + 3x2 − x3 = −4 3x1 + 9x2 − 3x3 = −12 −x1 − 3x2 + x3 = 4 16. (a) 6x1 + 2x2 = −8 3x1 + x2 = −4 (b) 2x − y + 2z = −4 6x − 3y + 6z = −12 −4 x + 2 y − 4 z = 8 In Exercises 17–18, ﬁnd a single elementary row operation that will create a 1 in the upper left corner of the given augmented matrix and will not create any fractions in its ﬁrst row. ⎡ −3 17. (a) ⎣ 2 0 ⎡ 2 18. (a) ⎣ 7 −5 −1 −3 2 4 1 4 ⎤ 2 3 −3 4 2⎦ 1 −6 8 3⎦ 7 4 2 ⎤ ⎡ 0 (b) ⎣2 1 ⎡ 7 (b) ⎣ 3 −6 −1 −9 ⎤ −5 0 2⎦ 3 3 −3 4 −4 −1 3 −2 8 −1 ⎤ 2 1⎦ 4 10 Chapter 1 Systems of Linear Equations and Matrices In Exercises 19–20, ﬁnd all values of k for which the given augmented matrix corresponds to a consistent linear system. 19. (a) 1 4 k −4 8 2 20. (a) 3 −6 −4 k 8 5 (b) (b) 1 4 k k 1 −1 4 8 −1 −4 −2 2 21. The curve y = ax 2 + bx + c shown in the accompanying ﬁgure passes through the points (x1 , y1 ), (x2 , y2 ), and (x3 , y3 ). Show that the coefﬁcients a , b, and c form a solution of the system of linear equations whose augmented matrix is ⎡ x12 ⎢ 2 ⎣x2 x32 y y1 ⎤ x1 1 x2 1 ⎥ y2 ⎦ x3 1 y3 Let x, y, and z denote the number of ounces of the ﬁrst, second, and third foods that the dieter will consume at the main meal. Find (but do not solve) a linear system in x, y, and z whose solution tells how many ounces of each food must be consumed to meet the diet requirements. 26. Suppose that you want to ﬁnd values for a, b, and c such that the parabola y = ax 2 + bx + c passes through the points (1, 1), (2, 4), and (−1, 1). Find (but do not solve) a system of linear equations whose solutions provide values for a, b, and c. How many solutions would you expect this system of equations to have, and why? 27. Suppose you are asked to ﬁnd three real numbers such that the sum of the numbers is 12, the sum of two times the ﬁrst plus the second plus two times the third is 5, and the third number is one more than the ﬁrst. Find (but do not solve) a linear system whose equations describe the three conditions. TrueFalse Exercises y = ax2 + bx + c TF. In parts (a)–(h) determine whether the statement is true or false, and justify your answer. (x3, y3) (x1, y1) (a) A linear system whose equations are all homogeneous must be consistent. (x2, y2) x Figure Ex21 22. Explain why each of the three elementary row operations does not affect the solution set of a linear system. 23. Show that if the linear equations x1 + kx2 = c and x1 + lx2 = d have the same solution set, then the two equations are identical (i.e., k = l and c = d ). 24. Consider the system of equations ax + by = k cx + dy = l ex + fy = m Discuss the relative positions of the lines ax + by = k , cx + dy = l , and ex + fy = m when (a) the system has no solutions. (b) the system has exactly one solution. (b) Multiplying a row of an augmented matrix through by zero is an acceptable elementary row operation. (c) The linear system x− y =3 2x − 2y = k cannot have a unique solution, regardless of the value of k . (d) A single linear equation with two or more unknowns must have inﬁnitely many solutions. (e) If the number of equations in a linear system exceeds the number of unknowns, then the system must be inconsistent. (f ) If each equation in a consistent linear system is multiplied through by a constant c, then all solutions to the new system can be obtained by multiplying solutions from the original system by c. (g) Elementary row operations permit one row of an augmented matrix to be subtracted from another. (h) The linear system with corresponding augmented matrix (c) the system has inﬁnitely many solutions. 25. Suppose that a certain diet calls for 7 units of fat, 9 units of protein, and 16 units of carbohydrates for the main meal, and suppose that an individual has three possible foods to choose from to meet these requirements: Food 1: Each ounce contains 2 units of fat, 2 units of protein, and 4 units of carbohydrates. Food 2: Each ounce contains 3 units of fat, 1 unit of protein, and 2 units of carbohydrates. Food 3: Each ounce contains 1 unit of fat, 3 units of protein, and 5 units of carbohydrates. 2 0 −1 0 4 −1 is consistent. Working withTechnology T1. Solve the linear systems in Examples 2, 3, and 4 to see how your technology utility handles the three types of systems. T2. Use the result in Exercise 21 to ﬁnd values of a , b, and c for which the curve y = ax 2 + bx + c passes through the points (−1, 1, 4), (0, 0, 8), and (1, 1, 7). 1.2 Gaussian Elimination 11 1.2 Gaussian Elimination In this section we will develop a systematic procedure for solving systems of linear equations. The procedure is based on the idea of performing certain operations on the rows of the augmented matrix that simplify it to a form from which the solution of the system can be ascertained by inspection. Considerations in Solving Linear Systems When considering methods for solving systems of linear equations, it is important to distinguish between large systems that must be solved by computer and small systems that can be solved by hand. For example, there are many applications that lead to linear systems in thousands or even millions of unknowns. Large systems require special techniques to deal with issues of memory size, roundoff errors, solution time, and so forth. Such techniques are studied in the ﬁeld of numerical analysis and will only be touched on in this text. However, almost all of the methods that are used for large systems are based on the ideas that we will develop in this section. Echelon Forms In Example 6 of the last section, we solved a linear system in the unknowns x , y , and z by reducing the augmented matrix to the form ⎡ 1 ⎢0 ⎣ 0 0 1 0 0 0 1 ⎤ 1 2⎥ ⎦ 3 from which the solution x = 1, y = 2, z = 3 became evident. This is an example of a matrix that is in reduced row echelon form. To be of this form, a matrix must have the following properties: 1. If a row does not consist entirely of zeros, then the ﬁrst nonzero number in the row is a 1. We call this a leading 1. 2. If there are any rows that consist entirely of zeros, then they are grouped together at the bottom of the matrix. 3. In any two successive rows that do not consist entirely of zeros, the leading 1 in the lower row occurs farther to the right than the leading 1 in the higher row. 4. Each column that contains a leading 1 has zeros everywhere else in that column. A matrix that has the ﬁrst three properties is said to be in row echelon form. (Thus, a matrix in reduced row echelon form is of necessity in row echelon form, but not conversely.) E X A M P L E 1 Row Echelon and Reduced Row Echelon Form The following matrices are in reduced row echelon form. ⎡ 1 ⎢ ⎣0 0 0 1 0 0 0 1 ⎤ ⎡ 4 1 ⎥ ⎢ 7⎦ , ⎣0 0 −1 0 1 0 ⎤ 0 ⎥ 0⎦ , 1 ⎡ 0 ⎢0 ⎢ ⎢ ⎣0 0 1 0 0 0 −2 0 0 0 0 1 0 0 ⎤ 1 3⎥ ⎥ ⎥, 0⎦ 0 0 0 0 0 The following matrices are in row echelon form but not reduced row echelon form. ⎡ 1 ⎢ ⎣0 0 4 1 0 −3 6 1 ⎤ ⎡ 7 1 ⎥ ⎢ 2⎦ , ⎣0 5 0 1 1 0 ⎤ ⎡ 0 0 ⎥ ⎢ 0⎦ , ⎣0 0 0 1 0 0 2 1 0 6 −1 0 ⎤ 0 ⎥ 0⎦ 1 12 Chapter 1 Systems of Linear Equations and Matrices E X A M P L E 2 More on Row Echelon and Reduced Row Echelon Form As Example 1 illustrates, a matrix in row echelon form has zeros below each leading 1, whereas a matrix in reduced row echelon form has zeros below and above each leading 1. Thus, with any real numbers substituted for the ∗’s, all matrices of the following types are in row echelon form: ⎡ 1 ⎢0 ⎢ ⎢ ⎣0 0 ⎤ ∗ ∗ ∗ 1 ∗ ∗⎥ ⎥ ⎥, 0 1 ∗⎦ ⎡ 1 ⎢0 ⎢ ⎢ ⎣0 0 0 0 1 ⎤ ∗ ∗ ∗ 1 ∗ ∗⎥ ⎥ ⎥, 0 1 ∗⎦ ⎡ 1 ⎢0 ⎢ ⎢ ⎣0 0 0 0 0 ⎤ ∗ ∗ ∗ 1 ∗ ∗⎥ ⎥ ⎥, 0 0 0⎦ 0 0 0 ⎡ 0 ⎢0 ⎢ ⎢ ⎢0 ⎢ ⎣0 0 1 0 0 0 0 ⎤ ∗ ∗⎥ ⎥ ⎥ ∗⎥ ⎥ ∗⎦ 0 0 0 0 0 0 1 ∗ ∗ ∗ ∗ ∗ ∗ 0 1 ∗ ∗ ∗ 0 0 1 ∗ ∗ 0 0 0 1 ∗ ∗ ∗ ∗ ∗ All matrices of the following types are in reduced row echelon form: ⎡ ⎤ ⎡ ⎤ ⎡ 1 0 0 0 1 0 0 ∗ 1 0 ⎢0 1 0 0⎥ ⎢0 1 0 ∗⎥ ⎢0 1 ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥, ⎢ ⎥, ⎢ ⎣0 0 1 0⎦ ⎣0 0 1 ∗⎦ ⎣0 0 0 0 0 1 0 0 0 0 0 0 ⎡ ⎤ 0 ∗ ∗ ⎢0 ⎢ ∗ ∗⎥ ⎥ ⎢ ⎥ , ⎢0 ⎢ 0 0⎦ ⎣0 0 0 0 1 0 0 0 0 ∗ 0 0 0 ∗ 0 1 0 0 ∗ 0 0 1 0 ∗ 0 0 0 1 ∗ ∗ ∗ ∗ ∗ 0 0 0 0 0 0 0 0 0 0 1 ∗ ∗ ∗ ∗ ⎤ ∗ ∗⎥ ⎥ ⎥ ∗⎥ ⎥ ∗⎦ ∗ If, by a sequence of elementary row operations, the augmented matrix for a system of linear equations is put in reduced row echelon form, then the solution set can be obtained either by inspection or by converting certain linear equations to parametric form. Here are some examples. E X A M P L E 3 Unique Solution Suppose that the augmented matrix for a linear system in the unknowns x1 , x2 , x3 , and x4 has been reduced by elementary row operations to ⎡ 1 ⎢0 ⎢ ⎢ ⎣0 0 0 1 0 0 0 0 1 0 0 0 0 1 ⎤ 3 −1⎥ ⎥ ⎥ 0⎦ 5 This matrix is in reduced row echelon form and corresponds to the equations x1 In Example 3 we could, if desired, express the solution more succinctly as the 4tuple (3, −1, 0, 5). x2 x3 = 3 = −1 = 0 x4 = 5 Thus, the system has a unique solution, namely, x1 = 3, x2 = −1, x3 = 0, x4 = 5. E X A M P L E 4 Linear Systems in Three Unknowns In each part, suppose that the augmented matrix for a linear system in the unknowns x , y , and z has been reduced by elementary row operations to the given reduced row echelon form. Solve the system. ⎡ 1 ⎢ (a) ⎣0 0 0 1 0 0 2 0 ⎤ 0 ⎥ 0⎦ 1 ⎡ 1 ⎢ (b) ⎣0 0 0 1 0 3 −4 0 ⎤ −1 ⎥ 2⎦ 0 ⎡ 1 ⎢ (c) ⎣0 0 −5 0 0 1 0 0 ⎤ 4 ⎥ 0⎦ 0 1.2 Gaussian Elimination 13 Solution (a) The equation that corresponds to the last row of the augmented matrix is 0x + 0y + 0z = 1 Since this equation is not satisﬁed by any values of x , y , and z, the system is inconsistent. Solution (b) The equation that corresponds to the last row of the augmented matrix is 0x + 0y + 0z = 0 This equation can be omitted since it imposes no restrictions on x , y , and z; hence, the linear system corresponding to the augmented matrix is + 3z = −1 y − 4z = 2 x Since x and y correspond to the leading 1’s in the augmented matrix, we call these the leading variables. The remaining variables (in this case z) are called free variables. Solving for the leading variables in terms of the free variables gives x = −1 − 3z y = 2 + 4z From these equations we see that the free variable z can be treated as a parameter and assigned an arbitrary value t , which then determines values for x and y . Thus, the solution set can be represented by the parametric equations x = −1 − 3t, y = 2 + 4t, z = t By substituting various values for t in these equations we can obtain various solutions of the system. For example, setting t = 0 yields the solution x = −1, y = 2, z = 0 and setting t = 1 yields the solution x = −4, y = 6, z = 1 Solution (c) As explained in part (b), we can omit the equations corresponding to the zero rows, in which case the linear system associated with the augmented matrix consists of the single equation x − 5y + z = 4 (1) We will usually denote parameters in a general solution by the letters r, s, t, . . . , but any letters that do not conﬂict with the names of the unknowns can be used. For systems with more than three unknowns, subscripted letters such as t1 , t2 , t3 , . . . are convenient. from which we see that the solution set is a plane in threedimensional space. Although (1) is a valid form of the solution set, there are many applications in which it is preferable to express the solution set in parametric form. We can convert (1) to parametric form by solving for the leading variable x in terms of the free variables y and z to obtain x = 4 + 5y − z From this equation we see that the free variables can be assigned arbitrary values, say y = s and z = t , which then determine the value of x . Thus, the solution set can be expressed parametrically as x = 4 + 5s − t, y = s, z = t (2) Formulas, such as (2), that express the solution set of a linear system parametrically have some associated terminology. DEFINITION 1 If a linear system has inﬁnitely many solutions, then a set of parametric equations from which all solutions can be obtained by assigning numerical values to the parameters is called a general solution of the system. 14 Chapter 1 Systems of Linear Equations and Matrices Elimination Methods We have just seen how easy it is to solve a system of linear equations once its augmented matrix is in reduced row echelon form. Now we will give a stepbystep elimination procedure that can be used to reduce any matrix to reduced row echelon form. As we state each step in the procedure, we illustrate the idea by reducing the following matrix to reduced row echelon form. ⎡ 0 0 ⎢ ⎣2 4 2 4 −2 −10 −5 0 7 6 12 6 12 ⎤ ⎥ 28⎦ −5 −1 Step 1. Locate the leftmost column that does not consist entirely of zeros. ⎡ 0 ⎢ 2 ⎣ 2 0 4 4 2 10 5 0 6 6 7 12 5 ⎤ 12 ⎥ 28⎦ 1 Leftmost nonzero column Step 2. Interchange the top row with another row, if necessary, to bring a nonzero entry to the top of the column found in Step 1. ⎡ 2 ⎢ ⎣0 2 −10 −2 0 −5 4 4 6 12 0 7 6 −5 ⎤ 28 ⎥ 12⎦ The ﬁrst and second rows in the preceding matrix were interchanged. −1 Step 3. If the entry that is now at the top of the column found in Step 1 is a , multiply the ﬁrst row by 1/a in order to introduce a leading 1. ⎡ 1 ⎢ ⎣0 2 −5 0 −2 4 −5 2 ⎤ 3 6 14 0 7 12⎦ 6 −5 ⎥ The ﬁrst row of the preceding matrix was multiplied by 21 . −1 Step 4. Add suitable multiples of the top row to the rows below so that all entries below the leading 1 become zeros. ⎡ 1 ⎢ ⎣0 0 ⎤ −5 0 −2 3 6 14 0 7 12⎦ 0 0 2 5 ⎥ −17 −29 −2 times the ﬁrst row of the preceding matrix was added to the third row. Step 5. Now cover the top row in the matrix and begin again with Step 1 applied to the submatrix that remains. Continue in this way until the entire matrix is in row echelon form. ⎡ 1 ⎢ ⎣0 0 2 0 0 5 2 5 3 0 0 6 7 17 ⎤ 14 ⎥ 12 ⎦ 29 Leftmost nonzero column in the submatrix ⎡ 1 ⎢ ⎣0 2 5 3 6 0 1 0 7 2 0 0 5 0 17 14 ⎤ ⎥ 6⎦ 29 The first row in the submatrix was multiplied by 1 to introduce a 2 leading 1. 1.2 Gaussian Elimination ⎡ 1 ⎢0 ⎣ 2 5 3 6 0 1 0 0 0 0 7 2 1 2 0 ⎡ 1 ⎢ ⎣0 2 5 3 6 0 1 0 0 0 0 0 7 2 1 2 ⎡ 1 ⎢ ⎣0 0 ⎤ 14 ⎥ 6⎦ 1 14 15 ⎤ ⎥ 6⎦ 1 –5 times the first row of the submatrix was added to the second row of the submatrix to introduce a zero below the leading 1. The top row in the submatrix was covered, and we returned again to Step 1. Leftmost nonzero column in the new submatrix 2 5 3 6 0 0 1 0 0 0 7 2 1 14 ⎤ ⎥ 6⎦ 2 The first (and only) row in the new submatrix was multiplied by 2 to introduce a leading 1. The entire matrix is now in row echelon form. To ﬁnd the reduced row echelon form we need the following additional step. Step 6. Beginning with the last nonzero row and working upward, add suitable multiples of each row to the rows above to introduce zeros above the leading 1’s. ⎡ 1 ⎢ ⎣0 0 2 0 0 −5 1 ⎢ ⎣0 0 2 0 0 −5 1 ⎢ ⎣0 0 2 0 0 ⎡ ⎡ ⎤ 3 0 0 6 0 1 14 ⎥ 1⎦ 2 7 times the third row of the preceding 2 matrix was added to the second row. 1 0 3 0 0 0 0 1 2 ⎥ 1⎦ 2 −6 times the third row was added to the ﬁrst row. 0 1 0 3 0 0 0 0 1 7 ⎥ 1⎦ 2 5 times the second row was added to the ﬁrst row. 1 0 ⎤ ⎤ The last matrix is in reduced row echelon form. The procedure (or algorithm) we have just described for reducing a matrix to reduced row echelon form is called Gauss–Jordan elimination. This algorithm consists of two parts, a forward phase in which zeros are introduced below the leading 1’s and a backward phase in which zeros are introduced above the leading 1’s. If only theforward phase is Carl Friedrich Gauss (1777–1855) Wilhelm Jordan (1842–1899) Historical Note Although versions of Gaussian elimination were known much earlier, its importance in scientiﬁc computation became clear when the great German mathematician Carl Friedrich Gauss used it to help compute the orbit of the asteroid Ceres from limited data. What happened was this: On January 1, 1801 the Sicilian astronomer and Catholic priest Giuseppe Piazzi (1746–1826) noticed a dim celestial object that he believed might be a “missing planet.” He named the object Ceres and made a limited number of positional observations but then lost the object as it neared the Sun. Gauss, then only 24 years old, undertook the problem of computing the orbit of Ceres from the limited data using a technique called “least squares,” the equations of which he solved by the method that we now call “Gaussian elimination.” The work of Gauss created a sensation when Ceres reappeared a year later in the constellation Virgo at almost the precise position that he predicted! The basic idea of the method was further popularized by the German engineer Wilhelm Jordan in his book on geodesy (the science of measuring Earth shapes) entitled Handbuch der Vermessungskunde and published in 1888. [Images: Photo Inc/Photo Researchers/Getty Images (Gauss); Leemage/Universal Images Group/Getty Images (Jordan)] 16 Chapter 1 Systems of Linear Equations and Matrices used, then the procedure produces a row echelon form and is called Gaussian elimination. For example, in the preceding computations a row echelon form was obtained at the end of Step 5. E X A M P L E 5 Gauss–Jordan Elimination Solve by Gauss–Jordan elimination. x1 + 3x2 − 2x3 + 2x5 2x1 + 6x2 − 5x3 − 2x4 + 4x5 − 3x6 5x3 + 10x4 + 15x6 2x1 + 6x2 + 8x4 + 4x5 + 18x6 = 0 = −1 = 5 = 6 Solution The augmented matrix for the system is ⎡ 1 ⎢2 ⎢ ⎢ ⎣0 2 3 6 0 6 −2 −5 5 0 0 −2 10 8 2 4 0 4 0 −3 15 18 ⎤ 0 −1⎥ ⎥ ⎥ 5⎦ 6 Adding −2 times the ﬁrst row to the second and fourth rows gives ⎡ 1 ⎢0 ⎢ ⎢ ⎣0 0 3 0 0 0 −2 −1 5 4 0 −2 10 8 2 0 0 0 0 −3 15 18 ⎤ 0 −1⎥ ⎥ ⎥ 5⎦ 6 Multiplying the second row by −1 and then adding −5 times the new second row to the third row and −4 times the new second row to the fourth row gives ⎡ 1 ⎢0 ⎢ ⎢ ⎣0 0 3 0 0 0 −2 1 0 0 0 2 0 0 2 0 0 0 ⎤ 0 3 0 6 0 1⎥ ⎥ ⎥ 0⎦ 2 Interchanging the third and fourth rows and then multiplying the third row of the resulting matrix by 16 gives the row echelon form ⎡ 1 ⎢0 ⎢ 3 0 −2 0 0 0 ⎢ ⎣0 ⎤ 1 0 2 2 0 0 3 0 1⎥ ⎥ 0 0 0 0 0 0 1 0 0 1⎥ ⎦ 3 This completes the forward phase since there are zeros below the leading 1’s. Adding −3 times the third row to the second row and then adding 2 times the second row of the resulting matrix to the ﬁrst row yields the reduced row echelon form ⎡ 3 0 0 1 4 2 2 0 0 0 0 0⎥ ⎥ 0 0 0 0 0 0 0 0 0 1 0 0 ⎢ ⎣0 Note that in constructing the linear system in (3) we ignored the row of zeros in the corresponding augmented matrix. Why is this justiﬁed? ⎤ 1 ⎢0 ⎢ 1⎥ ⎦ 3 This completes the backward phase since there are zeros above the leading 1’s. The corresponding system of equations is x1 + 3x2 + 4x4 + 2x5 x3 + 2x4 =0 =0 x6 = 1 3 (3) 1.2 Gaussian Elimination 17 Solving for the leading variables, we obtain x1 = −3x2 − 4x4 − 2x5 x3 = −2x4 x6 = 1 3 Finally, we express the general solution of the system parametrically by assigning the free variables x2 , x4 , and x5 arbitrary values r, s , and t , respectively. This yields x1 = −3r − 4s − 2t, x2 = r, x3 = −2s, x4 = s, x5 = t, x6 = Homogeneous Linear Systems 1 3 A system of linear equations is said to be homogeneous if the constant terms are all zero; that is, the system has the form a11 x1 + a12 x2 + · · · + a1n xn = 0 a21 x1 + a22 x2 + · · · + a2n xn = 0 .. .. .. .. . . . . am1 x1 + am2 x2 + · · · + amn xn = 0 Every homogeneous system of linear equations is consistent because all such systems have x1 = 0, x2 = 0, . . . , xn = 0 as a solution. This solution is called the trivial solution; if there are other solutions, they are called nontrivial solutions. Because a homogeneous linear system always has the trivial solution, there are only two possibilities for its solutions: • The system has only the trivial solution. • The system has inﬁnitely many solutions in addition to the trivial solution. In the special case of a homogeneous linear system of two equations in two unknowns, say a1 x + b1 y = 0 (a1 , b1 not both zero) a2 x + b2 y = 0 (a2 , b2 not both zero) the graphs of the equations are lines through the origin, and the trivial solution corresponds to the point of intersection at the origin (Figure 1.2.1). y y a1x + b1y = 0 x a 2 x + b2 y = 0 Only the trivial solution Figure 1.2.1 x a1x + b1y = 0 and a 2 x + b2 y = 0 Infinitely many solutions There is one case in which a homogeneous system is assured of having nontrivial solutions—namely, whenever the system involves more unknowns than equations. To see why, consider the following example of four equations in six unknowns. 18 Chapter 1 Systems of Linear Equations and Matrices E X A M P L E 6 A Homogeneous System Use Gauss–Jordan elimination to solve the homogeneous linear system x1 + 3x2 − 2x3 + 2 x5 2x1 + 6x2 − 5x3 − 2x4 + 4x5 − 3x6 + 15x6 5x3 + 10x4 + 8x4 + 4x5 + 18x6 2x1 + 6x2 =0 =0 =0 =0 (4) Solution Observe ﬁrst that the coefﬁcients of the unknowns in this system are the same as those in Example 5; that is, the two systems differ only in the constants on the right side. The augmented matrix for the given homogeneous system is ⎡ 1 ⎢2 ⎢ ⎢ ⎣0 2 3 6 0 6 −2 −5 0 −2 10 8 5 0 2 4 0 4 ⎤ 0 −3 15 18 0 0⎥ ⎥ ⎥ 0⎦ 0 (5) which is the same as the augmented matrix for the system in Example 5, except for zeros in the last column. Thus, the reduced row echelon form of this matrix will be the same as that of the augmented matrix in Example 5, except for the last column. However, a moment’s reﬂection will make it evident that a column of zeros is not changed by an elementary row operation, so the reduced row echelon form of (5) is ⎡ 1 ⎢0 ⎢ ⎢ ⎣0 0 3 0 0 0 0 1 0 0 4 2 0 0 2 0 0 0 0 0 1 0 ⎤ 0 0⎥ ⎥ ⎥ 0⎦ 0 (6) The corresponding system of equations is x1 + 3x2 + 4x4 + 2x5 x3 + 2x4 =0 =0 x6 = 0 Solving for the leading variables, we obtain x1 = −3x2 − 4x4 − 2x5 x3 = −2x4 x6 = 0 (7) If we now assign the free variables x2 , x4 , and x5 arbitrary values r , s , and t , respectively, then we can express the solution set parametrically as x1 = −3r − 4s − 2t, x2 = r, x3 = −2s, x4 = s, x5 = t, x6 = 0 Note that the trivial solution results when r = s = t = 0. Free Variables in Homogeneous Linear Systems Example 6 illustrates two important points about solving homogeneous linear systems: 1. Elementary row operations do not alter columns of zeros in a matrix, so the reduced row echelon form of the augmented matrix for a homogeneous linear system has a ﬁnal column of zeros. This implies that the linear system corresponding to the reduced row echelon form is homogeneous, just like the original system. 1.2 Gaussian Elimination 19 2. When we constructed the homogeneous linear system corresponding to augmented matrix (6), we ignored the row of zeros because the corresponding equation 0x1 + 0x2 + 0x3 + 0x4 + 0x5 + 0x6 = 0 does not impose any conditions on the unknowns. Thus, depending on whether or not the reduced row echelon form of the augmented matrix for a homogeneous linear system has any rows of zero, the linear system corresponding to that reduced row echelon form will either have the same number of equations as the original system or it will have fewer. Now consider a general homogeneous linear system with n unknowns, and suppose that the reduced row echelon form of the augmented matrix has r nonzero rows. Since each nonzero row has a leading 1, and since each leading 1 corresponds to a leading variable, the homogeneous system corresponding to the reduced row echelon form of the augmented matrix must have r leading variables and n − r free variables. Thus, this system is of the form xk1 + ()=0 + xk2 .. ()=0 .. . . x kr + ( ) = 0 (8) where in each equation the expression ( ) denotes a sum that involves the free variables, if any [see (7), for example]. In summary, we have the following result. THEOREM 1.2.1 Free Variable Theorem for Homogeneous Systems If a homogeneous linear system has n unknowns, and if the reduced row echelon form of its augmented matrix has r nonzero rows, then the system has n − r free variables. Note that Theorem 1.2.2 applies only to homogeneous systems—a nonhomogeneous system with more unknowns than equations need not be consistent. However, we will prove later that if a nonhomogeneous system with more unknowns then equations is consistent, then it has inﬁnitely many solutions. Theorem 1.2.1 has an important implication for homogeneous linear systems with more unknowns than equations. Speciﬁcally, if a homogeneous linear system has m equations in n unknowns, and if m < n, then it must also be true that r < n (why?). This being the case, the theorem implies that there is at least one free variable, and this implies that the system has inﬁnitely many solutions. Thus, we have the following result. THEOREM 1.2.2 A homogeneous linear system with more unknowns than equations has inﬁnitely many solutions. In retrospect, we could have anticipated that the homogeneous system in Example 6 would have inﬁnitely many solutions since it has four equations in six unknowns. Gaussian Elimination and BackSubstitution For small linear systems that are solved by hand (such as most of those in this text), Gauss–Jordan elimination (reduction to reduced row echelon form) is a good procedure to use. However, for large linear systems that require a computer solution, it is generally more efﬁcient to use Gaussian elimination (reduction to row echelon form) followed by a technique known as backsubstitution to complete the process of solving the system. The next example illustrates this technique. 20 Chapter 1 Systems of Linear Equations and Matrices E X A M P L E 7 Example 5 Solved by BackSubstitution From the computations in Example 5, a row echelon form of the augmented matrix is ⎡ 1 ⎢0 ⎢ ⎢ ⎣0 0 3 0 0 0 −2 0 2 0 0 1 0 0 2 0 0 0 ⎤ 0 3 1 0 0 1⎥ ⎥ 1⎥ ⎦ 3 0 To solve the corresponding system of equations x1 + 3x2 − 2x3 + 2 x5 x3 + 2x4 =0 + 3x6 = 1 x6 = 1 3 we proceed as follows: Step 1. Solve the equations for the leading variables. x1 = −3x2 + 2x3 − 2x5 x3 = 1 − 2x4 − 3x6 x6 = 1 3 Step 2. Beginning with the bottom equation and working upward, successively substitute each equation into all the equations above it. Substituting x6 = 13 into the second equation yields x1 = −3x2 + 2x3 − 2x5 x3 = −2x4 x6 = 1 3 Substituting x3 = −2x4 into the ﬁrst equation yields x1 = −3x2 − 4x4 − 2x5 x3 = −2x4 x6 = 1 3 Step 3. Assign arbitrary values to the free variables, if any. If we now assign x2 , x4 , and x5 the arbitrary values r , s , and t , respectively, the general solution is given by the formulas x1 = −3r − 4s − 2t, x2 = r, x3 = −2s, x4 = s, x5 = t, x6 = 1 3 This agrees with the solution obtained in Example 5. EXAMPLE 8 Suppose that the matrices below are augmented matrices for linear systems in the unknowns x1 , x2 , x3 , and x4 . These matrices are all in row echelon form but not reduced row echelon form. Discuss the existence and uniqueness of solutions to the corresponding linear systems 1.2 Gaussian Elimination ⎡ 1 ⎢0 ⎢ (a) ⎢ ⎣0 0 −3 1 0 0 7 2 1 0 2 −4 6 0 ⎤ 5 1⎥ ⎥ ⎥ 9⎦ 1 ⎡ 1 ⎢0 ⎢ (b) ⎢ ⎣0 0 −3 1 0 0 7 2 1 0 2 −4 6 0 ⎤ 5 1⎥ ⎥ ⎥ 9⎦ 0 ⎡ 1 ⎢0 ⎢ (c) ⎢ ⎣0 0 −3 1 0 0 7 2 1 0 2 −4 6 1 21 ⎤ 5 1⎥ ⎥ ⎥ 9⎦ 0 Solution (a) The last row corresponds to the equation 0x1 + 0x2 + 0x3 + 0x4 = 1 from which it is evident that the system is inconsistent. Solution (b) The last row corresponds to the equation 0x1 + 0x2 + 0x3 + 0x4 = 0 which has no effect on the solution set. In the remaining three equations the variables x1 , x2 , and x3 correspond to leading 1’s and hence are leading variables. The variable x4 is a free variable. With a little algebra, the leading variables can be expressed in terms of the free variable, and the free variable can be assigned an arbitrary value. Thus, the system must have inﬁnitely many solutions. Solution (c) The last row corresponds to the equation x4 = 0 which gives us a numerical value for x4 . If we substitute this value into the third equation, namely, x3 + 6x4 = 9 we obtain x3 = 9. You should now be able to see that if we continue this process and substitute the known values of x3 and x4 into the equation corresponding to the second row, we will obtain a unique numerical value for x2 ; and if, ﬁnally, we substitute the known values of x4 , x3 , and x2 into the equation corresponding to the ﬁrst row, we will produce a unique numerical value for x1 . Thus, the system has a unique solution. Some Facts About Echelon Forms There are three facts about row echelon forms and reduced row echelon forms that are important to know but we will not prove: 1. Every matrix has a unique reduced row echelon form; that is, regardless of whether you use Gauss–Jordan elimination or some other sequence of elementary row operations, the same reduced row echelon form will result in the end.* 2. Row echelon forms are not unique; that is, different sequences of elementary row operations can result in different row echelon forms. 3. Although row echelon forms are not unique, the reduced row echelon form and all row echelon forms of a matrix A have the same number of zero rows, and the leading 1’s always occur in the same positions. Those are called the pivot positions of A. A column that contains a pivot position is called a pivot column of A. * A proof of this result can be found in the article “The Reduced Row Echelon Form of a Matrix Is Unique: A Simple Proof,” by Thomas Yuster, Mathematics Magazine, Vol. 57, No. 2, 1984, pp. 93–94. 22 Chapter 1 Systems of Linear Equations and Matrices E X A M P L E 9 Pivot Positions and Columns Earlier in this section (immediately after Deﬁnition 1) we found a row echelon form of ⎡ 0 ⎢ A = ⎣2 2 If A is the augmented matrix for a linear system, then the pivot columns identify the leading variables. As an illustration, in Example 5 the pivot columns are 1, 3, and 6, and the leading variables are x1 , x3 , and x6 . ⎡ to be 0 4 4 1 ⎢ ⎣0 0 2 0 0 ⎤ −2 −10 −5 0 6 6 7 12 −5 12 ⎥ 28⎦ −1 −5 3 0 0 6 14 ⎥ −6 ⎦ 2 1 0 − 27 1 ⎤ The leading 1’s occur in positions (row 1, column 1), (row 2, column 3), and (row 3, column 5). These are the pivot positions. The pivot columns are columns 1, 3, and 5. Roundoff Error and Instability There is often a gap between mathematical theory and its practical implementation— Gauss–Jordan elimination and Gaussian elimination being good examples. The problem is that computers generally approximate numbers, thereby introducing roundoff errors, so unless precautions are taken, successive calculations may degrade an answer to a degree that makes it useless. Algorithms (procedures) in which this happens are called unstable. There are various techniques for minimizing roundoff error and instability. For example, it can be shown that for large linear systems Gauss–Jordan elimination involves roughly 50% more operations than Gaussian elimination, so most computer algorithms are based on the latter method. Some of these matters will be considered in Chapter 9. Exercise Set 1.2 ⎡ In Exercises 1–2, determine whether the matrix is in row echelon form, reduced row echelon form, both, or neither. ⎡ 1 ⎢ 1. (a) ⎣0 0 (d) ⎤ 0 1 0 ⎡ 0 ⎥ 0⎦ 1 1 ⎢ (b) ⎣0 0 1 0 3 1 0 1 2 4 ⎡ 0 ⎢ (f ) ⎣0 0 ⎡ 0 ⎢0 ⎢ ⎣0 0 ⎥ 0⎦ (g) 0 ⎤ 2 0 1 0⎦ 0 0 ⎡ ⎥ ⎤ 5 1 −3 0 0 0 ⎥ 1⎦ ⎡ 0 ⎢ (c) ⎣0 0 ⎤ 1 0 0 0 0 ⎥ 1⎦ 0 ⎤ 2 0 3 0 1 1 0 0 0 ⎥ 1⎦ 0 0 0 0 −7 5 5 0 1 3 2 ⎤ 1 0 0 1 0⎦ 2 0 ⎥ ⎡ 1 ⎢ (e) ⎣0 0 ⎡ ⎤ 3 4 0 1⎦ 0 0 2 3 0 0⎦ 0 1 ⎥ ⎥ ⎤ 2 3 4 5 0 7 1 0 0 0 1⎦ 0 0 0 0 3⎥ ⎥ ⎥ (g) 1 −2 0 1 0 0 1 −2 In Exercises 3–4, suppose that the augmented matrix for a linear system has been reduced by row operations to the given row echelon form. Solve the system. ⎤ 1 −3 4 7 3. (a) ⎣0 0 1 2 2⎦ 0 1 5 1 0 8 6 (b) ⎣0 0 1 4 −5 −9 0 1 1 2 1 ⎢0 ⎢ (c) ⎢ ⎣0 0 7 0 0 0 −2 −8 1 0 0 0 1 1 0 1 ⎢ (d) ⎣0 0 −3 7 4 0 1 ⎥ 0⎦ 1 ⎡ ⎢ 1 ⎤ 0 ⎢ (c) ⎣0 0 ⎢ ⎢1 ⎢ (f ) ⎢ ⎣0 ⎡ 0⎥ ⎥ 1 (b) ⎣0 0 ⎢ ⎢ (d) ⎣0 1 1 (e) ⎢ 1 ⎡ 0 ⎥ 0⎦ 0 ⎡ ⎤ 2. (a) ⎣0 0 ⎢ 0 1 0 ⎤ 1 ⎡ ⎡ 1 0 ⎥ ⎤ ⎤ ⎥ 3⎦ 6 3 0 ⎤ −3 5⎥ ⎥ ⎥ 9⎦ 0 1.2 Gaussian Elimination ⎡ 1 ⎤ −3 ⎥ 0⎦ 17. 3x1 + x2 + x3 + x4 = 0 5x1 − x2 + x3 − x4 = 0 0 0 1 0 0 0 1 1 ⎢ (b) ⎣0 0 0 1 0 0 0 1 −7 3 1 8 ⎥ 2⎦ −5 1 ⎢0 ⎢ (c) ⎢ ⎣0 0 −6 0 1 0 0 0 0 1 0 3 4 5 0 1 −3 0 0 0 0 1 0 0 ⎥ 0⎦ 1 ⎢ 4. (a) ⎣0 ⎡ ⎡ ⎡ ⎢ (d) ⎣0 0 0 0 7 ⎤ −2 ⎤ 7⎥ ⎥ ⎥ 8⎦ 0 In Exercises 5–8, solve the linear system by Gaussian elimination. 5. x1 + x2 + 2x3 = 8 −x1 − 2x2 + 3x3 = 1 3x1 − 7x2 + 4x3 = 10 7. x − y + 2z − w 2x + y − 2z − 2w −x + 2y − 4z + w − 3w 3x 8. − 2b + 3c = 1 3a + 6b − 3c = −2 6a + 6b + 3c = 5 2u + v − 4w + 3x = 0 2u + 3v + 2w − x = 0 −4u − 3v + 5w − 4x = 0 6. 2x1 + 2x2 + 2x3 = 0 −2x1 + 5x2 + 2x3 = 1 8x1 + x2 + 4x3 = −1 20. x1 + 3x2 x1 + 4x2 − 2x2 2x1 − 4x2 x1 − 2x2 + 4z = 0 − 3z = 0 + z=0 − 2z = 0 + 2x3 − 2x3 + x3 − x3 + x4 = 0 =0 − x4 = 0 + x4 = 0 + x4 = 0 21. 2I1 − I2 + 3I3 I1 − 2I3 3I1 − 3I2 + I3 2I1 + I2 + 4I3 22. = −1 = −2 = 1 = −3 + 2y − y + y + 3y 2x w 2 w + 3x −2 w + x + 4I4 + 7I4 + 5I4 + 4I4 v + 3w − 2 x = 0 18. ⎤ 19. 23 = 9 = 11 = 8 = 10 Z3 + Z4 −Z1 − Z2 + 2Z3 − 3Z4 Z1 + Z2 − 2Z3 2Z1 + 2Z2 − Z3 + Z5 + Z5 − Z5 + Z5 =0 =0 =0 =0 In each part of Exercises 23–24, the augmented matrix for a linear system is given in which the asterisk represents an unspeciﬁed real number. Determine whether the system is consistent, and if so whether the solution is unique. Answer “inconclusive” if there is not enough information to make a decision. In Exercises 9–12, solve the linear system by Gauss–Jordan elimination. 9. Exercise 5 10. Exercise 6 11. Exercise 7 12. Exercise 8 In Exercises 13–14, determine whether the homogeneous system has nontrivial solutions by inspection (without pencil and paper). ⎡ 1 23. (a) ⎣0 0 ⎡ 1 (c) ⎣0 0 ⎡ 1 24. (a) ⎣0 0 13. 2x1 − 3x2 + 4x3 − x4 = 0 7x1 + x2 − 8x3 + 9x4 = 0 2x1 + 8x2 + x3 − x4 = 0 ⎡ 1 (c) ⎣1 1 14. x1 + 3x2 − x3 = 0 x2 − 8x3 = 0 4 x3 = 0 ∗ 1 0 ∗ 1 0 ∗ 1 0 ∗ ∗ ⎤ ∗ ∗⎦ ∗ ⎤ ∗ ∗⎦ 0 1 ∗ ∗ ⎤ ∗ ∗⎦ 1 1 ∗ ∗ 1 ⎤ 0 0 0 0 0 1⎦ ∗ ∗ ∗ ⎡ 1 (b) ⎣0 0 ⎡ 1 (d) ⎣0 0 ⎡ ∗ 1 0 ∗ 0 0 ∗ ∗ ⎤ ∗ ∗⎦ 0 0 ∗ ∗ ⎤ ∗ 0⎦ ∗ 1 1 0 1 ∗ ⎡ ∗ 0 0 1 ∗ ∗ 0 0 0 0 (b) ⎣∗ 1 (d) ⎣1 1 ⎤ ∗ ∗⎦ ∗ ⎤ ∗ 1⎦ 1 In Exercises 15–22, solve the given linear system by any method. In Exercises 25–26, determine the values of a for which the system has no solutions, exactly one solution, or inﬁnitely many solutions. 15. 2x1 + x2 + 3x3 = 0 x1 + 2x2 =0 x2 + x3 = 0 25. x + 2y − 3z = 4 5z = 2 3x − y + 4x + y + (a 2 − 14)z = a + 2 16. 2x − y − 3z = 0 −x + 2y − 3z = 0 x + y + 4z = 0 24 Chapter 1 Systems of Linear Equations and Matrices 26. x + 2y + z=2 3z = 1 2x − 2y + x + 2y − (a 2 − 3)z = a 36. Solve the following system for x, y, and z. 1 x 2 In Exercises 27–28, what condition, if any, must a , b, and c satisfy for the linear system to be consistent? 27. x + 3y − z = a x + y + 2z = b 2 y − 3z = c 28. x + 3y + z = a −x − 2y + z = b 3x + 7y − z = c In Exercises 29–30, solve the following systems, where a , b, and c are constants. 29. 2x + y = a x − + y 3 y 9 y − 4 + 8 + 10 20 (0, 10) 2 7 (1, 7) ⎡ 2 (3, –11) –20 1 ⎢ ⎣0 −2 3 4 (4, –14) Figure Ex37 This exercise shows that a matrix can have multiple row echelon forms. 32. Reduce =5 x 3 z =0 6 31. Find two different row echelon forms of 1 z =1 y –2 z y = ax 3 + bx 2 + cx + d. + 2x3 = b 3x2 + 3x3 = c 2x1 + 2 37. Find the coefﬁcients a, b, c, and d so that the curve shown in the accompanying ﬁgure is the graph of the equation 30. x1 + x2 + x3 = a 3x + 6y = b 1 x + 3 ⎤ ⎥ −29⎦ 38. Find the coefﬁcients a, b, c, and d so that the circle shown in the accompanying ﬁgure is given by the equation ax 2 + ay 2 + bx + cy + d = 0. y (–2, 7) (–4, 5) 5 to reduced row echelon form without introducing fractions at any intermediate stage. x 33. Show that the following nonlinear system has 18 solutions if 0 ≤ α ≤ 2π , 0 ≤ β ≤ 2π , and 0 ≤ γ ≤ 2π . sin α + 2 cos β + 3 tan γ = 0 2 sin α + 5 cos β + 3 tan γ = 0 − sin α − 5 cos β + 5 tan γ = 0 [Hint: Begin by making the substitutions x = sin α , y = cos β , and z = tan γ .] 34. Solve the following system of nonlinear equations for the unknown angles α , β , and γ , where 0 ≤ α ≤ 2π , 0 ≤ β ≤ 2π , and 0 ≤ γ < π . 2 sin α − cos β + 3 tan γ = 3 4 sin α + 2 cos β − 2 tan γ = 2 6 sin α − 3 cos β + tan γ = 9 35. Solve the following system of nonlinear equations for x, y, and z. x 2 + y 2 + z2 = 6 x 2 − y 2 + 2z 2 = 2 2x 2 + y 2 − z 2 = 3 [Hint: Begin by making the substitutions X = x 2 , Y = y 2 , Z = z 2 .] (4, –3) Figure Ex38 39. If the linear system a1 x + b1 y + c1 z = 0 a2 x − b2 y + c2 z = 0 a3 x + b3 y − c3 z = 0 has only the trivial solution, what can be said about the solutions of the following system? a1 x + b1 y + c1 z = 3 a2 x − b2 y + c2 z = 7 a3 x + b3 y − c3 z = 11 40. (a) If A is a matrix with three rows and ﬁve columns, then what is the maximum possible number of leading 1’s in its reduced row echelon form? (b) If B is a matrix with three rows and six columns, then what is the maximum possible number of parameters in the general solution of the linear system with augmented matrix B ? (c) If C is a matrix with ﬁve rows and three columns, then what is the minimum possible number of rows of zeros in any row echelon form of C ? 1.3 Matrices and Matrix Operations 41. Describe all possible reduced row echelon forms of ⎡ a ⎢ (a) ⎣d g b e h ⎡ ⎤ c ⎥ f⎦ i a ⎢e ⎢ (b) ⎢ ⎣i m b f j n c g k p ⎤ d h⎥ ⎥ ⎥ l⎦ q 42. Consider the system of equations ax + by = 0 cx + dy = 0 ex + fy = 0 Discuss the relative positions of the lines ax + by = 0, cx + dy = 0, and ex + fy = 0 when the system has only the trivial solution and when it has nontrivial solutions. Working with Proofs 43. (a) Prove that if ad − bc = 0, then the reduced row echelon form of a b 1 0 is c d 0 1 (b) Use the result in part (a) to prove that if ad − bc = 0, then the linear system ax + by = k cx + dy = l has exactly one solution. 25 (d) A homogeneous linear system in n unknowns whose corresponding augmented matrix has a reduced row echelon form with r leading 1’s has n − r free variables. (e) All leading 1’s in a matrix in row echelon form must occur in different columns. (f ) If every column of a matrix in row echelon form has a leading 1, then all entries that are not leading 1’s are zero. (g) If a homogeneous linear system of n equations in n unknowns has a corresponding augmented matrix with a reduced row echelon form containing n leading 1’s, then the linear system has only the trivial solution. (h) If the reduced row echelon form of the augmented matrix for a linear system has a row of zeros, then the system must have inﬁnitely many solutions. (i) If a linear system has more unknowns than equations, then it must have inﬁnitely many solutions. Working withTechnology T1. Find the reduced row echelon form of the augmented matrix for the linear system: + 4x4 = −3 6x1 + x2 −9x1 + 2x2 + 3x3 − 8x4 = 1 − 4x3 + 5x4 = 2 7x1 Use your result to determine whether the system is consistent and, if so, ﬁnd its solution. TrueFalse Exercises TF. In parts (a)–(i) determine whether the statement is true or false, and justify your answer. (a) If a matrix is in reduced row echelon form, then it is also in row echelon form. (b) If an elementary row operation is applied to a matrix that is in row echelon form, the resulting matrix will still be in row echelon form. (c) Every matrix has a unique row echelon form. T2. Find values of the constants A, B , C , and D that make the following equation an identity (i.e., true for all values of x ). C D 3x 3 + 4x 2 − 6x Ax + B + + = 2 (x 2 + 2x + 2)(x 2 − 1) x + 2x + 2 x − 1 x + 1 [Hint: Obtain a common denominator on the right, and then equate corresponding coefﬁcients of the various powers of x in the two numerators. Students of calculus will recognize this as a problem in partial fractions.] 1.3 Matrices and Matrix Operations Rectangular arrays of real numbers arise in contexts other than as augmented matrices for linear systems. In this section we will begin to study matrices as objects in their own right by deﬁning operations of addition, subtraction, and multiplication on them. Matrix Notation and Terminology In Section 1.2 we used rectangular arrays of numbers, called augmented matrices, to abbreviate systems of linear equations. However, rectangular arrays of numbers occur in other contexts as well. For example, the following rectangular array with three rows and seven columns might describe the number of hours that a student spent studying three subjects during a certain week: 26 Chapter 1 Systems of Linear Equations and Matrices Math History Language Mon. Tues. Wed. Thurs. Fri. Sat. Sun. 2 0 4 3 3 1 2 1 3 4 4 1 1 3 0 4 2 0 2 2 2 If we suppress the headings, then we are left with the following rectangular array of numbers with three rows and seven columns, called a “matrix”: ⎡ 2 ⎢ ⎣0 4 3 3 1 2 1 3 4 4 1 1 3 0 ⎤ 4 2 0 2 ⎥ 2⎦ 2 More generally, we make the following deﬁnition. DEFINITION 1 A matrix is a rectangular array of numbers. The numbers in the array are called the entries in the matrix. E X A M P L E 1 Examples of Matrices Matrix brackets are often omitted from 1 × 1 matrices, making it impossible to tell, for example, whether the symbol 4 denotes the number “four” or the matrix [4]. This rarely causes problems because it is usually possible to tell which is meant from the context. Some examples of matrices are ⎡ 1 ⎣ 3 −1 ⎡ ⎤ 2 0⎦, [2 4 1 e ⎢ − 3], ⎣0 0 0 √ ⎤ − 2 ⎥ 1 ⎦, π 1 2 0 0 1 , [4] 3 The size of a matrix is described in terms of the number of rows (horizontal lines) and columns (vertical lines) it contains. For example, the ﬁrst matrix in Example 1 has three rows and two columns, so its size is 3 by 2 (written 3 × 2). In a size description, the ﬁrst number always denotes the number of rows, and the second denotes the number of columns. The remaining matrices in Example 1 have sizes 1 × 4, 3 × 3, 2 × 1, and 1 × 1, respectively. A matrix with only one row, such as the second in Example 1, is called a row vector (or a row matrix), and a matrix with only one column, such as the fourth in that example, is called a column vector (or a column matrix). The ﬁfth matrix in that example is both a row vector and a column vector. We will use capital letters to denote matrices and lowercase letters to denote numerical quantities; thus we might write A= 2 3 1 4 7 2 or C = a d b e c f When discussing matrices, it is common to refer to numerical quantities as scalars. Unless stated otherwise, scalars will be real numbers; complex scalars will be considered later in the text. The entry that occurs in row i and column j of a matrix A will be denoted by aij . Thus a general 3 × 4 matrix might be written as 1.3 Matrices and Matrix Operations ⎡ a11 ⎢ A = ⎣a21 a31 and a general m × n matrix as ⎡ a11 ⎢a ⎢ 21 A=⎢ . ⎣ .. am1 A matrix with n rows and n columns is said to be a square matrix of order n. a12 a22 a32 a13 a23 a33 a12 a22 .. . ··· ··· am2 27 ⎤ a14 ⎥ a24 ⎦ a34 ··· ⎤ a1n a2 n ⎥ ⎥ .. ⎥ . ⎦ amn (1) When a compact notation is desired, the preceding matrix can be written as [aij ]m×n or [aij ] the ﬁrst notation being used when it is important in the discussion to know the size, and the second when the size need not be emphasized. Usually, we will match the letter denoting a matrix with the letter denoting its entries; thus, for a matrix B we would generally use bij for the entry in row i and column j , and for a matrix C we would use the notation cij . The entry in row i and column j of a matrix A is also commonly denoted by the symbol (A)ij . Thus, for matrix (1) above, we have (A)ij = aij and for the matrix 2 −3 7 0 we have (A)11 = 2, (A)12 = −3, (A)21 = 7, and (A)22 = 0. Row and column vectors are of special importance, and it is common practice to denote them by boldface lowercase letters rather than capital letters. For such matrices, double subscripting of the entries is unnecessary. Thus a general 1 × n row vector a and a general m × 1 column vector b would be written as A= ⎤ b1 ⎢b ⎥ ⎢ 2⎥ · · · an ] and b = ⎢ .. ⎥ ⎣ . ⎦ bm ⎡ a = [a1 a2 A matrix A with n rows and n columns is called a square matrix of order n, and the shaded entries a11 , a22 , . . . , ann in (2) are said to be on the main diagonal of A. ⎡ ⎢ ⎢ ⎢ ⎣ Operations on Matrices a11 a21 .. . an1 a12 a22 .. . an2 ··· ··· a1n a2n .. . · · · ann ⎤ ⎥ ⎥ ⎥ ⎦ (2) So far, we have used matrices to abbreviate the work in solving systems of linear equations. For other applications, however, it is desirable to develop an “arithmetic of matrices” in which matrices can be added, subtracted, and multiplied in a useful way. The remainder of this section will be devoted to developing this arithmetic. DEFINITION 2 Two matrices are deﬁned to be equal if they have the same size and their corresponding entries are equal. 28 Chapter 1 Systems of Linear Equations and Matrices E X A M P L E 2 Equality of Matrices The equality of two matrices Consider the matrices A= A = [aij ] and B = [bij ] of the same size can be expressed either by writing (A)ij = (B)ij or by writing aij = bij where it is understood that the equalities hold for all values of i and j . 2 3 1 , B= x 2 3 1 2 , C= 5 3 1 4 0 0 If x = 5, then A = B , but for all other values of x the matrices A and B are not equal, since not all of their corresponding entries are equal. There is no value of x for which A = C since A and C have different sizes. DEFINITION 3 If A and B are matrices of the same size, then the sum A + B is the matrix obtained by adding the entries of B to the corresponding entries of A, and the difference A − B is the matrix obtained by subtracting the entries of B from the corresponding entries of A. Matrices of different sizes cannot be added or subtracted. In matrix notation, if A = [aij ] and B = [bij ] have the same size, then (A + B)ij = (A)ij + (B)ij = aij + bij and (A − B)ij = (A)ij − (B)ij = aij − bij E X A M P L E 3 Addition and Subtraction Consider the matrices ⎡ Then ⎤ ⎡ 1 0 −2 0 2 7 −4 3 ⎥ ⎢ 4⎦, B = ⎣ 2 0 3 −2 4 2 0 5 2 3 2 ⎢ A = ⎣−1 4 ⎡ ⎢ A+B =⎣ 1 7 3 2 2 ⎤ 5 0 −4 ⎤ 1 1 ⎥ −1⎦, C = 2 5 ⎡ 4 6 ⎥ ⎢ 3⎦ and A − B = ⎣−3 5 1 −2 −2 −4 −5 2 11 1 2 ⎤ 2 ⎥ 5⎦ −5 The expressions A + C , B + C , A − C , and B − C are undeﬁned. DEFINITION 4 If A is any matrix and c is any scalar, then the product cA is the matrix obtained by multiplying each entry of the matrix A by c. The matrix cA is said to be a scalar multiple of A. In matrix notation, if A = [aij ], then (cA)ij = c(A)ij = caij E X A M P L E 4 Scalar Multiples For the matrices 2 1 A= 3 3 4 0 , B= −1 1 2 3 7 9 , C= −5 3 −6 3 12 0 we have 2A = 4 2 6 6 8 0 , (−1)B = 2 1 −2 −7 , −3 5 It is common practice to denote (−1)B by −B . 1 C 3 = 3 1 −2 0 1 4 1.3 Matrices and Matrix Operations 29 Thus far we have deﬁned multiplication of a matrix by a scalar but not the multiplication of two matrices. Since matrices are added by adding corresponding entries and subtracted by subtracting corresponding entries, it would seem natural to deﬁne multiplication of matrices by multiplying corresponding entries. However, it turns out that such a deﬁnition would not be very useful for most problems. Experience has led mathematicians to the following more useful deﬁnition of matrix multiplication. A is an m × r matrix and B is an r × n matrix, then the product AB is the m × n matrix whose entries are determined as follows: To ﬁnd the entry in row i and column j of AB , single out row i from the matrix A and column j from the matrix B . Multiply the corresponding entries from the row and column together, DEFINITION 5 If and then add up the resulting products. E X A M P L E 5 Multiplying Matrices Consider the matrices A= ⎡ 1 2 2 6 4 4 ⎢ , B = ⎣0 0 2 1 −1 7 ⎤ 4 3 5 3 ⎥ 1⎦ 2 Since A is a 2 × 3 matrix and B is a 3 × 4 matrix, the product AB is a 2 × 4 matrix. To determine, for example, the entry in row 2 and column 3 of AB , we single out row 2 from A and column 3 from B . Then, as illustrated below, we multiply corresponding entries together and add up these products. ⎡ 4 1 2 4 ⎢ ⎣0 2 6 0 2 1 1 7 4 3 5 ⎤ ⎡ 3 ⎥ ⎢ 1⎦ = ⎣ 2 ⎤ ⎥ ⎦ 26 (2 · 4) + (6 · 3) + (0 · 5) = 26 The entry in row 1 and column 4 of AB is computed as follows: ⎡ 4 1 2 4 ⎢ ⎣0 2 6 0 2 1 1 7 4 3 5 ⎤ ⎡ 3 ⎥ ⎢ 1⎦ = ⎣ 2 ⎤ 13 ⎥ ⎦ (1 · 3) + (2 · 1) + (4 · 2) = 13 The computations for the remaining entries are (1 · 4) + (2 · 0) + (4 · 2) = 12 (1 · 1) − (2 · 1) + (4 · 7) = 27 (1 · 4) + (2 · 3) + (4 · 5) = 30 (2 · 4) + (6 · 0) + (0 · 2) = 8 (2 · 1) − (6 · 1) + (0 · 7) = −4 (2 · 3) + (6 · 1) + (0 · 2) = 12 AB = 12 8 27 −4 30 26 13 12 The deﬁnition of matrix multiplication requires that the number of columns of the ﬁrst factor A be the same as the number of rows of the second factor B in order to form the product AB . If this condition is not satisﬁed, the product is undeﬁned. A convenient 30 Chapter 1 Systems of Linear Equations and Matrices way to determine whether a product of two matrices is deﬁned is to write down the size of the ﬁrst factor and, to the right of it, write down the size of the second factor. If, as in (3), the inside numbers are the same, then the product is deﬁned. The outside numbers then give the size of the product. A m × r B r × n = AB m × n (3) Inside Outside E X A M P L E 6 Determining Whether a Product Is Deﬁned Suppose that A, B , and C are matrices with the following sizes: A B C 3×4 4×7 7×3 Then by (3), AB is deﬁned and is a 3 × 7 matrix; BC is deﬁned and is a 4 × 3 matrix; and CA is deﬁned and is a 7 × 4 matrix. The products AC , CB , and BA are all undeﬁned. In general, if A = [aij ] is an m × r matrix and B = [bij ] is an r × n matrix, then, as illustrated by the shading in the following display, ⎡ a11 ⎢a ⎢ 21 ⎢ . ⎢ .. AB = ⎢ ⎢ ai 1 ⎢ . ⎢ . ⎣ . a12 a22 .. . ai 2 .. . am1 am2 ··· ··· ··· ··· a1r a2r .. . air .. . ⎤ ⎥ ⎡b ⎥ 11 ⎥⎢ ⎥ ⎢b21 ⎥⎢ . ⎥⎣ . ⎥ . ⎥ ⎦ br 1 b12 b22 .. . · · · b1 j · · · b2 j .. . br 2 br j ··· ⎤ · · · b1n · · · b2n ⎥ ⎥ .. ⎥ . ⎦ · · · br n (4) amr the entry (AB)ij in row i and column j of AB is given by (AB)ij = ai 1 b1j + ai 2 b2j + ai 3 b3j + · · · + air brj (5) Formula (5) is called the rowcolumn rule for matrix multiplication. Partitioned Matrices A matrix can be subdivided or partitioned into smaller matrices by inserting horizontal and vertical rules between selected rows and columns. For example, the following are three possible partitions of a general 3 × 4 matrix A—the ﬁrst is a partition of A into Gotthold Eisenstein (1823–1852) Historical Note The concept of matrix multiplication is due to the German mathematician Gotthold Eisenstein, who introduced the idea around 1844 to simplify the process of making substitutions in linear systems. The idea was then expanded on and formalized by Cayley in his Memoir on the Theory of Matrices that was published in 1858. Eisenstein was a pupil of Gauss, who ranked him as the equal of Isaac Newton and Archimedes. However, Eisenstein, suffering from bad health his entire life, died at age 30, so his potential was never realized. [Image: http://wwwhistory.mcs.standrews.ac.uk/ Biographies/Eisenstein.html] 1.3 Matrices and Matrix Operations 31 four submatrices A11 , A12 , A21 , and A22 ; the second is a partition of A into its row vectors r1 , r2 , and r3 ; and the third is a partition of A into its column vectors c1 , c2 , c3 , and c4 : ⎡ a11 ⎢ A = ⎣a21 a31 ⎡ a11 ⎢ A = ⎣a21 a31 ⎡ a11 ⎢ A = ⎣a21 a31 Matrix Multiplication by Columns and by Rows a12 a22 a32 a13 a23 a33 a12 a22 a32 a13 a23 a33 a12 a22 a32 a13 a23 a33 ⎤ a14 A11 A12 ⎥ a24 ⎦ = A21 A22 a34 ⎤ ⎡ ⎤ a14 r1 ⎥ ⎢ ⎥ a24 ⎦ = ⎣r2 ⎦ a34 r3 ⎤ a14 ⎥ a24 ⎦ = [c1 c2 c3 a34 c4 ] Partitioning has many uses, one of which is for ﬁnding particular rows or columns of a matrix product AB without computing the entire product. Speciﬁcally, the following formulas, whose proofs are left as exercises, show how individual column vectors of AB can be obtained by partitioning B into column vectors and how individual row vectors of AB can be obtained by partitioning A into row vectors. AB = A[b1 b2 · · · bn ] = [Ab1 Ab2 · · · Abn ] (6) (AB computed column by column) ⎡ ⎤ a1 ⎢a ⎥ ⎢ 2⎥ ⎡ ⎤ a1 B ⎢a B ⎥ ⎢ 2 ⎥ AB = ⎢ . ⎥B = ⎢ . ⎥ ⎣ .. ⎦ ⎣ .. ⎦ am am B (7) (AB computed row by row) We now have three methods for computing a product of two matrices, entry by entry using Deﬁnition 5, column by column using Formula (8), and row by row using Formula (9). We will call these the entry method , the row method , and the column method , respectively. In words, these formulas state that j th column vector of AB = A[ j th column vector of B] (8) i th row vector of AB = [i th row vector of A]B (9) E X A M P L E 7 Example 5 Revisited If A and B are the matrices in Example 5, then from (8) the second column vector of AB can be obtained by the computation ⎡ 1 2 2 6 ⎤ 1 4 ⎢ ⎥ ⎣−1⎦ 0 7 27 −4 Second column of B = Second column of AB 32 Chapter 1 Systems of Linear Equations and Matrices and from (9) the ﬁrst row vector of AB can be obtained by the computation ⎡ [1 2 4 ⎢ 4 ]⎣0 2 1 1 7 4 3 5 ⎤ 3 ⎥ 1⎦ = 2 [ 12 27 30 13 ] First row of A Matrix Products as Linear Combinations Deﬁnition 6 is applicable, in particular, to row and column vectors. Thus, for example, a linear combination of column vectors x1 , x2 , . . . , xr of the same size is an expression of the form c1 x1 + c2 x2 + · · · + cr xr First row of AB The following deﬁnition provides yet another way of thinking about matrix multiplication. DEFINITION 6 If A1 , A2 , . . . , Ar are matrices of the same size, and if c1 , c2 , . . . , cr are scalars, then an expression of the form c 1 A1 + c 2 A2 + · · · + c r Ar is called a linear combination of A1 , A2 , . . . , Ar with coefﬁcients c1 , c2 , . . . , cr . To see how matrix products can be viewed as linear combinations, let A be an m × n matrix and x an n × 1 column vector, say ⎡ a12 a22 .. . a11 ⎢a ⎢ 21 A=⎢ . ⎣ .. am 1 Then am2 ⎤ ⎡ ⎤ a1n x1 ⎢x ⎥ a2 n ⎥ ⎥ ⎢ 2⎥ .. ⎥ and x = ⎢ .. ⎥ ⎦ ⎣.⎦ . xn · · · amn ··· ··· ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ a11 x1 + a12 x2 + · · · + a1n xn a11 a12 a1n ⎢a x + a x +···+ a x ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 21 1 ⎢ a21 ⎥ ⎢ a22 ⎥ ⎢ a2n ⎥ 22 2 2n n ⎥ Ax = ⎢ . ⎥ = x1 ⎢ . ⎥ + x2 ⎢ . ⎥ + · · · + xn ⎢ . ⎥ . . .. .. ⎦ ⎣ .. ⎣ .. ⎦ ⎣ .. ⎦ ⎣ .. ⎦ am1 x1 + am2 x2 + · · · + amn xn a m1 am2 amn (10) This proves the following theorem. THEOREM 1.3.1 If A is an m × n matrix, and if x is an n × 1 column vector, then the product Ax can be expressed as a linear combination of the column vectors of A in which the coefﬁcients are the entries of x. E X A M P L E 8 Matrix Products as Linear Combinations The matrix product ⎡ −1 3 2 2 1 ⎢ ⎣ 1 2 ⎤⎡ 2 ⎤ ⎡ ⎤ 1 ⎥⎢ ⎥ ⎢ ⎥ −3⎦ ⎣−1⎦ = ⎣−9⎦ −2 −3 3 can be written as the following linear combination of column vectors: ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ −1 3 2 1 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ − 3 − 1 2 2 ⎣ ⎦ − 1 ⎣ ⎦ + 3 ⎣ ⎦ = ⎣ 9⎦ −2 −3 2 1 1.3 Matrices and Matrix Operations 33 E X A M P L E 9 Columns of a Product AB as Linear Combinations We showed in Example 5 that ⎡ AB = 1 2 2 6 4 4 ⎢ ⎣0 0 2 ⎤ 1 4 3 −1 3 1⎦ = 7 5 2 ⎥ 12 27 30 13 8 −4 26 12 It follows from Formula (6) and Theorem 1.3.1 that the j th column vector of AB can be expressed as a linear combination of the column vectors of A in which the coefﬁcients in the linear combination are the entries from the j th column of B . The computations are as follows: 12 =4 8 27 −4 30 1 = 2 ColumnRow Expansion 2 1 2 6 +2 2 − 6 2 +3 6 +7 2 6 0 4 0 +5 + 4 =3 12 1 2 +0 13 2 =4 26 1 4 0 +2 4 0 Partitioning provides yet another way to view matrix multiplication. Speciﬁcally, suppose that an m × r matrix A is partitioned into its r column vectors c1 , c2 , . . . , cr (each of size m × 1) and an r × n matrix B is partitioned into its r row vectors r1 , r2 , . . . , rr (each of size 1 × n). Each term in the sum c1 r1 + c2 r2 + · · · + cr rr has size m × n so the sum itself is an m × n matrix. We leave it as an exercise for you to verify that the entry in row i and column j of the sum is given by the expression on the right side of Formula (5), from which it follows that AB = c1 r1 + c2 r2 + · · · + cr rr (11) We call (11) the columnrow expansion of AB . E X A M P L E 10 ColumnRow Expansion Find the columnrow expansion of the product AB = 1 3 2 −1 2 0 4 −3 5 1 (12) Solution The column vectors of A and the row vectors of B are, respectively, c1 = 1 2 , c2 = 3 −1 ; r1 = 2 0 4 , r2 = −3 5 1 34 Chapter 1 Systems of Linear Equations and Matrices Thus, it follows from (11) that the columnrow expansion of AB is 1 2 AB = 2 = The main use of the columnrow expansion is for developing theoretical results rather than for numerical computations. Matrix Form of a Linear System 4 + 0 2 0 4 4 0 8 + 3 −1 −3 5 1 −9 15 3 3 −5 −1 (13) As a check, we leave it for you to conﬁrm that the product in (12) and the sum in (13) both yield 7 −7 15 AB = 7 −5 7 Matrix multiplication has an important application to systems of linear equations. Consider a system of m linear equations in n unknowns: a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. .. .. .. . . . . am1 x1 + am2 x2 + · · · + amn xn = bm Since two matrices are equal if and only if their corresponding entries are equal, we can replace the m equations in this system by the single matrix equation ⎡ ⎤ ⎡ ⎤ a11 x1 + a12 x2 + · · · + a1n xn b1 ⎢ a x + a x + · · · + a x ⎥ ⎢b ⎥ 22 2 2n n ⎥ ⎢ 21 1 ⎢ 2⎥ ⎢ .. .. .. ⎥ = ⎢ .. ⎥ ⎣ . ⎦ ⎣ . ⎦ . . bm am1 x1 +