Vectors in Rn

Definition

Definition 1.1 (Vector in Rn )

A vector in the Rn space is a list of values that represents a magnitude
and a direction in such space.

In this class: we will consider vectors in Rn whose initial point is the

origin, hence a vector only represents magnitude
Notation: we will represent vectors v Rn as column matrices, i.e

v1
v2

v = ..
,
.
vn n1

it is also common to find v = (v1 , . . . , vn )T .

1
Notation:

numbers: naturals (N), reals (R), complex (C)

scalars: lowercase letters, e.g. , , , . . .
vectors: lowercase bolded letters, e.g. u, v , w , . . .
matrices: uppercase bolded letters, e.g. A, B, . . .
index set: In = {1, 2, . . . , n}, n N

2
Special Vectors:

Consider the following vectors in Rn :

1 Null vector:
0 = (0, . . . , 0)T
2 Sum vector:
s = (1, . . . , 1)T
In fact u T s =
P
iIn ui
3 Canonical vector:
ej = I j ,
where I j denotes the j-th column of the identity matrix. Also called
selector vector, since u T e j = uj

3
Vector Addition and Scalar Multiplication

Consider , xi R, and a i , u, v , w Rn .

Addition: w = u + v , where wi = ui + vi
Scalar Multiplication: v = u, where vi = ui

Moreover, vector
X
v = x1 a 1 + x2 a 2 + + xm a m = xi a i ,
iIm

is called a linear combination of vectors a i . We stress that

X
v = x1 a 1 + x2 a 2 + + xm a m = xi a i = Ax,
iIm

where x = (x1 , . . . , xm )T and A = [a 1 a 2 . . . a m ] is an n m matrix.

4
Properties:

Consider , R and 0, u, v , w Rn

1 u + (v + w ) = (u + v ) + w
2 u +0=u
3 u + (u) = 0
4 u +v =v +u
5 (u + v ) = u + v
6 ( + )u = u + u
7 ()u = (u)
8 1u = u

5
Inner Product

Definition 1.2 (Inner Product)

Consider u, v Rn . The inner product between vectors u and v is
denoted by u v or hu, v i and is defined as
X
hu, v i = u T v = ui vi
iIn

The inner product is sometimes called dot product.

6
Properties:

Consider R and 0, u, v , w Rn

1 h(u + v ), w i = hu, w i + hv , w i
2 hu, v i = hu, v i
3 hu, v i = hv , ui
4 hu, ui 0 and hu, ui = 0 iff u = 0

7
Norms

A vector norm is a scalar that measures the magnitude of a vector

P
1
2 2
L2 norm: kuk2 = iIn ui
P
L1 norm: kuk1 = iIn |ui |
L norm: kuk = maxi=1,...,n |ui |
1
P p
p
Lp norm: kukp = iIn ui ,1p

Hereafter we will use k k := k k2 only.

8
Unit spheres:

L2 L1
1.0
1.0

0.5
0.5

0.0 0.0

-0.5
-0.5

-1.0
-1.0
-1.0 -0.5 0.0 0.5 1.0 -1.0 -0.5 0.0 0.5 1.0

L Lp
1.0
1.0

0.5
0.5

0.0 0.0

-0.5
-0.5

-1.0
-1.0
-1.0 -0.5 0.0 0.5 1.0 -1.0 -0.5 0.0 0.5 1.0

A vector that lies in the unit circle is called unit vector. Any u Rn
under k k2 can be turned into a unit vector letting v = u/(u T u)1/2 .
9
Properties:

For R and u Rn , it follows that

1 kuk2 = u T u.
2 kuk 0 and kuk = 0 iff u = 0
3 kuk = ||kuk
4 k uk = kuk
5 ku v k = 0 iff u = v
6 ku v k2 = kuk2 + kv k2 2u T v

10
Angle between two Vectors

Let u, v Rn .The angle between u and v can be computed as

 T 
u v
= arccos , kuk > 0, kv k > 0,
kukkv k

where we have used cos( ) = cos() cos() sin() sin().

The sign of u T v is that of cos(). Thus u T v > 0 if is acute, and

u T v < 0 o.w.
If = 0, then cos() = 1 u T v = kukkv k
If = , then cos() = 1 u T v = kukkv k
If = /2, then cos() = 0 u T v = 0, ku + v k2 = kuk2 + kv k2

11
Important results:

Theorem 1.1 (Triangle inequality)

Let u, v Rn , it follows that

kv k + kw k ku w k
Proof.
Squaring and for cos() = u T v /kukkv k we obtain 1 cos(), which
holds . 

Theorem 1.2 (Cauchy-Schwarz inequality)

Let u, v Rn , it follows that

(u T v )2 kuk2 kv k2
Proof.
For cos() = u T v /kukkv k, we get cos2 () 1 0, which holds . 

12
Applications

Example 1.1 (Random movement)

Simulate the path a player makes in the pitch. Build a simple model to
accomplish the task.

Consider the case of a player who, for each moment t in time,

decides
1 if he/she moves horizontally (left or right) and vertically (up or
down)
2 how much he/she wants to move (call this t )

For example if he/she starts at the origin and moves horizontally in the
first moment and vertically on the second, we obtain that:
" # " # " # " #
x3 0 1 0
= + 1 + 2 ,
y3 0 0 1

i.e a linear combination of selector vectors

13
Sample path:

-4 -2 2 4 6

-5

-10

14
Example 1.2 (Regression)
Are the total sells of water bottles during the month related to the
average temperature on the month?

