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 $(1,0,0)^{T},(0,1,0)^{T},(0,0,1)^{T}$ of $\mathbb {R} ^{3}$. Any vector of $\mathbb {R} ^{3}$ is a linear combination of these three vectors, because for all $(\alpha ,\beta ,\gamma )^{T}\in \mathbb {R} ^{3}$ we have that:

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

$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: $\mathbb {R} ^{3}=\operatorname {span} (M)$, that means $M$ spans/generates the entire vector space. Sets with this spanning/generating property are called generators:

Definition (Generator of a vector space)

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

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

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

Hint

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

Examples

Generators of the plane

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

${\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 $e_{1}$ and $e_{2}$.

Vector space of polynomials

Let us consider the vector space $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 $P(x)=1$, $Q(x)=x$ and $R(x)=x^{2}$. Every polynomial with degree less than or equal to two has the form $ax^{2}+bx+c=a\cdot R(x)+b\cdot Q(x)+c\cdot P(x)$. So $\{P(x),Q(x),R(x)\}$ is a generator of $V_{\leq 2}$.

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

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

Therefore the (infinite) set of monomials $\lbrace 1,X,X^{2},X^{3},\ldots \rbrace$ is a generator of $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 $\mathbb {R} ^{2}$ as an example. The set $\left\{(1,0)^{T},(0,1)^{T}\right\}$ is a generator of the plane, since all $(\alpha ,\beta )^{T}\in \mathbb {R} ^{2}$ can be represented as a linear combination of the two vectors $e_{1}=(1,0)^{T}$ and $e_{2}=(0,1)^{T}$:

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

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

${\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 $v$ can be represented by two different linear combinations of $\{e_{1},\ e_{2}\}$ and $\{e_{1},e_{2},e_{3}\}$. This shows that vector spaces can have multiple generators.

Proofs about the generator

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

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

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

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

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

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

Example

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

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

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

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

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

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

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

This inserted into the second equation gives

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

This gives us in the first equation

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

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

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

So

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

${\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 $\mathbb {R} ^{3}$ as a linear combination of the three given vectors $v_{1}=(1,2,3)^{T}$, $v_{2}=(1,3,5)^{T}$ and $v_{3}=(1,3,6)^{T}$. This proves that the set $M$ spans the space $\mathbb {R} ^{3}$.