Linear Algebra - Generators of a Vector Space

> Linear Algebra

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>

Advertising

3 - Example

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

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

  • Another generating set for bbR^3 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.

Advertising

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.

linear_algebra/generator.txt · Last modified: 2013/08/28 17:42 by gerardnico