Image of a linear map – Serlo

The image of a linear map $f\colon V\to W$ is the set of all vectors in $W$ that are "hit by $f$". This set of vectors forms a subspace of $W$ and can be used to make the linear map $f$ surjective.

Derivation

Image of the linear map $f\colon \mathbb {R} ^{2}\to \mathbb {R} ^{3};$$(x,y)^{T}\mapsto (x,y,-0{,}5x)^{T}$

Visualization of the linear map $f\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2};$$(x,y)^{T}\mapsto (x+y,0)^{T}$

We consider a linear map $f:V\to W$ between two $K$-vector spaces $V$ and $W$. A vector $v\in V$ is transformed by $f$ into a vector $f(v)\in W$. The mapping $f$ does not necessarily hit all elements from $W$, because $f$ is not necessarily surjective. The mapped vectors $f(v)$ form a subset $\{f(v)|v\in V\}\subseteq W$. This set is called image of $f$.

Since $f$ is linear, $f$ preserves the structure of the vector spaces $V$ and $W$. Therefore, we conjecture that $f$ maps the vector space $V$ into a vector space. Consequently, the image of $f$, i.e., the set $\{f(v)|v\in V\}$ should be a subspace of $W$. We will indeed prove this in a theorem below.

Definition

Definition (Image of a linear map)

Let $V$ and $W$ be two $K$-vector spaces and $f:V\to W$ a linear map. Then we call $\operatorname {im} (f):=\lbrace f(v)|v\in V\rbrace$ the image of $f$.

Hint

In the literature, the notation $f(V)$ is also often used instead of $\operatorname {im} (f)$ for the image of $f$.

In the derivation we already considered that $\operatorname {im} (f)$ should be a subspace of $W$. We now prove this as a theorem.

Theorem (The image is a subspace)

Let $f:V\rightarrow W$ a linear map between the $K$-vector spaces $V$ and $W$. Then $\operatorname {im} (f)$ is a subspace of $W$.

Proof (The image is a subspace)

To show that $\operatorname {im} (f)$ is a subspace, we need to check the subspace criteria:

1. $\operatorname {im} (f)\subseteq W$
2. $0_{W}\in \operatorname {im} (f)$
3. For all $w_{1},w_{2}\in \operatorname {im} (f)$ we have $w_{1}+w_{2}\in \operatorname {im} (f)$.
4. For all $w\in \operatorname {im} (f)$ and for all $\rho \in K$ we have $\rho \cdot w\in \operatorname {im} (f)$.

Proof step: $\operatorname {im} (f)\subseteq W$

For every $v\in V$ we have $f(v)\in W$. So $\operatorname {im} (f)=\{f(v)|v\in V\}\subseteq W$.

Proof step: $0_{W}\in \operatorname {im} (f)$

Since $f$ is a linear map, it holds that $f(0_{V})=0_{W}$ . Thus $0_{W}\in \operatorname {im} (f)$.

Proof step: For all $w_{1},w_{2}\in \operatorname {im} (f)$ we have $w_{1}+w_{2}\in \operatorname {im} (f)$.

Consider $w_{1},w_{2}\in \operatorname {im} (f)$ as given. That means, we can choose vectors $v_{1}$ and $v_{2}$ from $V$ with $f(v_{1})=w_{1}$ and $f(v_{2})=w_{2}$. We now show that $w_{1}+w_{2}\in \operatorname {im} (f)$ . To do this, we need to find a vector in $V$ that is mapped by $f$ to $w_{1}+w_{2}$. Now

${\begin{aligned}&w_{1}+w_{2}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ f(v_{1})=w_{1}{\text{ and }}f(v_{2})=w_{2}\right.}\\[0.3em]=\ &f(v_{1})+f(v_{2})\\[0.3em]&{\color {OliveGreen}\left\downarrow \ f{\text{ is linear}}\right.}\\[0.3em]=\ &f(v_{1}+v_{2})\end{aligned}}$

As $f(v_{1}+v_{2})=w_{1}+w_{2}$ and $v_{1}+v_{2}\in V$ we have that $w_{1}+w_{2}$ is inside the image of $f$.

