Exercises Linear Maps – "Math for Non-Geeks"

We have compiled some tasks on linear maps here. The proof structures can help you to solve other similar tasks. As a reminder, here is the definition of a linear map:

Definition (Linear map)

Let $f:V\to W$ be a mapping between the two vector spaces $V$ and $W$. We call $f$ a linear map from $V$ to $W$ if the following two properties are satisfied:

1. Additivity: For all $v_1,v_2\in V$ we have $f(v_1+v_2)=f(v_1)+f(v_2)$
2. Homogeneity: For all $v\in V$ and $\lambda \in K$ we have $f(\lambda \cdot v)=\lambda \cdot f(v)$

Proving linearity of a mapping

Linear maps from ${ℝ}^n$ to ${ℝ}^m$

Exercise (Linear map into a field)

Let $f:{ℝ}^3\to ℝ$ be defined by $f((x,y,z{)}^T):=5x+y-3z$. Show that the map $f$ is linear.

How to get to the proof? (Linear map into a field)

First you have to show the additivity and then homogeneity of the map.

Solution (Linear map into a field)

Proof step: Additivity

For this step, let $v=\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)\in {ℝ}^3$ and $w=\left(\begin{array}{c}{w}_1\\ w_2\\ w_3\end{array}\right)\in {ℝ}^3$.

$\begin{array}{cc}f(v+w)& =\\ & =f(\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)+\left(\begin{array}{c}{w}_1\\ w_2\\ w_3\end{array}\right))=f\left(\begin{array}{c}{v}_1+w_1\\ v_2+w_2\\ v_3+w_3\end{array}\right)\\ & \downarrow \text{definition of }f\\ & =5(v_1+w_1)+(v_2+w_2)-3(v_3+w_3)\\ & \downarrow \text{distributivity in }ℝ\\ & =5v_1+5w_1+v_2+w_2-3v_3-3w_3\\ & \downarrow \text{commutativity and associativity in }ℝ\\ & =(5v_1+v_2-3v_3)+(5w_1+w_2-3w_3)\\ & \downarrow \text{definition of }f\\ & =f\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)+f\left(\begin{array}{c}{w}_1\\ w_2\\ w_3\end{array}\right)=f(v)+f(w)\end{array}$

Thus $f$ is additive.

Proof step: Homogeneity

Let $v=\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)\in {ℝ}^3$ and $\lambda \in ℝ$.

$\begin{array}{cc}f(\lambda \cdot v)& =f(\lambda \cdot \left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right))=f\left(\begin{array}{c}\lambda v_1\\ \lambda v_2\\ \lambda v_3\end{array}\right)\\ & \downarrow \text{definition of }f\\ & =5(\lambda v_1)+(\lambda v_2)-3(\lambda v_3)\\ & \downarrow \text{associativity of the multiplication in }ℝ\\ & =\lambda \cdot (5v_1)+\lambda \cdot (v_2)-\lambda \cdot (3v_3)\\ & \downarrow \text{distributivity in }ℝ\\ & =\lambda \cdot (5v_1+v_2-3v_3)\\ & \downarrow \text{definition of }f\\ & =\lambda \cdot f\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)=\lambda \cdot f(v)\end{array}$

Thus $f$ is homogeneous and $f$ is linear.

Exercise (Linear map from ${ℝ}^3$ to ${ℝ}^2$)

Show that the map $L:{ℝ}^3\to {ℝ}^2$ with $L\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right):=\left(\begin{array}{c}{v}_2-v_3\\ 3v_1+5v_3\end{array}\right)$ is linear.

How to get to the proof? (Linear map from ${ℝ}^3$ to ${ℝ}^2$)

You have to show that for $v=(v_1,v_2,v_3{)}^T$ and $w=(w_1,w_2,w_3{)}^T$ it holds true that

$L(\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)+\left(\begin{array}{c}{w}_1\\ w_2\\ w_3\end{array}\right))=L\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)+L\left(\begin{array}{c}{w}_1\\ w_2\\ w_3\end{array}\right)$

And you have to show that for $\rho \in ℝ$, it holds true that

$L(\rho \cdot \left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right))=\rho \cdot L\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)$

Solution (Linear map from ${ℝ}^3$ to ${ℝ}^2$)

Aktuelles Ziel: Additivity

$\begin{array}{cc}L(\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)+\left(\begin{array}{c}{w}_1\\ w_2\\ w_3\end{array}\right))& =L\left(\begin{array}{c}{v}_1+w_1\\ v_2+w_2\\ v_3+w_3\end{array}\right)\\ & \downarrow \text{definition of }L\\ & =\left(\begin{array}{c}(v_2+w_2)-(v_3+w_3)\\ 3(v_1+w_1)+5(v_3+w_3)\end{array}\right)\\ & \downarrow \text{commutative, associative, distributive in }ℝ\\ & =\left(\begin{array}{c}(v_2-v_3)+(w_2-w_3)\\ (3v_1-5v_3)+(3w_1-5w_3)\end{array}\right)\\ & =\left(\begin{array}{c}(v_2-v_3)\\ (3v_1-5v_3)\end{array}\right)+\left(\begin{array}{c}(w_2-w_3)\\ (3w_1-5w_3)\end{array}\right)\\ & \downarrow \text{definition of }L\\ & =L\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)+L\left(\begin{array}{c}{w}_1\\ w_2\\ w_3\end{array}\right)\end{array}$

Aktuelles Ziel: Scaling

$\begin{array}{cc}L(\rho \cdot \left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right))& =L\left(\begin{array}{c}\rho v_1\\ \rho v_2\\ \rho v_3\end{array}\right)\\ & \downarrow \text{definition of }L\\ & =\left(\begin{array}{c}\rho v_2-\rho v_3\\ 3(\rho v_1)+5(\rho v_3)\end{array}\right)\\ & \downarrow \text{commutative, associative, distributive in }ℝ\\ & =\left(\begin{array}{c}\rho (v_2-v_3)\\ (\rho (3v_1+5v_3)\end{array}\right)\\ & =\rho \cdot \left(\begin{array}{c}(v_2-v_3)\\ (3v_1+5v_3)\end{array}\right)\\ & \downarrow \text{definition of }L\\ & =\rho \cdot L\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)\end{array}$

Exercise (Linearity of the embedding)

Show that for $m\ge n$, the map $f:{ℝ}^n\to {ℝ}^m:(x_1,x_2,\dots ,x_n{)}^T\mapsto (x_1,x_2,\dots ,x_n,\underset{(m-n)\text{ times}}{\underbrace{0,\dots ,0}}{)}^T$ is linear.

Solution (Linearity of the embedding)