Let xi denote the number of water bottles sold in march for year i,
and let xi denote the average temperature in march year i.
Angle between x and y is an indicator of how align the vectors
are. If cos() > 0, x and y are positively related; if cos() < 0, they
are negatively related; and if cos() = 0, they have no relation.
This result is closely related to the linear regression problem. In fact

xT y ky k
cos() = = ,
kxkky k ky k

where y = x and = arg min ky xk2 .

15
Example 1.3 (PC1 2015-II)
Let x, y Rn , and let the angle between them be denoted by
xy [0, /2]. Consider R, and define e() = y x.

Find that minimizes ke()k2 .

Let = arg min ke()k2 . Denote y = x and e = e() = y y .
Show thtat kek2 = ky k2 ky k2 .
Denote = ky k2 /ky k2 . What is the relation between and xy ?

16
Review on Matrices
Definition

Definition 2.1 (Matrix)

A matrix of dimension m n is a rectangular array of numbers, with m
rows and n columns:

a1,1 a1,2 a1,n
a2,1 a2,2 a2,n

A= . .. .. ..
.. . . .

am,1 am,2 am,n

Sometimes we write A = [ai,j ].

If m = 1, then A is a row matrix. If n = 1 then A is a column
matrix. If m = n = 1, then A is a scalar.

17
Matrix Addition and Scalar Multiplication

Let R and A = [ai,j ], B = [bi,j ], C = [ci,j ], be all m n matrices

Addition: C = A + B where ci,j = ai,j + bi,j

Scalar multiplication: B = A where bi,j = ai,j

18
Properties:

Let , R, 0 be a m n matrix and A = [ai,j ], B = [bi,j ], C = [ci,j ],

be all m n matrices. It is easy to show that

1 (A + B) + C = A + (B + C )
2 A+0=0+A=A
3 A + (A) = 0
4 A+B =B +A
5 (A + B) = A + B
6 ( + )A = A + A
7 ()A = (A)
8 1A = A

19
Matrix Multiplication

Let A be a m n matrix, B be a p q matrix, and consider n = p. The

entries of the matrix resulting from multiplying A and B are given by
X
ci,j = ai,k bk,j
kIp

We stress that the product AB is not defined if n 6= p.

The following representations are also useful:

ci,j = h(AT )i , B j i,
X
Cj = AB j = bk,j Ak ,
kIp

where M ` denotes the `-th column of matrix M. Hence, each col of C is

a linear combination of cols of A

20
Properties:

Let R and A, B, C , D be conformable matrices

1 (AB)C = A(BC )
2 A(B + C ) = AB + AC
3 (A + B)C = AC + BC
4 (AB) = (A)B = A(B)

But we stress that:

AB 6= BA
AB = 0 6 B = 0 or A = 0
AB = AC 6 B = C

21
Example 2.1 (Image Processing)
Say you have a picture as a n n matrix A in a grey scale, i.e. with
entries ai,j [0, 1], where ai,j = 0 means black and ai,j = 1 means white.

1 How would you add light to the picture? (assume that for any
transformed matrix A it holds that ai,j 0 means black and ai,j 0
means white.)
2 How can you rotate the picture horizontally by pre or post
multiplying A by another matrix?

22
Define A = A, for > 0.

1A 1.5A 2A

2.5A 3A 3.5A

23
Define A = AB, where B j = I nj+1 .

24
Transpose of a Matrix

The transpose of a matrix, written AT is obtained by writing the columns

of A, in order, as rows. That is, if B = AT then bi,j = aj,i .

25
Properties:

Let R and A and B be conformable matrices.

(A + B)T = AT + B T
(AT )T = A
(A)T = AT
(AB)T = B T AT

26
Square Matrices

If A is a m n matrix and m = n then A is a square matrix and

ai,i , i = 1, . . . , n are its diagonal entries.

27
Example 2.2 (Identity matrix)
The n-dimensional identity matrix is given by

1 0 0
0 1 0


I n = [e 1 , . . . , e n ] =
.. .. .. .. .
. . . .


0 0 0 1

Sometimes one writes I n = [i,j ], where i,j is the Kronecker delta