Proof step: For all $w\in \operatorname {im} (f)$ and for all $\rho \in K$ we have $\rho \cdot w\in \operatorname {im} (f)$.

Let $w\in \operatorname {im} (f)$ and $\rho \in K$. Then there is a vector $v\in V$ with $f(v)=w$. We need to show that there is a vector in $V$ that is mapped to $\rho \cdot w$. It holds:

${\begin{aligned}&\rho \cdot w\\[0.3em]&{\color {OliveGreen}\left\downarrow \ w=f(v)\right.}\\[0.3em]=\ &\rho \cdot f(v)\\[0.3em]&{\color {OliveGreen}\left\downarrow \ f{\text{ is linear}}\right.}\\[0.3em]=\ &f(\rho \cdot v)\end{aligned}}$

Now, since $\rho \cdot v\in V$ we have that $\rho \cdot w\in \operatorname {im} (f)$.

Image and surjectivity

We already know that a mapping $f:V\to W$ is surjective if and only if the mapping "hits" all elements of $W$. Formally, this means that $f:V\to W$ is surjective if and only if $\operatorname {im} (f)=W$. Now if $f$ is a linear map, then $\operatorname {im} (f)$ is a subspace of $W$. In particular, if $W$ is finite-dimensional, then $f$ is surjective exactly if $\dim {W}=\dim({\operatorname {im} (f)})$.

Example

The identity $\operatorname {id} \colon \mathbb {R} ^{2}\to \mathbb {R} ^{2},(x,y)\mapsto (x,y)$ is a linear map. It is surjective, because every element $(x,y)^{T}\in \mathbb {R} ^{2}$ has the preimage $(x,y)^{T}\in \mathbb {R} ^{2}$. Hence, we have $\operatorname {im} (\operatorname {id} )=\mathbb {R} ^{2}$ and in particular $\dim({\operatorname {im} (\operatorname {id} )})=2=\dim(\mathbb {R} ^{2})$.

The map $f\colon \mathbb {R} ^{3}\to \mathbb {R} ^{2},(x,y,z)\mapsto (x,y)$ is also linear. Further, each element $(x,y)^{T}\in \mathbb {R} ^{2}$ has a preimage, for example $(x,y,0)^{T}\in \mathbb {R} ^{3}$. Thus we have shown $\operatorname {im} (f)=\mathbb {R} ^{2}$ and thus, $f$ is surjective. In particular $\dim({\operatorname {im} (f)})=2=\dim(\mathbb {R} ^{2})$.

The embedding $e\colon \mathbb {R} ^{2}\to \mathbb {R} ^{3},(x,y)\to (x,y,0)$ is also linear, but not surjective. The vector $(0,0,1)^{T}$ is not contained in $\operatorname {im} (f)=\{(x,y,0)\mid x,y\in \mathbb {R} \}$. Thus $\dim({\operatorname {im} (e)})<\dim(\mathbb {R} ^{3})$ must hold. And indeed $\dim({\operatorname {im} (e)})=2<3=\dim(\mathbb {R} ^{3})$.

Sometimes it is useful to show the surjectivity of $f$ by proving $\dim(\operatorname {im} (f))=\dim W$.

Example

We consider the linear map $f\colon \mathbb {R} ^{3}\to \mathbb {R} ^{2};(x,y,z)\mapsto (2x-7y+3z,2y-3z)$ and ask if $f$ is surjective. We want to answer the question by determining the dimension of $\operatorname {im} (f)$ and comparing it with $\dim(\mathbb {R} ^{2})=2$. To do this, we first look for linearly independent vectors in the image of $f$. The vectors $f((1,0,0)^{T})=(2,0)^{T}$ and $f((0,1,0^{T}))=(-7,2)$ are linearly independent. Therefore, $\dim(\operatorname {im} (f))\geq 2=\dim(\mathbb {R} ^{2})$. Now $\operatorname {im} (f)\subseteq \mathbb {R} ^{2}$ from which we get $\dim(\operatorname {im} (f))\leq \dim(\mathbb {R} ^{2})$. Thus, we obtain $\dim(\operatorname {im} (f))=\dim(\mathbb {R} ^{2})$ and $f$ is surjective.

The relationship between image and generating system

