Main content

## Linear algebra

### Course: Linear algebra > Unit 2

Lesson 4: Inverse functions and transformations- Introduction to the inverse of a function
- Proof: Invertibility implies a unique solution to f(x)=y
- Surjective (onto) and injective (one-to-one) functions
- Relating invertibility to being onto and one-to-one
- Determining whether a transformation is onto
- Exploring the solution set of Ax = b
- Matrix condition for one-to-one transformation
- Simplifying conditions for invertibility
- Showing that inverses are linear

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# Matrix condition for one-to-one transformation

Showing that the rank of the of an mxn transformation matrix has to be n for the transformation to be one-to-one (injective). Created by Sal Khan.

## Want to join the conversation?

- Have the terms "homogeneous" and "inhomogeneous" been defined somewhere in the Linear Algebra playlist?(28 votes)
- Ax= 0 is a homogeneous system, homogeneous just means that you are looking for solutions when the right side is zero. When the right side is not zero, then you'd call it inhomogeneous and the 'system' looks like Ax=b, where b is a non-zero vector.(32 votes)

- so in short, if matrix A's column vectors are not linearly independent then it's rank/dimension will be less than n. and if the dimension is less than n, the matrix won't be able to span R^n thus, the transformation of A is not one to one...? am i getting this right?(10 votes)
- Everything you said there is right. Even though there are a lot of different new concepts in linear algebra, they are all closely related to one another, so it's really a good idea to be able to tie them together like you did here!(7 votes)

- I felt good about Linear Algebra up until this video.

IF anybody else had trouble understanding this, could you give any advice on how you came to knowing what was going on?(10 votes)- 2 advices:

1. review relation betwen linear independence and N(A) = {0}:

https://www.khanacademy.org/math/linear-algebra/null_column_space/v/null-space-3--relation-to-linear-independence

2. looking at previous video:

https://www.khanacademy.org/math/linear-algebra/inverse_transformations/v/linear-algebra--exploring-the-solution-set-of-ax-b

as "contra point" - here we have one-to-one transformation (N={0}), in "Exploring the solution set of Ax=b", Nullspace is {0} + span([3,1]) - in simply words, there we have mapping any point on line to specific point so "many-to-one". Here transformation is one-to-one(3 votes)

- sal says that A times xp (particular solution) = B. how was this conclusion reached ?(5 votes)
- the problem I have with this statement is that Xp was also defined to be b' which is just a particular vector that satisfies Ax=b' but now its also a solution?(5 votes)

