xiliPrefacetothesecond editionclassical results. Its detailed treatment of unitary congruence includes Youla'stheorem(anormalformfora squarecomplexmatrixAunderunitarycongruencethat is associated with the eigenstructure of AA), as well as canonical forms forconjugate normal, congruence normal,and squared normal matrices.It also has anexposition ofrecentlydiscovered canonical formsforcongruenceand*congruenceand new algorithms to construct a basis of a coneigenspace.5.Chapter5containsan expanded discussion of normduality,many newproblems,and a treatment of semi-inner products that finds application in a discussion offinite-dimensional quantumsystemsinChapter7.6.Chapter6has a newtreatmentofthe"disjoint discs"aspectof Gersgorin's theoremand a reorganized discussion of eigenvalue perturbations, including differentiabil-ityofa simpleeigenvalue.7.Chapter 7has been reorganized now that the singular value decomposition isintroduced in Chapter 2.There is a new treatment of the polar decomposition, newfactorizations related to the singular value decomposition, and special emphasis onrow and column inclusion.The von Neumann trace theorem (proved via Birkhoff'stheorem)is now thefoundation on whichmany applications of the singular valuedecomposition are built. The Loewner partial order and block matrices are treatedin detail with new techniques, as are the classical determinant inequalities forpositivedefinitematrices.8.Chapter 8 uses facts about lefteigenvectors developed in Chapter1 to streamline itsexposition of the Perron-Frobenius theory of positive and nonnegative matrices.D. Appendix D contains new explicit perturbation bounds for the zeroes of a poly-nomial and theeigenvalues of amatrix.F.AppendixFtabulates a modern list of canonical forms for a pair of Hermitianmatrices,or a pair of matrices, one of which is symmetric and the other is skewsymmetric.These canonical pairs are applications of the canonical forms forcongruence and *congruence presented in Chapter 4.Readers who are curious about thetechnology of book making maybe interestedtoknow that this book began as a set of LTex files created manuallyby a company inIndia fromhard copy ofthe first edition.Those files were edited and revised using theScientific WorkPlace?graphical user interface and typesetting system.The cover art for the second edition was theresult of a lucky encounter on a Deltaflight from Salt LakeCitytoLosAngeles in spring2003.Theyoungman in themiddle seat said he was an artist who paints abstract paintings that are sometimesmathematically inspired.In the course of friendly conversation, he revealed that hisspecial areaof mathematicalenjoymentwaslinearalgebra,andthathehad studiedMatrix Analysis.After mutual expressions of surprise at the chance nature of ourmeetinganda pleasantdiscussion,weagreedthatappropriate cover artwouldenhancethe visual appeal of the second edition; he said he would send something to consider.InduecourseapacketarrivedfromSeattle.Itcontainedaletterandastunning4.5-by5-inchcolorphotograph,identifiedonthebackasanimageofa72-by66-inchoiloncanvas,painted in2002.Theletter saidthatthepaintingis entitledSurprisedAgainon the Diagonal and is inspired by the recurring prevalence of the diagonal in mathwhether it be in geometry,analysis, algebra, set theory or logic.I think that it would
Preface to the second edition xiii classical results. Its detailed treatment of unitary congruence includes Youla’s theorem (a normal form for a square complex matrix A under unitary congruence that is associated with the eigenstructure of AA¯), as well as canonical forms for conjugate normal, congruence normal, and squared normal matrices. It also has an exposition of recently discovered canonical forms for congruence and ∗congruence and new algorithms to construct a basis of a coneigenspace. 5. Chapter 5 contains an expanded discussion of norm duality, many new problems, and a treatment of semi-inner products that finds application in a discussion of finite-dimensional quantum systems in Chapter 7. 6. Chapter 6 has a new treatment of the “disjoint discs” aspect of Gersgorin’s theorem ˇ and a reorganized discussion of eigenvalue perturbations, including differentiability of a simple eigenvalue. 7. Chapter 7 has been reorganized now that the singular value decomposition is introduced in Chapter 2. There is a new treatment of the polar decomposition, new factorizations related to the singular value decomposition, and special emphasis on row and column inclusion. The von Neumann trace theorem (proved via Birkhoff’s theorem) is now the foundation on which many applications of the singular value decomposition are built. The Loewner partial order and block matrices are treated in detail with new techniques, as are the classical determinant inequalities for positive definite matrices. 8. Chapter 8 uses facts about left eigenvectors developed in Chapter 1 to streamline its exposition of the Perron–Frobenius theory of positive and nonnegative matrices. D. Appendix D contains new explicit perturbation bounds for the zeroes of a polynomial and the eigenvalues of a matrix. F. Appendix F tabulates a modern list of canonical forms for a pair of Hermitian matrices, or a pair of matrices, one of which is symmetric and the other is skew symmetric. These canonical pairs are applications of the canonical forms for congruence and ∗congruence presented in Chapter 4. Readers who are curious about the technology of book making may be interested to know that this book began as a set of LATEX files created manually by a company in India from hard copy of the first edition. Those files were edited and revised using the Scientific WorkPlaceR graphical user interface and typesetting system. The cover art for the second edition was the result of a lucky encounter on a Delta flight from Salt Lake City to Los Angeles in spring 2003. The young man in the middle seat said he was an artist who paints abstract paintings that are sometimes mathematically inspired. In the course of friendly conversation, he revealed that his special area of mathematical enjoyment was linear algebra, and that he had studied Matrix Analysis. After mutual expressions of surprise at the chance nature of our meeting, and a pleasant discussion, we agreed that appropriate cover art would enhance the visual appeal of the second edition; he said he would send something to consider. In due course a packet arrived from Seattle. It contained a letter and a stunning 4.5- by 5-inch color photograph, identified on the back as an image of a 72- by 66-inch oil on canvas, painted in 2002. The letter said that “the painting is entitled Surprised Again on the Diagonal and is inspired by the recurring prevalence of the diagonal in math whether it be in geometry, analysis, algebra, set theory or logic. I think that it would
xivPrefacetothe secondeditionbe an attractive addition to your wonderful book."Thank you, Lun-Yi Tsai, for yourwonderful coverart!A great many students,instructors, and professional colleagues have contributedto the evolution of thisnew edition since its predecessor appeared in 1985.Specialthanksareherebyacknowledged toT.Ando,WayneBarrett,IgnatDomanov,JimFill,Carlos Martins da Fonseca, Tatiana Gerasimova, Geoffrey Goodson,Robert Guralnick,Thomas Hawkins, Eugene Herman,Khakim Ikramov, Ilse Ipsen,Dennis C.JespersenHideki Kosaki, Zhongshan Li, Teck C. Lim, Ross A. Lippert, Roy Mathias, DennisMerino, Arnold Neumaier, Kevin O'Meara, Peter Rosenthal, Vladimir Sergeichuk,Wasin So,Hugo Woerdeman,and Fuzhen Zhang.R.A.H
xiv Preface to the second edition be an attractive addition to your wonderful book.” Thank you, Lun-Yi Tsai, for your wonderful cover art! A great many students, instructors, and professional colleagues have contributed to the evolution of this new edition since its predecessor appeared in 1985. Special thanks are hereby acknowledged to T. Ando, Wayne Barrett, Ignat Domanov, Jim Fill, Carlos Martins da Fonseca, Tatiana Gerasimova, Geoffrey Goodson, Robert Guralnick, Thomas Hawkins, Eugene Herman, Khakim Ikramov, Ilse Ipsen, Dennis C. Jespersen, Hideki Kosaki, Zhongshan Li, Teck C. Lim, Ross A. Lippert, Roy Mathias, Dennis Merino, Arnold Neumaier, Kevin O’Meara, Peter Rosenthal, Vladimir Sergeichuk, Wasin So, Hugo Woerdeman, and Fuzhen Zhang. R.A.H
Preface to the First EditionLinear algebra and matrix theory have long been fundamental tools in mathematicaldisciplines as well as fertile fieldsfor research in their own right. In this book, and in thecompanionvolume,Topics in MatrixAnalysis,wepresentclassical andrecent resultsofmatrix analysis that haveprovedtobeimportanttoappliedmathematics.Thebookmay be used as an undergraduate or graduate text and as a self-contained reference for avariety of audiences.We assume background equivalent to a one-semester elementarylinear algebra course and knowledge of rudimentary analytical concepts.We beginwiththenotionsofeigenvaluesand eigenvectors;nopriorknowledgeofthese conceptsis assumed.Facts about matrices,beyond thosefound in an elementary linearalgebra course,are necessary to understand virtually any area of mathematical science,whether itbedifferential equations;probability and statistics; optimization; or applications intheoretical andapplied economics,theengineeringdisciplines,oroperations research,toname onlya few.But until recently,much of thenecessarymaterial has occurredsporadically(ornotatall)intheundergraduate andgraduatecurricula.Asinterestinappliedmathematicshasgrownandmorecourseshavebeendevotedtoadvancedmatrixtheory,the needfor atextofferinga broad selectionof topicshasbecomemoreapparent, as has theneed for a modern reference on the subject.There are several well-lovedclassics in matrix theory,but they arenot well suitedforgeneral classroom use, norfor systematic individual study.Alack of problems,applications, and motivation; an inadequate index;and a dated approach are amongthe difficulties confronting readers of some traditional references.More recent bookstend to be either elementary texts or treatises devoted to special topics. Our goalwas to write a book that would be a useful modern treatment of a broad range oftopics.One view of"matrix analysis"is that it consists of those topics in linear algebrathat have arisen out of the needs of mathematical analysis, such as multivariablecalculus,complexvariables,differentialequations,optimization,and approximationtheory.Another view is that matrix analysis is an approach to real and complex linearxV
Preface to the First Edition Linear algebra and matrix theory have long been fundamental tools in mathematical disciplines as well as fertile fields for research in their own right. In this book, and in the companion volume, Topics in Matrix Analysis, we present classical and recent results of matrix analysis that have proved to be important to applied mathematics. The book may be used as an undergraduate or graduate text and as a self-contained reference for a variety of audiences. We assume background equivalent to a one-semester elementary linear algebra course and knowledge of rudimentary analytical concepts. We begin with the notions of eigenvalues and eigenvectors; no prior knowledge of these concepts is assumed. Facts about matrices, beyond those found in an elementary linear algebra course, are necessary to understand virtually any area of mathematical science, whether it be differential equations; probability and statistics; optimization; or applications in theoretical and applied economics, the engineering disciplines, or operations research, to name only a few. But until recently, much of the necessary material has occurred sporadically (or not at all) in the undergraduate and graduate curricula. As interest in applied mathematics has grown and more courses have been devoted to advanced matrix theory, the need for a text offering a broad selection of topics has become more apparent, as has the need for a modern reference on the subject. There are several well-loved classics in matrix theory, but they are not well suited for general classroom use, nor for systematic individual study. A lack of problems, applications, and motivation; an inadequate index; and a dated approach are among the difficulties confronting readers of some traditional references. More recent books tend to be either elementary texts or treatises devoted to special topics. Our goal was to write a book that would be a useful modern treatment of a broad range of topics. One view of “matrix analysis” is that it consists of those topics in linear algebra that have arisen out of the needs of mathematical analysis, such as multivariable calculus, complex variables, differential equations, optimization, and approximation theory. Another view is that matrix analysis is an approach to real and complex linear xv
xviPrefaceto the first editionalgebraic problems that does not hesitate to use notions from analysis-such as limits,continuity,and power series -when these seem more efficient or natural than a purelyalgebraic approach.Both views of matrix analysis are reflected in the choice andtreatment oftopicsinthisbook.Wepreferthetermmatrixanalysistolinear algebraas an accuratereflection of thebroad scope and methodology of thefield.For reviewand conveniencein reference,Chaptero contains a summaryofnecessary facts from elementary linear algebra, as well as other useful, though notnecessarily elementary,facts.Chapters 1,2, and 3 contain mainly core material likelyto be included in any second course in linear algebra or matrix theory: a basic treatmentofeigenvalues,eigenvectors,and similarity;unitary similarity,Schur triangularizationand its implications,and normal matrices; and canonical forms and factorizations,includingtheJordanform,LUfactorization,QRfactorization,andcompanionmatrices.Beyond this,each chapter is developed substantially independentlyand treats in somedepth a major topic:1.Hermitianand complexsymmetric matrices (Chapter4).Wegive special emphasisto variational methods for studying eigenvalues of Hermitian matrices and includean introductionto the notion of majorization.2. Norms on vectors and matrices (Chapter 5) are essential for error analyses ofnumerical linear algebraic algorithms and for the study of matrix power series anditerative processes.We discuss the algebraic,geometric, and analytic propertiesof norms in some detail and make a careful distinction between those norm resultsformatricesthatdepend on the submultiplicativityaxiomformatrixnormsandthose that do not.3.Eigenvalue location and perturbation results (Chapter6)forgeneral (not neces-sarilyHermitian)matricesareimportantformanyapplications.Wegiveadetailedtreatment of the theory of Gersgorin regions, and some of its modern refinements,and ofrelevant graph theoretic concepts.4.Positive definite matrices (Chapter 7) and their applications, including inequalities,are considered at some length.A discussion of the polar and singular value decom-positions is included, along with applications to matrix approximation problems.5.Entry-wise nonnegativeand positive matrices(Chapter 8)arise in manyapplica-tions in which nonnegative quantities necessarily occur (probability,economics,engineering,etc.),and their remarkable theory reflects the applications.Our devel-opment of the theory of nonnegative, positive, primitive, and irreducible matricesproceeds in elementary steps based on theuse of norms.In the companion volume,furthertopics of similar interest aretreated:thefieldof values and generalizations; inertia, stable matrices, M-matrices and related specialclasses; matrix equations,Kronecker and Hadamard products; and various ways inwhich functions and matrices may be linked.This book provides the basisfor a variety of one-or two-semester coursesthroughselection of chapters and sections appropriate to a particular audience.We recommendthat an instructor make a careful preselection of sections and portions of sections ofthebookfortheneedsofaparticularcourse.ThiswouldprobablyincludeChapter1,muchof Chapters2and3,and facts aboutHermitianmatricesand normsfrom Chapters4and 5
xvi Preface to the first edition algebraic problems that does not hesitate to use notions from analysis – such as limits, continuity, and power series – when these seem more efficient or natural than a purely algebraic approach. Both views of matrix analysis are reflected in the choice and treatment of topics in this book. We prefer the term matrix analysis to linear algebra as an accurate reflection of the broad scope and methodology of the field. For review and convenience in reference, Chapter 0 contains a summary of necessary facts from elementary linear algebra, as well as other useful, though not necessarily elementary, facts. Chapters 1, 2, and 3 contain mainly core material likely to be included in any second course in linear algebra or matrix theory: a basic treatment of eigenvalues, eigenvectors, and similarity; unitary similarity, Schur triangularization and its implications, and normal matrices; and canonical forms and factorizations, including the Jordan form, LU factorization, QR factorization, and companion matrices. Beyond this, each chapter is developed substantially independently and treats in some depth a major topic: 1. Hermitian and complex symmetric matrices(Chapter 4). We give special emphasis to variational methods for studying eigenvalues of Hermitian matrices and include an introduction to the notion of majorization. 2. Norms on vectors and matrices (Chapter 5) are essential for error analyses of numerical linear algebraic algorithms and for the study of matrix power series and iterative processes. We discuss the algebraic, geometric, and analytic properties of norms in some detail and make a careful distinction between those norm results for matrices that depend on the submultiplicativity axiom for matrix norms and those that do not. 3. Eigenvalue location and perturbation results (Chapter 6) for general (not necessarily Hermitian) matrices are important for many applications. We give a detailed treatment of the theory of Gersgorin regions, and some of its modern refinements, ˇ and of relevant graph theoretic concepts. 4. Positive definite matrices(Chapter 7) and their applications, including inequalities, are considered at some length. A discussion of the polar and singular value decompositions is included, along with applications to matrix approximation problems. 5. Entry-wise nonnegative and positive matrices (Chapter 8) arise in many applications in which nonnegative quantities necessarily occur (probability, economics, engineering, etc.), and their remarkable theory reflects the applications. Our development of the theory of nonnegative, positive, primitive, and irreducible matrices proceeds in elementary steps based on the use of norms. In the companion volume, further topics of similar interest are treated: the field of values and generalizations; inertia, stable matrices, M-matrices and related special classes; matrix equations, Kronecker and Hadamard products; and various ways in which functions and matrices may be linked. This book provides the basis for a variety of one- or two-semester courses through selection of chapters and sections appropriate to a particular audience. We recommend that an instructor make a careful preselection of sections and portions of sections of the book for the needs of a particular course. This would probably include Chapter 1, much of Chapters 2 and 3, and facts about Hermitian matrices and norms from Chapters 4 and 5
Preface to the first editionxviiMost chapters contain some relatively specialized or nontraditional material.Forexample,Chapter2 includesnotonlySchur's basictheorem on unitarytriangularizationofa singlematrixbutalso a discussion of simultaneoustriangularization offamiliesofmatrices.In the section on unitary equivalence,our presentation of the usual facts isfollowed by adiscussion oftraceconditionsfor twomatrices tobe unitarily equivalent.A discussion of complex symmetric matrices in Chapter 4provides a counterpoint tothedevelopment of the classical theory of Hermitian matrices.Basic aspects of atopicappear in the initial sections of each chapter,whilemore elaborate discussions occur atthe ends of sections or in later sections.This strategyhas the advantage of presentingtopics in a sequence that enhances the book's utility as a reference. It also provides arich variety of options to the instructor.Many of the results discussed are valid or can be generalized to be valid formatrices overotherfields orin some broaderalgebraic setting.However,wedeliberatelyconfineourdomaintothereal and complexfields wherefamiliar methodsof classicalanalysis as well as formal algebraic techniques may be employed.Though we generally consider matrices to have complex entries, most examplesareconfinedtoreal matrices,andno deepknowledgeofcomplexanalysisisrequired.Acquaintance with the arithmeticofcomplexnumbers is necessaryforan understandingof matrix analysis and is covered to the extent necessary in an appendix.Other briefappendices cover several peripheral,but essential, topics such as Weierstrass's theoremand convexity.We have included many exercises and problems because wefeel these areessential to the development of an understanding of the subject and its implications.The exercises occur throughout as part of the development of each section; they aregenerally elementary and of immediate use in understanding the concepts.We rec-ommend that the reader work at least a broad selection of these.Problems are listed(in no particular order)at the end of each section; they cover a range of difficultiesand types (from theoretical to computational)and they mayextend the topic,developspecial aspects, or suggest alternateproofs of major ideas.Significant hints are givenfor the moredifficult problems.Theresults of someproblems are referred to in otherproblems or in the text itself.Wecannot overemphasize the importance of the reader'sactive involvement in carrying out the exercises and solvingproblems.Whilethebook itselfisnotabout applications,wehave,formotivational purposes,begun each chapter with a section outlining a few applications to introduce the topicofthechapter.Readers who wish to consult alternative treatments of a topic for additionalinformationarereferredtothebookslistedintheReferencessectionfollowingtheappendices.The list of book references is not exhaustive. As a practical concession to thelimits of spacein ageneral multitopicbook,wehaveminimized thenumberofcitationsin the text.Asmall selection of references to papers -such as those we have explicitlyused-doesoccurattheendof mostsectionsaccompaniedbyabriefdiscussion,butwehavemadeno attemptto collecthistorical references toclassicalresults.Extensivebibliographiesareprovidedinthemorespecializedbookswehavereferenced.We appreciate the helpful suggestions of our colleagues and students who havetaken the time to convey their reactionsto the class notes and preliminarymanuscripts
Preface to the first edition xvii Most chapters contain some relatively specialized or nontraditional material. For example, Chapter 2 includes not only Schur’s basic theorem on unitary triangularization of a single matrix but also a discussion of simultaneous triangularization of families of matrices. In the section on unitary equivalence, our presentation of the usual facts is followed by a discussion of trace conditions for two matrices to be unitarily equivalent. A discussion of complex symmetric matrices in Chapter 4 provides a counterpoint to the development of the classical theory of Hermitian matrices. Basic aspects of a topic appear in the initial sections of each chapter, while more elaborate discussions occur at the ends of sections or in later sections. This strategy has the advantage of presenting topics in a sequence that enhances the book’s utility as a reference. It also provides a rich variety of options to the instructor. Many of the results discussed are valid or can be generalized to be valid for matrices over other fields or in some broader algebraic setting. However, we deliberately confine our domain to the real and complex fields where familiar methods of classical analysis as well as formal algebraic techniques may be employed. Though we generally consider matrices to have complex entries, most examples are confined to real matrices, and no deep knowledge of complex analysis is required. Acquaintance with the arithmetic of complex numbers is necessary for an understanding of matrix analysis and is covered to the extent necessary in an appendix. Other brief appendices cover several peripheral, but essential, topics such as Weierstrass’s theorem and convexity. We have included many exercises and problems because we feel these are essential to the development of an understanding of the subject and its implications. The exercises occur throughout as part of the development of each section; they are generally elementary and of immediate use in understanding the concepts. We recommend that the reader work at least a broad selection of these. Problems are listed (in no particular order) at the end of each section; they cover a range of difficulties and types (from theoretical to computational) and they may extend the topic, develop special aspects, or suggest alternate proofs of major ideas. Significant hints are given for the more difficult problems. The results of some problems are referred to in other problems or in the text itself. We cannot overemphasize the importance of the reader’s active involvement in carrying out the exercises and solving problems. While the book itself is not about applications, we have, for motivational purposes, begun each chapter with a section outlining a few applications to introduce the topic of the chapter. Readers who wish to consult alternative treatments of a topic for additional information are referred to the books listed in the References section following the appendices. The list of book references is not exhaustive. As a practical concession to the limits of space in a general multitopic book, we have minimized the number of citations in the text. A small selection of references to papers – such as those we have explicitly used – does occur at the end of most sections accompanied by a brief discussion, but we have made no attempt to collect historical references to classical results. Extensive bibliographies are provided in the more specialized books we have referenced. We appreciate the helpful suggestions of our colleagues and students who have taken the time to convey their reactions to the class notes and preliminary manuscripts