We have seen in the article on epimorphisms, that a linear map $f\colon V\to W$ preserves generators of $V$ if and only if it is surjective. In this case, the image of each generator of $V$ generates the entire vector space $W$. In particular, the image of each generator of $V$ generates the image $\operatorname {im} (f)$ of $f$. The last statement holds also for non-surjective linear maps:

Theorem (The image is the span of the images of a generating system)

Let $f\colon V\to W$ be a linear map between two $K$-vector spaces $V$ and $W$. Let $E\subseteq V$ be a generator of $V$. Then:

$\operatorname {span} (f(E))=\operatorname {im} (f).$

Proof (The image is the span of the images of a generating system)

We show the two inclusions.

Proof step: $\subseteq$

Let $w\in \operatorname {span} (f(E))$. Then there are $n\in \mathbb {N}$, $b_{1},\dots ,b_{n}\in f(E)$ and coefficients $\lambda _{1},\dots ,\lambda _{n}\in K$, such that

${\begin{aligned}w=\sum _{i=1}^{n}\lambda _{i}b_{i}.\end{aligned}}$

Since the $b_{i}$ are in $f(E)$, there exist some $e_{i}\in E$ with $f(e_{i})=b_{i}$ for $1\leq i\leq n$. Then, because of the linearity of $f$, we have

${\begin{aligned}w=\sum _{i=1}^{n}\lambda _{i}b_{i}=\sum _{i=1}^{n}\lambda _{i}f(e_{i})=f\left(\sum _{i=1}^{n}\lambda _{i}e_{i}\right)\in \operatorname {im} (f).\end{aligned}}$

Proof step: $\supseteq$

Let $w\in \operatorname {im} (f)$. Then there is a $v\in V$ with $f(v)=w$. Since $E$ is a generator of $V$, there are an $n\in \mathbb {N}$, $e_{1},\dots ,e_{n}\in E$ and coefficients $\lambda _{1},\dots ,\lambda _{n}\in K$, such that

${\begin{aligned}v=\sum _{i=1}^{n}\lambda _{i}e_{i}.\end{aligned}}$

Now linearity of $f$ finally implies:

${\begin{aligned}w=f(v)=\sum _{i=1}^{n}\lambda _{i}\underbrace {f(e_{i})} _{\in f(E)}\in \operatorname {span} (f(E)).\end{aligned}}$

Image and linear system

Let $A$ be an $(n\times m)$ matrix and $b\in K^{n}$. The associated system of linear equations is $Ax=b$. We can also interpret the matrix $A$ as a linear map $f_{A}:K^{m}\to K^{n},\ x\mapsto Ax$. In particular, the image $\operatorname {im} (f_{A})$ of $f_{A}$ is a subset of $K^{n}$.

If $b\in \operatorname {im} (f_{A})$, there is some $x_{0}\in K^{m}$ such that $f_{A}(x_{0})=b$. By definition of $f_{A}$ we have $Ax_{0}=b$. Thus, the linear system of equations $Ax=b$ is solvable. Conversely, if $Ax=b$ is solvable, then there exists an $x_{0}\in K^{m}$ with $Ax_{0}=b$. For this $x_{0}$, we now have $f_{A}(x_{0})=b$. Thus $b\in \operatorname {im} (f_{A})$.

So the image gives us a criterion for the solvability of systems of linear equations: A linear system of equations $Ax=b$ is solvable if and only if $b$ lies in the image of $f_{A}$. However, the criterion makes no statement about the uniqueness of solutions. For this, one can use the kernel.

Examples

We will now look at how to determine the image of a linear map.

Example

Let us consider the linear map

$f\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2},\quad {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}\mapsto {\begin{pmatrix}x_{1}\\0\end{pmatrix}}.$

This is a projection to the $x$ axis. Intuitively, then, the image of $f$ should be the $x$-axis, i.e.

$\operatorname {im} (f)=\left\{{\begin{pmatrix}x\\0\end{pmatrix}};x\in \mathbb {R} \right\}.$

We now want to prove this:

If $(x_{1},x_{2})^{T}\in \operatorname {im} (f)$, then there exists some $(z_{1},z_{2})^{T}\in \mathbb {R} ^{2}$ with $(x_{1},x_{2})^{T}=f((z_{1},z_{2})^{T})=(z_{1},0)^{T}$. So $x_{2}=0$.

