Linear Algebra lecture notes

linear algebra vector spaces lecture notes and lecture notes on introduction to linear algebra. what is linear algebra used for in computer science pdf free download
ZackVincent Profile Pic
ZackVincent,United Kingdom,Teacher
Published Date:15-07-2017
Your Website URL(Optional)
Comment
MA106 Linear Algebra lecture notes Lecturers: Martin Bright and Daan Krammer Warwick, January 2011 Contents 1 Number systems and elds 3 1.1 Axioms for number systems . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Vector spaces 4 2.1 Examples of vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Linear independence, spanning and bases of vector spaces 6 3.1 Linear dependence and independence . . . . . . . . . . . . . . . . . . . . 6 3.2 Spanning vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3 Bases of vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.4 Existence of a basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Subspaces 10 5 Linear transformations 13 5.1 De nition and examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.2 Kernels and images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.3 Rank and nullity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.4 Operations on linear maps . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6 Matrices 18 7 Linear transformations and matrices 20 7.1 Setting up the correspondence . . . . . . . . . . . . . . . . . . . . . . . . 20 7.2 The correspondence between operations on linear maps and matrices . . 22 7.3 Linear equations and the inverse image problem . . . . . . . . . . . . . . 24 8 Elementary operations and the rank of a matrix 25 8.1 Gauss transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 8.2 Elementary row operations . . . . . . . . . . . . . . . . . . . . . . . . . 26 8.3 The augmented matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 8.4 Row reducing a matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 8.5 Elementary column operations . . . . . . . . . . . . . . . . . . . . . . . 29 8.6 The rank of a matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 8.7 The rank criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 9 The inverse of a linear transformation and of a matrix 33 9.1 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 9.2 Matrix inversion by row reduction . . . . . . . . . . . . . . . . . . . . . 34 9.3 Elementary matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 9.4 Application to linear equations . . . . . . . . . . . . . . . . . . . . . . . 36 110 The determinant of a matrix 37 10.1 De nition of the determinant . . . . . . . . . . . . . . . . . . . . . . . . 37 10.2 The e ect of matrix operations on the determinant . . . . . . . . . . . . 39 10.3 The determinant of a product . . . . . . . . . . . . . . . . . . . . . . . . 42 10.4 Minors and cofactors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 10.5 The inverse of a matrix using determinants . . . . . . . . . . . . . . . . 44 10.6 Cramer's rule for solving simultaneous equations . . . . . . . . . . . . . 45 11 Change of basis and equivalent matrices 45 12 Similar matrices, eigenvectors and eigenvalues 48 12.1 Similar matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 12.2 Eigenvectors and eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . 49 12.3 The scalar product symmetric and orthogonal matrices . . . . . . . . . 54 21 Number systems and elds We introduce the number systems most commonly used in mathematics. 1. The natural numbersN =f1; 2; 3; 4;:::g. InN, addition is possible but not subtraction; e.g. 2 362N. 2. The integersZ =f:::;2;1; 0; 1; 2; 3;:::g. InZ, addition, subtraction and multiplication are always possible, but not division; e.g. 2=362Z. 3. The rational numbersQ =fp=qjp;q2Z; q =6 0g. In Q, addition, subtraction, multiplication and division (except by zero) are all p possible. However, 262Q. 4. The real numbersR. These are the numbers which can be expressed as decimals. The rational numbers are those with nite or recurring decimals. In R, addition, subtraction, multiplication and division (except by zero) are still p possible, and all positive numbers have square roots, but 162R. 2 5. The complex numbersC =fx +iyjx;y2Rg, where i =1. In C, addition, subtraction, multiplication and division (except by zero) are still possible, and all, numbers have square roots. In fact all polynomial equations with coecients inC have solutions inC. 1.1 Axioms for number systems Laws governing the way numbers combine together are called axioms. Any particular axiom might be true in some number systems but not in others. Axioms for addition. Let S be a number system. A1. + = + for all ; 2S. A2. ( + ) + = + ( + ) for all ; ; 2S. A3. There is a number 02S such that + 0 = 0 + = for all 2S. A4. For each number 2 S there exists a number 2 S such that + ( ) = ( ) + = 0. These axioms may or may not be satis ed by a given number systemS. For example, inN, A1 and A2 hold but A3 and A4 do not hold. A1A4 all hold inZ;Q;R andC. Axioms for multiplication. M1. : = : for all ; 2S. M2. ( : ): = :( : ) for all ; ; 2S. M3. There is a number 12S such that :1 = 1: = for all 2S. 1 M4. For each number 2 S with 6= 0, there exists a number 2 S such that 1 1 : = : = 1. InN andZ, M1M3 hold but M4 does not hold. M1M4 all hold inQ;R andC. 3Axiom relating addition and multiplication. D. ( + ): = : + : for all ; ; 2S. De nition. A setS on which addition and multiplication are de ned is called a eld if it satis es each of the axioms A1, A2, A3, A4, M1, M2, M3, M4, D, and if, in addition, 16= 0. Roughly speaking, S is a eld if addition, subtraction, multiplication and division (except by zero) are all possible in S. We shall always use the letter K for a general eld. Example. N andZ are not elds, butQ,R andC are all elds. There are many other elds, including some nite elds. For example, for each prime number p, there is a eld F =f0; 1; 2;:::;p 1g with p elements, where addition and p multiplication are carried out modulo p. Thus, inF , we have 5 + 4 = 2, 5 4 = 6 and 7 1 5 = 3 because 5 3 = 1. The smallest such eld F has just two elements 0 and 1, 2 where 1+1 = 0. This eld is extremely important in Computer Science since an element ofF represents a bit of information. 2 Various other familiar properties of numbers, such as 0 = 0, ( ) =( ) = ( ), ( )( ) = , (1) = , for all ; 2S, can be proved from the axioms. Why would we want to do this, when we can see they're true anyway? The point is that, when we meet a new number system, it is enough to check whether the axioms hold; if they do, then all these properties follow automatically. However, occasionally you need to be careful. For example, inF we have 1 + 1 = 0, 2 and so it is not possible to divide by 2 in this eld. 2 Vector spaces De nition. A vector space over a eld K is a set V which has two basic operations, addition and scalar multiplication, satisfying certain requirements. Thus for every pair u; v2 V , u + v2 V is de ned, and for every 2 K, v2 V is de ned. For V to be called a vector space, the following axioms must be satis ed for all ; 2K and all u; v2V . (i) Vector addition satis es axioms A1, A2, A3 and A4. (ii) (u + v) = u + v; (iii) ( + )v = v + v; (iv) ( )v = ( v); (v) 1v = v. Elements of the eld K will be called scalars. Note that we will use boldface letters like v to denote vectors. The zero vector in V will be written as 0 , or usually just 0. V This is di erent from the zero scalar 0 = 0 2K. K For nearly all results in this course, there is no loss in assuming that K is the eldR of real numbers. So you may assume this if you nd it helpful to do so. Just occasionally, we will need to assume K =C the eld of complex numbers. However, it is important to note that nearly all arguments in Linear Algebra use only the axioms for a eld and so are valid for any eld, which is why shall use a general eld K for most of the course. 42.1 Examples of vector spaces n 1. K =f( ; ;:::; )j 2Kg. This is the space of row vectors. Addition and 1 2 n i scalar multiplication are de ned by the obvious rules: ( ; ;:::; ) + ( ; ;:::; ) = ( + ; + ;:::; + ); 1 2 n 1 2 n 1 1 2 2 n n ( ; ;:::; ) = ( ; ;:::; ): 1 2 n 1 2 n The most familiar examples are 2 3 R =f(x;y)jx;y2Rg and R =f(x;y;z)jx;y;z2Rg; which we can think of geometrically as the points in ordinary 2- and 3-dimensional space, equipped with a coordinate system. 2 3 Vectors inR andR can also be thought of as directed lines joining the origin to the points with coordinates (x;y) or (x;y;z). (x;y) :            0 =(0,0) Addition of vectors is then given by the parallelogram law. v + v 1 2                        v 2   :    v 1                   0 1 Note that K is essentially the same as K itself. 2. Let Kx be the set of polynomials in an indeterminate x with coecients in the eld K. That is, n Kx =f + x + + x jn 0; 2Kg: 0 1 n i Then Kx is a vector space over K. 3. LetKx be the set of polynomials overK of degree at mostn, for somen 0. n Then Kx is also a vector space over K; in fact it is a subspace of Kx. n Note that the polynomials of degree exactly n do not form a vector space. (Why not?) 4. Let K = R and let V be the set of n-times di erentiable functions f : R R which are solutions of the di erential equation n n1 d f d f df  + + + + f = 0: 0 1 n1 n n n1 dx dx dx for xed  ; ;:::; 2 R. Then V is a vector space over R, for if f(x) and 0 1 n g(x) are both solutions of this equation, then so are f(x) +g(x) and f(x) for all 2R. 5. The previous example is a space of functions. There are many such examples that k are important in Analysis. For example, the set C ((0; 1);R), consisting of all (k) functionsf : (0; 1)R such that thekth derivative f exists and is continuous, is a vector space overR with the usual pointwise de nitions of addition and scalar multiplication of functions. 5n 6. Any n bits of information can be thought of as a vector in F . 2 Facing such a variety of vector spaces, a mathematician wants to derive useful meth- ods of handling all these vector spaces. If work out techniques for dealing with a single 3 8 example, sayR , how can we be certain that our methods will also work forR or even 8 C ? That is why we use the axiomatic approach to developing mathematics. We must use only arguments based on the vector space axioms. We have to avoid making any other assumptions. This ensures that everything we prove is valid for all vector spaces, 3 not just the familiar ones likeR . We shall be assuming the following additional simple properties of vectors and scalars from now on. They can all be deduced from the axioms (and it is a useful exercise to do so). (i) 0 = 0 for all 2K (ii) 0v = 0 for all v2V (iii) ( v) = ( )v = (v), for all 2K and v2V . (iv) if v = 0 then = 0 or v = 0. 3 Linear independence, spanning and bases of vector spaces 3.1 Linear dependence and independence De nition. Let V be a vector space over the eld K. The vectors v ; v ;::: v are 1 2 n said to be linearly dependent if there exist scalars ; ;:::; 2K, not all zero, such 1 2 n that v + v + + v = 0: 1 1 2 2 n n v ; v ;::: v are said to be linearly independent if they are not linearly dependent. In 1 2 n other words, they are linearly independent if the only scalars ; ;:::; 2 K that 1 2 n satisfy the above equation are = 0, = 0, :::; = 0: 1 2 n De nition. Vectors of the form v + v + + v for ; ;:::; 2K are 1 1 2 2 n n 1 2 n called linear combinations of v ; v ;::: v . 1 2 n 2 Example. Let V =R , v = (1; 3), v = (2; 5). 1 2 Then v + v = ( + 2 ; 3 + 5 ), which is equal to 0 = (0; 0) if and only 1 1 2 2 1 2 1 2 if + 2 = 0 and 3 + 5 = 0. Thus we have a pair of simultaneous equations in 1 2 1 2 ; and the only solution is = = 0, so v , v are linearly independent. 1 2 1 2 1 2 2 Example. Let V =Q , v = (1; 3), v = (2; 6). 1 2 This time the equations are + 2 = 0 and 3 + 6 = 0, and there are non-zero 1 2 1 2 solutions, such as =2, = 1, and so v , v are linearly dependent. 1 2 1 2 Lemma 3.1. v ; v ;:::; v 2V are linearly dependent if and only if either v = 0 or, 1 2 n 1 for some r, v is a linear combination of v ;:::; v . r 1 r1 Proof. If v = 0 then by putting = 1 and = 0 fori 1 we get v ++ v = 1 1 i 1 1 n n 0, so v ; v ;:::; v 2V are linearly dependent. 1 2 n If v is a linear combination of v ;:::; v , then v = v + + v for r 1 r1 r 1 1 r1 r1 some ;:::; 2 K and so we get v + + v 1 v = 0 and again 1 r1 1 1 r1 r1 r v ; v ;:::; v 2V are linearly dependent. 1 2 n Conversely, suppose that v ; v ;:::; v 2 V are linearly dependent, and are 1 2 n i scalars, not all zero, satisfying v + v + + v = 0. Let r be maximal 1 1 2 2 n n with 6= 0; then v + v + + v = 0. Ifr = 1 then v = 0 which, by (iv) r 1 1 2 2 r r 1 1 above, is only possible if v = 0. Otherwise, we get 1 1 r1 v = v  v : r 1 r1 r r In other words, v is a linear combination of v ;:::; v . r 1 r1 63.2 Spanning vectors De nition. The vectors v ;:::; v in V span V if every vector v 2 V is a linear 1 n combination v + v + + v of v ;:::; v . 1 1 2 2 n n 1 n 3.3 Bases of vector spaces De nition. The vectors v ;:::; v inV form a basis ofV if they are linearly indepen- 1 n dent and span V . Proposition 3.2. The vectors v ;:::; v form a basis of V if and only if every v2V 1 n can be written uniquely as v = v + v + + v ; that is, the coecients 1 1 2 2 n n ;:::; are uniquely determined by the vector v. 1 n Proof. Suppose that v ;:::; v form a basis ofV . Then they spanV , so certainly every 1 n v2 V can be written as v = v + v + + v . Suppose that we also had 1 1 2 2 n n v = v + v + + v for some other scalars 2K. Then we have 1 1 2 2 n n i 0 = v v = ( )v + ( )v + + ( )v 1 1 1 2 2 2 n n n and so ( ) = ( ) = = ( ) = 0 1 1 2 2 n n by linear independence of v ;:::; v . Hence = for all i, which means that the 1 n i i i are uniquely determined. Conversely, suppose that every v2V can be written uniquely as v = v + v + 1 1 2 2  + v . Then v ;:::; v certainly span V . If v + v + + v = 0, then n n 1 n 1 1 2 2 n n v + v + + v = 0v + 0v + + 0v 1 1 2 2 n n 1 2 n and so the uniqueness assumption implies that = = = = 0, and v ;:::; v 1 2 n 1 n are linearly independent. Hence they form a basis of V . De nition. The scalars ;:::; in the statement of the proposition are called the 1 n coordinates of v with respect to the basis v ;:::; v . 1 n With respect to a di erent basis, v will have di erent coordinates. Indeed, a basis for a vector space can be thought of as a choice of a system of coordinates. Examples Here are some examples of bases of vector spaces. 2 1. (1; 0) and (0; 1) form a basis ofK . This follows from Proposition 3.2, because each 2 element ( ; )2K can be written as (1; 0) + (0; 1), and this expression is 1 2 1 2 clearly unique. 3 2. More generally, (1; 0; 0), (0; 1; 0), (0; 0; 1) form a basis ofK , (1; 0; 0; 0), (0; 1; 0; 0), 4 (0; 0; 1; 0), (0; 0; 0; 1) form a basis of K and so on. This is called the standard n basis of K for n2N. n (To be precise, the standard basis ofK is v ;:::; v , where v is the vector with 1 n i a 1 in the ith position and a 0 in all other positions.) n 2 3. There are many other bases of K . For example (1; 0); (1; 1) form a basis of K , because ( ; ) = ( )(1; 0) + (1; 1), and this expression is unique. In 1 2 1 2 2 fact, any two non-zero vectors such that one is not a scalar multiple of the other 2 form a basis for K . 4. As we have de ned a basis, it has to consist of a nite number of vectors. Not every vector space has a nite basis. For example, let Kx be the space of polynomials in x with coecients in K. Let p (x);p (x);:::;p (x) be any nite collection of 1 2 n polynomials inKx. Then, ifd is the maximum degree ofp (x);p (x);:::;p (x), 1 2 n any linear combination of p (x);p (x);:::;p (x) has degree at most d, and so 1 2 n p (x);p (x);:::;p (x) cannot span Kx. On the other hand, it is possible (with 1 2 n a little care) to de ne what it means for an in nite set of vectors to be a basis of 2 3 n a vector space; in fact the in nite sequence of vectors 1;x;x ;x ;:::;x ;::: is a basis of Kx. 7A vector space with a nite basis is called nite-dimensional. In fact, nearly all of this course will be about nite-dimensional spaces, but it is important to remember that these are not the only examples. The spaces of functions mentioned in Example 5. of Section 2 typically have uncountably in nite dimension. Theorem 3.3 (The basis theorem). Suppose that v ;:::; v and w ;:::; w are both 1 m 1 n bases of the vector space V . Then m =n. In other words, all nite bases of V contain the same number of vectors. The proof of this theorem is quite tricky and uses the concept of sifting which we introduce after the next lemma. De nition. The number n of vectors in a basis of the nite-dimensional vector space V is called the dimension of V and we write dim(V ) =n. n Thus, as we might expect, K has dimension n. Kx is in nite-dimensional, but 2 n the space Kx of polynomials of degree at most n has basis 1;x;x ;:::;x , so its n dimension is n + 1 (not n). Note that the dimension of V depends on the eld K. Thus the complex numbers C can be considered as  a vector space of dimension 1 over C, with one possible basis being the single element 1;  a vector space of dimension 2 over R, with one possible basis given by the two elements 1;i;  a vector space of in nite dimension overQ. The rst step towards proving the basis theorem is to be able to remove unnecessary vectors from a spanning set of vectors. Lemma 3.4. Suppose that the vectors v ; v ;:::; v ; w span V and that w is a linear 1 2 n combination of v ;:::; v . Then v ;:::; v span V . 1 n 1 n Proof. Since v ; v ;:::; v ; w span V , any vector v2V can be written as 1 2 n v = v + + v + w; 1 1 n n But w is a linear combination of v ;:::; v , so w = v + + v for some scalars 1 n 1 1 n n , and hence i v = ( + )v + + ( + )v 1 1 1 n n n is a linear combination of v ;:::; v , which therefore span V . 1 n There is an important process, which we shall call sifting, which can be applied to any sequence of vectors v ; v ;:::; v in a vector space V , as follows. We consider 1 2 n each vector v in turn. If it is zero, or a linear combination of the preceding vectors i v ;:::; v , then we remove it from the list. 1 i1 3 Example. Let us sift the following sequence of vectors in R . v = (0; 0; 0) v = (1; 1; 1) v = (2; 2; 2) v = (1; 0; 0) 1 2 3 4 v = (3; 2; 2) v = (0; 0; 0) v = (1; 1; 0) v = (0; 0; 1) 5 6 7 8 v = 0, so we remove it. v is non-zero so it stays. v = 2v so it is removed. v is 1 2 3 2 4 clearly not a linear combination of v , so it stays. 2 We have to decide next whether v is a linear combination of v ; v . If so, then 5 2 4 (3; 2; 2) = (1; 1; 1) + (1; 0; 0), which (fairly obviously) has the solution = 2, 1 2 1 = 1, so remove v . Then v = 0 so that is removed too. 2 5 6 Next we try v = (1; 1; 0) = (1; 1; 1) + (1; 0; 0), and looking at the three compo- 7 1 2 nents, this reduces to the three equations 1 = + ; 1 = ; 0 = : 1 2 1 1 8The second and third of these equations contradict each other, and so there is no solution. Hence v is not a linear combination of v ; v , and it stays. 7 2 4 Finally, we need to try v = (0; 0; 1) = (1; 1; 1) + (1; 0; 0) + (1; 1; 0) 8 1 2 3 leading to the three equations 0 = + + 0 = + ; 1 = 1 2 3 1 3 1 and solving these in the normal way, we nd a solution = 1; = 0; =1. Thus 1 2 3 we delete v and we are left with just v ; v ; v . 8 2 4 7 Of course, the vectors that are removed during the sifting process depends very much on the order of the list of vectors. For example, if v had come at the beginning of the 8 list rather than at the end, then we would have kept it. The idea of sifting allows us to prove the following theorem, stating that every nite sequence of vectors which spans a vector space V actually contains a basis for V . Theorem 3.5. Suppose that the vectors v ;:::; v span the vector spaceV . Then there 1 r is a subsequence of v ;:::; v which forms a basis of V . 1 r Proof. We sift the vectors v ;:::; v . The vectors that we remove are linear combina- 1 r tions of the preceding vectors, and so by Lemma 3.4, the remaining vectors still span V . After sifting, no vector is zero or a linear combination of the preceding vectors (or it would have been removed), so by Lemma 3.1, the remaining vectors are linearly independent. Hence they form a basis of V . The theorem tells us that any vector space with a nite spanning set is nite- dimensional, and indeed the spanning set contains a basis. We now prove the dual result: any linearly independent set is contained in a basis. Theorem 3.6. Let V be a vector space over K which has a nite spanning set, and suppose that the vectors v ;:::; v are linearly independent in V . Then we can extend 1 r the sequence to a basis v ;:::; v of V , where nr. 1 n Proof. Suppose that w ;:::; w is a spanning set forV . We sift the combined sequence 1 q v ;:::; v ; w ;:::; w : 1 r 1 q Since w ;:::; w spanV , the whole sequence spansV . Sifting results in a basis forV as 1 q in the proof of Theorem 3.5. Since v ;:::; v are linearly independent, none of them can 1 r be a linear combination of the preceding vectors, and hence none of the v are deleted i in the sifting process. Thus the resulting basis contains v ;:::; v . 1 r 4 Example. The vectors v = (1; 2; 0; 2); v = (0; 1; 0; 2) are linearly independent in R . 1 2 4 Let us extend them to a basis ofR . The easiest thing is to append the standard basis 4 ofR , giving the combined list of vectors v = (1; 2; 0; 2); v = (0; 1; 0; 2); w = (1; 0; 0; 0); 1 2 1 w = (0; 1; 0; 0); w = (0; 0; 1; 0); w = (0; 0; 0; 1); 2 3 4 which we shall sift. We nd that (1; 0; 0; 0) = (1; 2; 0; 2)+ (0; 1; 0; 2) has no solution, 1 2 so w stays. However, w = v v w so w is deleted. It is clear that w is not a 1 2 1 2 1 2 3 linear combination of v ; v ; w , because all of those have a 0 in their third component. 1 2 1 Hence w remains. Now we have four linearly independent vectors, so must have a basis 3 at this stage, and we can stop the sifting early. The resulting basis is v = (1; 2; 0; 2); v = (0; 1; 0; 2); w = (1; 0; 0; 0); w = (0; 0; 1; 0): 1 2 1 3 We are now ready to prove Theorem 3.3. Since bases of V are both linearly inde- pendent and span V , the following proposition implies that any two bases contain the same number of vectors. 9Proposition 3.7 (The exchange lemma). Suppose that vectors v ;:::; v span V and 1 n that vectors w ;:::; w 2V are linearly independent. Then mn. 1 m Proof. The idea is to place the w one by one in front of the sequence v ;:::; v , sifting i 1 n each time. Since v ;:::; v span V , w ; v ;:::; v are linearly dependent, so when we sift, at 1 n 1 1 n least one v is deleted. We then place w in front of the resulting sequence and sift j 2 again. Then we put w in from of the result, and sift again, and carry on doing this 3 for each w in turn. Since w ;:::; w are linearly independent none of them are ever i 1 m deleted. Each time we place a vector in front of a sequence which spans V , and so the extended sequence is linearly dependent, and hence at least one v gets eliminated each j time. But in total, we append m vectors w , and each time at least one v is eliminated, i j so we must have mn. Corollary 3.8. Let V be a vector space of dimension n over K. Then any n vectors which span V form a basis of V , and no n 1 vectors can span V . Proof. After sifting a spanning sequence as in the proof of Theorem 3.5, the remaining vectors form a basis, so by Theorem 3.3, there must be precisely n = dim(V ) vectors remaining. The result is now clear. Corollary 3.9. Let V be a vector space of dimension n over K. Then any n linearly independent vectors form a basis of V and no n + 1 vectors can be linearly independent. Proof. By Theorem 3.6 any linearly independent set is contained in a basis but by Theorem 3.3, there must be precisely n = dim(V ) vectors in the extended set. The result is now clear. 3.4 Existence of a basis Although we have studied bases quite carefully in the previous section, we have not addressed the following fundamental question. LetV be a vector space. Does it contain a basis? Theorem 3.5 gives a partial answer that is good for many practical purposes. Let us formulate it as a corollary. Corollary 3.10. If a non-trivial vector spaceV is spanned by a nite number of vectors, then it has a basis. In fact, if we de ne the idea of an in nite basis carefully, then it can be proved that any vector space has a basis. That result will not be proved in this course. Its proof, which necessarily deals with in nite sets, requires a subtle result in axiomatic set theory called Zorn's lemma. 4 Subspaces Let V be a vector space over the eld K. Certain subsets of V have the nice property of being closed under addition and scalar multiplication; that is, adding or taking scalar multiples of vectors in the subset gives vectors which are again in the subset. We call such a subset a subspace: De nition. A subspace of V is a non-empty subset WV such that (i) W is closed under addition: u; v2W) u + v2W ; (ii) W is closed under scalar multiplication: v2W; 2K) v2W . These two conditions can be replaced with a single condition u; v2W; ; 2K) u + v2W: A subspace W is itself a vector space over K under the operations of vector ad- dition and scalar multiplication in V . Notice that all vector space axioms of W hold automatically. (They are inherited from V .) 102 Example. The subset ofR given by 2 W =f( ; )2R j = 2 g; that is, the subset consisting of all row vectors whose second entry is twice their rst 2 entry, is a subspace of R . You can check that adding two vectors of this form always gives another vector of this form; and multiplying a vector of this form by a scalar always gives another vector of this form. For any vector spaceV ,V is always a subspace of itself. Subspaces other thanV are sometimes called proper subspaces. We also always have a subspacef0g consisting of the zero vector alone. This is called the trivial subspace, and its dimension is 0, because it has no linearly independent sets of vectors at all. Intersecting two subspaces gives a third subspace: Proposition 4.1. If W and W are subspaces of V then so is W \W . 1 2 1 2 Proof. Let u; v2W \W and 2K. Then u + v2W (because W is a subspace) 1 2 1 1 and u + v2W (becauseW is a subspace). Hence u + v2W \W . Similarly, we get 2 2 1 2 v2W \W , so W \W is a subspace of V . 1 2 1 2 Warning It is not necessarily true that W W is a subspace, as the following 1 2 example shows. 2 Example. Let V =R , let W =f( ; 0)j 2Rg and W =f(0; )j 2Rg. Then 1 2 W ;W are subspaces of V , but W W is not a subspace, because (1; 0); (0; 1)2 1 2 1 2 W W , but (1; 0) + (0; 1) = (1; 1)62W W . 1 2 1 2 Note that any subspace of V that contains W and W has to contain all vectors of 1 2 the form u + v for u2W ; v2W . This motivates the following de nition. 1 2 De nition. LetW ;W be subspaces of the vector space V . Then W +W is de ned 1 2 1 2 to be the set of vectors v2 V such that v = w + w for some w 2 W ; w 2 W . 1 2 1 1 2 2 Or, if you prefer, W +W =fw + w j w 2W ; w 2Wg. 1 2 1 2 1 1 2 2 Do not confuse W +W with W W . 1 2 1 2 Proposition 4.2. If W ;W are subspaces of V then so is W +W . In fact, it is the 1 2 1 2 smallest subspace that contains both W and W . 1 2 Proof. Let u; v2 W +W . Then u = u + u for some u 2 W ; u 2 W and 1 2 1 2 1 1 2 2 v = v +v for some v 2W ; v 2W . Then u+v = (u +v )+(u +v )2W +W . 1 2 1 1 2 2 1 1 2 2 1 2 Similarly, if 2K then v = v + v 2W +W . Thus W +W is a subspace of 1 2 1 2 1 2 V . Any subspace of V that contains both W and W must contain W +W , so it is 1 2 1 2 the smallest such subspace. Theorem 4.3. Let V be a nite-dimensional vector space, and let W ;W be subspaces 1 2 of V . Then dim(W +W ) = dim(W ) + dim(W ) dim(W \W ): 1 2 1 2 1 2 Proof. First note that any subspace W of V is nite-dimensional. This follows from Corollary 3.9, because a largest linearly independent subset of W contains at most dim(V ) vectors, and such a subset must be a basis of W . Let dim(W \W ) =r and let e ;:::; e be a basis of W \W . Then e ;:::; e is 1 2 1 r 1 2 1 r a linearly independent set of vectors, so by Theorem 3.6 it can be extended to a basis e ;:::; e ,f ;:::; f ofW where dim(W ) =r +s, and it can also be extended to a basis 1 r 1 s 1 1 e ;:::; e ; g ;:::; g of W , where dim(W ) =r +t. 1 r 1 t 2 2 To prove the theorem, we need to show that dim(W +W ) =r +s +t, and to do 1 2 this, we shall show that e ;:::; e ; f ;:::; f ; g ;:::; g 1 r 1 s 1 t is a basis of W +W . Certainly they all lie in W +W . 1 2 1 2 11First we show that they span W +W . Any v2W +W is equal to w + w for 1 2 1 2 1 2 some w 2W ; w 2W : So we can write 1 1 2 2 w = e + + e + f + + f 1 1 1 r r 1 1 s s for some scalars ; 2K, and i j w = e + + e + g + + g 2 1 1 r r 1 1 t t for some scalars ; 2K. Then i j v = ( + )e + + ( + )e + f + + f + g + + g 1 1 1 r r r 1 1 s s 1 1 t t and so e ;:::; e ; f ;:::; f ; g ;:::; g span W +W . 1 r 1 s 1 t 1 2 Finally we have to show that e ;:::; e ; f ;:::; f ; g ;:::; g are linearly independent. 1 r 1 s 1 t Suppose that e + + e + f + + f + g + + g = 0 1 1 r r 1 1 s s 1 1 t t for some scalars ; ; 2K. Then i j k e + + e + f + + f = g  g () 1 1 r r 1 1 s s 1 1 t t The left-hand side of this equation lies inW and the right-hand side of this equation lies 1 inW . Since the two sides are equal, both must in fact lie in W \W . Since e ;:::; e 2 1 2 1 r is a basis of W \W , we can write 1 2  g  g = e + + e 1 1 t t 1 1 r r for some 2K, and so i e + + e + g + + g = 0: 1 1 r r 1 1 t t But, e ;:::; e ; g ;:::; g form a basis of W , so they are linearly independent, and 1 r 1 t 2 hence = 0 for 1 i r and  = 0 for 1 i t. But now, from the equation () i i above, we get e + + e + f + + f = 0: 1 1 r r 1 1 s s Now e ;:::; e ; f ;:::; f form a basis ofW , so they are linearly independent, and hence 1 r 1 s 1 = 0 for 1ir and = 0 for 1is. Thus e ;:::; e ; f ;:::; f ; g ;:::; g are i i 1 r 1 s 1 t linearly independent, which completes the proof that they form a basis of W +W . 1 2 Hence dim(W +W ) =r +s +t = (r +s) + (r +t)r = dim(W ) + dim(W ) dim(W \W ): 1 2 1 2 1 2 Another way to form subspaces is to take linear combinations of some given vectors: Proposition 4.4. Let v ;:::; v be vectors in the vector space V . Then the set of all 1 n linear combinations v + v + + v of v ;:::; v forms a subspace of V . 1 1 2 2 n n 1 n The proof of this is completely routine and will be omitted. The subspace in this proposition is known as the subspace spanned by v ;:::; v . 1 n De nition. Two subspaces W ;W of V are called complementary if W \W =f0g 1 2 1 2 and W +W =V . 1 2 Proposition 4.5. Let W ;W be subspaces of V . Then W ;W are complementary 1 2 1 2 subspaces if and only if each vector in v2 V can be written uniquely as v = w + w 1 2 with w 2W and w 2W . 1 1 2 2 12Proof. Suppose rst that W ;W are complementary subspaces and let v2 V . Then 1 2 W +W =V , so we can nd w 2W and w 2W with v = w + w . If we also had 1 2 1 1 2 2 1 2 0 0 0 0 0 0 v = w + w with w 2W ; w 2W , then we would have w w = w w . The 1 2 1 2 1 2 1 2 1 2 left-hand side lies in W and the right-hand side lies in W , and so both sides (being 1 2 0 equal) must lie in W \W =f0g. Hence both sides are zero, which means w = w 1 2 1 1 0 and w = w , so the expression is unique. 2 2 Conversely, suppose that every v2V can be written uniquely as v = w + w with 1 2 w 2 W and w 2 W . Then certainly W +W = V . If v was a non-zero vector in 1 1 2 2 1 2 W \W , then in fact v would have two distinct expressions as w + w with w 2W 1 2 1 2 1 1 and w 2W , one with w = v; w = 0 and the other with w = 0; w = v. Hence 2 2 1 2 1 2 W \W =f0g, and W and W are complementary. 1 2 1 2 Examples We give some examples of complementary subspaces. 2 1. As in the previous example, letV =R ,W =f( ; 0)j 2Rg andW =f(0; )j 1 2 2Rg. Then W and W are complementary subspaces. 1 2 3 2. Let V =R , W =f( ; 0; 0)j 2Rg and W =f(0; ; )j ; 2Rg. Then W 1 2 1 and W are complementary subspaces. 2 2 3. Let V =R , W =f( ; )j 2Rg and W =f( ; )j 2Rg. Then W and 1 2 1 W are complementary subspaces. 2 5 Linear transformations When you study sets, the notion of function is extremely important. There is little to say about a single isolated set, while functions allow you to link di erent sets. Similarly, in Linear Algebra, a single isolated vector space is not the end of the story. We have to connect di erent vector spaces by functions. However, a function having little regard to the vector space operations may be of little value. 5.1 De nition and examples Often in mathematics, it is as important to study special classes of functions as it is to study special classes of objects. Often these are functions which preserve certain properties or structures. For example, continuous functions preserve which points are close to which other points. In linear algebra, the functions which preserve the vector space structure are called linear transformations. De nition. LetU;V be two vector spaces over the same eldK. A linear transforma- tion or linear map T from U to V is a function T : UV such that (i) T (u + u ) =T (u ) +T (u ) for all u ; u 2U; 1 2 1 2 1 2 (ii) T ( u) = T (u) for all 2K and u2U. Notice that the two conditions for linearity are equivalent to a single condition T ( u + u ) = T (u ) + T (u ) for all u ; u 2U; ; 2K: 1 2 1 2 1 2 First let us state a couple of easy consequences of the de nition: Lemma 5.1. Let T : UV be a linear map. Then (i) T (0 ) = 0 ; U V (ii) T (u) =T (u) for all u2U. Proof. For (i), the de nition of linear map gives T (0 ) =T (0 + 0 ) =T (0 ) +T (0 ); U U U U U and thereforeT (0 ) = 0 . For (ii), just put =1 in the de nition of linear map. U V 13Examples Many familiar geometrical transformations, such as projections, rotations, re ections and magni cations are linear maps, and the rst three examples below are of this kind. Note, however, that a nontrivial translation is not a linear map, because it does not satisfy T (0 ) = 0 . U V 3 2 1. Let U =R ; V =R and de ne T : UV by T (( ; ; )) = ( ; ). Then T is a linear map. This type of map is known as a projection, because of the geometrical interpretation. z v  y     0  - T(v) X X X X X X x (Note: In future we shall just write T ( ; ; ) instead of T (( ; ; )).) 2 2 2. Let U = V = R . We interpret v in R as a directed line vector from 0 to v (see the examples in Section 2), and let T (v) be the vector obtained by rotating v through an angle  anti-clockwise about the origin. T (v)     v  1         0 It is easy to see geometrically that T (u + u ) = T (u ) +T (u ) and T ( u) = 1 2 1 2 T (u) (because everything is simply rotated about the origin), and so T is a linear map. By considering the unit vectors, we have T (1; 0) = (cos; sin) and T (0; 1) = ( sin; cos), and hence T ( ; ) = T (1; 0) + T (0; 1) = ( cos sin; sin + cos): (Exercise: Show this directly.) 2 3. Let U = V = R again. Now let T (v) be the vector resulting from re ecting v through a line through the origin that makes an angle =2 with the x-axis. T (v) 7J    J   J   J v  :           =2 0    This is again a linear map. We nd that T (1; 0) = (cos; sin) and T (0; 1) = (sin; cos), and so T ( ; ) = T (1; 0) + T (0; 1) = ( cos + sin; sin cos): 4. LetU =V =Rx, the set of polynomials overR, and letT be di erentiation; i.e. 0 T (p(x)) =p (x) for p2Rx. This is easily seen to be a linear map. 145. Let U = Kx, the set of polynomials over K. Every 2 K gives rise to two linear maps, shift S : U U; S (f(x)) = f(x ) and evaluation E : U K; E (f(x)) =f( ). The next two examples seem dull but are important 6. For any vector space V , we de ne the identity map I : V V by I (v) = v for V V all v2V . This is a linear map. 7. For any vector spacesU;V over the eldK, we de ne the zero map 0 : UV U;V by 0 (u) = 0 for all u2U. This is also a linear map. U;V V One of the most useful properties of linear maps is that, if we know how a linear map UV acts on a basis of U, then we know how it acts on the whole of U. Proposition 5.2 (Linear maps are uniquely determined by their action on a basis). Let U;V be vector spaces over K, let u ;:::; u be a basis of U and let v ;:::; v be 1 n 1 n any sequence of n vectors in V . Then there is a unique linear map T : U V with T (u ) = v for 1in. i i Proof. Let u2U. Then, since u ;:::; u is a basis ofU, by Proposition 3.2, there exist 1 n uniquely determined ;:::; 2K with u = u + + u . Hence, if T exists at 1 n 1 1 n n all, then we must have T (u) =T ( u + + u ) = v + + v ; 1 1 n n 1 1 n n and so T is uniquely determined. On the other hand, it is routine to check that the map T : U V de ned by the above equation is indeed a linear map, so T does exist and is unique. 5.2 Kernels and images To any linear map UV , we can associate a subspace of U and a subspace of V . De nition. Let T : UV be a linear map. The image of T , written as im(T ), is the set of vectors v2V such that v =T (u) for some u2U. De nition. The kernel of T , written as ker(T ), is the set of vectors u2 U such that T (u) = 0 . V If you prefer: im(T ) =fT (u)j u2Ug; ker(T ) =fu2UjT (u) = 0 g: V Examples Let us consider the examples 17 above. 2  In example 1, ker(T ) =f(0; 0; )j 2Rg; and im(T ) =R . 2  In example 2 and 3, ker(T ) =f0g and im(T ) =R .  In example 4, ker(T ) is the set of all constant polynomials (i.e. those of degree 0), and im(T ) =Rx.  In example 5, ker(S ) =f0g, and im(S ) = Kx, while ker(E ) is the set of all polynomials divisible by x , and im(E ) =K.  In example 6, ker(I ) =f0g and im(T ) =V . V  In example 7, ker(0 ) =U and im(0 ) =f0g. U;V U;V Proposition 5.3. Let T : UV be a linear map. Then (i) im(T ) is a subspace of V ; (ii) ker(T ) is a subspace of U. 15Proof. For i, we must show that im(T ) is closed under addition and scalar multiplication. Let v ; v 2 im(T ). Then v =T (u ); v =T (u ) for some u ; u 2U. Then 1 2 1 1 2 2 1 2 v + v =T (u ) +T (u ) =T (u + u )2 im(T ) 1 2 1 2 1 2 and v = T (u ) =T ( u )2 im(T ); 1 1 1 so im(T ) is a subspace of V . Let us now prove ii. Similarly,we must show that ker(T ) is closed under addition and scalar multiplication. Let u ; u 2 ker(T ). Then 1 2 T (u + u ) =T (0 + 0 ) =T (0 ) = 0 1 2 U U U V and T ( u ) = T (u ) = 0 = 0 ; 1 1 V V so u + u ; u 2 ker(T ) and ker(T ) is a subspace of U. 1 2 1 5.3 Rank and nullity The dimensions of the kernel and image of a linear map contain important information about it, and are related to each other. De nition. let T : UV be a linear map. (i) dim(im(T )) is called the rank of T ; (ii) dim(ker(T )) is called the nullity of T . Theorem 5.4 (The rank-nullity theorem). Let U;V be vector spaces over K with U nite-dimensional, and let T : UV be a linear map. Then rank(T ) + nullity(T ) = dim(U): Proof. Since U is nite-dimensional and ker(T ) is a subspace of U, ker(T ) is nite- dimensional. Let nullity(T ) =s and let e ;:::; e be a basis of ker(T ). By Theorem 3.6, 1 s we can extend e ;:::; e to a basis e ;:::; e ; f ;:::; f of U. Then dim(U) =s +r, so 1 s 1 s 1 r to prove the theorem we have to prove that dim(im(T )) =r. Clearly T (e );:::;T (e );T (f );:::;T (f ) span im(T ), and since 1 s 1 r T (e ) = =T (e ) = 0 1 s V this implies that T (f );:::;T (f ) span im(T ). We shall show that T (f );:::;T (f ) are 1 r 1 r linearly independent. Suppose that, for some scalars , we have i T (f ) + + T (f ) = 0 : 1 1 r r V ThenT ( f + + f ) = 0 , so f + + f 2 ker(T ). But e ;:::; e is a basis 1 1 r r V 1 1 r r 1 s of ker(T ), so there exist scalars with i f + + f = e + + e =) f + + f e  e = 0 : 1 1 r r 1 1 s s 1 1 r r 1 1 s s U But we know that e ;:::; e ; f ;:::; f form a basis ofU, so they are linearly independent, 1 s 1 r and hence = = = = = = 0; 1 r 1 s and we have proved that T (f );:::;T (f ) are linearly independent. 1 r Since T (f );:::;T (f ) both span im(T ) and are linearly independent, they form a 1 r basis of im(U), and hence dim(im(T )) =r, which completes the proof. 16Examples Once again, we consider examples 17 above. Since we only want to deal with nite-dimensional spaces, we restrict to an (n + 1)-dimensional space Kx in n examples 4 and 5, that is, we consider T : Rx Rx , S : Kx Kx , n n n n and E : Kx K correspondingly. Let n = dim(U) = dim(V ) in 5 and 6. n Example rank(T ) nullity(T ) dim(U) 1 2 1 3 2 2 0 2 3 2 0 2 4 n 1 n + 1 5 S n + 1 0 n + 1 4 E 1 n n + 1 6 n 0 n 7 0 n n Corollary 5.5. Let T : UV be a linear map, and suppose that dim(U) = dim(V ) = n. Then the following properties of T are equivalent: (i) T is surjective; (ii) rank(T ) =n; (iii) nullity(T ) = 0; (iv) T is injective; (v) T is bijective; Proof. That T is surjective means precisely that im(T ) = V , so (i)) (ii). But if rank(T ) = n, then dim(im(T )) = dim(V ) so (by Corollary 3.9) a basis of im(T ) is a basis of V , and hence im(T ) =V . Thus (ii), (i). That (ii), (iii) follows directly from Theorem 5.4. Now nullity(T ) = 0 means that ker(T ) =f0g so clearly (iv)) (iii). On the other hand, if ker(T ) =f0g and T (u ) =T (u ) then T (u u ) = 0, so u u 2 ker(T ) = 1 2 1 2 1 2 f0g, which implies u = u andT is injective. Thus (iii), (iv). (In fact, this argument 1 2 shows that (iii), (iv) is true for any linear map T .) Finally, (v) is equivalent to (i) and (iv), which we have shown are equivalent to each other. De nition. If the conditions in the above corollary are met, then T is called a non- singular linear map. Otherwise,T is called singular. Notice that the terms singular and non-singular are only used for linear mapsT : UV for whichU andV have the same dimension. 5.4 Operations on linear maps We can de ne the operations of addition, scalar multiplication and composition on linear maps. Let T : UV and T : UV be two linear maps, and let 2K be a scalar. 1 2 De nition (Addition of linear maps). We de ne a map T +T : UV 1 2 by the rule (T +T )(u) =T (u) +T (u) for u2U. 1 2 1 2 De nition (Scalar multiplication of linear maps). We de ne a map T : UV 1 by the rule ( T )(u) = T (u) for u2U. 1 1 Now let T : UV and T : V W be two linear maps. 1 2 17De nition (Composition of linear maps). We de ne a map T T : UW 2 1 by (T T )(u) =T (T (u)) for u2U. 2 1 2 1 2 i+1 i In particular, we de ne T =TT and T =T T for i 2. It is routine to check thatT +T , T andT T are themselves all linear maps (but 1 2 1 2 1 you should do it). Furthermore, for xed vector spaces U and V over K, the operations of addition and scalar multiplication on the set Hom (U;V ) of all linear maps from U toV makes K Hom (U;V ) into a vector space over K. K  Given a vector space U over a eld K, the vector space U = Hom (U;K) plays a K special role. It is often called the dual space or the space of covectors of U. One can  think of coordinates as elements of U . Indeed, let e be a basis ofU. Every x2U can i be uniquely written as x = e +::: e ; 2K: 1 1 n n i The elements depend on x as well as on a choice of the basis, so for each i one can i write the coordinate function i i e : UK; e (x) = : i i i It is routine to check that e is a linear map, and indeed the functions e form a basis  of the dual space U . 6 Matrices The material in this section will be familiar to many of you already, at least when K is the eld of real numbers. De nition. Let K be a eld and m;n2N. An mn matrix A over K is an mn rectangular array of numbers (i.e. scalars) in K. The entry in row i and column j is often written . (We use the corresponding Greek letter.) We writeA = ( ) to make ij ij things clear. For example, we could take 0 1 2 1  0 A K =R; m = 3; n = 4; A = ( ) = 3 3=2 0 6 ; ij 10 1:23 0 10 0 10 and then =, = 10 , = 0, and so on. 13 33 34 Having de ned what matrices are, we want to be able add them, multiply them by scalars, and multiply them by each other. You probably already know how to do this, but we will de ne these operations anyway. De nition (Addition of matrices). LetA = ( ) andB = ( ) be twomn matrices ij ij over K. We de ne A +B to be the mn matrix C = ( ), where = + for ij ij ij ij all i;j. Example.       1 3 2 3 1 0 + = : 0 2 1 4 1 2 De nition (Scalar multiplication of matrices). LetA = ( ) be anmn matrix over ij K and let 2K be a scalar. We de ne the scalar multiple A to be the mn matrix C = ( ), where = for all i;j. ij ij ij 18De nition (Multiplication of matrices). LetA = ( ) be anlm matrix overK and ij letB = ( ) be anmn matrix overK. The productAB is anln matrixC = ( ) ij ij where, for 1il and 1jn, m X = = + + + : ij ik kj i1 1j i2 2j im mj k=1 It is essential that the number m of columns of A is equal to the number of rows of B; otherwise AB makes no sense. If you are familiar with scalar products of vectors, note also that is the scalar ij product of the ith row of A with the jth column of B. Example. Let 0 1   2 6 2 3 4 A A = ; B = 3 2 : 1 6 2 1 9 Then     2 2 + 3 3 + 4 1 2 6 + 3 2 + 4 9 17 54 AB = = ; 1 2 + 6 3 + 2 1 1 6 + 6 2 + 2 9 22 36 0 1 10 42 20 A 8 21 16 BA = : 11 57 22   2 3 1 Let C = . Then AC and CA are not de ned. 6 2 9     1 2 4 15 8 Let D = . Then AD is not de ned, but DA = . 0 1 1 6 2 Proposition 6.1. Matrices satisfy the following laws whenever the sums and products involved are de ned: (i) A +B =B +A; (ii) (A +B)C =AC +BC; (iii) C(A +B) =CA +CB; (iv) (A)B =(AB) =A(B); (v) (AB)C =A(BC). Proof. These are all routine checks that the entries of the left-hand sides are equal to the corresponding entries on the right-hand side. Let us do (v) as an example. LetA,B andC belm,mn andnp matrices, respectively. ThenAB =D = ( ) ij P m is anln matrix with = , andBC =E = (" ) is anmp matrix with ij is sj ij s=1 P n " = . Then (AB)C =DC and A(BC) =AE are both lp matrices, and ij it tj t=1 we have to show that their coecients are equal. The (i;j)-coecient of DC is n n m m n m X XX X X X  = ( ) = ( ) = " it tj is st tj is st tj is sj t=1 t=1 s=1 s=1 t=1 s=1 which is the (i;j)-coecient of AE. Hence (AB)C =A(BC). There are some useful matrices to which we give names. De nition. Themn zero matrix 0 over any eldK has all of its entries equal to mn 0. De nition. The nn identity matrix I = ( ) over any eld K has = 1 for n ij ii 1in, but = 0 when i6=j. ij 19Example. 0 1   1 0 0 1 0 A I = (1); I = ; I = 0 1 0 : 1 2 3 0 1 0 0 1 Note that I A =A for any nm matrix A and AI =A for any mn matrix A. n n m;n m;n The set of all mn matrices over K will be denoted by K . Note that K is itself a vector space over K using the operations of addition and scalar multiplication de ned above, and it has dimension mn. (This should be obvious is it?) 1;n n A 1n matrix is called a row vector. We will regardK as being the same asK . n;1 A n 1 matrix is called a column vector. We will denote the the space K of all n;1 n;1 n column vectors by K . In matrix calculations, we will use K more often than K . 7 Linear transformations and matrices We shall see in this section that, for xed choice of bases, there is a very natural one-one correspondence between linear maps and matrices, such that the operations on linear maps and matrices de ned in Chapters 5 and 6 also correspond to each other. This is perhaps the most important idea in linear algebra, because it enables us to deduce properties of matrices from those of linear maps, and vice-versa. It also explains why we multiply matrices in the way we do. 7.1 Setting up the correspondence Let T : UV be a linear map, where dim(U) =n; dim(V ) =m. Suppose that we are given a basis e ;:::; e of U and a basis f ;:::; f of V . 1 n 1 m Now, for 1jn, the vector T (e ) lies in V , so T (e ) can be written uniquely as j j a linear combination of f ;:::; f . Let 1 m T (e ) = f + f + + f 1 11 1 21 2 m1 m T (e ) = f + f + + f 2 12 1 22 2 m2 m  T (e ) = f + f + + f n 1n 1 2n 2 mn m where the coecients 2 K (for 1 i m; 1 j n) are uniquely determined. ij Putting it more compactly, we de ne scalars by ij m X T (e ) = f for 1jn: j ij i i=1 The coecients form an mn matrix ij 0 1  11 12 1n B C  21 22 2n B C A = B C . . . . . . . . A . . . .  m1 m2 mn over K. Then A is called the matrix of the linear map T with respect to the chosen bases ofU andV . In general, di erent choice of bases gives di erent matrices. We shall address this issue later in the course, in Section 11. Notice the role of individual columns in A The jth column of A consists of the coordinates of T (e ) with respect to the basis vf ;:::; f of V . j 1 m Theorem 7.1. LetU;V be vector spaces overK of dimensionsn;m, respectively. Then, for a given choice of bases of U and V , there is a one-one correspondence between the m;n set Hom (U;V ) of linear maps UV and the set K of mn matrices over K. K 20

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.