maths.free › Linear Algebra › 7. Linear Transformations › Surjective Linear Transformations

Surjective Linear Transformations

The companion to an injection is a surjection. Surjective linear transformations are closely related to spanning sets and ranges. So as you read this section reflect back on and note the parallels and the contrasts.

Surjective Linear Transformations

Suppose $\ltdefn{T}{\complex{5}}{\complex{8}}$ is a linear transformation. Why is $T$ not surjective?
What is the relationship between a surjective linear transformation and its range?
There are many similarities and differences between injective and surjective linear transformations. Compare and contrast these two different types of linear transformations. (This means going well beyond just stating their definitions.)

Surjective Linear Transformations

As usual, we lead with a definition.

Given an arbitrary function, it is possible for there to be an element of the codomain that is not an output of the function (think about the function $y=f(x)=x^2$ and the codomain element $y=-3$). For a surjective function, this never happens. If we choose any element of the codomain ($\vect{v}\in V$) then there must be an input from the domain ($\vect{u}\in U$) which will create the output when used to evaluate the linear transformation ($\lt{T}{\vect{u}}=\vect{v}$). Some authors prefer the term onto where we use surjective, and we will sometimes refer to a surjective linear transformation as a surjection.

Examples of Surjective Linear Transformations

It is perhaps most instructive to examine a linear transformation that is not surjective first.

Example: Not surjective, Archetype Q

is the linear transformation

We will demonstrate that \vect{v}=\colvector{-1\\2\\3\\-1\\4} is an unobtainable element of the codomain. Suppose to the contrary that $\vect{u}$ is an element of the domain such that $\lt{T}{\vect{u}}=\vect{v}$.

Then \colvector{-1\\2\\3\\-1\\4}&=\vect{v}=\lt{T}{\vect{u}} =\lt{T}{\colvector{u_1\\u_2\\u_3\\u_4\\u_5}}\\ &=\colvector{ -2 u_1 + 3 u_2 + 3 u_3 - 6 u_4 + 3 u_5\\ -16 u_1 + 9 u_2 + 12 u_3 - 28 u_4 + 28 u_5\\ -19 u_1 + 7 u_2 + 14 u_3 - 32 u_4 + 37 u_5\\ -21 u_1 + 9 u_2 + 15 u_3 - 35 u_4 + 39 u_5\\ -9 u_1 + 5 u_2 + 7 u_3 - 16 u_4 + 16 u_5}\\ &= \begin{bmatrix} -2&3&3&-6&3\\ -16&9&12&-28&28\\ -19&7&14&-32&37\\ -21&9&15&-35&39\\ -9&5&7&-16&16 \end{bmatrix} \colvector{u_1\\u_2\\u_3\\u_4\\u_5}

Now we recognize the appropriate input vector $\vect{u}$ as a solution to a linear system of equations. Form the augmented matrix of the system, and row-reduce to \begin{bmatrix} \leading{1} & 0 & 0 & 0 & -1 & 0\\ 0 & \leading{1} & 0 & 0 & -\frac{4}{3} & 0\\ 0 & 0 & \leading{1} & 0 & -\frac{1}{3} & 0\\ 0 & 0 & 0 & \leading{1} & -1 & 0\\ 0 & 0 & 0 & 0 & 0 & \leading{1}\\ \end{bmatrix}

With a leading 1 in the last column, tells us the system is inconsistent. From the absence of any solutions we conclude that no such vector $\vect{u}$ exists, and by , $T$ is not surjective.

Again, do not concern yourself with how $\vect{v}$ was selected, as this will be explained shortly. However, do understand why this vector provides enough evidence to conclude that $T$ is not surjective.

To show that a linear transformation is not surjective, it is enough to find a single element of the codomain that is never created by any input, as in . However, to show that a linear transformation is surjective we must establish that every element of the codomain occurs as an output of the linear transformation for some appropriate input.

Let us now examine a surjective linear transformation between abstract vector spaces.

Condensed — the full section is in Beezer, A First Course in Linear Algebra.

Range of a Linear Transformation

For a linear transformation $\ltdefn{T}{U}{V}$, the range is a subset of the codomain $V$. Informally, it is the set of all outputs that the transformation creates when fed every possible input from the domain. It will have some natural connections with the column space of a matrix, so we will keep the same notation, and if you think about your objects, then there should be little confusion. Here is the careful definition.

Example: Range, Archetype O

is the linear transformation

