Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

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.

A map is said to be:

Table of Contents

Preliminaries

Before proceeding, 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$, and the function $f$ is 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$.

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.

The book

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