Search for probability and statistics terms on Statlect
StatLect

Surjective, injective and bijective linear maps

by , PhD

In this lecture we define and study some common properties of linear maps, called surjectivity, injectivity and bijectivity.

Infographic that helps to visualize the definitions of surjective, injective and bijective.

A map is said to be:

Table of Contents

Linear map

Remember that a function $f:S
ightarrow T$ between two linear spaces $S$ and $T$ associates one and only one element of $T$ to each element of $S$.

The function $f$ is said to be a linear map (or linear transformation) if and only if[eq1]for any two scalars $lpha _{1}$ and $lpha _{2}$ and any two vectors $s_{1},s_{2}in S$.

Domain, codomain, null space and range

The set $S$ is called the domain of $f$, while $T$ is the codomain.

Other two important concepts are those of:

Both the null space and the range are themselves linear spaces (subspaces of $S$ and $T$ respectively).

Surjective map

Let us start with a definition.

Definition Let $S$ and $T$ be two linear spaces. Let $f:S
ightarrow T$ be a linear map. The transformation $f$ is said to be surjective if and only if, for every $tin T$, there exists $sin S$ such that[eq4]

In other words, every element of $T$ can be obtained as a transformation of an element of $S$ through the map $f$.

When $f$ is surjective, we also often say that $f$ is a linear transformation from $S$ "onto" $T$.

Since the range of $f$ is the set of all the values taken by $fleft( s
ight) $ as $s$ varies over the domain, then a linear map is surjective if and only if its range and codomain coincide:[eq5]

Example Let $S=T$ be the space of all $2	imes 1$ column vectors having real entries. Let $f:S
ightarrow T$ be the linear map defined by the matrix product [eq6]where [eq7]In order to find the range of $f$, denote by $s_{1}$ and $s_{2}$ the two entries of a generic vector $sin S$, so that[eq8]If you are puzzled by the fact that we have transformed matrix multiplication into a linear combination of columns, you might want to revise the lecture on matrix products and linear combinations. As $s$ varies over the space $S$, the scalar $s_{1}$ can take on any real value. Therefore, the range of $f$ is the subspace spanned by the vector[eq9]More formally, we have that[eq10]There are elements of $T$ that do not belong to $QTR{rm}{range}f$. For example, the vector [eq11]does not belong to $QTR{rm}{range}f$ because it is not a multiple of the vector [eq12]Since the range and the codomain of the map do not coincide, the map is not surjective.

Example If you change the matrix A in the previous example to[eq13]then[eq14]which is the span of the standard basis of the space of $2	imes 1$ column vectors. In other words, the two vectors span all of $T$. As a consequence,[eq15]and the map is surjective.

Injective map

We can now define injectivity.

Definition Let $S$ and $T$ be two linear spaces. Let $f:S
ightarrow T$ be a linear map. The transformation $f$ is said to be injective if and only if, for every two vectors $s,sigma in S$ such that $s
eq sigma $, we have that[eq16]

Thus, a map is injective when two distinct vectors in $S$ always have two distinct images in $T$.

Injective maps are also often called "one-to-one".

Note that, by an elementary rule of logic, if we take the above implication[eq17]and we negate it, we obtain the equivalent implication[eq18]

Example As in the previous two examples, consider the case of a linear map induced by matrix multiplication. The domain $S$ is the space of all $2	imes 1$ column vectors and the codomain $T$ is the space of all $3	imes 1$ column vectors. A linear transformation $f:S
ightarrow T$ is defined by [eq19]where[eq20]We can write the matrix product as a linear combination:[eq21]where $s_{1}$ and $s_{2}$ are the two entries of $sin S$. Thus, the elements of $QTR{rm}{range}f$ are all the vectors that can be written as linear combinations of the first two vectors of the standard basis of the space $T$. In particular, we have that[eq22]As a consequence, if $s
eq sigma $, the two vectors differ by at least one entry and their transformations through $f$ also differ by at least one entry, so that [eq23]. Thus, the map $f$ is injective. Note that $f$ is not surjective because, for example, the vector[eq24]cannot be obtained as a linear combination of the first two vectors of the standard basis (hence there is at least one element of the codomain that does not belong to the range of $f$).

Example Modify the function in the previous example by setting[eq25]so that[eq26]Set[eq27]We have that[eq28]and [eq29]Therefore, we have found a case in which $s
eq sigma $ but [eq30]. We can conclude that the map $f$ is not injective.

A map is injective if and only if its kernel is a singleton

We can determine whether a map is injective or not by examining its kernel.

Proposition Let $S$ and $T$ be two linear spaces. A linear map $f:S
ightarrow T$ is injective if and only if its kernel contains only the zero vector, that is,[eq31]

Proof

The kernel of a linear map $f$ always includes the zero vector (see the lecture on kernels) because[eq32]Suppose that $f$ is injective. Then, there can be no other element $sin S$ such that $s
eq 0$ and [eq33]Therefore,[eq34]which proves the "only if" part of the proposition. Now, suppose the kernel contains only the zero vector. Take two vectors $s,sigma in S$ such that[eq35]Then, by the linearity of $f$ we have that[eq36]This implies that the vector $s-sigma $ belongs to the kernel. But we have assumed that the kernel contains only the zero vector. As a consequence, [eq37]We have just proved that[eq38]As previously discussed, this implication means that $f$ is injective. The latter fact proves the "if" part of the proposition.

Bijective map

We conclude with a definition that needs no further explanations or examples.

Definition Let $S$ and $T$ be two linear spaces. A linear map $f:S
ightarrow T$ is said to be bijective if and only if it is both surjective and injective.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

As we explained in the lecture on linear maps, a linear function $f:S
ightarrow T$ is completely specified by the values taken by $f$ on a basis for $S$.

Let [eq39] be a basis for $S$ and [eq40] be a basis for $T$.

Specify the function $f$ as follows:[eq41]

Is the function $f$ surjective?

Solution

The vector $c_{2}$ is a member of the basis $C$. Therefore $c_{2}in T$. Since $B$ is a basis for $S$, any element of the domain $sin S$ can be written as[eq42]where $lpha _{1}$ and $lpha _{2}$ are scalars. Therefore, the elements of the range of $f$ take the form[eq43]In other words, the elements of the range are those that can be written as linear combinations of $c_{1}$ and $c_{3}$. But $c_{2}$ cannot be written as a linear combination of $c_{1}$ and $c_{3}$ because altogether they form a basis, so that they are linearly independent. Thus, $c_{2}$ belongs to the codomain of $f$ but not to its range. Therefore, codomain and range do not coincide. As a consequence, the function $f$ is not surjective.

Exercise 2

Determine whether the function defined in the previous exercise is injective.

Solution

Suppose $s,sigma in S$ are such that $s
eq sigma $. Then, by the uniqueness of the representation in terms of a basis, we have that[eq44]where [eq45] are scalars and it cannot be that both $s_{1}=sigma _{1}$ and $s_{2}=sigma _{2}$. Therefore,[eq46]where we assert that the last expression is different from zero because: 1) $c_{1}
eq 0$ and $c_{2}
eq 0$ because $c_{1}$ and $c_{2}$ are members of a basis; 2) it cannot be that both $s_{1}=sigma _{1}$ and $s_{2}=sigma _{2}$. Therefore, [eq47]We have just proved that [eq48]Therefore $f$ is injective.

How to cite

Please cite as:

Taboga, Marco (2021). "Surjective, injective and bijective linear maps", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/surjective-injective-bijective-linear-maps.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.