To determine the elements of $\complex{5}$ in $\rng{T}$, find those vectors $\vect{v}$ such that $\lt{T}{\vect{u}}=\vect{v}$ for some $\vect{u}\in\complex{3}$, \vect{v}&=\lt{T}{\vect{u}}\\ &=\colvector{-u_1 + u_2 - 3 u_3\\ -u_1 + 2 u_2 - 4 u_3\\ u_1 + u_2 + u_3\\ 2 u_1 + 3 u_2 + u_3\\ u_1 + 2 u_3 }\\ &= \colvector{-u_1\\-u_1\\u_1\\2 u_1\\ u_1} + \colvector{u_2\\2u_2\\u_2\\3u_2\\ 0} + \colvector{-3u_3\\-4u_3\\u_3\\u_3\\ 2 u_3}\\ &= u_1\colvector{-1\\-1\\1\\2\\1} + u_2\colvector{1\\2\\1\\3\\ 0} + u_3\colvector{-3\\-4\\1\\1\\2}

This says that every output of $T$ (in other words, the vector $\vect{v}$) can be written as a linear combination of the three vectors \colvector{-1\\-1\\1\\2\\1} && \colvector{1\\2\\1\\3\\ 0} && \colvector{-3\\-4\\1\\1\\2} using the scalars $u_1,\,u_2,\,u_3$. Furthermore, since $\vect{u}$ can be any element of $\complex{3}$, every such linear combination is an output. This means that \rng{T}=\spn{\set{ \colvector{-1\\-1\\1\\2\\1},\, \colvector{1\\2\\1\\3\\ 0},\, \colvector{-3\\-4\\1\\1\\2} }}

The three vectors in this spanning set for $\rng{T}$ form a linearly dependent set (check this!). So we can find a more economical presentation by any of the various methods from and . We will place the vectors into a matrix as rows, row-reduce, toss out zero rows and appeal to , so we can describe the range of $T$ with a basis, \rng{T}=\spn{}

We know that the span of a set of vectors is always a subspace (), so the range computed in is also a subspace. This is no accident, the range of a linear transformation is always a subspace.

Let us compute another range, now that we know in advance that it will be a subspace.

In contrast to injective linear transformations having small (trivial) kernels (), surjective linear transformations have large ranges, as indicated in the next theorem.

Example: Not surjective, Archetype O

In the range of was determined to be \rng{T}=\spn{} a subspace of dimension 2 in $\complex{5}$. Since $\rng{T}\neq\complex{5}$, says $T$ is not surjective.

Condensed — the full section is in Beezer, A First Course in Linear Algebra.

Spanning Sets and Surjective Linear Transformations

Just as injective linear transformations are allied with linear independence (, ), surjective linear transformations are allied with spanning sets.

Theorem: Spanning Set for Range of a Linear Transformation

Suppose that $\ltdefn{T}{U}{V}$ is a linear transformation and S&=\set{\vectorlist{u}{t}} spans $U$. Then R&=\set{\lt{T}{\vect{u}_1},\,\lt{T}{\vect{u}_2},\,\lt{T}{\vect{u}_3},\,\ldots,\,\lt{T}{\vect{u}_t}} spans $\rng{T}$.

Proof

We need to establish that $\rng{T}=\spn{R}$, a set equality. First we establish that $\rng{T}\subseteq\spn{R}$. To this end, choose $\vect{v}\in\rng{T}$. Then there exists a vector $\vect{u}\in U$, such that $\lt{T}{\vect{u}}=\vect{v}$ (). Because $S$ spans $U$ there are scalars, $\scalarlist{a}{t}$, such that \vect{u}=\lincombo{a}{u}{t}

Then \vect{v} &=\lt{T}{\vect{u}}&&\\ &=\lt{T}{\lincombo{a}{u}{t}}&&\\ &=a_1\lt{T}{\vect{u}_1}+a_2\lt{T}{\vect{u}_2}+a_3\lt{T}{\vect{u}_3}+\ldots+a_t\lt{T}{\vect{u}_t}&&\\ which establishes that $\vect{v}\in\spn{R}$ (). So $\rng{T}\subseteq\spn{R}$.

To establish the opposite inclusion, choose an element of the span of $R$, say $\vect{v}\in\spn{R}$. Then there are scalars $\scalarlist{b}{t}$ so that \vect{v} &=b_1\lt{T}{\vect{u}_1}+b_2\lt{T}{\vect{u}_2}+b_3\lt{T}{\vect{u}_3}+\cdots+b_t\lt{T}{\vect{u}_t} &&\\ &=\lt{T}{\lincombo{b}{\vect{u}}{t}}&&

This demonstrates that $\vect{v}$ is an output of the linear transformation $T$, so $\vect{v}\in\rng{T}$. Therefore $\spn{R}\subseteq\rng{T}$, so we have the set equality $\rng{T}=\spn{R}$ (). In other words, $R$ spans $\rng{T}$ ().

