# Proofs for linear maps – Serlo

Zur Navigation springen Zur Suche springen

We will give here a proof structure that shows how to prove linearity of a map.

## General procedure

### Recap: Definition of a linear map

We recall that a linear map (or homomorphism) is a structure-preserving map of a ${\displaystyle K}$-vector space ${\displaystyle V}$ into a ${\displaystyle K}$-vector space ${\displaystyle W}$. That is, for the map ${\displaystyle f\colon V\to W}$, the following two conditions must hold:

1. ${\displaystyle f}$ must be additive, i.e., for ${\displaystyle v,w\in V}$ we have that: ${\displaystyle f(v+w)=f(v)+f(w)}$
2. ${\displaystyle f}$ must be homogeneous, i.e., for ${\displaystyle v\in V,\lambda \in K}$ we have that: ${\displaystyle f(\lambda \cdot v)=\lambda \cdot f(v)}$.

So for a linear map it doesn't matter if we first do the addition or scalar multiplication in the vector space ${\displaystyle V}$ and then map the sum into the vector space ${\displaystyle W}$, or first map the vectors ${\displaystyle v,\,w}$ into the vector space ${\displaystyle W}$ and perform the addition or scalar multiplication there, using the images of the map.

### Proving that a map is linear

The proof that a map is linear can be done according to the following structure. First, we assume that a map ${\displaystyle f\colon V\to W}$ is given between vector spaces. That is, ${\displaystyle V}$ and ${\displaystyle W}$ are ${\displaystyle K}$-vector spaces and ${\displaystyle f}$ is well-defined. Then for the linearity of ${\displaystyle f}$ we have to show:

1. additivity: ${\displaystyle \forall v,\,w\in V:\quad f(v+w)=f(v)+f(w)}$
2. homogeneity: ${\displaystyle \forall v\in V\,\forall \lambda \in K:\quad f(\lambda \cdot v)=\lambda \cdot f(v)}$

Exercise (Introductory example)

We consider the following map

${\displaystyle f\colon \mathbb {R} ^{2}\to \mathbb {R} ,\quad f{\begin{pmatrix}v_{1}\\v_{2}\end{pmatrix}}:=2v_{1}+v_{2}}$

and show that it is linear.

Proof (Introductory example)

First, ${\displaystyle \mathbb {R} ^{2}}$ and ${\displaystyle \mathbb {R} }$ are vector spaces over the field ${\displaystyle \mathbb {R} }$. Moreover, the map ${\displaystyle f}$ is well-defined.

Let ${\displaystyle {\begin{pmatrix}v_{1}\\v_{2}\end{pmatrix}},\,{\begin{pmatrix}w_{1}\\w_{2}\end{pmatrix}}\in \mathbb {R} ^{2}}$.

{\displaystyle {\begin{aligned}f\left({\begin{pmatrix}v_{1}\\v_{2}\end{pmatrix}}+{\begin{pmatrix}w_{1}\\w_{2}\end{pmatrix}}\right)&=f{\begin{pmatrix}v_{1}+w_{1}\\v_{2}+w_{2}\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}f\right.}\\[0.3em]&=\ 2(v_{1}+w_{1})+(v_{2}+w_{2})\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{distributive law}}\right.}\\[0.3em]&=\ 2v_{1}+2w_{1}+v_{2}+w_{2}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{commutative and associative law }}\right.}\\[0.3em]&=\ (2v_{1}+v_{2})+(2w_{1}+w_{2})\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}f\right.}\\[0.3em]&=\ f{\begin{pmatrix}v_{1}\\v_{2}\end{pmatrix}}+f{\begin{pmatrix}w_{1}\\w_{2}\end{pmatrix}}\end{aligned}}}

Thus we have proved the additivity of ${\displaystyle f}$.

Proof step: proving homogeneity

Let ${\displaystyle {\begin{pmatrix}v_{1}\\v_{2}\end{pmatrix}}\in \mathbb {R} ^{2}}$ and ${\displaystyle \lambda \in \mathbb {R} }$. Then, we have

