Image of a linear map

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

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

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

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

Proof (The image is a subspace)

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

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

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

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

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

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

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

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

${\displaystyle {\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 ${\displaystyle f(v_{1}+v_{2})=w_{1}+w_{2}}$ and ${\displaystyle v_{1}+v_{2}\in V}$ we have that ${\displaystyle w_{1}+w_{2}}$ is inside the image of ${\displaystyle f}$.

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

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

${\displaystyle {\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 ${\displaystyle \rho \cdot v\in V}$ we have that ${\displaystyle \rho \cdot w\in \operatorname {im} (f)}$.

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

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

We have seen in the article on epimorphisms, that a linear map ${\displaystyle f\colon V\to W}$ preserves generators of ${\displaystyle V}$ if and only if it is surjective. In this case, the image of each generator of ${\displaystyle V}$ generates the entire vector space ${\displaystyle W}$. In particular, the image of each generator of ${\displaystyle V}$ generates the image ${\displaystyle \operatorname {im} (f)}$ of ${\displaystyle 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 ${\displaystyle f\colon V\to W}$ be a linear map between two ${\displaystyle K}$-vector spaces ${\displaystyle V}$ and ${\displaystyle W}$. Let ${\displaystyle E\subseteq V}$ be a generator of ${\displaystyle V}$. Then:

${\displaystyle \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: ${\displaystyle \subseteq }$

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

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

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

${\displaystyle {\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: ${\displaystyle \supseteq }$

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

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

Now linearity of ${\displaystyle f}$ finally implies:

${\displaystyle {\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}}}$

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

If ${\displaystyle b\in \operatorname {im} (f_{A})}$, there is some ${\displaystyle x_{0}\in K^{m}}$ such that ${\displaystyle f_{A}(x_{0})=b}$. By definition of ${\displaystyle f_{A}}$ we have ${\displaystyle Ax_{0}=b}$. Thus, the linear system of equations ${\displaystyle Ax=b}$ is solvable. Conversely, if ${\displaystyle Ax=b}$ is solvable, then there exists an ${\displaystyle x_{0}\in K^{m}}$ with ${\displaystyle Ax_{0}=b}$. For this ${\displaystyle x_{0}}$, we now have ${\displaystyle f_{A}(x_{0})=b}$. Thus ${\displaystyle 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 ${\displaystyle Ax=b}$ is solvable if and only if ${\displaystyle b}$ lies in the image of ${\displaystyle f_{A}}$. However, the criterion makes no statement about the uniqueness of solutions. For this, one can use the kernel.

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

Example

Let us consider the linear map

${\displaystyle 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 ${\displaystyle x}$ axis. Intuitively, then, the image of ${\displaystyle f}$ should be the ${\displaystyle x}$-axis, i.e.

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

We now want to prove this:

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

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

This proves the desired statement.

Example

Let ${\displaystyle K}$ be a field. We consider the linear map

${\displaystyle 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 ${\displaystyle f}$. To do this, we exploit the fact that ${\displaystyle \{e_{1}=(1,0)^{T},e_{2}=(0,1)^{T}\}}$ is a basis of ${\displaystyle K^{2}}$ , so in particular it is a generator. We have seen in the last section that then ${\displaystyle \operatorname {im} (f)=\operatorname {span} (f(e_{1}),f(e_{2}))}$.

We can specify this space explicitly by calculating the span:

${\displaystyle {\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.

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.

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

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

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

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

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

Solution (Associating image spaces to figures)

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

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

Now we apply ${\displaystyle f}$ to the standard basis

${\displaystyle {\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 ${\displaystyle (2,1)^{T},(2,-3)^{T}}$ generate the image of ${\displaystyle f}$. Moreover, they are linearly independent and thus a basis of ${\displaystyle \mathbb {R} ^{2}}$. Therefore ${\displaystyle \operatorname {im} (f)=\mathbb {R} ^{2}}$. So ${\displaystyle \operatorname {im} (f)=U_{3}}$.

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

${\displaystyle {\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 ${\displaystyle g}$ is spanned by the vector ${\displaystyle (1,2)^{T}}$. Thus ${\displaystyle \operatorname {im} (g)=U_{1}}$.

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

${\displaystyle {\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 ${\displaystyle \operatorname {im} (h)=\operatorname {span} ((-3,1)^{T})}$ and thus ${\displaystyle \operatorname {im} (h)=U_{2}}$.

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

${\displaystyle {\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 ${\displaystyle k}$ is spanned by the vector ${\displaystyle (1,0)^{T}}$. Thus ${\displaystyle \operatorname {im} (k)}$ is the ${\displaystyle x}$-axis, so ${\displaystyle \operatorname {im} (k)=U_{4}}$.

How to get to the proof? (Surjectivity and dimension of ${\displaystyle V}$ and ${\displaystyle W}$)

We want to estimate the dimensions of ${\displaystyle V}$ and ${\displaystyle W}$ against each other. The dimension is defined as the cardinality of a basis. That is, if ${\displaystyle b_{1},\dots ,b_{n}}$ is a basis of ${\displaystyle V}$ and ${\displaystyle c_{1},\dots ,c_{m}}$ is a basis of ${\displaystyle W}$, we must show that ${\displaystyle 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 (${\displaystyle \Rightarrow ,\Leftarrow }$).

Given a surjective linear map ${\displaystyle f\colon V\to W}$, we must show that the dimension of ${\displaystyle V}$ is at least ${\displaystyle 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 ${\displaystyle m}$ elements. In the figure, we have already a linearly independent subset with ${\displaystyle m}$ elements, which is the basis ${\displaystyle c_{1},\dots ,c_{m}}$. Because ${\displaystyle f}$ is surjective, we can lift these to vectors ${\displaystyle {\hat {c}}_{1},\dots ,{\hat {c}}_{m}\in V}$ with ${\displaystyle f({\hat {c}}_{i})=c_{i}}$. Now we need to verify that ${\displaystyle {\hat {c}}_{1},\dots ,{\hat {c}}_{m}}$ are linearly independent in ${\displaystyle V}$. We see this, by converting a linear combination ${\displaystyle \lambda _{1}{\hat {c}}_{1}+\dots \lambda _{m}{\hat {c}}_{m}=0}$ via ${\displaystyle f}$ into a linear combination ${\displaystyle 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 ${\displaystyle c_{1},\dots ,c_{m}}$.

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

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

Then the image of ${\displaystyle f}$ is spanned by the vectors ${\displaystyle 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 ${\displaystyle W}$ and thus ${\displaystyle f}$ is surjective.

Solution (Surjectivity and dimension of ${\displaystyle V}$ and ${\displaystyle W}$)

Proof step: "${\displaystyle \Rightarrow }$"

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

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

${\displaystyle 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 ${\displaystyle w_{1},\ldots ,w_{n}}$, it follows that ${\displaystyle \lambda _{1}=\ldots =\lambda _{n}=0}$. So ${\displaystyle v_{1},\ldots ,v_{n}}$ are also linearly independent. Overall, we have shown that

${\displaystyle 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 ${\displaystyle V}$ (a maximal linearly independent subset of ${\displaystyle V}$) must contain at least as many elements as a basis of ${\displaystyle \operatorname {im} (f)}$, that is, ${\displaystyle \dim(V)\geq \dim(\operatorname {im} (f))}$.

Proof step: "${\displaystyle \Leftarrow }$"

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

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

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