**UFBA**

# Matrix Analysis and Applied Linear Algebra

(Parte **1** de 5)

Preface | ix |

1. Linear Equations | 1 |

1.1 Introduction | 1 |

1.2 Gaussian Elimination and Matrices | 3 |

1.3 Gauss–Jordan Method | 15 |

1.4 Two-Point BoundaryV alue Problems | 18 |

1.5 Making Gaussian Elimination Work | 21 |

1.6 Ill-Conditioned Systems | 3 |

2. Rectangular Systems and Echelon Forms | 41 |

2.1 Row Echelon Form and Rank | 41 |

2.2 Reduced Row Echelon Form | 47 |

2.3 Consistencyof Linear Systems | 53 |

2.4 Homogeneous Systems | 57 |

2.5 Nonhomogeneous Systems | 64 |

2.6 Electrical Circuits | 73 |

3. Matrix Algebra | 79 |

3.1 From Ancient China to Arthur Cayley | 79 |

3.2 Addition and Transposition | 81 |

3.3 Linearity | 89 |

3.4 WhyDo It This Way | 93 |

3.5 Matrix Multiplication | 95 |

3.6 Properties of Matrix Multiplication | 105 |

3.7 Matrix Inversion | 115 |

3.8 Inverses of Sums and Sensitivity | 124 |

3.9 ElementaryMatrices and Equivalence | 131 |

3.10 The LU Factorization | 141 |

4. Vector Spaces | 159 |

4.1 Spaces and Subspaces | 159 |

4.2 Four Fundamental Subspaces | 169 |

4.3 Linear Independence | 181 |

Contents 4.4 Basis and Dimension ............. 194

4.5 More about Rank | 210 |

4.6 Classical Least Squares | 223 |

4.7 Linear Transformations | 238 |

4.8 Change of Basis and Similarity | 251 |

4.9 Invariant Subspaces | 259 |

5. Norms, Inner Products, and Orthogonality | 269 |

5.1 Vector Norms | 269 |

5.2 Matrix Norms | 279 |

5.3 Inner-Product Spaces | 286 |

5.4 Orthogonal Vectors | 294 |

5.5 Gram–Schmidt Procedure | 307 |

5.6 Unitaryand Orthogonal Matrices | 320 |

5.7 Orthogonal Reduction | 341 |

5.8 Discrete Fourier Transform | 356 |

5.9 ComplementarySubspaces | 383 |

5.10 Range-Nullspace Decomposition | 394 |

5.1 Orthogonal Decomposition | 403 |

5.12 Singular Value Decomposition | 411 |

5.13 Orthogonal Projection | 429 |

5.14 WhyLeast Squares? | 446 |

5.15 Angles between Subspaces | 450 |

6. Determinants | 459 |

6.1 Determinants | 459 |

6.2 Additional Properties of Determinants | 475 |

7. Eigenvalues and Eigenvectors | 489 |

7.1 ElementaryProp erties of Eigensystems | 489 |

7.2 Diagonalization bySimilarit yT ransformations | 505 |

7.3 Functions of Diagonalizable Matrices | 525 |

7.4 Systems of Diﬀerential Equations | 541 |

7.5 Normal Matrices | 547 |

7.6 Positive Deﬁnite Matrices | 558 |

7.7 Nilpotent Matrices and Jordan Structure | 574 |

7.8 Jordan Form | 587 |

vi Contents 7.9 Functions of Nondiagonalizable Matrices ..... 599

7.10 Diﬀerence Equations, Limits, and Summability | 616 |

7.1 Minimum Polynomials and Krylov Methods | 642 |

8. Perron–Frobenius Theory | 661 |

8.1 Introduction | 661 |

8.2 Positive Matrices | 663 |

8.3 Nonnegative Matrices | 670 |

8.4 Stochastic Matrices and Markov Chains | 687 |

Contents vii Index ...................... 705

Preface

Scaffolding

Reacting to criticism concerning the lack of motivation in his writings,