Conversely, because $f((x_{1},0)^{T})=(x_{1},0)^{T}$ every vector of the form $(x_{1},0)^{T}$ has a preimage under $f$. So every such vector lies in $\operatorname {im} (f)$.

This proves the desired statement.

Example

Let $K$ be a field. We consider the linear map

$f\colon K^{2}\to K^{3},\quad {\begin{pmatrix}x\\y\end{pmatrix}}\mapsto {\begin{pmatrix}x+y\\-x\\y\end{pmatrix}}.$

We want to determine the image of $f$. To do this, we exploit the fact that $\{e_{1}=(1,0)^{T},e_{2}=(0,1)^{T}\}$ is a basis of $K^{2}$ , so in particular it is a generator. We have seen in the last section that then $\operatorname {im} (f)=\operatorname {span} (f(e_{1}),f(e_{2}))$.

We can specify this space explicitly by calculating the span:

${\begin{aligned}\operatorname {im} (f)&=\operatorname {span} (f(e_{1}),f(e_{2}))\\[1em]&{\color {OliveGreen}\left\downarrow \ {\text{Insert definition of the span}}\right.}\\[1em]&=\left\{\lambda \cdot {\begin{pmatrix}1\\-1\\0\end{pmatrix}}+\mu \cdot {\begin{pmatrix}1\\0\\1\end{pmatrix}};\lambda ,\mu \in K\right\}\\[1em]&{\color {OliveGreen}\left\downarrow \ {\text{Add up}}\right.}\\[1em]&=\left\{{\begin{pmatrix}\lambda +\mu \\-\lambda \\\mu \end{pmatrix}};\lambda ,\mu \in K\right\}\\[1em]&{\color {OliveGreen}\left\downarrow \ {\text{ replace }}\lambda {\text{ by }}-x{\text{ and }}\mu {\text{ by }}y\right.}\\[1em]&=\left\{{\begin{pmatrix}y-x\\x\\y\end{pmatrix}};x,y\in K\right\}\end{aligned}}$

After considering two examples in finite-dimensional vector spaces, we can venture to an example with an infinite-dimensional vector space. We consider the same function in the examples for determining the kernel of a linear map.

Example

Our goal is to determine the image of the linear map of the derivative $d$ of polynomials over $\mathbb {R}$. The set $\lbrace 1,X,X^{2},X^{3},\dots \rbrace$ is a basis of $\mathbb {R} \lbrack X\rbrack$. The derivative function $d:\mathbb {R} \lbrack X\rbrack \rightarrow \mathbb {R} \lbrack X\rbrack$ is defined by $d(X^{i}):=i\cdot X^{i-1}$ for all $i\in \mathbb {N}$.

We now want to know whether $d$ is surjective. To do this, we note that $d({\tfrac {1}{i+1}}\cdot X^{i+1})=X^{i}$ holds for every $i\geq 0$. Thus every basis element of $\mathbb {R} [X]$ is hit. So $\operatorname {im} (f)\supseteq \operatorname {span} (1,X,X^{2},\dots )=\mathbb {R} [X]$, and $d$ is indeed surjective.

When solving systems of linear equations, we will see many more examples. We will also learn a methodical way of solving for the determination of images.

To-Do:

link as soon as it is written.

Making linear maps "epic"

We now want to construct a surjective linear map from a given linear map $f\colon V\to W$. If we consider $f$ to be a mapping of sets, we already know how to accomplish this: We restrict the target set of $f$ to $\operatorname {im} (f)$ and get some restricted mapping $f'\colon V\to \operatorname {im} (f);v\mapsto f(v)$. Now, we just need to check that $f'$ is linear. But this is clear because $\operatorname {im} (f)\subseteq W$ is a subspace of $W$. So all we need to do to make $f$ surjective (i.e., an epi-morphism) is to restrict the objective of $f$ to $\operatorname {im} (f)$.

This method also gives us an approach for making functions between other structures surjective: We need to check that the restriction on the image preserves the structure. For example, for a group homomorphism $\varphi \colon G\to H$ we can show that $\operatorname {im} (\varphi )$ is again a group and $\varphi '\colon G\to \operatorname {im} (\varphi );g\mapsto \varphi (g)$ is again a group homomorphism.

