Matrices: Theory and Applications Denis Serre Springer 216 Graduate Texts in Mathematics Editorial Board S. Axler F.W. Gehring K.A. Ribet This page intentionally left blank Denis Serre Matrices Theory and Applications DenisSerre EcoleNormaleSupe´rieuredeLyon UMPA LyonCedex07,F-69364 France [email protected] EditorialBoard: S.Axler F.W.Gehring K.A.Ribet MathematicsDepartment MathematicsDepartment MathematicsDepartment SanFranciscoState EastHall UniversityofCalifornia, University UniversityofMichigan Berkeley SanFrancisco,CA94132 AnnArbor,MI48109 Berkeley,CA94720-3840 USA USA USA [email protected] [email protected] [email protected] MathematicsSubjectClassification(2000):15-01 LibraryofCongressCataloging-in-PublicationData Serre,D.(Denis) [Matrices.English.] Matrices:theoryandapplications/DenisSerre. p.cm.—(Graduatetextsinmathematics;216) Includesbibliographicalreferencesandindex. ISBN0-387-95460-0(alk.paper) 1.Matrices I.Title. II.Series. QA188.S47132002 512.9′434—dc21 2002022926 ISBN0-387-95460-0 Printedonacid-freepaper. TranslatedfromLesMatrices:The´orieetpratique,publishedbyDunod(Paris),2001. 2002Springer-VerlagNewYork,Inc. All rights reserved. This work may not be translated or copied in whole or in part without the writtenpermissionofthepublisher(Springer-VerlagNewYork,Inc.,175FifthAvenue,NewYork, NY10010,USA),exceptforbriefexcerptsinconnectionwithreviewsorscholarlyanalysis.Use inconnection withany formof informationstorageand retrieval,electronic adaptation,computer software,orbysimilarordissimilarmethodologynowknownorhereafterdevelopedisforbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if theyarenotidentifiedassuch,isnottobetakenasanexpressionofopinionastowhetherornot theyaresubjecttoproprietaryrights. PrintedintheUnitedStatesofAmerica. 9 8 7 6 5 4 3 2 1 SPIN10869456 Typesetting:PagescreatedbytheauthorinLaTeX2e. www.springer-ny.com Springer-Verlag NewYork Berlin Heidelberg AmemberofBertelsmannSpringerScience+BusinessMediaGmbH To Pascale and Joachim This page intentionally left blank Preface The study of matrices occupies a singular place within mathematics. It is still an area of active research, and it is used by every mathematician and by many scientists working in various specialities. Several examples illustrate its versatility: • Scientific computing librariesbegangrowingaroundmatrix calculus. Asamatteroffact,thediscretizationofpartialdifferentialoperators is an endless source of linear finite-dimensional problems. • At a discrete level, the maximum principle is related to nonnegative matrices. • Controltheoryandstabilizationofsystemswithfinitelymanydegrees of freedom involve spectral analysis of matrices. • The discrete Fourier transform,including the fast Fourier transform, makes use of Toeplitz matrices. • Statistics is widely based on correlation matrices. • The generalized inverse is involved in least-squares approximation. • Symmetric matrices are inertia, deformation, or viscous tensors in continuum mechanics. • Markov processes involve stochastic or bistochastic matrices. • Graphs can be described in a useful way by square matrices. viii Preface • Quantum chemistry is intimately related to matrix groups and their representations. • The caseofquantummechanicsis especiallyinteresting:Observables are Hermitian operators, their eigenvalues are energy levels. In the early years, quantum mechanics was called “mechanics of matrices,” and it has now given rise to the development of the theory of large random matrices. See [23] for a thorough account of this fashionable topic. This text was conceived during the years 1998–2001,on the occasion of a course that I taught at the E´cole Normale Sup´erieure de Lyon. As such, every result is accompanied by a detailed proof. During this course I tried toinvestigatealltheprincipalmathematicalaspectsofmatrices:algebraic, geometric, and analytic. In some sense, this is not a specialized book. For instance, it is not as detailed as [19] concerning numerics, or as [35] on eigenvalue problems, or as [21] about Weyl-type inequalities. But it covers, at a slightly higher than basic level, all these aspects, and is therefore well suited for a gradu- ate program. Students attracted by more advanced material will find one or two deeper results in each chapter but the first one, given with full proofs. They will also find further information in about the half of the 170 exercises. The solutions for exercises are available on the author’s site http://www.umpa.ens-lyon.fr/˜serre/exercises.pdf. This book is organized into ten chapters. The first three contain the basics of matrix theory and should be known by almost every graduate student in any mathematical field. The other parts can be read more or less independently of each other. However, exercises in a given chapter sometimes refer to the material introduced in another one. ThistextwasfirstpublishedinFrenchbyMasson(Paris)in2000,under the title Les Matrices: th´eorie et pratique. I have taken the opportunity during the translation process to correct typos and errors, to index a list of symbols, to rewrite some unclear paragraphs, and to add a modest amount of material and exercises. In particular, I added three sections, concerning alternate matrices, the singular value decomposition, and the Moore–Penrosegeneralizedinverse.Therefore,this edition differs fromthe French one by about 10 percent of the contents. Acknowledgments. Many thanks to the Ecole Normale Sup´erieure de Lyon and to my colleagues who have had to put up with my talking to them so often about matrices. Special thanks to Sylvie Benzoni for her constant interest and useful comments. Lyon, France Denis Serre December 2001 Contents Preface vii List of Symbols xiii 1 Elementary Theory 1 1.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Change of Basis . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Square Matrices 15 2.1 Determinants and Minors. . . . . . . . . . . . . . . . . . 15 2.2 Invertibility . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Alternate Matrices and the Pfaffian . . . . . . . . . . . . 21 2.4 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . 23 2.5 The Characteristic Polynomial . . . . . . . . . . . . . . . 24 2.6 Diagonalization . . . . . . . . . . . . . . . . . . . . . . . 28 2.7 Trigonalization. . . . . . . . . . . . . . . . . . . . . . . . 29 2.8 Irreducibility . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3 Matrices with Real or Complex Entries 40 3.1 Eigenvalues of Real- and Complex-Valued Matrices . . . 43 3.2 Spectral Decomposition of Normal Matrices . . . . . . . 45 3.3 Normal and Symmetric Real-Valued Matrices . . . . . . 47