VectorSpaces.html

Vector Spaces

> restart:with(linalg):

Warning, new definition for norm

Warning, new definition for trace

Vector Space Axioms

Addition axioms:

A1: If u and v V then u + v V.

A2: u + v = v + u

A3: u + ( v + w ) = ( u + v ) + w

A4: There is a vector 0 V, called the zero vector , satisfying 0 + u = u for all u V

A5: For each u V there is a vector - u V, called the negative of u , such that u + (- u ) = 0

Scalar multiplication axioms:

S1: k u V for every scalar k and every u V

S2: k( u + v ) = k u + k v

S3: (k + l) u = k u + l u

S4: k(l u ) = (kl) u

S5: 1 u = u

Definitions

Span

If S = { ,..., } is a set of vectors then the span of S, Span(S), is the set of all linear combinations of the vectors of S. i.e. Span(S) = { + ... + | , ... are scalars}

example:

Let S = {(1,2),(-1,3)}and show that Span(S) = .

> u:=vector([1,2]);v:=vector([-1,3]);x:=vector([a,b]);

We will show that you can express the arbitrary vector x as a linear combination of u and v. This will show that the two vectors span .

> evalm(a1*u+a2*v)=[a,b];

> solve({a1-a2=a,2*a1+3*a2=b},{a1,a2});

This shows that no matter what a and b are we can always find coefficients a1 and a2 for u and v so that

[a,b] = a1 u + a2 v

Just let and . For instance if we want x = [2,-4] then let a1 = 2/5 and a2 = -8/5. You should check that [2,-4] = 2/5 u + (-8/5) v.

linear independence

A set S = { v1, v2, v3,....,vr } of vectors is linearly independent if and only if the vector equation

k1 v1 + k2 v2 + ... + kr vr = 0

has only the trivial solution k1 = k2 = k3 = ... = kr = 0.

e.g. Show that the following vectors in are linearly independent:

> u:=vector([1,2,3,4]);v:=vector([-1,0,3,1]);w:=vector([0,2,1,0]);

We now look at the vector equation a u + b v + c w = 0:

> v_s:=evalm(a*u+b*v+c*w)=[0,0,0,0];

Notice that if you write down the linear system of four eqations in three unknowns needed to solve this equation that the columns of the coefficient matrix are exactly the vectors u, v and w. This suggests how to quickly get the appropriate augmented matrix:

> A:=augment(transpose(stackmatrix(u,v,w)),[0,0,0,0]);

You should check with pencil and paper that this is the required system. Now we reduce A:

> rref(A);

This shows that the only solution is a = b = c = 0. Therefor, the vectors are linearly independent.

Basis

If S = { v1, v2, v3,....,vn }is a set of n vectors in the vector space V then S is a basis for V if:

a) S is a linearly independent set of vectors from V

b) V = Span(S)

example

We showed above in the Span section that the vectors u = (1,2) and v = (-1,3) span . Let us show that they are linearly independent by examining the vector equation a u + b v = 0.

> restart:with(linalg):u:=vector([1,2]):v:=vector([-1,3]):

Warning, new definition for norm

Warning, new definition for trace

> evalm(a*u+b*v)=[0,0];

> M:=transpose(stackmatrix(u,v));det(M);

[Maple Math]

Since the coefficient matrix of the associated linear system has a nonzero determinant we know that the system has only the trivial solution and so the vectors are independent and so we have both conditions for a basis.

Subspaces

Definition:

W < V is a subspace of the vector space V iff W is a a vector space under the addition and scalar multiplication of V.

Memorize the following conditions on W to be a subspace of V:

W < V is a subspace of V iff:

A) W is non-empty and u + v W for all u W, v W

B) k u W for all u W and every scalar k

example of a subspace of and more:

> restart:with(linalg):v:=vector([1,2,3]):w:=vector([0,-1,2]):

Warning, new definition for norm

Warning, new definition for trace

Let W = Span( v,w ) = the set of all linear combinations of u and v.

Clearly, 0 = [0,0,0] W since 0 = 0 u + 0 v

Also, if x and y are in W then x + y = (a u + b v ) + (c u + d v ) = (a +c) u + (b+d) v W

Let's determine whether u = [2,-5,7] is in W by trying to find a and b such that u = a v + b w .

> u:=vector([2,-5,7]);

Notice that u W iff we can find scalars a and b such that u - av - bw = [0,0,0].

> System:=evalm(a*v+b*w)=[2,-5,7];

> A:=transpose(stackmatrix(v,w));

[Maple Math]

> AugmentA:=augment(A,u);

[Maple Math]

AugmentA is the augmented matrix that corresponds to the system of equations "System"

> rref(AugmentA);

[Maple Math]

This "says" that the vector equation " System" has no solution since line 3 says 0a + Ob = 1!