Let $v=(v_1,\dots ,v_n{)}^T\in {ℝ}^n$ and $w=(w_1,\dots ,w_n{)}^T\in {ℝ}^n$, as well as $\lambda ,\mu \in ℝ$. By definition of the map $f$, we have that

$f(\lambda v+\mu w)=f\left(\left(\begin{array}{c}\lambda v_1+\mu w_1\\ ⋮\\ \lambda v_n+\mu w_n\end{array}\right)\right)=\left(\begin{array}{c}\lambda v_1+\mu w_1\\ ⋮\\ \lambda v_n+\mu w_n\\ 0\\ ⋮\\ 0\end{array}\right)=\lambda \cdot \left(\begin{array}{c}{v}_1\\ ⋮\\ v_n\\ 0\\ ⋮\\ 0\end{array}\right)+\mu \cdot \left(\begin{array}{c}{w}_1\\ ⋮\\ w_n\\ 0\\ ⋮\\ 0\end{array}\right)=\lambda f(v)+\mu f(w).$

So $f$ is linear.

We consider an example for a linear map of ${ℝ}^2$ to ${ℝ}^2$:

$f:{ℝ}^2\to {ℝ}^2$ with $f\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}{x}_1+x_2\\ x_1-5x_2\end{array}\right)$

Exercise (Linearity of $f$)

Show that the map $f:{ℝ}^2\to {ℝ}^2,\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)\mapsto \left(\begin{array}{c}{x}_1+x_2\\ x_1-5x_2\end{array}\right)$ is linear.

Proof (Linearity of $f$)

${ℝ}^2$ is an $ℝ$-vector space. In addition, the map is well-defined.

Proof step: additivity

Let $(x_1,x_2{)}^T$ and $(y_1,y_2{)}^T$ be any vectors from the plane ${ℝ}^2$. Then, we have:

$\begin{array}{cc}f(\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)+\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right))& =f\left(\begin{array}{c}{x}_1+y_1\\ x_2+y_2\end{array}\right)\\ & \downarrow \text{definition of }f\\ & =\left(\begin{array}{c}(x_1+y_1)+(x_2+y_2)\\ (x_1+y_1)-5\cdot (x_2+y_2)\end{array}\right)\\ & \downarrow \text{distributive law}\\ & =\left(\begin{array}{c}(x_1+x_2)+(y_1+y_2)\\ (x_1-5x_2)+(y_1-5y_2)\end{array}\right)\\ & \downarrow \text{separate vectors}\\ & =\left(\begin{array}{c}{x}_1+x_2\\ x_1-5x_2\end{array}\right)+\left(\begin{array}{c}{y}_1+y_2\\ y_1-5y_2\end{array}\right)\\ & \downarrow \text{definition of }f\\ & =f\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)+f\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)\end{array}$

Proof step: homogeneity

Let $\lambda \in ℝ$ and $(x_1,x_2{)}^T\in {ℝ}^2$. Then:

$\begin{array}{cc}f(\lambda \cdot \left(\begin{array}{c}{x}_1\\ x_2\end{array}\right))& =f\left(\begin{array}{c}\lambda \cdot x_1\\ \lambda \cdot x_2\end{array}\right)\\ & \downarrow \text{definition of }f\\ & =\left(\begin{array}{c}\lambda x_1+\lambda x_2\\ \lambda x_1-5\lambda x_2\end{array}\right)\\ & \downarrow \text{distributive law}\\ & =\left(\begin{array}{c}\lambda (x_1+x_2)\\ \lambda (x_1-5x_2)\end{array}\right)\\ & \downarrow \text{scalar multiplication}\\ & =\lambda \cdot \left(\begin{array}{c}(x_1+x_2)\\ (x_1-5x_2)\end{array}\right)\\ & \downarrow \text{definition of }f\\ & =\lambda \cdot f\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)\\ \end{array}$

Thus, the map is linear.

Important special cases

Exercise (The identity is a linear map)

Let $V$ be a $K$-vector space. Prove that the identity $\mathrm{id}:V\to V$ with $\mathrm{id}(v)=v$ is a linear map.

Proof (The identity is a linear map)

The identity is additive: Let $v,w\in V$, then.

$\mathrm{id}(v+w)=v+w=\mathrm{id}(v)+\mathrm{id}(w)$

The identity is homogeneous: Let $\lambda \in K$ and $v\in V$, then

$\mathrm{id}(\lambda \cdot v)=\lambda \cdot v=\lambda \cdot \mathrm{id}(v)$

Exercise (The map to zero is a linear map)

Let $V,W$ be two $K$-vector spaces. Show that the map to zero $f:V\to W$, which maps all vectors $v\in V$ to the zero vector $0_{{}_W}$, is linear.

Proof (The map to zero is a linear map)

$f$ is additive: let $v_1,v_2$ be vectors in $V$. Then

$f(v_1+v_2)=0_{{}_W}=0_{{}_W}+0_{{}_W}=f(v_1)+f(v_2)$

$f$ is homogeneous: Let $v\in V$ and let $\lambda \in K$. Then

$f(\lambda \cdot v)=0_{{}_W}=\lambda \cdot 0_{{}_W}=\lambda \cdot f(v)$

Thus, the map to zero is linear

Linear maps between function spaces

Exercise (Mapping on a function space)

Consider the function space $\mathrm{Fun}([0,1],ℝ)$ of all functions from $ℝ$ to $ℝ$, as well as the map

$\begin{array}{cc}\varphi :\mathrm{Fun}([0,1],ℝ)& \to ℝ,\\ f& \mapsto f(0).\end{array}$

Show that $\varphi$ is linear.

Solution (Mapping on a function space)

The operations on the function space are defined element-wise in each case. That means: for $f,g\in \mathrm{Fun}([0,1],ℝ)$, $\lambda \in ℝ$ and $x\in [0,1]$ we have that $(f+g)(x)=f(x)+g(x)$ and $(\lambda f)(x)=\lambda f(x)$. In particular, this is true for $x=0$, which implies

$\begin{array}{c}\varphi (f+g)=(f+g)(0)=f(0)+g(0)=\varphi (f)+\varphi (g)\end{array}$

and

$\begin{array}{c}\varphi (\lambda f)=(\lambda f)(0)=\lambda f(0)=\lambda \varphi (f)\end{array}$

Thus, we have established linearity.

Exercise (The composition with a map is linear.)

Let $V$ be a vector space, let $M,N$ be sets, and let $\text{Fun}(M,V)$ or $\text{Fun}(N,V)$ be the vector space of functions from $M$ or $N$ to $V$. Let $t\in \text{Fun}(N,M)$ be arbitrary but fixed. We consider the mapping

$\begin{array}{cc}\mathrm{\Theta }:\text{Fun}(M,V)& \to \text{Fun}(N,V)\\ g& \mapsto g\circ t\end{array}$

