A transformation t of V is linear
<=>
For all vectors u , v and all real numbers r
t(u+v) = t(u)+t(v) and t(r.u) = r.t(u)
The set of all linear transformations of V is L(V).t : R x R -> R x R : (x,y) -> (x+y,x) t : R x R -> R x R : (x,y) -> (0,y) t : R -> R : x -> 6x
t(0) = t(0v) = 0.t(v) = 0
Hence, the image of the vector 0 is 0.
t is in L(V)
<=>
For all vectors u, v and all real numbers r, s
t(r.u + s.v) = r.t(u) + s.t(v)
Proof :
t(r.u + s.v) = t(r.u) + t(s.v) = r.t(u) + s.t(v)
Part 2 : If t(r.u + s.v) = r.t(u) + s.t(v) for all r, s then
take r = s = 1 t(u+v) = t(u)+t(v)
take s = 0 t(r.u) = r.t(u)
Q.E.D.
t(v) = k.u1 + l.u2 + m.u3
t is linear because :
t(v + w) = t( (k + k')e1 + (l + l')e2 + (m + m')e3 )
= (k + k')u1 + (l + l')u2 + (m + m')u3
= k.u1 + l.u2 + m.u3 + k'.u1 + l'.u2 + m'.u3
= t(v) + t(w)
t(r.v) = t(rk.e1 + rl.e2 + rm.e3)
= rk.u1 + rl.u2 + rm.u3
= r(k.u1 + l.u2 + m.u3)
= rt(v)
Furthermore
t(e1) = t(1.e1 + 0.e2 + 0.e3) = 1.u1 + 0.u2 + 0.u3 = u1
t(e2) = t(0.e1 + 1.e2 + 0.e3) = 0.u1 + 1.u2 + 0.u3 = u2
t(e3) = t(0.e1 + 0.e2 + 1.e3) = 0.u1 + 1.u2 + 1.u3 = u3
Finely, t is unique because
t(v) = t(k.e1+l.e2+m.e3)
= k.u1 + l.u2 + m.u3
and
t'(v)= t'(k.e1 + l.e2 + m.e3)
= t'(k.e1) + t'(l.e2) + t'(m.e3)
= k.t'(e1) + l.t'(e2) + m.t'(e3)
= k.u1 + l.u2 + m.u3
So t = t'
Example:
u1 = a.e1 + b.e2 + c.e3
u2 = d.e1 + e.e2 + f.e3
u3 = g.e1 + h.e2 + i.e3
A random vector v = k.e1+l.e2+m.e3 is transformed by t in
t(v) = k.u1+l.u2+m.u3
t(v) = k.u1 + l.u2 + m.u3
<=>
t(v) = k.(a.e1 + b.e2 + c.e3) +
l.(d.e1 + e.e2 + f.e3) +
m.(g.e1 + h.e2 + i.e3)
<=>
t(v) = (k.a + l.d + m.g).e1 +
(k.b + l.e + m.h).e2 +
(k.c + l.f + m.i).e3
The coordinates of v with respect to the basis (e1, e2, e3) are (k,l,m).
k' = k.a + l.d + m.g
l' = k.b + l.e + m.h
m' = k.c + l.f + m.i
<=>
[k'] [a d g] [k]
[l'] = [b e h] . [l]
[m'] [c f i] [m]
The last matrix formula is the transformation formula associated with t with respect to the basis (e1, e2, e3).
The matrix
[a d g]
[b e h]
[c f i]
is called the matrix of the linear transformation with respect to the basis (e1, e2, e3).
The columns of this matrix are the coordinates of (u1, u2, u3).
Example :
There is just one linear transformation of R x R such that
t(1,0) = (3,2)
t(0,1) = (5,4)
The matrix of the linear transformation with respect to the basis is
[3 5]
[2 4]
t(r.u + s.v) = r.t(u) + s.t(v)
= r.0 + s.0
= 0
So, r.u + s.v is in the null-space.
Hence the null-space is a subspace of V.
[a d g]
Ao = [b e h]
[c f i]
The linear transformation t transforms a random vector
[k'] [a d g] [k]
[l'] = [b e h].[l]
[m'] [c f i] [m]
[k'] [k]
Let Ko' = [l'] and Ko = [l]
[m'] [m]
Then, Ko' = Ao.Ko (*)
Now we take a new basis in V. Then, all the vectors of V have new
coordinates. From the theory of vector spaces, we know that
these new coordinates are linked to the old ones with a transformation
matrix C.
C.Kn' = Ao.C.Kn
<=> Kn' = C-1 .Ao.C.Kn (**)
The last formula gives the connection between the coordinates of v
and t(v) with respect to the new basis.
Kn' = An.Kn (***)
From (**) and (***) we see that
An = C-1 .Ao.C
The last formula gives us the possibility to calculate the new matrix An of
t from the old matrix Ao.
[3 1]
[-1 1]
Now we take a new basis
e1' = e1 + e2
e2' = e1 - e2
Then the transformation matrix C is
[1 1]
[1 -1]
and from this C-1 is
[1/2 1/2]
[1/2 -1/2]
The matrix of the linear transformation t with respect to the new
basis is
[1/2 1/2] [3 1] [1 1]
[1/2 -1/2] [-1 1] [1 -1]
= [2 0]
[2 2]
B = C-1. A .C
As a corollary from previous formula we see that the matrices of a linear
transformation, with respect to a different basis, are similar.
B = C-1. A .C
=> |B| =|C-1|.|A|.|C|
=> |B| =|C-1|.|C|.|A|
=> |B| = |A|
So, similar matrices have the same determinant.
t+t' : V -> V : v -> t(v) + t'(v)
It can easily be proved that t+t' is a linear transformation and that the matrix of t+t' is equal to the sum of the matrices of t and of t'.
r.t : V -> V : v -> r.t(v)
It can easily be proved that r.t is a linear transformation and that the matrix of r.t is equal to r.(matrix) of t.
t.t' : V -> V : v -> t(t(v))
It can easily be proved that t.t' is a linear transformation and that the matrix of t.t' is equal to (matrix of t).(matrix of t') .
u is called an eigenvector or characteristic vector with respect to t
if and only if
u is not 0
and there is a real number r such that t(u) = r.u
The real number r is called the eigenvalue of u.
[a b c]
[d e f]
[g h i]
We denote the co(u) = (x,y,z).
Now, u(x,y,z) is a characteristic vector of t with eigenvalue r
<=>
t(u) = r.u and u not 0
<=>
[a b c] [x] [x] [x] [0]
[d e f].[y] = r.[y] with [y] not [0]
[g h i] [z] [z] [z] [0]
<=>
[a b c] [x] [1 0 0] [x] [0] [x] [0]
[d e f].[y] - r.[0 1 0].[y] = [0] with [y] not [0]
[g h i] [z] [0 0 1] [z] [0] [z] [0]
<=>
[a b c] [x] [r 0 0] [x] [0] [x] [0]
[d e f].[y] - [0 r 0].[y] = [0] with [y] not [0]
[g h i] [z] [0 0 r] [z] [0] [z] [0]
<=>
The homogeneous system in x,y,z
[a-r b c ] [x] [0]
[d e-r f ].[y] = [0]
[g h i-r] [z] [0]
has a solution different from (0,0,0).
<=>
|a-r b c |
|d e-r f | = 0
|g h i-r|
The last equation is called the characteristic equation of t with respect to the fixed basis in V.
If r is a solution of this equation, then the system
[a b c] [x] [x]
[d e f].[y] = r.[y]
[g h i] [z] [z]
has a solution (x,y,z) different from (0,0,0). With this solution corresponds a characteristic vector u(x,y,z) of t.
This way of thinking can be extended to vector spaces with dimension n.
t(r.u + s.v) = r.t(u) + s.t(v) = r.k.u + s.k.v = k.(r.u + s.v)So, for all real r and s, (r.u + s.v) is a characteristic vector with eigenvalue k.
Proof:
Let v = characteristic vector with eigenvalue k.
Let w = characteristic vector with eigenvalue l.
Suppose v and w are linear dependent, then there is a scalar r such that
w = r v
=> t(w) = t(r v)
=> l w = r.t(v)
=> l w = r. k v
=> l r v = r. k v
=> k = l
This gives a contradiction with the fact that the
two characteristic vectors correspond with different eigenvalues.
This theorem can be extended for a vector space with dimension n.
Take a vector space with dimension n and a linear transformation t.
If the n chacteristic vectors correspond with all different eigenvalues,
then these characteristic vectors are linear independent.
t(v) = k.v = k.v + 0.w
t(w) = l.w = 0.v + l.w
The matrix of t with respect to the basis ( v , w ) is
[ k 0 ]
[ 0 l ]
We say that the matrix of t is diagonal.
This can be extended for a vector space with dimension n.
Take a vector space V with dimension n and a linear transformation t.
If n characteristic vectors correspond with all different eigenvalues,
then these characteristic vectors are linear independent.
The characteristic vectors can be used as a basis of V.
The matrix of t with respect to that basis is diagonal and the eigenvalues
are the diagonal elements of the matrix.
D = C-1 . A . C
Here, C is the transformation matrix. The columns of C are the coordinates
of the new basis-vectors (characteristic vectors) with respect to the
original basis in V.
[4 -1]
[2 1]
Calculating the eigenvalues we find 3 and 2.
[1 1]
[1 2]
Then we have
-1
[3 0] = [1 1] [4 -1] [1 1]
[0 2] [1 2] [2 1] [1 2]
diag(a, b, ... l) = diag(an, bn, ... ln)
D = C-1.A.C <=> A = C.D.C-1
Then
An = C.D.C-1 . C.D.C-1 . C.D.C-1 . ... . C.D.C-1
An = C.Dn.C-1
Since it is easy to calculate Dn, An can be calculated.The recursive formula is un = un-1 + un-2
Starting from this, we'll find the formula for the n-th term of the fibonacci sequence.
First we write un-1 + un-2 = un in matrix notation.
[ 1 1 ] [ un-1]
[ 1 0 ] [ un-2] =
[ un ]
[ un-1 ]
Let M =
[ 1 1 ]
[ 1 0 ]
and
Let F =
[1]
[1]
Then
[u3]
[ ] = M. F
[u2]
Then [u4] [u3]
[ ] = M.[ ] = M2. F
[u3] [u2]
...
Then [un ]
[ ] = Mn-2. F (1)
[un-1]
Now, we'll calculate Mn-2.
To use the method from above, we need the eigenvalues and
characteristic vectors connected with the matrix M.
The characteristic equation is r2 - r - 1 = 0 .
The eigenvalues are (1 + sqrt(5))/2 and (1 - sqrt(5))/2.
We call these eigenvalues respectively k and l.
Note that k - l = sqrt(5) and k.l = 1.
You'll find that (k,1) is a characteristic vector corresponding with k
and (l,1) is a characteristic vector corresponding with l.
If we choose these characteristic vectors as a new basis, then we have the connection between M and the diagonal matrix.
[k 0]
[0 l] =
-1
[k l] [k l]
[1 1] . M . [1 1]
This is equivalent with
M =
[k l] [k 0] [k l] -1
[1 1] [0 l] [1 1]
From this we can calculate Mn-2
Mn-2 =
[k l] [kn-2 0] [k l] -1
[1 1] [0 ln-2] [1 1]
Now
[k l] -1
[1 1] =
[1/(k-l) -l/(k-l)]
[-1/(k-l) k/(k-l)] =
[1/sqrt(5) -l/sqrt(5)]
[-1/sqrt(5) k/sqrt(5)]
Then, we have
Mn-2 =
[k l] [kn-2 0] [1/sqrt(5) -l/sqrt(5)]
[1 1] [0 ln-2] [-1/sqrt(5) k/sqrt(5)]
Writing only the first row of this product we have
= (1/sqrt(5)) . [kn-1 - ln-1 -l.kn-1+ln-1.k ]
Now from (1) above we can write
un = (1/sqrt(5)) .( kn-1 - ln-1 -l.kn-1+ln-1.k )
<=>
un = (1/sqrt(5)) .(kn-1.(1-l) - ln-1.(1-k))
<=>
un = (1/sqrt(5)) .(kn - ln)
with k = (1 + sqrt(5))/2 and l = (1 - sqrt(5))/2.
This is the formula for the n-th term of the fibonacci sequence.
You can find solved problems about linear transformations
here