xviiPrefacetothefirsteditionthat were the precursors of the book. They include Wayne Barrett, Leroy Beasley,BryanCain, David Carlson, Dipa Choudhury,Risana Chowdhury, Yoo Pyo Hong, DmitryKrass,DaleOlesky,StephenPierce,LeibaRodman,andPaulinevandenDriesscheR.A.H.C.R.J
xviii Preface to the first edition that were the precursors of the book. They include Wayne Barrett, Leroy Beasley, Bryan Cain, David Carlson, Dipa Choudhury, Risana Chowdhury, Yoo Pyo Hong, Dmitry Krass, Dale Olesky, Stephen Pierce, Leiba Rodman, and Pauline van den Driessche. R.A.H. C.R.J
CHAPTEROReview and Miscellanea0.0IntroductionIn this initial chapterwe summarize many useful concepts and facts, some of whichprovide a foundation for the material in the rest of the book. Some of this material isincluded in a typical elementary course in linear algebra, but we also include additionaluseful items,eventhoughtheydonotariseinoursubsequent exposition.Thereadermayuse this chapter as a reviewbeforebeginningthemainpartof thebook in Chapter l;subsequently,itcan serveasa convenientreferencefornotation and definitionsthatare encountered in later chapters.We assume that the reader is familiar with the basicconcepts of linear algebra and with mechanical aspects of matrix manipulations, suchas matrix multiplication and addition.0.1VectorspacesAfinitedimensional vectorspaceisthefundamental settingformatrixanalysis0.1.1 Scalar field.Underlying a vector space is its field, or set of scalars.For ourpurposes, that underlying field is typically the real numbers R or the complex numbersC (see Appendix A), but it could be the rational numbers, the integersmodulo aspecified prime number,or some other field. When the field is unspecified, we denote itby the symbol F.To qualify as a field, a set must beclosed under two binary operations:"addition"and"multiplication."Both operationsmust be associative and commutative,and eachmust have an identity element in the set; inverses must exist in the set forall elements under addition and for all elements except the additive identity undermultiplication; multiplication must be distributive over addition.0.1.2 Vector spaces. A vector space V over a field F is a set V of objects (calledvectors)that is closed under a binary operation ("addition")that is associative andcommutativeandhasanidentity(thezerovector,denotedbyO)andadditiveinverses1
CHAPTER 0 Review and Miscellanea 0.0 Introduction In this initial chapter we summarize many useful concepts and facts, some of which provide a foundation for the material in the rest of the book. Some of this material is included in a typical elementary course in linear algebra, but we also include additional useful items, even though they do not arise in our subsequent exposition. The reader may use this chapter as a review before beginning the main part of the book in Chapter 1; subsequently, it can serve as a convenient reference for notation and definitions that are encountered in later chapters. We assume that the reader is familiar with the basic concepts of linear algebra and with mechanical aspects of matrix manipulations, such as matrix multiplication and addition. 0.1 Vector spaces A finite dimensional vector space is the fundamental setting for matrix analysis. 0.1.1 Scalar field. Underlying a vector space is its field, or set of scalars. For our purposes, that underlying field is typically the real numbers R or the complex numbers C (see Appendix A), but it could be the rational numbers, the integers modulo a specified prime number, or some other field. When the field is unspecified, we denote it by the symbol F. To qualify as a field, a set must be closed under two binary operations: “addition” and “multiplication.” Both operations must be associative and commutative, and each must have an identity element in the set; inverses must exist in the set for all elements under addition and for all elements except the additive identity under multiplication; multiplication must be distributive over addition. 0.1.2 Vector spaces. A vector space V over a field F is a set V of objects (called vectors) that is closed under a binary operation (“addition”) that is associative and commutative and has an identity (the zero vector, denoted by 0) and additive inverses 1
2Reviewandmiscellaneain the set.The set is also closed under an operation of "scalar multiplication"ofthevectors by elements of the scalarfield F, with thefollowing properties for alla,b eFandall x,y eV:a(x +y) =ax +ay, (a+b)x =ax +bx,a(bx)=(ab)x,and ex = x for the multiplicative identity e e F.For a given field F and a given positive integer n,the set Fn of n-tuples with entriesfromFformsavectorspaceoverFunderentrywiseadditioninFn.Ourconventionis that elements of F" are always presented as column vectors; we often call themn-vectors.Thespecial casesR"and Carethebasic vector spaces of thisbook;Rn isa real vector space (that is, a vector space over the real field), while Cn is both a realvector spaceanda complexvector space (avector space overthecomplexfield).Theset of polynomials with real or with complex coefficients (of no more than a specifieddegreeorofarbitrarydegree)andthesetofreal-valuedorcomplex-valuedfunctionsonsubsetsofRorC(allwiththeusualnotionsof additionoffunctionsandmultiplicationof afunctionbya scalar)are also examples of real or complexvector spaces.0.1.3 Subspaces, span, and linear combinations. A subspace of a vector spaceV over a field F is a subset of V that is, by itself, a vector space over F using thesame operations of vectoraddition and scalar multiplicationas inV.A subsetofVis a subspace precisely when it is closed under these two operations.For example,[a,b, ojT : a,b e R) is a subspace of R’; see (0.2.5) for the transpose notation. Anintersection of subspaces is always a subspace; a union of subspaces need not be asubspace. The subsets (O) and V are always subspaces of V, so they are often calledtrivial subspaces;a subspace of Vis said to be nontrivial if it is differentfrom both[O) and V.A subspace of V is said to be a proper subspace if it is not equal to V. Wecall (O)thezerovector space.Sinceavectorspacealwayscontainsthezerovector,asubspacecannotbeempty.If S is a subset of a vector space V over a field F,span S is the intersection of allsubspaces of V that contain S. If s is nonempty, then span S= (aiu + ...+ axuk :U,...,vkS,a,..,akeF,andk =1,2,...J;ifSisempty,itiscontainedineverysubspace of V.The intersection of every subspace of V is the subspace(O),so thedefinition ensures that span S=(O). Notice that span S is always a subspace even if Sisnotasubspace;SissaidtospanVif spanS=V.A linear combination of vectors in a vector space V over a field F is any expressionof the form aiui + ..+ axus in which k is a positive integer, aj,..., ak e F, andUi,...,uk eV.Thus, the span of a nonempty subset S of V consists of all linearcombinations of finitely many vectors in S.A linear combination aiui +...+akukis trivial if a, =...=ak =O; otherwise,it is nontrivial.A linear combination is bydefinition a sum of finitelymany elements of a vector space.Let Siand S2be subspaces of a vector space overa fieldF.The sum of Srand S2isthe subspaceSi + S2= span(S, U S2) =(x+y :x eSi, y e S2)If S,n S2=(O),we saythat the sum of S,and S2 is a direct sum and write it asS,@S2;everyzES@S2canbewrittenasz=x+ywithxeS,andyeS,inoneand onlyone way
2 Review and miscellanea in the set. The set is also closed under an operation of “scalar multiplication” of the vectors by elements of the scalar field F, with the following properties for all a, b ∈ F and all x, y ∈ V: a(x + y) = ax + ay, (a + b)x = ax + bx, a(bx) = (ab)x, and ex = x for the multiplicative identity e ∈ F. For a given field F and a given positive integer n, the set Fn of n-tuples with entries from F forms a vector space over F under entrywise addition in Fn. Our convention is that elements of Fn are always presented as column vectors; we often call them n-vectors. The special cases Rn and Cn are the basic vector spaces of this book; Rn is a real vector space (that is, a vector space over the real field), while Cn is both a real vector space and a complex vector space (a vector space over the complex field). The set of polynomials with real or with complex coefficients (of no more than a specified degree or of arbitrary degree) and the set of real-valued or complex-valued functions on subsets of R or C (all with the usual notions of addition of functions and multiplication of a function by a scalar) are also examples of real or complex vector spaces. 0.1.3 Subspaces, span, and linear combinations. A subspace of a vector space V over a field F is a subset of V that is, by itself, a vector space over F using the same operations of vector addition and scalar multiplication as in V. A subset of V is a subspace precisely when it is closed under these two operations. For example, {[a, b, 0]T : a, b ∈ R} is a subspace of R3; see (0.2.5) for the transpose notation. An intersection of subspaces is always a subspace; a union of subspaces need not be a subspace. The subsets {0} and V are always subspaces of V, so they are often called trivial subspaces; a subspace of V is said to be nontrivial if it is different from both {0} and V. A subspace of V is said to be a proper subspace if it is not equal to V. We call {0} the zero vector space. Since a vector space always contains the zero vector, a subspace cannot be empty. If S is a subset of a vector space V over a field F, span S is the intersection of all subspaces of V that contain S. If S is nonempty, then span S = {a1v1 +···+ akvk : v1,.,vk ∈ S, a1,., ak ∈ F, and k = 1, 2,.}; if S is empty, it is contained in every subspace of V. The intersection of every subspace of V is the subspace {0}, so the definition ensures that span S = {0}. Notice that span S is always a subspace even if S is not a subspace; S is said to span V if span S = V. A linear combination of vectors in a vector space V over a field F is any expression of the form a1v1 +···+ akvk in which k is a positive integer, a1,., ak ∈ F, and v1,.,vk ∈ V. Thus, the span of a nonempty subset S of V consists of all linear combinations of finitely many vectors in S. A linear combination a1v1 +···+ akvk is trivial if a1 =···= ak = 0; otherwise, it is nontrivial. A linear combination is by definition a sum of finitely many elements of a vector space. Let S1 and S2 be subspaces of a vector space over a field F. The sum of S1 and S2 is the subspace S1 + S2 = span {S1 ∪ S2} = {x + y : x ∈ S1, y ∈ S2} If S1 ∩ S2 = {0}, we say that the sum of S1 and S2 is a direct sum and write it as S1 ⊕ S2; every z ∈ S1 ⊕ S2 can be written as z = x + y with x ∈ S1 and y ∈ S2 in one and only one way
30.1Vectorspaces0.1.4 Linear dependence and linear independence.We say that a finite list ofvectors vi,.., uk in a vector space V over a field F is linearly dependent if andonly if there are scalars ai,..., ak e F, not all zero, such that aixi +... + akxk = 0.Thus, a list of vectors ui, .., ux is linearly dependent if and only if some nontriviallinear combination of vi, .,vkis the zero vector. It is often convenient to say that"vi,...,Uare linearlydependent"instead ofthemore formal statement"the listofvec-tors ut,..,Vx islinearlydependent."Alistofvectors vi....,vx is saidtohavelengthk.A list of two or more vectors is linearly dependent if one of the vectors is a linear com-bination of some of the others; in particular, a list of two or morevectors in which twoof the vectors in the list are identical is linearly dependent.Two vectors are linearlydependent if and only if one of the vectors is a scalar multiple of the other.A listconsisting only of the zero vector is linearly dependent since a0 = 0 for a =1.A finite list of vectors Ui,...,Uk in a vector space V over a field F is linearlyindependent if it is not linearly dependent. Again, it can be convenient to say that"vi,.., Uk are linearly independent"instead of "the list of vectors vi,..., vk islinearly independent."Sometimes one encounters natural lists ofvectors that have infinitelymanyelements,forexample,themonomials l,t,t,t3....in thevector space ofall polynomials withreal coefficientsorthecomplexexponentials1,et,e2it,e3it,....inthevectorspaceofcomplex-valuedcontinuousfunctionsthatareperiodicon[O,2].If certain vectors in a list (finite or infinite)are deleted, the resulting list is a sublistof the original list. An infinite list of vectors is said to be linearly dependent if somefinite sublist is linearly dependent; it is said to be linearly independent if every finitesublist is linearly independent. Any sublist of a linearly independent list of vectors islinearly independent; any list of vectors that has a linearly dependent sublist is linearlydependent. Since a list consisting only ofthe zero vector is linearly dependent, any listof vectors that contains the zerovector is linearly dependent.A list of vectors can belinearly dependent, while any proper sublist is linearly independent; see (1.4.P12). Anempty list of vectors is not linearly dependent, so it is linearly independent.Thecardinalityof a finite set is thenumber of its (necessarilydistinct)elementsFor a given list of vectors vi, .., vs in a vector space V, the cardinality of the set(vi,..., vx) is less than k if and only if two or more vectors in the list are identical;if v, ..., vk are linearly independent, then the cardinality of the set (vi,..., x) is k.Thespan of a list of vectors (finite or not)is the span of the set of elements ofthe list:a list of vectors spans V if is the span of the list.A set S of vectors is said to be linearly independent if every finite list of distinctvectors in S is linearlyindependent;Sis said tobe linearlydependent if somefinitelist of distinct vectors in S is linearly dependent.0.1.5 Basis.A linearly independent list of vectors in a vector space V whose spanis V is a basis for V.Each element of V can be represented as a linear combinationof vectors in a basis in one and only one way;this is no longer true if any elementwhatsoever is appended to or deleted fromthebasis.A linearly independent list ofvectors in V is a basis of V if and only if no list of vectors that properly contains it islinearly independent. A list of vectors that spans V is a basis for V if and only if noproper sublist of it spans V.The empty list is a basis for the zero vector space
0.1 Vector spaces 3 0.1.4 Linear dependence and linear independence. We say that a finite list of vectors v1,.,vk in a vector space V over a field F is linearly dependent if and only if there are scalars a1,., ak ∈ F, not all zero, such that a1x1 +···+ ak xk = 0. Thus, a list of vectors v1,.,vk is linearly dependent if and only if some nontrivial linear combination of v1,.,vk is the zero vector. It is often convenient to say that “v1,.,vk are linearly dependent” instead of the more formal statement “the list of vectors v1,.,vk is linearly dependent.” A list of vectors v1,.,vk is said to have length k. A list of two or more vectors is linearly dependent if one of the vectors is a linear combination of some of the others; in particular, a list of two or more vectors in which two of the vectors in the list are identical is linearly dependent. Two vectors are linearly dependent if and only if one of the vectors is a scalar multiple of the other. A list consisting only of the zero vector is linearly dependent since a10 = 0 for a1 = 1. A finite list of vectors v1,.,vk in a vector space V over a field F is linearly independent if it is not linearly dependent. Again, it can be convenient to say that “v1,.,vk are linearly independent” instead of “the list of vectors v1,.,vk is linearly independent.” Sometimes one encounters natural lists of vectors that have infinitely many elements, for example, the monomials 1, t, t 2, t 3,. in the vector space of all polynomials with real coefficients or the complex exponentials 1, eit, e2it, e3it,. in the vector space of complex-valued continuous functions that are periodic on [0, 2π]. If certain vectors in a list (finite or infinite) are deleted, the resulting list is a sublist of the original list. An infinite list of vectors is said to be linearly dependent if some finite sublist is linearly dependent; it is said to be linearly independent if every finite sublist is linearly independent. Any sublist of a linearly independent list of vectors is linearly independent; any list of vectors that has a linearly dependent sublist is linearly dependent. Since a list consisting only of the zero vector is linearly dependent, any list of vectors that contains the zero vector is linearly dependent. A list of vectors can be linearly dependent, while any proper sublist is linearly independent; see (1.4.P12). An empty list of vectors is not linearly dependent, so it is linearly independent. The cardinality of a finite set is the number of its (necessarily distinct) elements. For a given list of vectors v1,.,vk in a vector space V, the cardinality of the set {v1,.,vk } is less than k if and only if two or more vectors in the list are identical; if v1,.,vk are linearly independent, then the cardinality of the set {v1,.,vk } is k. The span of a list of vectors (finite or not) is the span of the set of elements of the list; a list of vectors spans V if V is the span of the list. A set S of vectors is said to be linearly independent if every finite list of distinct vectors in S is linearly independent; S is said to be linearly dependent if some finite list of distinct vectors in S is linearly dependent. 0.1.5 Basis. A linearly independent list of vectors in a vector space V whose span is V is a basis for V. Each element of V can be represented as a linear combination of vectors in a basis in one and only one way; this is no longer true if any element whatsoever is appended to or deleted from the basis. A linearly independent list of vectors in V is a basis of V if and only if no list of vectors that properly contains it is linearly independent. A list of vectors that spans V is a basis for V if and only if no proper sublist of it spans V. The empty list is a basis for the zero vector space
4Review and miscellanea0.1.6Extension to a basis.Any linearly independent list of vectors in a vector spaceVmaybe extended,perhaps in more thanone way,toa basis ofV.Avector space canhaveabasis thatis notfinite;for example,the infinitelistofmonomials I,t,t?,3isabasisforthereal vectorspaceof allpolynomialswithreal coefficients;eachpolynomial is a unique linear combination of (finitely many)elements in the basis.0.1.7 Dimension.If there is a positive integer n such that a basis of the vector spaceV contains exactly n vectors, then every basis of V consists of exactly n vectors; thiscommon cardinalityof bases is the dimension of the vector spaceVand isdenotedbydimV.In this event, V is finite-dimensional; otherwise V is infinite-dimensional.In theinfinite-dimensional case,there is a one-to-one correspondencebetween theelementsof any two bases. The real vector space R" has dimension n. The vector space Cn hasdimension n over the field C but dimension 2n over the field R. The basis ei,,enof F" in which each n-vector e; has a I as its ith entry and Os elsewhere is called thestandard basis.It is convenient to say"v is an n-dimensional vector space"as a shorthand for"V is a finite-dimensional vector space whose dimension is n."Any subspace of ann-dimensional vector spaceis finite-dimensional; its dimension is strictly less than nif it is a proper subspace.LetVbea finite-dimensional vector space and letS and Sbetwo given subspacesof V.The subspace intersectionlemmais(0.1.7.1)dim(S, n S2) + dim(Si + S2) = dim Si + dim S2Rewriting this identityasdim(SinS2)= dimSi +dim S2- dim(Si + S2)≥dimS+dimS2-dimV(0.1.7.2)reveals the useful fact that if = dim S + dim S2- dim V ≥ 1, then the subspaceS,n S,has dimension at least 8, and hence it contains 8 linearly independent vectors,namely,anyelements ofabasisof SnS2.In particular,S,n S2 contains a nonzerovector.An induction argument shows that if Si,..., S are subspaces of V, and if8=dimSi+...+dimS-(k-1)dimV≥1,then(0.1.7.3)dim(Sin...nS)≥8and hence S, ...n S contains 8 linearly independent vectors; in particular, it con-tains a nonzero vector.0.1.8 Isomorphism. If U and V are vector spaces over the same scalar field F, andif f :U-→V is an invertible function such that f(ax+by)=af(r)+bf(y)for allx,y eU and all a,b eF, then f is said to be an isomorphism and U and V aresaidtobeisomorphic(same structure").Twofinite-dimensional vector spaces overthe same field are isomorphic if and only if they have the same dimension; thus, anyn-dimensional vector space overFis isomorphic toF".Anyn-dimensional real vectorspace is,therefore,isomorphic to R",and any n-dimensional complex vector space isisomorphic to C".Specifically,ifV is an n-dimensional vector space overa fieldF
4 Review and miscellanea 0.1.6 Extension to a basis. Any linearly independent list of vectors in a vector space V may be extended, perhaps in more than one way, to a basis of V. A vector space can have a basis that is not finite; for example, the infinite list of monomials 1, t, t 2, t 3,. is a basis for the real vector space of all polynomials with real coefficients; each polynomial is a unique linear combination of (finitely many) elements in the basis. 0.1.7 Dimension. If there is a positive integer n such that a basis of the vector space V contains exactly n vectors, then every basis of V consists of exactly n vectors; this common cardinality of bases is the dimension of the vector space V and is denoted by dimV. In this event, V is finite-dimensional; otherwise V is infinite-dimensional. In the infinite-dimensional case, there is a one-to-one correspondence between the elements of any two bases. The real vector space Rn has dimension n. The vector space Cn has dimension n over the field C but dimension 2n over the field R. The basis e1,., en of Fn in which each n-vector ei has a 1 as its ith entry and 0s elsewhere is called the standard basis. It is convenient to say “V is an n-dimensional vector space” as a shorthand for “V is a finite-dimensional vector space whose dimension is n.” Any subspace of an n-dimensional vector space is finite-dimensional; its dimension is strictly less than n if it is a proper subspace. Let V be a finite-dimensional vector space and let S1 and S2 be two given subspaces of V. The subspace intersection lemma is dim (S1 ∩ S2) + dim (S1 + S2) = dim S1 + dim S2 (0.1.7.1) Rewriting this identity as dim (S1 ∩ S2) = dim S1 + dim S2 − dim (S1 + S2) ≥ dim S1 + dim S2 − dim V (0.1.7.2) reveals the useful fact that if δ = dim S1 + dim S2 − dim V ≥ 1, then the subspace S1 ∩ S2 has dimension at least δ, and hence it contains δ linearly independent vectors, namely, any δ elements of a basis of S1 ∩ S2. In particular, S1 ∩ S2 contains a nonzero vector. An induction argument shows that if S1,., Sk are subspaces of V, and if δ = dim S1 +···+ dim Sk − (k − 1) dim V ≥ 1, then dim (S1 ∩···∩ Sk ) ≥ δ (0.1.7.3) and hence S1 ∩···∩ Sk contains δ linearly independent vectors; in particular, it contains a nonzero vector. 0.1.8 Isomorphism. If U and V are vector spaces over the same scalar field F, and if f : U → V is an invertible function such that f (ax + by) = a f (x) + bf (y) for all x, y ∈ U and all a, b ∈ F, then f is said to be an isomorphism and U and V are said to be isomorphic (“same structure”). Two finite-dimensional vector spaces over the same field are isomorphic if and only if they have the same dimension; thus, any n-dimensional vector space over F is isomorphic to Fn. Any n-dimensional real vector space is, therefore, isomorphic to Rn, and any n-dimensional complex vector space is isomorphic to Cn. Specifically, if V is an n-dimensional vector space over a field F