Show that $\mathrm{\Theta }$ is linear.

It is important that you exactly follow the definitions. Note that $\mathrm{\Theta }$ is a map that assigns to every map of $M$ to $V$ a map of $N$ to $V$. These maps, which are elements of $\text{Fun}(M,V)$ and $\text{Fun}(N,V)$ respectively, need not themselves be linear, since there is no vector space structure on the sets $M$ and $N$.

Summary of proof (The composition with a map is linear.)

In order to prove the linearity of $\mathrm{\Theta }$, we need to check the two properties again:

1. $\mathrm{\Theta }$ is additive: $\mathrm{\Theta }(g+h)=\mathrm{\Theta }(g)+\mathrm{\Theta }(h)$ for all $g,h\in \text{Fun}(M,V)$
2. $\mathrm{\Theta }$ is homogeneous: $\mathrm{\Theta }(\lambda \cdot g)=\lambda \cdot \mathrm{\Theta }(g)$ for all $g\in \text{Fun}(M,V)$ and $\lambda \in K$

So at both points an equivalence of maps $N\to V$ is to be shown. For this, we evaluate the maps at every m element $y\in N$.

Proof (The composition with a map is linear.)

Let $g,h\in \text{Fun}(M,V)$.

Proof step: additivity

For all $n\in N$ we have that

$\begin{array}{cc}\mathrm{\Theta }(g+h)(n)& =\\ & \downarrow \text{definition of }\mathrm{\Theta }\\ & =((g+h)\circ t)(n)\\ & =(g+h)(t(n))\\ & \downarrow \text{vector addition on Fun}(M,V)\\ & =g(t(n))+h(t(n))\\ & =(g\circ t)(n)+(h\circ t)(n)\\ & \downarrow \text{definition of }\mathrm{\Theta }\\ & =\mathrm{\Theta }(g)(n)+\mathrm{\Theta }(h)(n)\\ & \downarrow \text{vector addition on Fun}(N,V)\\ & =(\mathrm{\Theta }(g)+\mathrm{\Theta }(h))(n)\end{array}$

Thus, we have shown $\mathrm{\Theta }(g+h)=\mathrm{\Theta }(g)+\mathrm{\Theta }(h)$, i.e., $\mathrm{\Theta }$ is additive.

Let $g\in \text{Fun}(M,V)$ and $\lambda \in K$.

Proof step: homogeneity

For all $n\in N$ we have that

$\begin{array}{cc}\mathrm{\Theta }(\lambda \cdot g)(n)& =\\ & \downarrow \text{definition of }\mathrm{\Theta }\\ & =((\lambda \cdot g)\circ t)(n)\\ & =(\lambda \cdot g)(t(n))\\ & \downarrow \text{scalar multiplication on Fun}(M,V)\\ & =\lambda \cdot g(t(n))\\ & =\lambda \cdot (g\circ t)(n)\\ & \downarrow \text{definition of }\mathrm{\Theta }\\ & =\lambda \cdot \mathrm{\Theta }(g)(n)\\ & \downarrow \text{scalar multiplication on Fun}(N,V)\\ & =(\lambda \cdot \mathrm{\Theta }(g))(n)\end{array}$

Thus, we have shown $\mathrm{\Theta }(\lambda \cdot g)=\lambda \cdot \mathrm{\Theta }(g)$, i.e., $\mathrm{\Theta }$ is homogeneous.

Now, additivity and homogeneity of $\mathrm{\Theta }$ implies that $\mathrm{\Theta }$ is a linear map.

Exercise (Sequence space)

Let $V$ be the $ℝ$-vector space of all real-valued sequences. Show that the map

$\begin{array}{cc}f:V& \to V\\ (a_0,a_1,a_2,\dots )& \mapsto (a_1,a_2,a_3,\dots )\end{array}$

is linear.

How to get to the proof? (Sequence space)

To show linearity, two properties need to be checked:

1. $f$ is additive: $f(v+w)=f(v)+f(w)$ for all $v,w\in V$
2. $f$ is homogeneous: $f(\lambda \cdot v)=\lambda \cdot f(v)$ for all $v\in V$ and $\lambda \in ℝ$

The vectors $v$ and $w$ are sequences of real numbers, i.e. they are of the form $v=(a_0,a_1,a_2,\dots )$ and $w=(b_0,b_1,b_2,\dots )$ with $a_k,b_k\in ℝ$ for all $k\in {\mathbb{N}}_0$.

Proof (Sequence space)

Proof step: additivity

Let $v=(a_0,a_1,a_2,\dots )\in V$ and $w=(b_0,b_1,b_2,\dots )\in V$. Then, we have

$\begin{array}{cc}f(v+w)& =f((a_0,a_1,a_2,\dots )+(b_0,b_1,b_2,\dots ))\\ & =f(a_0+b_0,a_1+b_1,a_2+b_2,\dots )\\ & =(a_1+b_1,a_2+b_2,a_3+b_3,\dots )\\ & =(a_1,a_2,a_3,\dots )+(b_1,b_2,b_3,\dots )\\ & =f(a_0,a_1,a_2,\dots )+f(b_0,b_1,b_2,\dots )\\ & =f(v)+f(w)\end{array}$

It follows that $f$ is additive.

Proof step: homogeneity

Let $v=(a_0,a_1,a_2,\dots )\in V$ and $\lambda \in ℝ$. Then, we have

$\begin{array}{cc}f(\lambda \cdot v)& =f(\lambda \cdot (a_0,a_1,a_2,\dots ))\\ & =f(\lambda a_0,\lambda a_1,\lambda a_2,\dots )\\ & =(\lambda a_1,\lambda a_2,\lambda a_3,\dots )\\ & =\lambda \cdot (a_1,a_2,a_3,\dots )\\ & =\lambda \cdot f(a_0,a_1,a_2,\dots )\\ & =\lambda \cdot f(v)\end{array}$

So $f$ is homogeneous.

Thus, it was proved that $f$ is a $ℝ$-linear map.

Construction of a linear map from given values

Exercise (Construction of a linear map)

Let $a_1=(1,0,0{)}^T,a_2=(0,1,0{)}^T,a_3=(1,1,0{)}^T,a_4=(0,0,1{)}^T\in {ℝ}^3$.

Further, consider $b_1=(1,5{)}^T,b_2=(5,3{)}^T,b_3=(6,8{)}^T,b_4=(0,1{)}^T\in {ℝ}^2$.

Find a linear map $f:{ℝ}^3\to {ℝ}^2$ with $f(a_i)=b_i$ for all $i\in \{1,2,3,4\}$.

How to get to the proof? (Construction of a linear map)

Hint: Use the principle of linear continuation.

Solution (Construction of a linear map)

