Linear Algebra - Basis of a Vector Space

Card Puncher Data Processing

About

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

Thus a set S of vectors of V is a basis for V if S satisfies two properties:

  • Property B1 (Spanning) Span S = V, and
  • Property B2 (Independent) S is linearly independent.

Most important definition in linear algebra.

A set of vector S is a basis for the span of an other set of vector T if:

  • the span of S equal the span of T
  • S is a linearly independent set

If a set of vector S is a basis for a set of vector T, then the span of S is equal to the span of T.

Computation

def isABasis(L, i):
    '''
    Input:
        - L: list of vectors as instances of Vec class
        - i: integer in range(len(L))
    Output:
        False if the span of the vectors of L is the same
        as the span of the vectors of L, excluding L[i].

        True otherwise.
    '''
    if len(L)==1:
        return True
    litteL = [v for (j,v) in enumerate(L) if j != i] 
    A = coldict2mat(litteL)
    b = L[i]
    # The procedure solve(A, b) given a Mat A and a Vec b, 
    # returns a vector u such that A*u=b iff there is such a vector u 
    u = solve(A,b)
    # check that u is in fact a solution to the equation Ax = b.    
    # the solution returned by solve is approximate due to round-o�ff error. 
    # We compute the residual  
    residual = b - A*u
    # and test if the dot product is close to the zero vector:
    if (residual*residual < 10**(-14)):
        return False
    else:
        return True

Grow

Initialize S = 0;.
Repeat while possible: select a vector v in V that is not in Span S, and put it in S.

The Grow algorithm finds a basis for V if it terminates.

At each point in the execution of the algorithm, the set S is linearly independent.

Size

All bases for a vector space have the same size.

Morphing Lemma: Let V be a vector space. Suppose S is a set of generators for V, and B is a basis for V. Then |B| ⇐ |S| (cardinality of B ⇐ cardinality of S)

Theorem:

  • Any basis for V is a smallest generating set for V.
  • All bases for a vector space V have the same size.

Lemma

Unique-Representation

Let <math>a_1, \dots , a_n</math> be a basis for V. For any vector <math>v \in V</math> , there is exactly one representation of v in terms of the basis vectors.

Proof: Let v be any vector in V. The vectors <math>a_1, \dots , a_n</math> span V, so there is at least one representation of v in terms of the basis vectors.

Suppose there are two such representations: <MATH>v = \alpha_1 a_1 + \dots + \alpha_n a_n = \beta_1 a_1 + \dots + \beta_n a_n</MATH> We get the zero vector by subtracting one from the other: <MATH> \begin{array}{rcl} 0 & = & \alpha_1 a_1 + \dots + \alpha_n a_n − (\beta_1 a_1 + \dots + \beta_n a_n)\\ & = & (\alpha_1 - \beta_1) a_1 + \dots + (\alpha_n - \beta_n) a_n \end{array} </MATH> Since the vectors <math>a_1, \dots , a_n</math> are linearly independent, the coefficient <math>\alpha_1 - \beta_1, \dots, \alpha_n - \beta_n</math> must all be zero, so the two representations are really the same.

Subset

Every finite set T of vectors contains a subset S that is a basis for Span T.

Superset-Basis

Let V be a vector space. Let C be a linearly independent set of vectors belonging to V. Then V has a basis S containing all vectors in C.

Grow algorithm Computation

Initialize S to the empty set.
Repeat while possible: select a vector v in V (preferably in C) that is not in
Span S, and put it in S.

Theorem

  • For finite D, every subspace of <math>F^D</math> contains a basis.

Change of basis

From a vector to its coordinate representation

Suppose we have a basis <math>a_1, \dots , a_n</math> for some vector space V. How do we go

  • from a vector b in V
  • to the coordinate representation u of b in terms of <math>a_1, \dots , a_n</math> ?

By linear-combinations definition of matrix-vector multiplication, <MATH> \begin{bmatrix} \begin{array}{r|r|r} a_1 & \dots & a_n \end{array} \end{bmatrix} * \begin{bmatrix} \begin{array}{rrr} & u & \end{array} \end{bmatrix} = \begin{bmatrix} \begin{array}{rrr} & b & \end{array} \end{bmatrix} </MATH> By unique-representation_lemma u is the only solution to the equation <MATH> \begin{bmatrix} \begin{array}{r|r|r} a_1 & \dots & a_n \end{array} \end{bmatrix} * \begin{bmatrix} \begin{array}{rrr} & x & \end{array} \end{bmatrix} = \begin{bmatrix} \begin{array}{rrr} & b & \end{array} \end{bmatrix} </MATH> so we can obtain u by using a matrix-vector equation solver.

From a basis to another

Now suppose <math>a_1, \dots , a_n</math> is one basis for V and <math>c_1, \dots , c_k</math> is another.