- Why is b' called "a particular solution for Ax = b"? As far as I can see, b' is just a vector which we get if we do a rref for augmented matrix [A|b}(6 votes)
- When you find the rref you're solving the system. If b not = 0, sometimes b' is the solution for the system, sometimes it's just one solution from an infinite number. I guess that's why Sal uses "x_p" rather than "b'" (I didn't get that till now - thanks).

For example, if the rref of A is the identity matrix, then b' is a list of the values of all the variables that solve the equation, so b' clearly can be a solution to the system. If there are free variables, you get b' plus a span of vectors with the free variables as variable scalars, and in that case there are an infinite number of solutions, including b'. So if there is a solution, and b not = 0, b' is always part of it.

Could b' turn out to be 0 by coincidence?(3 votes)

- At8:23Sal substitutes
**x**for**x**-**x_p**, why? I fully understand the mechanical reasoning behind the substitution as it allows you to get to**0**, what I don't understand is how doing this allows you to show that ANY solution**x**has the form**x**=**x_p**+**n**where**n**is a member of the nullspace. Am I wrong in believing that this can be shown just based on the first part (checking the solution) alone? I don't see how this adds any new information.(5 votes) - What exactly does the subtitle of the video refer to?

"Showing that the rank of the of an mxn transformation matrix has to be an [sic?] for the transformation to be one-to-one (injective)"(4 votes)- an = n; where n is from "an mxn transformation matrix". See18:55.(2 votes)

- Towards the end of the video at around19:00, didn't Sal mean to write rank(A) = n?(2 votes)
- So this means that a transformation T:V->W is bijective (every element in W is reached exactly 1 time) iff rank(A)=dim(V) (prerequisite for injectivity) and rank(A)=dim(W) (prerequisite for surjectivity) so that dim(V)=dim(W) becomes the prerequisite for bijectivity?(2 votes)
- I think it is rank(A)=dim(V)=dim(W) rather than just dim(V)=dim(W) cause you could think of a square matrix A going from R^3 to R^3 but whose columns are linearly dependent. Therefore rank(A) wouldn't equal 3.(1 vote)

- isn't the definition of null space, N(A)= 0 where 0 is a 0 vector? what does he mean by @16:23that the function is injective if and only if N(A) = 0 vector?(1 vote)
- the def of null space is N(A) is the solution set of vectors x that satisfies the condition Ax=0 so for the transformation to be one-to-one the solution set N(A) can only have one member {zero vector}.(3 votes)

## Video transcript

Let's say I have
some matrix A. If I'm trying to determine
the null space of A, I'm essentially asking -- I'm
essentially just asking, look if we set up the equation Ax is
equal to the 0 vector, the null space of A is all the x's
that satisfy this equation. All the x's that satisfy
that equation. Ax is equal to the
0 vector, or you could call it the system. And the way you would solve it
-- and we've done this many times, this was many videos
ago -- you would make an augmented matrix with this. So the augmented matrix
would look like that. And you would have the 0 vector
on the right hand side. And then you'd perform a bunch
of row operations to put the left hand side into reduced
row echelon form. So, you would do a bunch
of operations. The left hand side would go into
reduced row echelon form. Let's call that reduced
row echelon form of A. And then the right hand side
is just going to stay 0, because you performed the
same row operations. But when you perform those row
operations on 0, you just get the 0 vector right here. And then when you un-augment--
when you create the system back from this right here,
because these two systems are equivalent, you are essentially
going to have your solution set look something
like this. You're going to have your--
let me write it like this, your solution set is
going to be equal to some scalar multiple. Let's say that, of your free
variables, your free variables are going to be the
scalar multiples. And you've seen this
multiple times, so I'll stay fairly general. But it's going to be some
multiple times, let's say, vector 1 plus some other scalar
times vector 2, these scalars tend to be your free
variables-- times vector 2 all the way to, I don't
know, whatever, c times your nth vector. I'm just trying to
stay general. We haven't seen any examples
that had more than two or three vectors here. But this is what, essentially,
your null space is spanned by these vectors right there. You get an equation-- you get
a solution set that looks something like that, and you
call that your null space. We've done that multiple
times. Your null space is that,
so it's all the linear combinations, or it's the span,
of these little vectors that you get here. And 1 and 2, all the
way to n, n. This is nothing new. I'm just restating something
that we've seen multiple, multiple times. We actually did this in
the previous video. I just maybe never wrote
it exactly like this. But what about the case when
you're solving the inhomogeneous equation. So the inhomogeneous equation
looks like this. So if I want to solve Ax is
equal to b, I would do something very similar
to this. I will create an augmented
matrix. We'll have A on the left hand
side, and I'd put b on the right hand side, and I'll
perform a bunch of row operations to put A into reduced
row echelon form. So, let me do that. So this left hand side will
be the reduced row echelon form of A. And then the right hand side,
whatever operations I did on A, I have to do on
the entire row. So I'll also be doing
them to b. So I'll have some
new vector here. Maybe I'll call it the vector--
maybe I'll call that the vector b prime. It's going to be different
than b, but let's just call it b prime. And so when you when you go back
to your-- I guess when you go out of the augmented
matrix world and rewrite it as a system, and you solve for
it, and we did this in the last video-- you'll get
your solution set. Your solution set that satisfies
this is going to be, x is going to be equal to this
b prime, whatever this new vector is, this b prime plus
something that looks exactly like this. It looks exactly like that, in
fact I'll copy and paste it, it'll look exactly like this. Let me see if it did copy. Copy and paste it. Edit, copy, and let
me paste it. So it will look something that
looks exactly like that. And we said in the last video
that you can kind of-- given this you can kind of think of
the solution set to the inhomogeneous equation is
equivalent to some particular solution, let's call that x
particular, some particular solution, plus some member
of your null space. So you could say it's plus some
homogeneous solution. So if you just pick particular
values for a, b and c, all of the different multiples of the
vector that span your null space, you'll get some particular homogeneous solution. So what I implied in the last
video, and I didn't show it to you rigorously, is that any
solution to the inhomogeneous system-- let me write it this
way, any solution-- and do it in white-- that's not white--
any solution to the inhomogeneous system Ax is equal
to b, this is a claim I made, will take the form-- some
particular solution-- that was this right here,
maybe I should do it in green-- this is this right
here-- When you do the reduced row echelon form, it becomes
that b prime vector. Plus some homogeneous solution,
so some member of the null space. Now I didn't prove it to
you, but I implied that this is the case. And what I want to in this video
is actually do a little bit of a more rigorous proof,
but it's actually fairly straightforward. So let's first of all verify
that this is a solution. So let's verify that
this is a solution. So let's just put this into
out original equation. Let's remember our original
equation was Ax is equal to b. So let's verify. Let me write it as a question. Is that particular solution,
plus some homogeneous solution, a solution to
Ax is equal to b? Well to do that you just put
that in the place of x. So let's try it out. So A times this guy right here,
times some particular solution, plus some homogeneous
solution is going to be equal to A times the
particular solution, plus A times some member of
my null space. And what is this equal to? That is going to
be equal to b. Right? We're saying that this
is a particular solution to this equation. That is going to be equal to b
and that this is going to be equal to the 0 vector because
this is a solution to our homogeneous equation. So this is going to be
equal to b plus 0, or it's equal to b. So A times this vector right
here is indeed equal to b. So this is a solution. This is a solution, yes. Now the next question is, does
every solution to the inhomogeneous system, or does
any solution to the inhomogeneous system,
take this form? So does any solution x, to Ax
equal to b, take the form x is equal to some particular
solution, plus a member of our null space, or plus a
homogeneous solution. So to do that let's take-- let's
test out what happens when we multiply the vector
A times x-- let me write it this way. let's say that x is any solution
to Ax is equal to b. Let's start off with that. And let's see what happens when
we take A times x minus some particular solution
to this. So when we distribute the matrix
vector product, you get A times our any solution
minus A times our particular solution. Now what is this going
to be equal to? We're saying that this is a
solution to Ax equals b. So this is going to
be equal to b. And of course, any particular
solution to this when you multiply it by A is also
going to be equal to b. So it's going to be b minus b,
so that's going to be equal to the 0 vector. Or another way to think about
it is, x, the vector x minus our particular solution is
a solution to A times x is equal to 0. Think about this if you take
this, in parentheses right here, and you put it right
there, and you multiply it times A you get the 0 vector. We just did that, you get the
0 vector, because when you multiply each of these guys
by A you get b and you get b minus b. And so that you get 0. So you can say that x minus--
so our any solution x minus the particular solution of x is
a member of our null space. Right? By definition our null space is
all of the x's that satisfy this equation. So, since its a member of our
null space, we can say that it is equal to-- so our any
solution minus our particular solution is equal to some member
of our null space. We could say that it is equal
to a homogeneous solution. There might be more than one. A homogeneous solution. Now, if we just add our
particular solution to both sides of this, we get that any
solution-- remember, we assume that x is any solution to this--
that any solution is equal to our homogeneous
solution, is equal to a homogeneous solution, plus a
particular solution-- or plus our particular solution. So we've proven it both ways. That this is a solution to our
inhomogeneous equation, and that any solution to our
inhomogeneous equation takes this form right here. Now why am I so concerned with
this, and I've been kind of fixated on this inhomogeneous
equation for some time. But we've been talking about the
notion of a transformation being one-to-one. That was one of the two
conditions for a transformation to
be invertible. Now to be one-to-one-- so let me
draw a transformation here. So let's say this is my domain,
X, and this is my co-domain right here, Y, and I
have a transformation that maps from X to Y. In order for T to be
one-to-one-- so I'll write it like this, one-to-one. In order for T to be one-to-one
that means for any b that you pick here, for any
b that is a member of our co-domain, there is at most
one solution to A times x. And I'm assuming that A is our
transformation matrix, so we can write our transformation T
as being equal to some matrix times our vector
in our domain. So this would be Ax if this is
x right here, so T would map from that to that right there. So in order for our
transformation to be one-to-one, that means if you
pick any b here, there has to be, at most, one solution
to Ax is equal to b. Or another way to say that is
that there is at most one guy that maps into that element
of our co-domain. There might be none. So there could be no solution
to this, but there has to be at most one solution. Now, we just said that any
solution to an inhomogeneous-- let me write it in blue-- any
solution takes the form-- if there is a solution. So if there isn't a solution,
that's fine. That will still satisfy
one-to-one. But if there is a solution, any
solution is going to take the form x particular plus a
member of your null space. Where this guy right here is
a member of the null space. This thing right here just
applies to that guy. Right here. Any solution if they exist,
if there are no solutions, that's fine. You can still be one-to-one. But if you do have a solution
you can have at most one person that maps to it,
and any solution will take this form. I just showed you that. Now in order to be one-to-one,
this can only be one solution. The solution set can only
be one solution. We can only have one solution
here, right? What does that mean? That means that this guy
right here cannot be more than one vector. It just has to be one vector. There's only one particular
solution right there. But this guy right here has to
be-- for any solution set, depending on how you define
it, there's only one particular vector there. But this guy, the only way that
you're only going to have one solution is if your null
space is trivial, if it only contains the 0 vector. Your null space will
always, at minimum, contain the 0 vector. In the last video I think I,
just off the cuff, said that all your null space
has to be empty. But no, your null space will
always, by definition, by the fact that it is a subspace,
it will always contain a 0 vector. You can always multiply
A times 0 to get 0. So your null space will
always contain that. But in order to have only one
solution, your null space can only have the 0 vector so
that this can only be 0. And so that your only solution
is going to be the particular solution that you found,
depending on how you got there, but it's only going to
be your particular solution. So let me put this this way. So in order to be one-to-one
your null space of your transformation matrix
has to be trivial. It has to contain only
the 0 vector. Now we've covered this many,
many videos ago. What does it mean if your
null space only contains a trivial vector? Let me make this clear. So if your transformation vector
looks like this, A1, A2, all the way to An, and
you're multiplying it times x1, x2, all the way to xn, and
the null space is all of the x's that satisfy this equation,
0, and you are going to have m 0's right there. So if your null space is
trivial, and we're saying that that is a condition for you
to be one-to-one, for your transformation to be one-to-one,
the transformation that's specified
by this matrix. If your null space is trivial,
what does that mean? That means that the only
solution to-- another way of writing this is x1 times a1,
plus x2 times a2, all the way to xn times an, is equal
to the 0 vector. These are equivalent statements
right here. I just multiplied each of
these terms times these respective column vectors. These are the same thing. Now if you say that your null
space has to be equal to 0, you're saying that the only
solution to this equation right here, the only scalars
that satisfy this equation-- oh sorry, these aren't-- let me
actually-- because I wrote the scalars as vectors-- so
this guy right here, this statement right here, is
equivalent to x1 times a1, plus x2 times a2, plus all the
way to xn times an, is equal to the 0 vector. Where the x1's through
xn's are scalars. Now, if we say the null space
is 0, we're saying the only way that this is satisfied is
if your x1 all the way to xn is equal to 0. And this means, this is our
definition actually, of linear independence. That means that a1-- so the null
space being 0 also means that your column vectors of a--
let me write it this way-- it also means that a1, a2, all
the way through an, are linearly independent. Now what does that mean? If all of these guys are
linearly independent, what is going to be the basis for
your column space? Remember, the column
space is the span. The column space of a is equal
to the span of a1, a2, all the way to an. What we just said, if we're
dealing with the one-to-one, or one of the conditions, or the
condition to be one-to-one is that your null space
has to be 0, or only contain the 0 vector. If your null space contains the
0 vector, then all of your columns are linearly
independent. If all of these columns span
your column space, and they are linearly independent,
then they form a basis. So that means that a1, a2, all
the way to an, are a basis for our column space. And then that means if all of
our column vectors here are linearly independent, they
obviously span our column space by definition, and they
all our linearly independent, they form the basis. So the dimension of our basis,
so the dimension of our column space, that's essentially the
number of vectors you need to form the basis, is going
to be equal to n. We have n columns. So it's going to
be equal to n. Or another way to say it is that
the rank of your matrix is going to be equal to n. So now we have a condition for
something to be one-to-one. Something is going to be
one-to-one if and only if, the rank of your matrix
is equal to n. And you can go both ways. If you assume something is
one-to-one, then that means that it's null space here has to
only have the 0 vector, so it only has one solution. If it's null space only has the
0 vector, then that means it's columns are linearly
independent. Which means that they all
are part of the basis. Which means that you have
n basis vectors, or you have a rank of n. Let's go the other way. If you have a rank of n, that
means that all of these guys are linearly independent. If all of these guys are
linearly independent, then the null space is just
the 0 vector. The null space is just the 0
vector, this part of your solution disappears. And then you are only left
with one solution. So you're one-to-one. So you're one-to-one if and
only if the rank of your transformation matrix
is equal to n.