DM554

Linear and Integer Programming

Lecture 8
Linear Transformations

Marco Chiarandini
Department of Mathematics & Computer Science
University of Southern Denmark
 Linear Transformations
Outline Coordinate Change

1. Linear Transformations

2. Coordinate Change

2
 Linear Transformations
Resume Coordinate Change

• Linear dependence and independence

• Determine linear dependency of a set of vertices, ie, find non-trivial

lin. combination that equal zero

• Basis

• Find a basis for a linear space

• Find a basis for the null space, range and row space of a matrix (from its
reduced echelon form)

• Dimension (finite, infinite)

• Rank-nullity theorem

3
 Linear Transformations
Outline Coordinate Change

1. Linear Transformations

2. Coordinate Change

4
 Linear Transformations
Linear Transformations Coordinate Change

Definition (Linear Transformation)

Let V and W be two vector spaces. A function T : V → W is linear if for all
u, v ∈ V and all α ∈ R:
1. T (u + v) = T (u) + T (v)
2. T (αu) = αT (u)
A linear transformation is a linear function between two vector spaces

• If V = W also known as linear operator

• Equivalent condition: T (αu + βv) = αT (u) + βT (v)

• for all 0 ∈ V , T (0) = 0

5
 Linear Transformations
Coordinate Change

Example (Linear Transformations)

• vector space V = R, F1 (x) = px for any p ∈ R

∀x, y ∈ R, α, β ∈ R : F1 (αx + βy ) = p(αx + βy ) = α(px) + β(px)

= αF1 (x) + βF1 (y )

• vector space V = R, F1 (x) = px + q for any p, q ∈ R or F3 (x) = x 2 are

not linear transformations

T (x + y ) 6= T (x) + T (y )∀x, y ∈ R

• vector spaces V = Rn , W = Rm , m × n matrix A, T (x) = Ax for x ∈ Rn

T (u + v) = A(u + v) = Au + Av = T (u) + T (v)

T (αu) = A(αu) = αAu = αT (u)

6
 Linear Transformations
Coordinate Change

Example (Linear Transformations)

• vector spaces V = Rn , W : f : R → R. T : Rn → W :
 
u1
u2 
T (u) = T  .  = pu1 ,u2 ,...,un = pu
 
 .. 
un

pu1 ,u2 ,...,un = u1 x 1 + u2 x 2 + u3 x 3 + · · · + un x n

pu+v (x) = · · · = (pu + pv )(x)

pαu (x) = · · · = αpu (x)

7
 Linear Transformations
Linear Transformations and Matrices Coordinate Change

• any m × n matrix A defines a linear transformation T : Rn → Rm TA

• for every linear transformation T : Rn → Rm there is a matrix A such

that T (v) = Av AT

Theorem
Let T : Rn → Rm be a linear transformation and {e1 , e2 , . . . , en } denote the
standard basis of Rn and let A be the matrix whose columns are the vectors
T (e1 ), T (e2 ), . . . , T (en ): that is,
 