function
(
1 if i = j
i,j = (i, j) =
0 if i 6= j

28
Non-singular Matrices

Definition 2.2 (Inverse of a Matrix)

An n n matrix A is invertible (non-singular) if there exists an n n
matrix B such that AB = I n

29
Example 2.3 (Inverse of a 2 2 matrix)
To find the inverse involves solving for xi,j in
" # " # " #
a1,1 a1,2 x1,1 x1,2 1 0
= .
a2,1 a2,2 x2,1 x2,2 0 1
| {z } | {z } | {z }
A B I2

i.e. solving for a linear system of 2 2 equations and 2 2 unknowns

a1,1 a1,2 0 0 x1,1 1
a
2,1 a2,2 0 0 x2,1 0

=


0 0 a1,1 a1,2 x1,2 0
0 0 a2,1 a2,2 x2,2 1

to obtain x1,1 = a2,2 /d, x1,2 = a1,2 /d, x2,1 = a2,1 /d, x2,2 = a1,1 /d,
where d = a1,1 a2,2 a1,2 a2,1 = det(A).

30
Properties (inverse):

For A, B non-singular n n matrices

(A1 )1 = A
(AT )1 = (A1 )T
(AB)1 = B 1 A1
1
det(A1 ) =
det(A)
(A + B)1 = A1 (A1 + B 1 )1 B 1
A1 (A + B)1 = A1 (A1 + B 1 )1 A1

31
Review on Gauian Elimination
This section is included for completeness. For full proofs on the theorems
stated here, see:

Javier Zuniga (2013). Precalculo. Universidad del Pacfico.

32
Basic Definitions

Many problems in linear algebra reduce to

a1,1 a1,2 a1,n x1 b1
a2,1 a2,2 a2,n x2 b2



. .. .. .. = .. (1)
..

.
. . . . . .


am,1 am,2 am,n xn bm
| {z } | {z } | {z }
A x b

where A is a matrix of coefficients ai,j R and b is a vector of

constants bi R, for i = 1, 2, . . . , m and j = 1, 2, . . . , m.

33
Note that we can write (1) as
X X
ai,j xj = bi or xj Aj = b,
jIn jIn

where A` Rm denotes the `-th column of A and i = 1, 2, . . . , n.

Linear systems can be classified in homogeneous (if b = 0) or
nonhomogeneous (if b 6= 0).

34

$$

  
 9
#

D  
#
  
D



#

 f 


#

 P 









n -  # D &

#

 D   #
 
  
  


( 

5
 (

  
  #



Linear systems can (also) be classified as
  
+  

 


 


 

 



  
(   &
 
&

/SQm .$

)dQYM[cMLm H[Lm +^MOKSM[cm7HcaSKMbm ^NmHm =jbcMYm

G






   
(& 
  

 



5

35
Theorem 3.1

Any system L of linear equations as in (1) has either

1 a unique solution
2 no solution
3 an infinite number of solutions

36
-*& (/7*!7$) -7
&" - 7

+. ] "> {&W-6,%#& 7&J %-# =9

'+ '+ '+

+ +

&+

! + &+
'+* +
e ! + &+ '+*+ ! + &+ '+*++
+ &+'+*+  + + '+*
e + &+ '+*+
+ +

/SQm .+

* "e$A$
e$$%


Bbb nb ~qb Zb ZZ~~b~ W@qm 5
Pnq __ nb nb ~qb nZb nb Zb ~b ^
`qfbbA qb_b nb

37
Ws #] {&W-6,%#& 7&J %-# <

*

*
*
*

 #(* &!('! *   '* ($*!*&!('! &*

*

   *

*
*
*
)*

+
!* &!('! &*

/SQm ..

7HcaSim -`dHcS^[m ^NmHm =`dHaMm =jbcMYm ^Nm6S[MHam-`dHcS^[bm

38
Solution of Linear Systems

Definition 3.1 (Echelon form)

A matrix is said to be in echelon form if

1 all zero rows, if any, are at the bottom of the matrix.

2 each leading non-zero entry in a row (pivot) is to the right of the
leading non-zero entry in the preceding row.

39
Example 3.1

The following matrices are in echelon form and their pivots are in red

2 3 2 0 4 5 6
1 2 3
0 0 1 1 3 2 0
A = , B= 0 0 1


0 0 0 0 0 6 2
0 0 0
0 0 0 0 0 0 0

0 1 3 0 0 4
C = 0 0 0 1 0 3 .

0 0 0 0 1 2

40
Definition 3.2 (Row Canonical form)
A matrix is said to be in row canonical form if it is in echelon form and

1 each pivot entry is one.

2 each pivot is the only non-zero entry in its column.

41
Example 3.2
The matrices from example 3.1 can be written in row canonical form
after applying a sequence of row operations.

1 3/2 0 1 5 0 19/6
1 2 0
0 0 1 1 3 0 2/3
A = , B= 0 0 1


0 0 0 0 0 1 1/3
0 0 0
0 0 0 0 0 0 0

0 1 3 0 0 4
C = 0 0 0 1 0 3 .

0 0 0 0 1 2

42
Consider the augmented matrix M = [A b], with A and b as in (1). It
can be shown that the following row operations preserve the solution of
the system:

1 row interchange: M i, M j,
2 row scaling: kM i, M i,
3 row addition: kM i, + M j M j, ,

where reads interchanges and reads replaces.

Theorem 3.2
Every matrix A is row eq. to some matrix in echelon form, and is row eq.
to a unique matrix in row canonical form.

43
Definition 3.3 (Rank)
The rank of a matrix A denoted rank(A) is equal to the number of pivots
in an echelon form of A.

44
Example 3.3
Find the rank for matrices in example 3.1

2 3 2 0 4 5 6
1 2 3
0 0 1 1 3 2 0
A = , B= 0 0 1


0 0 0 0 0 6 2
0 0 0
0 0 0 0 0 0 0

0 1 3 0 0 4
C = 0 0 0 1 0 3 , D = [B C ].

0 0 0 0 1 2

Trivially, rank(A) = 3, rank(B) = 2, rank(C ) = 3 and rank(D) = 3.

45
Properties (rank):

Let A be some m n matrix

rank(A) = rank(AT )
rank(A) min{m, n}
If rank(A) = min{m, n} we say A is full rank

46
Gauian Elimination

Gauian elimination is an algorithm that takes any matrix (as input) and
returns an its row canonical form (as output). It uses:

1 Forward Elimination: takes M and returns the echelon form of M

2 Backward Elimination: takes the echelon form of M and returns the
row canonical form of M

47
In fact, solving Ax = b is equivalent to finding the row canonical form of
M = [A b]. The justification follows from these facts:

1 any elementary row operation on M is equivalent to applying the

corresponding operation on the system itself.
2 the system has a solution iff the echelon form of the augmented
matrix does not have a row of the form (0, . . . , 0, bi ) with bi 6= 0.
3 in the row canonical form of M (excluding zero rows) the coefficient
of each basic variable is a pivot and it is equal to one, and it is the
only non-zero entry in its respective column; hence the free variable
form of the solution of the system of linear equations is obtained by
simply transferring the free variables to the other side.

48
Forward Elimination

Step 1 1 find the first column with a non-zero entry. Call it j1

2 interchange rows so that a1,j 6= 0
3 use a1,j1 as pivot to obtain zeros below a1,j1
ai,j1
1 set m = a1,j
1
2 for i > 1 do M i, mM 1, + M i,
Step 2 repeat step 1 with the submatrix formed by all the rows
excluding the first row. Let j2 denote the first column in
the subsystem with a non-zero entry. Hence a2,j2 6= 0
Step 3 to r repeat step 1 until the remaining submatrix has only zero
rows.

Note that in the resulting echelon form matrix, the pivots will be
a1,j1 , . . . , ar ,jr , where r is the rank of M.

49
Backward Elimination

Step 1 1 use row scaling so that the last pivot is one,

1
ar ,jr M r , M r ,
2 use ar ,jr = 1 to obtain zeroes above the last pivot,
ai,jr M r , + M i, M i,
Step 2 repeat step 1 for M r 1, , . . . , M 2,
Step r use row scaling so that the pivot in the first row is one.

50
 Cnb_Zq_Z~c cnb Zmbb`Zq>
b_~`qmbnb _bg_qbcbZ
^Zq_ ZqZ^~bq Z q b bZ~  Z`q q nb ~b b q q bb_qb _~
nb_bnbjbbZqZ^~bc cnb ~qcnb b c~qbZbZqq^Zqb`^ q
Zcbqm nb jbbZqZ^~b nb nb q`b
Exampleq~~Zb`
Pnq_bq 3.4 ^b~
Solve the following system
&!"%$ 0,2 W~lleitmtl m~~us l4

b'  !1 '2 5 x1 + xb ' 2x

2 
3 +!
4x1 '"
4 = ,5 / ' !: ' Y  (2)
"
!/b'!/ "/1 ' " !/b'"/'"/1  " !/ ' 5:  Y  ,
2x2 3x3 +
"/b'"/ ,/1  !/  " 2x1 +5/b'/' ,/1x'
4 = 53 "/ !: Y  5
! 3x1 + 3x2 4x3
6
2x4 = 1 5

 
f HB C{ f }D{ f Nn HE{
! 7



 *w 


 

 

?
, !
w

" " , ! "   !  " ,  " ,     

Hence the system has infinite solutions, with free variables x2 , x4 ; and pivot
variables x1 , x3 .

51
 "> {&W-6,%#& 7&J %-#
Example 3.5
Solve the following system
7



 
 1



;
n



 

 
2 2x3 + 3x4 M =
! v x\51 d+x!W 4 (3)
M q  MG
 q  !W ! MG v \5d
59 !2xB5
1 d+3x 2 + 3x3 x4 M9 =
!B  !B
3 B5d

Z
 


-

 Mq M9 

V

MG Md 

n
5x1 + 7x2 + 4x3 + x4 = 5

( "
V



f f E f
6



 *w 


 

?
  $ " 2   $ $ "
w  $ " "   "   B  B !B
- B 2  -  $ 2   2  5   





9

 w  




 

1

 
1


9

1
 



 <*






;
Hence the system has no solution.
\M q \MGIt\M9
contains
\Mdadegenerate
- equation.
  
 
1



m <
7



 *w 


 

 

?

$
$ $  $ 
e
-   " ! v \   " 52
 ( " E f
f f




 *w 


 

?
  $ " 2   $ $ "
w $ " 3.6"   "
Example  
B 
B !B
2 system
Solve-theB following -  $ 2   2  5   




9

 w  




 

1





9

1
 



 <*






x1 + 2x2 + 1x3 = 3 (4)
\M
2xq1 \M 1x3\M
+ 5xG2 \M9 4
=d  -
 
 
1


3x1 2x2 1x3 = 5

m <



 *w 


 

 

?

 $   Z 
$ $  $ 
e
-   " ! v \   "

D  D   $   m <
$   0 2 2   $0 !0 2
$  $   
"  
   

1

;

 M $ =      " 
;


1

  $ 

  



  w 

1 
   

 ;
 
 

Hence the system has a unique solution.
8
V1


cS^[m c^m -iSbcM[KMm H[LmB[S`dM[Mbbm >RM^aMYbm 53

Existence and Uniqueness

Theorem 3.3
Consider a system of equations with n unknowns s.t.: M = [A b], then

1 the system has a solution iff rank(A) = rank(M)

2 the solution is unique iff rank(A) = rank(M) = n

Theorem 3.4
The square system Ax = b has a unique solution iff A is invertible. In
such cases x = A1 b is the unique solution of the system.

54
Theorem 3.5
The following propositions are equivalent:

det(A) 6= 0
A is invertible
A is full rank
the columns of A are linearly independent
the rows of A are linearly independent
Ax = 0 has unique solution at x = 0

55
Vector Spaces
Definition

Definition 4.1 (Vector space)

Let V be a set closed under:

Vector addition: if a, b V, then a + b V

Scalar multiplication: if a V, k R, then ka V,

then V is called a vector space if for k, R and a, b, w V:

1 (a + b) + w = a + (b + w ) 4 a+b =b+a
2 0 V s.t. b + 0 = b, for 5 k(b + w ) = kb + kw
each b V 6 (k + )b = kb + b
3 For each b V, b V s.t. 7 (k)b = k(b)
b + (b) = 0
8 1a = a

56
Example 4.1 (Vector spaces)
The following are vector spaces:

Rn : space of n-dimensional vectors

Rmn : space of m n dimensional matrices
Pn (x): the space of polynomials of degree n, i.e.
( s
)
X
i
Pn (x) = p(x) = ai x , ai R : s n
i=0

57
Example 4.2 (Vector spaces in Rn )

For the following sets

V = {x Rn , a Rn : a T x = 0}
V = {x Rn , a Rn , 6= 0 : a T x = }

Show that V is a vector space, while V is not.

58
Linear Combinations

Definition 4.2 (Linear combination)

Let V be a vector space, a vector b is a linear combination (lc) of vectors
a 1 , . . . , a m V if there exist scalars x1 , . . . , xm s.t.
m
X
b = x1 a 1 + + xm a m = xi a i
i=1

Definition 4.3 (Linear combination)

We say b is a linear combination of a 1 , . . . , a m V if there is a solution
to the equation b = x1 a 1 + + xm a m , where xi are unknown scalars.

59
Remark 4.1
The question of expressing a given vector b Rn as a lc of
a . . . , a m Rn is equivalent to the question of solving Ax = b.

Such a system may have

unique solution
many solutions
no solution.

The no-solution case means that b cannot be written as lc of the as.

60
Example 4.3 (Linear combinations in R3 )
Express b = (3, 7, 4)T as a lc of

a 1 = (1, 2, 3)T , a 2 = (2, 3, 7)T and a 3 = (3, 5, 6)T

The augmented matrix for Ax = b reads

1 2 3 3 1 0 0 2
M = 2 3 5 7 0 1 0 4

3 7 6 4 0 0 1 3

Gauian elimination leads to: b = 2a 1 4a 2 + 3a 3 .

61
Example 4.4 (Linear combinations in Pn (x))
Express the polynomial q(x) = 3x 2 + 5x 5 as a lc of

p1 (x) = x 2 + 2x + 1, p2 (x) = 2x 2 + 5x + 4 and p3 (x) = x 2 + 3x + 6

The augmented matrix for Ax = b reads

1 2 1 3 1 0 0 3
M = 2 5 3 5 0 1 0 1

1 4 6 5 0 0 1 2

Gauian elimination leads to: q(x) = 3p1 (x) + p2 (x) 2p3 (x).

62
Spanning Sets

Definition 4.4 (Spanning Set)

Let V be a vector space. Vectors a 1 , . . . , a m V are said to be a
spanning set (ss) of V if

for every b V, x R : b = x1 a 1 + + xm a m

Remark 4.2
Suppose a 1 , . . . , a m are a ss of V. Then it holds that:

For any vector w , the set w , a 1 , . . . , a m also spans V

If a k , k m, is lc of some as. Then the as wo a k also span V
If one of the as is the zero vector, then the as wo it also span V

63
Example 4.5 (Spanning set of R3 )

1 e 1 = (1, 0, 0)T , e 2 = (0, 1, 0)T and e 3 = (0, 0, 1)T are a ss for R3 .

2 d 1 = (1, 0, 0)T , d 2 = (1, 1, 0)T and d 3 = (1, 1, 1)T are a ss for R3 .
3 u 1 = (1, 2, 3)T , u 2 = (1, 3, 5)T and u 3 = (1, 5, 9)T are not a ss for
a = (2, 7, 8)T .

64
Example 4.6 (Spanning set of Pn (x))
1 Every polynomial in Pn (t) can be expressed as a lc of n + 1
polynomials of degree n

1, x, x 2, x 3, . . . , x n

Thus these monomials (powers of x), are a ss of Pn (x) .

2 For any scalar c R, the following n + 1 powers of (x c)

1, (x c), (x c)2 , (x c)3 , . . . , (x c)n

are also a ss of Pn (x).

65
Example 4.7 (Spanning set of R22 )
Show that the matrices
" # " # " # " #
1 0 0 1 0 0 0 0
E1 = , E1 = , E1 = , and E 1 = ,
0 0 0 0 1 0 0 1

are a spanning set for Rmn .

66
Subspaces

Definition 4.5 (Subspace)

Let W V. Then W is a subspace of V if it is itself a vector space.
Formally, one would need to show that W V and that the conditions in
definition 4.1 hold. Eq., simple criteria for identifying subspaces follow:
Theorem 4.1
Let W V. Then W is a subspace of V if:

1 The zero vector belongs to W.

2 For every a, b W and , R it holds that a + b W.

Note that any vector space has always two trivial subspaces, i.e.
V, 0 V and V t 0 = V.

67
Example 4.8 (Subspaces of R3 )

1 Show that set U R3

U = {(x1 , x2 , x3 ) : x1 = x2 = x3 , xi R}

is a subspace of R3 .
2 Show that any plane that goes through the origin in R3 is a
subspace of R3 .

68
   4Y  
< m
 /
 M
$

<m   

3.Dv e








 M
  
3

 )

 Gm 
 ) $





M` 
 3 .Dv e
  )$ 

 





Gm   M
<mm

2
2

m
mm
m

mm
mm
mm
'+ m '+
  mm
m
-
-
RRR
RRR

+ +

/SQm 2$

#&!"%$ 6:

: /
 %A
7 



?   /
 M( 






 


Mk

 


$
? ?

 M( 

M(
T
 ?(

M(  

 
 (   
 

    
  
 


 

 



  

$ Mk 
b 69
Example 4.9 (Subspaces in Rn )
Show that

W = {x Rn , a, b Rn : a T x = 0, b T x = 0},

is a vector subspace of V, as defined in example 4.2.

70
Example 4.10 (Subspaces of Rnn )
Let V = Rnn ,

1 Show that W V is a subspace of V, where W is the set of all

upper triangular matrices n n.
2 Show that W V is a subspace of V, where W is the set of all
symmetric matrices n n.

71
Example 4.11 (Subspaces of P(x))
Let P(x) represent the space of all polynomials, then

1 Show that Pn (x), is a subspace of P(x), where Pn (x) denotes the

space of polynomials of degree at most n.
2 Show that Q(x) is a subspace of P(x), where Q(x) denotes the
space of polynomials with only even powers of x.

72
Theorem 4.2 (Intersection of subspaces)
The intersection of any number of subspaces of a vector space V is a
subspace of V.

Proof.
Without loss of generality, let U and W be subspaces of vector space V.
Hence, 0 U, 0 W and 0 U W. Now suppose a, b U W.
Then a, b U and a, b W. Further, since U and W are subspaces, for
any , R, a + b U and a + b W. Thus a + b U W.
Therefore U W is a subspace of V. 

73
Definition 4.6 (Nullspace of a Matrix)
Let A be a m n matrix, the Nullspace of matrix A, denoted null(A) is
the solution set of Ax = 0.
Note that null(A) Rn is a subspace of Rn since

1 0n null(A). Namely, A0n = 0m .

2 a + b null(A) for any a, b null(A) and , R. Namely,
A(a + b) = (Aa) + (Ab) = 0m .

74
Linear span

Definition 4.7 (Linear span)

Let a 1 , . . . , a m V. The collection of all lc of such vectors, denoted by

span(a i ),

is called linear span of a 1 . . . , a m .

Moreover, span(a i ) is a subspace of V since, in general, span(a i ) V,

1 0a 1 + 0a 2 + + 0a m = 0 (span)(a i )
2 If a, b span(ai ),

a = x1 a 1 + x2 a 2 + + xm a m
b = y1 a 1 + y2 a 2 + + ym a m ,

then for , R

(x1 + y1 )a 1 + + (xm + ym )a m = a + b span(a i )

75
Example 4.12 (Linear span in R3 )
Consider vector space V = R3 ,

1 Let u 6= 0, u V. Then span(u) consists of all scalar multiples of u.

Geometrically span(u) is the line through the origin O and the end
point u.
2 Let u, a V that are not multiples of each other. Then span(u, a)
is the plane through the origin O and the end points u and v .
3 Consider e 1 , e 2 , e 3 . Example 4.5 showed that e 1 , e 2 , e 3 form a
spanning set of R3 . Accordingly span(e i ) = R3 .

76
77
Definition 4.8 (Range of a matrix)
Let A be a m n matrix, the range of matrix A, denoted range(A) is the
space spanned by the columns of A, i.e. rank(A) = span(Ai ).
Note that range(A) Rm is a subspace of Rm since

1 0m range(A). Namely, y = A0n = 0m .

2 a + b range(A) for any a, b range(A) and , R.

y 1 = Aa y 1 = y 1 = Aa
y 2 = Ab y 2 = y 2 = Ab

Hence, y = y 1 + y 2 = A(a + b) range(A).

Notation: the range of A is also called directly the column space of

A, i.e. range(A) = colsp(A).

78
Linear Dependence and Independence

Definition 4.9 (Linear dependence)

a 1 , . . . , a m V are linearly dependent if there exist scalars x1 , . . . , xm ,
not all of them 0, such that

x1 a 1 + + xm a m = 0.

Otherwise we say the vectors are linearly independent.

79
Remark 4.3
1 Suppose 0 is one of the vectors a 1 , . . . , a m , say a j = 0 then the
vectors must be ld since

6= 0 : 0a 1 + 0a 2 + + 0a j1 + a j + 0a j+1 + + 0a m = 0

2 Let a 6= 0, then a by itself is li.

3 Let a i = a j , then the vectors must be ld. Without loss of
generality, let i = 1, j = 2 and note that

1a 1 + ()a 2 + 0a 3 + + 0a m = 0

4 Two vectors are ld iff one is a multiple of the other.

5 If {a 1 , a 2 , . . . , a m } is a li set, then any rearrangement of the vectors
is li as well.
6 If a set S of vectors is li, then any W V is li as well.

80
Example 4.13 (Linear independence)
1 Show that the vectors

u = (1, 1, 0)T , a = (1, 3, 2)T and w = (4, 9, 5)T

do not form a li set.

2 Show that

u = (1, 2, 3)T , a = (2, 5, 7)T and w = (1, 3, 5)T

are li.
3 Let V be the vector space of functions fi : R R. Show that the
functions f1 (x) = sin(x), f2 (x) = e x and f3 (x) = x 2 are li.
4 Show that every set a 1 , . . . , a m of mutually orthogonal vectors, i.e.
ha i , a j i = 0 for i 6= j, is li.

81
Linear dependence in R3 :

1 If a 1 , a 2 R3 lie in the same line O, then they are ld.

2 If a 1 , a 2 , a 3 R3 lie on a plane through the origin, then they are ld.
3 If a 1 , a 2 , a 3 R2 , then they are ld.

More generally, a set of m vectors in Rn is, necessarily ld if m > n.

82
83
Linear dependence and linear combinations:

Both notions are closely related.

1 Assume a k is a lc of the other vectors in a 1 . . . , a m

ak = x1 a 1 + x2 a 2 + + xk1 a k1 + xk+1 a k+1 + + xm a m

0 = x1 a 1 + x2 a 2 + + xk1 a k1 + (1)a k + xk+1 a k+1 + + xm a m

implying that the vectors are ld.

2 Assume the vectors a 1 , . . . , a m are ld

y1 a 1 + y2 a 2 + + ym a m = 0, for some yk 6= 0
ak = yk1 y1 a 1 + + yk1 yk1 a k1 + yk1 yk+1 a k+1 + yk1 ym a m ,

implying that there is one vector that is a lc of the others

84
Linear dependence and echelon matrices:

Consider echelon matrix A, with pivots in red, and rows r `

0 2 3 4 5 6 7
0 0 4 3 2 3 4

A= 0 0 0 0 7 8 9


0 0 0 0 0 6 7
0 0 0 0 0 0 0

r1 cannot be expressed as a lc of r2 , r3 , r4
The nonzero rows of a matrix in echelon form are linearly
independent.

85
Theorem 4.3
Let A be a m n matrix, with columns A1 , . . . , Am Rm , then if

m < n, the cols of A are ld

m = n, the cols of A are li iff det(A) 6= 0
m > n, the cols of A are li iff rank(A) = n

86
Basis and Dimension

Definition 4.10 (Basis)

A set S = {a 1 , . . . , a n } is a basis of V if S is li and S spans V.

Definition 4.11 (Basis)

A set S = {a 1 , . . . , a n } is a basis of V if every b V can be written

uniquely as a lc of a 1 , . . . , a n .

87
Theorem 4.4
Definitions 4.10 and 4.11 are equivalent.

Proof.
Consider the statements: [1] S = {a 1 , . . . , a n } is li and S spans V; and
[2] every b V can be written uniquely as a lc of a 1 , . . . , a n

Suppose [1] holds, then b = x1 a 1 + + xn a n and

b = y1 a 1 + + yn a n , hence

0 = (x1 y1 )a 1 + + (xn yn )a n ,

but since {a 1 , . . . , a n } is a li set, the last equality only holds for

xi = yi . Thus [1] implies [2].
Suppose [2] holds, then S spans V. Now assume
zi 6= 0 : 0 = z1 a 1 + + zn a n , but by [2] the representation
0 = 0a 1 + + 0a n is unique. Thus [2] implies [1].


88
Special cases:

Definition 4.12 (Orthogonal basis in Rn )

A basis S = a 1 , . . . , a n is orthogonal if ha i , a j i = 0 for i 6= j

Definition 4.13 (Orthonormal basis in Rn )

A basis S = a 1 , . . . , a n is orthonormal if ha i , a j i = ij

89
Example 4.14 (Orthogonal basis)
Show that the set

a 1 = (1, 1, 0)T , a 2 = (1, 1, 2)T , and a 3 = (1, 1, 1)T ,

form an orthogonal basis in R3 .

90
Lemma 4.1 (Steinitz)

Suppose {a 1 , . . . , a n } spans V, and suppose {b 1 , . . . , b m } is li. Then

m n, and V is spanned by a set of the form:

{b 1 , . . . , b m , a `1 , . . . , a `nm },

where, a `i is used to indicate that vectors a i can be in a different order.

91
Theorem 4.5
Let V be a vector space such that one basis has m elements and another
basis has n elements. Then m = n.

Proof.
Suppose {a 1 , . . . , a n } and {b 1 , . . . } are two bases of V. By lemma 4.1,
because {a i } spans V, then {b i } must contain n or less elements,
otherwise the vectors would be ld. If {b i } contains less than n elements,
then {a i } would be ld. Thus the cardinality of {b i } is exactly n. 

92
Definition 4.14 (Dimension of a vector space)
Let S = {a 1 , . . . , a n } be a basis of V. The dimension of V, denoted
dim(V), is the number of elements in the basis, i.e. dim(V) = #S = n.

The vector space {0} is defined to have dimension 0.

Suppose V does not have a finite basis, then V is said to be of
infinite dimension.

93
Example 4.15 (Rn basis)
Consider the following vectors in Rn

e 1 = (1, 0, . . . , 0)T , e 2 = (0, 1, . . . , 0)T , . . . , e n = (0, 0, . . . , 1)T .

These vectors are li and span Rn . Equivalently, any vector b Rn is a lc

of the above vectors:

b = a1 e 1 + a2 e 2 + + an e n .

Accordingly the vectors form a basis in Rn called the standard basis of

Rn . Thus Rn has dimension n.

94
Example 4.16 (Rmn basis)
The following matrices form a basis for the vector space R23 :
" # " # " #
1 0 0 0 1 0 0 0 1
, ,
0 0 0 0 0 0 0 0 0
" # " # " #
0 0 0 0 0 0 0 0 0
, , .
1 0 0 0 1 0 0 0 1

More generally, in the vector space Rmn of all m n matrices, let E ij

denote the matrix with the (i, j)-entry equal to 1 and 0s elsewhere. All
such matrices form a basis of Rmn called the standard basis of Rmn

95
Example 4.17 (Polynomial basis)
1 Consider Pn (x) and the set

S = {1, x, x 2 , . . . , x n }

of n + 1 monomials is a basis of Pn (x). In particular, any polynomial

of degree n can be expressed uniquely as a lc of the elements in
the basis. Therefore dim(Pn (x)) = n + 1.
2 Consider P(x), and the set

S = {f1 (x), f2 (x), . . . , fm (x)},

where f` denotes a polynomial of degree `. Then any polynomial of

degree > m cannot be written as a lc of the elements in S, thus S is
not a basis of P(x). In fact dim(P(x)) = .

96
Theorems on bases

Theorem 4.6

Let V be a vector space of finite dimension n. Then:

1 Any set of n + 1 vectors (or more) in V are ld

2 Any li set A = {a i }ni=1 with n elements is a basis of V
3 Any spanning set S = {a i }ni=1 of V with n elements is a basis of V

Proof.
Suppose B = {b 1 , . . . , b n } is a basis of V.

1 Because B spans V, any n + 1 vectors or more are ld.

2 Since elements from B can be adjoined to A to form a spanning set
of V with n elements. Because A has already n elements, A itself is
a spanning set of V. Thus S is a basis of V.
3 Suppose S is ld. Then S \ a k is ss of V with n 1 elements. But B
has n elements. Thus S must be li, and it is a basis of V.
97
Theorem 4.7

Suppose S spans a vector space V, then:

1 Any maximum number of li vectors in S form a basis of V

2 Suppose one deletes from S every vector that is a lc of preceding
vectors in S. Then the remaining vectors form a basis of V

Proof.
1 Suppose {a i }ni=1 is a maximum li subset of S, and suppose b S.
Accordingly {a 1 , . . . , a n , b} is ld because b span(a i ) and hence
S span(a i ). This leads to V = span(S) span(a i ) . Thus li set
{a}ni=1 spans V and hence it is a basis of V.
2 The remaining vectors form a maximum li subset of S, hence by [1],
it is a basis of V.

98
Theorem 4.8

Let V be a vector space of finite dimension and let S = {a 1 , . . . , a r } be a

set of linearly independent vectors in V, then S is part of a basis in V;
that is, S may be extended to a basis of V.

Proof.
Suppose B = {b i }ni=1 is a basis of V. Note that V is also spanned by

S B = {a 1 , . . . , a r , b 1 , . . . , b n }

By theorem 4.7, we can delete each vector that is a lc of the preceding

vectors to obtain a basis B 0 of V. Because S is li, no a i is a lc of the
preceding vectors. Thus B 0 contains every vector in S, and S is part of
the basis B 0 of V. 

99
Dimensions and subspaces:

The following theorem gives the basic relation between the dimension of
a vector space and the dimension of a subspace
Theorem 4.9

Let W be a subspace of an n-dimensional vector space V, then

dim(W) n. In particular if dim(W) = n, then W = V.

100
Example 4.18 (Dimension of a subspace)
Let W be a subspace of R3 . Note that dim(R3 ) = 3. Theorem 4.9 tells
us that dim(W) can only be 0, 1, 2 or 3. The following cases apply:

1 if dim(W) = 0, then W = {0}, is a point.

2 if dim(W) = 1, then W is a line that passes through the origin 0.
3 if dim(W) = 2, then W is a plane that passes through the origin 0.
4 if dim(W) = 3, W is the entire space R3 .

101
Example 4.19

1 Let M R22 be a vector subspace

M = {M R22 : M = M T }.

what is the dimension of M?

2 Let M R33 be a vector subspace

M = {M R33 : M = M T }.

what is the dimension of M?

102
Applications to Matrices, Rank of a Matrix

Let A be a m n matrix, and A` Rn denote its columns. Denote

colsp(A) the subspace of Rm spanned by the columns of A.
Definition 4.15 (Rank)
The rank of a matrix, written rank(A) is equal to the maximum number
of li cols in A, or equivalently, the dimension of the column space of A

rank(A) = dim(colsp(A))

Similarly, rowsp(A) is the subspace of Rn spanned by the rows of A.

103
Theorem 4.10

The maximum number of li cols in any A is equal to the maximum

number of li rows in A. Thus the dimension of the column space of A
equals the dimension of the row space of A. Hence

rank(A) = dim(colsp(A)) = dim(rowsp(A))

104
Application to finding a basis for W = span(u 1 , . . . , u r ):

Frequently we are given a list of vectors S = {u 1 , . . . , u r }, u i Rn and

we want to find a basis for the subspace W of Rn spanned by the given
vectors, that is a basis of

W = span(S) = span(u 1 , . . . , u r )

One method to accomplish this goal is the casting-out algorithm

105
Algorithm 4.1 (Casting-out algorithm)
1 Form matrix M, whose columns are the given vectors
2 Row reduce M to echelon form M
3 For each column M k without a pivot, delete (cast-out) the vector
u k from the list S of given vectors.
4 Output the remaining vectors in S (which correspond to columns
with pivots).

106
Example 4.20
Let W be a subspace of R5 spanned by

u 1 = (1, 2, 1, 3, 2)T , u 2 = (1, 3, 3, 5, 3)T , u 3 = (3, 8, 7, 13, 8)T

u 4 = (1, 4, 6, 9, 7)T and u 5 = (5, 13, 13, 25, 19)T .

Find a basis for W consisting of the original given vectors and find
dim(W).

107
Example 4.21
Let W be a subspace of R4 spanned by

u 1 = (1, 2, 5, 3)T , u 2 = (2, 3, 1, 4)T , u 3 = (3, 8, 3, 5)T

1 Find a basis and dimension of W.

2 Extend the basis of W to a basis of R4 .

108
Application to homogeneous systems of linear equations:

Consider Ax = 0, for A a m n matrix. We know that the solution space

W of the system is a subspace of Rn , and hence W has a dimension.
Theorem 4.11
The dimension of the solution space W of an homogeneous system
Ax = 0 is given by n r , where n is the number of unknowns, and r is
the rank of A.

dim(W) = n rank(A)

109
Coordinates

Consider vector space V, and basis A = {ai }ni=1 . For any b V we have

b = x1 a 1 + x2 a 2 + + xn a n ,

where b V is expressed relative to basis A in terms of its coordinates

xi . Thus

[b]A = (x1 , x2 , . . . , xn )T

is called the coordinate vector of b relative to basis A.

110
Example 4.22 (PC1 2015-II)
Consider the following vectors in R4 :

b 1 = (1, 0, 1, 0)T , b 2 = (1, 0, 0, 1)T , b 3 = (1, 1, 1, 1)T , b 4 = (1, 1, 1, 1)T ,

and let A = {x R4 : x1 = x2 + x3 + x4 } be a subspace of R4

Find = s.t. {b 1 , b 2 , b 3 , b 4 } spans A

Is {b 1 , b 2 , b 3 , b 4 } a basis of A given ?
Find a basis of subspace A and compute dim(A)

111