Generators – Serlo

A generator is a subset of a vector space that spans the entire vector space. Thus, every vector of the vector space can be written as a linear combination of vectors of the generator.

Derivation and definition

Consider the three vectors ${\displaystyle (1,0,0)^{T},(0,1,0)^{T},(0,0,1)^{T}}$ of ${\displaystyle \mathbb {R} ^{3}}$. Any vector of ${\displaystyle \mathbb {R} ^{3}}$ is a linear combination of these three vectors, because for all ${\displaystyle (\alpha ,\beta ,\gamma )^{T}\in \mathbb {R} ^{3}}$ we have that:

${\displaystyle {\begin{pmatrix}\alpha \\\beta \\\gamma \end{pmatrix}}=\alpha \cdot {\begin{pmatrix}1\\0\\0\end{pmatrix}}+\beta \cdot {\begin{pmatrix}0\\1\\0\end{pmatrix}}+\gamma \cdot {\begin{pmatrix}0\\0\\1\end{pmatrix}}}$

Let

${\displaystyle M=\left\{{\begin{pmatrix}1\\0\\0\end{pmatrix}},{\begin{pmatrix}0\\1\\0\end{pmatrix}},{\begin{pmatrix}0\\0\\1\end{pmatrix}}\right\}}$

We have that: ${\displaystyle \mathbb {R} ^{3}=\operatorname {span} (M)}$, that means ${\displaystyle M}$ spans/generates the entire vector space. Sets with this spanning/generating property are called generators:

Definition (Generator of a vector space)

A subset ${\displaystyle M\subseteq V}$ of a vector space ${\displaystyle V}$ over the field ${\displaystyle K}$ is a generator of ${\displaystyle V}$ if the span of ${\displaystyle M}$ is again the entire vector space ${\displaystyle V}$, i.e. ${\displaystyle \operatorname {span} (M)=V}$. In this case we call ${\displaystyle M}$ a generator of ${\displaystyle V}$.

${\displaystyle V}$ is called finitely generated if a finite set ${\displaystyle M}$ exists with ${\displaystyle \operatorname {span} (M)=V}$.

If ${\displaystyle M}$ is a generator of ${\displaystyle V}$, then for every ${\displaystyle v\in V}$ there are elements ${\displaystyle m_{1},m_{2},\ldots ,m_{k}\in M}$ and ${\displaystyle \lambda _{1},\lambda _{2},\ldots ,\lambda _{k}\in K}$ such that ${\textstyle v=\sum _{i=1}^{k}\lambda _{i}m_{i}}$. Each vector ${\displaystyle v\in V}$ can thus be written as a linear combination of elements from ${\displaystyle M}$.

Hint

Every vector space has a generator. For we have that ${\displaystyle \operatorname {span} (V)=V}$, so ${\displaystyle V}$ generates itself.

Examples

Generators of the plane

The vectors ${\displaystyle e_{1}=(1,0)^{T}}$ and ${\displaystyle e_{2}=(0,1)^{T}}$ span/generate the plane ${\displaystyle \mathbb {R} ^{2}}$. For all ${\displaystyle v=(\alpha ,\beta )^{T}\in \mathbb {R} ^{2}}$ we can write in coordinates:

${\displaystyle {\begin{pmatrix}\alpha \\\beta \end{pmatrix}}=\alpha \cdot {\begin{pmatrix}1\\0\end{pmatrix}}+\beta \cdot {\begin{pmatrix}0\\1\end{pmatrix}}}$

Thus every vector of the plane can be written as a linear combination of ${\displaystyle e_{1}}$ and ${\displaystyle e_{2}}$.

Vector space of polynomials