Outlook: How surjective is a linear map? - The cokernel

In the article about the kernel we see that the kernel "stores" exactly that information which a linear map $f\colon V\to W$ "eliminates". Further, $f$ is injective if and only if $\ker(f)=0$ and the kernel intuitively represents a "measure of the non-injectivity" of $f$.

We now want to construct a similar measure of the surjectivity of $f$. The image of $f$ is not sufficient for this purpose: For example, the images of $g\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2};(x,y)^{T}\mapsto (x,y)^{T}$ and $h\colon \mathbb {R} ^{2}\to \mathbb {R} ^{3};(x,y)\mapsto (x,y,0)$ are isomorphic, but $g$ is surjective and $h$ is not. From the image alone, no conclusions can be drawn as of whether $f$ is surjective, because surjectivity also depends on the target space $W$. To measure "non-surjectivity," on the other hand, we need a vector space that measures, which part of $W$ is not hit by $f$.

The space $\operatorname {im} (f)$ contains the information, which vectors are hit by $f$. The goal is to "remove this information" from $W$. We have already realized this "removal of information" in the article on the factor space by taking the quotient space $W/\operatorname {im} (f)$. We call this space $W/\operatorname {im} (f)$ the cokernel of $f$. It is indeed suitable for characterizing the non-surjectivity of $f$, because $W/\operatorname {im} (f)$ is equal to the null space $\{0\}$ if and only if $f$ is surjective: A vector in $W$ that is not hit by $f$ yields a nontrivial element in $W/\operatorname {im} (f)$ and, conversely, a nontrivial element in $W/\operatorname {im} (f)$ yields an element in $W$ that is not hit by $f$.

The kokernel even measures how non-surjective $f$ is exactly: if $W/\operatorname {im} (f)$ is larger, more vectors are not hit by $W$. If $W$ is finite dimensional, we can measure the size of $W/\operatorname {im} (f)$ using the dimension. Thus, $\dim(W/\operatorname {im} (f))=\dim(W)-\dim(\operatorname {im} (f))$ is a number we can use to quantify how non-surjective $f$ is. However, unlike $W/\operatorname {im} (f)$, this number does not allow us to reconstruct the exact vectors that are not hit by $f$.

Exercises

Exercise (Associating image spaces to figures)

We consider the following four subspaces from the vector space $\mathbb {R} ^{2}$, given as images of the linear maps

1. $f\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2},\ (x,y)^{T}\mapsto (2(x+y),x-3y)^{T}$
2. $g\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2},\ (x,y)^{T}\mapsto (x,2x)^{T}$
3. $h\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2},\ (x,y)^{T}\mapsto (-3(x-y),(x-y))^{T}$
4. $k\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2},\ (x,y)^{T}\mapsto (x,0)^{T}$

Match these four subspaces to the subspaces $U_{1},U_{2},U_{3},U_{4}$ shown in the figures below.

• 
  $U_{1}$: The subspace spanned by $(1,2)^{T}$ in $\mathbb {R} ^{2}$
• 
  $U_{2}$: The line spanned by $(3,-1)^{T}$
• 
  $U_{3}$: A plane covering all of the two-dimensional space
• 
  $U_{4}$: A line spanned by $(1,0)^{T}$

Solution (Associating image spaces to figures)

First we look for the image of $f$: To find $\operatorname {im} (f)$, we can apply a theorem from above: If $E$ is a generator of $\mathbb {R} ^{2}$, then $\operatorname {im} (f)=\operatorname {span} (f(E))$ holds. We take the standard basis $\{(1,0)^{T},(0,1)^{T}\}$ as the generator of $\mathbb {R} ^{2}$. Then

$\operatorname {im} (f)=\operatorname {span} \left(f{\begin{pmatrix}1\\0\end{pmatrix}},f{\begin{pmatrix}0\\1\end{pmatrix}}\right).$

Now we apply $f$ to the standard basis

${\begin{aligned}f{\begin{pmatrix}1\\0\end{pmatrix}}&={\begin{pmatrix}2\\1\end{pmatrix}}\\f{\begin{pmatrix}0\\1\end{pmatrix}}&={\begin{pmatrix}2\\-3\end{pmatrix}}\end{aligned}}$