<MATH> \begin{array}{lcr} f(x) = \begin{bmatrix} \begin{array}{r|r|r} a_1 & \dots & a_n \end{array} \end{bmatrix} * \begin{bmatrix} \begin{array}{rrr} & x & \end{array} \end{bmatrix} & \text{ and } & g(y) = \begin{bmatrix} \begin{array}{r|r|r} c_1 & \dots & c_k \end{array} \end{bmatrix} * \begin{bmatrix} \begin{array}{rrr} & y & \end{array} \end{bmatrix} \end{array} </MATH>

Then both f and g are invertible functions. The function <math>f^{-1} \circ g</math> maps:

  • from Linear Algebra - Coordinate system of a vector in terms of <math>c_1, \dots , c_k</math>
  • to coordinate representation of a vector in terms of <math>a_1, \dots , a_n</math>

In particular, if <math>V = \mathbb{F}^m</math> for some m then

f invertible implies that <math> \begin{bmatrix} \begin{array}{r|r|r} a_1 & \dots & a_n \end{array} \end{bmatrix} </math> is an invertible matrix.

g invertible implies that <math> \begin{bmatrix} \begin{array}{r|r|r} c_1 & \dots & c_k \end{array} \end{bmatrix} </math> is an invertible matrix.

Thus the function <math>f_{-1} \circ g</math> has the property:

<MATH> \begin{array}{lcr} (f_{-1} \circ g)(x) = \begin{bmatrix} \begin{array}{r|r|r} a_1 & \dots & a_n \end{array} \end{bmatrix}^{-1} \begin{bmatrix} \begin{array}{r|r|r} c_1 & \dots & c_k \end{array} \end{bmatrix} * \begin{bmatrix} \begin{array}{rrr} & x & \end{array} \end{bmatrix} \end{array} </MATH>

Proposition: If <math>a_1, \dots , a_n</math> and <math>c_1, \dots , c_k</math> are basis for <math>\mathbb{F}^m</math> then multiplication by the matrix:

<MATH> B = \begin{bmatrix} \begin{array}{r|r|r} a_1 & \dots & a_n \end{array} \end{bmatrix}^{-1} \begin{bmatrix} \begin{array}{r|r|r} c_1 & \dots & c_k \end{array} \end{bmatrix} </MATH> maps:

  • from the representation of a vector with respect to <math>c_1, \dots , c_k</math>
  • to the representation of that vector with respect to <math>a_1, \dots , a_n</math>

Conclusion: Given two bases of <math>\mathbb{F}^m</math> , there is a matrix B such that multiplication by B converts from one Linear Algebra - Coordinate system to the other.

Converting between vector itself and its coordinate representation is a special case: Think of the vector itself as coordinate representation with respect to standard basis.

Example: To map from coordinate representation with respect to <math>[1, 2, 3], [2, 1, 0], [0, 1, 4]</math> to coordinate representation with respect to <math>[2, 0, 1], [0, 1,-1], [1, 2, 0]</math> multiply by the matrix:

<MATH> \begin{bmatrix} \begin{array}{r|r|r} 2 & 0 & 1 \\ 0 & 1 & 2 \\ 1 & -1 & 0 \end{array} \end{bmatrix}^{-1} \begin{bmatrix} \begin{array}{r|r|r} 1 & 2 & 0 \\ 2 & 1 & 1 \\ 3 & 0 & 4 \end{array} \end{bmatrix} </MATH> which is:

<MATH> \begin{bmatrix} \begin{array}{r|r|r} \frac{2}{3} & -\frac{1}{3} & -\frac{1}{3} \\ \frac{2}{3} & -\frac{1}{3} & -\frac{4}{3} \\ -\frac{1}{3} & \frac{2}{3} & \frac{2}{3} \end{array} \end{bmatrix} \begin{bmatrix} \begin{array}{r|r|r} 1 & 2 & 0 \\ 2 & 1 & 1 \\ 3 & 0 & 4 \end{array} \end{bmatrix} </MATH> which is: <MATH> \begin{bmatrix} \begin{array}{r|r|r} -1 & 1 & -\frac{5}{3} \\ -4 & 1 & -\frac{17}{3} \\ 3 & 9 & \frac{10}{3} \end{array} \end{bmatrix} </MATH>

Example

Not a basis

  • Let <math>V = Span \{[1, 0, 2, 0], [0,-1, 0,-2], [2, 2, 4, 4]\}</math> . Is <math>\{[1, 0, 2, 0], [0,-1, 0,-2], [2, 2, 4, 4]\}</math> a basis for V?

The set is spanning but is not independent: <MATH>1 [1, 0, 2, 0] -1 [0,-1, 0,-2] -\frac{1}{2} [2, 2, 4, 4] = 0</MATH> It's then not a basis.

However, <math>\{[1, 0, 2, 0], [0,-1,0-2]\}</math> is a basis:

  • Obvious that these vectors are independent because each has a nonzero entry where the other has a zero.
  • To show