A = T (e1 ) T (e2 ) . . . T (en

Then, for every x ∈ Rn , T (x) = Ax.

Proof: write any vector x ∈ Rn as lin. comb. of standard basis and then make
the image of it.

8
Example
T : R3 → R3
   
x x +y +z
T y  =  x − y 
z x + 2y − 3z

• The image of u = [1, 2, 3]T can be found by substitution:

T (u) = [6, −1, −4]T .

• to find AT :
     
1 1 1
T (e1 ) = 1 T (e2 ) = −1 T (e3 ) =  0 
1 2 −3
 
1 1 1
A = [T (e1 ) T (e2 ) T (en )] = 1 −1 0 
1 2 −3
T (u) = Au = [6, −1, −4]T .
 Linear Transformations
Linear Transformation in R2 Coordinate Change

• We can visualize them!

• Reflection in the x axis:

     
x x 1 0
T : 7→ AT =
y −y 0 −1

• Stretching the plane away from the origin

  
2 0 x
T (x) =
0 3 y

10
 • Rotation anticlockwise by an angle θ
y

T (e2 ) e2
θ T (e1 )
θ x
(0, 0) e1 1

we search the images of the standard basis vector e1 , e2

   
a d
T (e1 ) = , T (e1 ) =
c b
they will be orthogonal and with length 1.
   
a b cos θ − sin θ
A= =
c d sin θ cos θ
For π/4:   " √1 #
− √1
 
a b cos θ − sin θ
A= = = √12 √1 2
c d sin θ cos θ 2 2

(the matrix A is correct, in the lecture, I made a mistake placing the θ angle on the other side of e2 )
 Linear Transformations
Identity and Zero Linear Transformations Coordinate Change

• For T : V → V the linear transformation such that T (v) = v is called

the identity.

• if V = Rn , the matrix AT = I (of size n × n)

• For T : V → W the linear transformation such that T (v) = 0 is called

the zero transformation.

• If V = Rn and W = Rm , the matrix AT is an m × n matrix of zeros.

12
 Linear Transformations
Composition of Linear Transformations Coordinate Change

• Let T : V → W and S : W → U be linear transformations.

The composition of ST is again a linear transformation given by:

ST (v) = S(T (v)) = S(w) = u

where w = T (v)

T S
• ST means do T and then do S: V −
→W −
→U

• if T : Rn → Rm and S : Rm → Rp in terms of matrices:

ST (v) = S(T (v)) = S(AT v) = AS AT v

note that composition is not commutative

13
 Linear Transformations
Combinations of Linear Transformations Coordinate Change

• If S, T : V → W are linear transformations between the same vector

spaces, then S + T and αS, α ∈ R are linear transformations.

• hence also αS + βT , α, β ∈ R is

14
 Linear Transformations
Inverse Linear Transformations Coordinate Change

• If V and W are finite-dimensional vector spaces of the same dimension,

then the inverse of a lin. transf. T : V → W is the lin. transf such that

T −1 (T (v )) = v

• In Rn if T −1 exists, then its matrix satisfies:

T −1 (T (v )) = AT −1 AT v = I v

that is, T −1 exists iff (AT )−1 exists and AT −1 = (AT )−1
(recall that if BA = I then B = A−1 )

• In R2 for rotations:
   
cos(−θ) − sin(−θ) cos θ sin θ
AT −1 = =
sin(−θ) cos(−θ) − sin θ cos θ

15
 Linear Transformations
Coordinate Change

Example
Is there an inverse to T : R3 → R3
   
x x +y +z
T y  =  x − y 
z x + 2y − 3z
 
1 1 1
A = 1 −1 0 
1 2 −3
Since det(A) = 9 then the matrix is invertible, and T − 1 is given by the
matrix:
     1 5 1

1
3 5 1 u 3u + 9v + 9w
A−1 = 3 −4 1  T −1  v  =  13 u − 49 v + 91 w 
9 1 1 2
3 −1 −2 w 3u + 9v − 9w

16
 Linear Transformations
Linear Transformations from V to W Coordinate Change

Theorem
Let V be a finite-dimensional vector space and let T be a linear
transformation from V to a vector space W .
Then T is completely determined by what it does to a basis of V .

Proof

(unique representation in V implies unique representation in T )

17
 Linear Transformations
Coordinate Change

• If both V and W are finite dimensional vector spaces, then we can find
a matrix that represents the linear transformation:

• suppose V has dim(V ) = n and basis B = {v1 , v2 , . . . , vn }

and W has dim(W ) = m and basis S = {w1 , w2 , . . . , wm };

• coordinates of v ∈ V are [v]B

coordinates of T (v) ∈ W are [T (v)]S

• we search for a matrix A such that:

[T (v)]S = A[v]B

• we find it by:

[T (v)]S = a1 [T (v1 )]S + a2 [T (v2 )]S + · · · + an [T (vn )]S

= [[T (v1 )]S [T (v2 )]S · · · [T (vn )]S ] [v]B

where [v]B = [a1 , a2 , . . . , an ]T

18
 Linear Transformations
Range and Null Space Coordinate Change

Definition (Range and null space)

T : V → W . The range R(T ) of T is:

R(T ) = {T (v) | v ∈ V }

and the null space (or kernel) N(T ) of T is

N(T ) = {v ∈ V | T (v) = 0}

• the range is a subspace of W and the null space of V .

• Matrix case, T : Rn → Rm
R(T ) = R(A) N(T ) = N(A)

• Rank-nullity theorem:
rank(T ) = dim(R(T ))
nullity(T ) = dim(N(T ))
rank(T ) + nullity(T ) = dim(V )
19
 Linear Transformations
Coordinate Change

Example
Construct a linear transformation T : R3 → R3 with
   
 1 
N(T ) = t 2 : t ∈ R , R(T ) = xy -plane.
3
 

20
 Linear Transformations
Outline Coordinate Change

1. Linear Transformations

2. Coordinate Change

21
 Linear Transformations
Coordinates Coordinate Change

Recall:
Definition (Coordinates)
If S = {v1 , v2 , . . . , vn } is a basis of a vector space V , then
• any vector v ∈ V can be expressed uniquely as v = α1 v1 + · · · + αn vn
• and the real numbers α1 , α2 , . . . , αn are the coordinates of v wrt the
basis S.
To denote the coordinate vector of v in the basis S we use the notation
 
α1
α2 
[v]S =  . 
 
 .. 
αn S

• In the standard basis the coordinates of v are precisely the components

of the vector v: v = v1 e1 + v2 e2 + · · · + vn en
• How to find coordinates of a vector v wrt another basis?
22
 Linear Transformations
Transition from Standard to Basis B Coordinate Change

Definition (Transition Matrix)

Let B = {v1 , v2 , . . . , vn } be a basis of Rn . The coordinates of a vector x wrt
B, a = [a, a2 , . . . , an ]T = [x]B , are found by solving the linear system:

a1 v1 + a2 v2 + . . . + an vn = x that is x = [v1 v2 · · · vn ]a

We call P the matrix whose columns are the basis vectors:

P = [v1 v2 · · · vn ]

Then for any vector x ∈ Rn

x = P[x]B transition matrix from B coords to standard coords

moreover P is invertible (columns are a basis):

[x]B = P −1 x transition matrix from standard coords to B coords

23
Example
       
 1 2 3  4
B =  2  , −1 , 2 [v]B =  1 
−1 4 1 −5
 

 
1 2 3
P =  2 −1 2
−1 4 1
det(P) = 4 6= 0 so B is a basis of R3 standard coordinates of v:
       
1 2 3 −9
v = 4  2  + −1 − 5 2 = −3
−1 4 1 −5
    
1 2 3 4 −9
v =  2 −1 2  1  = −3
−1 4 1 −5 B −5
Example (cntd)
       
 1 2 3  5
B =  2  , −1 , 2 , [x] =  7 
−1 4 1 −3
 

B coordinates of vector x:
       
5 1 2 3
 7  = a1  2  + a2 −1 + a3 2
−3 −1 4 1

either we solve Pa = x in a by Gaussian elimination or

we find the inverse P −1 :
 
1
[x]B = P −1 x = −1 check the calculation
2 B

What are the B coordinates of the basis vector? ([1, 0, 0], [0, 1, 0], [0, 0, 1])
 Linear Transformations
Change of Basis Coordinate Change

Since T (x) = Px then T (ei ) = vi , ie, T maps standard basis vector to new
basis vectors
Example
Rotate basis in R2 by π/4 anticlockwise, find coordinates of a vector wrt the
new basis.
 " √1 √1
#
cos π4 − sin π4 −

AT = = √12 √1 2
sin π4 cos π4 2 2

Since the matrix AT rotates {e1 , e2 }, then AT = P and its columns tell us
the coordinates of the new basis and v = P[v]B and [v]B = P −1 v. The
inverse is a rotation clockwise:
 " √1 √1
#
cos(− π4 ) − sin(− π4 ) cos( π4 ) sin( π4 )
  
−1 2 2
P = = =
sin(− π4 ) cos(− π4 ) − sin( π4 ) cos( π4 ) − √12 √12

26
 Linear Transformations
Coordinate Change

Example (cntd)
Find the new coordinates of a vector x = [1, 1]T
" #   √ 
√1 √1 1 2
[x]B = P −1 x = 2 2 =
− √12 √12 1 0

27
 Linear Transformations
Change of basis from B to B 0 Coordinate Change

Given a basis B of Rn with transition matrix PB ,

and another basis B 0 with transition matrix PB 0 ,
how do we change from coords in the basis B to coords in the basis B 0 ?
v=PB [v]B B
[v]B 0 =P −1
0 v
coordinates in B −−−−−−→ standard coordinates −−−−−−−→ coordinates in B 0
[v]B 0 = PB−1
0 PB [v]B

ex7sh3
M = PB−1 −1
0 PB = PB 0 [v1 v2 . . . vn ] = [PB−1 −1 −1
0 v1 PB 0 v2 . . . PB 0 vn ]

Theorem
If B and B 0 are two bases of Rn , with

B = {v1 , v2 , . . . , vn }

then the transition matrix from B coordinates to B 0 coordinates is given by

 
M = [v1 ]B 0 [v2 ]B 0 · · · [vn ]B 0

(the columns of M are the B 0 coordinates of the basis B)

28
 Linear Transformations
Coordinate Change

Example
       
1 −1 3 5
B= , S= ,
2 1 1 2

are basis of R2 , indeed the corresponding transition matrices from standard

basis:
   
1 −1 3 5
P= Q=
2 1 1 2

have det(P) = 3, det(Q) = 1. Hence, lin. indep. vectors.

We are given
 
4
[x]B =
−1 B

find its coordinates in S.

29
Example (cntd)
1. find first the standard coordinates of x
        
1 −1 1 −1 4 5
x=4 − = =
2 1 2 1 −1 7

and then find S coordinates:

    
2 −5 5 −25
[x]S = Q −1 x = =
−1 3 7 16 S

2. use transition matrix M from B to S coordinates:

v = P[v]B
and v = Q[v]S [v]S = Q −1 P[v]B :
    
−1 2 −5 1 −1 −8 −7
M=Q P= =
−1 3 2 1 5 4
    
−8 −7 4 −25
[x]S = =
5 4 −1 16 S