Matrices: Theory And Applications
Matrices:Theory and ApplicationsDenis SerreSpringer
Graduate Texts in Mathematics216Editorial BoardS. Axler F.W. Gehring K.A. Ribet
This page intentionally left blank
Denis SerreMatricesTheory and Applications
Denis SerreEcole Normale Supérieure de LyonUMPALyon Cedex 07, F-69364FranceDenis.SERRE@umpa.ens-lyon.frEditorial Board:S. AxlerMathematics DepartmentSan Francisco StateUniversitySan Francisco, CA 94132USAaxler@sfsu.eduF.W. GehringMathematics DepartmentEast HallUniversity of MichiganAnn Arbor, MI 48109USAfgehring@math.lsa.umich.eduK.A. RibetMathematics DepartmentUniversity of California,BerkeleyBerkeley, CA 94720-3840USAribet@math.berkeley.eduMathematics Subject Classification (2000): 15-01Library of Congress Cataloging-in-Publication DataSerre, D. (Denis)[Matrices. English.]Matrices : theory and applications / Denis Serre.p. cm.—(Graduate texts in mathematics ; 216)Includes bibliographical references and index.ISBN 0-387-95460-0 (alk. paper)1. Matrices I. Title. II. Series.QA188 .S4713 2002512.9′434—dc212002022926ISBN 0-387-95460-0Printed on acid-free paper.Translated from Les Matrices: Théorie et pratique, published by Dunod (Paris), 2001. 2002 Springer-Verlag New York, Inc.All rights reserved. This work may not be translated or copied in whole or in part without thewritten permission of the publisher (Springer-Verlag New York, Inc., 175 Fifth Avenue, New York,NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Usein connection with any form of information storage and retrieval, electronic adaptation, computersoftware, or by similar or dissimilar methodology now known or hereafter developed is forbidden.The use in this publication of trade names, trademarks, service marks, and similar terms, even ifthey are not identified as such, is not to be taken as an expression of opinion as to whether or notthey are subject to proprietary rights.Printed in the United States of America.9 8 7 6 5 4 3 2 1SPIN 10869456Typesetting: Pages created by the author in LaTeX2e.www.springer-ny.comSpringer-Verlag New York Berlin HeidelbergA member of BertelsmannSpringer Science Business Media GmbH
To Pascale and Joachim
This page intentionally left blank
PrefaceThe study of matrices occupies a singular place within mathematics. Itis still an area of active research, and it is used by every mathematicianand by many scientists working in various specialities. Several examplesillustrate its versatility: Scientific computing libraries began growing around matrix calculus.As a matter of fact, the discretization of partial differential operatorsis an endless source of linear finite-dimensional problems. At a discrete level, the maximum principle is related to nonnegativematrices. Control theory and stabilization of systems with finitely many degreesof 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 incontinuum mechanics. Markov processes involve stochastic or bistochastic matrices. Graphs can be described in a useful way by square matrices.
viiiPreface Quantum chemistry is intimately related to matrix groups and theirrepresentations. The case of quantum mechanics is especially interesting: Observablesare Hermitian operators, their eigenvalues are energy levels. In theearly years, quantum mechanics was called “mechanics of matrices,”and it has now given rise to the development of the theory of largerandom matrices. See [23] for a thorough account of this fashionabletopic.This text was conceived during the years 1998–2001, on the occasion ofa course that I taught at the École Normale Supérieure de Lyon. As such,every result is accompanied by a detailed proof. During this course I triedto investigate all the principal mathematical aspects of matrices: algebraic,geometric, and analytic.In some sense, this is not a specialized book. For instance, it is not asdetailed as [19] concerning numerics, or as [35] on eigenvalue problems,or as [21] about Weyl-type inequalities. But it covers, at a slightly higherthan basic level, all these aspects, and is therefore well suited for a graduate program. Students attracted by more advanced material will find oneor two deeper results in each chapter but the first one, given with fullproofs. They will also find further information in about the half of the170 exercises. The solutions for exercises are available on the author’s sitehttp://www.umpa.ens-lyon.fr/ serre/exercises.pdf.This book is organized into ten chapters. The first three contain thebasics of matrix theory and should be known by almost every graduatestudent in any mathematical field. The other parts can be read more orless independently of each other. However, exercises in a given chaptersometimes refer to the material introduced in another one.This text was first published in French by Masson (Paris) in 2000, underthe title Les Matrices: théorie et pratique. I have taken the opportunityduring the translation process to correct typos and errors, to index a listof symbols, to rewrite some unclear paragraphs, and to add a modestamount of material and exercises. In particular, I added three sections,concerning alternate matrices, the singular value decomposition, and theMoore–Penrose generalized inverse. Therefore, this edition differs from theFrench one by about 10 percent of the contents.Acknowledgments. Many thanks to the Ecole Normale Supérieure de Lyonand to my colleagues who have had to put up with my talking to themso often about matrices. Special thanks to Sylvie Benzoni for her constantinterest and useful comments.Lyon, FranceDecember 2001Denis Serre
ContentsPrefaceviiList of Symbolsxiii1 Elementary Theory1.1Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2Change of Basis . . . . . . . . . . . . . . . . . . . . . . .1.3Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . .118132 Square Matrices2.1Determinants and Minors . . . . . .2.2Invertibility . . . . . . . . . . . . .2.3Alternate Matrices and the Pfaffian2.4Eigenvalues and Eigenvectors . . .2.5The Characteristic Polynomial . . .2.6Diagonalization . . . . . . . . . . .2.7Trigonalization . . . . . . . . . . . .2.8Irreducibility . . . . . . . . . . . . .2.9Exercises . . . . . . . . . . . . . . .151519212324282930313 Matrices with Real or Complex Entries3.1Eigenvalues of Real- and Complex-Valued Matrices . . .3.2Spectral Decomposition of Normal Matrices . . . . . . .3.3Normal and Symmetric Real-Valued Matrices . . . . . .40434547.
xContents3.43.5The Spectrum and the Diagonal of Hermitian Matrices .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . .4 Norms4.1A Brief Review . . . . . . . . . .4.2Householder’s Theorem . . . . . .4.3An Interpolation Inequality . . .4.4A Lemma about Banach Algebras4.5The Gershgorin Domain . . . . .4.6Exercises . . . . . . . . . . . . . .5155.616166677071735 Nonnegative Matrices5.1Nonnegative Vectors and Matrices . . . . . . .5.2The Perron–Frobenius Theorem: Weak Form .5.3The Perron–Frobenius Theorem: Strong Form5.4Cyclic Matrices . . . . . . . . . . . . . . . . .5.5Stochastic Matrices . . . . . . . . . . . . . . .5.6Exercises . . . . . . . . . . . . . . . . . . . . .80808182858791.6 Matrices with Entries in a Principal Ideal Domain;Jordan Reduction6.1Rings, Principal Ideal Domains . . . . . . . . . . . . . .6.2Invariant Factors of a Matrix . . . . . . . . . . . . . . . .6.3Similarity Invariants and Jordan Reduction . . . . . . .6.4Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . .97971011041117 Exponential of a Matrix, Polar Decomposition, andClassical Groups1147.1The Polar Decomposition . . . . . . . . . . . . . . . . . .1147.2Exponential of a Matrix . . . . . . . . . . . . . . . . . .1167.3Structure of Classical Groups . . . . . . . . . . . . . . .1207.4The Groups U(p, q) . . . . . . . . . . . . . . . . . . . . .1227.5The Orthogonal Groups O(p, q) . . . . . . . . . . . . . .1231277.6The Symplectic Group Spn . . . . . . . . . . . . . . . .7.7Singular Value Decomposition . . . . . . . . . . . . . . .1287.8Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . .1308 Matrix Factorizations8.1The LU Factorization . . . . . .8.2Choleski Factorization . . . . .8.3The QR Factorization . . . . . .8.4The Moore–Penrose Generalized8.5Exercises . . . . . . . . . . . . . . . . . . . . . . . . .Inverse. . . . .9 Iterative Methods for Linear Problems.136137142143145147149
Contents9.19.29.39.49.59.6A Convergence Criterion . . . . . . . .Basic Methods . . . . . . . . . . . . . .Two Cases of Convergence . . . . . . .The Tridiagonal Case . . . . . . . . . .The Method of the Conjugate GradientExercises . . . . . . . . . . . . . . . . .10 Approximation of Eigenvalues10.1 Hessenberg Matrices . . . .10.2 The QR Method . . . . . . .10.3 The Jacobi Method . . . . .10.4 The Power Methods . . . . .10.5 Leverrier’s Method . . . . .10.6 Exercises . . . . . . . . . . nces195Index199
This page intentionally left blank
List of Symbols A , 80a b, 97A B, 59A† , 145A 0, 80a b, 52a b, 97A , 15, 97B C, 13(b), 97BP , 106Cn , 33Cr , 83 n , 87δij , 5det M , 16Di , 71diag(d1 , . . . , dn ), 5dim E, 3dimK F , 3Dk (N ), 102e, 87ei , 3EK (λ), 28Eλ , 29End(E), 7 (σ), 16exp A, 116F G, 2F G, 3F G, 12F , 11G, 152G, 121G(A), 71Gα , 125GC , 3gcd, 98GLn (A), 20G0 , 126H h, 42H 0n , 42Hn , 41HPDn , 42 H, 115 , imaginary part, 56
xivList of SymbolsOn (K), 200nm , 5O n , 123O(p, q), 120 A , 160In , 5J, 151J(a; r), 110Jik , 100J2 , 132J3 , 132J4 , 132Pf, 22PG , 156π0 , 125PJ , 156PM , 24Pω , 156p , 62PSL2 (IR), 56K(A), 162K, 4ker M , 7ker u, 7KI , 2K(M ), 6Kn , 57K[X], 15k[X, Y ], 99RA (F ), 57rk M , 5, real part, 63R(h; A), 92ρ(A), 61R(M ), 8r(x), 70, 160λk (A), 57L(E, F ), 7Lω , 152adj M , 17M̄ , 40M̂ , 17i1 i2 · · ·Mj1 j2 · · ·M k, 6M 1 , 20M k , 20M T , 20[M, N ], 6Mn (K), 5Mn m (K), 5M , 40M , 40M T , 10A , 64A p , 65x p , 61x A , 154x , 61· , 64 · , 65ωJ , 1580n , 5ipjp , 17x, y , 11, 41S n , 90σr , 188sj (A), 75sk (a), 52SLn (A), 20sm , 189S n , 15SOn (K), 20S 1 , 86Sp(M ), 24SpK (M ), 24SPDn , 42Spm , 120Spm , 120S 2 , 56, 126SUn , 41Symn (K), 10τ , 151τCG , 164Tk , 162Tr M , 25Un , 41U p , 85
List of SymbolsU(p, q), 120u , 42uT , 11V (a), 173 x , 80x y, 80x 0, 80x 0, 80xv
This page intentionally left blank
1Elementary Theory1.1 Basics1.1.1 Vectors and ScalarsFields. Let (K, , ·) be a field. It could be IR, the field of real numbers, CC(complex numbers), or, more rarely, QQ (rational numbers). Other choicesare possible, of course. The elements of K are called scalars.Given a field k, one may build larger fields containing k: algebraic extensions k(α1 , . . . , αn ), fields of rational fractions k(X1 , . . . , Xn ), fields offormal power series k[[X1 , . . . , Xn ]]. Since they are rarely used in this book,we do not define them and let the reader consult his or her favorite textbookon abstract algebra.The digits 0 and 1 have the usual meaning in a field K, with 0 x 1 · x x. Let us consider the subring ZZ1, composed of all sums (possiblyempty) of the form (1 · · · 1). Then ZZ1 is isomorphic to either ZZ orto a field ZZ/pZZ. In the latter case, p is a prime number, and we call it thecharacteristic of K. In the former case, K is said to have characteristic 0.Vector spaces. Let (E, ) be a commutative group. Since E is usuallynot a subset of K, it is an abuse of notation that we use for the additivelaws of both E and K. Finally, let(a, x)K E ax, E,
21. Elementary Theorybe a map such that(a b)x ax bx,a(x y) ax ay.One says that E is a vector space over K (one often speaks of a K-vectorspace) if moreover,a(bx) (ab)x,1x x,hold for all a, b K and x E. The elements of E are called vectors. In avector space one always has 0x 0 (more precisely, 0K x 0E ).When P, Q K and F, G E, one denotes by P Q (respectively P Q, F G, P F ) the set of products pq as (p, q) ranges over P Q (respectivelyp q, f g, pf as p, q, f, g range over P, Q, F, G). A subgroup (F, ) of (E, )that is stable under multiplication by scalars, i.e., such that KF F , isagain a K-vector space. One says that it is a linear subspace of E, or just asubspace. Observe that F , as a subgroup, is nonempty, since it contains 0E .The intersection of any family of linear subspaces is a linear subspace. Thesum F G of two linear subspaces is again a linear subspace. The trivialformula (F G) H F (G H) allows us to define unambiguouslyF G H and, by induction, the sum of any finite family of subsets of E.When these subsets are linear subspaces, their sum is also a linear subspace.Let I be a set. One denotes by K I the set of maps a (ai )i I : I Kwhere only finitely many of the ai ’s are nonzero. This set is naturallyendowed with a K-vector space structure, by the addition and productlaws(a b)i : ai bi ,(λa)i : λai .Let E be a vector space and let i fi be a map from I to E. A linearcombination of (fi )i I is a sum ai f i ,i Iwhere the ai ’s are scalars, only finitely many of which are nonzero (in otherwords, (ai )i I K I ). This sum involves only finitely many terms. It is avector of E. The family (fi )i I is free if every linear combination but thetrivial one (when all coefficients are zero) is nonzero. It is a generatingfamily if every vector of E is a linear combination of its elements. In otherwords, (fi )i I is free (respectively generating) if the mapKI(ai )i I E, ai f i ,i Iis injective (respectively onto). Last, one says that (fi )i I is a basis of E ifit is free and generating. In that case, the above map is bijective, and it isactually an isomorphism between vector spaces.
1.1. Basics3If G E, one often identifies G and the associated family (g)g G . The setG of linear combinations of elements of G is a linear subspace E, called thelinear subspace spanned by G. It is the smallest linear subspace E containingG, equal to the intersection of all linear subspaces containing G. The subsetG is generating when G E.One can prove that every K-vector space admits at least one basis. Inthe most general setting, this is a consequence of the axiom of choice.All the bases of E have the same cardinality, which is therefore called thedimension of E, denoted by dim E. The dimension is an upper (respectivelya lower) bound for the cardinality of free (respectively generating) families.In this book we shall only use finite-dimensional vector spaces. If F, G aretwo linear subspaces of E, the following formula holds:dim F dim G dim F G dim(F G).If F G {0}, one writes F G instead of F G, and one says that Fand G are in direct sum. One has thendim F G dim F dim G.Given a set I, the family (ei )i I , defined by 0, j i,i(e )j 1, j i,is a basis of K I , called the canonical basis. The dimension of K I is thereforeequal to the cardinality of I.In a vector space, every generating family contains at least one basis ofE. Similarly, given a free family, it is contained in at least one basis of E.This is the incomplete basis theorem.Let L be a field and K a subfield of L. If F is an L-vector space, then Fis also a K-vector space. As a matter of fact, L is itself a K-vector space,and one hasdimK F dimL F · dimK L.The most common example (the only one that we shall consider) is K IR,L CC, for which we havedimIR F 2 dimCC F.Conversely, if G is an IR-vector space, one builds its complexification GCCas follows:GCC G G,with the induced structure of an additive group. An element (x, y) of GCCis also denoted x iy. One defines multiplication by a complex number by(λ a ib, z x iy) λz : (ax by, ay bx).
41. Elementary TheoryOne verifies easily that GCC is a CC-vector space, withdimCC GCC dimIR G.Furthermore, G may be identified with an IR-linear subspace of GCC byx (x, 0).Under this identification, one has GCC G iG. In a more general setting,one may consider two fields K and L with K L, instead of IR and CC, butLismoredelicateandinvolvesthenotionoftensorthe construction of Gproduct. We shall not use it in this book.One says that a polynomial P L[X] splits over L if it can be writtenas a product of the formar (X ai )ni ,a, ai L,r IN , ni IN .i 1Such a factorization is unique, up to the order of the factors. A field L inwhich every nonconstant polynomial P L[X] admits a root, or equivalently in which every polynomial P L[X] splits, is algebraically closed. Ifthe field K contains the field K and if every polynomial P K[X] admitsa root in K , then the set of roots in K of polynomials in K[X] is an algebraically closed field that contains K, and it is the smallest such field. Onecalls K the algebraic closure of K. Every field K admits an algebraic closure, unique up to isomorphism, denoted by K. The fundamental theoremC. The algebraic closure of QQ, for instance,of algebra asserts that IR Cis the set of algebraic complex numbers, meaning that they are roots ofpolynomials P ZZ[X].1.1.2 MatricesLet K be a field. If n, m 1, a matrix of size n m with entries in K is amap from {1, . . . , n} {1, . . . , m} with values in K. One represents it asan array with n rows and m columns, an element of K (an entry) at eachpoint of intersection of a row an a column. In general, if M is the name ofthe matrix, one denotes by mij the element at the intersection of the ithrow and the jth column. One has therefore m11 . . . m1m . ,.M . mn1.mnmwhich one also writesM (mij )1 i n,1 j m .In particular circumstances (extraction of matrices or minors, for example)the rows and the columns can be numbered in a different way, using non-
1.1. Basics5consecutive numbers. One needs only two finite sets, one for indexing therows, the other for indexing the columns.The set of matrices of size n m with entries in K is denoted byMn m (K). It is an additive group, where M M denotes the matrix M whose entries are given by m ij mij m ij . One defines likewise multiplication by a scalar a K. The matrix M : aM is defined by m ij amij .One has the formulas a(bM ) (ab)M , a(M M ) (aM ) (aM ), and(a b)M (aM ) (bM ), which endow Mn m (K) with a K-vector spacestructure. The zero matrix is denoted by 0, or 0nm when one needs to avoidambiguity.When m n, one writes simply Mn (K) instead of Mn n (K), and 0ninstead of 0nn . The matrices of sizes n n are called square matrices. Onewrites In for the identity matrix, defined by 0, if i j,mij δij 1, if i j.In other words, In 10.···.00.0 ··· 0. . . 0 1The identity matrix is a special case of a permutation matrix, which aresquare matrices having exactly one nonzero entry in each row and eachcolumn, that entry being a 1. In other words, a permutation matrix Mreadsσ(j)mij δifor some permutation σ S n .A square matrix for which i j implies mij 0 is called a lowertriangular matrix. It is upper triangular if i j implies mij 0. It isstrictly upper triangular if i j implies mij 0. Last, it is diagonal if mijvanishes for every pair (i, j) such that i j. In particular, given n scalarsd1 , . . . , dn K, one denotes by diag(d1 , . . . , dn ) the diagonal matrix whosediag
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
22 Dense matrices over the Real Double Field using NumPy435 23 Dense matrices over GF(2) using the M4RI library437 24 Dense matrices over F 2 for 2 16 using the M4RIE library447 25 Dense matrices over Z/ Z for 223 using LinBox’s Modular double 455 26 Dense matrices over Z/ Z for 211 using LinBox’s Modular&l
Class XII – NCERT – Maths Chapter 3 - Matrices 3.Matrices . Exercise 3.1 . Question 1: In the matrix 2 5 19 7 5 35 2 12 2 3 1 5 17. A . As the given matrices are equal, their corresponding elements are also equal. Class XII – NCERT – Maths . Chapter 3 - Matrices . 3.Matrices . Comparing the corresponding elements, we get: .
Matrices and Determinants (i) Matrices Concept, notation, order, equality, types of matrices, zero and identity matrix, transpose of a matrix, symmetric and skew symmetric matrices. Operation on matrices: Addition and multiplication and multiplication with a . Further Reduced ISC Class 12 Maths Syllabus 2020-21
BLOSUM vs. PAM Equivalent PAM and BLOSUM matrices based on relative entropy PAM100 Blosum90 PAM120 Blosum80 PAM160 Blosum60 PAM200 Blosum52 PAM250 Blosum45 PAM matrices have lower expected scores for the BLOSUM matrices with the same entropy BLOSUM matrices “generally perform better” than PAM matrices
matrices with capital letters, like A, B, etc, although we will sometimes use lower case letters for one dimensional matrices (ie: 1 m or n 1 matrices). One dimensional matrices are often called vectors, as in row vector for a n 1 matrix or column vector for a 1 m matrix but we are going
In this section you learn to add and subtract matrices, to multiply a matrix by a number and to multiply two matrices. Matrices are classified by number of rows and the number of columns they have. The matrix above has 3 rows and 3 columns, it is a 3 3 matrix (read as ‘3 by 3’). A matrix with m rows and n columns is an m n matrix.
In this week’s lectures, we learn about matrices. Matrices are rectangular arrays of numbers or other mathematical objects and are fundamental to engineering mathematics. We will define matrices and how to add and multiply them, discuss some special matrices such as the identity and zero matrix,
Agile Software Development with Scrum An Iterative, Empirical and Incremental Framework for Completing Complex Projects (Slides by Prof. Dr. Matthias Hölzl, based on material from Dr. Philip Mayer with input from Dr. Andreas Schroeder and Dr. Annabelle Klarl) CHAOS Report 2009 Completion of projects: 32% success 44% challenged 24% impaired Some of the reasons for failure: Incomplete .
