# Linear Algebra - Generators of a Vector Space

### Table of Contents

## 1 - About

The generators for the set of vectors <math>V</math> are the vectors <math>v_1, \dots,v_n</math> in the following formula:

<MATH>V = Span \{v_1,\dots,v_n\}</MATH>

where <math>\{v_1,\dots,v_n\}</math> is a generating set for <math>V</math>

## 2 - Articles Related

## 3 - 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]}

## 4 - Type

### 4.1 - 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

### 4.2 - Orthogonal

Building an orthogonal set of generators is known as orthogonalization:

## 5 - 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.

### 5.1 - 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.

### 5.2 - 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.

## 6 - Superfluous-Vector Lemma

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

## 7 - Basis

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