We see that $(a_1,a_2,a_4)$ is a basis of ${ℝ}^3$, namely the standard basis.

According to the theorem of linear continuation, we can construct a linear map

$f:{ℝ}^3\to {ℝ}^2$ defined by $f(a_1):=b_1,f(a_2):=b_2,f(a_4):=b_4$

Now we only have to check if $f(a_3)=b_3$ is satisfied. It is true that $a_3=a_1+a_2$, so

$f(a_3)=f(a_1+a_2)=f(a_1)+f(a_2)=b_1+b_2=(1,5{)}^T+(5,3{)}^T=(6,8{)}^T=b_3$

Thus, the condition $f(a_i)=b_i$ is satisfied for each $i\in \{1,2,3,4\}$. The mapping $f$ is linear by definition, so we are done.

Exercise (Linear maps under some conditions)

Let $u=(1,0,-1{)}^T,v=(0,1,2{)}^T$ and $w=(1,2,3{)}^T$. Is there an $ℝ$-linear map $f:{ℝ}^3{ℝ}^2$ that satisfies $f(u)=(0,1{)}^T,f(v)=(1,-1{)}^T,f(w)=(2,1{)}^T$?

How to get to the proof? (Linear maps under some conditions)

First you should check if the vectors $u,v,w$ are linearly independent. If this is the case, $\{u,v,w\}$ is a basis of ${ℝ}^3$ because of $\dim ({ℝ}^3)=3$. Using the principle of linear continuation, the existence of such a linear map would follow $f$. Let thus ${\lambda }_1,{\lambda }_2,{\lambda }_3\in ℝ$:

${\lambda }_{1}u+{\lambda }_{2}v+{\lambda }_{3}w=\left(\begin{array}{c}{\lambda }_1+{\lambda }_3\\ {\lambda }_2+2{\lambda }_3\\ -{\lambda }_1+2{\lambda }_2+3{\lambda }_3\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right).$

But then also ${\lambda }_1=-{\lambda }_3,{\lambda }_2=-2{\lambda }_3$ and so $2{\lambda }_1={\lambda }_2$ must be fulfilled. However, this equation has not only the "trivial" solution ${\lambda }_1={\lambda }_2={\lambda }_3=0$. In fact, the upper equation is satisfied for ${\lambda }_1=1,{\lambda }_2=2,{\lambda }_3=-1$. Thus, one obtains

$\begin{array}{c}u+2v=w.\end{array}$

For such a map $f$, the relation $f(u)+2f(v)=f(w)$ would then have to hold, which is a contradiction to

$\begin{array}{c}f(u)+2f(v)=(2,-1{)}^T,f(w)=(2,1{)}^T\end{array}$

Solution (Linear maps under some conditions)

Let us first assume that such a linear map $f$ would exist. By the following calculation

$\begin{array}{c}u+2v=\left(\begin{array}{c}1\\ 0\\ -1\end{array}\right)+\left(\begin{array}{c}0\\ 2\\ 4\end{array}\right)=\left(\begin{array}{c}1\\ 2\\ 3\end{array}\right)=w\end{array}$

we see that $f(u)+2f(v)=f(w)$ should hold. But this is a contradiction to the other conditions, because those would imply

$\begin{array}{c}f(u)+2f(v)=(0,1{)}^T+2(1,-1{)}^T=(2,-1{)}^T\ne (2,1{)}^T=f(w)\end{array}$

So there is no such $f$.

Linear independence of two preimages

Exercise

Let $L:V\to W$ be a linear map and let $v_1$ and $v_2$ be two distinct vectors from $V$, both mapped to a vector $w\in W$ with $w\ne 0_W$. Prove that $v_1$ and $v_2$ are linearly independent.

How to get to the proof?

We show that the two vectors cannot be linearly dependent. So assume that $v_1,v_2$ were linearly dependent. Then there would be a $\rho \in K$ such that $v_1=\rho \cdot v_2$. We now map these two dependent vectors into the vector space $W$ using the linear map $L$. This yields

$w=\rho \cdot w$

Since by premise, $w\ne 0$, this is a contradiction and our assumption of linear dependence must be false.

Solution

Assume that $v_1$ and $v_2$ were linearly dependent. Then there would be a $\rho \in K$ with $v_1=\rho \cdot v_2$ and $\rho \ne 1$. Since the map $L$ is linear, it follows that

$w=L(v_2)=L(v_1)=L(\rho \cdot v_2)=\rho \cdot L(v_2)=\rho \cdot w$

Thus

$w=\rho \cdot w\Rightarrow w-\rho \cdot w=(1_K-\rho )\cdot w=0_W\Rightarrow 1_K-\rho =0_K\vee w=0_W$

Since by assumption $w\ne 0_W$, we must have $1_K-\rho =0_K$. But this contradicts our assumption $\rho \ne 1_K$. Thus, we get a contradiction to our assumption of linear dependence. So the vectors $v_1,v_2\in V$ are linearly independent.

Exercises: Isomorphisms

Exercise (complex $ℝ$-vector spaces)

Let $V$ be a finite-dimensional $ℂ$-vector space. Show that $V\cong {ℝ}^{2{\dim }_{ℂ}(V)}$ (interpreted as $ℝ$-vector spaces).

Solution (complex $ℝ$-vector spaces)

Set $n:={\dim }_{ℂ}(V)$. We choose a $ℂ$ basis $ℬ=\{b_1,\dots ,b_n\}$ of $V$. Define $c_j:=i\cdot b_j$ for all $1\le j\le n$.

We have to show that $\{b_1,\dots ,b_n,c_1,\dots ,c_n\}$ is an $ℝ$-basis of $V$. Then, ${\dim }_{ℝ}(V)=2n={\dim }_{ℝ}({ℝ}^{2n})$. According to a theorem above, we have $V\cong {ℝ}^{2n}$ as $ℝ$-vector spaces.

We now show $ℝ$-linear independence.

Proof step: $\{b_1,\dots ,b_n,c_1,\dots ,c_n\}$ is $ℝ$-linearly independent

Let ${\beta }_1,\dots ,{\beta }_n,{\gamma }_1,\dots ,{\gamma }_n\in ℝ$ and assume that $\sum _{j=1}^n{\beta }_j\cdot b_j+\sum _{j=1}^n{\gamma }_j\cdot c_j=0$. We substitute the definition for $c_j$, conclude the sums and obtain $\sum _{j=1}^n({\beta }_j+i\cdot {\gamma }_j)\cdot b_j=0$. By $ℂ$-linear independence of $b_j$ we obtain ${\beta }_j+i\cdot {\gamma }_j=0$ for all $j\in \{1,\dots ,n\}$. Thus, ${\beta }_j={\gamma }_j=0$ for all $j\in \{1,\dots ,n\}$. This establishes the $ℝ$-linear independence.

