Chapter 3 Linear Maps So far our attention has focused on vector spaces. No one gets excited about vector spaces. The interesting part of linear algebra is the subject to which we now turn—linear maps. We will frequently use the powerful fundamental theorem of linear maps, which states that the dimension of the domain of a linear map equals the dimension of the subspace that gets sent to 0 plus the dimension of the range. This will imply the striking result that a linear map from a finite-dimensional vector space to itself is one-to-one if and only if its range is the whole space. A major concept that we will introduce in this chapter is the matrix associated with a linear map and with a basis of the domain space and a basis of the target space. This correspondence between linear maps and matrices provides much insight into key aspects of linear algebra. This chapter concludes by introducing product, quotient, and dual spaces. In this chapter we will need additional vector spaces, which we call 𝑈 and 𝑊 , in addition to 𝑉 . Thus our standing assumptions are now as follows. standing assumptions for this chapter - • 𝐅 denotes 𝐑 or 𝐂 . - • 𝑈 , 𝑉 , and 𝑊 denote vector spaces over 𝐅 . Stefan Schäfer CC BY-SA The twelfth-century Dankwarderode Castle in Brunswick ( Braunschweig ) , where Carl Friedrich Gauss ( 1777–1855 ) was born and grew up. In 1809 Gauss published a method for solving systems of linear equations. This method, now called Gaussian elimination, was used in a Chinese book written over 1600 years earlier. Section 3A Vector Space of Linear Maps Definition and Examples of Linear Maps Now we are ready for one of the key definitions in linear algebra. 3.1 definition: linear map A linear map from 𝑉 to 𝑊 is a function 𝑇 ∶ 𝑉 → 𝑊 with the following properties. - additivity 𝑇(𝑢 + 𝑣) = 𝑇𝑢 + 𝑇𝑣 for all 𝑢 , 𝑣 ∈ 𝑉 . - homogeneity 𝑇(𝜆𝑣) = 𝜆(𝑇𝑣) for all 𝜆 ∈ 𝐅 and all 𝑣 ∈ 𝑉 . - Some mathematicians use the phrase linear transformation , which means the same as linear map. - Note that for linear maps we often use the notation 𝑇𝑣 as well as the usual function notation 𝑇(𝑣) . 3.2 notation: ℒ (𝑉 , 𝑊) , ℒ (𝑉) - • The set of linear maps from 𝑉 to 𝑊 is denoted by ℒ (𝑉 , 𝑊) . - • The set of linear maps from 𝑉 to 𝑉 is denoted by ℒ (𝑉) . - In other words, ℒ (𝑉) = ℒ (𝑉 , 𝑉) . - Let’s look at some examples of linear maps. Make sure you verify that each of the functions defined in the next example is indeed a linear map: 3.3 example: linear maps - **zero** In addition to its other uses, we let the symbol 0 denote the linear map that takes every element of some vector space to the additive identity of another (or possibly the same) vector space. To be specific, 0 ∈ ℒ (𝑉 , 𝑊) is defined by 0𝑣 = 0. The 0 on the left side of the equation above is a function from 𝑉 to 𝑊 , whereas the 0 on the right side is the additive identity in 𝑊 . As usual, the context should allow you to distinguish between the many uses of the symbol 0 . - **identity operator** The identity operator , denoted by 𝐼 , is the linear map on some vector space that takes each element to itself. To be specific, 𝐼 ∈ ℒ (𝑉) is defined by 𝐼𝑣 = 𝑣. - **differentiation** - Define 𝐷 ∈ ℒ ( 𝒫 (𝐑)) by 𝐷𝑝 = 𝑝 ′ . The assertion that this function is a linear map is another way of stating a basic result about differentiation: ( 𝑓 + 𝑔) ′ = 𝑓 ′ + 𝑔 ′ and (𝜆 𝑓 ) ′ = 𝜆 𝑓 ′ whenever 𝑓 , 𝑔 are differentiable and 𝜆 is a constant. - **integration** - Define 𝑇 ∈ ℒ ( 𝒫 (𝐑) , 𝐑) by 𝑇𝑝 = ∫ 1 0 𝑝. The assertion that this function is linear is another way of stating a basic result about integration: the integral of the sum of two functions equals the sum of the integrals, and the integral of a constant times a function equals the constant times the integral of the function. - **multiplication by** $𝑥^2$ - Define a linear map 𝑇 ∈ ℒ ( 𝒫 (𝐑)) by (𝑇𝑝)(𝑥) = $𝑥^2$ 𝑝(𝑥) for each 𝑥 ∈ 𝐑 . - **backward shift** - Recall that 𝐅 ∞ denotes the vector space of all sequences of elements of 𝐅 . - Define a linear map 𝑇 ∈ ℒ ($𝐅^∞$ ) by 𝑇($𝑥_1$ , $𝑥_2$ , $𝑥_3$ , … ) = ($𝑥_2$ , $𝑥_3$ , … ). - from 𝐑 3 to 𝐑 2 - Define a linear map 𝑇 ∈ ℒ (𝐑 3 , 𝐑 2 ) by 𝑇(𝑥 , 𝑦 , 𝑧) = (2𝑥 − 𝑦 + 3𝑧 , 7𝑥 + 5𝑦 − 6𝑧). - **from $𝐅^𝑛$ to $𝐅^𝑚$** To generalize the previous example, let 𝑚 and 𝑛 be positive integers, let 𝐴 𝑗 , 𝑘 ∈ 𝐅 for each 𝑗 = 1 , … , 𝑚 and each 𝑘 = 1 , … , 𝑛 , and define a linear map 𝑇 ∈ ℒ (𝐅 𝑛 , 𝐅 𝑚 ) by 𝑇(𝑥 1 , … , 𝑥 𝑛 ) = ($𝐴_{1,1}$ $𝑥_1$ + ⋯ + $𝐴_1,n$ , $𝑥_𝑛$, … , 𝐴 𝑚 , 1 𝑥 1 + ⋯ + 𝐴 𝑚 , 𝑛 𝑥 𝑛 ). Actually every linear map from 𝐅 𝑛 to 𝐅 𝑚 is of this form. - **composition** - Fix a polynomial 𝑞 ∈ 𝒫 (𝐑) . Define a linear map 𝑇 ∈ ℒ ( 𝒫 (𝐑)) by (𝑇𝑝)(𝑥) = 𝑝(𝑞(𝑥)). - --- The **existence** part of the next result means that we can find a linear map that takes on whatever values we wish on the vectors in a basis. The **uniqueness** part of the next result means that a linear map is completely determined by its values on a basis. 3.4 linear map lemma Suppose 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑛 ∈ 𝑊 . Then there exists a unique linear map 𝑇 ∶ 𝑉 → 𝑊 such that $𝑇𝑣_𝑘$ = $𝑤_𝑘$ for each 𝑘 = 1 , … , 𝑛 . Proof First we show the existence of a linear map 𝑇 with the desired property. Define 𝑇 ∶ 𝑉 → 𝑊 by 𝑇(𝑐 1 𝑣 1 + ⋯ + 𝑐 𝑛 𝑣 𝑛 ) = 𝑐 1 𝑤 1 + ⋯ + 𝑐 𝑛 𝑤 𝑛 , where 𝑐 1 , … , 𝑐 𝑛 are arbitrary elements of 𝐅 . The list 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 . Thus the equation above does indeed define a function 𝑇 from 𝑉 to 𝑊 (because each element of 𝑉 can be uniquely written in the form 𝑐 1 𝑣 1 + ⋯ + 𝑐 𝑛 𝑣 𝑛 ). For each 𝑘 , taking 𝑐 𝑘 = 1 and the other 𝑐 ’s equal to 0 in the equation above shows that 𝑇𝑣 𝑘 = 𝑤 𝑘 . If 𝑢 , 𝑣 ∈ 𝑉 with 𝑢 = 𝑎 1 𝑣 1 + ⋯ + 𝑎 𝑛 𝑣 𝑛 and 𝑣 = 𝑐 1 𝑣 1 + ⋯ + 𝑐 𝑛 𝑣 𝑛 , then 𝑇(𝑢 + 𝑣) = 𝑇((𝑎 1 + 𝑐 1 )𝑣 1 + ⋯ + (𝑎 𝑛 + 𝑐 𝑛 )𝑣 𝑛 ) = (𝑎 1 + 𝑐 1 )𝑤 1 + ⋯ + (𝑎 𝑛 + 𝑐 𝑛 )𝑤 𝑛 = (𝑎 1 𝑤 1 + ⋯ + 𝑎 𝑛 𝑤 𝑛 ) + (𝑐 1 𝑤 1 + ⋯ + 𝑐 𝑛 𝑤 𝑛 ) = 𝑇𝑢 + 𝑇𝑣. Similarly, if 𝜆 ∈ 𝐅 and 𝑣 = 𝑐 1 𝑣 1 + ⋯ + 𝑐 𝑛 𝑣 𝑛 , then 𝑇(𝜆𝑣) = 𝑇(𝜆𝑐 1 𝑣 1 + ⋯ + 𝜆𝑐 𝑛 𝑣 𝑛 ) = 𝜆𝑐 1 𝑤 1 + ⋯ + 𝜆𝑐 𝑛 𝑤 𝑛 = 𝜆(𝑐 1 𝑤 1 + ⋯ + 𝑐 𝑛 𝑤 𝑛 ) = 𝜆𝑇𝑣. Thus 𝑇 is a linear map from 𝑉 to 𝑊 . To prove uniqueness, now suppose that 𝑇 ∈ ℒ (𝑉 , 𝑊) and that 𝑇𝑣 𝑘 = 𝑤 𝑘 for each 𝑘 = 1 , … , 𝑛 . Let 𝑐 1 , … , 𝑐 𝑛 ∈ 𝐅 . Then the homogeneity of 𝑇 implies that 𝑇(𝑐 𝑘 𝑣 𝑘 ) = 𝑐 𝑘 𝑤 𝑘 for each 𝑘 = 1 , … , 𝑛 . The additivity of 𝑇 now implies that 𝑇(𝑐 1 𝑣 1 + ⋯ + 𝑐 𝑛 𝑣 𝑛 ) = 𝑐 1 𝑤 1 + ⋯ + 𝑐 𝑛 𝑤 𝑛 . Thus 𝑇 is uniquely determined on span (𝑣 1 , … , 𝑣 𝑛 ) by the equation above. Because 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 , this implies that 𝑇 is uniquely determined on 𝑉 , as desired. Algebraic Operations on ℒ (𝑉 , 𝑊) We begin by defining addition and scalar multiplication on ℒ (𝑉 , 𝑊) . 3.5 definition: addition and scalar multiplication on ℒ (𝑉 , 𝑊) Suppose 𝑆 , 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝜆 ∈ 𝐅 . The sum 𝑆 + 𝑇 and the product 𝜆𝑇 are the linear maps from 𝑉 to 𝑊 defined by (𝑆 + 𝑇)(𝑣) = 𝑆𝑣 + 𝑇𝑣 and (𝜆𝑇)(𝑣) = 𝜆(𝑇𝑣) for all 𝑣 ∈ 𝑉 . Linear maps are pervasive throughout mathematics. However, they are not as ubiquitous as imagined by people who seem to think cos is a linear map from 𝐑 to 𝐑 when they incorrectly write that cos (𝑥 + 𝑦) equals cos 𝑥 + cos 𝑦 and that cos 2𝑥 equals 2 cos 𝑥 . You should verify that 𝑆 + 𝑇 and 𝜆𝑇 as defined above are indeed linear maps. In other words, if 𝑆 , 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝜆 ∈ 𝐅 , then 𝑆 + 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝜆𝑇 ∈ ℒ (𝑉 , 𝑊) . Because we took the trouble to define addition and scalar multiplication on ℒ (𝑉 , 𝑊) , the next result should not be a surprise. 3.6 ℒ (𝑉 , 𝑊) is a vector space With the operations of addition and scalar multiplication as defined above, ℒ (𝑉 , 𝑊) is a vector space. The routine proof of the result above is left to the reader. Note that the additive identity of ℒ (𝑉 , 𝑊) is the zero linear map defined in Example 3.3. Usually it makes no sense to multiply together two elements of a vector space, but for some pairs of linear maps a useful product exists, as in the next definition. 3.7 definition: product of linear maps If 𝑇 ∈ ℒ (𝑈 , 𝑉) and 𝑆 ∈ ℒ (𝑉 , 𝑊) , then the product 𝑆𝑇 ∈ ℒ (𝑈 , 𝑊) is defined by (𝑆𝑇)(𝑢) = 𝑆(𝑇𝑢) for all 𝑢 ∈ 𝑈 . Thus 𝑆𝑇 is just the usual composition 𝑆 ∘ 𝑇 of two functions, but when both functions are linear, we usually write 𝑆𝑇 instead of 𝑆 ∘ 𝑇 . The product notation 𝑆𝑇 helps make the distributive properties (see next result) seem natural. Note that 𝑆𝑇 is defined only when 𝑇 maps into the domain of 𝑆 . You should verify that 𝑆𝑇 is indeed a linear map from 𝑈 to 𝑊 whenever 𝑇 ∈ ℒ (𝑈 , 𝑉) and 𝑆 ∈ ℒ (𝑉 , 𝑊) . 3.8 algebraic properties of products of linear maps - associativity - (𝑇 1 𝑇 2 )𝑇 3 = 𝑇 1 (𝑇 2 𝑇 3 ) whenever 𝑇 1 , 𝑇 2 , and 𝑇 3 are linear maps such that the products make sense (meaning 𝑇 3 maps into the domain of 𝑇 2 , and 𝑇 2 maps into the domain of 𝑇 1 ). - identity - 𝑇𝐼 = 𝐼𝑇 = 𝑇 whenever 𝑇 ∈ ℒ (𝑉 , 𝑊) ; here the first 𝐼 is the identity operator on 𝑉 , and the second 𝐼 is the identity operator on 𝑊 . - distributive properties - (𝑆 1 + 𝑆 2 )𝑇 = 𝑆 1 𝑇 + 𝑆 2 𝑇 and 𝑆(𝑇 1 + 𝑇 2 ) = 𝑆𝑇 1 + 𝑆𝑇 2 whenever 𝑇 , 𝑇 1 , 𝑇 2 ∈ ℒ (𝑈 , 𝑉) and 𝑆 , 𝑆 1 , 𝑆 2 ∈ ℒ (𝑉 , 𝑊) . The routine proof of the result above is left to the reader. Multiplication of linear maps is not commutative. In other words, it is not necessarily true that 𝑆𝑇 = 𝑇𝑆 , even if both sides of the equation make sense. 3.9 example: two noncommuting linear maps from 𝒫 (𝐑) to 𝒫 (𝐑) Suppose 𝐷 ∈ ℒ ( 𝒫 (𝐑)) is the differentiation map defined in Example 3.3 and 𝑇 ∈ ℒ ( 𝒫 (𝐑)) is the multiplication by 𝑥 2 map defined earlier in this section. Then ((𝑇𝐷)𝑝)(𝑥) = 𝑥 2 𝑝 ′ (𝑥) but ((𝐷𝑇)𝑝)(𝑥) = 𝑥 2 𝑝 ′ (𝑥) + 2𝑥𝑝(𝑥). Thus 𝑇𝐷 ≠ 𝐷𝑇 —differentiating and then multiplying by 𝑥 2 is not the same as multiplying by 𝑥 2 and then differentiating. 3.10 linear maps take 0 to 0 Suppose 𝑇 is a linear map from 𝑉 to 𝑊 . Then 𝑇(0) = 0 . Proof By additivity, we have 𝑇(0) = 𝑇(0 + 0) = 𝑇(0) + 𝑇(0). Add the additive inverse of 𝑇(0) to each side of the equation above to conclude that 𝑇(0) = 0 . Suppose 𝑚 , 𝑏 ∈ 𝐑 . The function 𝑓 ∶ 𝐑 → 𝐑 defined by 𝑓 (𝑥) = 𝑚𝑥 + 𝑏 is a linear map if and only if 𝑏 = 0 (use 3.10). Thus the linear functions of high school algebra are not the same as linear maps in the context of linear algebra. --- Exercises 3A 1 Suppose 𝑏 , 𝑐 ∈ 𝐑 . Define 𝑇 ∶ 𝐑 3 → 𝐑 2 by 𝑇(𝑥 , 𝑦 , 𝑧) = (2𝑥 − 4𝑦 + 3𝑧 + 𝑏 , 6𝑥 + 𝑐𝑥𝑦𝑧). Show that 𝑇 is linear if and only if 𝑏 = 𝑐 = 0 . 2 Suppose 𝑏 , 𝑐 ∈ 𝐑 . Define 𝑇 ∶ 𝒫 (𝐑) → 𝐑 2 by 𝑇𝑝 = (3𝑝(4) + 5𝑝 ′ (6) + 𝑏𝑝(1)𝑝(2) , ∫ 2 −1 𝑥 3 𝑝(𝑥) 𝑑𝑥 + 𝑐 sin 𝑝(0)). Show that 𝑇 is linear if and only if 𝑏 = 𝑐 = 0 . 3 Suppose that 𝑇 ∈ ℒ (𝐅 𝑛 , 𝐅 𝑚 ) . Show that there exist scalars 𝐴 𝑗 , 𝑘 ∈ 𝐅 for 𝑗 = 1 , … , 𝑚 and 𝑘 = 1 , … , 𝑛 such that 𝑇(𝑥 1 , … , 𝑥 𝑛 ) = (𝐴 1 , 1 𝑥 1 + ⋯ + 𝐴 1 , 𝑛 𝑥 𝑛 , … , 𝐴 𝑚 , 1 𝑥 1 + ⋯ + 𝐴 𝑚 , 𝑛 𝑥 𝑛 ) for every (𝑥 1 , … , 𝑥 𝑛 ) ∈ 𝐅 𝑛 . This exercise shows that the linear map 𝑇 has the form promised in the second to last item of Example 3.3. 4 Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝑣 1 , … , 𝑣 𝑚 is a list of vectors in 𝑉 such that 𝑇𝑣 1 , … , 𝑇𝑣 𝑚 is a linearly independent list in 𝑊 . Prove that 𝑣 1 , … , 𝑣 𝑚 is linearly independent. 5 Prove that ℒ (𝑉 , 𝑊) is a vector space, as was asserted in 3.6. 6 Prove that multiplication of linear maps has the associative, identity, and distributive properties asserted in 3.8. 7 Show that every linear map from a one-dimensional vector space to itself is multiplication by some scalar. More precisely, prove that if dim 𝑉 = 1 and 𝑇 ∈ ℒ (𝑉) , then there exists 𝜆 ∈ 𝐅 such that 𝑇𝑣 = 𝜆𝑣 for all 𝑣 ∈ 𝑉 . 8 Give an example of a function 𝜑 ∶ 𝐑 2 → 𝐑 such that 𝜑(𝑎𝑣) = 𝑎𝜑(𝑣) for all 𝑎 ∈ 𝐑 and all 𝑣 ∈ 𝐑 2 but 𝜑 is not linear. This exercise and the next exercise show that neither homogeneity nor additivity alone is enough to imply that a function is a linear map. 9 Give an example of a function 𝜑 ∶ 𝐂 → 𝐂 such that 𝜑(𝑤 + 𝑧) = 𝜑(𝑤) + 𝜑(𝑧) for all 𝑤 , 𝑧 ∈ 𝐂 but 𝜑 is not linear. (Here 𝐂 is thought of as a complex vector space.) There also exists a function 𝜑 ∶ 𝐑 → 𝐑 such that 𝜑 satisfies the additivity condition above but 𝜑 is not linear. However, showing the existence of such a function involves considerably more advanced tools. 10 Prove or give a counterexample: If 𝑞 ∈ 𝒫 (𝐑) and 𝑇 ∶ 𝒫 (𝐑) → 𝒫 (𝐑) is defined by 𝑇𝑝 = 𝑞 ∘ 𝑝 , then 𝑇 is a linear map. The function 𝑇 defined here differs from the function 𝑇 defined in the last bullet point of 3.3 by the order of the functions in the compositions. 11 Suppose 𝑉 is finite-dimensional and 𝑇 ∈ ℒ (𝑉) . Prove that 𝑇 is a scalar multiple of the identity if and only if 𝑆𝑇 = 𝑇𝑆 for every 𝑆 ∈ ℒ (𝑉) . 12 Suppose 𝑈 is a subspace of 𝑉 with 𝑈 ≠ 𝑉 . Suppose 𝑆 ∈ ℒ (𝑈 , 𝑊) and 𝑆 ≠ 0 (which means that 𝑆𝑢 ≠ 0 for some 𝑢 ∈ 𝑈 ). Define 𝑇 ∶ 𝑉 → 𝑊 by 𝑇𝑣 = ⎧{ ⎨{⎩ 𝑆𝑣 if 𝑣 ∈ 𝑈 , 0 if 𝑣 ∈ 𝑉 and 𝑣 ∉ 𝑈. Prove that 𝑇 is not a linear map on 𝑉 . 13 Suppose 𝑉 is finite-dimensional. Prove that every linear map on a subspace of 𝑉 can be extended to a linear map on 𝑉 . In other words, show that if 𝑈 is a subspace of 𝑉 and 𝑆 ∈ ℒ (𝑈 , 𝑊) , then there exists 𝑇 ∈ ℒ (𝑉 , 𝑊) such that 𝑇𝑢 = 𝑆𝑢 for all 𝑢 ∈ 𝑈 . The result in this exercise is used in the proof of 3.125. 14 Suppose 𝑉 is finite-dimensional with dim 𝑉 > 0 , and suppose 𝑊 is infinite- dimensional. Prove that ℒ (𝑉 , 𝑊) is infinite-dimensional. 15 Suppose 𝑣 1 , … , 𝑣 𝑚 is a linearly dependent list of vectors in 𝑉 . Suppose also that 𝑊 ≠ {0} . Prove that there exist 𝑤 1 , … , 𝑤 𝑚 ∈ 𝑊 such that no 𝑇 ∈ ℒ (𝑉 , 𝑊) satisfies 𝑇𝑣 𝑘 = 𝑤 𝑘 for each 𝑘 = 1 , … , 𝑚 . 16 Suppose 𝑉 is finite-dimensional with dim 𝑉 > 1 . Prove that there exist 𝑆 , 𝑇 ∈ ℒ (𝑉) such that 𝑆𝑇 ≠ 𝑇𝑆 . 17 Suppose 𝑉 is finite-dimensional. Show that the only two-sided ideals of ℒ (𝑉) are {0} and ℒ (𝑉) . A subspace ℰ of ℒ (𝑉) is called a two-sided ideal of ℒ (𝑉) if 𝑇𝐸 ∈ ℰ and 𝐸𝑇 ∈ ℰ for all 𝐸 ∈ ℰ and all 𝑇 ∈ ℒ (𝑉) . --- Section 3B Null Spaces and Ranges Null Space and Injectivity In this section we will learn about two subspaces that are intimately connected with each linear map. We begin with the set of vectors that get mapped to 0 . 3.11 definition: null space, null 𝑇 For 𝑇 ∈ ℒ (𝑉 , 𝑊) , the null space of 𝑇 , denoted by null 𝑇 , is the subset of 𝑉 consisting of those vectors that 𝑇 maps to 0 : null 𝑇 = {𝑣 ∈ 𝑉 ∶ 𝑇𝑣 = 0}. 3.12 example: null space • If 𝑇 is the zero map from 𝑉 to 𝑊 , meaning that 𝑇𝑣 = 0 for every 𝑣 ∈ 𝑉 , then null 𝑇 = 𝑉 . • Suppose 𝜑 ∈ ℒ (𝐂 3 , 𝐂) is defined by 𝜑(𝑧 1 , 𝑧 2 , 𝑧 3 ) = 𝑧 1 + 2𝑧 2 + 3𝑧 3 . Then null 𝜑 equals {(𝑧 1 , 𝑧 2 , 𝑧 3 ) ∈ 𝐂 3 ∶ 𝑧 1 + 2𝑧 2 + 3𝑧 3 = 0} , which is a subspace of the domain of 𝜑 . We will soon see that the null space of each linear map is a subspace of its domain. • The word “null” means zero. Thus the term “null space”should remind you of the connection to 0 . Some mathematicians use the term kernel instead of null space. Suppose 𝐷 ∈ ℒ ( 𝒫 (𝐑)) is the differentiation map defined by 𝐷𝑝 = 𝑝 ′ . The only functions whose derivative equals the zero function are the constant functions. Thus the null space of 𝐷 equals the set of constant functions. • Suppose that 𝑇 ∈ ℒ ( 𝒫 (𝐑)) is the multiplication by 𝑥 2 map defined by (𝑇𝑝)(𝑥) = 𝑥 2 𝑝(𝑥) . The only polynomial 𝑝 such that 𝑥 2 𝑝(𝑥) = 0 for all 𝑥 ∈ 𝐑 is the 0 polynomial. Thus null 𝑇 = {0} . • Suppose 𝑇 ∈ ℒ (𝐅 ∞ ) is the backward shift defined by 𝑇(𝑥 1 , 𝑥 2 , 𝑥 3 , … ) = (𝑥 2 , 𝑥 3 , … ). Then 𝑇(𝑥 1 , 𝑥 2 , 𝑥 3 , … ) equals 0 if and only if the numbers 𝑥 2 , 𝑥 3 , … are all 0 . Thus null 𝑇 = {(𝑎 , 0 , 0 , … ) ∶ 𝑎 ∈ 𝐅} . The next result shows that the null space of each linear map is a subspace of the domain. In particular, 0 is in the null space of every linear map. 3.13 the null space is a subspace Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then null 𝑇 is a subspace of 𝑉 . Proof Because 𝑇 is a linear map, 𝑇(0) = 0 (by 3.10). Thus 0 ∈ null 𝑇 . Suppose 𝑢 , 𝑣 ∈ null 𝑇 . Then 𝑇(𝑢 + 𝑣) = 𝑇𝑢 + 𝑇𝑣 = 0 + 0 = 0. Hence 𝑢 + 𝑣 ∈ null 𝑇 . Thus null 𝑇 is closed under addition. Suppose 𝑢 ∈ null 𝑇 and 𝜆 ∈ 𝐅 . Then 𝑇(𝜆𝑢) = 𝜆𝑇𝑢 = 𝜆0 = 0. Hence 𝜆𝑢 ∈ null 𝑇 . Thus null 𝑇 is closed under scalar multiplication. We have shown that null 𝑇 contains 0 and is closed under addition and scalar multiplication. Thus null 𝑇 is a subspace of 𝑉 (by 1.34). As we will soon see, for a linear map the next definition is closely connected to the null space. 3.14 definition: injective A function 𝑇 ∶ 𝑉 → 𝑊 is called injective if 𝑇𝑢 = 𝑇𝑣 implies 𝑢 = 𝑣 . The term one-to-one means the same as injective. We could rephrase the definition above to say that 𝑇 is injective if 𝑢 ≠ 𝑣 implies that 𝑇𝑢 ≠ 𝑇𝑣 . Thus 𝑇 is injective if and only if it maps distinct inputs to distinct outputs. The next result says that we can check whether a linear map is injective by checking whether 0 is the only vector that gets mapped to 0 . As a simple application of this result, we see that of the linear maps whose null spaces we computed in 3.12, only multiplication by 𝑥 2 is injective (except that the zero map is injective in the special case 𝑉 = {0} ). 3.15 injectivity ⟺ null space equals {0} Let 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then 𝑇 is injective if and only if null 𝑇 = {0} . Proof First suppose 𝑇 is injective. We want to prove that null 𝑇 = {0} . We already know that {0} ⊆ null 𝑇 (by 3.10). To prove the inclusion in the other direction, suppose 𝑣 ∈ null 𝑇 . Then 𝑇(𝑣) = 0 = 𝑇(0). Because 𝑇 is injective, the equation above implies that 𝑣 = 0 . Thus we can conclude that null 𝑇 = {0} , as desired. To prove the implication in the other direction, now suppose null 𝑇 = {0} . We want to prove that 𝑇 is injective. To do this, suppose 𝑢 , 𝑣 ∈ 𝑉 and 𝑇𝑢 = 𝑇𝑣 . Then 0 = 𝑇𝑢 − 𝑇𝑣 = 𝑇(𝑢 − 𝑣). Thus 𝑢 − 𝑣 is in null 𝑇 , which equals {0} . Hence 𝑢 − 𝑣 = 0 , which implies that 𝑢 = 𝑣 . Hence 𝑇 is injective, as desired. Annotated Entity: ID: 74 Spans: True Boxes: True Text: Section 3B Null Spaces and Ranges 61 Range and Surjectivity Now we give a name to the set of outputs of a linear map. 3.16 definition: range For 𝑇 ∈ ℒ (𝑉 , 𝑊) , the range of 𝑇 is the subset of 𝑊 consisting of those vectors that are equal to 𝑇𝑣 for some 𝑣 ∈ 𝑉 : range 𝑇 = {𝑇𝑣 ∶ 𝑣 ∈ 𝑉}. 3.17 example: range • If 𝑇 is the zero map from 𝑉 to 𝑊 , meaning that 𝑇𝑣 = 0 for every 𝑣 ∈ 𝑉 , then range 𝑇 = {0} . • Suppose 𝑇 ∈ ℒ (𝐑 2 , 𝐑 3 ) is defined by 𝑇(𝑥 , 𝑦) = (2𝑥 , 5𝑦 , 𝑥 + 𝑦) . Then range 𝑇 = {(2𝑥 , 5𝑦 , 𝑥 + 𝑦) ∶ 𝑥 , 𝑦 ∈ 𝐑}. Note that range 𝑇 is a subspace of 𝐑 3 . We will soon see that the range of each element of ℒ (𝑉 , 𝑊) is a subspace of 𝑊 . • Suppose 𝐷 ∈ ℒ ( 𝒫 (𝐑)) is the differentiation map defined by 𝐷𝑝 = 𝑝 ′ . Because for every polynomial 𝑞 ∈ 𝒫 (𝐑) there exists a polynomial 𝑝 ∈ 𝒫 (𝐑) such that 𝑝 ′ = 𝑞 , the range of 𝐷 is 𝒫 (𝐑) . The next result shows that the range of each linear map is a subspace of the vector space into which it is being mapped. 3.18 the range is a subspace If 𝑇 ∈ ℒ (𝑉 , 𝑊) , then range 𝑇 is a subspace of 𝑊 . Proof Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then 𝑇(0) = 0 (by 3.10), which implies that 0 ∈ range 𝑇 . If 𝑤 1 , 𝑤 2 ∈ range 𝑇 , then there exist 𝑣 1 , 𝑣 2 ∈ 𝑉 such that 𝑇𝑣 1 = 𝑤 1 and 𝑇𝑣 2 = 𝑤 2 . Thus 𝑇(𝑣 1 + 𝑣 2 ) = 𝑇𝑣 1 + 𝑇𝑣 2 = 𝑤 1 + 𝑤 2 . Hence 𝑤 1 + 𝑤 2 ∈ range 𝑇 . Thus range 𝑇 is closed under addition. If 𝑤 ∈ range 𝑇 and 𝜆 ∈ 𝐅 , then there exists 𝑣 ∈ 𝑉 such that 𝑇𝑣 = 𝑤 . Thus 𝑇(𝜆𝑣) = 𝜆𝑇𝑣 = 𝜆𝑤. Hence 𝜆𝑤 ∈ range 𝑇 . Thus range 𝑇 is closed under scalar multiplication. We have shown that range 𝑇 contains 0 and is closed under addition and scalar multiplication. Thus range 𝑇 is a subspace of 𝑊 (by 1.34). 3.19 definition: surjective A function 𝑇 ∶ 𝑉 → 𝑊 is called surjective if its range equals 𝑊 . To illustrate the definition above, note that of the ranges we computed in 3.17, only the differentiation map is surjective (except that the zero map is surjective in the special case 𝑊 = {0} ). Some people use the term onto , which means the same as surjective. Whether a linear map is surjective depends on what we are thinking of as the vector space into which it maps. 3.20 example: surjectivity depends on the target space The differentiation map 𝐷 ∈ ℒ ( 𝒫 5 (𝐑)) defined by 𝐷𝑝 = 𝑝 ′ is not surjective, because the polynomial 𝑥 5 is not in the range of 𝐷 . However, the differentiation map 𝑆 ∈ ℒ ( 𝒫 5 (𝐑) , 𝒫 4 (𝐑)) defined by 𝑆𝑝 = 𝑝 ′ is surjective, because its range equals 𝒫 4 (𝐑) , which is the vector space into which 𝑆 maps. ### Fundamental Theorem of Linear Maps The next result is so important that it gets a dramatic name. 3.21 fundamental theorem of linear maps Suppose 𝑉 is finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then range 𝑇 is finite-dimensional and dim 𝑉 = dim null 𝑇 + dim range 𝑇. Proof Let 𝑢 1 , … , 𝑢 𝑚 be a basis of null 𝑇 ; thus dim null 𝑇 = 𝑚 . The linearly independent list 𝑢 1 , … , 𝑢 𝑚 can be extended to a basis 𝑢 1 , … , 𝑢 𝑚 , 𝑣 1 , … , 𝑣 𝑛 of 𝑉 (by 2.32). Thus dim 𝑉 = 𝑚 + 𝑛 . To complete the proof, we need to show that range 𝑇 is finite-dimensional and dim range 𝑇 = 𝑛 . We will do this by proving that 𝑇𝑣 1 , … , 𝑇𝑣 𝑛 is a basis of range 𝑇 . Let 𝑣 ∈ 𝑉 . Because 𝑢 1 , … , 𝑢 𝑚 , 𝑣 1 , … , 𝑣 𝑛 spans 𝑉 , we can write 𝑣 = 𝑎 1 𝑢 1 + ⋯ + 𝑎 𝑚 𝑢 𝑚 + 𝑏 1 𝑣 1 + ⋯ + 𝑏 𝑛 𝑣 𝑛 , where the 𝑎 ’s and 𝑏 ’s are in 𝐅 . Applying 𝑇 to both sides of this equation, we get 𝑇𝑣 = 𝑏 1 𝑇𝑣 1 + ⋯ + 𝑏 𝑛 𝑇𝑣 𝑛 , where the terms of the form 𝑇𝑢 𝑘 disappeared because each 𝑢 𝑘 is in null 𝑇 . The last equation implies that the list 𝑇𝑣 1 , … , 𝑇𝑣 𝑛 spans range 𝑇 . In particular, range 𝑇 is finite-dimensional. To show 𝑇𝑣 1 , … , 𝑇𝑣 𝑛 is linearly independent, suppose 𝑐 1 , … , 𝑐 𝑛 ∈ 𝐅 and 𝑐 1 𝑇𝑣 1 + ⋯ + 𝑐 𝑛 𝑇𝑣 𝑛 = 0. Then 𝑇(𝑐 1 𝑣 1 + ⋯ + 𝑐 𝑛 𝑣 𝑛 ) = 0. Hence 𝑐 1 𝑣 1 + ⋯ + 𝑐 𝑛 𝑣 𝑛 ∈ null 𝑇. Because 𝑢 1 , … , 𝑢 𝑚 spans null 𝑇 , we can write 𝑐 1 𝑣 1 + ⋯ + 𝑐 𝑛 𝑣 𝑛 = 𝑑 1 𝑢 1 + ⋯ + 𝑑 𝑚 𝑢 𝑚 , where the 𝑑 ’s are in 𝐅 . This equation implies that all the 𝑐 ’s (and 𝑑 ’s) are 0 (because 𝑢 1 , … , 𝑢 𝑚 , 𝑣 1 , … , 𝑣 𝑛 is linearly independent). Thus 𝑇𝑣 1 , … , 𝑇𝑣 𝑛 is linearly independent and hence is a basis of range 𝑇 , as desired. Now we can show that no linear map from a finite-dimensional vector space to a “smaller” vector space can be injective, where “smaller” is measured by dimension. 3.22 linear map to a lower-dimensional space is not injective Suppose 𝑉 and 𝑊 are finite-dimensional vector spaces such that dim 𝑉 > dim 𝑊 . Then no linear map from 𝑉 to 𝑊 is injective. Proof Let 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then dim null 𝑇 = dim 𝑉 − dim range 𝑇 ≥ dim 𝑉 − dim 𝑊 > 0 , where the first line above comes from the fundamental theorem of linear maps (3.21) and the second line follows from 2.37. The inequality above states that dim null 𝑇 > 0 . This means that null 𝑇 contains vectors other than 0 . Thus 𝑇 is not injective (by 3.15). 3.23 example: linear map from 𝐅 4 to 𝐅 3 is not injective Define a linear map 𝑇 ∶ 𝐅 4 → 𝐅 3 by 𝑇(𝑧 1 , 𝑧 2 , 𝑧 3 , 𝑧 4 ) = ( √ 7𝑧 1 + 𝜋𝑧 2 + 𝑧 4 , 97𝑧 1 + 3𝑧 2 + 2𝑧 3 , 𝑧 2 + 6𝑧 3 + 7𝑧 4 ). Because dim 𝐅 4 > dim 𝐅 3 , we can use 3.22 to assert that 𝑇 is not injective, without doing any calculations. The next result shows that no linear map from a finite-dimensional vector space to a “bigger” vector space can be surjective, where “bigger” is measured by dimension. 3.24 linear map to a higher-dimensional space is not surjective Suppose 𝑉 and 𝑊 are finite-dimensional vector spaces such that dim 𝑉 < dim 𝑊 . Then no linear map from 𝑉 to 𝑊 is surjective. Proof Let 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then dim range 𝑇 = dim 𝑉 − dim null 𝑇 ≤ dim 𝑉 < dim 𝑊 , where the equality above comes from the fundamental theorem of linear maps (3.21). The inequality above states that dim range 𝑇 < dim 𝑊 . This means that range 𝑇 cannot equal 𝑊 . Thus 𝑇 is not surjective. As we will soon see, 3.22 and 3.24 have important consequences in the theory of linear equations. The idea is to express questions about systems of linear equations in terms of linear maps. Let’s begin by rephrasing in terms of linear maps the question of whether a homogeneous system of linear equations has a nonzero solution. Homogeneous , in this context, means that the constant term on the right side of each equation below is 0 . Fix positive integers 𝑚 and 𝑛 , and let 𝐴 𝑗 , 𝑘 ∈ 𝐅 for 𝑗 = 1 , … , 𝑚 and 𝑘 = 1 , … , 𝑛 . Consider the homogeneous system of lin- ear equations 𝑛 ∑ 𝑘=1 𝐴 1 , 𝑘 𝑥 𝑘 = 0 ⋮ 𝑛 ∑ 𝑘=1 𝐴 𝑚 , 𝑘 𝑥 𝑘 = 0. Clearly 𝑥 1 = ⋯ = 𝑥 𝑛 = 0 is a solution of the system of equations above; the question here is whether any other solutions exist. Define 𝑇 ∶ 𝐅 𝑛 → 𝐅 𝑚 by 3.25 𝑇(𝑥 1 , … , 𝑥 𝑛 ) = ( 𝑛 ∑ 𝑘=1 𝐴 1 , 𝑘 𝑥 𝑘 , … , 𝑛 ∑ 𝑘=1 𝐴 𝑚 , 𝑘 𝑥 𝑘 ). The equation 𝑇(𝑥 1 , … , 𝑥 𝑛 ) = 0 (the 0 here is the additive identity in 𝐅 𝑚 , namely, the list of length 𝑚 of all 0 ’s) is the same as the homogeneous system of linear equations above. Thus we want to know if null 𝑇 is strictly bigger than {0} , which is equivalent to 𝑇 not being injective (by 3.15). The next result gives an important condition for ensuring that 𝑇 is not injective. 3.26 homogeneous system of linear equations A homogeneous system of linear equations with more variables than equations has nonzero solutions. Proof Use the notation and result from the discussion above. Thus 𝑇 is a linear map from 𝐅 𝑛 to 𝐅 𝑚 , and we have a homogeneous system of 𝑚 linear equations with 𝑛 variables 𝑥 1 , … , 𝑥 𝑛 . From 3.22 we see that 𝑇 is not injective if 𝑛 > 𝑚 . Example of the result above: a homogeneous system of four linear equations with five variables has nonzero solutions. Inhomogeneous , as used in this context, means that the constant term on the right side of at least one equation below does not equal 0 . Now we consider the question of whether an inhomogeneous system of linear equations has no solutions for some choice of the constant terms. To rephrase this question in terms of a linear map, fix positive integers 𝑚 and 𝑛 , and let 𝐴 𝑗 , 𝑘 ∈ 𝐅 for all 𝑗 = 1 , … , 𝑚 and all 𝑘 = 1 , … , 𝑛 . For 𝑐 1 , … , 𝑐 𝑚 ∈ 𝐅 , consider the system of linear equations 𝑛 ∑ 𝑘=1 𝐴 1 , 𝑘 𝑥 𝑘 = 𝑐 1 ⋮ 3.27 𝑛 ∑ 𝑘=1 𝐴 𝑚 , 𝑘 𝑥 𝑘 = 𝑐 𝑚 . The question here is whether there is some choice of 𝑐 1 , … , 𝑐 𝑚 ∈ 𝐅 such that no solution exists to the system above. The results 3.26 and 3.28, which compare the number of variables and the number of equations, can also be proved using Gaussian elimina- tion. The abstract approach taken here seems to provide cleaner proofs. Define 𝑇 ∶ 𝐅 𝑛 → 𝐅 𝑚 as in 3.25. The equation 𝑇(𝑥 1 , … , 𝑥 𝑛 )=(𝑐 1 , … , 𝑐 𝑚 ) is the same as the system of equations 3.27. Thus we want to know if range 𝑇 ≠ 𝐅 𝑚 . Hence we can rephrase our question about not having a solution for some choice of 𝑐 1 , … , 𝑐 𝑚 ∈ 𝐅 as follows: What condition ensures that 𝑇 is not surjective? The next result gives one such condition. 3.28 inhomogeneous system of linear equations An inhomogeneous system of linear equations with more equations than variables has no solution for some choice of the constant terms. Proof Use the notation and result from the example above. Thus 𝑇 is a linear map from 𝐅 𝑛 to 𝐅 𝑚 , and we have a system of 𝑚 equations with 𝑛 variables 𝑥 1 , … , 𝑥 𝑛 . From 3.24 we see that 𝑇 is not surjective if 𝑛 < 𝑚 . Example of the result above: an inhomogeneous system of five linear equations with four variables has no solution for some choice of the constant terms. Annotated Entity: ID: 79 Spans: True Boxes: True Text: 66 Chapter 3 Linear Maps Exercises 3B 1 Give an example of a linear map 𝑇 with dim null 𝑇 = 3 and dim range 𝑇 = 2 . 2 Suppose 𝑆 , 𝑇 ∈ ℒ (𝑉) are such that range 𝑆 ⊆ null 𝑇 . Prove that (𝑆𝑇) 2 = 0 . 3 Suppose 𝑣 1 , … , 𝑣 𝑚 is a list of vectors in 𝑉 . Define 𝑇 ∈ ℒ (𝐅 𝑚 , 𝑉) by 𝑇(𝑧 1 , … , 𝑧 𝑚 ) = 𝑧 1 𝑣 1 + ⋯ + 𝑧 𝑚 𝑣 𝑚 . (a) What property of 𝑇 corresponds to 𝑣 1 , … , 𝑣 𝑚 spanning 𝑉 ? (b) What property of 𝑇 corresponds to the list 𝑣 1 , … , 𝑣 𝑚 being linearly independent? 4 Show that {𝑇 ∈ ℒ (𝐑 5 , 𝐑 4 ) ∶ dim null 𝑇 > 2} is not a subspace of ℒ (𝐑 5 , 𝐑 4 ) . 5 Give an example of 𝑇 ∈ ℒ (𝐑 4 ) such that range 𝑇 = null 𝑇 . 6 Prove that there does not exist 𝑇 ∈ ℒ (𝐑 5 ) such that range 𝑇 = null 𝑇 . 7 Suppose 𝑉 and 𝑊 are finite-dimensional with 2 ≤ dim 𝑉 ≤ dim 𝑊 . Show that {𝑇 ∈ ℒ (𝑉 , 𝑊) ∶ 𝑇 is not injective } is not a subspace of ℒ (𝑉 , 𝑊) . 8 Suppose 𝑉 and 𝑊 are finite-dimensional with dim 𝑉 ≥ dim 𝑊 ≥ 2 . Show that {𝑇 ∈ ℒ (𝑉 , 𝑊) ∶ 𝑇 is not surjective } is not a subspace of ℒ (𝑉 , 𝑊) . 9 Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) is injective and 𝑣 1 , … , 𝑣 𝑛 is linearly independent in 𝑉 . Prove that 𝑇𝑣 1 , … , 𝑇𝑣 𝑛 is linearly independent in 𝑊 . 10 Suppose 𝑣 1 , … , 𝑣 𝑛 spans 𝑉 and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Show that 𝑇𝑣 1 , … , 𝑇𝑣 𝑛 spans range 𝑇 . 11 Suppose that 𝑉 is finite-dimensional and that 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that there exists a subspace 𝑈 of 𝑉 such that 𝑈 ∩ null 𝑇 = {0} and range 𝑇 = {𝑇𝑢 ∶ 𝑢 ∈ 𝑈}. 12 Suppose 𝑇 is a linear map from 𝐅 4 to 𝐅 2 such that null 𝑇 = {(𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 ) ∈ 𝐅 4 ∶ 𝑥 1 = 5𝑥 2 and 𝑥 3 = 7𝑥 4 }. Prove that 𝑇 is surjective. 13 Suppose 𝑈 is a three-dimensional subspace of 𝐑 8 and that 𝑇 is a linear map from 𝐑 8 to 𝐑 5 such that null 𝑇 = 𝑈 . Prove that 𝑇 is surjective. 14 Prove that there does not exist a linear map from 𝐅 5 to 𝐅 2 whose null space equals {(𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 ) ∈ 𝐅 5 ∶ 𝑥 1 = 3𝑥 2 and 𝑥 3 = 𝑥 4 = 𝑥 5 } . 15 Suppose there exists a linear map on 𝑉 whose null space and range are both finite-dimensional. Prove that 𝑉 is finite-dimensional. Annotated Entity: ID: 80 Spans: True Boxes: True Text: Section 3B Null Spaces and Ranges 67 16 Suppose 𝑉 and 𝑊 are both finite-dimensional. Prove that there exists an injective linear map from 𝑉 to 𝑊 if and only if dim 𝑉 ≤ dim 𝑊 . 17 Suppose 𝑉 and 𝑊 are both finite-dimensional. Prove that there exists a surjective linear map from 𝑉 onto 𝑊 if and only if dim 𝑉 ≥ dim 𝑊 . 18 Suppose 𝑉 and 𝑊 are finite-dimensional and that 𝑈 is a subspace of 𝑉 . Prove that there exists 𝑇 ∈ ℒ (𝑉 , 𝑊) such that null 𝑇 = 𝑈 if and only if dim 𝑈 ≥ dim 𝑉 − dim 𝑊 . 19 Suppose 𝑊 is finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that 𝑇 is injective if and only if there exists 𝑆 ∈ ℒ (𝑊 , 𝑉) such that 𝑆𝑇 is the identity operator on 𝑉 . 20 Suppose 𝑊 is finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that 𝑇 is surjective if and only if there exists 𝑆 ∈ ℒ (𝑊 , 𝑉) such that 𝑇𝑆 is the identity operator on 𝑊 . 21 Suppose 𝑉 is finite-dimensional, 𝑇 ∈ ℒ (𝑉 , 𝑊) , and 𝑈 is a subspace of 𝑊 . Prove that {𝑣 ∈ 𝑉 ∶ 𝑇𝑣 ∈ 𝑈} is a subspace of 𝑉 and dim {𝑣 ∈ 𝑉 ∶ 𝑇𝑣 ∈ 𝑈} = dim null 𝑇 + dim (𝑈 ∩ range 𝑇). 22 Suppose 𝑈 and 𝑉 are finite-dimensional vector spaces and 𝑆 ∈ ℒ (𝑉 , 𝑊) and 𝑇 ∈ ℒ (𝑈 , 𝑉) . Prove that dim null 𝑆𝑇 ≤ dim null 𝑆 + dim null 𝑇. 23 Suppose 𝑈 and 𝑉 are finite-dimensional vector spaces and 𝑆 ∈ ℒ (𝑉 , 𝑊) and 𝑇 ∈ ℒ (𝑈 , 𝑉) . Prove that dim range 𝑆𝑇 ≤ min { dim range 𝑆 , dim range 𝑇}. 24 (a) Suppose dim 𝑉 = 5 and 𝑆 , 𝑇 ∈ ℒ (𝑉) are such that 𝑆𝑇 = 0 . Prove that dim range 𝑇𝑆 ≤ 2 . (b) Give an example of 𝑆 , 𝑇 ∈ ℒ (𝐅 5 ) with 𝑆𝑇 = 0 and dim range 𝑇𝑆 = 2 . 25 Suppose that 𝑊 is finite-dimensional and 𝑆 , 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that null 𝑆 ⊆ null 𝑇 if and only if there exists 𝐸 ∈ ℒ (𝑊) such that 𝑇 = 𝐸𝑆 . 26 Suppose that 𝑉 is finite-dimensional and 𝑆 , 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that range 𝑆 ⊆ range 𝑇 if and only if there exists 𝐸 ∈ ℒ (𝑉) such that 𝑆 = 𝑇𝐸 . 27 Suppose 𝑃 ∈ ℒ (𝑉) and 𝑃 2 = 𝑃 . Prove that 𝑉 = null 𝑃 ⊕ range 𝑃 . 28 Suppose 𝐷 ∈ ℒ ( 𝒫 (𝐑)) is such that deg 𝐷𝑝 = ( deg 𝑝) − 1 for every non- constant polynomial 𝑝 ∈ 𝒫 (𝐑) . Prove that 𝐷 is surjective. The notation 𝐷 is used above to remind you of the differentiation map that sends a polynomial 𝑝 to 𝑝 ′ . Annotated Entity: ID: 81 Spans: True Boxes: True Text: 68 Chapter 3 Linear Maps 29 Suppose 𝑝 ∈ 𝒫 (𝐑) . Prove that there exists a polynomial 𝑞 ∈ 𝒫 (𝐑) such that 5𝑞 ″ + 3𝑞 ′ = 𝑝 . This exercise can be done without linear algebra, but it’s more fun to do it using linear algebra. 30 Suppose 𝜑 ∈ ℒ (𝑉 , 𝐅) and 𝜑 ≠ 0 . Suppose 𝑢 ∈ 𝑉 is not in null 𝜑 . Prove that 𝑉 = null 𝜑 ⊕ {𝑎𝑢 ∶ 𝑎 ∈ 𝐅}. 31 Suppose 𝑉 is finite-dimensional, 𝑋 is a subspace of 𝑉 , and 𝑌 is a finite- dimensional subspace of 𝑊 . Prove that there exists 𝑇 ∈ ℒ (𝑉 , 𝑊) such that null 𝑇 = 𝑋 and range 𝑇 = 𝑌 if and only if dim 𝑋 + dim 𝑌 = dim 𝑉 . 32 Suppose 𝑉 is finite-dimensional with dim 𝑉 > 1 . Show that if 𝜑 ∶ ℒ (𝑉)→ 𝐅 is a linear map such that 𝜑(𝑆𝑇) = 𝜑(𝑆)𝜑(𝑇) for all 𝑆 , 𝑇 ∈ ℒ (𝑉) , then 𝜑 = 0 . Hint: The description of the two-sided ideals of ℒ (𝑉) given by Exercise 17 in Section 3A might be useful. 33 Suppose that 𝑉 and 𝑊 are real vector spaces and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Define 𝑇 𝐂 ∶ 𝑉 𝐂 → 𝑊 𝐂 by 𝑇 𝐂 (𝑢 + 𝑖𝑣) = 𝑇𝑢 + 𝑖𝑇𝑣 for all 𝑢 , 𝑣 ∈ 𝑉 . (a) Show that 𝑇 𝐂 is a (complex) linear map from 𝑉 𝐂 to 𝑊 𝐂 . (b) Show that 𝑇 𝐂 is injective if and only if 𝑇 is injective. (c) Show that range 𝑇 𝐂 = 𝑊 𝐂 if and only if range 𝑇 = 𝑊 . See Exercise 8 in Section 1B for the definition of the complexification 𝑉 𝐂 . The linear map 𝑇 𝐂 is called the complexification of the linear map 𝑇 . Annotated Entity: ID: 82 Spans: True Boxes: True Text: Section 3C Matrices 69 3C Matrices Representing a Linear Map by a Matrix We know that if 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑇 ∶ 𝑉 → 𝑊 is linear, then the values of 𝑇𝑣 1 , … , 𝑇𝑣 𝑛 determine the values of 𝑇 on arbitrary vectors in 𝑉 —see the linear map lemma (3.4). As we will soon see, matrices provide an efficient method of recording the values of the 𝑇𝑣 𝑘 ’s in terms of a basis of 𝑊 . 3.29 definition: matrix, 𝐴 𝑗 , 𝑘 Suppose 𝑚 and 𝑛 are nonnegative integers. An 𝑚 -by- 𝑛 matrix 𝐴 is a rectangular array of elements of 𝐅 with 𝑚 rows and 𝑛 columns: 𝐴 = ⎛⎜⎜⎜⎝ 𝐴 1 , 1 ⋯ 𝐴 1 , 𝑛 ⋮ ⋮ 𝐴 𝑚 , 1 ⋯ 𝐴 𝑚 , 𝑛 ⎞⎟⎟⎟⎠. The notation 𝐴 𝑗 , 𝑘 denotes the entry in row 𝑗 , column 𝑘 of 𝐴 . 3.30 example: 𝐴 𝑗 , 𝑘 equals entry in row 𝑗 , column 𝑘 of 𝐴 When dealing with matrices, the first index refers to the row number; the second index refers to the column number. Suppose 𝐴 = ( 8 4 5 − 3𝑖 1 9 7 ) . Thus 𝐴 2 , 3 refers to the entry in the sec- ond row, third column of 𝐴 , which means that 𝐴 2 , 3 = 7 . Now we come to the key definition in this section. 3.31 definition: matrix of a linear map, ℳ (𝑇) Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑚 is a basis of 𝑊 . The matrix of 𝑇 with respect to these bases is the 𝑚 -by- 𝑛 matrix ℳ (𝑇) whose entries 𝐴 𝑗 , 𝑘 are defined by 𝑇𝑣 𝑘 = 𝐴 1 , 𝑘 𝑤 1 + ⋯ + 𝐴 𝑚 , 𝑘 𝑤 𝑚 . If the bases 𝑣 1 , … , 𝑣 𝑛 and 𝑤 1 , … , 𝑤 𝑚 are not clear from the context, then the notation ℳ (𝑇 , (𝑣 1 , … , 𝑣 𝑛 ) , (𝑤 1 , … , 𝑤 𝑚 )) is used. The matrix ℳ (𝑇) of a linear map 𝑇 ∈ ℒ (𝑉 , 𝑊) depends on the basis 𝑣 1 , … , 𝑣 𝑛 of 𝑉 and the basis 𝑤 1 , … , 𝑤 𝑚 of 𝑊 , as well as on 𝑇 . However, the bases should be clear from the context, and thus they are often not included in the notation. To remember how ℳ (𝑇) is constructed from 𝑇 , you might write across the top of the matrix the basis vectors 𝑣 1 , … , 𝑣 𝑛 for the domain and along the left the basis vectors 𝑤 1 , … , 𝑤 𝑚 for the vector space into which 𝑇 maps, as follows: 𝑣 1 ⋯ 𝑣 𝑘 ⋯ 𝑣 𝑛 𝑤 1 ℳ (𝑇) = ⋮ 𝑤 𝑚 ⎛⎜⎜⎜⎝ 𝐴 1 , 𝑘 ⋮ 𝐴 𝑚 , 𝑘 ⎞⎟⎟⎟⎠. The 𝑘 th column of ℳ (𝑇) consists of the scalars needed to write 𝑇𝑣 𝑘 as a linear combination of 𝑤 1 , … , 𝑤 𝑚 : 𝑇𝑣 𝑘 = 𝑚 ∑ 𝑗=1 𝐴 𝑗 , 𝑘 𝑤 𝑗 . In the matrix above only the 𝑘 th col- umn is shown. Thus the second index of each displayed entry of the matrix above is 𝑘 . The picture above should remind you that 𝑇𝑣 𝑘 can be computed from ℳ (𝑇) by multiplying each entry in the 𝑘 th column by the corresponding 𝑤 𝑗 from the left col- umn, and then adding up the resulting vectors. If 𝑇 is a linear map from an 𝑛 -dimensional vector space to an 𝑚 -dimensional vector space, then ℳ (𝑇) is an 𝑚 -by- 𝑛 matrix. If 𝑇 is a linear map from 𝐅 𝑛 to 𝐅 𝑚 , then unless stated otherwise, assume the bases in question are the standard ones (where the 𝑘 th basis vector is 1 in the 𝑘 th slot and 0 in all other slots). If you think of elements of 𝐅 𝑚 as columns of 𝑚 numbers, then you can think of the 𝑘 th column of ℳ (𝑇) as 𝑇 applied to the 𝑘 th standard basis vector. 3.32 example: the matrix of a linear map from 𝐅 2 to 𝐅 3 Suppose 𝑇 ∈ ℒ (𝐅 2 , 𝐅 3 ) is defined by 𝑇(𝑥 , 𝑦) = (𝑥 + 3𝑦 , 2𝑥 + 5𝑦 , 7𝑥 + 9𝑦). Because 𝑇(1 , 0) = (1 , 2 , 7) and 𝑇(0 , 1) = (3 , 5 , 9) , the matrix of 𝑇 with respect to the standard bases is the 3 -by- 2 matrix below: ℳ (𝑇) = ⎛⎜⎜⎜⎝ 1 3 2 5 7 9 ⎞⎟⎟⎟⎠. When working with 𝒫 𝑚 (𝐅) , use the standard basis 1 , 𝑥 , 𝑥 2 , … , 𝑥 𝑚 unless the context indicates otherwise. 3.33 example: matrix of the differentiation map from 𝒫 3 (𝐑) to 𝒫 2 (𝐑) Suppose 𝐷 ∈ ℒ ( 𝒫 3 (𝐑) , 𝒫 2 (𝐑)) is the differentiation map defined by 𝐷𝑝 = 𝑝 ′ . Because (𝑥 𝑛 ) ′ = 𝑛𝑥 𝑛−1 , the matrix of 𝐷 with respect to the standard bases is the 3 -by- 4 matrix below: ℳ (𝐷) = ⎛ ⎜ ⎜⎜⎝ 0 1 0 0 0 0 2 0 0 0 0 3 ⎞ ⎟ ⎟⎟⎠. For the rest of this section, assume that 𝑈 , 𝑉 , and 𝑊 are finite-dimensional and that a basis has been chosen for each of these vector spaces. Thus for each linear map from 𝑉 to 𝑊 , we can talk about its matrix (with respect to the chosen bases). Is the matrix of the sum of two linear maps equal to the sum of the matrices of the two maps? Right now this question does not yet make sense because although we have defined the sum of two linear maps, we have not defined the sum of two matrices. Fortunately, the natural definition of the sum of two matrices has the right properties. Specifically, we make the following definition. 3.34 definition: matrix addition The sum of two matrices of the same size is the matrix obtained by adding corresponding entries in the matrices: $ \left( \begin{array}{ccc} A_{1,1}& \cdots & A_{1,n} \\\\\ \vdots & & \vdots \\\\ A_{m,1} & \cdots & A_{m,n}\ \\ \end{array}\right) + \left(\begin{array}{ccc} C_{1,1} & \cdots & C_{1,n} \\\\ \vdots & & \vdots \\\\ C_{m,1} & \cdots & C_{m,n} \ \\ \end{array} \ \right) = $ $\ \left(\begin{array}{ccc} A_{1,1}+C_{1,1} & \cdots & A_{1,n}+C_{1,n} \\\\ \ \vdots & & \ \vdots \\\\ A_{m,1}+C_{m,1} & \ \cdots & A_{m,n}+C_{m,n} \ \\ \end{array} \ \right). $ 3.35 matrix of the sum of linear maps Suppose 𝑆 , 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then ℳ (𝑆 + 𝑇) = ℳ (𝑆) + ℳ (𝑇) . The verification of the result above follows from the definitions and is left to the reader. Still assuming that we have some bases in mind, is the matrix of a scalar times a linear map equal to the scalar times the matrix of the linear map? Again, the question does not yet make sense because we have not defined scalar multiplication on matrices. Fortunately, the natural definition again has the right properties. 3.36 definition: scalar multiplication of a matrix The product of a scalar and a matrix is the matrix obtained by multiplying each entry in the matrix by the scalar: 𝜆 ⎛ ⎜ ⎜ ⎜⎝ 𝐴 1 , 1 ⋯ 𝐴 1 , 𝑛 ⋮ ⋮ 𝐴 𝑚 , 1 ⋯ 𝐴 𝑚 , 𝑛 ⎞ ⎟ ⎟ ⎟⎠ = ⎛ ⎜ ⎜ ⎜⎝ 𝜆𝐴 1 , 1 ⋯ 𝜆𝐴 1 , 𝑛 ⋮ ⋮ 𝜆𝐴 𝑚 , 1 ⋯ 𝜆𝐴 𝑚 , 𝑛 ⎞ ⎟ ⎟ ⎟⎠. Annotated Entity: ID: 85 Spans: True Boxes: True Text: 72 Chapter 3 Linear Maps 3.37 example: addition and scalar multiplication of matrices 2( 3 1 −1 5 ) + ( 4 2 1 6 ) = ( 6 2 −2 10 ) + ( 4 2 1 6 ) = ( 10 4 −1 16 ) In the next result, the assumption is that the same bases are used for both the linear maps 𝜆𝑇 and 𝑇 . 3.38 the matrix of a scalar times a linear map Suppose 𝜆 ∈ 𝐅 and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then ℳ (𝜆𝑇) = 𝜆 ℳ (𝑇) . The verification of the result above is also left to the reader. Because addition and scalar multiplication have now been defined for matrices, you should not be surprised that a vector space is about to appear. First we introduce a bit of notation so that this new vector space has a name, and then we find the dimension of this new vector space. 3.39 notation: 𝐅 𝑚 , 𝑛 For 𝑚 and 𝑛 positive integers, the set of all 𝑚 -by- 𝑛 matrices with entries in 𝐅 is denoted by 𝐅 𝑚 , 𝑛 . 3.40 dim 𝐅 𝑚 , 𝑛 = 𝑚𝑛 Suppose 𝑚 and 𝑛 are positive integers. With addition and scalar multiplication defined as above, 𝐅 𝑚 , 𝑛 is a vector space of dimension 𝑚𝑛 . Proof The verification that 𝐅 𝑚 , 𝑛 is a vector space is left to the reader. Note that the additive identity of 𝐅 𝑚 , 𝑛 is the 𝑚 -by- 𝑛 matrix all of whose entries equal 0 . The reader should also verify that the list of distinct 𝑚 -by- 𝑛 matrices that have 0 in all entries except for a 1 in one entry is a basis of 𝐅 𝑚 , 𝑛 . There are 𝑚𝑛 such matrices, so the dimension of 𝐅 𝑚 , 𝑛 equals 𝑚𝑛 . Matrix Multiplication Suppose, as previously, that 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑚 is a basis of 𝑊 . Suppose also that 𝑢 1 , … , 𝑢 𝑝 is a basis of 𝑈 . Consider linear maps 𝑇 ∶ 𝑈 → 𝑉 and 𝑆 ∶ 𝑉 → 𝑊 . The composition 𝑆𝑇 is a linear map from 𝑈 to 𝑊 . Does ℳ (𝑆𝑇) equal ℳ (𝑆) ℳ (𝑇) ? This question does not yet make sense because we have not defined the product of two matrices. We will choose a definition of matrix multiplication that forces this question to have a positive answer. Let’s see how to do this. Suppose ℳ (𝑆) = 𝐴 and ℳ (𝑇) = 𝐵 . For 1 ≤ 𝑘 ≤ 𝑝 , we have (𝑆𝑇)𝑢 𝑘 = 𝑆( 𝑛 ∑ 𝑟=1 𝐵 𝑟 , 𝑘 𝑣 𝑟 ) = 𝑛 ∑ 𝑟=1 𝐵 𝑟 , 𝑘 𝑆𝑣 𝑟 = 𝑛 ∑ 𝑟=1 𝐵 𝑟 , 𝑘 𝑚 ∑ 𝑗=1 𝐴 𝑗 , 𝑟 𝑤 𝑗 = 𝑚 ∑ 𝑗=1 ( 𝑛 ∑ 𝑟=1 𝐴 𝑗 , 𝑟 𝐵 𝑟 , 𝑘 )𝑤 𝑗 . Thus ℳ (𝑆𝑇) is the 𝑚 -by- 𝑝 matrix whose entry in row 𝑗 , column 𝑘 , equals 𝑛 ∑ 𝑟=1 𝐴 𝑗 , 𝑟 𝐵 𝑟 , 𝑘 . Now we see how to define matrix multiplication so that the desired equation ℳ (𝑆𝑇) = ℳ (𝑆) ℳ (𝑇) holds. From Claude: $ \text{Suppose $\mathcal{M}(S) = A$ and $\mathcal{M}(T) = B$. For $1 \leq k \leq p$, we have} \begin{align*} (ST)u_k &= S\left(\sum_{r=1}^n B_{r,k}v_r\right) \\\\ &= \sum_{r=1}^n B_{r,k}Sv_r \\\\ &= \sum_{r=1}^n B_{r,k} \sum_{j=1}^m A_{j,r}w_j \\\\ &= \sum_{j=1}^m\left(\sum_{r=1}^n A_{j,r}B_{r,k}\right)w_j. \end{align*}\\\\ $ $\text{Thus $\mathcal{M}(ST)$ is the $m$-by-$p$ matrix whose entry in row $j$, column $k$, equals} \sum_{r=1}^n A_{j,r}B_{r,k}.$ 3.41 definition: matrix multiplication Suppose 𝐴 is an 𝑚 -by- 𝑛 matrix and 𝐵 is an 𝑛 -by- 𝑝 matrix. Then 𝐴𝐵 is defined to be the 𝑚 -by- 𝑝 matrix whose entry in row 𝑗 , column 𝑘 , is given by the equation (𝐴𝐵) 𝑗 , 𝑘 = 𝑛 ∑ 𝑟=1 𝐴 𝑗 , 𝑟 𝐵 𝑟 , 𝑘 . Thus the entry in row 𝑗 , column 𝑘 , of 𝐴𝐵 is computed by taking row 𝑗 of 𝐴 and column 𝑘 of 𝐵 , multiplying together corresponding entries, and then summing. You may have learned this definition of matrix multiplication in an earlier course, although you may not have seen this motivation for it. Note that we define the product of two matrices only when the number of columns of the first matrix equals the number of rows of the second matrix. 3.42 example: matrix multiplication Here we multiply together a 3 -by- 2 matrix and a 2 -by- 4 matrix, obtaining a 3 -by- 4 matrix: ⎛⎜⎜⎜⎝ 1 2 3 4 5 6 ⎞⎟⎟⎟⎠( 6 5 4 3 2 1 0 −1 ) = ⎛⎜⎜⎜⎝ 10 7 4 1 26 19 12 5 42 31 20 9 ⎞⎟⎟⎟⎠ . Matrix multiplication is not commutative— 𝐴𝐵 is not necessarily equal to 𝐵𝐴 even if both products are defined (see Exercise 10). Matrix multiplication is distributive and associative (see Exercises 11 and 12). Annotated Entity: ID: 87 Spans: True Boxes: True Text: 74 Chapter 3 Linear Maps In the next result, we assume that the same basis of 𝑉 is used in considering 𝑇 ∈ ℒ (𝑈 , 𝑉) and 𝑆 ∈ ℒ (𝑉 , 𝑊) , the same basis of 𝑊 is used in considering 𝑆 ∈ ℒ (𝑉 , 𝑊) and 𝑆𝑇 ∈ ℒ (𝑈 , 𝑊) , and the same basis of 𝑈 is used in considering 𝑇 ∈ ℒ (𝑈 , 𝑉) and 𝑆𝑇 ∈ ℒ (𝑈 , 𝑊) . 3.43 matrix of product of linear maps If 𝑇 ∈ ℒ (𝑈 , 𝑉) and 𝑆 ∈ ℒ (𝑉 , 𝑊) , then ℳ (𝑆𝑇) = ℳ (𝑆) ℳ (𝑇) . The proof of the result above is the calculation that was done as motivation before the definition of matrix multiplication. In the next piece of notation, note that as usual the first index refers to a row and the second index refers to a column, with a vertically centered dot used as a placeholder. 3.44 notation: 𝐴 𝑗 , ⋅ , 𝐴 ⋅ , 𝑘 Suppose 𝐴 is an 𝑚 -by- 𝑛 matrix. • If 1 ≤ 𝑗 ≤ 𝑚 , then 𝐴 𝑗 , ⋅ denotes the 1 -by- 𝑛 matrix consisting of row 𝑗 of 𝐴 . • If 1 ≤ 𝑘 ≤ 𝑛 , then 𝐴 ⋅ , 𝑘 denotes the 𝑚 -by- 1 matrix consisting of column 𝑘 of 𝐴 . 3.45 example: 𝐴 𝑗 , ⋅ equals 𝑗 th row of 𝐴 and 𝐴 ⋅ , 𝑘 equals 𝑘 th column of 𝐴 The notation 𝐴 2 , ⋅ denotes the second row of 𝐴 and 𝐴 ⋅ , 2 denotes the second column of 𝐴 . Thus if 𝐴 = ( 8 4 5 1 9 7 ) , then 𝐴 2 , ⋅ = ( 1 9 7 ) and 𝐴 ⋅ , 2 = ( 4 9 ). The product of a 1 -by- 𝑛 matrix and an 𝑛 -by- 1 matrix is a 1 -by- 1 matrix. How- ever, we will frequently identify a 1 -by- 1 matrix with its entry. For example, ( 3 4 )( 6 2 ) = ( 26 ) because 3 ⋅ 6 + 4 ⋅ 2 = 26 . However, we can identify ( 26 ) with 26 , writing ( 3 4 )( 6 2 ) = 26 . The next result uses the convention discussed in the paragraph above to give another way to think of matrix multiplication. For example, the next result and the calculation in the paragraph above explain why the entry in row 2 , column 1 , of the product in Example 3.42 equals 26 . Annotated Entity: ID: 88 Spans: True Boxes: True Text: Section 3C Matrices 75 3.46 entry of matrix product equals row times column Suppose 𝐴 is an 𝑚 -by- 𝑛 matrix and 𝐵 is an 𝑛 -by- 𝑝 matrix. Then (𝐴𝐵) 𝑗 , 𝑘 = 𝐴 𝑗 , ⋅ 𝐵 ⋅ , 𝑘 if 1 ≤ 𝑗 ≤ 𝑚 and 1 ≤ 𝑘 ≤ 𝑝 . In other words, the entry in row 𝑗 , column 𝑘 , of 𝐴𝐵 equals (row 𝑗 of 𝐴 ) times (column 𝑘 of 𝐵 ). Proof Suppose 1 ≤ 𝑗 ≤ 𝑚 and 1 ≤ 𝑘 ≤ 𝑝 . The definition of matrix multiplication states that 3.47 (𝐴𝐵) 𝑗 , 𝑘 = 𝐴 𝑗 , 1 𝐵 1 , 𝑘 + ⋯ + 𝐴 𝑗 , 𝑛 𝐵 𝑛 , 𝑘 . The definition of matrix multiplication also implies that the product of the 1 -by- 𝑛 matrix 𝐴 𝑗 , ⋅ and the 𝑛 -by- 1 matrix 𝐵 ⋅ , 𝑘 is the 1 -by- 1 matrix whose entry is the number on the right side of the equation above. Thus the entry in row 𝑗 , column 𝑘 , of 𝐴𝐵 equals (row 𝑗 of 𝐴 ) times (column 𝑘 of 𝐵 ). The next result gives yet another way to think of matrix multiplication. In the result below, (𝐴𝐵) ⋅ , 𝑘 is column 𝑘 of the 𝑚 -by- 𝑝 matrix 𝐴𝐵 . Thus (𝐴𝐵) ⋅ , 𝑘 is an 𝑚 -by- 1 matrix. Also, 𝐴𝐵 ⋅ , 𝑘 is an 𝑚 -by- 1 matrix because it is the product of an 𝑚 -by- 𝑛 matrix and an 𝑛 -by- 1 matrix. Thus the two sides of the equation in the result below have the same size, making it reasonable that they might be equal. 3.48 column of matrix product equals matrix times column Suppose 𝐴 is an 𝑚 -by- 𝑛 matrix and 𝐵 is an 𝑛 -by- 𝑝 matrix. Then (𝐴𝐵) ⋅ , 𝑘 = 𝐴𝐵 ⋅ , 𝑘 if 1 ≤ 𝑘 ≤ 𝑝 . In other words, column 𝑘 of 𝐴𝐵 equals 𝐴 times column 𝑘 of 𝐵 . Proof As discussed above, (𝐴𝐵) ⋅ , 𝑘 and 𝐴𝐵 ⋅ , 𝑘 are both 𝑚 -by- 1 matrices. If 1 ≤ 𝑗 ≤ 𝑚 , then the entry in row 𝑗 of (𝐴𝐵) ⋅ , 𝑘 is the left side of 3.47 and the entry in row 𝑗 of 𝐴𝐵 ⋅ , 𝑘 is the right side of 3.47. Thus (𝐴𝐵) ⋅ , 𝑘 = 𝐴𝐵 ⋅ , 𝑘 . Our next result will give another way of thinking about the product of an 𝑚 -by- 𝑛 matrix and an 𝑛 -by- 1 matrix, motivated by the next example. 3.49 example: product of a 3 -by- 2 matrix and a 2 -by- 1 matrix Use our definitions and basic arithmetic to verify that ⎛⎜⎜⎜⎝ 1 2 3 4 5 6 ⎞⎟⎟⎟⎠( 5 1 ) = ⎛⎜⎜⎜⎝ 7 19 31 ⎞⎟⎟⎟⎠ = 5⎛⎜⎜⎜⎝ 1 3 5 ⎞⎟⎟⎟⎠ + 1⎛⎜⎜⎜⎝ 2 4 6 ⎞⎟⎟⎟⎠. Thus in this example, the product of a 3 -by- 2 matrix and a 2 -by- 1 matrix is a linear combination of the columns of the 3 -by- 2 matrix, with the scalars ( 5 and 1 ) that multiply the columns coming from the 2 -by- 1 matrix. Annotated Entity: ID: 89 Spans: True Boxes: True Text: 76 Chapter 3 Linear Maps The next result generalizes the example above. 3.50 linear combination of columns Suppose 𝐴 is an 𝑚 -by- 𝑛 matrix and 𝑏 = ⎛⎜⎜⎜ ⎝ 𝑏 1 ⋮ 𝑏 𝑛 ⎞⎟⎟⎟ ⎠ is an 𝑛 -by- 1 matrix. Then 𝐴𝑏 = 𝑏 1 𝐴 ⋅ , 1 + ⋯ + 𝑏 𝑛 𝐴 ⋅ , 𝑛 . In other words, 𝐴𝑏 is a linear combination of the columns of 𝐴 , with the scalars that multiply the columns coming from 𝑏 . Proof If 𝑘 ∈ {1 , … , 𝑚} , then the definition of matrix multiplication implies that the entry in row 𝑘 of the 𝑚 -by- 1 matrix 𝐴𝑏 is 𝐴 𝑘 , 1 𝑏 1 + ⋯ + 𝐴 𝑘 , 𝑛 𝑏 𝑛 . The entry in row 𝑘 of 𝑏 1 𝐴 ⋅ , 1 + ⋯ + 𝑏 𝑛 𝐴 ⋅ , 𝑛 also equals the number displayed above. Because 𝐴𝑏 and 𝑏 1 𝐴 ⋅ , 1 + ⋯ + 𝑏 𝑛 𝐴 ⋅ , 𝑛 have the same entry in row 𝑘 for each 𝑘 ∈ {1 , … , 𝑚} , we conclude that 𝐴𝑏 = 𝑏 1 𝐴 ⋅ , 1 + ⋯ + 𝑏 𝑛 𝐴 ⋅ , 𝑛 . Our two previous results focus on the columns of a matrix. Analogous results hold for the rows of a matrix. Specifically, see Exercises 8 and 9, which can be proved using appropriate modifications of the proofs of 3.48 and 3.50. The next result is the main tool used in the next subsection to prove the column–row factorization (3.56) and to prove that the column rank of a matrix equals the row rank (3.57). To be consistent with the notation often used with the column–row factorization, including in the next subsection, the matrices in the next result are called 𝐶 and 𝑅 instead of 𝐴 and 𝐵 . 3.51 matrix multiplication as linear combinations of columns Suppose 𝐶 is an 𝑚 -by- 𝑐 matrix and 𝑅 is a 𝑐 -by- 𝑛 matrix. (a) If 𝑘 ∈ {1 , … , 𝑛} , then column 𝑘 of 𝐶𝑅 is a linear combination of the columns of 𝐶 , with the coefficients of this linear combination coming from column 𝑘 of 𝑅 . (b) If 𝑗 ∈ {1 , … , 𝑚} , then row 𝑗 of 𝐶𝑅 is a linear combination of the rows of 𝑅 , with the coefficients of this linear combination coming from row 𝑗 of 𝐶 . Proof Suppose 𝑘 ∈ {1 , … , 𝑛} . Then column 𝑘 of 𝐶𝑅 equals 𝐶𝑅 ⋅ , 𝑘 (by 3.48), which equals the linear combination of the columns of 𝐶 with coefficients coming from 𝑅 ⋅ , 𝑘 (by 3.50). Thus (a) holds. To prove (b), follow the pattern of the proof of (a) but use rows instead of columns and use Exercises 8 and 9 instead of 3.48 and 3.50. Annotated Entity: ID: 90 Spans: True Boxes: True Text: Section 3C Matrices 77 Column–Row Factorization and Rank of a Matrix We begin by defining two nonnegative integers associated with each matrix. 3.52 definition: column rank, row rank Suppose 𝐴 is an 𝑚 -by- 𝑛 matrix with entries in 𝐅 . • The column rank of 𝐴 is the dimension of the span of the columns of 𝐴 in 𝐅 𝑚 , 1 . • The row rank of 𝐴 is the dimension of the span of the rows of 𝐴 in 𝐅 1 , 𝑛 . If 𝐴 is an 𝑚 -by- 𝑛 matrix, then the column rank of 𝐴 is at most 𝑛 (because 𝐴 has 𝑛 columns) and the column rank of 𝐴 is also at most 𝑚 (because dim 𝐅 𝑚 , 1 = 𝑚 ). Similarly, the row rank of 𝐴 is also at most min {𝑚 , 𝑛} . 3.53 example: column rank and row rank of a 2 -by- 4 matrix Suppose 𝐴 = ( 4 7 1 8 3 5 2 9 ). The column rank of 𝐴 is the dimension of span ⎛⎜⎜⎝( 4 3 ) , ( 7 5 ) , ( 1 2 ) , ( 8 9 )⎞⎟⎟⎠ in 𝐅 2 , 1 . Neither of the first two vectors listed above in 𝐅 2 , 1 is a scalar multiple of the other. Thus the span of this list of length four has dimension at least two. The span of this list of vectors in 𝐅 2 , 1 cannot have dimension larger than two because dim 𝐅 2 , 1 = 2 . Thus the span of this list has dimension two, which means that the column rank of 𝐴 is two. The row rank of 𝐴 is the dimension of span (( 4 7 1 8 ) , ( 3 5 2 9 )) in 𝐅 1 , 4 . Neither of the two vectors listed above in 𝐅 1 , 4 is a scalar multiple of the other. Thus the span of this list of length two has dimension two, which means that the row rank of 𝐴 is two. We now define the transpose of a matrix. 3.54 definition: transpose, 𝐴 t The transpose of a matrix 𝐴 , denoted by 𝐴 t , is the matrix obtained from 𝐴 by interchanging rows and columns. Specifically, if 𝐴 is an 𝑚 -by- 𝑛 matrix, then 𝐴 t is the 𝑛 -by- 𝑚 matrix whose entries are given by the equation (𝐴 t ) 𝑘 , 𝑗 = 𝐴 𝑗 , 𝑘 . Annotated Entity: ID: 91 Spans: True Boxes: True Text: 78 Chapter 3 Linear Maps 3.55 example: transpose of a matrix If 𝐴 = ⎛⎜⎜⎜⎝ 5 −7 3 8 −4 2 ⎞⎟⎟⎟⎠ , then 𝐴 t = ( 5 3 −4 −7 8 2 ) . Note that here 𝐴 is a 3 -by- 2 matrix and 𝐴 t is a 2 -by- 3 matrix. The transpose has nice algebraic properties: (𝐴 + 𝐵) t = 𝐴 t + 𝐵 t , (𝜆𝐴) t = 𝜆𝐴 t , and (𝐴𝐶) t = 𝐶 t 𝐴 t for all 𝑚 -by- 𝑛 matrices 𝐴 , 𝐵 , all 𝜆 ∈ 𝐅 , and all 𝑛 -by- 𝑝 matrices 𝐶 (see Exercises 14 and 15). The next result will be the main tool used to prove that the column rank equals the row rank (see 3.57). 3.56 column–row factorization Suppose 𝐴 is an 𝑚 -by- 𝑛 matrix with entries in 𝐅 and column rank 𝑐 ≥ 1 . Then there exist an 𝑚 -by- 𝑐 matrix 𝐶 and a 𝑐 -by- 𝑛 matrix 𝑅 , both with entries in 𝐅 , such that 𝐴 = 𝐶𝑅 . Proof Each column of 𝐴 is an 𝑚 -by- 1 matrix. The list 𝐴 ⋅ , 1 , … , 𝐴 ⋅ , 𝑛 of columns of 𝐴 can be reduced to a basis of the span of the columns of 𝐴 (by 2.30). This basis has length 𝑐 , by the definition of the column rank. The 𝑐 columns in this basis can be put together to form an 𝑚 -by- 𝑐 matrix 𝐶 . If 𝑘 ∈ {1 , … , 𝑛} , then column 𝑘 of 𝐴 is a linear combination of the columns of 𝐶 . Make the coefficients of this linear combination into column 𝑘 of a 𝑐 -by- 𝑛 matrix that we call 𝑅 . Then 𝐴 = 𝐶𝑅 , as follows from 3.51(a). In Example 3.53, the column rank and row rank turned out to equal each other. The next result states that this happens for all matrices. 3.57 column rank equals row rank Suppose 𝐴 ∈ 𝐅 𝑚 , 𝑛 . Then the column rank of 𝐴 equals the row rank of 𝐴 . Proof Let 𝑐 denote the column rank of 𝐴 . Let 𝐴 = 𝐶𝑅 be the column–row factorization of 𝐴 given by 3.56, where 𝐶 is an 𝑚 -by- 𝑐 matrix and 𝑅 is a 𝑐 -by- 𝑛 matrix. Then 3.51(b) tells us that every row of 𝐴 is a linear combination of the rows of 𝑅 . Because 𝑅 has 𝑐 rows, this implies that the row rank of 𝐴 is less than or equal to the column rank 𝑐 of 𝐴 . To prove the inequality in the other direction, apply the result in the previous paragraph to 𝐴 t , getting column rank of 𝐴 = row rank of 𝐴 t ≤ column rank of 𝐴 t = row rank of 𝐴. Thus the column rank of 𝐴 equals the row rank of 𝐴 . Annotated Entity: ID: 92 Spans: True Boxes: True Text: Section 3C Matrices 79 Because the column rank equals the row rank, the last result allows us to dispense with the terms “column rank” and “row rank” and just use the simpler term “rank”. 3.58 definition: rank The rank of a matrix 𝐴 ∈ 𝐅 𝑚 , 𝑛 is the column rank of 𝐴 . See 3.133 and Exercise 8 in Section 7A for alternative proofs that the column rank equals the row rank. Exercises 3C 1 Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) . Show that with respect to each choice of bases of 𝑉 and 𝑊 , the matrix of 𝑇 has at least dim range 𝑇 nonzero entries. 2 Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that dim range 𝑇 = 1 if and only if there exist a basis of 𝑉 and a basis of 𝑊 such that with respect to these bases, all entries of ℳ (𝑇) equal 1 . 3 Suppose 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑚 is a basis of 𝑊 . (a) Show that if 𝑆 , 𝑇 ∈ ℒ (𝑉 , 𝑊) , then ℳ (𝑆 + 𝑇) = ℳ (𝑆) + ℳ (𝑇) . (b) Show that if 𝜆 ∈ 𝐅 and 𝑇 ∈ ℒ (𝑉 , 𝑊) , then ℳ (𝜆𝑇) = 𝜆 ℳ (𝑇) . This exercise asks you to verify 3.35 and 3.38. 4 Suppose that 𝐷 ∈ ℒ ( 𝒫 3 (𝐑) , 𝒫 2 (𝐑)) is the differentiation map defined by 𝐷𝑝 = 𝑝 ′ . Find a basis of 𝒫 3 (𝐑) and a basis of 𝒫 2 (𝐑) such that the matrix of 𝐷 with respect to these bases is ⎛⎜⎜⎜⎝ 1 0 0 0 0 1 0 0 0 0 1 0 ⎞⎟⎟⎟⎠ . Compare with Example 3.33. The next exercise generalizes this exercise. 5 Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that there exist a basis of 𝑉 and a basis of 𝑊 such that with respect to these bases, all entries of ℳ (𝑇) are 0 except that the entries in row 𝑘 , column 𝑘 , equal 1 if 1 ≤ 𝑘 ≤ dim range 𝑇 . 6 Suppose 𝑣 1 , … , 𝑣 𝑚 is a basis of 𝑉 and 𝑊 is finite-dimensional. Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that there exists a basis 𝑤 1 , … , 𝑤 𝑛 of 𝑊 such that all entries in the first column of ℳ (𝑇) [with respect to the bases 𝑣 1 , … , 𝑣 𝑚 and 𝑤 1 , … , 𝑤 𝑛 ] are 0 except for possibly a 1 in the first row, first column. In this exercise, unlike Exercise 5, you are given the basis of 𝑉 instead of being able to choose a basis of 𝑉 . Annotated Entity: ID: 93 Spans: True Boxes: True Text: 80 Chapter 3 Linear Maps 7 Suppose 𝑤 1 , … , 𝑤 𝑛 is a basis of 𝑊 and 𝑉 is finite-dimensional. Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that there exists a basis 𝑣 1 , … , 𝑣 𝑚 of 𝑉 such that all entries in the first row of ℳ (𝑇) [with respect to the bases 𝑣 1 , … , 𝑣 𝑚 and 𝑤 1 , … , 𝑤 𝑛 ] are 0 except for possibly a 1 in the first row, first column. In this exercise, unlike Exercise 5, you are given the basis of 𝑊 instead of being able to choose a basis of 𝑊 . 8 Suppose 𝐴 is an 𝑚 -by- 𝑛 matrix and 𝐵 is an 𝑛 -by- 𝑝 matrix. Prove that (𝐴𝐵) 𝑗 , ⋅ = 𝐴 𝑗 , ⋅ 𝐵 for each 1 ≤ 𝑗 ≤ 𝑚 . In other words, show that row 𝑗 of 𝐴𝐵 equals (row 𝑗 of 𝐴 ) times 𝐵 . This exercise gives the row version of 3.48. 9 Suppose 𝑎 = ( 𝑎 1 ⋯ 𝑎 𝑛 ) is a 1 -by- 𝑛 matrix and 𝐵 is an 𝑛 -by- 𝑝 matrix. Prove that 𝑎𝐵 = 𝑎 1 𝐵 1 , ⋅ + ⋯ + 𝑎 𝑛 𝐵 𝑛 , ⋅ . In other words, show that 𝑎𝐵 is a linear combination of the rows of 𝐵 , with the scalars that multiply the rows coming from 𝑎 . This exercise gives the row version of 3.50. 10 Give an example of 2 -by- 2 matrices 𝐴 and 𝐵 such that 𝐴𝐵 ≠ 𝐵𝐴 . 11 Prove that the distributive property holds for matrix addition and matrix multiplication. In other words, suppose 𝐴 , 𝐵 , 𝐶 , 𝐷 , 𝐸 , and 𝐹 are matrices whose sizes are such that 𝐴(𝐵 + 𝐶) and (𝐷 + 𝐸)𝐹 make sense. Explain why 𝐴𝐵 + 𝐴𝐶 and 𝐷𝐹 + 𝐸𝐹 both make sense and prove that 𝐴(𝐵 + 𝐶) = 𝐴𝐵 + 𝐴𝐶 and (𝐷 + 𝐸)𝐹 = 𝐷𝐹 + 𝐸𝐹. 12 Prove that matrix multiplication is associative. In other words, suppose 𝐴 , 𝐵 , and 𝐶 are matrices whose sizes are such that (𝐴𝐵)𝐶 makes sense. Explain why 𝐴(𝐵𝐶) makes sense and prove that (𝐴𝐵)𝐶 = 𝐴(𝐵𝐶). Try to find a clean proof that illustrates the following quote from Emil Artin: “It is my experience that proofs involving matrices can be shortened by 50% if one throws the matrices out.” 13 Suppose 𝐴 is an 𝑛 -by- 𝑛 matrix and 1 ≤ 𝑗 , 𝑘 ≤ 𝑛 . Show that the entry in row 𝑗 , column 𝑘 , of 𝐴 3 (which is defined to mean 𝐴𝐴𝐴 ) is 𝑛 ∑ 𝑝=1 𝑛 ∑ 𝑟=1 𝐴 𝑗 , 𝑝 𝐴 𝑝 , 𝑟 𝐴 𝑟 , 𝑘 . 14 Suppose 𝑚 and 𝑛 are positive integers. Prove that the function 𝐴 ↦ 𝐴 t is a linear map from 𝐅 𝑚 , 𝑛 to 𝐅 𝑛 , 𝑚 . Annotated Entity: ID: 94 Spans: True Boxes: True Text: Section 3C Matrices 81 15 Prove that if 𝐴 is an 𝑚 -by- 𝑛 matrix and 𝐶 is an 𝑛 -by- 𝑝 matrix, then (𝐴𝐶) t = 𝐶 t 𝐴 t . This exercise shows that the transpose of the product of two matrices is the product of the transposes in the opposite order. 16 Suppose 𝐴 is an 𝑚 -by- 𝑛 matrix with 𝐴 ≠ 0 . Prove that the rank of 𝐴 is 1 if and only if there exist (𝑐 1 , … , 𝑐 𝑚 ) ∈ 𝐅 𝑚 and (𝑑 1 , … , 𝑑 𝑛 ) ∈ 𝐅 𝑛 such that 𝐴 𝑗 , 𝑘 = 𝑐 𝑗 𝑑 𝑘 for every 𝑗 = 1 , … , 𝑚 and every 𝑘 = 1 , … , 𝑛 . 17 Suppose 𝑇 ∈ ℒ (𝑉) , and 𝑢 1 , … , 𝑢 𝑛 and 𝑣 1 , … , 𝑣 𝑛 are bases of 𝑉 . Prove that the following are equivalent. (a) 𝑇 is injective. (b) The columns of ℳ (𝑇) are linearly independent in 𝐅 𝑛 , 1 . (c) The columns of ℳ (𝑇) span 𝐅 𝑛 , 1 . (d) The rows of ℳ (𝑇) span 𝐅 1 , 𝑛 . (e) The rows of ℳ (𝑇) are linearly independent in 𝐅 1 , 𝑛 . Here ℳ (𝑇) means ℳ (𝑇 , (𝑢 1 , … , 𝑢 𝑛 ) , (𝑣 1 , … , 𝑣 𝑛 )) . Annotated Entity: ID: 95 Spans: True Boxes: True Text: 82 Chapter 3 Linear Maps 3D Invertibility and Isomorphisms Invertible Linear Maps We begin this section by defining the notions of invertible and inverse in the context of linear maps. 3.59 definition: invertible, inverse • A linear map 𝑇 ∈ ℒ (𝑉 , 𝑊) is called invertible if there exists a linear map 𝑆 ∈ ℒ (𝑊 , 𝑉) such that 𝑆𝑇 equals the identity operator on 𝑉 and 𝑇𝑆 equals the identity operator on 𝑊 . • A linear map 𝑆 ∈ ℒ (𝑊 , 𝑉) satisfying 𝑆𝑇 = 𝐼 and 𝑇𝑆 = 𝐼 is called an inverse of 𝑇 (note that the first 𝐼 is the identity operator on 𝑉 and the second 𝐼 is the identity operator on 𝑊 ). The definition above mentions “an inverse”. However, the next result shows that we can change this terminology to “the inverse”. 3.60 inverse is unique An invertible linear map has a unique inverse. Proof Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) is invertible and 𝑆 1 and 𝑆 2 are inverses of 𝑇 . Then 𝑆 1 = 𝑆 1 𝐼 = 𝑆 1 (𝑇𝑆 2 ) = (𝑆 1 𝑇)𝑆 2 = 𝐼𝑆 2 = 𝑆 2 . Thus 𝑆 1 = 𝑆 2 . Now that we know that the inverse is unique, we can give it a notation. 3.61 notation: 𝑇 −1 If 𝑇 is invertible, then its inverse is denoted by 𝑇 −1 . In other words, if 𝑇 ∈ ℒ (𝑉 , 𝑊) is invertible, then 𝑇 −1 is the unique element of ℒ (𝑊 , 𝑉) such that 𝑇 −1 𝑇 = 𝐼 and 𝑇𝑇 −1 = 𝐼 . 3.62 example: inverse of a linear map from 𝐑 3 to 𝐑 3 Suppose 𝑇 ∈ ℒ (𝐑 3 ) is defined by 𝑇(𝑥 , 𝑦 , 𝑧) = (−𝑦 , 𝑥 , 4𝑧) . Thus 𝑇 is a counterclockwise rotation by 90 ∘ in the 𝑥𝑦 -plane and a stretch by a factor of 4 in the direction of the 𝑧 -axis. Hence the inverse map 𝑇 −1 ∈ ℒ (𝐑 3 ) is the clockwise rotation by 90 ∘ in the 𝑥𝑦 -plane and a stretch by a factor of 1 4 in the direction of the 𝑧 -axis: 𝑇 −1 (𝑥 , 𝑦 , 𝑧) = (𝑦 , −𝑥 , 14 𝑧). Annotated Entity: ID: 96 Spans: True Boxes: True Text: Section 3D Invertibility and Isomorphisms 83 The next result shows that a linear map is invertible if and only if it is one-to- one and onto. 3.63 invertibility ⟺ injectivity and surjectivity A linear map is invertible if and only if it is injective and surjective. Proof Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) . We need to show that 𝑇 is invertible if and only if it is injective and surjective. First suppose 𝑇 is invertible. To show that 𝑇 is injective, suppose 𝑢 , 𝑣 ∈ 𝑉 and 𝑇𝑢 = 𝑇𝑣 . Then 𝑢 = 𝑇 −1 (𝑇𝑢) = 𝑇 −1 (𝑇𝑣) = 𝑣 , so 𝑢 = 𝑣 . Hence 𝑇 is injective. We are still assuming that 𝑇 is invertible. Now we want to prove that 𝑇 is surjective. To do this, let 𝑤 ∈ 𝑊 . Then 𝑤 = 𝑇(𝑇 −1 𝑤) , which shows that 𝑤 is in the range of 𝑇 . Thus range 𝑇 = 𝑊 . Hence 𝑇 is surjective, completing this direction of the proof. Now suppose 𝑇 is injective and surjective. We want to prove that 𝑇 is invertible. For each 𝑤 ∈ 𝑊 , define 𝑆(𝑤) to be the unique element of 𝑉 such that 𝑇(𝑆(𝑤)) = 𝑤 (the existence and uniqueness of such an element follow from the surjectivity and injectivity of 𝑇 ). The definition of 𝑆 implies that 𝑇 ∘ 𝑆 equals the identity operator on 𝑊 . To prove that 𝑆 ∘ 𝑇 equals the identity operator on 𝑉 , let 𝑣 ∈ 𝑉 . Then 𝑇((𝑆 ∘ 𝑇)𝑣) = (𝑇 ∘ 𝑆)(𝑇𝑣) = 𝐼(𝑇𝑣) = 𝑇𝑣. This equation implies that (𝑆 ∘ 𝑇)𝑣 = 𝑣 (because 𝑇 is injective). Thus 𝑆 ∘ 𝑇 equals the identity operator on 𝑉 . To complete the proof, we need to show that 𝑆 is linear. To do this, suppose 𝑤 1 , 𝑤 2 ∈ 𝑊 . Then 𝑇(𝑆(𝑤 1 ) + 𝑆(𝑤 2 )) = 𝑇(𝑆(𝑤 1 )) + 𝑇(𝑆(𝑤 2 )) = 𝑤 1 + 𝑤 2 . Thus 𝑆(𝑤 1 ) + 𝑆(𝑤 2 ) is the unique element of 𝑉 that 𝑇 maps to 𝑤 1 + 𝑤 2 . By the definition of 𝑆 , this implies that 𝑆(𝑤 1 + 𝑤 2 ) = 𝑆(𝑤 1 ) + 𝑆(𝑤 2 ) . Hence 𝑆 satisfies the additive property required for linearity. The proof of homogeneity is similar. Specifically, if 𝑤 ∈ 𝑊 and 𝜆 ∈ 𝐅 , then 𝑇(𝜆𝑆(𝑤)) = 𝜆𝑇(𝑆(𝑤)) = 𝜆𝑤. Thus 𝜆𝑆(𝑤) is the unique element of 𝑉 that 𝑇 maps to 𝜆𝑤 . By the definition of 𝑆 , this implies that 𝑆(𝜆𝑤) = 𝜆𝑆(𝑤) . Hence 𝑆 is linear, as desired. For a linear map from a vector space to itself, you might wonder whether injectivity alone, or surjectivity alone, is enough to imply invertibility. On infinite- dimensional vector spaces, neither condition alone implies invertibility, as illus- trated by the next example, which uses two familiar linear maps from Example 3.3. Annotated Entity: ID: 97 Spans: True Boxes: True Text: 84 Chapter 3 Linear Maps 3.64 example: neither injectivity nor surjectivity implies invertibility • The multiplication by 𝑥 2 linear map from 𝒫 (𝐑) to 𝒫 (𝐑) (see 3.3) is injective but it is not invertible because it is not surjective (the polynomial 1 is not in the range). • The backward shift linear map from 𝐅 ∞ to 𝐅 ∞ (see 3.3) is surjective but it is not invertible because it is not injective [ the vector (1 , 0 , 0 , 0 , … ) is in the null space ] . In view of the example above, the next result is remarkable—it states that for a linear map from a finite-dimensional vector space to a vector space of the same dimension, either injectivity or surjectivity alone implies the other condition. Note that the hypothesis below that dim 𝑉 = dim 𝑊 is automatically satisfied in the important special case where 𝑉 is finite-dimensional and 𝑊 = 𝑉 . 3.65 injectivity is equivalent to surjectivity ( if dim 𝑉 = dim 𝑊 < ∞ ) Suppose that 𝑉 and 𝑊 are finite-dimensional vector spaces, dim 𝑉 = dim 𝑊 , and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then 𝑇 is invertible ⟺ 𝑇 is injective ⟺ 𝑇 is surjective . Proof The fundamental theorem of linear maps (3.21) states that 3.66 dim 𝑉 = dim null 𝑇 + dim range 𝑇. If 𝑇 is injective (which by 3.15 is equivalent to the condition dim null 𝑇 = 0 ), then the equation above implies that dim range 𝑇 = dim 𝑉 − dim null 𝑇 = dim 𝑉 = dim 𝑊 , which implies that 𝑇 is surjective (by 2.39). Conversely, if 𝑇 is surjective, then 3.66 implies that dim null 𝑇 = dim 𝑉 − dim range 𝑇 = dim 𝑉 − dim 𝑊 = 0 , which implies that 𝑇 is injective. Thus we have shown that 𝑇 is injective if and only if 𝑇 is surjective. Thus if 𝑇 is either injective or surjective, then 𝑇 is both injective and surjective, which implies that 𝑇 is invertible. Hence 𝑇 is invertible if and only if 𝑇 is injective if and only if 𝑇 is surjective. The next example illustrates the power of the previous result. Although it is possible to prove the result in the example below without using linear algebra, the proof using linear algebra is cleaner and easier. Annotated Entity: ID: 98 Spans: True Boxes: True Text: Section 3D Invertibility and Isomorphisms 85 3.67 example: there exists a polynomial 𝑝 such that ((𝑥 2 + 5𝑥 + 7)𝑝) ″ = 𝑞 The linear map 𝑝 ↦ ((𝑥 2 + 5𝑥 + 7)𝑝) ″ from 𝒫 (𝐑) to itself is injective, as you can show. Thus we are tempted to use 3.65 to show that this map is surjective. However, Example 3.64 shows that the magic of 3.65 does not apply to the infinite-dimensional vector space 𝒫 (𝐑) . We will get around this problem by restricting attention to the finite-dimensional vector space 𝒫 𝑚 (𝐑) . Suppose 𝑞 ∈ 𝒫 (𝐑) . There exists a nonnegative integer 𝑚 such that 𝑞 ∈ 𝒫 𝑚 (𝐑) . Define 𝑇 ∶ 𝒫 𝑚 (𝐑) → 𝒫 𝑚 (𝐑) by 𝑇𝑝 = ((𝑥 2 + 5𝑥 + 7)𝑝) ″ . Multiplying a nonzero polynomial by (𝑥 2 + 5𝑥 + 7) increases the degree by 2 , and then differentiating twice reduces the degree by 2 . Thus 𝑇 is indeed a linear map from 𝒫 𝑚 (𝐑) to itself. Every polynomial whose second derivative equals 0 is of the form 𝑎𝑥 + 𝑏 , where 𝑎 , 𝑏 ∈ 𝐑 . Thus null 𝑇 = {0} . Hence 𝑇 is injective. Thus 𝑇 is surjective (by 3.65), which means that there exists a polynomial 𝑝 ∈ 𝒫 𝑚 (𝐑) such that ((𝑥 2 + 5𝑥 + 7)𝑝) ″ = 𝑞 , as claimed in the title of this example. Exercise 35 in Section 6A gives a similar but more spectacular example of using 3.65. The hypothesis in the result below that dim 𝑉 = dim 𝑊 holds in the important special case in which 𝑉 is finite-dimensional and 𝑊 = 𝑉 . Thus in that case, the equation 𝑆𝑇 = 𝐼 implies that 𝑆𝑇 = 𝑇𝑆 , even though we do not have multiplicative commutativity of arbitrary linear maps from 𝑉 to 𝑉 . 3.68 𝑆𝑇 = 𝐼 ⟺ 𝑇𝑆 = 𝐼 ( on vector spaces of the same dimension ) Suppose 𝑉 and 𝑊 are finite-dimensional vector spaces of the same dimension, 𝑆 ∈ ℒ (𝑊 , 𝑉) , and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then 𝑆𝑇 = 𝐼 if and only if 𝑇𝑆 = 𝐼 . Proof First suppose 𝑆𝑇 = 𝐼 . If 𝑣 ∈ 𝑉 and 𝑇𝑣 = 0 , then 𝑣 = 𝐼𝑣 = (𝑆𝑇)𝑣 = 𝑆(𝑇𝑣) = 𝑆(0) = 0. Thus 𝑇 is injective (by 3.15). Because 𝑉 and 𝑊 have the same dimension, this implies that 𝑇 is invertible (by 3.65). Now multiply both sides of the equation 𝑆𝑇 = 𝐼 by 𝑇 −1 on the right, getting 𝑆 = 𝑇 −1 . Thus 𝑇𝑆 = 𝑇𝑇 −1 = 𝐼 , as desired. To prove the implication in the other direction, simply reverse the roles of 𝑆 and 𝑇 (and 𝑉 and 𝑊 ) in the direction we have already proved, showing that if 𝑇𝑆 = 𝐼 , then 𝑆𝑇 = 𝐼 . Annotated Entity: ID: 99 Spans: True Boxes: True Text: 86 Chapter 3 Linear Maps Isomorphic Vector Spaces The next definition captures the idea of two vector spaces that are essentially the same, except for the names of their elements. 3.69 definition: isomorphism, isomorphic • An isomorphism is an invertible linear map. • Two vector spaces are called isomorphic if there is an isomorphism from one vector space onto the other one. Think of an isomorphism 𝑇 ∶ 𝑉 → 𝑊 as relabeling 𝑣 ∈ 𝑉 as 𝑇𝑣 ∈ 𝑊 . This viewpoint explains why two isomorphic vector spaces have the same vector space properties. The terms “isomorphism” and “invertible linear map” mean the same thing. Use “isomorphism” when you want to emphasize that the two spaces are essentially the same. It can be difficult to determine whether two mathematical structures (such as groups or topological spaces) are essentially the same, differing only in the names of the elements of underlying sets. However, the next result shows that we need to look at only a single number (the dimension) to determine whether two vector spaces are isomorphic. 3.70 dimension shows whether vector spaces are isomorphic Two finite-dimensional vector spaces over 𝐅 are isomorphic if and only if they have the same dimension. Proof First suppose 𝑉 and 𝑊 are isomorphic finite-dimensional vector spaces. Thus there exists an isomorphism 𝑇 from 𝑉 onto 𝑊 . Because 𝑇 is invertible, we have null 𝑇 = {0} and range 𝑇 = 𝑊 . Thus dim null 𝑇 = 0 and dim range 𝑇 = dim 𝑊. The formula dim 𝑉 = dim null 𝑇 + dim range 𝑇 (the fundamental theorem of linear maps, which is 3.21) thus becomes the equation dim 𝑉 = dim 𝑊 , completing the proof in one direction. To prove the other direction, suppose 𝑉 and 𝑊 are finite-dimensional vector spaces of the same dimension. Let 𝑣 1 , … , 𝑣 𝑛 be a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑛 be a basis of 𝑊 . Let 𝑇 ∈ ℒ (𝑉 , 𝑊) be defined by 𝑇(𝑐 1 𝑣 1 + ⋯ + 𝑐 𝑛 𝑣 𝑛 ) = 𝑐 1 𝑤 1 + ⋯ + 𝑐 𝑛 𝑤 𝑛 . Then 𝑇 is a well-defined linear map because 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 . Also, 𝑇 is surjective because 𝑤 1 , … , 𝑤 𝑛 spans 𝑊 . Furthermore, null 𝑇 = {0} because 𝑤 1 , … , 𝑤 𝑛 is linearly independent. Thus 𝑇 is injective. Because 𝑇 is injective and surjective, it is an isomorphism (see 3.63). Hence 𝑉 and 𝑊 are isomorphic. Annotated Entity: ID: 100 Spans: True Boxes: True Text: Section 3D Invertibility and Isomorphisms 87 Every finite-dimensional vector space is isomorphic to some 𝐅 𝑛 . Thus why not just study 𝐅 𝑛 instead of more general vector spaces? To answer this ques- tion, note that an investigation of 𝐅 𝑛 would soon lead to other vector spaces. For example, we would encounter the null space and range of linear maps. Although each of these vector spaces is isomorphic to some 𝐅 𝑚 , thinking of them that way often adds complexity but no new insight. The previous result implies that each finite-dimensional vector space 𝑉 is iso- morphic to 𝐅 𝑛 , where 𝑛 = dim 𝑉 . For example, if 𝑚 is a nonnegative integer, then 𝒫 𝑚 (𝐅) is isomorphic to 𝐅 𝑚 + 1 . Recall that the notation 𝐅 𝑚 , 𝑛 denotes the vector space of 𝑚 -by- 𝑛 matrices with entries in 𝐅 . If 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑚 is a basis of 𝑊 , then for each 𝑇 ∈ ℒ (𝑉 , 𝑊) , we have a matrix ℳ (𝑇) ∈ 𝐅 𝑚 , 𝑛 . Thus once bases have been fixed for 𝑉 and 𝑊 , ℳ becomes a function from ℒ (𝑉 , 𝑊) to 𝐅 𝑚 , 𝑛 . Notice that 3.35 and 3.38 show that ℳ is a lin- ear map. This linear map is actually an isomorphism, as we now show. 3.71 ℒ (𝑉 , 𝑊) and 𝐅 𝑚 , 𝑛 are isomorphic Suppose 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑚 is a basis of 𝑊 . Then ℳ is an isomorphism between ℒ (𝑉 , 𝑊) and 𝐅 𝑚 , 𝑛 . Proof We already noted that ℳ is linear. We need to prove that ℳ is injective and surjective. We begin with injectivity. If 𝑇 ∈ ℒ (𝑉 , 𝑊) and ℳ (𝑇) = 0 , then 𝑇𝑣 𝑘 = 0 for each 𝑘 = 1 , … , 𝑛 . Because 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 , this implies 𝑇 = 0 . Thus ℳ is injective (by 3.15). To prove that ℳ is surjective, suppose 𝐴 ∈ 𝐅 𝑚 , 𝑛 . By the linear map lemma (3.4), there exists 𝑇 ∈ ℒ (𝑉 , 𝑊) such that 𝑇𝑣 𝑘 = 𝑚 ∑ 𝑗=1 𝐴 𝑗 , 𝑘 𝑤 𝑗 for each 𝑘 = 1 , … , 𝑛 . Because ℳ (𝑇) equals 𝐴 , the range of ℳ equals 𝐅 𝑚 , 𝑛 , as desired. Now we can determine the dimension of the vector space of linear maps from one finite-dimensional vector space to another. 3.72 dim ℒ (𝑉 , 𝑊) = ( dim 𝑉)( dim 𝑊) Suppose 𝑉 and 𝑊 are finite-dimensional. Then ℒ (𝑉 , 𝑊) is finite-dimensional and dim ℒ (𝑉 , 𝑊) = ( dim 𝑉)( dim 𝑊). Proof The desired result follows from 3.71, 3.70, and 3.40. Annotated Entity: ID: 101 Spans: True Boxes: True Text: 88 Chapter 3 Linear Maps Linear Maps Thought of as Matrix Multiplication Previously we defined the matrix of a linear map. Now we define the matrix of a vector. 3.73 definition: matrix of a vector, ℳ (𝑣) Suppose 𝑣 ∈ 𝑉 and 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 . The matrix of 𝑣 with respect to this basis is the 𝑛 -by- 1 matrix ℳ (𝑣) = ⎛⎜⎜⎜⎝ 𝑏 1 ⋮ 𝑏 𝑛 ⎞⎟⎟⎟⎠ , where 𝑏 1 , … , 𝑏 𝑛 are the scalars such that 𝑣 = 𝑏 1 𝑣 1 + ⋯ + 𝑏 𝑛 𝑣 𝑛 . The matrix ℳ (𝑣) of a vector 𝑣 ∈ 𝑉 depends on the basis 𝑣 1 , … , 𝑣 𝑛 of 𝑉 , as well as on 𝑣 . However, the basis should be clear from the context and thus it is not included in the notation. 3.74 example: matrix of a vector • The matrix of the polynomial 2 − 7𝑥 + 5𝑥 3 + 𝑥 4 with respect to the standard basis of 𝒫 4 (𝐑) is ⎛⎜⎜⎜ ⎜ ⎜ ⎜⎜⎜⎜⎜⎝ 2 −7 0 5 1 ⎞⎟⎟⎟ ⎟ ⎟ ⎟⎟⎟⎟⎟⎠ . • The matrix of a vector 𝑥 ∈ 𝐅 𝑛 with respect to the standard basis is obtained by writing the coordinates of 𝑥 as the entries in an 𝑛 -by- 1 matrix. In other words, if 𝑥 = (𝑥 1 , … , 𝑥 𝑛 ) ∈ 𝐅 𝑛 , then ℳ (𝑥) = ⎛⎜⎜⎜⎝ 𝑥 1 ⋮ 𝑥 𝑛 ⎞⎟⎟⎟⎠. Occasionally we want to think of elements of 𝑉 as relabeled to be 𝑛 -by- 1 matrices. Once a basis 𝑣 1 , … , 𝑣 𝑛 is chosen, the function ℳ that takes 𝑣 ∈ 𝑉 to ℳ (𝑣) is an isomorphism of 𝑉 onto 𝐅 𝑛 , 1 that implements this relabeling. Recall that if 𝐴 is an 𝑚 -by- 𝑛 matrix, then 𝐴 ⋅ , 𝑘 denotes the 𝑘 th column of 𝐴 , thought of as an 𝑚 -by- 1 matrix. In the next result, ℳ (𝑇𝑣 𝑘 ) is computed with respect to the basis 𝑤 1 , … , 𝑤 𝑚 of 𝑊 . Annotated Entity: ID: 102 Spans: True Boxes: True Text: Section 3D Invertibility and Isomorphisms 89 3.75 ℳ (𝑇) ⋅ , 𝑘 = ℳ (𝑇𝑣 𝑘 ) . Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑚 is a basis of 𝑊 . Let 1 ≤ 𝑘 ≤ 𝑛 . Then the 𝑘 th column of ℳ (𝑇) , which is denoted by ℳ (𝑇) ⋅ , 𝑘 , equals ℳ (𝑇𝑣 𝑘 ) . Proof The desired result follows immediately from the definitions of ℳ (𝑇) and ℳ (𝑇𝑣 𝑘 ) . The next result shows how the notions of the matrix of a linear map, the matrix of a vector, and matrix multiplication fit together. 3.76 linear maps act like matrix multiplication Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝑣 ∈ 𝑉 . Suppose 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑚 is a basis of 𝑊 . Then ℳ (𝑇𝑣) = ℳ (𝑇) ℳ (𝑣). Proof Suppose 𝑣 = 𝑏 1 𝑣 1 + ⋯ + 𝑏 𝑛 𝑣 𝑛 , where 𝑏 1 , … , 𝑏 𝑛 ∈ 𝐅 . Thus 3.77 𝑇𝑣 = 𝑏 1 𝑇𝑣 1 + ⋯ + 𝑏 𝑛 𝑇𝑣 𝑛 . Hence ℳ (𝑇𝑣) = 𝑏 1 ℳ (𝑇𝑣 1 ) + ⋯ + 𝑏 𝑛 ℳ (𝑇𝑣 𝑛 ) = 𝑏 1 ℳ (𝑇) ⋅ , 1 + ⋯ + 𝑏 𝑛 ℳ (𝑇) ⋅ , 𝑛 = ℳ (𝑇) ℳ (𝑣) , where the first equality follows from 3.77 and the linearity of ℳ , the second equality comes from 3.75, and the last equality comes from 3.50. Each 𝑚 -by- 𝑛 matrix 𝐴 induces a linear map from 𝐅 𝑛 , 1 to 𝐅 𝑚 , 1 , namely the matrix multiplication function that takes 𝑥 ∈ 𝐅 𝑛 , 1 to 𝐴𝑥 ∈ 𝐅 𝑚 , 1 . The result above can be used to think of every linear map (from a finite-dimensional vector space to another finite-dimensional vector space) as a matrix multiplication map after suitable relabeling via the isomorphisms given by ℳ . Specifically, if 𝑇 ∈ ℒ (𝑉 , 𝑊) and we identify 𝑣 ∈ 𝑉 with ℳ (𝑣) ∈ 𝐅 𝑛 , 1 , then the result above says that we can identify 𝑇𝑣 with ℳ (𝑇) ℳ (𝑣) . Because the result above allows us to think (via isomorphisms) of each linear map as multiplication on 𝐅 𝑛 , 1 by some matrix 𝐴 , keep in mind that the specific matrix 𝐴 depends not only on the linear map but also on the choice of bases. One of the themes of many of the most important results in later chapters will be the choice of a basis that makes the matrix 𝐴 as simple as possible. In this book, we concentrate on linear maps rather than on matrices. However, sometimes thinking of linear maps as matrices (or thinking of matrices as linear maps) gives important insights that we will find useful. Annotated Entity: ID: 103 Spans: True Boxes: True Text: 90 Chapter 3 Linear Maps Notice that no bases are in sight in the statement of the next result. Although ℳ (𝑇) in the next result depends on a choice of bases of 𝑉 and 𝑊 , the next result shows that the column rank of ℳ (𝑇) is the same for all such choices (because range 𝑇 does not depend on a choice of basis). 3.78 dimension of range 𝑇 equals column rank of ℳ (𝑇) Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then dim range 𝑇 equals the column rank of ℳ (𝑇) . Proof Suppose 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑚 is a basis of 𝑊 . The linear map that takes 𝑤 ∈ 𝑊 to ℳ (𝑤) is an isomorphism from 𝑊 onto the space 𝐅 𝑚 , 1 of 𝑚 -by- 1 column vectors. The restriction of this isomorphism to range 𝑇 [ which equals span (𝑇𝑣 1 , … , 𝑇𝑣 𝑛 ) by Exercise 10 in Section 3B ] is an isomorphism from range 𝑇 onto span ( ℳ (𝑇𝑣 1 ) , … , ℳ (𝑇𝑣 𝑛 )) . For each 𝑘 ∈ {1 , … , 𝑛} , the 𝑚 -by- 1 matrix ℳ (𝑇𝑣 𝑘 ) equals column 𝑘 of ℳ (𝑇) . Thus dim range 𝑇 = the column rank of ℳ (𝑇) , as desired. Change of Basis In Section 3C we defined the matrix ℳ (𝑇 , (𝑣 1 , … , 𝑣 𝑛 ) , (𝑤 1 , … , 𝑤 𝑚 )) of a linear map 𝑇 from 𝑉 to a possibly different vector space 𝑊 , where 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑤 1 , … , 𝑤 𝑚 is a basis of 𝑊 . For linear maps from a vector space to itself, we usually use the same basis for both the domain vector space and the target vector space. When using a single basis in both capacities, we often write the basis only once. In other words, if 𝑇 ∈ ℒ (𝑉) and 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 , then the notation ℳ (𝑇 , (𝑣 1 , … , 𝑣 𝑛 )) is defined by the equation ℳ (𝑇 , (𝑣 1 , … , 𝑣 𝑛 )) = ℳ (𝑇 , (𝑣 1 , … , 𝑣 𝑛 ) , (𝑣 1 , … , 𝑣 𝑛 )). If the basis 𝑣 1 , … , 𝑣 𝑛 is clear from the context, then we can write just ℳ (𝑇) . 3.79 definition: identity matrix, I Suppose 𝑛 is a positive integer. The 𝑛 -by- 𝑛 matrix ⎛⎜⎜⎜⎝ 1 0 ⋱ 0 1 ⎞⎟⎟⎟⎠ with 1 ’s on the diagonal (the entries where the row number equals the column number) and 0 ’s elsewhere is called the identity matrix and is denoted by 𝐼 . Annotated Entity: ID: 104 Spans: True Boxes: True Text: Section 3D Invertibility and Isomorphisms 91 In the definition above, the 0 in the lower left corner of the matrix indicates that all entries below the diagonal are 0 , and the 0 in the upper right corner indicates that all entries above the diagonal are 0 . With respect to each basis of 𝑉 , the matrix of the identity operator 𝐼 ∈ ℒ (𝑉) is the identity matrix 𝐼 . Note that the symbol 𝐼 is used to denote both the identity operator and the identity matrix. The context indicates which meaning of 𝐼 is intended. For example, consider the equation ℳ (𝐼) = 𝐼 ; on the left side 𝐼 denotes the identity operator, and on the right side 𝐼 denotes the identity matrix. If 𝐴 is a square matrix (with entries in 𝐅 , as usual) of the same size as 𝐼 , then 𝐴𝐼 = 𝐼𝐴 = 𝐴 , as you should verify. 3.80 definition: invertible, inverse, 𝐴 −1 A square matrix 𝐴 is called invertible if there is a square matrix 𝐵 of the same size such that 𝐴𝐵 = 𝐵𝐴 = 𝐼 ; we call 𝐵 the inverse of 𝐴 and denote it by 𝐴 −1 . Some mathematicians use the terms nonsingular and singular , which mean the same as invertible and non- invertible. The same proof as used in 3.60 shows that if 𝐴 is an invertible square matrix, then there is a unique matrix 𝐵 such that 𝐴𝐵 = 𝐵𝐴 = 𝐼 (and thus the notation 𝐵 = 𝐴 −1 is justified). If 𝐴 is an invertible matrix, then (𝐴 −1 ) −1 = 𝐴 because 𝐴 −1 𝐴 = 𝐴𝐴 −1 = 𝐼. Also, if 𝐴 and 𝐶 are invertible square matrices of the same size, then 𝐴𝐶 is invertible and (𝐴𝐶) −1 = 𝐶 −1 𝐴 −1 because (𝐴𝐶)(𝐶 −1 𝐴 −1 ) = 𝐴(𝐶𝐶 −1 )𝐴 −1 = 𝐴𝐼𝐴 −1 = 𝐴𝐴 −1 = 𝐼 , and similarly (𝐶 −1 𝐴 −1 )(𝐴𝐶) = 𝐼 . The next result holds because we defined matrix multiplication to make it true—see 3.43 and the material preceding it. Now we are just being more explicit about the bases involved. 3.81 matrix of product of linear maps Suppose 𝑇 ∈ ℒ (𝑈 , 𝑉) and 𝑆 ∈ ℒ (𝑉 , 𝑊) . If 𝑢 1 , … , 𝑢 𝑚 is a basis of 𝑈 , 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 , and 𝑤 1 , … , 𝑤 𝑝 is a basis of 𝑊 , then ℳ (𝑆𝑇 , (𝑢 1 , … , 𝑢 𝑚 ) , (𝑤 1 , … , 𝑤 𝑝 )) = ℳ (𝑆 , (𝑣 1 , … , 𝑣 𝑛 ) , (𝑤 1 , … , 𝑤 𝑝 )) ℳ (𝑇 , (𝑢 1 , … , 𝑢 𝑚 ) , (𝑣 1 , … , 𝑣 𝑛 )). Annotated Entity: ID: 105 Spans: True Boxes: True Text: 92 Chapter 3 Linear Maps The next result deals with the matrix of the identity operator 𝐼 with respect to two different bases. Note that the 𝑘 th column of ℳ (𝐼 , (𝑢 1 , … , 𝑢 𝑛 ) , (𝑣 1 , … , 𝑣 𝑛 )) consists of the scalars needed to write 𝑢 𝑘 as a linear combination of the basis 𝑣 1 , … , 𝑣 𝑛 . In the statement of the next result, 𝐼 denotes the identity operator from 𝑉 to 𝑉 . In the proof, 𝐼 also denotes the 𝑛 -by- 𝑛 identity matrix. 3.82 matrix of identity operator with respect to two bases Suppose that 𝑢 1 , … , 𝑢 𝑛 and 𝑣 1 , … , 𝑣 𝑛 are bases of 𝑉 . Then the matrices ℳ (𝐼 , (𝑢 1 , … , 𝑢 𝑛 ) , (𝑣 1 , … , 𝑣 𝑛 )) and ℳ (𝐼 , (𝑣 1 , … , 𝑣 𝑛 ) , (𝑢 1 , … , 𝑢 𝑛 )) are invertible, and each is the inverse of the other. Proof In 3.81, replace 𝑤 𝑘 with 𝑢 𝑘 , and replace 𝑆 and 𝑇 with 𝐼 , getting 𝐼 = ℳ (𝐼 , (𝑣 1 , … , 𝑣 𝑛 ) , (𝑢 1 , … , 𝑢 𝑛 )) ℳ (𝐼 , (𝑢 1 , … , 𝑢 𝑛 ) , (𝑣 1 , … , 𝑣 𝑛 )). Now interchange the roles of the 𝑢 ’s and 𝑣 ’s, getting 𝐼 = ℳ (𝐼 , (𝑢 1 , … , 𝑢 𝑛 ) , (𝑣 1 , … , 𝑣 𝑛 )) ℳ (𝐼 , (𝑣 1 , … , 𝑣 𝑛 ) , (𝑢 1 , … , 𝑢 𝑛 )). These two equations above give the desired result. 3.83 example: matrix of identity operator on 𝐅 2 with respect to two bases Consider the bases (4 , 2) , (5 , 3) and (1 , 0) , (0 , 1) of 𝐅 2 . Because 𝐼(4 , 2) = 4(1 , 0) + 2(0 , 1) and 𝐼(5 , 3) = 5(1 , 0) + 3(0 , 1) , we have ℳ (𝐼 , ((4 , 2) , (5 , 3)) , ((1 , 0) , (0 , 1))) = ( 4 5 2 3 ). The inverse of the matrix above is ⎛⎜⎝ 32 − 52 −1 2 ⎞⎟⎠ , as you should verify. Thus 3.82 implies that ℳ (𝐼 , ((1 , 0) , (0 , 1)) , ((4 , 2) , (5 , 3))) = ⎛⎜⎝ 32 − 52 −1 2 ⎞⎟⎠. Our next result shows how the matrix of 𝑇 changes when we change bases. In the next result, we have two different bases of 𝑉 , each of which is used as a basis for the domain space and as a basis for the target space. Recall our shorthand notation that allows us to display a basis only once when it is used in both capacities: ℳ (𝑇 , (𝑢 1 , … , 𝑢 𝑛 )) = ℳ (𝑇 , (𝑢 1 , … , 𝑢 𝑛 ) , (𝑢 1 , … , 𝑢 𝑛 )). Annotated Entity: ID: 106 Spans: True Boxes: True Text: Section 3D Invertibility and Isomorphisms 93 3.84 change-of-basis formula Suppose 𝑇 ∈ ℒ (𝑉) . Suppose 𝑢 1 , … , 𝑢 𝑛 and 𝑣 1 , … , 𝑣 𝑛 are bases of 𝑉 . Let 𝐴 = ℳ (𝑇 , (𝑢 1 , … , 𝑢 𝑛 )) and 𝐵 = ℳ (𝑇 , (𝑣 1 , … , 𝑣 𝑛 )) and 𝐶 = ℳ (𝐼 , (𝑢 1 , … , 𝑢 𝑛 ) , (𝑣 1 , … , 𝑣 𝑛 )) . Then 𝐴 = 𝐶 −1 𝐵𝐶. Proof In 3.81, replace 𝑤 𝑘 with 𝑢 𝑘 and replace 𝑆 with 𝐼 , getting 3.85 𝐴 = 𝐶 −1 ℳ (𝑇 , (𝑢 1 , … , 𝑢 𝑛 ) , (𝑣 1 , … , 𝑣 𝑛 )) , where we have used 3.82. Again use 3.81, this time replacing 𝑤 𝑘 with 𝑣 𝑘 . Also replace 𝑇 with 𝐼 and replace 𝑆 with 𝑇 , getting ℳ (𝑇 , (𝑢 1 , … , 𝑢 𝑛 ) , (𝑣 1 , … , 𝑣 𝑛 )) = 𝐵𝐶. Substituting the equation above into 3.85 gives the equation 𝐴 = 𝐶 −1 𝐵𝐶 . The proof of the next result is left as an exercise. 3.86 matrix of inverse equals inverse of matrix Suppose that 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝑇 ∈ ℒ (𝑉) is invertible. Then ℳ (𝑇 −1 ) = ( ℳ (𝑇)) −1 , where both matrices are with respect to the basis 𝑣 1 , … , 𝑣 𝑛 . Exercises 3D 1 Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) is invertible. Show that 𝑇 −1 is invertible and (𝑇 −1 ) −1 = 𝑇. 2 Suppose 𝑇 ∈ ℒ (𝑈 , 𝑉) and 𝑆 ∈ ℒ (𝑉 , 𝑊) are both invertible linear maps. Prove that 𝑆𝑇 ∈ ℒ (𝑈 , 𝑊) is invertible and that (𝑆𝑇) −1 = 𝑇 −1 𝑆 −1 . 3 Suppose 𝑉 is finite-dimensional and 𝑇 ∈ ℒ (𝑉) . Prove that the following are equivalent. (a) 𝑇 is invertible. (b) 𝑇𝑣 1 , … , 𝑇𝑣 𝑛 is a basis of 𝑉 for every basis 𝑣 1 , … , 𝑣 𝑛 of 𝑉 . (c) 𝑇𝑣 1 , … , 𝑇𝑣 𝑛 is a basis of 𝑉 for some basis 𝑣 1 , … , 𝑣 𝑛 of 𝑉 . 4 Suppose 𝑉 is finite-dimensional and dim 𝑉 > 1 . Prove that the set of noninvertible linear maps from 𝑉 to itself is not a subspace of ℒ (𝑉) . Annotated Entity: ID: 107 Spans: True Boxes: True Text: 94 Chapter 3 Linear Maps 5 Suppose 𝑉 is finite-dimensional, 𝑈 is a subspace of 𝑉 , and 𝑆 ∈ ℒ (𝑈 , 𝑉) . Prove that there exists an invertible linear map 𝑇 from 𝑉 to itself such that 𝑇𝑢 = 𝑆𝑢 for every 𝑢 ∈ 𝑈 if and only if 𝑆 is injective. 6 Suppose that 𝑊 is finite-dimensional and 𝑆 , 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that null 𝑆 = null 𝑇 if and only if there exists an invertible 𝐸 ∈ ℒ (𝑊) such that 𝑆 = 𝐸𝑇 . 7 Suppose that 𝑉 is finite-dimensional and 𝑆 , 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that range 𝑆 = range 𝑇 if and only if there exists an invertible 𝐸 ∈ ℒ (𝑉) such that 𝑆 = 𝑇𝐸 . 8 Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑆 , 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that there exist invertible 𝐸 1 ∈ ℒ (𝑉) and 𝐸 2 ∈ ℒ (𝑊) such that 𝑆 = 𝐸 2 𝑇𝐸 1 if and only if dim null 𝑆 = dim null 𝑇 . 9 Suppose 𝑉 is finite-dimensional and 𝑇 ∶ 𝑉 → 𝑊 is a surjective linear map of 𝑉 onto 𝑊 . Prove that there is a subspace 𝑈 of 𝑉 such that 𝑇| 𝑈 is an isomorphism of 𝑈 onto 𝑊 . Here 𝑇| 𝑈 means the function 𝑇 restricted to 𝑈 . Thus 𝑇| 𝑈 is the function whose domain is 𝑈 , with 𝑇| 𝑈 defined by 𝑇| 𝑈 (𝑢) = 𝑇𝑢 for every 𝑢 ∈ 𝑈 . 10 Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑈 is a subspace of 𝑉 . Let ℰ = {𝑇 ∈ ℒ (𝑉 , 𝑊) ∶ 𝑈 ⊆ null 𝑇}. (a) Show that ℰ is a subspace of ℒ (𝑉 , 𝑊) . (b) Find a formula for dim ℰ in terms of dim 𝑉 , dim 𝑊 , and dim 𝑈 . Hint: Define Φ ∶ ℒ (𝑉 , 𝑊) → ℒ (𝑈 , 𝑊) by Φ(𝑇) = 𝑇| 𝑈 . What is null Φ ? What is range Φ ? 11 Suppose 𝑉 is finite-dimensional and 𝑆 , 𝑇 ∈ ℒ (𝑉) . Prove that 𝑆𝑇 is invertible ⟺ 𝑆 and 𝑇 are invertible . 12 Suppose 𝑉 is finite-dimensional and 𝑆 , 𝑇 , 𝑈 ∈ ℒ (𝑉) and 𝑆𝑇𝑈 = 𝐼 . Show that 𝑇 is invertible and that 𝑇 −1 = 𝑈𝑆 . 13 Show that the result in Exercise 12 can fail without the hypothesis that 𝑉 is finite-dimensional. 14 Prove or give a counterexample: If 𝑉 is a finite-dimensional vector space and 𝑅 , 𝑆 , 𝑇 ∈ ℒ (𝑉) are such that 𝑅𝑆𝑇 is surjective, then 𝑆 is injective. 15 Suppose 𝑇 ∈ ℒ (𝑉) and 𝑣 1 , … , 𝑣 𝑚 is a list in 𝑉 such that 𝑇𝑣 1 , … , 𝑇𝑣 𝑚 spans 𝑉 . Prove that 𝑣 1 , … , 𝑣 𝑚 spans 𝑉 . 16 Prove that every linear map from 𝐅 𝑛 , 1 to 𝐅 𝑚 , 1 is given by a matrix multipli- cation. In other words, prove that if 𝑇 ∈ ℒ (𝐅 𝑛 , 1 , 𝐅 𝑚 , 1 ) , then there exists an 𝑚 -by- 𝑛 matrix 𝐴 such that 𝑇𝑥 = 𝐴𝑥 for every 𝑥 ∈ 𝐅 𝑛 , 1 . Annotated Entity: ID: 108 Spans: True Boxes: True Text: Section 3D Invertibility and Isomorphisms 95 17 Suppose 𝑉 is finite-dimensional and 𝑆 ∈ ℒ (𝑉) . Define 𝒜 ∈ ℒ ( ℒ (𝑉)) by 𝒜 (𝑇) = 𝑆𝑇 for 𝑇 ∈ ℒ (𝑉) . (a) Show that dim null 𝒜 = ( dim 𝑉)( dim null 𝑆) . (b) Show that dim range 𝒜 = ( dim 𝑉)( dim range 𝑆) . 18 Show that 𝑉 and ℒ (𝐅 , 𝑉) are isomorphic vector spaces. 19 Suppose 𝑉 is finite-dimensional and 𝑇 ∈ ℒ (𝑉) . Prove that 𝑇 has the same matrix with respect to every basis of 𝑉 if and only if 𝑇 is a scalar multiple of the identity operator. 20 Suppose 𝑞 ∈ 𝒫 (𝐑) . Prove that there exists a polynomial 𝑝 ∈ 𝒫 (𝐑) such that 𝑞(𝑥) = (𝑥 2 + 𝑥)𝑝 ″ (𝑥) + 2𝑥𝑝 ′ (𝑥) + 𝑝(3) for all 𝑥 ∈ 𝐑 . 21 Suppose 𝑛 is a positive integer and 𝐴 𝑗 , 𝑘 ∈ 𝐅 for all 𝑗 , 𝑘 = 1 , … , 𝑛 . Prove that the following are equivalent (note that in both parts below, the number of equations equals the number of variables). (a) The trivial solution 𝑥 1 = ⋯ = 𝑥 𝑛 = 0 is the only solution to the homogeneous system of equations 𝑛 ∑ 𝑘=1 𝐴 1 , 𝑘 𝑥 𝑘 = 0 ⋮ 𝑛 ∑ 𝑘=1 𝐴 𝑛 , 𝑘 𝑥 𝑘 = 0. (b) For every 𝑐 1 , … , 𝑐 𝑛 ∈ 𝐅 , there exists a solution to the system of equations 𝑛 ∑ 𝑘=1 𝐴 1 , 𝑘 𝑥 𝑘 = 𝑐 1 ⋮ 𝑛 ∑ 𝑘=1 𝐴 𝑛 , 𝑘 𝑥 𝑘 = 𝑐 𝑛 . 22 Suppose 𝑇 ∈ ℒ (𝑉) and 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 . Prove that ℳ (𝑇 , (𝑣 1 , … , 𝑣 𝑛 )) is invertible ⟺ 𝑇 is invertible . 23 Suppose that 𝑢 1 , … , 𝑢 𝑛 and 𝑣 1 , … , 𝑣 𝑛 are bases of 𝑉 . Let 𝑇 ∈ ℒ (𝑉) be such that 𝑇𝑣 𝑘 = 𝑢 𝑘 for each 𝑘 = 1 , … , 𝑛 . Prove that ℳ (𝑇 , (𝑣 1 , … , 𝑣 𝑛 )) = ℳ (𝐼 , (𝑢 1 , … , 𝑢 𝑛 ) , (𝑣 1 , … , 𝑣 𝑛 )). 24 Suppose 𝐴 and 𝐵 are square matrices of the same size and 𝐴𝐵 = 𝐼 . Prove that 𝐵𝐴 = 𝐼 . Annotated Entity: ID: 109 Spans: True Boxes: True Text: 96 Chapter 3 Linear Maps 3E Products and Quotients of Vector Spaces Products of Vector Spaces As usual when dealing with more than one vector space, all vector spaces in use should be over the same field. 3.87 definition: product of vector spaces Suppose 𝑉 1 , … , 𝑉 𝑚 are vector spaces over 𝐅 . • The product 𝑉 1 × ⋯ × 𝑉 𝑚 is defined by 𝑉 1 × ⋯ × 𝑉 𝑚 = {(𝑣 1 , … , 𝑣 𝑚 ) ∶ 𝑣 1 ∈ 𝑉 1 , … , 𝑣 𝑚 ∈ 𝑉 𝑚 }. • Addition on 𝑉 1 × ⋯ × 𝑉 𝑚 is defined by (𝑢 1 , … , 𝑢 𝑚 ) + (𝑣 1 , … , 𝑣 𝑚 ) = (𝑢 1 + 𝑣 1 , … , 𝑢 𝑚 + 𝑣 𝑚 ). • Scalar multiplication on 𝑉 1 × ⋯ × 𝑉 𝑚 is defined by 𝜆(𝑣 1 , … , 𝑣 𝑚 ) = (𝜆𝑣 1 , … , 𝜆𝑣 𝑚 ). 3.88 example: product of the vector spaces 𝒫 5 (𝐑) and 𝐑 3 Elements of 𝒫 5 (𝐑) × 𝐑 3 are lists of length two, with the first item in the list an element of 𝒫 5 (𝐑) and the second item in the list an element of 𝐑 3 . For example, (5 − 6𝑥 + 4𝑥 2 , (3 , 8 , 7)) and (𝑥 + 9𝑥 5 , (2 , 2 , 2)) are elements of 𝒫 5 (𝐑) × 𝐑 3 . Their sum is defined by (5 − 6𝑥 + 4𝑥 2 , (3 , 8 , 7)) + (𝑥 + 9𝑥 5 , (2 , 2 , 2)) = (5 − 5𝑥 + 4𝑥 2 + 9𝑥 5 , (5 , 10 , 9)). Also, 2(5 − 6𝑥 + 4𝑥 2 , (3 , 8 , 7)) = (10 − 12𝑥 + 8𝑥 2 , (6 , 16 , 14)) . The next result should be interpreted to mean that the product of vector spaces is a vector space with the operations of addition and scalar multiplication as defined by 3.87. 3.89 product of vector spaces is a vector space Suppose 𝑉 1 , … , 𝑉 𝑚 are vector spaces over 𝐅 . Then 𝑉 1 × ⋯ × 𝑉 𝑚 is a vector space over 𝐅 . The proof of the result above is left to the reader. Note that the additive identity of 𝑉 1 × ⋯ × 𝑉 𝑚 is (0 , … , 0) , where the 0 in the 𝑘 th slot is the additive identity of 𝑉 𝑘 . The additive inverse of (𝑣 1 , … , 𝑣 𝑚 ) ∈ 𝑉 1 × ⋯ × 𝑉 𝑚 is (−𝑣 1 , … , −𝑣 𝑚 ) . Annotated Entity: ID: 110 Spans: True Boxes: True Text: Section 3E Products and Quotients of Vector Spaces 97 3.90 example: 𝐑 2 × 𝐑 3 ≠ 𝐑 5 but 𝐑 2 × 𝐑 3 is isomorphic to 𝐑 5 Elements of the vector space 𝐑 2 × 𝐑 3 are lists ((𝑥 1 , 𝑥 2 ) , (𝑥 3 , 𝑥 4 , 𝑥 5 )) , where 𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 ∈ 𝐑 . Elements of 𝐑 5 are lists (𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 ) , where 𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 ∈ 𝐑 . Although elements of 𝐑 2 × 𝐑 3 and 𝐑 5 look similar, they are not the same kind of object. Elements of 𝐑 2 × 𝐑 3 are lists of length two (with the first item itself a list of length two and the second item a list of length three), and elements of 𝐑 5 are lists of length five. Thus 𝐑 2 × 𝐑 3 does not equal 𝐑 5 . This isomorphism is so natural that we should think of it as a relabel- ing. Some people informally say that 𝐑 2 ×𝐑 3 equals 𝐑 5 , which is not techni- cally correct but which captures the spirit of identification via relabeling. The linear map ((𝑥 1 , 𝑥 2 ) , (𝑥 3 , 𝑥 4 , 𝑥 5 )) ↦ (𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 ) is an isomorphism of the vector space 𝐑 2 × 𝐑 3 onto the vector space 𝐑 5 . Thus these two vector spaces are isomorphic, al- though they are not equal. The next example illustrates the idea that we will use in the proof of 3.92. 3.91 example: a basis of 𝒫 2 (𝐑) × 𝐑 2 Consider this list of length five of elements of 𝒫 2 (𝐑) × 𝐑 2 : (1 , (0 , 0)) , (𝑥 , (0 , 0)) , (𝑥 2 , (0 , 0)) , (0 , (1 , 0)) , (0 , (0 , 1)). The list above is linearly independent and it spans 𝒫 2 (𝐑) × 𝐑 2 . Thus it is a basis of 𝒫 2 (𝐑) × 𝐑 2 . 3.92 dimension of a product is the sum of dimensions Suppose 𝑉 1 , … , 𝑉 𝑚 are finite-dimensional vector spaces. Then 𝑉 1 × ⋯ × 𝑉 𝑚 is finite-dimensional and dim (𝑉 1 × ⋯ × 𝑉 𝑚 ) = dim 𝑉 1 + ⋯ + dim 𝑉 𝑚 . Proof Choose a basis of each 𝑉 𝑘 . For each basis vector of each 𝑉 𝑘 , consider the element of 𝑉 1 ×⋯×𝑉 𝑚 that equals the basis vector in the 𝑘 th slot and 0 in the other slots. The list of all such vectors is linearly independent and spans 𝑉 1 × ⋯ × 𝑉 𝑚 . Thus it is a basis of 𝑉 1 × ⋯ × 𝑉 𝑚 . The length of this basis is dim 𝑉 1 + ⋯ + dim 𝑉 𝑚 , as desired. Annotated Entity: ID: 111 Spans: True Boxes: True Text: 98 Chapter 3 Linear Maps In the next result, the map Γ is surjective by the definition of 𝑉 1 + ⋯ + 𝑉 𝑚 . Thus the last word in the result below could be changed from “injective” to “invertible”. 3.93 products and direct sums Suppose that 𝑉 1 , … , 𝑉 𝑚 are subspaces of 𝑉 . Define a linear map Γ ∶ 𝑉 1 × ⋯ × 𝑉 𝑚 → 𝑉 1 + ⋯ + 𝑉 𝑚 by Γ(𝑣 1 , … , 𝑣 𝑚 ) = 𝑣 1 + ⋯ + 𝑣 𝑚 . Then 𝑉 1 + ⋯ + 𝑉 𝑚 is a direct sum if and only if Γ is injective. Proof By 3.15, Γ is injective if and only if the only way to write 0 as a sum 𝑣 1 + ⋯ + 𝑣 𝑚 , where each 𝑣 𝑘 is in 𝑉 𝑘 , is by taking each 𝑣 𝑘 equal to 0 . Thus 1.45 shows that Γ is injective if and only if 𝑉 1 + ⋯ + 𝑉 𝑚 is a direct sum, as desired. 3.94 a sum is a direct sum if and only if dimensions add up Suppose 𝑉 is finite-dimensional and 𝑉 1 , … , 𝑉 𝑚 are subspaces of 𝑉 . Then 𝑉 1 + ⋯ + 𝑉 𝑚 is a direct sum if and only if dim (𝑉 1 + ⋯ + 𝑉 𝑚 ) = dim 𝑉 1 + ⋯ + dim 𝑉 𝑚 . Proof The map Γ in 3.93 is surjective. Thus by the fundamental theorem of linear maps (3.21), Γ is injective if and only if dim (𝑉 1 + ⋯ + 𝑉 𝑚 ) = dim (𝑉 1 × ⋯ × 𝑉 𝑚 ). Combining 3.93 and 3.92 now shows that 𝑉 1 + ⋯ + 𝑉 𝑚 is a direct sum if and only if dim (𝑉 1 + ⋯ + 𝑉 𝑚 ) = dim 𝑉 1 + ⋯ + dim 𝑉 𝑚 , as desired. In the special case 𝑚 = 2 , an alternative proof that 𝑉 1 + 𝑉 2 is a direct sum if and only if dim (𝑉 1 + 𝑉 2 ) = dim 𝑉 1 + dim 𝑉 2 can be obtained by combining 1.46 and 2.43. Quotient Spaces We begin our approach to quotient spaces by defining the sum of a vector and a subset. 3.95 notation: 𝑣 + 𝑈 Suppose 𝑣 ∈ 𝑉 and 𝑈 ⊆ 𝑉 . Then 𝑣 + 𝑈 is the subset of 𝑉 defined by 𝑣 + 𝑈 = {𝑣 + 𝑢 ∶ 𝑢 ∈ 𝑈}. Annotated Entity: ID: 112 Spans: True Boxes: True Text: Section 3E Products and Quotients of Vector Spaces 99 3.96 example: sum of a vector and a one-dimensional subspace of 𝐑 2 (17 , 20) + 𝑈 is parallel to the subspace 𝑈 . Suppose 𝑈 = {(𝑥 , 2𝑥) ∈ 𝐑 2 ∶ 𝑥 ∈ 𝐑}. Hence 𝑈 is the line in 𝐑 2 through the origin with slope 2 . Thus (17 , 20) + 𝑈 is the line in 𝐑 2 that contains the point (17 , 20) and has slope 2 . Because (10 , 20) ∈ 𝑈 and (17 , 20) ∈ (17 , 20) + 𝑈 , we see that (17 , 20) + 𝑈 is obtained by moving 𝑈 to the right by 7 units. 3.97 definition: translate For 𝑣 ∈ 𝑉 and 𝑈 a subset of 𝑉 , the set 𝑣 + 𝑈 is said to be a translate of 𝑈 . 3.98 example: translates • If 𝑈 is the line in 𝐑 2 defined by 𝑈 = {(𝑥 , 2𝑥) ∈ 𝐑 2 ∶ 𝑥 ∈ 𝐑} , then all lines in 𝐑 2 with slope 2 are translates of 𝑈 . See Example 3.96 above for a drawing of 𝑈 and one of its translates. • More generally, if 𝑈 is a line in 𝐑 2 , then the set of all translates of 𝑈 is the set of all lines in 𝐑 2 that are parallel to 𝑈 . • If 𝑈 = {(𝑥 , 𝑦 , 0) ∈ 𝐑 3 ∶ 𝑥 , 𝑦 ∈ 𝐑} , then the translates of 𝑈 are the planes in 𝐑 3 that are parallel to the 𝑥𝑦 -plane 𝑈 . • More generally, if 𝑈 is a plane in 𝐑 3 , then the set of all translates of 𝑈 is the set of all planes in 𝐑 3 that are parallel to 𝑈 (see, for example, Exercise 7). 3.99 definition: quotient space, 𝑉/𝑈 Suppose 𝑈 is a subspace of 𝑉 . Then the quotient space 𝑉/𝑈 is the set of all translates of 𝑈 . Thus 𝑉/𝑈 = {𝑣 + 𝑈 ∶ 𝑣 ∈ 𝑉}. Annotated Entity: ID: 113 Spans: True Boxes: True Text: 100 Chapter 3 Linear Maps 3.100 example: quotient spaces • If 𝑈 = {(𝑥 , 2𝑥) ∈ 𝐑 2 ∶ 𝑥 ∈ 𝐑} , then 𝐑 2 /𝑈 is the set of all lines in 𝐑 2 that have slope 2 . • If 𝑈 is a line in 𝐑 3 containing the origin, then 𝐑 3 /𝑈 is the set of all lines in 𝐑 3 parallel to 𝑈 . • If 𝑈 is a plane in 𝐑 3 containing the origin, then 𝐑 3 /𝑈 is the set of all planes in 𝐑 3 parallel to 𝑈 . Our next goal is to make 𝑉/𝑈 into a vector space. To do this, we will need the next result. 3.101 two translates of a subspace are equal or disjoint Suppose 𝑈 is a subspace of 𝑉 and 𝑣 , 𝑤 ∈ 𝑉 . Then 𝑣 − 𝑤 ∈ 𝑈 ⟺ 𝑣 + 𝑈 = 𝑤 + 𝑈 ⟺ (𝑣 + 𝑈) ∩ (𝑤 + 𝑈) ≠ ∅. Proof First suppose 𝑣 − 𝑤 ∈ 𝑈 . If 𝑢 ∈ 𝑈 , then 𝑣 + 𝑢 = 𝑤 + ((𝑣 − 𝑤) + 𝑢) ∈ 𝑤 + 𝑈. Thus 𝑣 + 𝑈 ⊆ 𝑤 + 𝑈 . Similarly, 𝑤 + 𝑈 ⊆ 𝑣 + 𝑈 . Thus 𝑣 + 𝑈 = 𝑤 + 𝑈 , completing the proof that 𝑣 − 𝑤 ∈ 𝑈 implies 𝑣 + 𝑈 = 𝑤 + 𝑈 . The equation 𝑣 + 𝑈 = 𝑤 + 𝑈 implies that (𝑣 + 𝑈) ∩ (𝑤 + 𝑈) ≠ ∅ . Now suppose (𝑣 + 𝑈) ∩ (𝑤 + 𝑈) ≠ ∅ . Thus there exist 𝑢 1 , 𝑢 2 ∈ 𝑈 such that 𝑣 + 𝑢 1 = 𝑤 + 𝑢 2 . Thus 𝑣 − 𝑤 = 𝑢 2 − 𝑢 1 . Hence 𝑣 − 𝑤 ∈ 𝑈 , showing that (𝑣 + 𝑈) ∩ (𝑤 + 𝑈) ≠ ∅ implies 𝑣 − 𝑤 ∈ 𝑈 , which completes the proof. Now we can define addition and scalar multiplication on 𝑉/𝑈 . 3.102 definition: addition and scalar multiplication on 𝑉/𝑈 Suppose 𝑈 is a subspace of 𝑉 . Then addition and scalar multiplication are defined on 𝑉/𝑈 by (𝑣 + 𝑈) + (𝑤 + 𝑈) = (𝑣 + 𝑤) + 𝑈 𝜆(𝑣 + 𝑈) = (𝜆𝑣) + 𝑈 for all 𝑣 , 𝑤 ∈ 𝑉 and all 𝜆 ∈ 𝐅 . As part of the proof of the next result, we will show that the definitions above make sense. Annotated Entity: ID: 114 Spans: True Boxes: True Text: Section 3E Products and Quotients of Vector Spaces 101 3.103 quotient space is a vector space Suppose 𝑈 is a subspace of 𝑉 . Then 𝑉/𝑈 , with the operations of addition and scalar multiplication as defined above, is a vector space. Proof The potential problem with the definitions above of addition and scalar multiplication on 𝑉/𝑈 is that the representation of a translate of 𝑈 is not unique. Specifically, suppose 𝑣 1 , 𝑣 2 , 𝑤 1 , 𝑤 2 ∈ 𝑉 are such that 𝑣 1 + 𝑈 = 𝑣 2 + 𝑈 and 𝑤 1 + 𝑈 = 𝑤 2 + 𝑈. To show that the definition of addition on 𝑉/𝑈 given above makes sense, we must show that (𝑣 1 + 𝑤 1 ) + 𝑈 = (𝑣 2 + 𝑤 2 ) + 𝑈 . By 3.101, we have 𝑣 1 − 𝑣 2 ∈ 𝑈 and 𝑤 1 − 𝑤 2 ∈ 𝑈. Because 𝑈 is a subspace of 𝑉 and thus is closed under addition, this implies that (𝑣 1 − 𝑣 2 ) + (𝑤 1 − 𝑤 2 ) ∈ 𝑈 . Thus (𝑣 1 + 𝑤 1 ) − (𝑣 2 + 𝑤 2 ) ∈ 𝑈 . Using 3.101 again, we see that (𝑣 1 + 𝑤 1 ) + 𝑈 = (𝑣 2 + 𝑤 2 ) + 𝑈 , as desired. Thus the definition of addition on 𝑉/𝑈 makes sense. Similarly, suppose 𝜆 ∈ 𝐅 . We are still assuming that 𝑣 1 + 𝑈 = 𝑣 2 + 𝑈 . Because 𝑈 is a subspace of 𝑉 and thus is closed under scalar multiplication, we have 𝜆(𝑣 1 − 𝑣 2 ) ∈ 𝑈 . Thus 𝜆𝑣 1 − 𝜆𝑣 2 ∈ 𝑈 . Hence 3.101 implies that (𝜆𝑣 1 ) + 𝑈 = (𝜆𝑣 2 ) + 𝑈. Thus the definition of scalar multiplication on 𝑉/𝑈 makes sense. Now that addition and scalar multiplication have been defined on 𝑉/𝑈 , the verification that these operations make 𝑉/𝑈 into a vector space is straightforward and is left to the reader. Note that the additive identity of 𝑉/𝑈 is 0 + 𝑈 (which equals 𝑈 ) and that the additive inverse of 𝑣 + 𝑈 is (−𝑣) + 𝑈 . The next concept will lead to a computation of the dimension of 𝑉/𝑈 . 3.104 definition: quotient map, 𝜋 Suppose 𝑈 is a subspace of 𝑉 . The quotient map 𝜋 ∶ 𝑉 → 𝑉/𝑈 is the linear map defined by 𝜋(𝑣) = 𝑣 + 𝑈 for each 𝑣 ∈ 𝑉 . The reader should verify that 𝜋 is indeed a linear map. Although 𝜋 depends on 𝑈 as well as 𝑉 , these spaces are left out of the notation because they should be clear from the context. Annotated Entity: ID: 115 Spans: True Boxes: True Text: 102 Chapter 3 Linear Maps 3.105 dimension of quotient space Suppose 𝑉 is finite-dimensional and 𝑈 is a subspace of 𝑉 . Then dim 𝑉/𝑈 = dim 𝑉 − dim 𝑈. Proof Let 𝜋 denote the quotient map from 𝑉 to 𝑉/𝑈 . If 𝑣 ∈ 𝑉 , then 𝑣 + 𝑈 = 0 + 𝑈 if and only if 𝑣 ∈ 𝑈 (by 3.101), which implies that null 𝜋 = 𝑈 . The definition of 𝜋 implies range 𝜋 = 𝑉/𝑈 . The fundamental theorem of linear maps (3.21) now implies dim 𝑉 = dim 𝑈 + dim 𝑉/𝑈 , which gives the desired result. Each linear map 𝑇 on 𝑉 induces a linear map ̃𝑇 on 𝑉/( null 𝑇) , which we now define. 3.106 notation: ̃𝑇 Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) . Define ̃𝑇 ∶ 𝑉/( null 𝑇) → 𝑊 by ̃𝑇(𝑣 + null 𝑇) = 𝑇𝑣. To show that the definition of ̃𝑇 makes sense, suppose 𝑢 , 𝑣 ∈ 𝑉 are such that 𝑢 + null 𝑇 = 𝑣 + null 𝑇 . By 3.101, we have 𝑢 − 𝑣 ∈ null 𝑇 . Thus 𝑇(𝑢 − 𝑣) = 0 . Hence 𝑇𝑢 = 𝑇𝑣 . Thus the definition of ̃𝑇 indeed makes sense. The routine verification that ̃𝑇 is a linear map from 𝑉/( null 𝑇) to 𝑊 is left to the reader. The next result shows that we can think of ̃𝑇 as a modified version of 𝑇 , with a domain that produces a one-to-one map. 3.107 null space and range of ̃ 𝑇 Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then (a) ̃𝑇 ∘ 𝜋 = 𝑇 , where 𝜋 is the quotient map of 𝑉 onto 𝑉/( null 𝑇) ; (b) ̃𝑇 is injective; (c) range ̃𝑇 = range 𝑇 ; (d) 𝑉/( null 𝑇) and range 𝑇 are isomorphic vector spaces. Proof (a) If 𝑣 ∈ 𝑉 , then ( ̃ 𝑇 ∘ 𝜋)(𝑣) = ̃ 𝑇(𝜋(𝑣)) = ̃ 𝑇(𝑣 + null 𝑇) = 𝑇𝑣 , as desired. (b) Suppose 𝑣 ∈ 𝑉 and ̃𝑇(𝑣 + null 𝑇) = 0 . Then 𝑇𝑣 = 0 . Thus 𝑣 ∈ null 𝑇 . Hence 3.101 implies that 𝑣 + null 𝑇 = 0 + null 𝑇 . This implies that null ̃𝑇 = {0 + null 𝑇} . Hence ̃𝑇 is injective, as desired. (c) The definition of ̃𝑇 shows that range ̃𝑇 = range 𝑇 . (d) Now (b) and (c) imply that if we think of ̃𝑇 as mapping into range 𝑇 , then ̃𝑇 is an isomorphism from 𝑉/( null 𝑇) onto range 𝑇 . Annotated Entity: ID: 116 Spans: True Boxes: True Text: Section 3E Products and Quotients of Vector Spaces 103 Exercises 3E 1 Suppose 𝑇 is a function from 𝑉 to 𝑊 . The graph of 𝑇 is the subset of 𝑉× 𝑊 defined by graph of 𝑇 = {(𝑣 , 𝑇𝑣) ∈ 𝑉× 𝑊 ∶ 𝑣 ∈ 𝑉}. Prove that 𝑇 is a linear map if and only if the graph of 𝑇 is a subspace of 𝑉× 𝑊 . Formally, a function 𝑇 from 𝑉 to 𝑊 is a subset 𝑇 of 𝑉× 𝑊 such that for each 𝑣 ∈ 𝑉 , there exists exactly one element (𝑣 , 𝑤) ∈ 𝑇 . In other words, formally a function is what is called above its graph. We do not usually think of functions in this formal manner. However, if we do become formal, then this exercise could be rephrased as follows: Prove that a function 𝑇 from 𝑉 to 𝑊 is a linear map if and only if 𝑇 is a subspace of 𝑉× 𝑊 . 2 Suppose that 𝑉 1 , … , 𝑉 𝑚 are vector spaces such that 𝑉 1 × ⋯ × 𝑉 𝑚 is finite- dimensional. Prove that 𝑉 𝑘 is finite-dimensional for each 𝑘 = 1 , … , 𝑚 . 3 Suppose 𝑉 1 , … , 𝑉 𝑚 are vector spaces. Prove that ℒ (𝑉 1 × ⋯ × 𝑉 𝑚 , 𝑊) and ℒ (𝑉 1 , 𝑊) × ⋯ × ℒ (𝑉 𝑚 , 𝑊) are isomorphic vector spaces. 4 Suppose 𝑊 1 , … , 𝑊 𝑚 are vector spaces. Prove that ℒ (𝑉 , 𝑊 1 × ⋯ × 𝑊 𝑚 ) and ℒ (𝑉 , 𝑊 1 ) × ⋯ × ℒ (𝑉 , 𝑊 𝑚 ) are isomorphic vector spaces. 5 For 𝑚 a positive integer, define 𝑉 𝑚 by 𝑉 𝑚 = 𝑉× ⋯ × 𝑉 ⏟ 𝑚 times . Prove that 𝑉 𝑚 and ℒ ( 𝐅 𝑚 , 𝑉 ) are isomorphic vector spaces. 6 Suppose that 𝑣 , 𝑥 are vectors in 𝑉 and that 𝑈 , 𝑊 are subspaces of 𝑉 such that 𝑣 + 𝑈 = 𝑥 + 𝑊 . Prove that 𝑈 = 𝑊 . 7 Let 𝑈 = {(𝑥 , 𝑦 , 𝑧) ∈ 𝐑 3 ∶ 2𝑥 + 3𝑦 + 5𝑧 = 0} . Suppose 𝐴 ⊆ 𝐑 3 . Prove that 𝐴 is a translate of 𝑈 if and only if there exists 𝑐 ∈ 𝐑 such that 𝐴 = {(𝑥 , 𝑦 , 𝑧) ∈ 𝐑 3 ∶ 2𝑥 + 3𝑦 + 5𝑧 = 𝑐}. 8 (a) Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝑐 ∈ 𝑊 . Prove that {𝑥 ∈ 𝑉 ∶ 𝑇𝑥 = 𝑐} is either the empty set or is a translate of null 𝑇 . (b) Explain why the set of solutions to a system of linear equations such as 3.27 is either the empty set or is a translate of some subspace of 𝐅 𝑛 . 9 Prove that a nonempty subset 𝐴 of 𝑉 is a translate of some subspace of 𝑉 if and only if 𝜆𝑣 + (1 − 𝜆)𝑤 ∈ 𝐴 for all 𝑣 , 𝑤 ∈ 𝐴 and all 𝜆 ∈ 𝐅 . 10 Suppose 𝐴 1 = 𝑣 + 𝑈 1 and 𝐴 2 = 𝑤 + 𝑈 2 for some 𝑣 , 𝑤 ∈ 𝑉 and some subspaces 𝑈 1 , 𝑈 2 of 𝑉 . Prove that the intersection 𝐴 1 ∩ 𝐴 2 is either a translate of some subspace of 𝑉 or is the empty set. Annotated Entity: ID: 117 Spans: True Boxes: True Text: 104 Chapter 3 Linear Maps 11 Suppose 𝑈 = {(𝑥 1 , 𝑥 2 , … ) ∈ 𝐅 ∞ ∶ 𝑥 𝑘 ≠ 0 for only finitely many 𝑘} . (a) Show that 𝑈 is a subspace of 𝐅 ∞ . (b) Prove that 𝐅 ∞ /𝑈 is infinite-dimensional. 12 Suppose 𝑣 1 , … , 𝑣 𝑚 ∈ 𝑉 . Let 𝐴 = {𝜆 1 𝑣 1 + ⋯ + 𝜆 𝑚 𝑣 𝑚 ∶ 𝜆 1 , … , 𝜆 𝑚 ∈ 𝐅 and 𝜆 1 + ⋯ + 𝜆 𝑚 = 1}. (a) Prove that 𝐴 is a translate of some subspace of 𝑉 . (b) Prove that if 𝐵 is a translate of some subspace of 𝑉 and {𝑣 1 , … , 𝑣 𝑚 } ⊆ 𝐵 , then 𝐴 ⊆ 𝐵 . (c) Prove that 𝐴 is a translate of some subspace of 𝑉 of dimension less than 𝑚 . 13 Suppose 𝑈 is a subspace of 𝑉 such that 𝑉/𝑈 is finite-dimensional. Prove that 𝑉 is isomorphic to 𝑈 × (𝑉/𝑈) . 14 Suppose 𝑈 and 𝑊 are subspaces of 𝑉 and 𝑉 = 𝑈 ⊕ 𝑊 . Suppose 𝑤 1 , … , 𝑤 𝑚 is a basis of 𝑊 . Prove that 𝑤 1 + 𝑈 , … , 𝑤 𝑚 + 𝑈 is a basis of 𝑉/𝑈 . 15 Suppose 𝑈 is a subspace of 𝑉 and 𝑣 1 + 𝑈 , … , 𝑣 𝑚 + 𝑈 is a basis of 𝑉/𝑈 and 𝑢 1 , … , 𝑢 𝑛 is a basis of 𝑈 . Prove that 𝑣 1 , … , 𝑣 𝑚 , 𝑢 1 , … , 𝑢 𝑛 is a basis of 𝑉 . 16 Suppose 𝜑 ∈ ℒ (𝑉 , 𝐅) and 𝜑 ≠ 0 . Prove that dim 𝑉/( null 𝜑) = 1 . 17 Suppose 𝑈 is a subspace of 𝑉 such that dim 𝑉/𝑈 = 1 . Prove that there exists 𝜑 ∈ ℒ (𝑉 , 𝐅) such that null 𝜑 = 𝑈 . 18 Suppose that 𝑈 is a subspace of 𝑉 such that 𝑉/𝑈 is finite-dimensional. (a) Show that if 𝑊 is a finite-dimensional subspace of 𝑉 and 𝑉 = 𝑈 + 𝑊 , then dim 𝑊 ≥ dim 𝑉/𝑈 . (b) Prove that there exists a finite-dimensional subspace 𝑊 of 𝑉 such that dim 𝑊 = dim 𝑉/𝑈 and 𝑉 = 𝑈 ⊕ 𝑊 . 19 Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝑈 is a subspace of 𝑉 . Let 𝜋 denote the quotient map from 𝑉 onto 𝑉/𝑈 . Prove that there exists 𝑆 ∈ ℒ (𝑉/𝑈 , 𝑊) such that 𝑇 = 𝑆 ∘ 𝜋 if and only if 𝑈 ⊆ null 𝑇 . Annotated Entity: ID: 118 Spans: True Boxes: True Text: Section 3F Duality 105 3F Duality Dual Space and Dual Map Linear maps into the scalar field 𝐅 play a special role in linear algebra, and thus they get a special name. 3.108 definition: linear functional A linear functional on 𝑉 is a linear map from 𝑉 to 𝐅 . In other words, a linear functional is an element of ℒ (𝑉 , 𝐅) . 3.109 example: linear functionals • Define 𝜑 ∶ 𝐑 3 → 𝐑 by 𝜑(𝑥 , 𝑦 , 𝑧) = 4𝑥 − 5𝑦 + 2𝑧 . Then 𝜑 is a linear functional on 𝐑 3 . • Fix (𝑐 1 , … , 𝑐 𝑛 ) ∈ 𝐅 𝑛 . Define 𝜑 ∶ 𝐅 𝑛 → 𝐅 by 𝜑(𝑥 1 , … , 𝑥 𝑛 ) = 𝑐 1 𝑥 1 + ⋯ + 𝑐 𝑛 𝑥 𝑛 . Then 𝜑 is a linear functional on 𝐅 𝑛 . • Define 𝜑 ∶ 𝒫 (𝐑) → 𝐑 by 𝜑(𝑝) = 3𝑝 ″ (5) + 7𝑝(4). Then 𝜑 is a linear functional on 𝒫 (𝐑) . • Define 𝜑 ∶ 𝒫 (𝐑) → 𝐑 by 𝜑(𝑝) = ∫ 1 0 𝑝 for each 𝑝 ∈ 𝒫 (𝐑) . Then 𝜑 is a linear functional on 𝒫 (𝐑) . The vector space ℒ (𝑉 , 𝐅) also gets a special name and special notation. 3.110 definition: dual space, 𝑉 ′ The dual space of 𝑉 , denoted by 𝑉 ′ , is the vector space of all linear functionals on 𝑉 . In other words, 𝑉 ′ = ℒ (𝑉 , 𝐅) . 3.111 dim 𝑉 ′ = dim 𝑉 Suppose 𝑉 is finite-dimensional. Then 𝑉 ′ is also finite-dimensional and dim 𝑉 ′ = dim 𝑉. Proof By 3.72 we have dim 𝑉 ′ = dim ℒ (𝑉 , 𝐅) = ( dim 𝑉)( dim 𝐅) = dim 𝑉 , as desired. Annotated Entity: ID: 119 Spans: True Boxes: True Text: 106 Chapter 3 Linear Maps In the following definition, the linear map lemma (3.4) implies that each 𝜑 𝑗 is well defined. 3.112 definition: dual basis If 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 , then the dual basis of 𝑣 1 , … , 𝑣 𝑛 is the list 𝜑 1 , … , 𝜑 𝑛 of elements of 𝑉 ′ , where each 𝜑 𝑗 is the linear functional on 𝑉 such that 𝜑 𝑗 (𝑣 𝑘 ) = ⎧{ ⎨{⎩ 1 if 𝑘 = 𝑗 , 0 if 𝑘 ≠ 𝑗. 3.113 example: the dual basis of the standard basis of 𝐅 𝑛 Suppose 𝑛 is a positive integer. For 1 ≤ 𝑗 ≤ 𝑛 , define 𝜑 𝑗 to be the linear functional on 𝐅 𝑛 that selects the 𝑗 th coordinate of a vector in 𝐅 𝑛 . Thus 𝜑 𝑗 (𝑥 1 , … , 𝑥 𝑛 ) = 𝑥 𝑗 for each (𝑥 1 , … , 𝑥 𝑛 ) ∈ 𝐅 𝑛 . Let 𝑒 1 , … , 𝑒 𝑛 be the standard basis of 𝐅 𝑛 . Then 𝜑 𝑗 (𝑒 𝑘 ) = ⎧{ ⎨{⎩ 1 if 𝑘 = 𝑗 , 0 if 𝑘 ≠ 𝑗. Thus 𝜑 1 , … , 𝜑 𝑛 is the dual basis of the standard basis 𝑒 1 , … , 𝑒 𝑛 of 𝐅 𝑛 . The next result shows that the dual basis of a basis of 𝑉 consists of the linear functionals on 𝑉 that give the coefficients for expressing a vector in 𝑉 as a linear combination of the basis vectors. 3.114 dual basis gives coefficients for linear combination Suppose 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝜑 1 , … , 𝜑 𝑛 is the dual basis. Then 𝑣 = 𝜑 1 (𝑣)𝑣 1 + ⋯ + 𝜑 𝑛 (𝑣)𝑣 𝑛 for each 𝑣 ∈ 𝑉 . Proof Suppose 𝑣 ∈ 𝑉 . Then there exist 𝑐 1 , … , 𝑐 𝑛 ∈ 𝐅 such that 3.115 𝑣 = 𝑐 1 𝑣 1 + ⋯ + 𝑐 𝑛 𝑣 𝑛 . If 𝑗 ∈ {1 , … , 𝑛} , then applying 𝜑 𝑗 to both sides of the equation above gives 𝜑 𝑗 (𝑣) = 𝑐 𝑗 . Substituting the values for 𝑐 1 , … , 𝑐 𝑛 given by the equation above into 3.115 shows that 𝑣 = 𝜑 1 (𝑣)𝑣 1 + ⋯ + 𝜑 𝑛 (𝑣)𝑣 𝑛 . Annotated Entity: ID: 120 Spans: True Boxes: True Text: Section 3F Duality 107 The next result shows that the dual basis is indeed a basis of the dual space. Thus the terminology “dual basis” is justified. 3.116 dual basis is a basis of the dual space Suppose 𝑉 is finite-dimensional. Then the dual basis of a basis of 𝑉 is a basis of 𝑉 ′ . Proof Suppose 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 . Let 𝜑 1 , … , 𝜑 𝑛 denote the dual basis. To show that 𝜑 1 , … , 𝜑 𝑛 is a linearly independent list of elements of 𝑉 ′ , suppose 𝑎 1 , … , 𝑎 𝑛 ∈ 𝐅 are such that 3.117 𝑎 1 𝜑 1 + ⋯ + 𝑎 𝑛 𝜑 𝑛 = 0. Now (𝑎 1 𝜑 1 + ⋯ + 𝑎 𝑛 𝜑 𝑛 )(𝑣 𝑘 ) = 𝑎 𝑘 for each 𝑘 = 1 , … , 𝑛 . Thus 3.117 shows that 𝑎 1 = ⋯ = 𝑎 𝑛 = 0 . Hence 𝜑 1 , … , 𝜑 𝑛 is linearly independent. Because 𝜑 1 , … , 𝜑 𝑛 is a linearly independent list in 𝑉 ′ whose length equals dim 𝑉 ′ (by 3.111), we can conclude that 𝜑 1 , … , 𝜑 𝑛 is a basis of 𝑉 ′ (see 2.38). In the definition below, note that if 𝑇 is a linear map from 𝑉 to 𝑊 then 𝑇 ′ is a linear map from 𝑊 ′ to 𝑉 ′ . 3.118 definition: dual map, 𝑇 ′ Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) . The dual map of 𝑇 is the linear map 𝑇 ′ ∈ ℒ (𝑊 ′ , 𝑉 ′ ) defined for each 𝜑 ∈ 𝑊 ′ by 𝑇 ′ (𝜑) = 𝜑 ∘ 𝑇. If 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝜑 ∈ 𝑊 ′ , then 𝑇 ′ (𝜑) is defined above to be the composition of the linear maps 𝜑 and 𝑇 . Thus 𝑇 ′ (𝜑) is indeed a linear map from 𝑉 to 𝐅 ; in other words, 𝑇 ′ (𝜑) ∈ 𝑉 ′ . The following two bullet points show that 𝑇 ′ is a linear map from 𝑊 ′ to 𝑉 ′ . • If 𝜑 , 𝜓 ∈ 𝑊 ′ , then 𝑇 ′ (𝜑 + 𝜓) = (𝜑 + 𝜓) ∘ 𝑇 = 𝜑 ∘ 𝑇 + 𝜓 ∘ 𝑇 = 𝑇 ′ (𝜑) + 𝑇 ′ (𝜓). • If 𝜆 ∈ 𝐅 and 𝜑 ∈ 𝑊 ′ , then 𝑇 ′ (𝜆𝜑) = (𝜆𝜑) ∘ 𝑇 = 𝜆(𝜑 ∘ 𝑇) = 𝜆𝑇 ′ (𝜑). The prime notation appears with two unrelated meanings in the next example: 𝐷 ′ denotes the dual of the linear map 𝐷 , and 𝑝 ′ denotes the derivative of a polynomial 𝑝 . Annotated Entity: ID: 121 Spans: True Boxes: True Text: 108 Chapter 3 Linear Maps 3.119 example: dual map of the differentiation linear map Define 𝐷 ∶ 𝒫 (𝐑) → 𝒫 (𝐑) by 𝐷𝑝 = 𝑝 ′ . • Suppose 𝜑 is the linear functional on 𝒫 (𝐑) defined by 𝜑(𝑝) = 𝑝(3) . Then 𝐷 ′ (𝜑) is the linear functional on 𝒫 (𝐑) given by (𝐷 ′ (𝜑))(𝑝) = (𝜑 ∘ 𝐷)(𝑝) = 𝜑(𝐷𝑝) = 𝜑(𝑝 ′ ) = 𝑝 ′ (3). Thus 𝐷 ′ (𝜑) is the linear functional on 𝒫 (𝐑) taking 𝑝 to 𝑝 ′ (3) . • Suppose 𝜑 is the linear functional on 𝒫 (𝐑) defined by 𝜑(𝑝) = ∫ 10 𝑝 . Then 𝐷 ′ (𝜑) is the linear functional on 𝒫 (𝐑) given by (𝐷 ′ (𝜑))(𝑝) = (𝜑 ∘ 𝐷)(𝑝) = 𝜑(𝐷𝑝) = 𝜑(𝑝 ′ ) = ∫ 1 0 𝑝 ′ = 𝑝(1) − 𝑝(0). Thus 𝐷 ′ (𝜑) is the linear functional on 𝒫 (𝐑) taking 𝑝 to 𝑝(1) − 𝑝(0) . In the next result, (a) and (b) imply that the function that takes 𝑇 to 𝑇 ′ is a linear map from ℒ (𝑉 , 𝑊) to ℒ (𝑊 ′ , 𝑉 ′ ) . In (c) below, note the reversal of order from 𝑆𝑇 on the left to 𝑇 ′ 𝑆 ′ on the right. 3.120 algebraic properties of dual maps Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then (a) (𝑆 + 𝑇) ′ = 𝑆 ′ + 𝑇 ′ for all 𝑆 ∈ ℒ (𝑉 , 𝑊) ; (b) (𝜆𝑇) ′ = 𝜆𝑇 ′ for all 𝜆 ∈ 𝐅 ; (c) (𝑆𝑇) ′ = 𝑇 ′ 𝑆 ′ for all 𝑆 ∈ ℒ (𝑊 , 𝑈) . Proof The proofs of (a) and (b) are left to the reader. To prove (c), suppose 𝜑 ∈ 𝑈 ′ . Then (𝑆𝑇) ′ (𝜑) = 𝜑 ∘ (𝑆𝑇) = (𝜑 ∘ 𝑆) ∘ 𝑇 = 𝑇 ′ (𝜑 ∘ 𝑆) = 𝑇 ′ (𝑆 ′ (𝜑)) = (𝑇 ′ 𝑆 ′ )(𝜑) , Some books use the notation 𝑉 ∗ and 𝑇 ∗ for duality instead of 𝑉 ′ and 𝑇 ′ . However, here we reserve the notation 𝑇 ∗ for the adjoint, which will be intro- duced when we study linear maps on inner product spaces in Chapter 7. where the first, third, and fourth equal- ities above hold because of the defini- tion of the dual map, the second equality holds because composition of functions is associative, and the last equality fol- lows from the definition of composition. The equation above shows that (𝑆𝑇) ′ (𝜑) = (𝑇 ′ 𝑆 ′ )(𝜑) for all 𝜑 ∈ 𝑈 ′ . Thus (𝑆𝑇) ′ = 𝑇 ′ 𝑆 ′ . Annotated Entity: ID: 122 Spans: True Boxes: True Text: Section 3F Duality 109 Null Space and Range of Dual of Linear Map Our goal in this subsection is to describe null 𝑇 ′ and range 𝑇 ′ in terms of range 𝑇 and null 𝑇 . To do this, we will need the next definition. 3.121 definition: annihilator, 𝑈 0 For 𝑈 ⊆ 𝑉 , the annihilator of 𝑈 , denoted by 𝑈 0 , is defined by 𝑈 0 = {𝜑 ∈ 𝑉 ′ ∶ 𝜑(𝑢) = 0 for all 𝑢 ∈ 𝑈}. 3.122 example: element of an annihilator Suppose 𝑈 is the subspace of 𝒫 (𝐑) consisting of polynomial multiples of 𝑥 2 . If 𝜑 is the linear functional on 𝒫 (𝐑) defined by 𝜑(𝑝) = 𝑝 ′ (0) , then 𝜑 ∈ 𝑈 0 . For 𝑈 ⊆ 𝑉 , the annihilator 𝑈 0 is a subset of the dual space 𝑉 ′ . Thus 𝑈 0 depends on the vector space containing 𝑈 , so a notation such as 𝑈 0𝑉 would be more precise. However, the containing vector space will always be clear from the context, so we will use the simpler notation 𝑈 0 . 3.123 example: the annihilator of a two-dimensional subspace of 𝐑 5 Let 𝑒 1 , 𝑒 2 , 𝑒 3 , 𝑒 4 , 𝑒 5 denote the standard basis of 𝐑 5 ; let 𝜑 1 , 𝜑 2 , 𝜑 3 , 𝜑 4 , 𝜑 5 ∈ (𝐑 5 ) ′ denote the dual basis of 𝑒 1 , 𝑒 2 , 𝑒 3 , 𝑒 4 , 𝑒 5 . Suppose 𝑈 = span (𝑒 1 , 𝑒 2 ) = {(𝑥 1 , 𝑥 2 , 0 , 0 , 0) ∈ 𝐑 5 ∶ 𝑥 1 , 𝑥 2 ∈ 𝐑}. We want to show that 𝑈 0 = span (𝜑 3 , 𝜑 4 , 𝜑 5 ) . Recall (see 3.113) that 𝜑 𝑗 is the linear functional on 𝐑 5 that selects the 𝑗 th coordinate: 𝜑 𝑗 (𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 ) = 𝑥 𝑗 . First suppose 𝜑 ∈ span (𝜑 3 , 𝜑 4 , 𝜑 5 ) . Then there exist 𝑐 3 , 𝑐 4 , 𝑐 5 ∈ 𝐑 such that 𝜑 = 𝑐 3 𝜑 3 + 𝑐 4 𝜑 4 + 𝑐 5 𝜑 5 . If (𝑥 1 , 𝑥 2 , 0 , 0 , 0) ∈ 𝑈 , then 𝜑(𝑥 1 , 𝑥 2 , 0 , 0 , 0) = (𝑐 3 𝜑 3 + 𝑐 4 𝜑 4 + 𝑐 5 𝜑 5 )(𝑥 1 , 𝑥 2 , 0 , 0 , 0) = 0. Thus 𝜑 ∈ 𝑈 0 . Hence we have shown that span (𝜑 3 , 𝜑 4 , 𝜑 5 ) ⊆ 𝑈 0 . To show the inclusion in the other direction, suppose that 𝜑 ∈ 𝑈 0 . Be- cause the dual basis is a basis of (𝐑 5 ) ′ , there exist 𝑐 1 , 𝑐 2 , 𝑐 3 , 𝑐 4 , 𝑐 5 ∈ 𝐑 such that 𝜑 = 𝑐 1 𝜑 1 + 𝑐 2 𝜑 2 + 𝑐 3 𝜑 3 + 𝑐 4 𝜑 4 + 𝑐 5 𝜑 5 . Because 𝑒 1 ∈ 𝑈 and 𝜑 ∈ 𝑈 0 , we have 0 = 𝜑(𝑒 1 ) = (𝑐 1 𝜑 1 + 𝑐 2 𝜑 2 + 𝑐 3 𝜑 3 + 𝑐 4 𝜑 4 + 𝑐 5 𝜑 5 )(𝑒 1 ) = 𝑐 1 . Similarly, 𝑒 2 ∈ 𝑈 and thus 𝑐 2 = 0 . Hence 𝜑 = 𝑐 3 𝜑 3 + 𝑐 4 𝜑 4 + 𝑐 5 𝜑 5 . Thus 𝜑 ∈ span (𝜑 3 , 𝜑 4 , 𝜑 5 ) , which shows that 𝑈 0 ⊆ span (𝜑 3 , 𝜑 4 , 𝜑 5 ) . Thus 𝑈 0 = span (𝜑 3 , 𝜑 4 , 𝜑 5 ) . Annotated Entity: ID: 123 Spans: True Boxes: True Text: 110 Chapter 3 Linear Maps 3.124 the annihilator is a subspace Suppose 𝑈 ⊆ 𝑉 . Then 𝑈 0 is a subspace of 𝑉 ′ . Proof Note that 0 ∈ 𝑈 0 (here 0 is the zero linear functional on 𝑉 ) because the zero linear functional applied to every vector in 𝑈 equals 0 ∈ 𝐅 . Suppose 𝜑 , 𝜓 ∈ 𝑈 0 . Thus 𝜑 , 𝜓 ∈ 𝑉 ′ and 𝜑(𝑢) = 𝜓(𝑢) = 0 for every 𝑢 ∈ 𝑈 . If 𝑢 ∈ 𝑈 , then (𝜑 + 𝜓)(𝑢) = 𝜑(𝑢) + 𝜓(𝑢) = 0 + 0 = 0. Thus 𝜑 + 𝜓 ∈ 𝑈 0 . Similarly, 𝑈 0 is closed under scalar multiplication. Thus 1.34 implies that 𝑈 0 is a subspace of 𝑉 ′ . The next result shows that dim 𝑈 0 is the difference of dim 𝑉 and dim 𝑈 . For example, this shows that if 𝑈 is a two-dimensional subspace of 𝐑 5 , then 𝑈 0 is a three-dimensional subspace of (𝐑 5 ) ′ , as in Example 3.123. The next result can be proved following the pattern of Example 3.123: choose a basis 𝑢 1 , … , 𝑢 𝑚 of 𝑈 , extend to a basis 𝑢 1 , … , 𝑢 𝑚 , … , 𝑢 𝑛 of 𝑉 , let 𝜑 1 , … , 𝜑 𝑚 , … , 𝜑 𝑛 be the dual basis of 𝑉 ′ , and then show that 𝜑 𝑚 + 1 , … , 𝜑 𝑛 is a basis of 𝑈 0 , which implies the desired result. You should construct the proof just outlined, even though a slicker proof is presented here. 3.125 dimension of the annihilator Suppose 𝑉 is finite-dimensional and 𝑈 is a subspace of 𝑉 . Then dim 𝑈 0 = dim 𝑉 − dim 𝑈. Proof Let 𝑖 ∈ ℒ (𝑈 , 𝑉) be the inclusion map defined by 𝑖(𝑢) = 𝑢 for each 𝑢 ∈ 𝑈 . Thus 𝑖 ′ is a linear map from 𝑉 ′ to 𝑈 ′ . The fundamental theorem of linear maps (3.21) applied to 𝑖 ′ shows that dim range 𝑖 ′ + dim null 𝑖 ′ = dim 𝑉 ′ . However, null 𝑖 ′ = 𝑈 0 (as can be seen by thinking about the definitions) and dim 𝑉 ′ = dim 𝑉 (by 3.111), so we can rewrite the equation above as 3.126 dim range 𝑖 ′ + dim 𝑈 0 = dim 𝑉. If 𝜑 ∈ 𝑈 ′ , then 𝜑 can be extended to a linear functional 𝜓 on 𝑉 (see, for example, Exercise 13 in Section 3A). The definition of 𝑖 ′ shows that 𝑖 ′ (𝜓) = 𝜑 . Thus 𝜑 ∈ range 𝑖 ′ , which implies that range 𝑖 ′ = 𝑈 ′ . Hence dim range 𝑖 ′ = dim 𝑈 ′ = dim 𝑈 , and then 3.126 becomes the equation dim 𝑈 + dim 𝑈 0 = dim 𝑉 , as desired. Annotated Entity: ID: 124 Spans: True Boxes: True Text: Section 3F Duality 111 The next result can be a useful tool to show that a subspace is as big as possible—see (a)—or to show that a subspace is as small as possible—see (b). 3.127 condition for the annihilator to equal {0} or the whole space Suppose 𝑉 is finite-dimensional and 𝑈 is a subspace of 𝑉 . Then (a) 𝑈 0 = {0} ⟺ 𝑈 = 𝑉 ; (b) 𝑈 0 = 𝑉 ′ ⟺ 𝑈 = {0} . Proof To prove (a), we have 𝑈 0 = {0} ⟺ dim 𝑈 0 = 0 ⟺ dim 𝑈 = dim 𝑉 ⟺ 𝑈 = 𝑉 , where the second equivalence follows from 3.125 and the third equivalence follows from 2.39. Similarly, to prove (b) we have 𝑈 0 = 𝑉 ′ ⟺ dim 𝑈 0 = dim 𝑉 ′ ⟺ dim 𝑈 0 = dim 𝑉 ⟺ dim 𝑈 = 0 ⟺ 𝑈 = {0} , where one direction of the first equivalence follows from 2.39, the second equiva- lence follows from 3.111, and the third equivalence follows from 3.125. The proof of (a) in the next result does not use the hypothesis that 𝑉 and 𝑊 are finite-dimensional. 3.128 the null space of 𝑇 ′ Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then (a) null 𝑇 ′ = ( range 𝑇) 0 ; (b) dim null 𝑇 ′ = dim null 𝑇 + dim 𝑊 − dim 𝑉 . Proof (a) First suppose 𝜑 ∈ null 𝑇 ′ . Thus 0 = 𝑇 ′ (𝜑) = 𝜑 ∘ 𝑇 . Hence 0 = (𝜑 ∘ 𝑇)(𝑣) = 𝜑(𝑇𝑣) for every 𝑣 ∈ 𝑉. Thus 𝜑 ∈ ( range 𝑇) 0 . This implies that null 𝑇 ′ ⊆ ( range 𝑇) 0 . To prove the inclusion in the opposite direction, now suppose 𝜑 ∈ ( range 𝑇) 0 . Thus 𝜑(𝑇𝑣) = 0 for every vector 𝑣 ∈ 𝑉 . Hence 0 = 𝜑 ∘ 𝑇 = 𝑇 ′ (𝜑) . In other words, 𝜑 ∈ null 𝑇 ′ , which shows that ( range 𝑇) 0 ⊆ null 𝑇 ′ , completing the proof of (a). Annotated Entity: ID: 125 Spans: True Boxes: True Text: 112 Chapter 3 Linear Maps (b) We have dim null 𝑇 ′ = dim ( range 𝑇) 0 = dim 𝑊 − dim range 𝑇 = dim 𝑊 − ( dim 𝑉 − dim null 𝑇) = dim null 𝑇 + dim 𝑊 − dim 𝑉 , where the first equality comes from (a), the second equality comes from 3.125, and the third equality comes from the fundamental theorem of linear maps (3.21). The next result can be useful because sometimes it is easier to verify that 𝑇 ′ is injective than to show directly that 𝑇 is surjective. 3.129 𝑇 surjective is equivalent to 𝑇 ′ injective Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then 𝑇 is surjective ⟺ 𝑇 ′ is injective . Proof We have 𝑇 ∈ ℒ (𝑉 , 𝑊) is surjective ⟺ range 𝑇 = 𝑊 ⟺ ( range 𝑇) 0 = {0} ⟺ null 𝑇 ′ = {0} ⟺ 𝑇 ′ is injective , where the second equivalence comes from 3.127(a) and the third equivalence comes from 3.128(a). 3.130 the range of 𝑇 ′ Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then (a) dim range 𝑇 ′ = dim range 𝑇 ; (b) range 𝑇 ′ = ( null 𝑇) 0 . Proof (a) We have dim range 𝑇 ′ = dim 𝑊 ′ − dim null 𝑇 ′ = dim 𝑊 − dim ( range 𝑇) 0 = dim range 𝑇 , where the first equality comes from 3.21, the second equality comes from 3.111 and 3.128(a), and the third equality comes from 3.125. Annotated Entity: ID: 126 Spans: True Boxes: True Text: Section 3F Duality 113 (b) First suppose 𝜑 ∈ range 𝑇 ′ . Thus there exists 𝜓 ∈ 𝑊 ′ such that 𝜑 = 𝑇 ′ (𝜓) . If 𝑣 ∈ null 𝑇 , then 𝜑(𝑣) = (𝑇 ′ (𝜓))𝑣 = (𝜓 ∘ 𝑇)(𝑣) = 𝜓(𝑇𝑣) = 𝜓(0) = 0. Hence 𝜑 ∈ ( null 𝑇) 0 . This implies that range 𝑇 ′ ⊆ ( null 𝑇) 0 . We will complete the proof by showing that range 𝑇 ′ and ( null 𝑇) 0 have the same dimension. To do this, note that dim range 𝑇 ′ = dim range 𝑇 = dim 𝑉 − dim null 𝑇 = dim ( null 𝑇) 0 , where the first equality comes from (a), the second equality comes from 3.21, and the third equality comes from 3.125. The next result should be compared to 3.129. 3.131 𝑇 injective is equivalent to 𝑇 ′ surjective Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then 𝑇 is injective ⟺ 𝑇 ′ is surjective . Proof We have 𝑇 is injective ⟺ null 𝑇 = {0} ⟺ ( null 𝑇) 0 = 𝑉 ′ ⟺ range 𝑇 ′ = 𝑉 ′ , where the second equivalence follows from 3.127(b) and the third equivalence follows from 3.130(b). Matrix of Dual of Linear Map The setting for the next result is the assumption that we have a basis 𝑣 1 , … , 𝑣 𝑛 of 𝑉 , along with its dual basis 𝜑 1 , … , 𝜑 𝑛 of 𝑉 ′ . We also have a basis 𝑤 1 , … , 𝑤 𝑚 of 𝑊 , along with its dual basis 𝜓 1 , … , 𝜓 𝑚 of 𝑊 ′ . Thus ℳ (𝑇) is computed with respect to the bases just mentioned of 𝑉 and 𝑊 , and ℳ (𝑇 ′ ) is computed with respect to the dual bases just mentioned of 𝑊 ′ and 𝑉 ′ . Using these bases gives the following pretty result. 3.132 matrix of 𝑇 ′ is transpose of matrix of 𝑇 Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Then ℳ (𝑇 ′ ) = ( ℳ (𝑇)) t . Annotated Entity: ID: 127 Spans: True Boxes: True Text: 114 Chapter 3 Linear Maps Proof Let 𝐴 = ℳ (𝑇) and 𝐶 = ℳ (𝑇 ′ ) . Suppose 1 ≤ 𝑗 ≤ 𝑚 and 1 ≤ 𝑘 ≤ 𝑛 . From the definition of ℳ (𝑇 ′ ) we have 𝑇 ′ (𝜓 𝑗 ) = 𝑛 ∑ 𝑟=1 𝐶 𝑟 , 𝑗 𝜑 𝑟 . The left side of the equation above equals 𝜓 𝑗 ∘ 𝑇 . Thus applying both sides of the equation above to 𝑣 𝑘 gives (𝜓 𝑗 ∘ 𝑇)(𝑣 𝑘 ) = 𝑛 ∑ 𝑟=1 𝐶 𝑟 , 𝑗 𝜑 𝑟 (𝑣 𝑘 ) = 𝐶 𝑘 , 𝑗 . We also have (𝜓 𝑗 ∘ 𝑇)(𝑣 𝑘 ) = 𝜓 𝑗 (𝑇𝑣 𝑘 ) = 𝜓 𝑗 ( 𝑚 ∑ 𝑟=1 𝐴 𝑟 , 𝑘 𝑤 𝑟 ) = 𝑚 ∑ 𝑟=1 𝐴 𝑟 , 𝑘 𝜓 𝑗 (𝑤 𝑟 ) = 𝐴 𝑗 , 𝑘 . Comparing the last line of the last two sets of equations, we have 𝐶 𝑘 , 𝑗 = 𝐴 𝑗 , 𝑘 . Thus 𝐶 = 𝐴 t . In other words, ℳ (𝑇 ′ ) = ( ℳ (𝑇)) t , as desired. Now we use duality to give an alternative proof that the column rank of a matrix equals the row rank of the matrix. This result was previously proved using different tools—see 3.57. 3.133 column rank equals row rank Suppose 𝐴 ∈ 𝐅 𝑚 , 𝑛 . Then the column rank of 𝐴 equals the row rank of 𝐴 . Proof Define 𝑇 ∶ 𝐅 𝑛 , 1 → 𝐅 𝑚 , 1 by 𝑇𝑥 = 𝐴𝑥 . Thus ℳ (𝑇) = 𝐴 , where ℳ (𝑇) is computed with respect to the standard bases of 𝐅 𝑛 , 1 and 𝐅 𝑚 , 1 . Now column rank of 𝐴 = column rank of ℳ (𝑇) = dim range 𝑇 = dim range 𝑇 ′ = column rank of ℳ (𝑇 ′ ) = column rank of 𝐴 t = row rank of 𝐴 , where the second equality comes from 3.78, the third equality comes from 3.130(a), the fourth equality comes from 3.78, the fifth equality comes from 3.132, and the last equality follows from the definitions of row and column rank. See Exercise 8 in Section 7A for another alternative proof of the result above. Annotated Entity: ID: 128 Spans: True Boxes: True Text: Section 3F Duality 115 Exercises 3F 1 Explain why each linear functional is surjective or is the zero map. 2 Give three distinct examples of linear functionals on 𝐑 [0 , 1] . 3 Suppose 𝑉 is finite-dimensional and 𝑣 ∈ 𝑉 with 𝑣 ≠ 0 . Prove that there exists 𝜑 ∈ 𝑉 ′ such that 𝜑(𝑣) = 1 . 4 Suppose 𝑉 is finite-dimensional and 𝑈 is a subspace of 𝑉 such that 𝑈 ≠ 𝑉 . Prove that there exists 𝜑 ∈ 𝑉 ′ such that 𝜑(𝑢) = 0 for every 𝑢 ∈ 𝑈 but 𝜑 ≠ 0 . 5 Suppose 𝑇 ∈ ℒ (𝑉 , 𝑊) and 𝑤 1 , … , 𝑤 𝑚 is a basis of range 𝑇 . Hence for each 𝑣 ∈ 𝑉 , there exist unique numbers 𝜑 1 (𝑣) , … , 𝜑 𝑚 (𝑣) such that 𝑇𝑣 = 𝜑 1 (𝑣)𝑤 1 + ⋯ + 𝜑 𝑚 (𝑣)𝑤 𝑚 , thus defining functions 𝜑 1 , … , 𝜑 𝑚 from 𝑉 to 𝐅 . Show that each of the func- tions 𝜑 1 , … , 𝜑 𝑚 is a linear functional on 𝑉 . 6 Suppose 𝜑 , 𝛽 ∈ 𝑉 ′ . Prove that null 𝜑 ⊆ null 𝛽 if and only if there exists 𝑐 ∈ 𝐅 such that 𝛽 = 𝑐𝜑 . 7 Suppose that 𝑉 1 , … , 𝑉 𝑚 are vector spaces. Prove that (𝑉 1 × ⋯ × 𝑉 𝑚 ) ′ and 𝑉 1′ × ⋯ × 𝑉 𝑚′ are isomorphic vector spaces. 8 Suppose 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝜑 1 , … , 𝜑 𝑛 is the dual basis of 𝑉 ′ . Define Γ ∶ 𝑉 → 𝐅 𝑛 and Λ ∶ 𝐅 𝑛 → 𝑉 by Γ(𝑣) = (𝜑 1 (𝑣) , … , 𝜑 𝑛 (𝑣)) and Λ(𝑎 1 , … , 𝑎 𝑛 ) = 𝑎 1 𝑣 1 + ⋯ + 𝑎 𝑛 𝑣 𝑛 . Explain why Γ and Λ are inverses of each other. 9 Suppose 𝑚 is a positive integer. Show that the dual basis of the basis 1 , 𝑥 , … , 𝑥 𝑚 of 𝒫 𝑚 (𝐑) is 𝜑 0 , 𝜑 1 , … , 𝜑 𝑚 , where 𝜑 𝑘 (𝑝) = 𝑝 (𝑘) (0) 𝑘! . Here 𝑝 (𝑘) denotes the 𝑘 th derivative of 𝑝 , with the understanding that the 0 th derivative of 𝑝 is 𝑝 . 10 Suppose 𝑚 is a positive integer. (a) Show that 1 , 𝑥 − 5 , … , (𝑥 − 5) 𝑚 is a basis of 𝒫 𝑚 (𝐑) . (b) What is the dual basis of the basis in (a)? 11 Suppose 𝑣 1 , … , 𝑣 𝑛 is a basis of 𝑉 and 𝜑 1 , … , 𝜑 𝑛 is the corresponding dual basis of 𝑉 ′ . Suppose 𝜓 ∈ 𝑉 ′ . Prove that 𝜓 = 𝜓(𝑣 1 )𝜑 1 + ⋯ + 𝜓(𝑣 𝑛 )𝜑 𝑛 . Annotated Entity: ID: 129 Spans: True Boxes: True Text: 116 Chapter 3 Linear Maps 12 Suppose 𝑆 , 𝑇 ∈ ℒ (𝑉 , 𝑊) . (a) Prove that (𝑆 + 𝑇) ′ = 𝑆 ′ + 𝑇 ′ . (b) Prove that (𝜆𝑇) ′ = 𝜆𝑇 ′ for all 𝜆 ∈ 𝐅 . This exercise asks you to verify ( a ) and ( b ) in 3.120. 13 Show that the dual map of the identity operator on 𝑉 is the identity operator on 𝑉 ′ . 14 Define 𝑇 ∶ 𝐑 3 → 𝐑 2 by 𝑇(𝑥 , 𝑦 , 𝑧) = (4𝑥 + 5𝑦 + 6𝑧 , 7𝑥 + 8𝑦 + 9𝑧). Suppose 𝜑 1 , 𝜑 2 denotes the dual basis of the standard basis of 𝐑 2 and 𝜓 1 , 𝜓 2 , 𝜓 3 denotes the dual basis of the standard basis of 𝐑 3 . (a) Describe the linear functionals 𝑇 ′ (𝜑 1 ) and 𝑇 ′ (𝜑 2 ) . (b) Write 𝑇 ′ (𝜑 1 ) and 𝑇 ′ (𝜑 2 ) as linear combinations of 𝜓 1 , 𝜓 2 , 𝜓 3 . 15 Define 𝑇 ∶ 𝒫 (𝐑) → 𝒫 (𝐑) by (𝑇𝑝)(𝑥) = 𝑥 2 𝑝(𝑥) + 𝑝 ″ (𝑥) for each 𝑥 ∈ 𝐑 . (a) Suppose 𝜑 ∈ 𝒫 (𝐑) ′ is defined by 𝜑(𝑝) = 𝑝 ′ (4) . Describe the linear functional 𝑇 ′ (𝜑) on 𝒫 (𝐑) . (b) Suppose 𝜑 ∈ 𝒫 (𝐑) ′ is defined by 𝜑(𝑝) = ∫ 10 𝑝 . Evaluate (𝑇 ′ (𝜑))(𝑥 3 ) . 16 Suppose 𝑊 is finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that 𝑇 ′ = 0 ⟺ 𝑇 = 0. 17 Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . Prove that 𝑇 is invertible if and only if 𝑇 ′ ∈ ℒ (𝑊 ′ , 𝑉 ′ ) is invertible. 18 Suppose 𝑉 and 𝑊 are finite-dimensional. Prove that the map that takes 𝑇 ∈ ℒ (𝑉 , 𝑊) to 𝑇 ′ ∈ ℒ (𝑊 ′ , 𝑉 ′ ) is an isomorphism of ℒ (𝑉 , 𝑊) onto ℒ (𝑊 ′ , 𝑉 ′ ) . 19 Suppose 𝑈 ⊆ 𝑉 . Explain why 𝑈 0 = {𝜑 ∈ 𝑉 ′ ∶ 𝑈 ⊆ null 𝜑}. 20 Suppose 𝑉 is finite-dimensional and 𝑈 is a subspace of 𝑉 . Show that 𝑈 = {𝑣 ∈ 𝑉 ∶ 𝜑(𝑣) = 0 for every 𝜑 ∈ 𝑈 0 }. 21 Suppose 𝑉 is finite-dimensional and 𝑈 and 𝑊 are subspaces of 𝑉 . (a) Prove that 𝑊 0 ⊆ 𝑈 0 if and only if 𝑈 ⊆ 𝑊 . (b) Prove that 𝑊 0 = 𝑈 0 if and only if 𝑈 = 𝑊 . Annotated Entity: ID: 130 Spans: True Boxes: True Text: Section 3F Duality 117 22 Suppose 𝑉 is finite-dimensional and 𝑈 and 𝑊 are subspaces of 𝑉 . (a) Show that (𝑈 + 𝑊) 0 = 𝑈 0 ∩ 𝑊 0 . (b) Show that (𝑈 ∩ 𝑊) 0 = 𝑈 0 + 𝑊 0 . 23 Suppose 𝑉 is finite-dimensional and 𝜑 1 , … , 𝜑 𝑚 ∈ 𝑉 ′ . Prove that the follow- ing three sets are equal to each other. (a) span (𝜑 1 , … , 𝜑 𝑚 ) (b) (( null 𝜑 1 ) ∩ ⋯ ∩ ( null 𝜑 𝑚 )) 0 (c) {𝜑 ∈ 𝑉 ′ ∶ ( null 𝜑 1 ) ∩ ⋯ ∩ ( null 𝜑 𝑚 ) ⊆ null 𝜑} 24 Suppose 𝑉 is finite-dimensional and 𝑣 1 , … , 𝑣 𝑚 ∈ 𝑉 . Define a linear map Γ ∶ 𝑉 ′ → 𝐅 𝑚 by Γ(𝜑) = (𝜑(𝑣 1 ) , … , 𝜑(𝑣 𝑚 )) . (a) Prove that 𝑣 1 , … , 𝑣 𝑚 spans 𝑉 if and only if Γ is injective. (b) Prove that 𝑣 1 , … , 𝑣 𝑚 is linearly independent if and only if Γ is surjective. 25 Suppose 𝑉 is finite-dimensional and 𝜑 1 , … , 𝜑 𝑚 ∈ 𝑉 ′ . Define a linear map Γ ∶ 𝑉 → 𝐅 𝑚 by Γ(𝑣) = (𝜑 1 (𝑣) , … , 𝜑 𝑚 (𝑣)) . (a) Prove that 𝜑 1 , … , 𝜑 𝑚 spans 𝑉 ′ if and only if Γ is injective. (b) Prove that 𝜑 1 , … , 𝜑 𝑚 is linearly independent if and only if Γ is surjective. 26 Suppose 𝑉 is finite-dimensional and Ω is a subspace of 𝑉 ′ . Prove that Ω = {𝑣 ∈ 𝑉 ∶ 𝜑(𝑣) = 0 for every 𝜑 ∈ Ω} 0 . 27 Suppose 𝑇 ∈ ℒ ( 𝒫 5 (𝐑)) and null 𝑇 ′ = span (𝜑) , where 𝜑 is the linear functional on 𝒫 5 (𝐑) defined by 𝜑(𝑝) = 𝑝(8) . Prove that range 𝑇 = {𝑝 ∈ 𝒫 5 (𝐑) ∶ 𝑝(8) = 0}. 28 Suppose 𝑉 is finite-dimensional and 𝜑 1 , … , 𝜑 𝑚 is a linearly independent list in 𝑉 ′ . Prove that dim (( null 𝜑 1 ) ∩ ⋯ ∩ ( null 𝜑 𝑚 )) = ( dim 𝑉) − 𝑚. 29 Suppose 𝑉 and 𝑊 are finite-dimensional and 𝑇 ∈ ℒ (𝑉 , 𝑊) . (a) Prove that if 𝜑 ∈ 𝑊 ′ and null 𝑇 ′ = span (𝜑) , then range 𝑇 = null 𝜑 . (b) Prove that if 𝜓 ∈ 𝑉 ′ and range 𝑇 ′ = span (𝜓) , then null 𝑇 = null 𝜓 . 30 Suppose 𝑉 is finite-dimensional and 𝜑 1 , … , 𝜑 𝑛 is a basis of 𝑉 ′ . Show that there exists a basis of 𝑉 whose dual basis is 𝜑 1 , … , 𝜑 𝑛 . 31 Suppose 𝑈 is a subspace of 𝑉 . Let 𝑖 ∶ 𝑈 → 𝑉 be the inclusion map defined by 𝑖(𝑢) = 𝑢 . Thus 𝑖 ′ ∈ ℒ (𝑉 ′ , 𝑈 ′ ) . (a) Show that null 𝑖 ′ = 𝑈 0 . (b) Prove that if 𝑉 is finite-dimensional, then range 𝑖 ′ = 𝑈 ′ . (c) Prove that if 𝑉 is finite-dimensional, then ̃ 𝑖 ′ is an isomorphism from 𝑉 ′ /𝑈 0 onto 𝑈 ′ . The isomorphism in ( c ) is natural in that it does not depend on a choice of basis in either vector space. Annotated Entity: ID: 131 Spans: True Boxes: True Text: 118 Chapter 3 Linear Maps 32 The double dual space of 𝑉 , denoted by 𝑉 ″ , is defined to be the dual space of 𝑉 ′ . In other words, 𝑉 ″ = (𝑉 ′ ) ′ . Define Λ ∶ 𝑉 → 𝑉 ″ by (Λ𝑣)(𝜑) = 𝜑(𝑣) for each 𝑣 ∈ 𝑉 and each 𝜑 ∈ 𝑉 ′ . (a) Show that Λ is a linear map from 𝑉 to 𝑉 ″ . (b) Show that if 𝑇 ∈ ℒ (𝑉) , then 𝑇 ″ ∘ Λ = Λ ∘ 𝑇 , where 𝑇 ″ = (𝑇 ′ ) ′ . (c) Show that if 𝑉 is finite-dimensional, then Λ is an isomorphism from 𝑉 onto 𝑉 ″ . Suppose 𝑉 is finite-dimensional. Then 𝑉 and 𝑉 ′ are isomorphic, but finding an isomorphism from 𝑉 onto 𝑉 ′ generally requires choosing a basis of 𝑉 . In contrast, the isomorphism Λ from 𝑉 onto 𝑉 ″ does not require a choice of basis and thus is considered more natural. 33 Suppose 𝑈 is a subspace of 𝑉 . Let 𝜋 ∶ 𝑉 → 𝑉/𝑈 be the usual quotient map. Thus 𝜋 ′ ∈ ℒ ((𝑉/𝑈) ′ , 𝑉 ′ ) . (a) Show that 𝜋 ′ is injective. (b) Show that range 𝜋 ′ = 𝑈 0 . (c) Conclude that 𝜋 ′ is an isomorphism from (𝑉/𝑈) ′ onto 𝑈 0 . The isomorphism in ( c ) is natural in that it does not depend on a choice of basis in either vector space. In fact, there is no assumption here that any of these vector spaces are finite-dimensional.