{\displaystyle {\begin{aligned}f\left(\lambda {\begin{pmatrix}v_{1}\\v_{1}\end{pmatrix}}\right)&=f{\begin{pmatrix}\lambda v_{1}\\\lambda v_{2}\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}f\right.}\\[0.3em]&=\ 2\lambda v_{1}+\lambda v_{2}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{distributive law }}\right.}\\[0.3em]&=\ \lambda (2v_{1}+v_{2})\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}f\right.}\\[0.3em]&=\ \lambda \cdot f{\begin{pmatrix}v_{1}\\v_{2}\end{pmatrix}}\end{aligned}}}

Thus we have proved the homogeneity of ${\displaystyle f}$.

## The map to zero

The map to zero is the map which sends every vector to zero. For instance, the map to zero of ${\displaystyle \mathbb {R} }$ to ${\displaystyle \mathbb {R} ^{3}}$ looks as follows:

${\displaystyle f\colon \mathbb {R} \to \mathbb {R} ^{3},\quad x\mapsto {\begin{pmatrix}0\\0\\0\end{pmatrix}}}$

Exercise (The map to zero linear)

Show that the map ${\displaystyle f\colon \mathbb {R} \to \mathbb {R} ^{3},\quad x\mapsto {\begin{pmatrix}0\\0\\0\end{pmatrix}}}$ is linear.

Proof (The map to zero linear)

We already know that ${\displaystyle \mathbb {R} }$ and ${\displaystyle \mathbb {R} ^{3}}$ are both ${\displaystyle \mathbb {R} }$-vector spaces and that the map to zero is well-defined.

For all ${\displaystyle x,y\in \mathbb {R} }$ we have that

{\displaystyle {\begin{aligned}f(x+y)&={\begin{pmatrix}0\\0\\0\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{additive neutral element}}\right.}\\[0.3em]&={\begin{pmatrix}0\\0\\0\end{pmatrix}}+{\begin{pmatrix}0\\0\\0\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}f\right.}\\[0.3em]&=f(x)+f(y)\end{aligned}}}

Proof step: homogeneity

For all ${\displaystyle x\in \mathbb {R} ,\lambda \in \mathbb {R} }$ we have that

{\displaystyle {\begin{aligned}f(\lambda \cdot x)&={\begin{pmatrix}0\\0\\0\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{scalar multiplication }}\right.}\\[0.3em]&=\lambda \cdot {\begin{pmatrix}0\\0\\0\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}f\right.}\\[0.3em]&=\lambda \cdot f(x)\end{aligned}}}

Thus, the map to zero is linear.

## An example in ${\displaystyle \mathbb {R} ^{2}}$

We consider an example for a linear map of ${\displaystyle \mathbb {R} ^{2}}$ to ${\displaystyle \mathbb {R} ^{2}}$:

${\displaystyle f\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2}}$ with ${\displaystyle f{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}={\begin{pmatrix}x_{1}+x_{2}\\x_{1}-5x_{2}\end{pmatrix}}}$

Exercise (Linearity of ${\displaystyle f}$)

Show that the map ${\displaystyle f\colon \mathbb {R} ^{2}\to \mathbb {R} ^{2},{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}\mapsto {\begin{pmatrix}x_{1}+x_{2}\\x_{1}-5x_{2}\end{pmatrix}}}$ is linear.

Proof (Linearity of ${\displaystyle f}$)

${\displaystyle \mathbb {R} ^{2}}$ is an ${\displaystyle \mathbb {R} }$-vector space. In addition, the map is well-defined.

Let ${\displaystyle (x_{1},x_{2})^{T}}$ and ${\displaystyle (y_{1},y_{2})^{T}}$ be any vectors from the plane ${\displaystyle \mathbb {R} ^{2}}$. Then, we have:

{\displaystyle {\begin{aligned}f\left({\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}+{\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}\right)&=f{\begin{pmatrix}x_{1}+y_{1}\\x_{2}+y_{2}\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}f\right.}\\[0.3em]&={\begin{pmatrix}(x_{1}+y_{1})+(x_{2}+y_{2})\\(x_{1}+y_{1})-5\cdot (x_{2}+y_{2})\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{distributive law}}\right.}\\[0.3em]&={\begin{pmatrix}(x_{1}+x_{2})+(y_{1}+y_{2})\\(x_{1}-5x_{2})+(y_{1}-5y_{2})\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{separate vectors}}\right.}\\[0.3em]&={\begin{pmatrix}x_{1}+x_{2}\\x_{1}-5x_{2}\end{pmatrix}}+{\begin{pmatrix}y_{1}+y_{2}\\y_{1}-5y_{2}\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}f\right.}\\[0.3em]&=f{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}+f{\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}\end{aligned}}}