Gauss remarked that architects of great cathedrals do not obscure the beauty of their work by leaving the scaﬀolding in place after the construction has been completed. His philosophy epitomized the formal presentation and teaching of mathematics throughout the nineteenth and twentieth centuries, and it is still commonly found in mid-to-upper-level mathematics textbooks. The inherent efﬁciency and natural beauty of mathematics are compromised by straying too far from Gauss’s viewpoint. But, as with most things in life, appreciation is generally preceded by some understanding seasoned with a bit of maturity, and in mathematics this comes from seeing some of the scaﬀolding.

Purpose, Gap, and Challenge

The purpose of this text is to present the contemporary theory and applications of linear algebra to university students studying mathematics, engineering, or applied science at the postcalculus level. Because linear algebra is usually encountered between basic problem solving courses such as calculus or diﬀerential equations and more advanced courses that require students to cope with mathematical rigors, the challenge in teaching applied linear algebra is to expose some of the scaﬀolding while conditioning students to appreciate the utility and beauty of the subject. Eﬀectively meeting this challenge and bridging the inherent gaps between basic and more advanced mathematics are primary goals of this book.

Rigor and Formalism

To reveal portions of the scaﬀolding, narratives, examples, and summaries are used in place of the formal deﬁnition–theorem–proof development. But while well-chosen examples can be more eﬀective in promoting understanding than rigorous proofs, and while precious classroom minutes cannot be squandered on theoretical details, I believe that all scientiﬁcally oriented students should be exposed to some degree of mathematical thought, logic, and rigor. And if logic and rigor are to reside anywhere, they have to be in the textbook. So even when logic and rigor are not the primary thrust, they are always available. Formal deﬁnition–theorem–proof designations are not used, but deﬁnitions, theorems, and proofs nevertheless exist, and they become evident as a student’s maturity increases. A signiﬁcant eﬀort is made to present a linear development that avoids forward references, circular arguments, and dependence on prior knowledge of the subject. This results in some ineﬃciencies—e.g., the matrix2-norm is presented x Preface before eigenvalues or singular values are thoroughly discussed. To compensate, I try to provide enough “wiggle room” so that an instructor can temper the ineﬃciencies by tailoring the approach to the students’ prior background.

Comprehensiveness and Flexibility

A rather comprehensive treatment of linear algebra and its applications is presented and, consequently, the book is not meant to be devoured cover-to-cover in a typical one-semester course. However, the presentation is structured to provide ﬂexibility in topic selection so that the text can be easily adapted to meet the demands of diﬀerent course outlines without suﬀering breaks in continuity. Each section contains basic material paired with straightforward explanations, examples, and exercises. But every section also contains a degree of depth coupled with thought-provoking examples and exercises that can take interested students to a higher level. The exercises are formulated not only to make a student think about material from a current section, but they are designed also to pave the way for ideas in future sections in a smooth and often transparent manner. The text accommodates a variety of presentation levels by allowing instructors to select sections, discussions, examples, and exercises of appropriate sophistication. For example, traditional one-semester undergraduate courses can be taught from the basic material in Chapter 1 (Linear Equations); Chapter 2 (Rectangular Systems and Echelon Forms); Chapter 3 (MatrixAlgebra); Chapter 4 (Vector Spaces); Chapter 5 (Norms, Inner Products, and Orthogonality); Chapter 6 (Determinants); and Chapter 7 (Eigenvalues and Eigenvectors). The level of the course and the degree of rigor are controlled by the selection and depth of coverage in the latter sections of Chapters 4, 5, and 7. An upper-level course might consist of a quick review of Chapters 1, 2, and 3 followed by a more in-depth treatment of Chapters 4, 5, and 7. For courses containing advanced undergraduate or graduate students, the focus can be on material in the latter sections of Chapters 4, 5, 7, and Chapter 8 (Perron–Frobenius Theory of Nonnegative Matrices). A rich two-semester course can be taught by using the text in its entirety.

What Does “Applied” Mean?