Notice that this tells us that u is not in W = Span( v,w ) so it follows that W is not all of .

Let's see if we can figure out just what is W. Consider the plane that is prallel to u and v and contains the origin (we know that (0,0,0) W since (0,0,0) = 0 v + 0 w. The normal to the plane is:

> n:=crossprod(v,w);

and it follows that the plane is P:

> P:=7*x-2*y-z=0;

Now, every vector in W is of the form a v + b w for some scalars a and b. If we think of points as the endpoints of vectors (why not?) we can try plugging in the point a v + b w into P:

> evalm(a*v-b*w);

> subs({x=a,y=2*a+b,z=3*a-2*b},P);

Wow ! It seems that every "point" of the form a v + b w satisfies the equation of the plane P. Conversely, we could show that every "point" on P can be written as a linear combination a v + b w. We are forced to conclude that W and P are one and the same!

Now let's see what happens when we add in the vector u and consider W' = Span( u,v,w ) = { x | x = a u + b v + c w }.

Let [x,y,z] be any vector in and try to find scalars a,b,c such that a u + b v + c w = [x,y,z]:

> evalm(a*u+b*v+c*w)=[x,y,z];

The augmented matrix of the necessary system follows.

> AA:=augment(transpose(stackmatrix(u,v,w)),[x,y,z]);

[Maple Math]

> AAreduced:=rref(%);

[Maple Math]

The system is consistent and in fact tells us how to express any vector in as a linear combination of u, v, w.

For instance, if we want the vector [1,1,1] then we merely choose:

> a:=subs({x=1,y=1,z=1},AAreduced[1,4]);b:=subs({x=1,y=1,z=1},AAreduced[2,4]);c:=subs({x=1,y=1,z=1},AAreduced[3,4]);

Just to check we try a u + b v + c w with these values:

> x:=evalm(a*u+b*v+c*w);

et voila! You should be convinced that 2 vectors were not enough to get all of but 3 were and we have what is called a basis for .

