Serlo: EN: Generators

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

Let

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

If $M$ is a generator of $V$, then for every $v\in V$ there are elements $m_1,m_2,\dots ,m_k\in M$ and ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k\in K$ such that $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$.

Examples

Generators of the plane

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

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_{\le 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 $a{x}^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_{\le 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,\dots$.

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

The vectors $e_1=(1,0{)}^T$, $e_2=(0,1{)}^T$, $e_3=(1,1{)}^T$ also generate the ${ℝ}^2$, because $v$ can be represented as follows:

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,\dots 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,\dots ,{\lambda }_n\in K$ such that

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,\dots ,v_n$ with unknown coefficients ${\lambda }_1,\dots ,{\lambda }_n\in K$.
3. Solve system of equations according to the variables ${\lambda }_1,\dots ,{\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.