Now only one step is missing:

Proof step: $\{b_1,\dots ,b_n,c_1,\dots ,c_n\}$ is a generator with respect to $ℝ$

Let $v\in V$ be arbitrary.

Since $ℬ$ is a $ℂ$-basis of $V$ , we can find some ${\lambda }_1,\dots ,{\lambda }_n\in ℂ$, such that $v=\sum _{j=1}^n{\lambda }_j\cdot b_j$ . We write ${\lambda }_j={\beta }_j+{\gamma }_{j}i$ with ${\beta }_j,{\gamma }_j\in ℝ$ for all $j$. Then we obtain

$\begin{array}{cc}v& =\sum _{j=1}^n{\lambda }_j\cdot b_j\\ & =\sum _{j=1}^n({\beta }_j+{\gamma }_{j}i)\cdot b_j\\ & =\sum _{j=1}^n({\beta }_j\cdot b_j+{\gamma }_j\cdot (i\cdot b_j))\\ & =\sum _{j=1}^n({\beta }_j\cdot b_j+{\gamma }_j\cdot c_j)\\ & =\sum _{j=1}^n{\beta }_j\cdot b_j+\sum _{j=1}^n{\gamma }_j\cdot c_j.\end{array}$

So $v$ is inside the $ℝ$-span of $\{b_1,\dots ,b_n,c_1,\dots ,c_n\}$. This establishes the assertion.

Exercise (Isomorphic coordinate spaces)

Let $K$ be a field and consider $n,m\in {\mathbb{N}}_0$. Prove that $K^n\cong K^m$ holds if and only if $m=n$.

Solution (Isomorphic coordinate spaces)

We know that $\dim (K^k)=k$ for all $k\in {\mathbb{N}}_0$. We use the theorem above, which states that finite-dimensional vector spaces are isomorphic exactly if their dimensions coincide. So $K^n\cong K^m$ holds if and only if $n=\dim (K^n)=\dim (K^m)=m$ .

Exercise (Isomorphism criteria for endomorphisms)

Let $K$ be a field, $V$ a finite-dimensional $K$-vector space and $f:V\to V$ a $K$-linear map. Prove that the following three statements are equivalent:

(i) $f$ is an isomorphism.

(ii) $f$ is injective.

(iii) $f$ is surjective.

(Note: For this task, it may be helpful to know the terms kernel and image of a linear map. Using the dimension theorem, this exercise becomes much easier. However, we give a solution here, which works without the dimension theorem).

Solution (Isomorphism criteria for endomorphisms)

(i)$⟹$(ii) and (iii): According to the definition of an isomorphism, $f$ is bijective, i.e. injective and surjective. Therefore (ii) and (iii) hold.

(ii)$⟹$(i): Let $f$ be an injective mapping. We need to show that $f$ is also surjective. The image $\mathrm{i}\mathrm{m}(f):=\{f(v)|v\in V\}$ of $f$ is a subspace of $V$. This can be verified by calculation. We now define a mapping $f^{\prime }$ that does the same thing as $f$, except that it will be surjective by definition. This mapping is defined as follows:

$\begin{array}{cc}{f}^{\prime }:V& \to \mathrm{i}\mathrm{m}(f)\\ v& \mapsto f(v)\end{array}$

The surjectivity comes from the fact that every element $w\in \mathrm{i}\mathrm{m}(f)$ can be written as $w=f(v^{\prime })$, for a suitable $v^{\prime }\in V$. Moreover, the mapping $f^{\prime }$ is injective and linear. This is because $f$ already has these two properties. So $V$ and $\mathrm{i}\mathrm{m}(f)$ are isomorphic. Therefore, $V$ and $\mathrm{i}\mathrm{m}(f)$ have the same finite dimension. Since $\mathrm{i}\mathrm{m}(f)$ is a subspace of $V$, $\mathrm{i}\mathrm{m}(f)=V$ holds. This can be seen by choosing a basis in $\mathrm{i}\mathrm{m}(f)$, for instance the basis given by the vectors $v_1,\dots ,v_n\in \mathrm{i}\mathrm{m}(f)$. These $v_1,\dots ,v_n$ are also linearly independent in $V$, since $\mathrm{i}\mathrm{m}(f)\subseteq V$. And since $V$ and $\mathrm{i}\mathrm{m}(f)$ have the same dimension, the $v_1,\dots ,v_n$ are also a basis in $V$. So the two vector spaces $V$ and $\mathrm{i}\mathrm{m}(f)$ must now be the same, because all elements from them are $K$-linear combinations formed with the $v_1,\dots ,v_n$. Thus, we have shown that $f$ is surjective.

(iii)$⟹$(i): Now suppose $f$ is surjective. We need to show that $f$ is also injective. Let $\mathrm{k}\mathrm{e}\mathrm{r}(f):=\{v\in V|f(v)=0\}$ be the kernel of the mapping $f$. You may convince yourself by calculation, that this kernel is a subspace of $V$. Let $v_1,\dots ,v_k$ be a basis of $\mathrm{k}\mathrm{e}\mathrm{r}(f)$. We can complete this (small) basis to a (large) basis of $V$, by including the additional vectors $v_{k+1},\dots ,v_n$. We will now show that $f(v_{k+1}),\dots ,f(v_n)$ are linearly independent. So let coefficients ${\lambda }_{k+1},\dots ,{\lambda }_n\in K$ be given such that

$\begin{array}{c}{\lambda }_{k+1}f(v_{k+1})+\dots +{\lambda }_{n}f(v_n)=0.\end{array}$

By linearity of $f$ we conclude: $f({\lambda }_{k+1}{v}_{k+1}+\dots {\lambda }_n{v}_n)=0$. This means that the linear combination

$\begin{array}{c}{\lambda }_{k+1}{v}_{k+1}+\dots +{\lambda }_n{v}_n\end{array}$

is in the kernel of $f$. But we already know a basis of $\mathrm{k}\mathrm{e}\mathrm{r}(f)$. Therefore, there are coefficients ${\lambda }_1,\dots ,{\lambda }_k\in K$, such that

$\begin{array}{c}{\lambda }_{k+1}{v}_{k+1}+\dots +{\lambda }_n{v}_n={\lambda }_1{v}_1+\dots +{\lambda }_k{v}_k.\end{array}$

Because of the linear independence of $v_1,\dots ,v_n$ it now follows that ${\lambda }_1,\dots ,{\lambda }_n=0$. Therefore, the $f(v_{k+1}),\dots ,f(v_n)$ are linearly independent. Next, we will show that these vectors also form a basis of $V$. To do this, we show that each vector in $V$ can be written as a linear combination of the $f(v_{k+1}),\dots ,f(v_n)$. Let $w\in V$. Because of the surjectivity of $f$, there is a $v\in V$, with $w=f(v)$. Since the $v_1,\dots ,v_n$ form a basis of $V$, there are coefficients ${\lambda }_1,\dots ,{\lambda }_n\in K$ such that