The vectors $(2,1)^{T},(2,-3)^{T}$ generate the image of $f$. Moreover, they are linearly independent and thus a basis of $\mathbb {R} ^{2}$. Therefore $\operatorname {im} (f)=\mathbb {R} ^{2}$. So $\operatorname {im} (f)=U_{3}$.

Next, we want to find the image of $g$. However, it is also possible to compute the image $\operatorname {im} (g)$ directly by definition, which we will demonstrate here.

${\begin{aligned}\operatorname {im} (g)&=\left\{g{\begin{pmatrix}x\\y\end{pmatrix}}\mid {\begin{pmatrix}x\\y\end{pmatrix}}\in \mathbb {R} ^{2}\right\}\\&=\left\{{\begin{pmatrix}x\\2x\end{pmatrix}}\mid {\begin{pmatrix}x\\y\end{pmatrix}}\in \mathbb {R} ^{2}\right\}\\&=\left\{x{\begin{pmatrix}1\\2\end{pmatrix}}\mid {\begin{pmatrix}x\\y\end{pmatrix}}\in \mathbb {R} ^{2}\right\}\\&{\color {OliveGreen}\left\downarrow \ {\text{The left side does not depend on }}y\right.}\\[0.3em]&=\left\{x{\begin{pmatrix}1\\2\end{pmatrix}}\mid x\in \mathbb {R} \right\}\\&=\operatorname {span} \left({\begin{pmatrix}1\\2\end{pmatrix}}\right)\end{aligned}}$

So the image of $g$ is spanned by the vector $(1,2)^{T}$. Thus $\operatorname {im} (g)=U_{1}$.

Now we determine the image of $h$ using, for example, the same method as for $f$. That means we apply $h$ to the standard basis:

${\begin{aligned}h{\begin{pmatrix}1\\0\end{pmatrix}}={\begin{pmatrix}-3\\1\end{pmatrix}}\\h{\begin{pmatrix}0\\1\end{pmatrix}}={\begin{pmatrix}3\\-1\end{pmatrix}}\end{aligned}}$

Both vectors are linearly dependent. So it follows that $\operatorname {im} (h)=\operatorname {span} ((-3,1)^{T})$ and thus $\operatorname {im} (h)=U_{2}$.

Finally, we determine the image of $k$. For this we proceed for example as with $g$.

${\begin{aligned}\operatorname {im} (k)&=\left\{k{\begin{pmatrix}x\\y\end{pmatrix}}\mid {\begin{pmatrix}x\\y\end{pmatrix}}\in \mathbb {R} ^{2}\right\}\\&=\left\{{\begin{pmatrix}x\\0\end{pmatrix}}\mid {\begin{pmatrix}x\\y\end{pmatrix}}\in \mathbb {R} ^{2}\right\}\\&=\left\{x{\begin{pmatrix}1\\0\end{pmatrix}}\mid {\begin{pmatrix}x\\y\end{pmatrix}}\in \mathbb {R} ^{2}\right\}\\&{\color {OliveGreen}\left\downarrow \ {\text{The left side does not depend on }}y\right.}\\[0.3em]&=\left\{x{\begin{pmatrix}1\\0\end{pmatrix}}\mid x\in \mathbb {R} \right\}\\&=\operatorname {span} \left({\begin{pmatrix}1\\0\end{pmatrix}}\right)\end{aligned}}$

So the image of $k$ is spanned by the vector $(1,0)^{T}$. Thus $\operatorname {im} (k)$ is the $x$-axis, so $\operatorname {im} (k)=U_{4}$.

Exercise (Surjectivity and dimension of $V$ and $W$)

Let $V$ and $W$ be two finite-dimensional vector spaces. Show that there exists a surjective linear map $f\colon V\to W$ if and only if $\dim(V)\geq \dim(W)$.

How to get to the proof? (Surjectivity and dimension of $V$ and $W$)

