Lecture notes for Numerical Linear Algebra

lecture notes on elementary linear algebra, lecture notes on probability statistics and linear algebra, advanced linear algebra lecture notes pdf linear algebra vector spaces lecture notes
Prof.SteveBarros Profile Pic
Prof.SteveBarros,United Kingdom,Teacher
Published Date:28-07-2017
Your Website URL(Optional)
Comment
Linear Algebra Done Wrong Sergei Treil Department of Mathematics, Brown UniversityChapter 1 Basic Notions 1. Vector spaces A vector space V is a collection of objects, called vectors (denoted in this book by lowercase bold letters, like v), along with two operations, addition 1 of vectors and multiplication by a number (scalar) , such that the following 8 properties (the so-called axioms of a vector space) hold: The rst 4 properties deal with the addition: 1. Commutativity: v + w = w + v for all v; w2V ; A question arises, \How one can mem- 2. Associativity: (u + v) + w = u + (v + w) for all u; v; w2V ; orize the above prop- 3. Zero vector: there exists a special vector, denoted by 0 such that erties?" And the an- v + 0 = v for all v2V ; swer is that one does not need to, see be- 4. Additive inverse: For every vector v2V there exists a vector w2V low such that v + w = 0. Such additive inverse is usually denoted as v; The next two properties concern multiplication: 5. Multiplicative identity: 1v = v for all v2V ; 1 We need some visual distinction between vectors and other objects, so in this book we use bold lowercase letters for vectors and regular lowercase letters for numbers (scalars). In some (more advanced) books Latin letters are reserved for vectors, while Greek letters are used for scalars; in even more advanced texts any letter can be used for anything and the reader must understand from the context what each symbol means. I think it is helpful, especially for a beginner to have some visual distinction between di erent objects, so a bold lowercase letters will always denote a vector. And on a blackboard an arrow (like inv) is used to identify a vector. 12 1. Basic Notions 6. Multiplicative associativity: ( )v = ( v) for all v2 V and all scalars , ; And nally, two distributive properties, which connect multipli- cation and addition: 7. (u + v) = u + v for all u; v2V and all scalars ; 8. ( + )v = v + v for all v2V and all scalars , . Remark. The above properties seem hard to memorize, but it is not nec- essary. They are simply the familiar rules of algebraic manipulations with numbers, that you know from high school. The only new twist here is that you have to understand what operations you can apply to what objects. You can add vectors, and you can multiply a vector by a number (scalar). Of course, you can do with number all possible manipulations that you have learned before. But, you cannot multiply two vectors, or add a number to a vector. Remark. It is easy to prove that zero vector 0 is unique, and that given v2V its additive inversev is also unique. It is also not hard to show using properties 5, 6 and 8 that 0 = 0v for any v2 V , and thatv = (1)v. Note, that to do this one still needs to use other properties of a vector space in the proofs, in particular properties 3 and 4. If the scalars are the usual real numbers, we call the space V a real vector space. If the scalars are the complex numbers, i.e. if we can multiply vectors by complex numbers, we call the space V a complex vector space. Note, that any complex vector space is a real vector space as well (if we can multiply by complex numbers, we can multiply by real numbers), but not the other way around. If you do not know It is also possible to consider a situation when the scalars are elements of what a eld is, do an arbitrary eldF. In this case we say thatV is a vector space over the eld not worry, since in F. Although many of the constructions in the book (in particular, everything this book we con- in Chapters 13) work for general elds, in this text we are considering only sider only the case real and complex vector spaces. of real and complex If we do not specify the set of scalars, or use a letter F for it, then the spaces. results are true for both real and complex spaces. If we need to distinguish real and complex cases, we will explicitly say which case we are considering. Note, that in the de nition of a vector space over an arbitrary eld, we require the set of scalars to be a eld, so we can always divide (without a remainder) by a non-zero scalar. Thus, it is possible to consider vector space over rationals, but not over the integers.1. Vector spaces 3 1.1. Examples. n Example. The spaceR consists of all columns of size n, 0 1 v 1 B C v 2 B C v = B C . . A . v n whose entries are real numbers. Addition and multiplication are de ned entrywise, i.e. 0 1 0 1 0 1 0 1 0 1 v v v w v +w 1 1 1 1 1 1 B C B C B C B C B C v v v w v +w 2 2 2 2 2 2 B C B C B C B C B C = ; + = B C B C B C B C B C . . . . . . . . . . A A A A A . . . . . v v v w v +w n n n n n n n Example. The spaceC also consists of columns of sizen, only the entries now are complex numbers. Addition and multiplication are de ned exactly n as in the case ofR , the only di erence is that we can now multiply vectors n by complex numbers, i.e.C is a complex vector space. n n Many results in this text are true for bothR andC . In such cases we n will use notationF . Example. The spaceM (also denoted asM ) ofmn matrices: the mn m;n addition and multiplication by scalars are de ned entrywise. If we allow only real entries (and so only multiplication only by reals), then we have a real vector space; if we allow complex entries and multiplication by complex numbers, we then have a complex vector space. Formally, we have to distinguish between between real and complex R C cases, i.e. write something like M or M . However, in most situa- m;n m;n tions there is no di erence between real and complex case, and there is no need to specify which case we are considering. If there is a di erence we say explicitly which case we are considering. Remark. As we mentioned above, the axioms of a vector space are just the familiar rules of algebraic manipulations with (real or complex) numbers, so if we put scalars (numbers) for the vectors, all axioms will be satis ed. Thus, the set R of real numbers is a real vector space, and the set C of complex numbers is a complex vector space. More importantly, since in the above examples all vector operations (addition and multiplication by a scalar) are performed entrywise, for these examples the axioms of a vector space are automatically satis ed because they are satis ed for scalars (can you see why?). So, we do not have to4 1. Basic Notions check the axioms, we get the fact that the above examples are indeed vector spaces for free The same can be applied to the next example, the coecients of the polynomials play the role of entries there. Example. The spaceP of polynomials of degree at most n, consists of all n polynomials p of form 2 n p(t) =a +a t +a t +::: +a t ; 0 1 2 n wheret is the independent variable. Note, that some, or even all, coecients a can be 0. k In the case of real coecients a we have a real vector space, complex k coecient give us a complex vector space. Again, we will specify whether we treating real or complex case only when it is essential; otherwise everything applies to both cases. Question: What are zero vectors in each of the above examples? 1.2. Matrix notation. An mn matrix is a rectangular array with m rows andn columns. Elements of the array are called entries of the matrix. It is often convenient to denote matrix entries by indexed letters: the rst index denotes the number of the row, where the entry is, and the second one is the number of the column. For example 0 1 a a ::: a 1;1 1;2 1;n B C a a ::: a 2;1 2;2 2;n B C m; n (1.1) A = (a ) = B C j;k . . . k=1 j=1; . . . A . . . a a ::: a m;1 m;2 m;n is a general way to write an mn matrix. Very often for a matrixA the entry in row numberj and column number k is denoted byA or (A) , and sometimes as in example (1.1) above the j;k j;k same letter but in lowercase is used for the matrix entries. T Given a matrix A, its transpose (or transposed matrix) A , is de ned by transforming the rows of A into the columns. For example 0 1   T 1 4 1 2 3 A = 2 5 : 4 5 6 3 6 T T So, the columns of A are the rows of A and vice versa, the rows of A are the columns of A. T The formal de nition is as follows: (A ) = (A) meaning that the j;k k;j T entry of A in the row number j and column number k equals the entry of A in the row number k and row number j.1. Vector spaces 5 The transpose of a matrix has a very nice interpretation in terms of linear transformations, namely it gives the so-called adjoint transformation. We will study this in detail later, but for now transposition will be just a useful formal operation. One of the rst uses of the transpose is that we can write a column n T vector x2F (recall that F is R or C) as x = (x ;x ;:::;x ) . If we put 1 2 n the column vertically, it will use signi cantly more space. Exercises. T T T 1.1. Let x = (1; 2; 3) , y = (y ;y ;y ) , z = (4; 2; 1) . Compute 2x, 3y, x + 2y 1 2 3 3z. 1.2. Which of the following sets (with natural addition and multiplication by a scalar) are vector spaces. Justify your answer. a) The set of all continuous functions on the interval 0; 1; b) The set of all non-negative functions on the interval 0; 1; c) The set of all polynomials of degree exactly n; d) The set of all symmetric n n matrices, i.e. the set of matrices A = n T fa g such that A =A. j;k j;k=1 1.3. True or false: a) Every vector space contains a zero vector; b) A vector space can have more than one zero vector; c) An mn matrix has m rows and n columns; d) If f and g are polynomials of degree n, then f +g is also a polynomial of degree n; e) If f and g are polynomials of degree at most n, then f + g is also a polynomial of degree at most n 1.4. Prove that a zero vector 0 of a vector space V is unique. 1.5. What matrix is the zero vector of the space M ? 23 1.6. Prove that the additive inverse, de ned in Axiom 4 of a vector space is unique. 1.7. Prove that 0v = 0 for any vector v2V . 1.8. Prove that for any vector v its additive inversev is given by (1)v.6 1. Basic Notions 2. Linear combinations, bases. LetV be a vector space, and let v ; v ;:::; v 2V be a collection of vectors. 1 2 p A linear combination of vectors v ; v ;:::; v is a sum of form 1 2 p p X v + v +::: + v = v : 1 1 2 2 p p k k k=1 De nition 2.1. A system of vectors v ; v ;::: v 2V is called a basis (for 1 2 n the vector space V ) if any vector v2V admits a unique representation as a linear combination n X v = v + v +::: + v = v : 1 1 2 2 n n k k k=1 The coecients ; ;:::; are called coordinates of the vector v (in the 1 2 n basis, or with respect to the basis v ; v ;:::; v ). 1 2 n Another way to say that v ; v ;:::; v is a basis is to say that for any 1 2 n possible choice of the right side v, the equationx v +x v +:::+x v = v 1 1 2 2 m n (with unknowns x ) has a unique solution. k 2 Before discussing any properties of bases , let us give a few examples, showing that such objects exist, and that it makes sense to study them. n Example 2.2. In the rst example the space V isF , whereF is eitherR orC. Consider vectors 0 1 0 1 0 1 0 1 1 0 0 0 B C B C B C B C 0 1 0 0 B C B C B C B C B C B C B C B C 0 0 1 0 e =B C; e =B C; e =B C;:::; e =B C; 1 2 3 n B C B C B C B C . . . . . . . . A A A A . . . . 0 0 0 1 (the vector e has all entries 0 except the entry number k, which is 1). The k n system of vectors e ; e ;:::; e is a basis inF . Indeed, any vector 1 2 n 0 1 x 1 B C x 2 B C n v =B C2F . . A . x n can be represented as the linear combination n X v =x e +x e +:::x e = x e 1 1 2 2 n n k k k=1 2 the plural for the \basis" is bases, the same as the plural for \base"2. Linear combinations, bases. 7 n and this representation is unique. The system e ; e ;:::; e 2F is called 1 2 n n the standard basis inF Example 2.3. In this example the space is the spaceP of the polynomials n of degree at most n. Consider vectors (polynomials) e ; e ; e ;:::; e 2P 0 1 2 n n de ned by 2 3 n e := 1; e :=t; e :=t ; e :=t ; :::; e :=t : 0 1 2 3 n 2 n Clearly, any polynomialp,p(t) =a +a t+a t +:::+a t admits a unique 0 1 2 n representation p =a e +a e +::: +a e : 0 0 1 1 n n So the system e ; e ; e ;:::; e 2 P is a basis in P . We will call it the 0 1 2 n n n standard basis inP . n Remark 2.4. If a vector spaceV has a basis v ; v ;:::; v , then any vector 1 2 n P n v is uniquely de ned by its coecients in the decomposition v = v . This is a very im- k k k=1 portant remark, that So, if we stack the coecients in a column, we can operate with them k n will be used through- as if they were column vectors, i.e. as with elements of F (again hereF is out the book. It al- eitherR orC, but everything also works for an abstract eldF). lows us to translate P P n n Namely, if v = v and w = v , then k k k k any statement about k=1 k=1 the standard column n n n X X X n space F to a vector v + w = v + v = ( + )v ; k k k k k k k spaceV with a basis k=1 k=1 k=1 v ; v ;:::; v 1 2 n i.e. to get the column of coordinates of the sum one just need to add the columns of coordinates of the summands. Similarly, to get the coordinates of v we need simply to multiply the column of coordinates of v by . 2.1. Generating and linearly independent systems. The de nition of a basis says that any vector admits a unique representation as a linear combination. This statement is in fact two statements, namely that the rep- resentation exists and that it is unique. Let us analyze these two statements separately. If we only consider the existence we get the following notion De nition 2.5. A system of vectors v ; v ;:::; v 2V is called a generating 1 2 p system (also a spanning system, or a complete system) in V if any vector v2V admits representation as a linear combination p X v = v + v +::: + v = v : 1 1 2 2 p p k k k=1 The only di erence from the de nition of a basis is that we do not assume that the representation above is unique.8 1. Basic Notions The words generating, spanning and complete here are synonyms. I per- sonally prefer the term complete, because of my operator theory background. Generating and spanning are more often used in linear algebra textbooks. Clearly, any basis is a generating (complete) system. Also, if we have a basis, say v ; v ;:::; v , and we add to it several vectors, say v ;:::; v , 1 2 n n+1 p then the new system will be a generating (complete) system. Indeed, we can represent any vector as a linear combination of the vectors v ; v ;:::; v , 1 2 n and just ignore the new ones (by putting corresponding coecients = 0). k Now, let us turn our attention to the uniqueness. We do not want to worry about existence, so let us consider the zero vector 0, which always admits a representation as a linear combination. De nition. A linear combination v + v +::: + v is called trivial 1 1 2 2 p p if = 08k. k A trivial linear combination is always (for all choices of vectors v ; v ;:::; v ) equal to 0, and that is probably the reason for the name. 1 2 p De nition. A system of vectors v ; v ;:::; v 2 V is called linearly inde- 1 2 p P p pendent if only the trivial linear combination ( v with = 08k) k k k k=1 of vectors v ; v ;:::; v equals 0. 1 2 p In other words, the system v ; v ;:::; v is linearly independent i the 1 2 p equation x v +x v +::: +x v = 0 (with unknowns x ) has only trivial 1 1 2 2 p p k solution x =x =::: =x = 0. 1 2 p If a system is not linearly independent, it is called linearly dependent. By negating the de nition of linear independence, we get the following De nition. A system of vectors v ; v ;:::; v is called linearly dependent 1 2 p P p if 0 can be represented as a nontrivial linear combination, 0 = v . k k k=1 Non-trivial here means that at least one of the coecient is non-zero. k P p This can be (and usually is) written as j j6= 0. k k=1 So, restating the de nition we can say, that a system is linearly depen- P p dent if and only if there exist scalars ; ;:::; , j j6= 0 such 1 2 p k k=1 that p X v = 0: k k k=1 An alternative de nition (in terms of equations) is that a system v ; 1 v ;:::; v is linearly dependent i the equation 2 p x v +x v +::: +x v = 0 1 1 2 2 p p (with unknowns x ) has a non-trivial solution. Non-trivial, once again k means that at least one of x is di erent from 0, and it can be written k P p as jxj6= 0. k k=12. Linear combinations, bases. 9 The following proposition gives an alternative description of linearly de- pendent systems. Proposition 2.6. A system of vectors v ; v ;:::; v 2 V is linearly de- 1 2 p pendent if and only if one of the vectors v can be represented as a linear k combination of the other vectors, p X (2.1) v = v : k j j j=1 j6=k Proof. Suppose the system v ; v ;:::; v is linearly dependent. Then there 1 2 p P p exist scalars , j j6= 0 such that k k k=1 v + v +::: + v = 0: 1 1 2 2 p p Let k be the index such that 6= 0. Then, moving all terms except v k k k to the right side we get p X v = v : k k j j j=1 j=6 k Dividing both sides by we get (2.1) with = = . j j k k On the other hand, if (2.1) holds, 0 can be represented as a non-trivial linear combination p X v v = 0: j j k j=1 j6=k  Obviously, any basis is a linearly independent system. Indeed, if a system v ; v ;:::; v is a basis, 0 admits a unique representation 1 2 n n X 0 = v + v +::: + v = v : 1 1 2 2 n n k k k=1 Since the trivial linear combination always gives 0, the trivial linear combi- nation must be the only one giving 0. So, as we already discussed, if a system is a basis it is a complete (gen- erating) and linearly independent system. The following proposition shows that the converse implication is also true. Proposition 2.7. A system of vectors v ; v ;:::; v 2V is a basis if and In many textbooks 1 2 n a basis is de ned only if it is linearly independent and complete (generating). as a complete and linearly independent system. By Propo- sition 2.7 this de ni- tion is equivalent to ours.10 1. Basic Notions Proof. We already know that a basis is always linearly independent and complete, so in one direction the proposition is already proved. Let us prove the other direction. Suppose a system v ; v ;:::; v is lin- 1 2 n early independent and complete. Take an arbitrary vector v2V . Since the system v ; v ;:::; v is linearly complete (generating), v can be represented 1 2 n as n X v = v + v +::: + v = v : 1 1 2 2 n n k k k=1 We only need to show that this representation is unique. Suppose v admits another representation n X v = e v : k k k=1 Then n n n X X X ( e )v = v e v = v v = 0: k k k k k k k k=1 k=1 k=1 Since the system is linearly independent, e = 08k, and thus the k k representation v = v + v +::: + v is unique.  1 1 2 2 n n Remark. In many textbooks a basis is de ned as a complete and linearly independent system (by Proposition 2.7 this de nition is equivalent to ours). Although this de nition is more common than one presented in this text, I prefer the latter. It emphasizes the main property of a basis, namely that any vector admits a unique representation as a linear combination. Proposition 2.8. Any ( nite) generating system contains a basis. Proof. Suppose v ; v ;:::; v 2 V is a generating (complete) set. If it is 1 2 p linearly independent, it is a basis, and we are done. Suppose it is not linearly independent, i.e. it is linearly dependent. Then there exists a vector v which can be represented as a linear combination of k the vectors v , j =6 k. j Since v can be represented as a linear combination of vectors v ,j =6 k, k j any linear combination of vectors v ; v ;:::; v can be represented as a linear 1 2 p combination of the same vectors without v (i.e. the vectors v , 1jp, k j j =6 k). So, if we delete the vector v , the new system will still be a complete k one. If the new system is linearly independent, we are done. If not, we repeat the procedure. Repeating this procedure nitely many times we arrive to a linearly independent and complete system, because otherwise we delete all vectors and end up with an empty set.2. Linear combinations, bases. 11 So, any nite complete (generating) set contains a complete linearly independent subset, i.e. a basis.  Exercises. 2.1. Find a basis in the space of 3 2 matrices M . 32 2.2. True or false: a) Any set containing a zero vector is linearly dependent b) A basis must contain 0; c) subsets of linearly dependent sets are linearly dependent; d) subsets of linearly independent sets are linearly independent; e) If v + v +::: + v = 0 then all scalars are zero; 1 1 2 2 n n k T 2.3. Recall, that a matrix is called symmetric ifA =A. Write down a basis in the space of symmetric 2 2 matrices (there are many possible answers). How many elements are in the basis? 2.4. Write down a basis for the space of a) 3 3 symmetric matrices; b) nn symmetric matrices; T c) nn antisymmetric (A =A) matrices; 2.5. Let a system of vectors v ; v ;:::; v be linearly independent but not gen- 1 2 r erating. Show that it is possible to nd a vector v such that the system r+1 v ; v ;:::; v ; v is linearly independent. Hint: Take for v any vector that 1 2 r r+1 r+1 P r cannot be represented as a linear combination v and show that the system k k k=1 v ; v ;:::; v ; v is linearly independent. 1 2 r r+1 2.6. Is it possible that vectors v ; v ; v are linearly dependent, but the vectors 1 2 3 w = v + v , w = v + v and w = v + v are linearly independent? 1 1 2 2 2 3 3 3 112 1. Basic Notions 3. Linear Transformations. Matrixvector multiplication The words \trans- A transformation T from a setX to a setY is a rule that for each argument formation", \trans- (input) x2X assigns a value (output) y =T (x)2Y . form", \mapping", The set X is called the domain of T , and the set Y is called the target \map", \operator", space or codomain of T . \function" all denote the same object. We writeT :XY to say thatT is a transformation with the domain X and the target space Y . De nition. LetV ,W be vector spaces (over the same eldF). A transfor- mation T :V W is called linear if 1. T (u + v) =T (u) +T (v)8u; v2V ; 2. T ( v) = T (v) for all v2V and for all scalars 2F. Properties 1 and 2 together are equivalent to the following one: T ( u + v) = T (u) + T (v) for all u; v2V and for all scalars ; : 3.1. Examples. You dealt with linear transformation before, may be with- out even suspecting it, as the examples below show. Example. Di erentiation: LetV =P (the set of polynomials of degree at n most n), W =P , and let T :P P be the di erentiation operator, n1 n n1 0 T (p) :=p 8p2P : n 0 0 0 0 0 Since (f +g) =f +g and ( f) = f , this is a linear transformation. 2 Example. Rotation: in this example V = W = R (the usual coordinate 2 2 2 plane), and a transformation T :R R takes a vector inR and rotates it counterclockwise by radians. Since T rotates the plane as a whole, it rotates as a whole the parallelogram used to de ne a sum of two vectors (parallelogram law). Therefore the property 1 of linear transformation holds. It is also easy to see that the property 2 is also true. 2 Example. Re ection: in this example again V =W =R , and the trans- 2 2 formation T :R R is the re ection in the rst coordinate axis, see the g. It can also be shown geometrically, that this transformation is linear, but we will use another way to show that. Namely, it is easy to write a formula for T ,       x x 1 1 T = x x 2 2 and from this formula it is easy to check that the transformation is linear. 3. Linear Transformations. Matrixvector multiplication 13 Figure 1. Rotation Example. Let us investigate linear transformations T :RR. Any such transformation is given by the formula T (x) =ax where a =T (1): Indeed, T (x) =T (x 1) =xT (1) =xa =ax: So, any linear transformation ofR is just a multiplication by a constant. n m 3.2. Linear transformations F F . Matrixcolumn multiplica- n m tion. It turns out that a linear transformation T : F F also can be represented as a multiplication, not by a scalar, but by a matrix. n m Let us see how. Let T : F F be a linear transformation. What n information do we need to computeT (x) for all vectors x2F ? My claim is that it is sucient to know how T acts on the standard basis e ; e ;:::; e 1 2 n n m of F . Namely, it is sucient to know n vectors in F (i.e. the vectors of size m), a =T (e ); a :=T (e ); ::: ; a :=T (e ): 1 1 2 2 n n14 1. Basic Notions Indeed, let 0 1 x 1 B C x 2 B C x =B C: . . A . x n P n Then x =x e +x e +::: +x e = x e and 1 1 2 2 n n k k k=1 n n n n X X X X T (x) =T ( x e ) = T (x e ) = x T (e ) = x a : k k k k k k k k k=1 k=1 k=1 k=1 So, if we join the vectors (columns) a ; a ;:::; a together in a matrix 1 2 n A = a ; a ;:::; a (a being the kth column of A, k = 1; 2;:::;n), this 1 2 n k matrix contains all the information about T . Let us show how one should de ne the product of a matrix and a vector (column) to represent the transformation T as a product, T (x) =Ax. Let 0 1 a a ::: a 1;1 1;2 1;n B C a a ::: a 2;1 2;2 2;n B C A =B C: . . . . . . A . . . a a ::: a m;1 m;2 m;n Recall, that the column number k of A is the vector a , i.e. k 0 1 a 1;k B C a 2;k B C a = : B C k . . A . a m;k Then if we want Ax =T (x) we get 0 1 0 1 0 1 a a a 1;1 1;2 1;n n B C B C B C X a a a 2;1 2;2 2;n B C B C B C Ax = x a =x +x +::: +x : B C B C B C k k 1 . 2 . n . . . . A A A . . . k=1 a a a m;1 m;2 m;n So, the matrixvector multiplication should be performed by the follow- ing column by coordinate rule: multiply each column of the matrix by the corresponding coordi- nate of the vector. Example. 0 1           1 1 2 3 1 2 3 14 A 2 = 1 + 2 + 3 = : 3 2 1 3 2 1 10 33. Linear Transformations. Matrixvector multiplication 15 The \column by coordinate" rule is very well adapted for parallel com- puting. It will be also very important in di erent theoretical constructions later. However, when doing computations manually, it is more convenient to compute the result one entry at a time. This can be expressed as the fol- lowing row by column rule: To get the entry numberk of the result, one need to multiply row number k of the matrix by the vector, that is, if Ax = y, then P n y = a x , k = 1; 2;:::m; k k;j j j=1 here x and y are coordinates of the vectors x and y respectively, and a j k j;k are the entries of the matrix A. Example. 0 1       1 1 2 3 1 1 + 2 2 + 3 3 14 A 2 = = 4 5 6 4 1 + 5 2 + 6 3 32 3 3.3. Linear transformations and generating sets. As we discussed n m above, linear transformationT (acting fromF toF ) is completely de ned n by its values on the standard basis inF . The fact that we consider the standard basis is not essential, one can consider any basis, even any generating (spanning) set. Namely, A linear transformation T : V W is completely de ned by its values on a generating set (in particular by its values on a basis). So, if v ; v ;:::; v is a generating set (in particular, if it is a basis) in V , 1 2 n and T and T are linear transformations T;T :V W such that 1 1 Tv =T v ; k = 1; 2;:::;n k 1 k then T =T . 1 The proof of this statement is trivial and left as an exercise. 3.4. Conclusions. n m  To get the matrix of a linear transformationT :F F one needs to join the vectors a = Te (where e ; e ;:::; e is the standard k k 1 2 n n basis in F ) into a matrix: kth column of the matrix is a , k = k 1; 2;:::;n.  If the matrix A of the linear transformation T is known, then T (x) can be found by the matrixvector multiplication, T (x) = Ax. To perform matrixvector multiplication one can use either \column by coordinate" or \row by column" rule.16 1. Basic Notions The latter seems more appropriate for manual computations. The former is well adapted for parallel computers, and will be used in di erent theoretical constructions. n m For a linear transformation T :F F , its matrix is usually denoted as T . However, very often people do not distinguish between a linear trans- formation and its matrix, and use the same symbol for both. When it does not lead to confusion, we will also use the same symbol for a transformation and its matrix. The notation Tv is Since a linear transformation is essentially a multiplication, the notation often used instead of Tv is often used instead of T (v). We will also use this notation. Note that T (v). the usual order of algebraic operations apply, i.e. Tv + u means T (v) + u, not T (v + u). In the matrix vector Remark. In the matrixvector multiplication Ax the number of columns multiplication using of the matrix A matrix must coincide with the size of the vector x, i.e. a n the \row by column" vector inF can only be multiplied by an mn matrix. rule be sure that you It makes sense, since an mn matrix de nes a linear transformation have the same num- n m n F F , so vector x must belong toF . ber of entries in the row and in the col- The easiest way to remember this is to remember that if performing umn. The entries multiplication you run out of some elements faster, then the multiplication in the row and in is not de ned. For example, if using the \row by column" rule you run the column should out of row entries, but still have some unused entries in the vector, the end simultaneously: multiplication is not de ned. It is also not de ned if you run out of vector's if not, the multipli- entries, but still have unused entries in the row. cation is not de ned. n Remark. One does not have to restrict himself to the case of F with standard basis: everything described in this section works for transformation between arbitrary vector spaces as long as there is a basis in the domain and in the target space. Of course, if one changes a basis, the matrix of the linear transformation will be di erent. This will be discussed later in Section 8. Exercises. 3.1. Multiply: 0 1   1 1 2 3 A a) 3 ; 4 5 6 2 0 1   1 2 1 A b) 0 1 ; 3 2 0 0 10 1 1 2 0 0 1 B CB C 0 1 2 0 2 B CB C c) ; A A 0 0 1 2 3 0 0 0 1 44. Linear transformations as a vector space 17 0 10 1 1 2 0 1 B CB C 0 1 2 2 B CB C d) . A A 0 0 1 3 0 0 0 4 2 3.2. Let a linear transformation in R be the re ection in the line x =x . Find 1 2 its matrix. 3.3. For each linear transformation below nd it matrix 2 3 T T a) T :R R de ned by T (x;y) = (x + 2y; 2x 5y; 7y) ; 4 3 T b) T :R R de ned byT (x ;x ;x ;x ) = (x +x +x +x ;x x ;x + 1 2 3 4 1 2 3 4 2 4 1 T 3x + 6x ) ; 2 4 0 c) T :P P , Tf(t) =f (t) ( nd the matrix with respect to the standard n n 2 n basis 1;t;t ;:::;t ); 0 00 d) T :P P , Tf(t) = 2f(t) + 3f (t) 4f (t) (again with respect to the n n 2 n standard basis 1;t;t ;:::;t ). 3 3.4. Find 3 3 matrices representing the transformations ofR which: a) project every vector onto x-y plane; b) re ect every vector through x-y plane;  c) rotate the x-y plane through 30 , leaving z-axis alone. 3.5. Let A be a linear transformation. If z is the center of the straight interval x; y, show that Az is the center of the interval Ax;Ay. Hint: What does it mean that z is the center of the interval x; y? 2 3.6. The setC of complex numbers can be canonically identi ed with the spaceR T 2 by treating each z =x +iy2C as a column (x;y) 2R . a) Treating C as a complex vector space, show that the multiplication by =a +ib2C is a linear transformation inC. What is its matrix? 2 b) Treating C as the real vector space R show that the multiplication by =a +ib de nes a linear transformation there. What is its matrix? c) De neT (x+iy) = 2xy +i(x3y). Show that this transformation is not a linear transformation in the complex vectors space C, but if we treat C 2 as the real vector spaceR then it is a linear transformation there (i.e. that T is a real linear but not a complex linear transformation). Find the matrix of the real liner transformation T . 3.7. Show that any linear transformation inC (treated as a complex vector space) is a multiplication by 2C. 4. Linear transformations as a vector space What operations can we perform with linear transformations? We can al- ways multiply a linear transformation for a scalar, i.e. if we have a linear18 1. Basic Notions transformation T :V W and a scalar we can de ne a new transforma- tion T by ( T )v = (Tv) 8v2V: It is easy to check that T is also a linear transformation: ( T )( v + v ) = (T ( v + v )) by the de nition of T 1 1 2 2 1 1 2 2 = ( Tv + Tv ) by the linearity of T 1 1 2 2 = Tv + Tv = ( T )v + ( T )v 1 1 2 2 1 1 2 2 IfT andT are linear transformations with the same domain and target 1 2 space (T : V W and T : V W , or in short T ;T : V W ), 1 2 1 2 then we can add these transformations, i.e. de ne a new transformation T = (T +T ) :V W by 1 2 (T +T )v =T v +T v 8v2V: 1 2 1 2 It is easy to check that the transformation T +T is a linear one, one just 1 2 needs to repeat the above reasoning for the linearity of T . So, if we x vector spaces V and W and consider the collection of all linear transformations from V to W (let us denote it byL(V;W )), we can de ne 2 operations onL(V;W ): multiplication by a scalar and addition. It can be easily shown that these operations satisfy the axioms of a vector space, de ned in Section 1. This should come as no surprise for the reader, since axioms of a vector space essentially mean that operation on vectors follow standard rules of algebra. And the operations on linear transformations are de ned as to satisfy these rules As an illustration, let us write down a formal proof of the rst distribu- tive law (axiom 7) of a vector space. We want to show that (T +T ) = 1 2 T + T . For any v2V 1 2 (T +T )v = ((T +T )v) by the de nition of multiplication 1 2 1 2 = (T v +T v) by the de nition of the sum 1 2 = T v + T v by Axiom 7 for W 1 2 = ( T + T )v by the de nition of the sum 1 2 So indeed (T +T ) = T + T . 1 2 1 2 Remark. Linear operations (addition and multiplication by a scalar) on n m linear transformationsT :F F correspond to the respective operations on their matrices. Since we know that the set of mn matrices is a vector n m space, this immediately implies thatL(F ;F ) is a vector space. We presented the abstract proof above, rst of all because it work for general spaces, for example, for spaces without a basis, where we cannot5. Composition of linear transformations and matrix multiplication. 19 work with coordinates. Secondly, the reasonings similar to the abstract one presented here, are used in many places, so the reader will bene t from understanding it. And as the reader gains some mathematical sophistication, he/she will see that this abstract reasoning is indeed a very simple one, that can be performed almost automatically. 5. Composition of linear transformations and matrix multiplication. 5.1. De nition of the matrix multiplication. Knowing matrixvector multiplication, one can easily guess what is the natural way to de ne the productAB of two matrices: Let us multiply byA each column ofB (matrix- vector multiplication) and join the resulting column-vectors into a matrix. Formally, if b ; b ;:::; b are the columns ofB, thenAb ;Ab ;:::;Ab are 1 2 r 1 2 r the columns of the matrix AB. Recalling the row by column rule for the matrixvector multiplication we get the following row by column rule for the matrices the entry (AB) (the entry in the row j and column k) of the j;k product AB is de ned by (AB) = (row j of A) (column k of B) j;k Formally it can be rewritten as X (AB) = a b ; j;k j;l l;k l if a and b are entries of the matrices A and B respectively. j;k j;k I intentionally did not speak about sizes of the matrices A and B, but if we recall the row by column rule for the matrixvector multiplication, we can see that in order for the multiplication to be de ned, the size of a row of A should be equal to the size of a column of B. In other words the product AB is de ned if and only if A is an mn and B is nr matrix. 5.2. Motivation: composition of linear transformations. One can ask yourself here: Why are we using such a complicated rule of multiplica- tion? Why don't we just multiply matrices entrywise? And the answer is, that the multiplication, as it is de ned above, arises naturally from the composition of linear transformations.

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