Proof step: homogeneity

Let ${\displaystyle \lambda \in \mathbb {R} }$ and ${\displaystyle (x_{1},x_{2})^{T}\in \mathbb {R} ^{2}}$. Then:

{\displaystyle {\begin{aligned}f\left(\lambda \cdot {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}\right)&=f{\begin{pmatrix}\lambda \cdot x_{1}\\\lambda \cdot x_{2}\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}f\right.}\\[0.3em]&={\begin{pmatrix}\lambda x_{1}+\lambda x_{2}\\\lambda x_{1}-5\lambda x_{2}\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{distributive law}}\right.}\\[0.3em]&={\begin{pmatrix}\lambda (x_{1}+x_{2})\\\lambda (x_{1}-5x_{2})\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{scalar multiplication}}\right.}\\[0.3em]&=\lambda \cdot {\begin{pmatrix}(x_{1}+x_{2})\\(x_{1}-5x_{2})\end{pmatrix}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}f\right.}\\[0.3em]&=\lambda \cdot f{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}\\[0.3em]\end{aligned}}}

Thus the map is linear.

## A linear map in the vector space of sequences

Next, we consider the space of all sequences of real numbers. This space is infinite-dimensional, because there are not finitely many sequences generating this sequence space. But it is a vector space, as we have shown in the chapter about sequence spaces.

Exercise (Sequence space)

Let ${\displaystyle V}$ be the ${\displaystyle \mathbb {R} }$-vector space of all real-valued sequences. Show that the map

{\displaystyle {\begin{aligned}f:V&\to V\\(a_{0},a_{1},a_{2},\ldots )&\mapsto (a_{1},a_{2},a_{3},\ldots )\end{aligned}}}

is linear.

How to get to the proof? (Sequence space)

To show linearity, two properties need to be checked:

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

The vectors ${\displaystyle v}$ and ${\displaystyle w}$ are sequences of real numbers, i.e. they are of the form ${\displaystyle v=(a_{0},a_{1},a_{2},\ldots )}$ and ${\displaystyle w=(b_{0},b_{1},b_{2},\ldots )}$ with ${\displaystyle a_{k},b_{k}\in \mathbb {R} }$ for all ${\displaystyle k\in \mathbb {N} _{0}}$.

Proof (Sequence space)

Let ${\displaystyle v=(a_{0},a_{1},a_{2},\ldots )\in V}$ and ${\displaystyle w=(b_{0},b_{1},b_{2},\ldots )\in V}$. Then, we have

{\displaystyle {\begin{aligned}f(v+w)&=f((a_{0},a_{1},a_{2},\ldots )+(b_{0},b_{1},b_{2},\ldots ))\\[0.3em]&=\ f(a_{0}+b_{0},a_{1}+b_{1},a_{2}+b_{2},\ldots )\\[0.3em]&=\ (a_{1}+b_{1},a_{2}+b_{2},a_{3}+b_{3},\ldots )\\[0.3em]&=\ (a_{1},a_{2},a_{3},\ldots )+(b_{1},b_{2},b_{3},\ldots )\\[0.3em]&=\ f(a_{0},a_{1},a_{2},\ldots )+f(b_{0},b_{1},b_{2},\ldots )\\[0.3em]&=\ f(v)+f(w)\end{aligned}}}

It follows that ${\displaystyle f}$ is additive.

Proof step: homogeneity

Let ${\displaystyle v=(a_{0},a_{1},a_{2},\ldots )\in V}$ and ${\displaystyle \lambda \in \mathbb {R} }$. Then, we have

{\displaystyle {\begin{aligned}f(\lambda \cdot v)&=f(\lambda \cdot (a_{0},a_{1},a_{2},\ldots ))\\[0.3em]&=\ f(\lambda a_{0},\lambda a_{1},\lambda a_{2},\ldots )\\[0.3em]&=\ (\lambda a_{1},\lambda a_{2},\lambda a_{3},\ldots )\\[0.3em]&=\ \lambda \cdot (a_{1},a_{2},a_{3},\ldots )\\[0.3em]&=\ \lambda \cdot f(a_{0},a_{1},a_{2},\ldots )\\[0.3em]&=\ \lambda \cdot f(v)\end{aligned}}}