$\begin{array}{c}v={\lambda }_1{v}_1+\dots +{\lambda }_n{v}_n\end{array}$

If we now apply $f$ to this equation, we get:

$\begin{array}{c}w=f(v)={\lambda }_1\underset{=0}{\underbrace{f(v_1)}}+\dots +{\lambda }_k\underset{=0}{\underbrace{f(v_k)}}+{\lambda }_{k+1}f(v_{k+1})+\dots +{\lambda }_{n}f(v_n).\end{array}$

Here we used the linearity of $f$. Since the first $k$ elements of our basis are in the kernel, their images are $0$. So we get the desired representation of $w$:

$\begin{array}{c}w=f(v)={\lambda }_{k+1}f(v_{k+1})+\dots +{\lambda }_{n}f(v_n).\end{array}$

Thus, we have shown that $f(v_{k+1}),\dots ,f(v_n)$ forms a linearly independent generator of $V$. So these vectors form a basis of $V$. Now, if $k$ were not $0$, two finite bases in $V$ would not contain equally many elements. This cannot be the case. Therefore, $k=0$, so $\mathrm{k}\mathrm{e}\mathrm{r}(f)$ is the trivial vector space and $f$ is indeed injective.

Exercise (Function spaces)

Let $X$ be a finite set with $n\in \mathbb{N}$ elements and let $K$ be a field. We have seen that the set of functions from $X$ to $K$ forms a $K$-vector space, denoted by $\mathrm{Fun}(X,K)$. Show that $\mathrm{Fun}(X,K)\cong K^n$.

Solution (Function spaces)

We already know according to a theorem above that two finite dimensional vector spaces are isomorphic exactly if they have the same dimension. So we just need to show that $\dim (\mathrm{fun}(X,K))=n=\dim (K^n)$ holds.

To show this, we first need a basis of $\mathrm{Fun}(X,K)$. For this, let $x_1,\dots ,x_n$ be the elements of the set $X$. We define $f_1,\dots ,f_n\in \mathrm{Fun}(X,K)$ by

$f_j(x_i):={\delta }_{i,j}=\{\begin{array}{c}1,\text{ for }i=j\\ 0,\text{ for }i\ne j.\end{array}$

We now show that the functions $f_1,\dots ,f_n$ indeed form a basis of $\mathrm{Fun}(X,K)$.

Proof step: $f_1,\dots ,f_n$ are linearly independent

Let ${\alpha }_1,\dots ,{\alpha }_n\in K$ with $\sum _{k=1}^n{\alpha }_k\cdot f_k=0$ being the zero function. If we apply this function to any $x_j$ with $j\in \{1,\dots ,n\}$, then we obtain: $\sum _{k=1}^n{\alpha }_k\cdot f_k(x_j)=0$. By definition of $f_1,\dots ,f_n$ it follows that

$0=\sum _{k=1}^n{\alpha }_k{f}_k(x_j)={\alpha }_j\cdot f_j(x_j)={\alpha }_j\cdot 1={\alpha }_j$.

Since $j$ was arbitrary and $\sum _{k=1}^n{\alpha }_k\cdot f_k(x_j)=0$ must hold for all $x_j\in X$, it follows that ${\alpha }_1=\dots ={\alpha }_n=0$. So we have shown that $f_1,\dots ,f_n$ are linearly independent.

Proof step: $f_1,\dots ,f_n$ generate $\mathrm{Fun}(X,K)$

Let $g\in \mathrm{Fun}(X,K)$ be arbitrary. We now want to write $g$ as a linear combination of $f_1,\dots ,f_n$. For this we show $g=\sum _{j=1}^{n}g(x_j)\cdot f_j$, i.e., $g$ is a linear combination of $f_1,\dots ,f_n$ with coefficients $g(x_1),\dots ,g(x_n)\in K$. We now verify that $g(x_i)=\sum _{j=1}^{n}g(x_j)\cdot f_j(x_i)$ for all $i\in \{1,\dots ,n\}$. Let $i\in \{1,\dots ,n\}$ be arbitrary. By definition of $f_1,\dots ,f_n$ we obtain:

$\sum _{j=1}^{n}g(x_j)\cdot f_j(x_i)=g(x_i)\cdot f_i(x_i)=g(x_i)\cdot 1=g(x_i)$.

Since equality holds for all $i$, the functions agree at every point and are therefore identical. So we have shown that $f_1,\dots ,f_n$ generate $\mathrm{Fun}(X,K)$.

Thus, we have proved that $f_1,\dots ,f_n$ is a basis of $\mathrm{Fun}(X,K)$. Since we have $n$ basis elements of $\mathrm{Fun}(X,K)$, it follows that $\dim (\mathrm{Fun}(X,K))=n=\dim (K^n)$.

Exercises: Images

Exercise (Associating image spaces to figures)

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

1. $f:{ℝ}^2\to {ℝ}^2,(x,y{)}^T\mapsto (2(x+y),x-3y{)}^T$
2. $g:{ℝ}^2\to {ℝ}^2,(x,y{)}^T\mapsto (x,2x{)}^T$
3. $h:{ℝ}^2\to {ℝ}^2,(x,y{)}^T\mapsto (-3(x-y),(x-y){)}^T$
4. $k:{ℝ}^2\to {ℝ}^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 ${ℝ}^2$
• 
  $U_2$: The line spanned by $(3,-1{)}^T$
• 
  $U_3$: A plane covering all 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 $\mathrm{im}(f)$, we can apply a theorem from above: If $E$ is a generator of ${ℝ}^2$, then $\mathrm{im}(f)=\mathrm{span}(f(E))$ holds. We take the standard basis $\{(1,0{)}^T,(0,1{)}^T\}$ as the generator of ${ℝ}^2$. Then

$\mathrm{im}(f)=\mathrm{span}(f\left(\begin{array}{c}1\\ 0\end{array}\right),f\left(\begin{array}{c}0\\ 1\end{array}\right)).$

Now we apply $f$ to the standard basis

$\begin{array}{cc}f\left(\begin{array}{c}1\\ 0\end{array}\right)& =\left(\begin{array}{c}2\\ 1\end{array}\right)\\ f\left(\begin{array}{c}0\\ 1\end{array}\right)& =\left(\begin{array}{c}2\\ -3\end{array}\right)\end{array}$

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

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

$\begin{array}{cc}\mathrm{im}(g)& =\{g\left(\begin{array}{c}x\\ y\end{array}\right)\mid \left(\begin{array}{c}x\\ y\end{array}\right)\in {ℝ}^2\}\\ & =\{\left(\begin{array}{c}x\\ 2x\end{array}\right)\mid \left(\begin{array}{c}x\\ y\end{array}\right)\in {ℝ}^2\}\\ & =\{x\left(\begin{array}{c}1\\ 2\end{array}\right)\mid \left(\begin{array}{c}x\\ y\end{array}\right)\in {ℝ}^2\}\\ & \downarrow \text{The left side does not depend on }y\\ & =\{x\left(\begin{array}{c}1\\ 2\end{array}\right)\mid x\in ℝ\}\\ & =\mathrm{span}\left(\left(\begin{array}{c}1\\ 2\end{array}\right)\right)\end{array}$

So the image of $g$ is spanned by the vector $(1,2{)}^T$. Thus $\mathrm{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{array}{c}h\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}-3\\ 1\end{array}\right)\\ h\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}3\\ -1\end{array}\right)\end{array}$

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

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

