SECONDEDITIONMATRIXANALYSISROGERA.HORN CHARLESR.JOHNSONCAMBRIDGE
MatrixAnalysisSecondEditionLinear algebra and matrix theory arefundamental tools in mathematical and physicalscience, as well as fertile fields for research.This new edition ofthe acclaimed text presentsresults of both classic and recent matrix analysis using canonical forms as a unifying theme,and demonstrates their importance in a variety of applications.The authors have thoroughly revised, updated, and expanded on the first edition. Thebook opens with an extended summary of useful concepts and facts and includes numerousnewtopicsand features,such as:.New sections on the singular value and CS decompositions.New applications of the Jordan canonical form.AnewsectionontheWeyrcanonicalformExpanded treatments of inverse problems and of block matricesAcentral role for the von Neumann tracetheorem.A new appendix with a modern list of canonical forms for a pair of Hermitianmatrices and for a symmetric-skew symmetric pair·Expanded index with more than 3,500 entries for easy referenceMore than 1,100 problems and exercises, many with hints, to reinforce understand-.ing and develop auxiliary themes such as finite-dimensional quantum systems, thecompound and adjugate matrices, and the Loewner ellipsoid:Anewappendixprovidesacollectionofproblem-solvinghintsRoger A.Horn is a Research Professor in the Department of Mathematics at the Universityof Utah.He is the author of Topics in Matrix Analysis (Cambridge University Press 1994)CharlesR.Johnson istheauthorof Topics inMatrixAnalysis(CambridgeUniversityPress1994)
Matrix Analysis Second Edition Linear algebra and matrix theory are fundamental tools in mathematical and physical science, as well as fertile fields for research. This new edition of the acclaimed text presents results of both classic and recent matrix analysis using canonical forms as a unifying theme, and demonstrates their importance in a variety of applications. The authors have thoroughly revised, updated, and expanded on the first edition. The book opens with an extended summary of useful concepts and facts and includes numerous new topics and features, such as: New sections on the singular value and CS decompositions New applications of the Jordan canonical form A new section on the Weyr canonical form Expanded treatments of inverse problems and of block matrices A central role for the von Neumann trace theorem A new appendix with a modern list of canonical forms for a pair of Hermitian matrices and for a symmetric–skew symmetric pair Expanded index with more than 3,500 entries for easy reference More than 1,100 problems and exercises, many with hints, to reinforce understanding and develop auxiliary themes such as finite-dimensional quantum systems, the compound and adjugate matrices, and the Loewner ellipsoid A new appendix provides a collection of problem-solving hints. Roger A. Horn is a Research Professor in the Department of Mathematics at the University of Utah. He is the author of Topics in Matrix Analysis (Cambridge University Press 1994). Charles R. Johnson is the author of Topics in Matrix Analysis (Cambridge University Press 1994).
Matrix AnalysisSecond EditionRoger A. HornUniversity of UtahCharles R. Johnson劳究CAMBRIDGE明UNIVERSITYPRESS
Matrix Analysis Second Edition Roger A. Horn University of Utah Charles R. Johnson
CAMBRIDGEUNIVERSITYPRESSCambridge, New York, Melbourne, Madrid, Cape Town,Singapore, Sao Paulo, Delhi, Mexico CityCambridge University Press32Avenue of the Americas, New York, NY10013-2473, USAwww.cambridge.orgInformation on this title: www.cambridge.org/9780521548236@ Roger A. Horn and Charles R. Johnson 1985, 2013This publication is in copyright. Subject to statutory exceptionand to the provisions of relevant collective licensing agreements.no reproduction of any part may take place without the writtenpermission of Cambridge University Press.First published 1985First paperback edition 1990Second edition first published 2013Printed in the United States of AmericaAcatalog record forthispublication isavailablefromtheBritish Library.LibraryofCongressCataloginginPublicationDataHorn, Roger A.Matrix analysis / Roger A. Horn, Charles R. Johnson. 2nd ed.p.cm.Includes bibliographical references and index.ISBN978-0-521-83940-2 (hardback)1.Matrices. I. Johnson, Charles R.I. Title.QA188.H662012512.9434dc232012012300ISBN978-0-521-83940-2HardbackISBN978-0-521-54823-6 PaperbackCambridge University Press has no responsibility for the persistence or accuracy of URLs for externalorthird-party Internet Web sites referred to in this publication and does not guarantee that any contenton such Web sites is, or will remain,accurate or appropriate
cambridge university press Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sao Paulo, Delhi, Mexico City ˜ Cambridge University Press 32 Avenue of the Americas, New York, NY 10013-2473, USA www.cambridge.org Information on this title: www.cambridge.org/9780521548236 C Roger A. Horn and Charles R. Johnson 1985, 2013 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 1985 First paperback edition 1990 Second edition first published 2013 Printed in the United States of America A catalog record for this publication is available from the British Library. Library of Congress Cataloging in Publication Data Horn, Roger A. Matrix analysis / Roger A. Horn, Charles R. Johnson. – 2nd ed. p. cm. Includes bibliographical references and index. ISBN 978-0-521-83940-2 (hardback) 1. Matrices. I. Johnson, Charles R. II. Title. QA188.H66 2012 512.9 434–dc23 2012012300 ISBN 978-0-521-83940-2 Hardback ISBN 978-0-521-54823-6 Paperback Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party Internet Web sites referred to in this publication and does not guarantee that any content on such Web sites is, or will remain, accurate or appropriate.
To the matrix theory community
To the matrix theory community
ContentspagexiPrefacetothe SecondEditionXVPrefacetotheFirstEdition10 Review and Miscellanea10.0Introduction10.1Vector spaces50.2Matrices80.3Determinants120.4Rank0.514Nonsingularity150.6The Euclidean inner product and norm160.7Partitioned sets and matrices210.8Determinants again300.9Special types of matrices390.10Change of basis400.11Equivalence relations4311Eigenvalues, Eigenvectors, and Similarity431.0Introduction441.1The eigenvalue-eigenvector equation491.2The characteristic polynomial and algebraic multiplicity571.3Similarity751.4Left and right eigenvectors and geometric multiplicity832Unitary Similarity and Unitary Equivalence832.0Introduction832.1Unitary matrices and the QR factorization942.2Unitary similarity1012.3Unitary and real orthogonal triangularizations1082.4Consequences of Schur's triangularization theorem1312.5Normal matricesvii
Contents Preface to the Second Edition page xi Preface to the First Edition xv 0 Review and Miscellanea 1 0.0 Introduction 1 0.1 Vector spaces 1 0.2 Matrices 5 0.3 Determinants 8 0.4 Rank 12 0.5 Nonsingularity 14 0.6 The Euclidean inner product and norm 15 0.7 Partitioned sets and matrices 16 0.8 Determinants again 21 0.9 Special types of matrices 30 0.10 Change of basis 39 0.11 Equivalence relations 40 1 Eigenvalues, Eigenvectors, and Similarity 43 1.0 Introduction 43 1.1 The eigenvalue–eigenvector equation 44 1.2 The characteristic polynomial and algebraic multiplicity 49 1.3 Similarity 57 1.4 Left and right eigenvectors and geometric multiplicity 75 2 Unitary Similarity and Unitary Equivalence 83 2.0 Introduction 83 2.1 Unitary matrices and the QR factorization 83 2.2 Unitary similarity 94 2.3 Unitary and real orthogonal triangularizations 101 2.4 Consequences of Schur’s triangularization theorem 108 2.5 Normal matrices 131 vii
viliContents1492.6Unitary equivalence and the singular value decomposition1592.7TheCSdecomposition1633 Canonical Forms for Similarity and Triangular Factorizations1633.0Introduction1643.1The Jordan canonical form theorem1753.2Consequences of the Jordan canonical form1913.3The minimal polynomial and the companion matrix2013.4The real Jordan and Weyr canonical forms2163.5Triangular factorizations and canonical forms2254Hermitian Matrices, Symmetric Matrices, and Congruences2254.0Introduction2274.1Properties and characterizations of Hermitian matrices2344.2Variational characterizationsand subspaceintersections2394.3Eigenvalue inequalities for Hermitian matrices2604.4Unitary congruence and complex symmetric matrices2794.5Congruences and diagonalizations3004.6Consimilarity and condiagonalization3135 Norms for Vectors and Matrices3135.0Introduction3145.1Definitions of norms and inner products3205.2Examples of norms and inner products5.3324Algebraicproperties of norms5.4324Analytic properties of norms5.5335Duality and geometric properties of norms3405.6Matrix norms5.7371Vector norms on matrices5.8381Condition numbers: inverses and linear systems3876Location and Perturbation of Eigenvalues3876.0Introduction3876.1Gersgorin discs3966.2Gersgorin discs - a closer look6.3405Eigenvalue perturbation theorems4136.4Other eigenvalue inclusion sets4257Positive Definiteand Semidefinite Matrices4257.0Introduction7.1429Definitions and properties7.2438Characterizations and properties4487.3The polar and singular value decompositions4587.4Consequences of the polar and singular value decompositions4777.5The Schur product theorem4857.6Simultaneous diagonalizations, products, and convexity4937.7The Loewner partial order and block matrices5057.8Inequalities involving positive definite matrices
viii Contents 2.6 Unitary equivalence and the singular value decomposition 149 2.7 The CS decomposition 159 3 Canonical Forms for Similarity and Triangular Factorizations 163 3.0 Introduction 163 3.1 The Jordan canonical form theorem 164 3.2 Consequences of the Jordan canonical form 175 3.3 The minimal polynomial and the companion matrix 191 3.4 The real Jordan and Weyr canonical forms 201 3.5 Triangular factorizations and canonical forms 216 4 Hermitian Matrices, Symmetric Matrices, and Congruences 225 4.0 Introduction 225 4.1 Properties and characterizations of Hermitian matrices 227 4.2 Variational characterizations and subspace intersections 234 4.3 Eigenvalue inequalities for Hermitian matrices 239 4.4 Unitary congruence and complex symmetric matrices 260 4.5 Congruences and diagonalizations 279 4.6 Consimilarity and condiagonalization 300 5 Norms for Vectors and Matrices 313 5.0 Introduction 313 5.1 Definitions of norms and inner products 314 5.2 Examples of norms and inner products 320 5.3 Algebraic properties of norms 324 5.4 Analytic properties of norms 324 5.5 Duality and geometric properties of norms 335 5.6 Matrix norms 340 5.7 Vector norms on matrices 371 5.8 Condition numbers: inverses and linear systems 381 6 Location and Perturbation of Eigenvalues 387 6.0 Introduction 387 6.1 Gersgorin discs ˇ 387 6.2 Gersgorin discs – a closer look ˇ 396 6.3 Eigenvalue perturbation theorems 405 6.4 Other eigenvalue inclusion sets 413 7 Positive Definite and Semidefinite Matrices 425 7.0 Introduction 425 7.1 Definitions and properties 429 7.2 Characterizations and properties 438 7.3 The polar and singular value decompositions 448 7.4 Consequences of the polar and singular value decompositions 458 7.5 The Schur product theorem 477 7.6 Simultaneous diagonalizations, products, and convexity 485 7.7 The Loewner partial order and block matrices 493 7.8 Inequalities involving positive definite matrices 505
ixContents5178Positiveand NonnegativeMatrices5178.0Introduction5198.1Inequalities and generalities5248.2Positivematrices5298.3Nonnegative matrices5338.4Irreducible nonnegative matrices5408.5Primitive matrices5458.6A general limit theorem5478.7Stochastic and doubly stochastic matrices555AppendixAComplexNumbers557AppendixB ConvexSetsandFunctions561AppendixCTheFundamentalTheorem of AlgebraAppendix D Continuity of Polynomial Zeroes and Matrix563Eigenvalues565AppendixE Continuity, Compactness,and Weierstrass's Theorem567AppendixF Canonical Pairs571References575Notation579Hints for Problems607Index
Contents ix 8 Positive and Nonnegative Matrices 517 8.0 Introduction 517 8.1 Inequalities and generalities 519 8.2 Positive matrices 524 8.3 Nonnegative matrices 529 8.4 Irreducible nonnegative matrices 533 8.5 Primitive matrices 540 8.6 A general limit theorem 545 8.7 Stochastic and doubly stochastic matrices 547 Appendix A Complex Numbers 555 Appendix B Convex Sets and Functions 557 Appendix C The Fundamental Theorem of Algebra 561 Appendix D Continuity of Polynomial Zeroes and Matrix Eigenvalues 563 Appendix E Continuity, Compactness, and Weierstrass’s Theorem 565 Appendix F Canonical Pairs 567 References 571 Notation 575 Hints for Problems 579 Index 607
Preface to the Second EditionThe basic structure of the first edition has been preserved in the second because itremains congruent with thegoal of writing"a book that would be a useful moderntreatment of a broad range of topics..[that] may be used as an undergraduate orgraduatetext and as a self-contained referencefora variety ofaudiences."Thequotationisfrom thePreface to the First Edition, whose declaration of goals forthe work remainsunchanged.What is different in the second edition?The core role of canonical forms has been expanded as a unifying element inunderstanding similarity (complex,real, and simultaneous),unitary equivalence, uni-tary similarity,congruence,*congruence,unitary congruence,triangular equivalence,andother equivalence relations.More attention is paid to casesof equality in themanyinequalitiesconsidered inthebook.Block matrices are aubiquitous feature of theexpositionintheneweditionLearningmathematics hasneverbeen a spectatorsport, so the newedition continuesto emphasize the value of exercises and problems for the active reader. Numerous2-by-2examples illustrate conceptsthroughoutthebook.Problemthreads (some spanseveral chapters) develop special topics as the foundation for them evolves in the text.For example,there are threads involving the adjugatematrix,the compound matrix,finite-dimensional quantum systems, the Loewner ellipsoid and the Loewner-Johnmatrix,and normalizable matrices; see the index for page referencesfor these threads.Thefirsteditionhadabout690problems;the second editionhasmorethan1,100.Many problems have hints; they may be found in an appendix that appears just beforethe index.A comprehensive index is essential for a book that is intended for sustained use asa reference after initial use as a text. The index to the first edition had about 1,200entries;thecurrentindexhasmorethan3,500entries.Anunfamiliartermencounteredin the text should be looked up in the index, where a pointer to a definition (in ChapterOorelsewhere)islikelytobefound.New discoveries since 1985 have shaped the presentation of many topics and havestimulated inclusion of some new ones.A few examples of the latter are the Jordanxi
Preface to the Second Edition The basic structure of the first edition has been preserved in the second because it remains congruent with the goal of writing “a book that would be a useful modern treatment of a broad range of topics.[that] may be used as an undergraduate or graduate text and as a self-contained reference for a variety of audiences.” The quotation is from the Preface to the First Edition, whose declaration of goals for the work remains unchanged. What is different in the second edition? The core role of canonical forms has been expanded as a unifying element in understanding similarity (complex, real, and simultaneous), unitary equivalence, unitary similarity, congruence, *congruence, unitary congruence, triangular equivalence, and other equivalence relations. More attention is paid to cases of equality in the many inequalities considered in the book. Block matrices are a ubiquitous feature of the exposition in the new edition. Learning mathematics has never been a spectator sport, so the new edition continues to emphasize the value of exercises and problems for the active reader. Numerous 2-by-2 examples illustrate concepts throughout the book. Problem threads (some span several chapters) develop special topics as the foundation for them evolves in the text. For example, there are threads involving the adjugate matrix, the compound matrix, finite-dimensional quantum systems, the Loewner ellipsoid and the Loewner–John matrix, and normalizable matrices; see the index for page references for these threads. The first edition had about 690 problems; the second edition has more than 1,100. Many problems have hints; they may be found in an appendix that appears just before the index. A comprehensive index is essential for a book that is intended for sustained use as a reference after initial use as a text. The index to the first edition had about 1,200 entries; the current index has more than 3,500 entries. An unfamiliar term encountered in the text should be looked up in the index, where a pointer to a definition (in Chapter 0 or elsewhere) is likely to be found. New discoveries since 1985 have shaped the presentation of many topics and have stimulated inclusion of some new ones. A few examples of the latter are the Jordan xi
xiiPreface to the second editioncanonical form of a rank-one perturbation, motivated by enduring student interest inthe Google matrix; a generalization of real normal matrices (normal matrices A suchthat AA is real); computable block matrix criteria for simultaneous unitary similarityor simultaneous unitarycongruence;G.Belitskii'sdiscoverythatamatrixcommuteswith a Weyr canonical form if and only if it is block upper triangular and has aspecial structure;the discovery by K.C.O'Meara and C.Vinsonhaler that, unlikethecorresponding situationfor the Jordan canonical form, a commuting family can besimultaneously upper triangularized by similarity in such a way that any one specifiedmatrix in the family is in Weyr canonical form; and canonical forms for congruenceand*congruence.Queries frommanyreaders have motivated changes in the way that some topics arepresented.For example, discussion of Lidskii's eigenvalue majorization inequalitieswas moved from a section primarilydevoted to singular value inequalities to thesection where majorization is discussed.Fortunately,a splendid new proof of Lidski'sinequalitiesbyC.K.Li andR.Mathias becameavailableand wasperfectlyalignedwith Chapter 4's new approach to eigenvalue inequalities for Hermitian matrices.AsecondexampleisanewproofofBirkhoff'stheorem,whichhasaverydifferentflavorfromtheproof inthefirstedition.Instructorsaccustomedtotheorderoftopicsinthefirsteditionmaybeinterestedina chapter-by-chapter summary of what is different in the new edition:0.Chapter 0 has been expanded by about75% to include a more comprehensivesummary of useful concepts and facts. It is intended to serve as an as-neededreference.Definitions of terms andnotationsused throughout the book can befound here, but it has no exercises or problems. Formal courses and reading forself-studytypicallybegin withChapter1.1. Chapter 1 contains new examples related to similarity and the characteristic poly-nomial, as well as an enhanced emphasis on the role of left eigenvectors in matrixanalysis.2. Chapter 2 contains a detailed presentation of real orthogonal similarity, anexposition of McCoy's theorem on simultaneous triangularization, and a rigor-ous treatment of continuity of eigenvalues that makes essential use of both theunitary and triangular aspects of Schur's unitary triangularization theorem. Sec-tion 2.4 (Consequences of Schur's triangularization theorem) is almost twice thelength of the corresponding section in the first edition. There are two new sections,one devoted to the singular value decomposition and one devoted to the Cs de-composition.Earlyintroduction ofthe singular valuedecomposition permits thisessential tool ofmatrixanalysistobeused throughouttherestof thebook.3.Chapter3 approaches the Jordan canonical form via the Weyr characteristic; itcontains an exposition of the Weyr canonical form and its unitary variant thatwerenot inthe first edition.Section3.2(Consequences of the Jordan canonicalform)discussesmanynewapplications;itcontains60%morematerialthanthecorresponding section in the first edition.4.Chapter 4 now has a moderm presentation of variational principles and eigen-value inequalities for Hermitian matrices via subspace intersections. It containsanexpandedtreatmentof inverseproblemsassociated with interlacing andother
xii Preface to the second edition canonical form of a rank-one perturbation, motivated by enduring student interest in the Google matrix; a generalization of real normal matrices (normal matrices A such that AA¯ is real); computable block matrix criteria for simultaneous unitary similarity or simultaneous unitary congruence; G. Belitskii’s discovery that a matrix commutes with a Weyr canonical form if and only if it is block upper triangular and has a special structure; the discovery by K. C. O’Meara and C. Vinsonhaler that, unlike the corresponding situation for the Jordan canonical form, a commuting family can be simultaneously upper triangularized by similarity in such a way that any one specified matrix in the family is in Weyr canonical form; and canonical forms for congruence and ∗congruence. Queries from many readers have motivated changes in the way that some topics are presented. For example, discussion of Lidskii’s eigenvalue majorization inequalities was moved from a section primarily devoted to singular value inequalities to the section where majorization is discussed. Fortunately, a splendid new proof of Lidskii’s inequalities by C. K. Li and R. Mathias became available and was perfectly aligned with Chapter 4’s new approach to eigenvalue inequalities for Hermitian matrices. A second example is a new proof of Birkhoff’s theorem, which has a very different flavor from the proof in the first edition. Instructors accustomed to the order of topics in the first edition may be interested in a chapter-by-chapter summary of what is different in the new edition: 0. Chapter 0 has been expanded by about 75% to include a more comprehensive summary of useful concepts and facts. It is intended to serve as an as-needed reference. Definitions of terms and notations used throughout the book can be found here, but it has no exercises or problems. Formal courses and reading for self-study typically begin with Chapter 1. 1. Chapter 1 contains new examples related to similarity and the characteristic polynomial, as well as an enhanced emphasis on the role of left eigenvectors in matrix analysis. 2. Chapter 2 contains a detailed presentation of real orthogonal similarity, an exposition of McCoy’s theorem on simultaneous triangularization, and a rigorous treatment of continuity of eigenvalues that makes essential use of both the unitary and triangular aspects of Schur’s unitary triangularization theorem. Section 2.4 (Consequences of Schur’s triangularization theorem) is almost twice the length of the corresponding section in the first edition. There are two new sections, one devoted to the singular value decomposition and one devoted to the C S decomposition. Early introduction of the singular value decomposition permits this essential tool of matrix analysis to be used throughout the rest of the book. 3. Chapter 3 approaches the Jordan canonical form via the Weyr characteristic; it contains an exposition of the Weyr canonical form and its unitary variant that were not in the first edition. Section 3.2 (Consequences of the Jordan canonical form) discusses many new applications; it contains 60% more material than the corresponding section in the first edition. 4. Chapter 4 now has a modern presentation of variational principles and eigenvalue inequalities for Hermitian matrices via subspace intersections. It contains an expanded treatment of inverse problems associated with interlacing and other