Injective Surjective

INJECTIVE, SURJECTIVE AND INVERTIBLE Surjectivity: Maps which hit every value in the target space Let’s start with a puzzle. I have a remote car, controlled by 3 buttons. When I hold  control  1 down the red button, it moves in direction ; when I hold down the green button it moves in 2     2 −3 direction ; when I hold down the blue button, it moves in direction . Can I get anywhere 3 −5   12 in the plane? For example, can I get to ? 19 Let r be the amount of time I hold down the red button, and write g and b for the green and blue buttons. So we move     r 1 2 −5   g 2 3 −3 b and we want to solve     r   1 2 −3   12 g = . 2 3 −5 19 b We run through the usual row reduction process     r   1 2 −3   12 g = 0 −1 1 −5 b   r   1 2 −3   12 g = 0 1 −1 5 b   r   1 0 −1   2 g = . 0 1 −1 5 b So there are lots of solutions, the simplest of which is to hold down the red button for 2 seconds and the green for 5.   5 Notice that, if I wanted to move to instead, I only need to redo the computations on the 2 right hand  side of the equations; the left hand sides stay the same.   x x 1 For any , we can find (r, g, b) values which will move us in direction . There is a term y y for this: Vocabulary. A linear map A : Rk → R` is called surjective if, for every v in R` , we can find u in Rk with A(u) = v. 1From the physical motivation from this problem, in only makes sense to look at solutions where r, g and b ≥ 0. In fact, such solutions exist in this case. The subject of solving linear equations together with inequalities is studied in Math 561. I’ll ignore this issue. 1 2 DAVID SPEYER Another word which is sometimes used is onto.   1 2 −3 So we say that is surjective. 2 3 −5   1 4 −2 Let’s say a new car comes on the market. It moves by the matrix . Can we still 3 12 −6 go anywhere?   x Let’s run the row reduction algorithm again. We want to move to position . y     r   1 4 −2   x g = 3 12 −6 y b   r   1 4 −2   x g = . 0 0 0 y − 3x b   x So we can only go to if y − 3x = 0. In other words, this car can only drive along the line y y = 3x.   1 4 −2 The map is not surjective. 3 12 −6 Let’s understand the difference between these two examples: General Fact. Let A be a matrix and let Ared be the row reduced form of A. If Ared has a leading 1 in every row, then A is surjective. If Ared has an all zero row, then A is not surjective. Remember that, in a row reduced matrix, every row either has a leading 1, or is all zeroes, so one of these two cases occurs. Injectivity: Maps that don’t destroy information Wanda owns two types of pets: birds and cats. I ask her how many of each she has. She replies: “My pets have 14 legs, 10 eyes and 5 tails.” Can we figure out how many of each animal there are? Let b be the number of birds and c the number of cats. So     2 4   14 2 2 b = 10 . c 1 1 5 We proceed as usual   1 2   2 2  b c  1 1 1 2   0 −2 b c 0 −1 1 2   0 1  b c 0 −1  1 0   0 1  b c 0 0 So there are 3 birds and 2 cats.   7 = 10 5  7 = −4 −2 7  2 = −2  3 = 2 0 INJECTIVE, SURJECTIVE AND INVERTIBLE 3 Yes, Wanda has given us enough clues to recover the data. On the other hand, suppose Wanda said “My pets have 5 heads, 10 eyes and 5 tails.” Then we get     5 1 1   2 2 b = 10 c  5 . 1 1   5 1 1 0 0 b = 0 c 0 0 0 All we can conclude is that the total number of pets is 5; we can’t tell how many are cats and how many are birds. Wanda has wickedly failed to give us enough information! Vocabulary. A linear map A : Rk → R` is called injective if, for every v in R` , there is at most one u in Rk with A(u) = v. In other words, A does preserves enough data to recover u. Another word which is sometimes used isone to  one.   2 4 1 1 So 2 2 is injective but 2 2 is not. 1 1 1 1 We have discussed before how, if there are columns without leading 1’s, they give us multiple solutions. If, on the other hand, every column has a leading 1 in it, then there is at most one solution. In our new language: General Fact. Let A be a matrix and let Ared be the row reduced form of A. If Ared has a leading 1 in every column, then A is injective. If Ared has a column without a leading 1 in it, then A is not injective. Invertible maps If a map is both injective and surjective, it is called invertible. This means, for every v in R` , there is exactly one solution to Au = v. So we can make a map back in the other direction, taking v to u. Note that, if A is invertible, then Ared has a 1 in every column and in every row. This can only happen if A is a square matrix, so k = `. This reverse map is called A−1 . We have AA−1 = A−1 A = Idk .