$\begin{array}{cc}\mathrm{im}(k)& =\{k\left(\begin{array}{c}x\\ y\end{array}\right)\mid \left(\begin{array}{c}x\\ y\end{array}\right)\in {ℝ}^2\}\\ & =\{\left(\begin{array}{c}x\\ 0\end{array}\right)\mid \left(\begin{array}{c}x\\ y\end{array}\right)\in {ℝ}^2\}\\ & =\{x\left(\begin{array}{c}1\\ 0\end{array}\right)\mid \left(\begin{array}{c}x\\ y\end{array}\right)\in {ℝ}^2\}\\ & \downarrow \text{The left side does not depend on }y\\ & =\{x\left(\begin{array}{c}1\\ 0\end{array}\right)\mid x\in ℝ\}\\ & =\mathrm{span}\left(\left(\begin{array}{c}1\\ 0\end{array}\right)\right)\end{array}$

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

Exercise (Image of a matrix)

1. Consider the matrix $(1,2)\in {ℝ}^{1\times 2}$ and the mapping $f:{ℝ}^2\to ℝ,x\mapsto (1,2)x$ induced by it. What is the image $\mathrm{im}(f)$?
2. Now let $A=(a_1,\dots ,a_m)\in K^{n\times m}$ be any matrix over a field $K$, where $a_1,\dots ,a_m\in K^n$ denote the columns of $A$. Consider the mapping $f_A:K^m\to K^n,x\mapsto Ax$ induced by $A$. Show that $\mathrm{im}(f_A)=\mathrm{span}\{a_1,\dots ,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 $\mathrm{im}(f)$ of the linear map $f$ is a subspace of $ℝ$. Since the $ℝ$-vector space $ℝ$ 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 $ℝ$. So $ℝ$ has only the two subspaces $\{0\}$ and $ℝ$. Since $(1,2)(1,0{)}^T=1\ne 0$ holds, we have that $\mathrm{im}(f)\ne \{0\}$. Thus, $\mathrm{im}(f)=ℝ$.

Solution sub-exercise 2:

Proof step: "$\subseteq$"

Let $y\in \mathrm{im}(f_A)$. Then, there is some $x=(x_1,\dots ,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{array}{cc}y& =Ax\\ & \downarrow x=\sum _{i=1}^m{x}_i{e}_i\\ & =A\left(\sum _{i=1}^m{x}_i{e}_i\right)\\ & \downarrow \text{application of }A\text{ is linear}\\ & =\sum _{i=1}^m{x}_{i}A{e}_i\\ & \downarrow A{e}_i=a_i\text{, the }i\text{-th column of }A\\ & =\sum _{i=1}^m{x}_i{a}_i.\end{array}$

Since $\sum _{i=1}^m{x}_i{a}_i\in \mathrm{span}\{a_1,\dots ,a_n\}$, we obtain $y\in \mathrm{span}\{a_1,\dots ,a_n\}$.

Proof step: "$\supseteq$"

Let $y=\sum _{i=1}^m{y}_i\cdot a_i\in \mathrm{span}(f_A)$ with $y_i\in K$ for $i=1,\dots ,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}A{e}_i=\sum _{i=1}^m{y}_i{a}_i=y.$

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:V\to W$ if and only if $\dim (V)\ge \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\ge 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: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\ge m$ holds, we must construct a surjective linear map $f: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{array}{cc}{c}_i& i\le m\\ 0& i>m\end{array}$

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 $\mathrm{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)\ge \dim (\mathrm{im}(f))=\dim (W)$.

So let $w_1,\dots ,w_n\in \mathrm{im}(f)$ be linearly independent. There exists $v_1,\dots ,v_n\in V$ with $f(v_i)=w_i$ for $i\in \{1,\dots ,n\}$. We show that $v_1,\dots ,v_n$ are also linearly independent: Let ${\lambda }_1,\dots ,{\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,\dots ,w_n$, it follows that ${\lambda }_1=\dots ={\lambda }_n=0$. So $v_1,\dots ,v_n$ are also linearly independent. Overall, we have shown that

$w_1,\dots ,w_n\in \mathrm{im}(f)\text{ linearly independent }⟹v_1,\dots ,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 $\mathrm{im}(f)$, that is, $\dim (V)\ge \dim (\mathrm{im}(f))$.

Proof step: "$\Leftarrow$"

Assume that $\dim (V)\ge \dim (W)$. We use that a linear map is already uniquely determined by the images of the basis vectors. Let $\{v_1,\dots ,v_m\}$ be a basis of $V$ and $\{w_1,\dots ,w_n\}$ be a basis of $W$. Define the surjective linear map $f:V\to W$ by

$f(v_i)=\{\begin{array}{cc}{w}_i& \text{ if }i\le n\\ 0& \text{ else.}\end{array}$

This works, since by assumption, $m\ge n$ holds. The mapping constructed in this way is surjective, since by construction, $\{w_1,\dots ,w_n\}\subseteq \mathrm{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 \mathrm{im}(f)\subseteq W$ holds and $f$ is surjective.

Exercises: Kernel

Exercise

We consider the linear map $f:{ℝ}^2\to {ℝ}^2,(x,y{)}^T\mapsto (-3(x-y),x-y{)}^T$. Determine the kernel of $f$.

Solution

We are looking for vectors $(x,y{)}^T\in {ℝ}^2$ such that $f\left(\left(\begin{array}{c}x\\ y\end{array}\right)\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$. Let $(x,y{)}^T$ be any vector in ${ℝ}^2$ for which $f\left(\left(\begin{array}{c}x\\ y\end{array}\right)\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$ is true. We now examine what properties this vector must have. It holds that

$\left(\begin{array}{c}0\\ 0\end{array}\right)=f\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}-3(x-y)\\ x-y\end{array}\right)$

So $-3(x-y)=0$ and $x-y=0$. From this we conclude $x=y$. So any vector $(x,y{)}^T$ in the kernel of $f$ satisfies the condition $x=y$. Now take a vector $(x,x{)}^T$ with $x\in ℝ$. Then

$f\left(\begin{array}{c}x\\ x\end{array}\right)=\left(\begin{array}{c}-3(x-x)\\ x-x\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$

We see that $(x,x{)}^T\in \ker (f)$. In total

$\ker (f)=\{\left(\begin{array}{c}x\\ x\end{array}\right)|x\in ℝ\}$

Check your understanding: Can you visualize $\ker (f)$ in the plane? What does the image of $f$ look like? How do the kernel and the image relate to each other?

The kernel of f

We have already seen that

$\ker (f)=\{\left(\begin{array}{c}x\\ x\end{array}\right)\mid x\in ℝ\}=\mathrm{span}\left(\left(\begin{array}{c}1\\ 1\end{array}\right)\right)$

Now we determine the image of $f$ by applying $f$ to the canonical basis.

$\begin{array}{c}f\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}-3\\ 1\end{array}\right)\\ f\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}3\\ -1\end{array}\right)\end{array}$

So $\mathrm{im}(f)=\mathrm{span}(f((1,0{)}^T),f((0,1{)}^T))$ holds. We see that the two vectors are linearly dependent. That is, we can generate the image with only one vector: $\mathrm{im}(f)=\mathrm{span}((-3,1{)}^T)$.

• 
  The image of f
• 
  Image and kernel of f together

In our example, the image and the kernel of the linear map $f$ are straight lines through the origin. The two straight lines intersect only at the zero and together span the whole ${ℝ}^2$.

Exercise

Let $V$ be a vector space, $V\ne \{0\}$, and $f:V\to V$ be a nilpotent linear map, i.e., there is some $n\in \mathbb{N}$ such that

$f^n=\underset{n\text{ times}}{\underbrace{f\circ \cdots \circ f}}=0$

is the zero mapping. Show that $\ker (f)\ne \{0\}$ holds.

Does the converse also hold, that is, is any linear map $f:V\to V$ with $\ker (f)\ne \{0\}$ nilpotent?

Solution

Proof step: $f$ nilpotent $⟹\ker (f)\ne \{0\}$

We prove the statement by contraposition. That is we show: If $\ker (f)=\{0\}$, then $f$ is not nilpotent.

Let $\ker (f)=\{0\}$. Then $f$ is injective, and as a concatenation of injective functions, $f\circ f$ is also injective. By induction, it follows that for all $n\in \mathbb{N}$ the function $f^n=\underset{n\text{ times}}{\underbrace{f\circ \cdots \circ f}}$ is injective. But then also $\ker (f^n)=\{0\}$ for all $n\in \mathbb{N}$. Since the kernel of the zero mapping would be all of $V\ne \{0\}$, the map $f^n$ could not be the zero mapping for any $n\in \mathbb{N}$. Consequently, $f$ is not nilpotent.

Proof step: The converse implication

The converse implication does not hold. There are mappings that are neither injective nor nilpotent. For example, we can define

$f:{ℝ}^2\to {ℝ}^2,\left(\begin{array}{c}x\\ y\end{array}\right)\mapsto \left(\begin{array}{c}x\\ 0\end{array}\right)$

This mapping is not injective, because $(0,1{)}^T\in \ker (f)$. But it is also not nilpotent, because we have $f^n((1,0{)}^T)=(1,0)\ne 0$ for all $n\in \mathbb{N}$.

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

Let $V$ and $W$ be two finite-dimensional vector spaces. Show that there exists an injective linear map $f:V\to W$ if and only if $\dim (V)\le \dim (W)$.

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

To prove equivalence, we need to show two implications. For the execution, we use that every monomorphism $f:V\to W$ preserves linear independence: If $\{b_1,\dots ,b_n\}\subseteq V$ is a basis of $V$, then the $n$ vectors $f(b_1),\dots ,f(b_n)\in W$ are linearly independent. For the converse direction, we need to construct a monomorphism from $V$ to $W$ using the assumption $\dim V\le \dim W$. To do this, we choose bases in $V$ and $W$ and then use the principle of linear continuation to define a monomorphism by the images of the basis vectors.

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

Proof step: There is a monomorphism $⟹\dim (V)\le \dim (W)$

Let $f:V\to W$ be a monomorphism and $\{v_1,\mathrm{...},v_n\}$ a basis of $V$. Then $\{v_1,\mathrm{...},v_n\}$ is in particular linearly independent and therefore $\{f(v_1),\mathrm{...},f(v_n)\}$ is linearly independent. Thus, it follows that $\dim (W)\ge n=\dim (V)$. So $\dim (W)\ge \dim (V)$ is a necessary criterion for the existence of a monomorphism from $V$ to $W$.

Proof step: $\dim (V)\le \dim (W)⟹$ there is a monomorphism

Conversely, in the case $\dim (V)\le \dim (W)$ we can construct a monomorphism: Let $\{v_1,\dots ,v_n\}$ be a basis of $V$ and $\{w_1,\dots ,w_m\}$ be a basis of $W$. Then $n=\dim (V)\le \dim (W)=m$. We define a linear map $f:V\to W$ by setting

$f(v_i)=w_i$

for all $i=1,\dots ,n$. According to the principle of linear continuation, such a linear map exists and is uniquely determined. We now show that $f$ is injective by proving that $\ker (f)=\{0_V\}$ holds. Let $x\in \ker (f)$. Because $\{v_1,\dots ,v_n\}$ is a basis of $V$, there exist some ${\lambda }_1,\dots ,{\lambda }_n\in K$ with

$x=\sum _{i=1}^n{\lambda }_i{v}_i.$

Thus, we get $\begin{array}{cc}{0}_V=f(x)& =f\left(\sum _{i=1}^n{\lambda }_i{v}_i\right)\\ & \downarrow f\text{ is linear}\\ & =\sum _{i=1}^n{\lambda }_{i}f(v_i)\\ & \downarrow f(v_i)=w_i\\ & =\sum _{i=1}^n{\lambda }_i{w}_i\\ & \downarrow {\lambda }_i=0\text{ for }i>n\\ & =\sum _{i=1}^m{\lambda }_i{w}_i\end{array}$

Since $\{w_1,\dots ,w_m\}$ are linearly independent, ${\lambda }_i=0_K$ must hold for all $i=1,\dots ,n$. So it follows for $x$ that

$x=\sum _{i=1}^n{\lambda }_i{v}_i=\sum _{i=1}^n{0}_K\cdot v_i=0_V.$

We have shown that $\ker (f)=\{0_V\}$ holds and thus $f$ is a monomorphism.