Current time:0:00Total duration:25:51

0 energy points

# Determining whether a transformation is onto

Determining whether a transformation is onto. Created by Sal Khan.

Video transcript

Let's say I have a linear
transformation T that's a mapping between Rn and Rm. We know that we can represent
this linear transformation as a matrix product. So we can say that T of x, so
the transformation T-- let me write it a little higher to save
space-- so we can write that the transformation T
applied to some vector x is equal to some matrix times x. And this matrix, since it's a
mapping from Rn to Rm, this is going to be a m by n matrix. Because each of these entries
are going have n components, they're going to be members of
Rn, so this guy has to have n columns in order to be able
to have this matrix vector product well defined. So we can go back to what we've
been talking about now. In the last couple of videos,
we've have been talking about invertibility of functions,
and we can just as easily apply it to this transformation,
because transformations are
just functions. We just use the word
transformations when we start talking about maps between the
vector spaces or between sets of vectors, but they are
essentially the same thing. Everything we've done
the last two videos have been very general. I never told you what the set
of our domain and the set of our co-domains were
made up of. Now we're dealing with vectors,
so we can apply the same ideas. So T is a mapping right
here from Rn to Rm. So if you take some vector here,
x, T will map it to some other vector in Rm. Call that Ax. If we take this matrix vector
product right there and this is the mapping T right there. So let's ask the same questions
about T that we've been asking in general
about functions. Is T invertible? And we learned in the last
video that there's two conditions for invertibility. T has to be onto, or the other
way, the other word was surjective. That's one condition
for invertibility. And then T also has
to be 1 to 1. And the fancy word for that was
injective, right there. So in this video, I'm going to
just focus on this first one. So I'm not going to prove to you
whether T is invertibile. We will at least be able to try
to figure out whether T is onto, or whether it's
surjective. So just as a reminder, what does
onto or surjective mean? It means that you take any
element in Rm, you take any element in your co-domain, so
you give me any element in your co-domain-- let's call that
element b; it's going to be a vector-- the fact, if T is
surjective or if T is onto, that means that any b that you
pick in our co-domain, there's always going to be some vector,
at least one vector, in our domain. That if you apply the
transformation to it you're going to get b. Or another way to think about
it is the image of our transformation is all of Rm. All of these guys
can be reached. So let's think about
what that means. So we know that the
transformation is Ax. It's some matrix A. So the transformation of x--
I'll just rewrite it-- is equal to some matrix A-- that's
an m by n matrix-- times the vector x. Now, if T has to be onto, that
means that Ax, this matrix vector product, has to be equal
to any member of our co-domain can be reached by
multiplying our matrix A by some member of our domain. So what's another way of
thinking about it? Another way of thinking about
it is for any b, so onto, implies that for any vector b
that is a member of Rm-- so any b here-- there exists at
least one solution to a times x is equal to b. Where, of course, x is, the
vector x is, a member of Rn. It's just another way of saying
exactly what I've been saying in the first part
of this video. You give me any b in this set,
and then there has to be, if we assume that T is onto, or for
T to be onto, there has to be at least one solution
to Ax is equal to b. There has to be at least one x
out here, that if I multiply it by A, I get to my b. And this has to be true for
every, maybe I should write, for every instead of any. But they are the same idea. But, for every b in Rm, we have
to be able to find at least one x that makes
this true. So what does that mean? That means that A times x has
to be equal to-- you can construct any member of Rm by
taking a product of A and x, where x is a member of Rn,
where x is a member here. Now what is this? If x is an arbitrary member of
Rn, Let me write like this. We know that matrix A would
look like this. It'll be a bunch of
column vectors. a1, a2 and it has n columns,
so it looks like that. That's what our matrix
A looks like. So we're saying if you take this
product, you have to be able to reach any guy,
any member of Rm. Well, what does this product
look like if where taking this product instead of writing
an x there, I could write x like this. x1, x2, all the way to xn. So this product is going to be
x1 times the first column vector of A, plus x2 times the
second column vector of A, all the way to plus xn times the
nth column vector of A. That's what this product is. And in order for T to be onto,
this combination has to be equal to any vector in Rm. Well, what does this mean? These are just linear
combinations of the column vectors of A. So another way to say that is
for T to be onto, So for T to be surjective or onto, the
column vectors of A have to span Rm, have to span
our co-domain. They have to span
this right here. You have to be able to get any
vector here with a linear combination of these guys. Right? And the linear combination is
set up because the weights are just arbitrary members
of the real numbers. This vector is just a bunch
of arbitrary real numbers. So for T to be onto, the span of
a1, a2, all the way to an, has to be equal to Rm, has to
be equal to your co-domain. That just means that you can
achieve any vector in your co-domain with the linear
combinations of the column vectors of this. What's the span of a matrices'
column vectors? By definition that is the
matrices' column space. So we could say, that means that
the span of these guys have to be Rn, or another way
is that the column space of A-- let me switch colors-- the
column space of A has to be equal to Rm. So how do we know if
a vector's column space is equal to Rm? So here, maybe it might be
instructive to think about, when can we not find solutions
to the equation Ax is equal to b? So whenever you're faced
with this type of an equation, what do we do? We can set up an augmented
matrix that looks like this, where you put A on this side,
and then you put the vector b on the right-hand side. And then you, essentially,
perform a bunch of row operations. You have to perform the entire
rows in both cases, on both sides, and we've done
this multiple times. Your goal is to get the
left-hand side into reduced row echelon form. So what you want to do is,
eventually, get your augmented matrix to look like this. Where the left-handed side is--
let me define R, capital R, to be the reduced row
echelon form of A. And we've done many
videos on that. That's just, you have a matrix
where you have your pivots and the pivot will be the only
non-zero entry in its column. But not every column has
to have a pivot in it. Maybe, you have a free column
or non-pivot column and then they could have a
bunch of 0's. And maybe this has a pivot. This would have to be 0 if
there is a pivot there. These would have to be 0,
and so on and so forth. And maybe the next pivot
is right there. These would have to be 0,
and you get the idea. You could have some columns
the don't have pivots, but whenever you do have a pivot,
they have to be the only non-zero entry in
their column. This is reduced row
echelon form. So, what we do with any matrix
is we keep performing those row operations so that we
eventually get it into a reduced row echelon form. And as we do that we are
performing those same operations on the
right-hand side. We're performing on
the entire row of these augmented matrices. So this vector b right here, I
guess I could write it as a vector, it's eventually going
to be some other vector c right here. You know, if this is 1, 2, 3,
maybe I will perform a bunch of operations and this
will be 3, 2, 1, or something of that nature. Now, when does this not
have a solution? We reviewed this early on. The only time where you don't
have a solution, remember, there are three cases, where
you have many solutions. and that's the situation where
you have three variables. We've talked about
that before. You have the case where you have
only one unique solution, that's the other case. And then you have
the final case where you have no solutions. And when do you have
no solutions? What has to happen to
have no solution? To have no solutions, when you
perform these row operations, you have to eventually get to
a point where your matrix looks something like this. I don't know what all this stuff
looks like maybe there's a 1 here, a bunch of stuff. There is a 1 here and a 0. But if you have a whole row, at
least one whole row of 0's, you just have a bunch
of 0's like that. And over here you have something
that is non-zero. This is the only time that
you have no solution. So let's remember what
we're even talking about this stuff for. We are saying that our
transformation is onto, if its column vectors or if its column
space is Rm, if its column vectors span Rm. And what I'm trying to figure
out is how do I know that it spans Rm? So, essentially, for it to span
Rm, you can give me any b here, any b that's a member of
Rm, and I should be able to get a solution. So we asked ourselves the
question, when do we not get a solution? Well, we definitely don't get a
solution if we have a bunch of 0's in a row. And then we have something
non-zero here. That's definitely not going
to be a solution. Now there's the other case where
we have a bunch of 0's. So there's the other case
where we do have some solutions, where it's only
valid for certain b's. So that's the case-- let
me draw it like this. Let me start it like this. So let's say I have my matrix
A, and I have my b1, b2, let me write it all the way,
and then you have bm. Remember, this is
a member of Rm. And we do our reduced row
echelon form with this augmented matrix, and
A goes to its reduced row echelon form. Let's say it's reduced row
echelon form has a row of 0's at the end of it. So it just has a row
of 0's right there. Everything else looks
like your standard stuff, 1's and 0's. But the last row, let's say
it's a bunch of 0's. And when we perform the row
operations here on this generalized member of Rm, this
last row has some function. Maybe it just looks like 2b1
plus 3b2-- I'm just writing a particular case, it won't always
be this-- minus b3. And it will essentially
be some function of all of the b's. So let me write it this way. I'm writing a particular case
in here, maybe I shouldn't have written a particular
case. This will be some function of
b1, b2, all the way to bm. Now, clearly if this
is non-zero, we don't have a solution. And so if we don't have a
solution for some cases of b, then we are definitely
not spanning Rm. So, let me write that down. If we don't have a solution for
some cases of b, then we don't span Rm. I don't know if I'm overstating
something that is maybe obvious to you, but I
really want to make sure you understand this. Anytime you just want to solve
the equation Ax is equal to b-- and remember, we want to
make sure that this can be true for any b we chose-- what
we could do is we just set up this augmented matrix like this,
and we perform a bunch of row operations until we get
A, we get this matrix A to reduced row echelon form. As we do this, the right-hand
side is going to be a bunch of functions of b. So maybe the first
row is b1 minus b2, plus b4, or something. And then the next row will
be something like that. We've seen examples of this in
the past. And if you end up by doing the reduced row echelon
form with a row of 0's here, the only way that you're going
to have a solution is if your vector b, if its entries satisfy
this function here on the right, so that this
thing equals 0. So it's only going to be
true for certain b's. And if this only has a solution
for the certain b's that make this equal to 0, then
we definitely are not spanning all of Rm. Let me do it visually. So if that is Rm, and if we
put-- if this is only 0 for a couple of b's, for, let's say
for some handful of b's, then these are the only guys that we
can reach by multiplying A times some vector in Rm. And we definitely won't
be spanning all of Rm. In order to span all of Rm, when
we put this in a reduced row echelon form, we have to
always find a solution. And the only way we are always
going be finding a solution is if we don't run into this
condition where we have a row of 0's. Because when you have a row 0's,
then you have to put the constraint that this right-hand
side has to be 0. So what's the only reduced row
echelon form where you don't have a row of 0's at the end? Well, any row in reduced row
echelon form either has to have all 0's or it has to have
a pivot entry in every row. So the only way that you span--
so T is onto, if and only if, it's the column space
of its transformation vector is equal to Rm. Its column vectors
span all of Rm. And the only way that that's
happening is if the reduced row echelon form of A has a
pivot entry in every row. And how many rows
does it have? This is an m by n matrix. It has m rows and n columns. So it has a pivot entry
in every row. That means that it has to have
m pivot entries, right there. Now, what's another way of
thinking about that? Remember, earlier on, several
videos ago, we thought about how do you figure out-- and this
might confuse things a little bit-- how do you
figure out the basis for your column space? So the basis for the column
space of a matrix, and this is a bit of review. What we did is we say, look, you
take your matrix, and you put it in reduced row echelon
form of your matrix, and then, essentially-- let me draw it a
little bit different heree-- well, you put it in reduced
row echelon form. So let's say that's just reduced
row echelon form. And you look at which columns
have pivot entries. And the corresponding columns in
your original matrices, in your original matrix,
forms the basis for your column space. So let me draw that out. So, I'll do a particular
instance. So, let's say that it has its
column vectors a1, a2, all the way to an. That's what A looks like. And when you put it in reduced
row echelon form, let's say that this column right here
has a pivot entry. That column has a pivot entry. Let's say that this
one doesn't. Let's say this is a 2 there. I'm just picking particular
numbers. Let's say there's a 3. Let's say all of these are
non-pivot entries, and then our last entry n is
a pivot entry. So it just has a bunch of 0's,
and then a 1 like that. How do you determine what are
the basis vectors for the column space? Well, obviously, the column
space is everything that's spanned by all these guys. But, what's the minimum
set you need to have that same span? Well, you look at which one
has a corresponding pivot entries or pivot columns. And you say, I have a pivot
column here, and I have a pivot column there. So the basis for my column space
must be this column in my original matrix, and that
column in my original matrix. And then we said, well, how do
you define the dimension of it's column space? And you just essentially count
the number of vectors you need for your basis, and we call
that the rank of A. This is all review. The rank of A was equal to the
dimension of the column space of A, which is equal to number
of basis vectors for the column space. And this is how you
determine it. You essentially figure out how
many pivot columns you have, the number of pivot columns
you have is the number of basis vectors you have,
and so that's going to be the rank of A. Now, the whole reason why I
talked about this is we just said that our transformation T
is onto, if and only if, its column space is Rm, which is
the case if it has a pivot entry in every row in its
reduced row echelon form. Or, since it has m rows, it has
to have m pivot entries. So for every row, you have a
pivot entry, but every pivot entry corresponds to
a pivot column. So if you have m pivot entries,
you also have m pivot columns, which means that if you
were to do this exercise right here, you would have m
basis vectors for your column space, or that you would
have a rank of m. So this whole video was
just a big long way of saying that T is onto. And another way of saying that
is that if you have your domain here, which was Rm, and
you have your co-domain here, that is Rm, that every member
of Rm can be reached by T by some member of Rn. Any guy here, there's always at
least one guy here, that if you apply T to it, you
get right there. There might be more than one. We're not even talking
about 1 to 1 yet. So we say that T is onto, if and
only if, the rank of its transformation matrix,
A, is equal to m. So that was the big takeaway
of this video. Let's just actually do an
example, because sometimes when you do things really
abstract it seems a little bit confusing, when you see
something particular. Let me define some
transformation S. Let's say the transformation S
is a mapping from R2 to R3. And let's say that S applied to
some vector x is equal to the matrix 1, 2, 3, 4, 5,
6, times the vector x. So this is clearly
a 3 by 2 matrix. Let's see if S is onto. Well, based on what we just did,
we just have to go and put this guy in reduced
row echelon form. So let's do that. So if you put this guy into
reduced row echelon form, so let's keep 1, 2, 3, 4, 5, 6. Now, let's keep the first row
the same, that's 1, 2. Let's replace the second row
with the second row minus 3 times the first row. Actually, let's replace it with
3 times the first row minus the second row. So, 3 times 1 minus 3 is 0. 3 times 2 minus 4, that's
6 minus 4, is 2. Now let's replace the third
row with 5 times the first row, minus the third row. So 5 times 1 minus 5 is 0. 5 times 2 is 10, minus 6 is 4. Now, let's see if we can
get a 1 right here. So I'm going to keep my
middle row the same. Or, actually, let's just divide
the middle row by 2, or multiply it by 1/2 So, you
get 0, 1 and then you have a 0, 4, 1, 2. And now let's try to make these
0, get it into reduced row echelon form. So I'm going to keep my middle
row the same, 0, 1. And let's replace the top row
with the top row minus 2 times the second row. So 1 minus 2 times 0 is 1. 2 minus 2, times 1 is 0. Now, let's replace this last row
with the last row minus 4 times this row. So we get 0 minus 4,
times that, is 0. 4 minus 4, times 1, is 0. So notice, we have a
row with 0's here. We have two pivot entries or two
rows with pivot entries, and we also have two pivot
columns right there. So the rank of this guy right
here, of 1, 2, 3, 4, 5, 6. The rank of that is equal
to 2, which is not equal to our co-domain. It is not equal to R3. It's not equal to R3, so S is
not onto, or not surjective. It's one of the two conditions
for invertibility. So, we definitely know that
S is not invertible. Hopefully that's helpful. Now, in the next video we're
going to focus on the second condition for invertibility,
and that's being 1 to 1.