<MATH>Span \{[1, 0, 2, 0], [0,-1,0,-2]\} = Span \{[1, 0, 2, 0], [0,-1,0,-2],[[2, 2, 4, 4]\}</MATH> can use superfluous-vector_lemma: <MATH>[2, 2, 4, 4] = 2 [1, 0, 2, 0]-2 [0,-1,0,-2] </MATH>

A simple basis over <math>\mathbb{R}^3</math> : the standard generators

<MATH>e1 = [1, 0, 0], e2 = [0, 1, 0], e3 = [0, 0, 1]</MATH>

  • Spanning: For any vector <math>[x, y, z] \in \mathbb{R}^3</math> ,

<MATH>[x, y, z] = x [1, 0, 0] + y [0, 1, 0] + z [0, 0, 1]</MATH>

  • Independent: Suppose

<MATH>0 = \alpha_1 [1, 0, 0] + \alpha_2 [0, 1, 0] + \alpha_3 [0, 0, 1] = [\alpha_1, \alpha_2, \alpha_3]</MATH> Then <math>\alpha_1 = \alpha_2 = \alpha_3 = 0</math>

Instead of “standard generators”, we call them standard basis vectors. We refer to <math>\{[1, 0, 0], [0, 1, 0], [0, 0, 1]\}</math> as standard basis for <math>\mathbb{R}^3</math> . In general the standard generators are usually called standard basis vectors.

Another basis for <math>\mathbb{R}^3</math> : [1, 1, 1], [1, 1, 0], [0, 1, 1]

  • Spanning: Can write standard generators in terms of these vectors:

<MATH> [1, 0, 0] = [1, 1, 1] - [0, 1, 1] [0, 1, 0] = [1, 1, 0] + [0, 1, 1] - [1, 1, 1] [0, 0, 1] = [1, 1, 1] - [1, 1, 0] </MATH> Since e1, e2, e3 can be written in terms of these new vectors, every vector in Span {e1, e2, e3} is in span of new vectors. Thus <math>\mathbb{R}^3</math> equals span of new vectors.

  • Linearly independent: Write zero vector as linear combination:

<MATH>0 = x [1, 1, 1] + y [1, 1, 0] + z [0, 1, 1] = [x + y, x + y + z, x + z]</MATH>

Looking at each entry, we get <MATH> \begin{array}{l} 0 = x + y \\ 0 = x + y + z \\ 0 = x + z \end{array} </MATH>

  • Plug x + y = 0 into second equation to get 0 = z.
  • Plug z = 0 into third equation to get x = 0.
  • Plug x = 0 into first equation to get y = 0.

Thus the linear combination is Linear Algebra - Linear combination.

Documentation / Reference





Discover More
Card Puncher Data Processing
Linear Algebra - (Direct Sum | Union) of vector spaces

Let U and V be two vector spaces consisting of D-vectors over a field F. Definition: If U and V share only the zero vector then we define the direct sum of U and V to be the set: written: That is, ...
Card Puncher Data Processing
Linear Algebra - (Gaussian|Common) Elimination

Method illustrated in Chapter Eight of a Chinese text, The Nine Chapters on the Mathematical Art, that was written roughly two thousand years ago. Rediscovered in Europe by Isaac Newton (England) and Michel...
Card Puncher Data Processing
Linear Algebra - Coordinate system

coordinate system in terms of vector. Idea of coordinate system for a vector space V: (and generalized beyond two dimensions), Coordinate system for a vector space V is specified by generators of...
Card Puncher Data Processing
Linear Algebra - Dimension of a vector space

The dimension of a vector space V is the size of a basis for that vector space written: dim V. rank If U is a subspace of W then D1: (or ) and D2: if then Example: Suppose V = Span...
Card Puncher Data Processing
Linear Algebra - Dual of a vector space

The set of vectors u such that u · v = 0 for every vector v in V is called thedual of V. Dual is written as . Definition: For a subspace V of , the dual space of V, written , is: The dual of Span {a1,...
Card Puncher Data Processing
Linear Algebra - Find a basis computation problem

Find a basis for a vector space Example: Find a basis for the null space of By the dot-product definition of matrix-vector multiplication, a vector v is in the null space of A if the dot-product...
Card Puncher Data Processing
Linear Algebra - Find intersection of geometric objects

Find intersection of geometric objects Find the intersection of the plane spanned by [1, 0, 0] and [0, 1,−1] the plane spanned by [1, 2,−2] and [0, 1, 1] The orthogonal complement in of...
Card Puncher Data Processing
Linear Algebra - Generators of a Vector Space

The generators for the set of vectors are the vectors in the following formula: where is a generating set for {[3, 0, 0], [0, 2, 0], [0, 0, 1]} is a generating set for . = Span {[3, 0,...
Graph
Linear Algebra - Graph

graph in linear algebra Formulating GF(2) vector: subset {Pembroke, Main, Gregorian} is represented by: Pembroke Athletic Bio-Med Main Keeney Wriston Gregorian 1 1 1 Edge Representation...
Linear Algebra Image Scheme
Linear Algebra - Image representation

A generalized image consists of a grid of generalized pixels, where each generalized pixel is a quadrilateral (not necessarily a rectangle). Think of an image as a grid of rectangles, each assigned a...



Share this page:
Follow us:
Task Runner