كتاب الجبر الخطي.pdf

WileyPLUS is a research-based 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...

WileyPLUS is a research-based 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 2-Minute Tutorials and all Student support from an Collaborate with your colleagues, of the resources you and your experienced student user find a mentor, attend virtual and live students need to get started events, and view resources www.WhereFacultyConnect.com Quick Start © Courtney Keating/iStockphoto Pre-loaded, ready-to-use Technical Support 24/7 assignments and presentations FAQs, online chat, Your WileyPLUS Account Manager, created by subject matter experts and phone support providing personal training www.wileyplus.com/support 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 Laurie Rosatone SENIOR ACQUISITIONS EDITOR David Dietz ASSOCIATE CONTENT EDITOR Jacqueline Sinacori FREELANCE DEVELOPMENT EDITOR Anne Scanlan-Rohrer MARKETING MANAGER Melanie Kurkjian EDITORIAL ASSISTANT Michael O’Neal SENIOR PRODUCT DESIGNER Thomas Kulesa SENIOR PRODUCTION EDITOR Ken Santor SENIOR CONTENT MANAGER Karoline Luciano OPERATIONS MANAGER Melissa Edwards SENIOR DESIGNER Maddy Lesure MEDIA SPECIALIST Laura Abrams PHOTO RESEARCH EDITOR Felicia Ruocco COPY EDITOR Lilian Brady PRODUCTION SERVICES Carol Sawyer/The Perfect Proof COVER ART 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 acid-free 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 per-copy 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 07030-5774, (201) 748-6011, fax (201) 748-6008, 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 qualified 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 Cataloging-in-Publication Data Anton, Howard, author. Elementary linear algebra : applications version / Howard Anton, Chris Rorres. -- 11th edition. pages cm Includes index. ISBN 978-1-118-43441-3 (cloth) 1. Algebras, Linear--Textbooks. I. Rorres, Chris, author. II. Title. QA184.2.A58 2013 512'.5--dc23 2013033542 ISBN 978-1-118-43441-3 ISBN Binder-Ready Version 978-1-118-47422-8 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 This textbook is an expanded version of Elementary Linear Algebra, eleventh edition, by Howard Anton. The first nine chapters of this book are identical to the first 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 flexibility 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 satisfied. 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 first 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 Summary of Changes in Many parts of the text have been revised based on an extensive set of reviews. Here are This Edition 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 flow of the text. Exercise Sets Reorganized Many multiple-part 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 defined 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 Chap- ter 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 reflect 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 mod- ules, three modules on linear programming, and an alternative presentation of deter- minants 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 three-module set on Linear vi  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 definitions 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 difficult 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 first nine chapters begins with routine drill problems and progresses to problems with more substance. These are followed by three categories of exercises, the first 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 identifi- 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 un- derstanding 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 files have been posted on the websites that accompany this text. Supplementary Exercises Each of the first nine chapters ends with a set of supplemen- tary exercises that draw on all topics in the chapter. These tend to be more challenging. Supplementary Materials Student Solutions Manual This supplement provides detailed solutions to most odd- for Students numbered exercises (ISBN 978-1-118-464427). Data Files Data files 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 specific proofs in the text. Supplementary Materials Instructor’s Solutions Manual This supplement provides worked-out solutions to most for Instructors exercises in the text (ISBN 978-1-118-434482). PowerPoint Presentations PowerPoint slides are provided that display important def- initions, 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 confidence 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 fit 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 Short 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 Chapter 4: General Vector Spaces 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 Total: 39 lectures 30 lectures Reviewers 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, Embry-Riddle 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 solu- tions 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 coordi- nation with this text. Sky Pelletier Waterpeace – who critiqued the technology exercises, suggested improve- ments, 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 Scanlan-Rohrer – 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 ben- eficiary 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 compo- sition, and resolved many difficult technical issues. Brian Haughwout – of Techsetters, Inc., for his careful and accurate work on the illustra- tions. 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 Introduction to Systems of Linear Equations 2 1.2 Gaussian Elimination 11 1.3 Matrices and Matrix Operations 25 1.4 Inverses; Algebraic Properties of Matrices 39 1.5 Elementary Matrices and a Method for Finding A−1 52 1.6 More on Linear Systems and Invertible Matrices 61 1.7 Diagonal, Triangular, and Symmetric Matrices 67 1.8 Matrix Transformations 75 1.9 Applications of Linear Systems 84 Network Analysis (Traffic Flow) 84 Electrical Circuits 86 Balancing Chemical Equations 88 Polynomial Interpolation 91 1.10 Application: Leontief Input-Output Models 96 C HA PT E R 2 Determinants 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 131 3.1 Vectors in 2-Space, 3-Space, and n-Space 131 3.2 Norm, Dot Product, and Distance in Rn 142 3.3 Orthogonality 155 3.4 The Geometry of Linear Systems 164 3.5 Cross Product 172 C HA PT E R 4 General Vector Spaces 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 248 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 280 x  Contents xi C HA PT E R 5 Eigenvalues and Eigenvectors 291 5.1 Eigenvalues and Eigenvectors 291 5.2 Diagonalization 302 5.3 Complex Vector Spaces 313 5.4 Application: Differential Equations 326 5.5 Application: Dynamical Systems and Markov Chains 332 C HA PT E R 6 Inner Product Spaces 345 6.1 Inner Products 345 6.2 Angle and Orthogonality in Inner Product Spaces 355 6.3 Gram–Schmidt Process; QR-Decomposition 364 6.4 Best Approximation; Least Squares 378 6.5 Application: Mathematical Modeling Using Least Squares 387 6.6 Application: Function Approximation; Fourier Series 394 C HA PT E R 7 Diagonalization and Quadratic Forms 401 7.1 Orthogonal Matrices 401 7.2 Orthogonal Diagonalization 409 7.3 Quadratic Forms 417 7.4 Optimization Using Quadratic Forms 429 7.5 Hermitian, Unitary, and Normal Matrices 437 C HA PT E R 8 General Linear Transformations 447 8.1 General Linear Transformations 447 8.2 Compositions and Inverse Transformations 458 8.3 Isomorphism 466 8.4 Matrices for General Linear Transformations 472 8.5 Similarity 481 C HA PT E R 9 Numerical Methods 491 9.1 LU-Decompositions 491 9.2 The Power Method 501 9.3 Comparison of Procedures for Solving Linear Systems 509 9.4 Singular Value Decomposition 514 9.5 Application: Data Compression Using Singular Value Decomposition 521 C HA PT E R 10 Applications of Linear Algebra 527 10.1 Constructing Curves and Surfaces Through Specified Points 528 10.2 The Earliest Applications of Linear Algebra 533 10.3 Cubic Spline Interpolation 540 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 Age-Specific Population Growth 673 10.17 Harvesting of Animal Populations 683 10.18 A Least Squares Model for Human Hearing 691 10.19 Warps and Morphs 697 10.20 Internet Search Engines 706 APPENDIX A Working with Proofs A1 APPENDIX B Complex Numbers A5 Answers to Exercises A13 Index I1  CHAPTER 1 Systems of Linear Equations and Matrices CHAPTER CONTENTS 1.1 Introduction to Systems of Linear Equations 2 1.2 Gaussian Elimination 11 1.3 Matrices and Matrix Operations 25 1.4 Inverses; Algebraic Properties of Matrices 39 1.5 Elementary Matrices and a Method for Finding A−1 52 1.6 More on Linear Systems and Invertible Matrices 61 1.7 Diagonal,Triangular, and Symmetric Matrices 67 1.8 MatrixTransformations 75 1.9 Applications of Linear Systems 84 Network Analysis (Traffic Flow) 84 Electrical Circuits 86 Balancing Chemical Equations 88 Polynomial Interpolation 91 1.10 Leontief Input-Output Models 96 INTRODUCTION 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 3 2 −1 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 field 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 first 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 repre- sented by an equation of the form ax + by = c (a, b not both 0) and in three dimensions a plane in a rectangular xyz-coordinate system can be repre- sented by an equation of the form ax + by + cz = d (a, b, c not all 0) These are examples of “linear equations,” the first 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 define 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) (2) a1 x + a2 y + a3 z = b (a1 , a2 , a3 not all 0) (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 first power and do not appear, for example, as arguments of trigonometric, logarithmic, or exponential functions. The following are linear equations: x + 3y = 7 x1 − 2x2 − 3x3 + x4 = 0 1 2 x − y + 3z = −1 x1 + x2 + · · · + xn = 1 The following are not linear equations: x + 3y 2 = 4 3x + 2y − xy = 5 √ sin x + y = 0 x1 + 2x2 + x3 = 1 A finite set of linear equations is called a system of linear equations or, more briefly, 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 4x1 − x2 + 3x3 = −1 (5–6) 2x − y = 4 3x1 + x2 + 9x3 = −4  1.1 Introduction to Systems of Linear Equations 3 A general linear system of m equations in the n unknowns x1 , x2 ,... , xn can be written The double subscripting on as the coefficients aij of the un- a11 x1 + a12 x2 + · · · + a1n xn = b1 knowns gives their location in the system—the first sub- a21 x1 + a22 x2 + · · · + a2n xn = b2........ (7) script indicates the equation.... in which the coefficient occurs, am1 x1 + am2 x2 + · · · + amn xn = bm and the second indicates which A solution of a linear system in n unknowns x1 , x2 ,... , xn is a sequence of n numbers unknown it multiplies. Thus, a12 is in the first equation and s1 , s2 ,... , sn for which the substitution multiplies x2. 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 two-dimensional and three-dimensional 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 n-tuple. With this notation it is understood that all variables appear in the same order in each equation. If n = 2, then the n-tuple is called an ordered pair, and if n = 3, then it is called an ordered triple. Linear Systems inTwo and Linear systems in two unknowns arise in connection with intersections of lines. For Three Unknowns 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 xy-plane. 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 infinitely many points of intersection (the points on the common line) and consequently infinitely 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 x x x No solution One solution Infinitely many solutions (coincident lines) Figure 1.1.1 two unknowns has either one solution or infinitely 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 infinitely many solutions (Figure 1.1.2). No solutions No solutions No solutions No solutions (three parallel planes; (two parallel planes; (no common intersection) (two coincident planes no common intersection) no common intersection) parallel to the third; no common intersection) One solution Infinitely many solutions Infinitely many solutions Infinitely many solutions (intersection is a point) (intersection is a line) (planes are all coincident; (two coincident planes; intersection is a plane) 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 infinitely 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 Solution We can eliminate x from the second equation by adding −2 times the first equation to the second. This yields the simplified system x−y =1 3y = 4 From the second equation we obtain y = 43 , and on substituting this value in the first 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 first equation to the second equation. This yields the simplified 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 Infinitely 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 first equation to the second. This yields the simplified 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 to y. This allows us to express the solution by the pair of equations (called parametric In Example 4 we could have equations) also obtained parametric equations for the solutions x= 1 4 + 21 t, y = t by solving (8) for y in terms We can obtain specific numerical solutions from these equations by substituting  1  numer- of x and letting x = t be ical values for the parameter  t. For example, t = 0 yields  the solution  4 ,0 , t = 1 the parameter. The resulting yields the solution 43 , 1 , and t = −1 yields the solution − 41 , −1. You can confirm parametric equations would that these are solutions by substituting their coordinates into the given equations. look different but would define the same solution set. E X A M P L E 5 A Linear System with Infinitely 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 first. 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 suffices to find the solutions of (9). We can do this by first 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 Specific 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 As the number of equations and unknowns in a linear system increases, so does the Elementary Row Operations complexity of the algebra involved in finding 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 a12 · · · a1n b1 ⎢ ⎥ ⎢a21 a22 · · · a2 n b2 ⎥ ⎢....... ⎥ As noted in the introduction ⎣..... ⎦ to this chapter, the term “ma- am1 am2 · · · amn bm trix” is used in mathematics to denote a rectangular array of This is called the augmented matrix for the system. For example, the augmented matrix numbers. In a later section for the system of equations we will study matrices in de- ⎡ ⎤ tail, but for now we will only x1 + x2 + 2x3 = 9 1 1 2 9 ⎢ ⎥ be concerned with augmented 2x1 + 4x2 − 3x3 = 1 is ⎣2 4 −3 1⎦ matrices for linear systems. 3x1 + 6x2 − 5x3 = 0 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 first equation to the second Add −2 times the first row to the second to to obtain obtain ⎡ ⎤ x + y + 2z = 9 1 1 2 9 ⎢ ⎥ 2y − 7z = −17 ⎣0 2 −7 −17⎦ 3x + 6y − 5z = 0 3 6 −5 0 Historical Note The first 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 coefficients 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 intro- duced by the American mathematician Maxime Bôcher in his book In- troduction 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 text- books were greatly appreciated by students and are still in demand Maxime Bôcher today. (1867–1918) [Image: Courtesy of the American Mathematical Society www.ams.org] 8 Chapter 1 Systems of Linear Equations and Matrices Add −3 times the first equation to the third to Add −3 times the first row to the third to obtain obtain ⎡ ⎤ x + y + 2z = 9 1 1 2 9 ⎢ ⎥ 2y − 7z = −17 ⎣0 2 −7 −17⎦ 3y − 11z = −27 0 3 −11 −27 1 1 Multiply the second equation by 2 to obtain Multiply the second row by 2 to obtain ⎡ ⎤ x + y + 2z = 9 1 1 2 9 ⎢ ⎥ y− 7 2 z = − 172 ⎣0 1 − 27 − 172 ⎦ 3y − 11z = −27 0 3 −11 −27 Add −3 times the second equation to the third Add −3 times the second row to the third to to obtain obtain ⎡ ⎤ x + y + 2z = 9 1 1 2 9 ⎢ ⎥ y − 27 z = − 172 ⎢0 1 − 27 − 172 ⎥ ⎣ ⎦ − 21 z = − 23 0 0 − 21 − 23 Multiply the third equation by −2 to obtain Multiply the third row by −2 to obtain ⎡ ⎤ x + y + 2z = 9 1 1 2 9 ⎢ ⎥ y − 27 z = − 172 ⎣0 1 − 27 − 172 ⎦ z= 3 0 0 1 3 Add −1 times the second equation to the first Add −1 times the second row to the first to to obtain obtain ⎡ ⎤ x + 11 z = 35 1 0 11 35 2 2 ⎢ 2 2 ⎥ y− 7 z = − 172 ⎢0 1 − 27 − 172 ⎥ 2 ⎣ ⎦ z= 3 0 0 1 3 The solution in this example Add −11 2 times the third equation to the first Add − 112 times the third row to the first and 7 2 can also be expressed as the or- and 27 times the third equation to the second to times the third row to the second to obtain dered triple (1, 2, 3) with the obtain ⎡ ⎤ x =1 1 0 0 1 understanding that the num- ⎢ ⎥ bers in the triple are in the y =2 ⎣0 1 0 2⎦ same order as the variables in z=3 0 0 1 3 the system, namely, x, y, z. 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 , 2. In each part, determine whether the equation is linear in x x2 , and x3. and y. √ √ √ (a) x1 + 5x2 − 2 x3 = 1 (b) x1 + 3x2 + x1 x3 = 2 (a) 21/3 x + 3y = 1 (b) 2x 1/3 + 3 y = 1 π  (c) x1 = −7x2 + 3x3 (d) x1−2 + x2 + 8x3 = 5 (c) cos x − 4y = log 3 (d) π cos x − 4y = 0 7 7 3/5 √ (e) x1 − 2x2 + x3 = 4 (f ) πx1 − 2 x2 = 7 1/3 (e) xy = 1 (f ) y + 7 = x  1.1 Introduction to Systems of Linear Equations 9 5  5  3. Using the notation of Formula (7), write down a general linear (a) , 87 , 1 (b) , 87 , 0 (c) (5, 8, 1) 7 7 system of 5  5  10 2 (a) two equations in two unknowns. (d) 7 , , 7 7 (e) 7 , 227 , 2 (b) three equations in three unknowns. 11. In each part, solve the linear system, if possible, and use the (c) two equations in four unknowns. result to determine whether the lines represented by the equa- tions in the system have zero, one, or infinitely many points of 4. Write down the augmented matrix for each of the linear sys- intersection. If there is a single point of intersection, give its tems in Exercise 3. coordinates, and if there are infinitely many, find parametric In each part of Exercises 5–6, find a linear system in the un- equations for them. knowns x1 , x2 , x3 ,... , that corresponds to the given augmented (a) 3x − 2y = 4 (b) 2x − 4y = 1 (c) x − 2y = 0 matrix. 6x − 4 y = 9 4 x − 8y = 2 x − 4y = 8 ⎡ ⎤ ⎡ ⎤ 2 0 0 3 0 −2 5 ⎢ ⎥ ⎢ ⎥ 12. Under what conditions on a and b will the following linear 5. (a) ⎣3 −4 0⎦ (b) ⎣7 1 4 −3⎦ system have no solutions, one solution, infinitely many solu- 0 1 1 0 −2 1 7 tions?   2 x − 3y = a 0 3 −1 −1 −1 4x − 6y = b 6. (a) 5 2 0 −3 −6 In each part of Exercises 13–14, use parametric equations to ⎡ ⎤ describe the solution set of the linear equation. 3 0 1 −4 3 ⎢−4 −3 ⎥ 13. (a) 7x − 5y = 3 ⎢ 0 4 1 ⎥ (b) ⎢ ⎥ ⎣−1 3 0 −2 −9 ⎦ (b) 3x1 − 5x2 + 4x3 = 7 0 0 0 −1 −2 (c) −8x1 + 2x2 − 5x3 + 6x4 = 1 In each part of Exercises 7–8, find the augmented matrix for (d) 3v − 8w + 2x − y + 4z = 0 the linear system. 14. (a) x + 10y = 2 7. (a) −2x1 = 6 (b) 6x1 − x2 + 3x3 = 4 3x1 = 8 5x2 − x3 = 1 (b) x1 + 3x2 − 12x3 = 3 9x1 = −3 (c) 4x1 + 2x2 + 3x3 + x4 = 20 (c) 2x2 − 3x4 + x5 = 0 (d) v + w + x − 5y + 7z = 0 −3x1 − x2 + x3 = −1 6x1 + 2x2 − x3 + 2x4 − 3x5 = 6 In Exercises 15–16, each linear system has infinitely many so- lutions. Use parametric equations to describe its solution set. 8. (a) 3x1 − 2x2 = −1 (b) 2x1 + 2x3 = 1 15. (a) 2x − 3y = 1 4x1 + 5x2 = 3 3x1 − x2 + 4x3 = 7 6 x − 9y = 3 7x1 + 3x2 = 2 6x1 + x2 − x3 = 0 (b) x1 + 3x2 − x3 = −4 (c) x1 =1 3x1 + 9x2 − 3x3 = −12 x2 =2 −x1 − 3x2 + x3 = 4 x3 =3 9. In each part, determine whether the given 3-tuple is a solution 16. (a) 6x1 + 2x2 = −8 (b) 2x − y + 2z = −4 of the linear system 3x1 + x2 = −4 6x − 3y + 6z = −12 2x1 − 4x2 − x3 = 1 −4 x + 2 y − 4 z = 8 x1 − 3x2 + x3 = 1 In Exercises 17–18, find a single elementary row operation that 3x1 − 5x2 − 3x3 = 1 will create a 1 in the upper left corner of the given augmented ma- trix and will not create any fractions in its first row. (a) (3, 1, 1) (b) (3, −1, 1) (c) (13, 5, 2)  13  ⎡ ⎤ ⎡ ⎤ (d) 2 , 25 , 2 (e) (17, 7, 5) −3 −1 2 4 0 −1 −5 0 17. (a) ⎣ 2 −3 3 2⎦ (b) ⎣2 −9 3 2⎦ 10. In each part, determine whether the given 3-tuple is a solution 0 2 −3 1 1 4 −3 3 of the linear system ⎡ ⎤ ⎡ ⎤ x + 2y − 2z = 3 2 4 −6 8 7 −4 −2 2 3x − y + z = 1 18. (a) ⎣ 7 1 4 3⎦ (b) ⎣ 3 −1 8 1⎦ −x + 5y − 5z = 5 −5 4 2 7 −6 3 −1 4 10 Chapter 1 Systems of Linear Equations and Matrices In Exercises 19–20, find all values of k for which the given Let x, y, and z denote the number of ounces of the first, sec- augmented matrix corresponds to a consistent linear system. ond, 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 1 k −4 1 k −1 whose solution tells how many ounces of each food must be 19. (a) (b) 4 8 2 4 8 −4 consumed to meet the diet requirements. 3 −4 k k 1 −2 26. Suppose that you want to find values for a, b, and c such that 20. (a) (b) the parabola y = ax 2 + bx + c passes through the points −6 8 5 4 −1 2 (1, 1), (2, 4), and (−1, 1). Find (but do not solve) a system 21. The curve y = ax 2 + bx + c shown in the accompanying fig- of linear equations whose solutions provide values for a, b, ure passes through the points (x1 , y1 ), (x2 , y2 ), and (x3 , y3 ). and c. How many solutions would you expect this system of Show that the coefficients a , b, and c form a solution of the equations to have, and why? system of linear equations whose augmented matrix is ⎡ ⎤ 27. Suppose you are asked to find three real numbers such that the x12 x1 1 y1 sum of the numbers is 12, the sum of two times the first plus ⎢ 2 ⎥ ⎣x2 x2 1 y2 ⎦ the second plus two times the third is 5, and the third number x32 x3 1 y3 is one more than the first. Find (but do not solve) a linear system whose equations describe the three conditions. y y = ax2 + bx + c True-False Exercises (x3, y3) TF. In parts (a)–(h) determine whether the statement is true or (x1, y1) false, and justify your answer. (a) A linear system whose equations are all homogeneous must (x2, y2) be consistent. x Figure Ex-21 (b) Multiplying a row of an augmented matrix through by zero is an acceptable elementary row operation. 22. Explain why each of the three elementary row operations does (c) The linear system not affect the solution set of a linear system. x− y =3 2x − 2y = k 23. Show that if the linear equations cannot have a unique solution, regardless of the value of k. x1 + kx2 = c and x1 + lx2 = d (d) A single linear equation with two or more unknowns must have the same solution set, then the two equations are identical have infinitely many solutions. (i.e., k = l and c = d ). (e) If the number of equations in a linear system exceeds the num- 24. Consider the system of equations ber of unknowns, then the system must be inconsistent. ax + by = k cx + dy = l (f ) If each equation in a consistent linear system is multiplied through by a constant c, then all solutions to the new system ex + fy = m can be obtained by multiplying solutions from the original Discuss the relative positions of the lines ax + by = k , system by c. cx + dy = l , and ex + fy = m when (g) Elementary row operations permit one row of an augmented (a) the system has no solutions. matrix to be subtracted from another. (b) the system has exactly one solution. (h) The linear system with corresponding augmented matrix (c) the system has infinitely many solutions. 2 −1 4 25. Suppose that a certain diet calls for 7 units of fat, 9 units of 0 0 −1 protein, and 16 units of carbohydrates for the main meal, and suppose that an individual has three possible foods to choose is consistent. from to meet these requirements: Working withTechnology Food 1: Each ounce contains 2 units of fat, 2 units of protein, and 4 units of carbohydrates. T1. Solve the linear systems in Examples 2, 3, and 4 to see how your technology utility handles the three types of systems. Food 2: Each ounce contains 3 units of fat, 1 unit of protein, and 2 units of carbohydrates. T2. Use the result in Exercise 21 to find values of a , b, and c Food 3: Each ounce contains 1 unit of fat, 3 units of for which the curve y = ax 2 + bx + c passes through the points protein, and 5 units of carbohydrates. (−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 When considering methods for solving systems of linear equations, it is important to Linear Systems 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 field 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 1 ⎢0 2⎥ ⎣ 1 0 ⎦ 0 0 1 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 first 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 first 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. ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ 0 1 −2 0 1 1 0 0 4 1 0 0 ⎢0 3⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 0 0 1 ⎥ 0 0 ⎣0 1 0 7⎦ , ⎣0 1 0⎦ , ⎢ ⎥, ⎣0 0 0 0 0⎦ 0 0 0 0 1 −1 0 0 1 0 0 0 0 0 The following matrices are in row echelon form but not reduced row echelon form. ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ 1 4 −3 7 1 1 0 0 1 2 6 0 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣0 1 6 2⎦ , ⎣0 1 0⎦ , ⎣0 0 1 −1 0⎦ 0 0 1 5 0 0 0 0 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: ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ 0 1 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 1 ∗ ∗ ∗ 1 ∗ ∗ ∗ 1 ∗ ∗ ∗ ⎢0 ⎢0 0 1 ∗ ∗ ∗ ∗⎥ ∗ ∗ 1 ∗ ∗⎥ ⎢0 1 ∗ ∗⎥ ⎢0 1 ∗ ∗⎥ ⎢ ⎥ 0 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥, ⎢ ⎥, ⎢ ⎥, ⎢0 0 0 0 1 ∗ ∗ ∗ ∗⎥ ∗ ⎣0 0 1 ∗⎦ ⎣0 0 1 ∗⎦ ⎣0 0 0 0⎦ ⎢ ⎥ ⎣0 0 0 0 0 1 ∗ ∗⎦ ∗ ∗ 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ∗ All matrices of the following types are in reduced row echelon form: ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ 0 1 ∗ 0 0 0 ∗ 0 ∗ ∗ 1 0 0 0 1 0 0 ∗ 1 0 ∗ ∗ ⎢0 ⎢0 1 0 0⎥ ⎢0 1 0 ∗⎥ ⎢0 1 0 1 0 0 ∗ ∗ ∗⎥ ∗ ∗⎥ ⎢ ⎥ 0 0 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥, ⎢ ⎥, ⎢ ⎥ , ⎢0 0 0 0 1 0 ∗ 0 ∗ ∗⎥ ⎣0 0 1 0⎦ ⎣0 0 1 ∗⎦ ⎣0 0 0 0⎦ ⎢ ⎥ ⎣0 0 0 0 0 1 ∗ 0 ∗ ∗⎦ 0 0 0 1 0 0 0 0 0 0 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 3 ⎢0 −1⎥ ⎢ 1 0 0 ⎥ ⎢ ⎥ ⎣0 0 1 0 0⎦ 0 0 0 1 5 This matrix is in reduced row echelon form and corresponds to the equations x1 = 3 In Example 3 we could, if x2 = −1 desired, express the solution x3