Linear Algebra - Generators of a Vector Space

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:

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

Articles Related

Example

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

bbR^3 = 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 <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>

Basis

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