Most people agree that linear algebra is at the heart of applied science, but there are divergent views concerning what “applied linear algebra” really means; the academician’s perspective is not always the same as that of the practitioner. In a poll conducted by SIAM in preparation for one of the triannual SIAM conferences on applied linear algebra, a diverse group of internationally recognized scientiﬁc corporations and government laboratories was asked how linear algebra ﬁnds application in their missions. The overwhelming response was that the primary use of linear algebra in applied industrial and laboratory work involves the development, analysis, and implementation of numerical algorithms along with some discrete and statistical modeling. The applications in this book tend to reﬂect this realization. While most of the popular “academic” applications are included, and “applications” to other areas of mathematics are honestly treated,

Preface xi there is an emphasis on numerical issues designed to prepare students to use linear algebra in scientiﬁc environments outside the classroom.

Computing Projects

Computing projects help solidify concepts, and I include many exercises that can be incorporated into a laboratory setting. But my goal is to write a mathematics text that can last, so I don’t muddy the development by marrying the material to a particular computer package or language. I am old enough to remember what happened to the FORTRAN- and APL-based calculus and linear algebra texts that came to market in the 1970s. I provide instructors with a ﬂexible environment that allows for an ancillary computing laboratory in which any number of popular packages and lab manuals can be used in conjunction with the material in the text.

History

Finally, I believe that revealing only the scaﬀolding without teaching something about the scientiﬁc architects who erected it deprives students of an important part of their mathematical heritage. It also tends to dehumanize mathematics, which is the epitome of human endeavor. Consequently, I make an eﬀort to say things (sometimes very human things that are not always complimentary) about the lives of the people who contributed to the development and applications of linear algebra. But, as I came to realize, this is a perilous task because writing history is frequently an interpretation of facts rather than a statement of facts. I considered documenting the sources of the historical remarks to help mitigate the inevitable challenges, but it soon became apparent that the sheer volume required to do so would skew the direction and ﬂavor of the text. I can only assure the reader that I made an eﬀort to be as honest as possible, and I tried to corroborate “facts.” Nevertheless, there were times when interpretations had to be made, and these were no doubt inﬂuenced by my own views and experiences.

Supplements

Included with this text is a solutions manual and a CD-ROM. The solutions manual contains the solutions for each exercise given in the book. The solutions are constructed to be an integral part of the learning process. Rather than just providing answers, the solutions often contain details and discussions that are intended to stimulate thought and motivate material in the following sections. The CD, produced by Vickie Kearn and the people at SIAM, contains the entire book along with the solutions manual in PDF format. This electronic version of the text is completely searchable and linked. With a click of the mouse a student can jump to a referenced page, equation, theorem, deﬁnition, or proof, and then jump back to the sentence containing the reference, thereby making learning quite eﬃcient. In addition, the CD contains material that extends historical remarks in the book and brings them to life with a large selection of xii Preface portraits, pictures, attractive graphics, and additional anecdotes. The supporting Internet site at MatrixAnalysis.com contains updates, errata, new material, and additional supplements as they become available.

I thank the SIAM organization and the people who constitute it (the infrastructure as well as the general membership) for allowing me the honor of publishing my book under their name. I am dedicated to the goals, philosophy, and ideals of SIAM, and there is no other company or organization in the world that I would rather have publish this book. In particular, I am most thankful to Vickie Kearn, publisher at SIAM, for the conﬁdence, vision, and dedication she has continually provided, and I am grateful for her patience that allowed me to write the book that I wanted to write. The talented people on the SIAM staﬀ went far above and beyond the call of ordinary duty to make this project special. This group includes Lois Sellers (art and cover design), Michelle Montgomery and Kathleen LeBlanc (promotion and marketing), Marianne Will and Deborah Poulson (copy for CD-ROM biographies), Laura Helfrich and David Comdico (design and layout of the CD-ROM), Kelly Cuomo (linking the CDROM), and Kelly Thomas (managing editor for the book). Special thanks goes to Jean Anderson for her eagle-sharp editor’s eye.

Acknowledgments

