Proofs for linear maps – "Math for Non-Geeks"

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 homeomorphism) is a structure-preserving map of a $K$-vector space $V$ into a $K$-vector space $W$. That is, for the map $f:V\to W$, the following two conditions must hold:

1. $f$ must be additive, i.e., for $v,w\in V$ we have that: $f(v+w)=f(v)+f(w)$
2. $f$ must be homogeneous, i.e., for $v\in V,\lambda \in K$ we have that: $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 $V$ and then map the sum into the vector space $W$, or first map the vectors $v,w$ into the vector space $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 $f:V\to W$ is given between vector spaces. That is, $V$ and $W$ are $K$-vector spaces and $f$ is well-defined. Then for the linearity of $f$ we have to show:

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

Exercise (Introductory example)

We consider the following map

$f:{ℝ}^2\to ℝ,f\left(\begin{array}{c}{v}_1\\ v_2\end{array}\right):=2v_1+v_2$

and show that it is linear.

Proof (Introductory example)

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

Proof step: proving additivity

Let $\left(\begin{array}{c}{v}_1\\ v_2\end{array}\right),\left(\begin{array}{c}{w}_1\\ w_2\end{array}\right)\in {ℝ}^2$.

$\begin{array}{cc}f(\left(\begin{array}{c}{v}_1\\ v_2\end{array}\right)+\left(\begin{array}{c}{w}_1\\ w_2\end{array}\right))& =f\left(\begin{array}{c}{v}_1+w_1\\ v_2+w_2\end{array}\right)\\ & \downarrow \text{definition of }f\\ & =2(v_1+w_1)+(v_2+w_2)\\ & \downarrow \text{distributive law}\\ & =2v_1+2w_1+v_2+w_2\\ & \downarrow \text{commutative and associative law }\\ & =(2v_1+v_2)+(2w_1+w_2)\\ & \downarrow \text{definition of }f\\ & =f\left(\begin{array}{c}{v}_1\\ v_2\end{array}\right)+f\left(\begin{array}{c}{w}_1\\ w_2\end{array}\right)\end{array}$

Thus, we have proved the additivity of $f$.

Proof step: proving homogeneity

Let $\left(\begin{array}{c}{v}_1\\ v_2\end{array}\right)\in {ℝ}^2$ and $\lambda \in ℝ$. Then, we have

$\begin{array}{cc}f\left(\lambda \left(\begin{array}{c}{v}_1\\ v_1\end{array}\right)\right)& =f\left(\begin{array}{c}\lambda v_1\\ \lambda v_2\end{array}\right)\\ & \downarrow \text{definition of }f\\ & =2\lambda v_1+\lambda v_2\\ & \downarrow \text{distributive law }\\ & =\lambda (2v_1+v_2)\\ & \downarrow \text{definition of }f\\ & =\lambda \cdot f\left(\begin{array}{c}{v}_1\\ v_2\end{array}\right)\end{array}$

Thus, we have proved the homogeneity of $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 $ℝ$ to ${ℝ}^3$ looks as follows:

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

Exercise (The map to zero linear)

Show that the map $f:ℝ\to {ℝ}^3,x\mapsto \left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)$ is linear.

Proof (The map to zero linear)

We already know that $ℝ$ and ${ℝ}^3$ are both $ℝ$-vector spaces, and that the map to zero is well-defined.

Proof step: additivity

For all $x,y\in ℝ$ we have that

$\begin{array}{cc}f(x+y)& =\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)\\ & \downarrow \text{additive neutral element}\\ & =\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)+\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)\\ & \downarrow \text{definition of }f\\ & =f(x)+f(y)\end{array}$

Proof step: homogeneity

For all $x\in ℝ,\lambda \in ℝ$ we have that

$\begin{array}{cc}f(\lambda \cdot x)& =\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)\\ & \downarrow \text{scalar multiplication }\\ & =\lambda \cdot \left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)\\ & \downarrow \text{definition of }f\\ & =\lambda \cdot f(x)\end{array}$

Thus, the map to zero is linear.

An example in ${ℝ}^2$

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.

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 $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.

Abstract example

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

$(f+g)(m)=f(m)+g(m)$

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

$(\lambda \cdot f)(m)=\lambda \cdot f(m)$

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

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

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

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

Simply check the vector space axioms.

We now show that the composition with a mapping $t\in \text{Fun}(N,M)$ is a linear map from $\text{Fun}(M,V)$ to $\text{Fun}(N,V)$.

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.