Injective and surjective functions

1 LECTURE 18: Injective AND surjective functions ANDTRANSFORMATIONSMA1111: LINEAR ALGEBRA I, MICHAELMAS and surjective functionsThere are two types of special properties of functions which are important in manydifferent mathematical theories, and which you may have seen. The first property werequire is the notion of an Injective functionffrom a setXto a setYisinjective(also called one-to-one)if distinct inputs map to distinct outputs, that is, iff(x1) =f(x2)impliesx1=x2for anyx1, x2 functionf:R Rgiven byf(x) =x2is not Injective as, ,( 1)2= 12= 1. In general, you can tell if functions like this are one-to-one by usingthehorizontal line test; if a horizontal line ever intersects the graph in two differ-ent places, the real-valued function is not Injective .

2 In this example, it is clear that theparabola can intersect a horizontal line at more than one projection operatorT:R2 R2withT(x, y) = (x,0)isn t Injective , asmany points can project to the same point on dual notion which we shall require is that of surjective functionf:X Yissurjective(also called onto) if every elementy Yis in the image off, that is, if for anyy Y, there is somex Xwithf(x) = examplef(x) =x2as a function fromR Ris also not onto, asnegative numbers aren t squares of real numbers. For example, the square root of 1isn t a real number. However, like every function, this is sujective when we changeYtobe the image of the map. In this case,f(x) =x2can also be considered as a map fromRto the set of non-negative real numbers, and it is then a surjective function.

3 Thus,note that injectivity of functions is typically well-defined, whereas the same function canbe thought of as mapping into possible many different setsY(although we will typicallyuse the same letter for the function anyways), and whether the function is surjective ornot will depend on this : November 18, : LINEAR ALGEBRA I, MICHAELMAS linear transformation which rotates vectors inR2by a fixed angle ,which we discussed last time, is a surjective operator fromR2 R2. To see this, notethat we can find a preimage of any vector by undoing the rotation and rotatingclockwiseby the same angle .Finally, we will call a functionbijective(also called a one-to-one correspondence)if it is both Injective and surjective .

4 It is not hard to show, but a crucial fact is thatfunctions have inverses (with respect to function composition) if and only if they bijection from a finite set to itself is just a permutation. Specifically, ifXis a finite set withnelements, we might as well label its elements as1,2, .. n(if youtake the elements of a set and paint them green, it doesn t change anything about theset), and then the permutations which we discussed before are precisely the bijections ofX. More generally, for finite setsX, Ya bijection fromX Yexists if and only if theyhave the same number of elements. Surprisingly, there is even a bijection fromRtoR2(although it is not an obvious one, and horribly violates usual properties of functions incalculus like differentiability).

5 However, Cantor very famously showed that there is nobijection from the set of positive integers toR, meaning that some infinities are really larger than other infinities. Thus, functions between sets without additional structureare too coarse to notice anything like geometry or dimension, and can be quite general, it can take some work to check if a function is Injective or surjectiveby hand. However, for linear transformations of vector spaces, there are enough extraconstraints to make determining these properties straightforward. Our first main resultalong these lines is the linear transformation is Injective if and only if its kernel is the trivialsubspace{0}.

6 ThatTis Injective . Then for anyv ker(T), we have (using the factthatTis linear in the second equality)T(v) = 0 =T(0),and so by injectivityv= , suppose that ker(T) ={0}. Then ifT(x) =T(y),by linearity we have0 =T(x) T(y) =T(x y),so thatx y ker(T) But as only 0 is in the kernel,x y= 0, orx=y. Thus,Tisinjective. LECTURE is completely false for non-linear functions . For example, the mapf:R Rwithf(x) =x2was seen above to not be Injective , but its kernel is zero asf(x) = 0implies thatx= the linear transformationT:R2 P 2given byT((a, b)) =ax2+ is a linear transformation asT((a, b) + (a , b )) =T((a+a , b+b )) = (a+a )x2+ (b+b )x= (ax2+bx) + (a x2+b x) =T((a, b)) +T((a , b ))andT(c(a, b)) =T((ca, cb)) = (ca)x2= (cb)x=c(ax2+bx) =cT((a, b)).

7 Note thatker(T) ={0}, as ifT((a, b)) = 0, then the polynomialax2+bxmust beidentically zero, and hencea=b= 0, so(a, b) = 0 R2. Thus, we automatically havethatTis particularly interesting phenomenon arises whenVandWhave the same finite-dimensional vector spaces with the same dimension,then a linear mapT:V Wis Injective if and only if it is surjective . In particular,ker(T) ={0}if and only ifTis the rank-nullity theorem, the dimension of the kernel plus the dimension ofthe image is the common dimension ofVandW, sayn. By the last result,Tis injectiveif and only if the kernel is{0}, that is, if and only if it the nullity is zero. By therank-nullity theorem, this happens if and only if the rank ofTisn, that is, if and onlyif the image ofTis ann-dimensional subspace of the (n-dimensional) vector the only full-dimensional subspace of a finite-dimensional vector space is itself, sothis happens if and only if the image is all ofW, namely, ifTis surjective .

8 In particular, we will say that a linear transformation between vector spacesVandWof the same dimension is anisomorphism, and thatVandWareisomorphic,writtenV =W, if it is bijective. If two vector spaces are isomorphic, we can think ofthem as being the same. any non-negative integern, all vector spaces of dimensionnover a fieldFare isomorphic to toFn(and hence to each other, as it isn t too hard to show that =isanequivalence relation). To find an isomorphism from a vector spaceVof dimensionntoF, choose some basisv1, .. , vnofV. Then we have a functionT:V Fngivenby taking coordinate vectors with respect to this basis, and it isn t hard to show thatthis map is linear. The last theorem shows that it is bijective if the kernel is zero, asVandFnhave the same dimension by assumption.

9 To see that this is true, supposethat some coordinate vectorc= (c1, .. , cn)of some non-zero vectorvwas zero. Thenv=c1v1+..+cnvn= 0, which contradicts the assumption thatv6= : LINEAR ALGEBRA I, MICHAELMAS 2016 Another key property of linear transformations is that they are determined by theirvalues on a basis, and can, moreover, be specified to have arbitrary values on basiselements. We have seen this when we studied multilinear maps, but for completenesswe record a version of this result thatVandWare vector spaces overFand that{v1, .. , vn}is a ba-sis forV. Then for any vectorsw1, .. , wn W, there is a unique linear transformationT:V Wfor whichT(vj) =wj,withj= 1.

10 , n. The process of building up a linear transformation by using its valueson a basis is calledextending by linearity. In particular, if two linear transformationshave the same values on a set of basis vectors forV, then they are equal on all that we take as a basis forR3the set{v1, v2, v3}={(1,1,1),(2,3,1),(4,1,5)}.This is really a basis as if we put them into a matrix and take the determinant, we finddet 1 2 41 3 11 1 5 = 26= that we define a linear functionT:R3 P(R)by settingT(v1) =x2 5,T(v2) =x7+ 1,T(v3) = 11and extending linearly. Then the values ofTon any vector(a, b, c) R3may be found by finding the coordinate vector and pluggin in. For instance,ifv= (1,2,5), then we saw before that we could find the coordinate vectorcofvbytaking the product 1 2 41 3 11 1 5 1 125 = 7352 1/2 3/21 1/2 1/2 125 = 24 13/2 5/2.