So ${\displaystyle f}$ is homogeneous.

Thus it was proved that ${\displaystyle f}$ is a ${\displaystyle \mathbb {R} }$-linear map.

## Abstract example

In this chapter, we deal with somewhat more abstract vectors. Let ${\displaystyle M,\,N}$ be arbitrary sets; ${\displaystyle K}$ a field and ${\displaystyle V}$ a ${\displaystyle K}$-vector space. We now consider the set of all maps/ functions of the set ${\displaystyle M}$ into the vector space ${\displaystyle V}$ and denote this set with ${\displaystyle {\text{Fun}}(M,V)}$. Furthermore, we also consider the set of all maps of the set ${\displaystyle N}$ into the vector space ${\displaystyle V}$ and denote this set with ${\displaystyle {\text{Fun}}(N,V)}$. The addition of two maps is defined for ${\displaystyle f,g\in {\text{Fun}}(M,V)}$ by

${\displaystyle (f+g)(m)=f(m)+g(m)}$

Die scalar multiplication is defined for ${\displaystyle \lambda \in K}$ via

${\displaystyle (\lambda \cdot f)(m)=\lambda \cdot f(m)}$

Analogously, we define addition scalar multiplication for ${\displaystyle {\text{Fun}}(N,V)}$.

Exercise (The set ${\displaystyle {\text{Fun}}(M,V)}$ is a ${\displaystyle K}$-vector space)

Show that ${\displaystyle {\text{Fun}}(M,V)}$ is a ${\displaystyle K}$-vector space.

How to get to the proof? (The set ${\displaystyle {\text{Fun}}(M,V)}$ is a ${\displaystyle K}$-vector space)

Simply check the vector space axioms.

We now consider a function/ map

{\displaystyle {\begin{aligned}\Theta :{\text{Fun}}(M,V)&\to {\text{Fun}}(N,V)\\g&\mapsto g\circ t\end{aligned}}}

where ${\displaystyle t\colon N\to M;\,n\mapsto t(n)\in M}$, so ${\displaystyle t\in {\text{Fun}}(N,M)}$ is arbitrary.

Exercise (The map ${\displaystyle \Theta }$ is linear.)

Show that:

${\displaystyle \Theta :{\text{Fun}}(M,V)\to {\text{Fun}}(N,V);\,g\mapsto g\circ t}$

is a linear map.

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

Summary of proof (The map ${\displaystyle \Theta }$ is linear.)

To prove the linearity of ${\displaystyle \Theta }$, we need to check the two properties again:

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

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

Proof (The map ${\displaystyle \Theta }$ is linear.)

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

For all ${\displaystyle n\in N}$ we have that

{\displaystyle {\begin{aligned}\Theta (g+h)(n)&=\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}\Theta \right.}\\[0.3em]&=\ ((g+h)\circ t)(n)\\[0.3em]&=\ (g+h)(t(n))\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{vector addition on Fun}}(M,V)\right.}\\[0.3em]&=\ g(t(n))+h(t(n))\\[0.3em]&=\ (g\circ t)(n)+(h\circ t)(n)\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}\Theta \right.}\\[0.3em]&=\ \Theta (g)(n)+\Theta (h)(n)\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{vector addition on Fun}}(N,V)\right.}\\[0.3em]&=\ (\Theta (g)+\Theta (h))(n)\end{aligned}}}

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

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

Proof step: homogeneity

For all ${\displaystyle n\in N}$ we have that

{\displaystyle {\begin{aligned}\Theta (\lambda \cdot g)(n)&=\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}\Theta \right.}\\[0.3em]&=\ ((\lambda \cdot g)\circ t)(n)\\[0.3em]&=\ (\lambda \cdot g)(t(n))\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{scalar multiplication on Fun}}(M,V)\right.}\\[0.3em]&=\ \lambda \cdot g(t(n))\\[0.3em]&=\ \lambda \cdot (g\circ t)(n)\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{definition of }}\Theta \right.}\\[0.3em]&=\ \lambda \cdot \Theta (g)(n)\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{scalar multiplication on Fun}}(N,V)\right.}\\[0.3em]&=\ (\lambda \cdot \Theta (g))(n)\end{aligned}}}

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

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