To check that u,v,w are linearly independent (there are theoretical considerations that we don't know yet that would tell us that the check is not really necessary) we try to solve the vector equation x1 u + x2 v + x3 w = 0 .

> evalm(x1*u+x2*v+x3*w)=[0,0,0];

The coefficient matrix of this system is B, which follows:

> B:=transpose(stackmatrix(u,v,w));

[Maple Math]

> det(B);

Since det(B) = 17 <> 0 we know that B is invertible and so the system x1 u + x2 v + x3 w = 0 has only the trivial solution, so the 3 vectors are linearly independent. Two vectors were not enough to give us all of and clearly four would not be necessary. Although we will not prove it , it seems that three linearly independant vectors are necessary and sufficient to form a basis for .

The subspaces of and :

We know that the zero vector must be present in all subspaces (why?). It follows that every subspace of contains the origin (the zero vector). We proved in class that planes through the origin are subspaces of 3-space when we identify the points on the plane with the endpoints of their "position vectors" (e.g. (1,2,3) can be thought of as a point or equivalently as the components of the vector pointing from the origin to (1,2,3)). You will show as an exercise that lines through the origin are also subspaces of 3-space.

Fact: the only subspaces of are { 0 }, lines throught the origin, planes through the origin and .

Fact: the only subspaces of are { 0 }, lines throught the origin. and .

> restart:with(linalg):

Warning, new definition for norm

Warning, new definition for trace

Three more Subspaces

Defiitions : Let A be any m x n matrix. The subspace of spanned by the column vectors of A is called the column space of A and denoted Col(A). The subspace of spanned by the row vectors of A is called the row space of A and denoted Row(A). The solution space of A X = 0 is a subspace of , called the nullspace of A .

e.g.

Consider the following augmented matrix of the linear system A X = B:

> aug_a:=matrix(3,5,[1,2,-3,1,1,-2,1,2,1,0,-1,3,-1,2,1]);

First note that if the system has a solution then B must be in the Col(A) since we can write the system in the form:

x c1 + y c2 + z c3 + w c4 = B . Try it!!

It follows that AX = B is consistent if and only if B is in the column space of A .

Now, lets find the nullspace of A:

> rref(aug_a);

=> the solution of the system is [x,y,z,w] = [1/5,2/5,0,0] + [7/5,4/5,1,0]r + [1/5, -3/5,0,1]t

It follows that the nullspace of A = solution space of A X = 0 = Span{[7/5,4/5,1,0] + [1/5, -3/5,0,1]}. It is easy to see (verify!) that these vectors are linearly independent and so the nullspace has dimension 2.

We can generalize this example to the statement: The general solution of A X=B can always be written as the sum of any particular solution of A X=B and the general solution of A X=0. The vectors associated with the parameters in the solution to A X=0 are linearly independent and hence are a basis for the nullspace of A.

E.R.O.'s and Row(A) and Col(A)

Fact: ERO's do not change the rowspace (or the nullspace) of a matrix. This is clear for the nullspace since ERO's do not change the solution set of a linear system. The rowspace result takes more words -- see the proof following 5.5.4 in Anton.

Fact: ERO's can change the column space of a matrix:

e.g. consider the following matrices (this e.g. is from Anton):

> a:=matrix([[1, 3], [2, 6]]);b:=rref(a);

> a := matrix([[1, 3], [2, 6]]);

You should check that Row(A) = Row(B) but that Col(A) = span{ }and Col(B) = span{ } <> Col(A).

Big Fact : If A and B are row equivalent then a given set of column vectors of A are linearly independent if and only if the corresponding column vectors of B are linearly independent.

> A:=delcols(aug_a,5..5);B:=rref(A);

Clearly, columns 1 and 2 of B are linearly independent (why?) and so it follows that columns 1 and 2 of A are linearly independent. Notice: c3 of B is (-7/5)c1 + (-4/5)c2. It turns out that in matrix A the same relationship holds! i.e. if v1, v2, v3, v4 are the respective column vectors of A then v3 = (-7/5) v1 + (-4/5) v2. Can you see how to write v4 as a linear combination of v1 and v2 ??

Row space: By looking at A and B=rref(A) above you can see that the rows in the rref of A that contain a leading 1 (i.e. the nonzero rows) form a basis for Row(A).

e.g. Fin d a basis for Row(A) in terms of the row vectors of A and express any vectors not in the basis as a linear combination of basis vectors if A is the following matrix.

> A:=matrix(4,5,[1,1,2,1,1,0,1,1,1,-1,2,1,3,1,3,-1,-2,4,1,4]);

We will use the obvious fact that Row(A) = Col( ) (make sure that this is obvious!) and find the rref of :

> rref(transpose(A));

You can see now that columns 1, 2 and 4 of are linearly independent and form a basis for Col( ) and since the columns of are the rows of A it follows that v1, v2 and v4 form a basis for Row(A) where vi stands for the row vector of A.

Noting that in the rref of , C3 = 2*C1 - 1*C1, we can see that v3 = 2 v1 + (-1) v2.

>

Another basis e.g.

If S is the span of a set of vectors, the techniques of the preceeding example can be used to "extract" a basis for S from the spanning set.

e.g. Consider S = span{ v1, v2, v3, v4 } for the following vectors:

> v1:=vector([1,2,3]);v2:=vector([0,1,-1]);v3:=vector([2,5,5]);v4:=vector([1,0,5]);

We first form the matrix C that has the vectors for its columns and then row reduce:

> C:=transpose(stackmatrix(v1,v2,v3,v4));rref(C);

=> columns 1 and 2 form a basis for Col(C) and hence { v1, v2 } is a basis for S.

i.e. S = span{ v1,v2,v3,v4 } = span{ v1,v2 } so S is a two dimendion subspace of .

Rank and Nullity

The dimension of Row(A) is called the rank of A . Therefore, rank(A) = the number of vectors in any basis for Row(A) = the number of nonzero rows in rref(A).

Fact: The row and column space of A have the same dimension.

Proof: The nonzero rows of rref(A) are the rows that have a leading 1 and these leading 1's are the same leading 1's for the columns. i.e. the number of nonzero rows in rref(A) = the number of columns in rref(A) with a leading 1.

The dimension of the nullspace of A is called the nullity of A.

Nullity(A) = the number of parameters in the general solution of A X = 0

= the number of free variables in the general solution of A X = 0.

Notice: the number of leading variables in the general solution of A X = 0 = the number of nonzero rows in rref(A) = rank(A).

It follows that if A is any m x n matrix then rank(A) + nullity(A) = n.

e.g. Consider the folowing matrix G, which could be the coefficient matrix for a linear system of 4 equations in 5 unknowns:

> G:=matrix(4,5,[1,4,5,6,9,3,-2,1,4,-1,-1,0,-1,-2,-1,2,3,5,7,8]);

> rref(G);

You can see that there will be 3 free variables in the general solution to G X = 0 so nullity(G) = 3. Since there are 2 nonzero rows in rref(G) we have that rank(G) = 2. Therefore, rank(G) + nullity(G) = 5 = # of columns of G.

Final BIG statement of the course:

If A is an n x n matrix the the following are equivalent:

a) A is invertible

b) A X = 0 has only the trivial solution

c) The rref(A) is I

d) A is expressible as a product of elementary matrices

e) A X = B is consistent for every n x 1 matrix B

f) A X = B has exactly one solution for every n x 1 matrix B

g) det(A) <> 0

h) The column vectors of A are linearly independent

i) The row vectors of A are linearly independent

j) The column vectors of A span