This book evolved over a period of several years through many diﬀerent courses populated by hundreds of undergraduate and graduate students. To all my students and colleagues who have oﬀered suggestions, corrections, criticisms, or just moral support, I oﬀer my heartfelt thanks, and I hope to see as many of you as possible at some point in the future so that I can convey my feelings to you in person. I am particularly indebted to Michele Benzi for conversations and suggestions that led to several improvements. All writers are inﬂuenced by people who have written before them, and for me these writers include (in no particular order) Gil Strang, Jim Ortega, Charlie Van Loan, Leonid Mirsky, Ben Noble, Pete Stewart, Gene Golub, Charlie Johnson, Roger Horn, Peter Lancaster, Paul Halmos, Franz Hohn, Nick Rose, and Richard Bellman—thanks for lighting the path. I want to oﬀer particular thanks to Richard J. Painter and Franklin A. Graybill, two exceptionally ﬁne teachers, for giving a rough Colorado farm boy a chance to pursue his dreams. Finally, neither this book nor anything else I have done in my career would have been possible without the love, help, and unwavering support from Bethany, my friend, partner, and wife. Her multiple readings of the manuscript and suggestions were invaluable. I dedicate this book to Bethany and our children, Martin and Holly, to our granddaughter, Margaret, and to the memory of my parents, Carl and Louise Meyer.

Carl D. Meyer April 19, 2000

CHAPTER 1

Linear Equations

1.1 INTRODUCTION

A fundamental problem that surfaces in all mathematical sciences is that of analyzing and solving m algebraic equations in n unknowns. The study of a system of simultaneous linear equations is in a natural and indivisible alliance with the study of the rectangular array of numbers deﬁned by the coeﬃcients of the equations. This link seems to have been made at the outset.

The earliest recorded analysis of simultaneous equations is found in the ancient Chinese book Chiu-chang Suan-shu (Nine Chapters on Arithmetic), estimated to have been written some time around 200 B.C. In the beginning of Chapter VIII, there appears a problem of the following form.

Three sheafs of a good crop, two sheafs of a mediocre crop, and one sheaf of a bad crop are sold for 39 dou. Two sheafs of good, three mediocre, and one bad are sold for 34 dou; and one good, two mediocre, and three bad are sold for 26 dou. What is the price received for each sheaf of a good crop, each sheaf of a mediocre crop, and each sheaf of a bad crop?

Today, this problem would be formulated as three equations in three un-

where x, y, and z represent the price for one sheaf of a good, mediocre, and bad crop, respectively. The Chinese saw right to the heart of the matter. They placed the coeﬃcients (represented by colored bamboo rods) of this system in

2 Chapter 1 Linear Equations a square array on a “counting board” and then manipulated the lines of the array according to prescribed rules of thumb. Their counting board techniques and rules of thumb found their way to Japan and eventually appeared in Europe with the colored rods having been replaced by numerals and the counting board replaced by pen and paper. In Europe, the technique became known as Gaussian elimination in honor of the German mathematician Carl Gauss,1 whose extensive use of it popularized the method.

Because this elimination technique is fundamental, we begin the study of our subject by learning how to apply this method in order to compute solutions for linear equations. After the computational aspects have been mastered, we will turn to the more theoretical facets surrounding linear systems.

1 Carl Friedrich Gauss (1777–1855) is considered by many to have been the greatest mathemati- cian who has ever lived,and his astounding career requires several volumes to document. He was referred to by his peers as the “prince of mathematicians.” Upon Gauss’s death one of them wrote that “His mind penetrated into the deepest secrets of numbers,space,and nature; He measured the course of the stars,the form and forces of the Earth; He carried within himself the evolution of mathematical sciences of a coming century.” History has proven this remark to be true.

1.2 Gaussian Elimination and Matrices 3 1.2 GAUSSIANELIMINATIONANDMATRICES

The problem is to calculate, if possible, a common solution for a system of m linear algebraic equations in n unknowns

where the xi ’s are the unknowns and the aij ’s and the bi ’s are known constants.

The aij ’s are called the coeﬃcients of the system, and the set of bi ’s is referred to as the right-hand side of the system. For any such system, there are exactly three possibilities for the set of solutions.

Three Possibilities

• UNIQUE SOLUTION: There is one and only one set of values for the xi ’s that satisﬁes all equations simultaneously.

(Parte **1** de 5)