We want to estimate the dimensions of $V$ and $W$ against each other. The dimension is defined as the cardinality of a basis. That is, if $b_{1},\dots ,b_{n}$ is a basis of $V$ and $c_{1},\dots ,c_{m}$ is a basis of $W$, we must show that $n\geq m$ holds if and only if there exists a surjective linear map. "if and only if" means that we need to establish two directions ($\Rightarrow ,\Leftarrow$).

Given a surjective linear map $f\colon V\to W$, we must show that the dimension of $V$ is at least $m$. Now bases are maximal linearly independent subsets. That is, to estimate the dimension from below, we need to construct a linearly independent subset with $m$ elements. In the figure, we have already a linearly independent subset with $m$ elements, which is the basis $c_{1},\dots ,c_{m}$. Because $f$ is surjective, we can lift these to vectors ${\hat {c}}_{1},\dots ,{\hat {c}}_{m}\in V$ with $f({\hat {c}}_{i})=c_{i}$. Now we need to verify that ${\hat {c}}_{1},\dots ,{\hat {c}}_{m}$ are linearly independent in $V$. We see this, by converting a linear combination $\lambda _{1}{\hat {c}}_{1}+\dots \lambda _{m}{\hat {c}}_{m}=0$ via $f$ into a linear combination $0=f(\lambda _{1}{\hat {c}}_{1}+\dots \lambda _{m}{\hat {c}}_{m})=\lambda _{1}c_{1}+\dots \lambda _{m}c_{m}$ and exploiting the linear independence of $c_{1},\dots ,c_{m}$.

Conversely, if $n\geq m$ holds, we must construct a surjective linear map $f\colon V\to W$. Following the principle of linear continuation, we can construct the linear map $f$ by specifying how $f$ acts on a basis of $V$. For this we need elements of $W$ on which we can send $b_{1},\dots ,b_{n}$. We have already chosen a basis of $W$ above. Therefore, it is convenient to define $f$ as follows:

$f(b_{i})={\begin{cases}c_{i}&i\leq m\\0&i>m\end{cases}}$

Then the image of $f$ is spanned by the vectors $f(b_{1})=c_{1},\dots ,f(b_{m})=c_{m},f(b_{m+1})=0,\dots ,f(b_{m})=0$. However, these vectors also span all of $W$ and thus $f$ is surjective.

Solution (Surjectivity and dimension of $V$ and $W$)

Proof step: "$\Rightarrow$"

Suppose there is a suitable surjective mapping $f$. We show that the dimension of $\operatorname {im} (f)=f(V)$ cannot be larger than the dimension of $V$ (this is true for any linear map). Because of the surjectivity of $f$, it follows that $\dim(V)\geq \dim(\operatorname {im} (f))=\dim(W)$.

So let $w_{1},\ldots ,w_{n}\in \operatorname {im} (f)$ be linearly independent. There exists $v_{1},\ldots ,v_{n}\in V$ with $f(v_{i})=w_{i}$ for $i\in \{1,\ldots ,n\}$. We show that $v_{1},\ldots ,v_{n}$ are also linearly independent: Let $\lambda _{1},\ldots ,\lambda _{n}\in K$ with $\sum _{i=1}^{n}\lambda _{i}v_{i}=0$. Then we also have that

$0=f(\sum _{i=1}^{n}\lambda _{i}v_{i})=\sum _{i=1}^{n}\lambda _{i}f(v_{i})=\sum _{i=1}^{n}\lambda _{i}w_{i},$

By linear independence of $w_{1},\ldots ,w_{n}$, it follows that $\lambda _{1}=\ldots =\lambda _{n}=0$. So $v_{1},\ldots ,v_{n}$ are also linearly independent. Overall, we have shown that

$w_{1},\ldots ,w_{n}\in \operatorname {im} (f){\text{ linearly independent }}\implies v_{1},\ldots ,v_{n}{\text{ linearly independent for any choice of preimages }}v_{i}\in f^{-1}(w_{i}).$

In particular, it holds that a basis of $V$ (a maximal linearly independent subset of $V$) must contain at least as many elements as a basis of $\operatorname {im} (f)$, that is, $\dim(V)\geq \dim(\operatorname {im} (f))$.

Proof step: "$\Leftarrow$"

