# Linear Algebra - Generators of a Vector Space

The generators for the set of vectors $V$ are the vectors $v_1, \dots,v_n$ in the following formula:

$$V = Span \{v_1,\dots,v_n\}$$

where $\{v_1,\dots,v_n\}$ is a generating set for $V$

## Example

• {[3, 0, 0], [0, 2, 0], [0, 0, 1]} is a generating set for .

= Span {[3, 0, 0], [0, 2, 0], [0, 0, 1]}

• Another generating set for is {[1, 0, 0], [1, 1, 0], [1, 1, 1]}

## Type

### Standard

Writing [x, y, z] as a linear combination of the vectors [3, 0, 0], [0, 2, 0], and [0, 0, 1] is simple

[x, y, z] = (x/3) [3, 0, 0] + (y/2) [0, 2, 0] + z [0, 0, 1]


Even simpler if instead we use [1, 0, 0], [0, 1, 0], and [0, 0, 1]:

[x, y, z] = x [1, 0, 0] + y [0, 1, 0] + z [0, 0, 1]


These are called standard generators for R3 written e1, e2, e3

### Orthogonal

Building an orthogonal set of generators is known as orthogonalization:

## Minimum Set

Greedy algorithms for finding a set of generators

For a given vector space V, what is the minimum number of vectors whose span equals V? How can we obtain a minimum number of vectors? Two natural approaches come to mind, the Grow algorithm and the Shrink algorithm.

Grow and Shrink algorithms both test whether a vector is superfluous in spanning a vector space V.

### Grow

def Grow(V)
S = 0;
repeat while possible:
find a vector v in V that is not in Span S, and put it in S.


The algorithm stops when there is no vector to add, at which time S spans all of V. Thus, if the algorithm stops, it will have found a generating set.

### Shrink

def Shrink(V)
S = some finite set of vectors that spans V
repeat while possible:
find a vector v in S such that Span (S - {v}) = V, and remove v from S


The algorithm stops when there is no vector whose removal would leave a spanning set. At every point during the algorithm, S spans V, so it spans V at the end. Thus, if the algorithm stops, the algorithm will have found a generating set.

## Superfluous-Vector Lemma

Superfluous-Vector Lemma: For any set S and any vector $v \in S$ , if v can be written as a linear combination of the other vectors in S then $$Span (S − \{v\}) = Span S$$

## Basis

Let V be a vector space. A basis for V is a linearly independent set of generators for V.