provides an easy way to begin the construction of a basis for the range of a linear transformation, since the construction of a spanning set requires simply evaluating the linear transformation on a spanning set of the domain. In practice the best choice for a spanning set of the domain would be as small as possible, in other words, a basis. The resulting spanning set for the codomain may not be linearly independent, so to find a basis for the range might require tossing out redundant vectors from the spanning set. Here is an example.

Elements of the range are precisely those elements of the codomain with nonempty preimages.

Now would be a good time to return to which depicted the pre-images of a non-surjective linear transformation. The vectors $\vect{x},\,\vect{y}\in V$ were elements of the codomain whose pre-images were empty, as we expect for a non-surjective linear transformation from the characterization in .

Condensed — the full section is in Beezer, A First Course in Linear Algebra.

Surjective Linear Transformations and Dimension

Example: Not surjective by dimension, Archetype T

The linear transformation in is

Since $\dimension{P_4}=5\lt 6=\dimension{P_5}$, $T$ cannot be surjective for then it would violate .

Notice that the previous example made no use of the actual formula defining the function. Merely a comparison of the dimensions of the domain and codomain are enough to conclude that the linear transformation is not surjective. and are two more examples of linear transformations that have small domains and big codomains, resulting in an inability to create all possible outputs and thus they are non-surjective linear transformations.

Composition of Surjective Linear Transformations

In we saw how to combine linear transformations to build new linear transformations, specifically, how to build the composition of two linear transformations (). It will be useful later to know that the composition of surjective linear transformations is again surjective, so we prove that here.

Theorem: Composition of Surjective Linear Transformations is Surjective

Suppose that $\ltdefn{T}{U}{V}$ and $\ltdefn{S}{V}{W}$ are surjective linear transformations. Then $\ltdefn{(\compose{S}{T})}{U}{W}$ is a surjective linear transformation.

Proof

That the composition is a linear transformation was established in , so we need only establish that the composition is surjective. Applying , choose $\vect{w}\in W$.

Because $S$ is surjective, there must be a vector $\vect{v}\in V$, such that $\lt{S}{\vect{v}}=\vect{w}$. With the existence of $\vect{v}$ established, that $T$ is surjective guarantees a vector $\vect{u}\in U$ such that $\lt{T}{\vect{u}}=\vect{v}$. Now, \lt{\left(\compose{S}{T}\right)}{\vect{u}}&=\lt{S}{\lt{T}{\vect{u}}}&&\\ &=\lt{S}{\vect{v}}&&\text{Definition of $\vect{u}$}\\ &=\vect{w}&&\text{Definition of $\vect{v}$}

This establishes that any element of the codomain ($\vect{w}$) can be created by evaluating $\compose{S}{T}$ with the right input ($\vect{u}$). Thus, by , $\compose{S}{T}$ is surjective.

Composition of Surjective Linear Transformations

As we mentioned in the last section, experimenting with Sage is a worthwhile complement to other methods of learning mathematics. We have purposely avoided providing illustrations of deeper results, such as and , which you should now be equipped to investigate yourself. For completeness, and since composition will be very important in the next few sections, we will provide an illustration of . Similar to what we did in the previous section, we choose dimensions suggested by , and then use randomly constructed matrices to form a pair of surjective linear transformations.

Symbols used here

A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}

matrix
A rectangular array of numbers; a linear map.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

\mathbf{v},\ \vec{v}

vector
A quantity with magnitude and direction; a column of numbers.

\det A,\ |A|

determinant
Scaling factor of area/volume under A; zero means singular.

A^{-1},\ A^{T}

inverse, transpose
The matrix that undoes A; A with rows and columns swapped.

\lambda

lambda (eigenvalue)
The factor by which an eigenvector is stretched: Av = λv.

\mathbf{u} \cdot \mathbf{v},\ \|\mathbf{v}\|

dot product, norm
Σ u_i v_i; the length of v, √(v·v).

Questions people ask

What does a determinant mean geometrically?

It is the factor by which the matrix scales area (2×2) or volume (3×3), with a negative sign if orientation flips. Zero means the matrix flattens space and cannot be undone.

What is an eigenvector?

A direction the matrix does not turn — it only stretches it by the eigenvalue. Along eigenvectors a complicated matrix acts like multiplication by a number.

Why is matrix multiplication not commutative?

Because a matrix is a transformation and AB means "do B, then A". Rotating then reflecting is not the same as reflecting then rotating.

Өзүңүздүн аракетиңизди көрүңүз

Parts of this page are adapted from Beezer, A First Course in Linear Algebra (GFDL 1.2). Condensed and re-explained here; errors are ours.

Кээ бирлери Linear Algebra

Determinants Matrix inverse Eigenvalues and eigenvectors Matrix multiplication Row reduction Vector spaces, span and linear independence Orthogonality, projections and least squares Diagonalisation and matrix powers Linear transformations and change of basis