Home
Contact
Sitemap
Bookmark us
Home
Services
Products
Biometrics
eFinance
Company
Coordinate systems and change of basis
Due to the short length of this course, we will not be covering the topic of least squares as previously advertised. This lecture will be about change of basis.
Two examples will illustrate the ideas:
Magic squares
Population movement
Definitions:
5: Coordinate system:
A coordinate system is a basis that is used to describe points in the vector space
6: Change of basis:
A change of basis is a description of how to get from a description of points in terms of one basis to a description in terms of another. Eg, (1,1) and (1,-1) form a basis of R
2
, call it B. Then (0,1)=(1/2)(1,1)-(1/2)(1,-1), so (0,1) is 1/2 of one vector, and -1/2 of the other, so we write this as (0,1)=(1/2,-1/2)
B
. This is a change of basis from the standard basis to the basis B. This can be given in terms of a matrix.
Notes on text book:
5.3: Linear independent sets, basis
We've already seen the ideas of this section. One reason a vector space is such a great thing is that all the infinitely many things in it can be described by just a few - you need some vectors that will span it, eg, (1,0) and (0,1) span the two dimensional space R
2
, since you can get to any other point using them. They are also linearly independent; you could take (1,0), (0,1), and (1,1), but that is more than we need. A basis is a collection of vectors that is just right; not too little, not too much. We'll also mention orthogonal basis a little, which is from section 7.1 and 7.2. Orthogonal basis come up when we find the eigen vectors of a symmetric matrix.
5.4: Coordinate systems
This is about when you choose a different basis. It's about how something is in the span of a certain set, eg, (1,1)=1(1,0)+1(0,1), but in another coordinate system, eg, that with basis (1,1), (1,-1), we get (1,1)=1(1,1)+0(1,-1).
5.7: Change of basis
Section 5.4 talks about different basis. This section gives a rule for how to change from a description of a point in terms of one basis to a description in terms of another. Eg, how to quicly work out how something is in the span of a different choice of vectors, eg, what is (1,1) in terms of (1,1) and (1,-1) rather than in terms of (1,0) and (0,1)? We will also look at reasons why you might want to do this, in particular, the population Markov chain. When we look at orthogonal systems, we'll see a really easy way to change basis, and see a use of the projection map.
Basis and coordinate systems
We've already seen how we need to find how something is in the span of the eigen vectors to find what happens in some process in the long run. In those examples, the eigen vectors are a linearly independent spanning set, and so formed a basis. When we expressed the initial vector in terms of the eigen vectors, we were making a change of coordinate system.
There are other situations were one might want to change basis, or it might not be clear what is the best basis. We'll look at some examples.
Example: Magic Squares
The problem is about finding magic squares. It could be done for very large squares, but we'll just do it for a small example.
A 2 by 2 magic square is a square like this:
a
b
c
d
For it to be magic we must have the sums of the rows and columns all equal, so
a+b=c+d=a+c=b+d
For example, the following is a magic square, with all the rows and columns adding up to 10.
7
3
3
7
What are all the possible magic squares?
The set of magic squares is a vector space, since if we add two magic squares, or multiply by a constant, we still have a magic square:
a
b
c
d
+
e
f
g
h
=
a+e
b+f
c+g
d+h
k
a
b
c
d
=
ka
kb
kc
kd
Eg, if we have a magic square whos rows and cols add to 8, and another whos rows and cols add to 7, then the sum is a magic square whos rows and cols add to 15.
We can make this more like a normal linear algebra problem that we're used to by making squares correspond to points in R
4
.
The space of all 2 by 2 squares corresponds to R
4
, eg,
1
2
3
4
corresponds to (1,2,3,4), and in general
a
b
c
d
corresponds to (a,b,c,d).
The conditions on a,b,c,d can be written as:
a
+
b
=
c
+
d
a
+
c
=
b
+
d
a
+
b
=
a
+
c
We can write this as follows:
a
+
b
-
c
-
d
=
0
a
-
b
+
c
-
d
=
0
b
-
c
=
0
Solve by augmented matrix and row reduction:
/
1
1
-1
-1
|
0
\
/
1
1
-1
-1
|
0
\
/
1
1
-1
-1
|
0
\
R
1
-R
2
/
1
0
0
-1
|
0
\
|
1
-1
1
-1
|
0
|
R
2
-R
1
|
0
-2
2
0
|
0
|
-(1/2)R
2
|
0
1
-1
0
|
0
|
|
0
1
-1
0
|
0
|
\
0
1
-1
0
|
0
/
\
0
1
-1
0
|
0
/
R
3
+(1/2)R
2
\
0
0
0
0
|
0
/
\
0
0
0
0
|
0
/
So the solution is
a=d and b=c
We have (a,b,c,d)=(a,b,d,c)=(d,c,c,d)=d(1,0,0,1)+c(0,1,1,0), so for the problem in R
4
, (1,0,0,1) and (0,1,10) is a basis for the solution space of the homogeneous system of linear equations.
The following magic squares are a basis of the space of magic squares:
1
0
0
1
,
0
1
1
0
So any magic square is a sum of these, eg:
6
1
0
0
1
+
4
0
1
1
0
=
6
4
4
6
The above is not the only possible basis. For instance, the following is also a basis:
1
1
1
1
,
1
-1
-1
1
To check this is a basis, note that they are linearly independent, and that there are two of them, so they span a space of dimension two. They are both magic squares, so they span a subspace of the space of magic squares of dimension two; but the space of magic squares itself is only of dimension two, so these must span the whole space of magic squares. We could also check this by writing linear equations, and solving them. We can also write how to get to any magic square with them, eg:
5
1
1
1
1
+
1
-1
-1
1
=
6
4
4
6
What we've done is made a change of basis.
We are going to talk about how to change from a description in terms of one basis to a description in terms of another basis.
Watch this space for more to come soon.
Change of basis matrix
Population movement example
Orthonormal basis
Recurrence relation: trains and Fibonnaci sequence
I learned about the following problem in Peter Taylor's class on math and poetry (highly recommended), and you can find more details about this, and lots of variations on it, in his high school math text book.
We have carriages that are length 1 or two, and these can be used to make trains.
The carriages:
Some trains:
The problem is, how many trains can you make of a certain length?
For example, how many trains are there of length 5?
Well, you can play around and find that the below are all the possibilities:
To make sure you've got them all, you have to think of some way of thinking about them. Eg, you could think about trains with two carriages of length 2, or one, or no carriages of length 2:
Or another way is to pick out which trains start with carriages of length one, and which start with carriages of length 2:
This second way turns out to be very useful, since now, if we cut off the front carriage, in one case we have trains of length 4 left over, and in the other case, trains of length 3.
So, now we can see that
Number of trains of length 5 = number of trains of length 4 + number of trains of length 3
And in general, the same kind of thing is going to work, we have a sequence of relations:
If t
n
is the number of trains of length n, then we have:
t
2
=t
1
+t
0
t
3
=t
2
+t
1
t
4
=t
3
+t
2
t
5
=t
4
+t
3
t
6
=t
5
+t
4
t
7
=t
6
+t
5
t
8
=t
7
+t
6
and so on:
t
n
=t
n-1
+t
n-2
n
1
2
3
4
5
6
7
8
9
10
t
n
1
2
3
5
8
13
21
34
55
89
This is a linear relation; in terms of vectors, we could write it as:
(
t
n
)
=
(
1
1
)
/
t
n-1
\
\
t
n-2
/
Well, we're applying some kind of transformation, and we want to apply it many times. But we've studied examples were you apply the transformation to something, eg, a vector (a,b) in R
2
, and you get out another vector in R
2
. In the above, you apply the transformation to two things, t
n-1
and t
n-2
, but only get one thing out, t
n
. But we can make it so we get the same kind of thing out as what we put in by using two linear equations instead of just one:
t
n
=t
n-1
+t
n-2
t
n-1
=t
n-1
Now this can be written as an equation like this:
/
t
n
\
=
/
1
1
\
/
t
n-1
\
\
t
n-1
/
\
1
0
/
\
t
n-2
/
If we use some short hand:
x
n
=
/
t
n
\
A
=
/
1
1
\
\
t
n-1
/
\
1
0
/
And then the linear equations become
x
n
=Ax
n-1
eg,
x
5
=Ax
4
x
4
=Ax
3
x
3
=Ax
2
x
2
=Ax
1
x
1
=Ax
0
So to get x
5
we apply A 5 times, starting from x
0
. Generally we have
x
n
=A
n
x
0
Actually, we do need to check that x
0
makes sence, since this is (x
0
,x
-1
). Well, we can just say that there is only one way to make a train no cars long, and that is to take no carriages, and that there are no ways to get trains of length -1. So x
0
=(1,0).
To find x
n
, what we need to do is apply A n times. We've seen how to work out how to easily apply a matrix many times - find the eigen vectors and use them. More specifically:
Find the eigen values
Find the eigen vectors
Find how to express the initial state in terms of the eigen vectors
Find apply the matrix the required number of times.
Eigen values
The eigen values are (1+root(5))/2 and (1-root(5))/2. For short I'll call these t and t
~
respectively. Note that t is the
golden ratio.
Eigen vectors
An eigen vector for t is (t,1)
An eigen vector for t
~
is (t
~
,1)
Initial state in terms of eigen vectors
By solving a linear system, we can find that
x
0
=
/
1
\
\
0
/
=
(1/root(5))
/
t
\
\
1
/
-
(1/root(5))
/
t
~
\
\
0
/
Applying A
n
Now we can find x
n
=(t
n
,t
n-1
)
x
n
=
A
n
x
0
=
A
n
/
1
\
\
0
/
=
A
n
x
0
=
A
n
(
(1/root(5))
/
t
\
\
1
/
-
(1/root(5))
/
t
~
\
\
0
/
)
=
(1/root(5))
A
n
/
t
\
\
1
/
-
(1/root(5))
A
n
/
t
~
\
\
0
/
=
(1/root(5))
t
n
/
t
\
\
1
/
-
(1/root(5))
(t
~
)
n
/
t
~
\
\
0
/
=
/
(1/root(5))
t
n+1
-
(1/root(5))
t
~
n+1
\
\
(1/root(5))
t
n
-
(1/root(5))
t
~
n
/
So, using the definition of t and t
~
, and substituting into the fomular, we get that the number of ways of making trains of length n is
(1/root(5))[((1+root(5))/2)
n+1
-((1-root(5))/2)
n+1
]
So, using your calculator, you can find that there are 233 ways of making trains of length 12. Can you draw them all? Will complete this soon....
Quiz
The quiz on Thursday 12th June will be similar to the following question:
Question
what is the rank of the following matrix:
/
1
2
3
\
|
0
2
1
|
\
1
6
5
/
What is the nullity?
Find a basis for the column space
Find a basis for the null space
Solution
The rank is equal to the dimension of the column space, and also equal to the dimension of the row space, and also equal to the number of leading ones in the reduced matrix.
So we can row reduce to find the rank. Alternatively, we can just note that the third column is 2 of the first, plus half the second, and the first and second are independent, so the dimension of the column space is 2, so the rank is two.
If you don't spot the relationship between columns by inspection, you need to do some row reduction:
/
1
2
3
\
/
1
2
3
\
/
1
2
3
\
|
0
2
1
|
|
0
2
1
|
|
0
2
1
|
\
1
6
5
/
\
0
4
2
/
\
0
0
0
/
/
1
2
3
\
/
1
0
2
\
|
0
1
1/2
|
|
0
1
1/2
|
\
0
0
0
/
\
0
0
0
/
In the reduced matrix, the third column is clearly 1 of the first, plus half of the second, and so the same relationship must hold in the original matrix. There are two leading ones, so the rank is 2.
The nullity is the dimension of the space of solution to the linear system with augmented matrix
/
1
2
3
|
0
\
|
0
2
1
|
0
|
\
1
6
5
|
0
/
The rank nullity formula tells us the the nullity will be 3-2=1.
Since the first two columns are independent, and the third depends on them, the first two give a basis for the column space, so we can take for a basis:
{(1,0,1),(2,2,6)}
To find the null space, we reduce the augmented matrix to echelon form:
/
1
0
2
|
0
\
|
0
1
1/2
|
0
|
\
0
0
0
|
0
/
So if the columns correspond to variables x,y,z, then z is the free variable, and x=-2z, y=-(1/2)z, so in terms of the free variable,
(x,y,z)=(-2z,-(1/2)z,z)=z(-2,-(1/2),1)
So every solution is a multiple of (-2,-(1/2),1), so this is a basis of the null space.
Assignment
The assignment is due in on Tuesday 17th, at my office, Jeffrey 401, before 6pm. Solutions will be posted below soon after 6pm.
Note that some exam questions may be similar to these questions. Generally exam questions will be similar to homework and quiz questions.
Note
For solutions to the assignment, see
here.
Note, these are not quite completed yet. Will be by Wednesday morning.
Problem 1
Problem 2
Problem 3
Problem 1
(
Solution
)
A polynomial in x of degree 4 is something of the form:
ax
4
+bx
3
+cx
2
+dx+e
eg:
2x
4
+3x
3
-5x
2
+8x+2
The set of all polynomials of degree 4 is called P
4
for short.
(i) Show P
4
is a vector space (check the first
four conditions given in lecture 10
(ii) Give a basis for P
4
(iii) Which of the following is a subspace of P
4
?
(a) The set of polynomials with the coefficient of x
2
=7
(b) The set of polynomials f in P
4
with f(0)=3
(c) The set of polynomials with P
4
f(1)=f(2), and f(3)=0
(iv)
(a) For the examples of (iii) that are not subspaces, give and example to show why not.
(b) For the examples of (iii) that are subspaces, give a basis.
Problem 2
(
Solution
)
We have carriages of lengths 2 and 3.
There are no carriages of length 1.
There are two types of carriage of length 2, type A, and type B.
There is one carriage of length 3, type C.
Find a formula for the number of trains of length n that can be made from these carriages.
Eg:
for n=1, we have no ways to make a train of length 1
For n=2, there are two ways, [AA], and [BB]
For n=3, there is one way, [CCC]
For n=2, there are 4 ways: [AA][BB], [AA][AA], [BB][BB], [BB][AA]
Hint:
how can you write (t
n
,t
n-1
,t
n-2
) in terms of (t
n-1
,t
n-2
,t
n-3
) if t
n
is the number of different types of trains of length n?
You might find it useful that the roots of
-L
3
+2L+1
are -1, (1-root(5))/2, (1+root(5))/2
Problem 3
(
Solution
)
A magic square of size 3 by 3 looks like:
a
b
c
d
e
f
g
h
k
where we have the conditions:
a+b+c=d+e+f=g+h+k=a+d+g=b+e+h=c+f+k=a+e+k=g+e+c
(i) Show that the set of all three by three magic squares is a vector space
(ii) Write the conditions as 7 linear equations, and use an augmented matrix and row reduction to find a general solution
(iii) Write a basis for the space of 3 by three magic squares