Let us consider the vector space ${\displaystyle V_{\leq 2}}$ of polynomials of degree less than or equal to two. Here any polynomial can be formed by a linear combination of the polynomials ${\displaystyle P(x)=1}$, ${\displaystyle Q(x)=x}$ and ${\displaystyle R(x)=x^{2}}$. Every polynomial with degree less than or equal to two has the form ${\displaystyle ax^{2}+bx+c=a\cdot R(x)+b\cdot Q(x)+c\cdot P(x)}$. So ${\displaystyle \{P(x),Q(x),R(x)\}}$ is a generator of ${\displaystyle V_{\leq 2}}$.

We can also formulate this for polynomials of arbitrarily high degree:

If ${\displaystyle K}$ is a field and ${\displaystyle K[X]}$ is the vector space of polynomials with coefficients in ${\displaystyle K}$, then every element of ${\displaystyle K[X]}$ has the form ${\displaystyle P=a_{0}+a_{1}X+a_{2}X^{2}+\cdots a_{n}X^{n}}$, so it is a (finite! ) linear combination of ${\displaystyle 1,X,X^{2},X^{3},\ldots }$.

Therefore the (infinite) set of monomials ${\displaystyle \lbrace 1,X,X^{2},X^{3},\ldots \rbrace }$ is a generator of ${\displaystyle K[X]}$.

Generators are not unique

a vector space can have several generators. The generator is usually not uniquely determined.

Let us take the plane ${\displaystyle \mathbb {R} ^{2}}$ as an example. The set ${\displaystyle \left\{(1,0)^{T},(0,1)^{T}\right\}}$ is a generator of the plane, since all ${\displaystyle (\alpha ,\beta )^{T}\in \mathbb {R} ^{2}}$ can be represented as a linear combination of the two vectors ${\displaystyle e_{1}=(1,0)^{T}}$ and ${\displaystyle e_{2}=(0,1)^{T}}$:

${\displaystyle {\begin{pmatrix}\alpha \\\beta \end{pmatrix}}=\alpha \cdot {\begin{pmatrix}1\\0\end{pmatrix}}+\beta \cdot {\begin{pmatrix}0\\1\end{pmatrix}}}$

The vectors ${\displaystyle e_{1}=(1,0)^{T}}$, ${\displaystyle e_{2}=(0,1)^{T}}$, ${\displaystyle e_{3}=(1,1)^{T}}$ also generate the ${\displaystyle \mathbb {R} ^{2}}$, because ${\displaystyle v}$ can be represented as follows:

${\displaystyle {\begin{pmatrix}\alpha \\\beta \end{pmatrix}}=\alpha \cdot {\begin{pmatrix}1\\0\end{pmatrix}}+\beta \cdot {\begin{pmatrix}1\\1\end{pmatrix}}+(-\beta )\cdot {\begin{pmatrix}1\\0\end{pmatrix}}}$

Thus the vector ${\displaystyle v}$ can be represented by two different linear combinations of ${\displaystyle \{e_{1},\ e_{2}\}}$ and ${\displaystyle \{e_{1},e_{2},e_{3}\}}$. This shows that vector spaces can have multiple generators.

How to prove that a set generates ${\displaystyle K^{n}}$?

We sketch in this section how to prove that a set is a generator of a vector space ${\displaystyle K^{n}}$ (${\displaystyle K}$ is a field). A subset ${\displaystyle M}$ of a vector space ${\displaystyle V}$ is called a generator if every vector ${\displaystyle v\in V}$ can be represented as a linear combination of the vectors from ${\displaystyle M}$.

Let ${\displaystyle M=\{v_{1},\ldots v_{n}\}}$ be the given set of vectors. Then one has to show that for all vectors ${\displaystyle v\in K^{n}}$, there are coefficients ${\displaystyle \lambda _{1},\ldots ,\lambda _{n}\in K}$ such that

${\displaystyle v=\lambda _{1}\cdot v_{1}+...+\lambda _{n}\cdot v_{n}}$

This equation can usually be translated into a system of equations, and the ${\displaystyle \lambda _{i}}$ provide a solution of this system of equations. We can summarise the general procedure like this:

1. Select a vector ${\displaystyle v}$ of the vector space ${\displaystyle V}$.
2. Equate ${\displaystyle v}$ with a linear combination of vectors ${\displaystyle v_{1},\ldots ,v_{n}}$ with unknown coefficients ${\displaystyle \lambda _{1},\ldots ,\lambda _{n}\in K}$.
3. Solve system of equations according to the variables ${\displaystyle \lambda _{1},\ldots ,\lambda _{m}}$. If there is always at least one solution, then ${\displaystyle M}$ is a generator. If there is no solution for a vector ${\displaystyle v}$, then ${\displaystyle M}$ is not a generator.

Example

Exercise (Generators of ${\displaystyle \mathbb {R} ^{3}}$)

Let ${\displaystyle v_{1}=(1,2,3)^{T}}$, ${\displaystyle v_{2}=(1,3,5)^{T}}$ and ${\displaystyle v_{3}=(1,3,6)^{T}}$. Show that ${\displaystyle \{v_{1},v_{2},v_{3}\}}$ is a generator of ${\displaystyle \mathbb {R} ^{3}}$ .

Solution (Generators of ${\displaystyle \mathbb {R} ^{3}}$)

Let ${\displaystyle x=(x_{1},x_{2},x_{3})^{T}}$ be any vector of ${\displaystyle \mathbb {R} ^{3}}$. We are looking for ${\displaystyle \alpha ,\beta ,\gamma }$ with

${\displaystyle {\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}=\alpha \cdot {\begin{pmatrix}1\\2\\3\end{pmatrix}}+\beta \cdot {\begin{pmatrix}1\\3\\5\end{pmatrix}}+\gamma \cdot {\begin{pmatrix}1\\3\\6\end{pmatrix}}={\begin{pmatrix}\alpha +\beta +\gamma \\2\alpha +3\beta +3\gamma \\3\alpha +5\beta +6\gamma \end{pmatrix}}}$

From this we get the system of equations

${\displaystyle {\begin{array}{rrl}\mathrm {I} :&x_{1}&=\alpha +\beta +\gamma \\\mathrm {II} :&x_{2}&=2\alpha +3\beta +3\gamma \\\mathrm {III} :&x_{3}&=3\alpha +5\beta +6\gamma \\\end{array}}}$

From the first equation we obtain

${\displaystyle \alpha =x_{1}-\beta -\gamma }$

This inserted into the second equation gives

${\displaystyle \beta +\gamma =x_{2}-2x_{1}\implies \beta =\ x_{2}-2x_{1}-\gamma }$

This gives us in the first equation

${\displaystyle \alpha =3x_{1}-x_{2}}$

If we now plug ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ into the third equation, we get:

${\displaystyle 3\cdot (3x_{1}-x_{2})+5\cdot (x_{2}-2x_{1}-\gamma )+6\gamma =x_{3}}$

So

{\displaystyle {\begin{aligned}\alpha &=(3x_{1}-x_{2})\\\gamma &=x_{1}-2x_{2}+x_{3}\\\beta &=-3x_{1}+3x_{2}-x_{3}\end{aligned}}}

Hence we have that:

${\displaystyle {\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}}\,=\,(3x_{1}-x_{2})\cdot {\begin{pmatrix}1\\2\\3\end{pmatrix}}+(-3x_{1}+3x_{2}-x_{3})\cdot {\begin{pmatrix}1\\3\\5\end{pmatrix}}+(x_{1}-2x_{2}+x_{3})\cdot {\begin{pmatrix}1\\3\\6\end{pmatrix}}}$

Thus we have found a way to represent every vector of ${\displaystyle \mathbb {R} ^{3}}$ as a linear combination of the three given vectors ${\displaystyle v_{1}=(1,2,3)^{T}}$, ${\displaystyle v_{2}=(1,3,5)^{T}}$ and ${\displaystyle v_{3}=(1,3,6)^{T}}$. This proves that the set ${\displaystyle M}$ spans the space ${\displaystyle \mathbb {R} ^{3}}$.