Assume that $\dim(V)\geq \dim(W)$. We use that a linear map is already uniquely determined by the images of the basis vectors. Let $\{v_{1},\ldots ,v_{m}\}$ be a basis of $V$ and $\{w_{1},\ldots ,w_{n}\}$ be a basis of $W$. Define the surjective linear map $f\colon V\to W$ by

$f(v_{i})={\begin{cases}w_{i}&{\text{ if }}i\leq n\\0&{\text{ else.}}\end{cases}}$

This works, since by assumption, $m\geq n$ holds. The mapping constructed in this way is surjective, since by construction, $\{w_{1},\ldots ,w_{n}\}\subseteq \operatorname {im} (f)$. As the image of $f$ is a subspace of $W$, the subspace generated by these vectors, i.e., $W$, also lies in the image of $f$. Accordingly, $W\subseteq \operatorname {im} (f)\subseteq W$ holds and $f$ is surjective.

Exercise (Image of a matrix)

1. Consider the matrix $(1,2)\in \mathbb {R} ^{1\times 2}$ and the mapping $f\colon \mathbb {R} ^{2}\to \mathbb {R} ,x\mapsto (1,2)x$ induced by it. What is the image $\operatorname {im} (f)$?
2. Now let $A=(a_{1},\ldots ,a_{m})\in K^{n\times m}$ be any matrix over a field $K$, where $a_{1},\ldots ,a_{m}\in K^{n}$ denote the columns of $A$. Consider the mapping $f_{A}\colon K^{m}\to K^{n},x\mapsto Ax$ induced by $A$. Show that $\operatorname {im} (f_{A})=\operatorname {span} \{a_{1},\ldots ,a_{m}\}$ holds. So the image of a matrix is the span of its columns.

Solution (Image of a matrix)

Solution sub-exercise 1:

We know that the image $\operatorname {im} (f)$ of the linear map $f$ is a subspace of $\mathbb {R}$. Since the $\mathbb {R}$-vector space $\mathbb {R}$ has dimension $1$, a subspace can only have dimension $0$ or $1$. In the first case the subspace is the null vector space, in the second case it is already all of $\mathbb {R}$. So $\mathbb {R}$ has only the two subspaces $\{0\}$ and $\mathbb {R}$. Since $(1,2)(1,0)^{T}=1\neq 0$ holds, we have that $\operatorname {im} (f)\neq \{0\}$. Thus, $\operatorname {im} (f)=\mathbb {R}$.

Solution sub-exercise 2:

Proof step: "$\subseteq$"

Let $y\in \operatorname {im} (f_{A})$. Then, there is some $x=(x_{1},\ldots ,x_{m})^{T}\in K^{m}$ with $Ax=y$. We can write $x$ as $x=\sum _{i=1}^{m}x_{i}e_{i}$. Plugging this into the equation $Ax=y$, we get.

${\begin{aligned}y&=Ax\\&{\color {OliveGreen}\left\downarrow \ x=\sum _{i=1}^{m}x_{i}e_{i}\right.}\\[0.3em]&=A\left(\sum _{i=1}^{m}x_{i}e_{i}\right)\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{application of }}A{\text{ is linear}}\right.}\\[0.3em]&=\sum _{i=1}^{m}x_{i}Ae_{i}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ Ae_{i}=a_{i}{\text{, the }}i{\text{-th column of }}A\right.}\\[0.3em]&=\sum _{i=1}^{m}x_{i}a_{i}.\end{aligned}}$

Since $\sum _{i=1}^{m}x_{i}a_{i}\in \operatorname {span} \{a_{1},\ldots ,a_{n}\}$, we obtain $y\in \operatorname {span} \{a_{1},\ldots ,a_{n}\}$.

Proof step: "$\supseteq$"

Let $y=\sum _{i=1}^{m}y_{i}\cdot a_{i}\in \operatorname {span} (f_{A})$ with $y_{i}\in K$ for $i=1,\ldots ,m$. We want to find $x\in K^{m}$ with $Ax=y$. So let us define $x:=\sum _{i=1}^{m}y_{i}e_{i}$. The same calculation as in the first step of the proof then shows

$Ax=A\left(\sum _{i=1}^{m}y_{i}e_{i}\right)=\sum _{i=1}^{m}y_{i}Ae_{i}=\sum _{i=1}^{m}y_{i}a_{i}=y.$