Generators – "Math for Non-Geeks"

Fehler: Aktuelle Seite wurde in der Sitemap nicht gefunden. Deswegen kann keine Navigation angezeigt werden

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

Fehler: Aktuelle Seite wurde in der Sitemap nicht gefunden. Deswegen kann keine Navigation angezeigt werden