MATH1550

Lecture 15: Basis

Last updated: October 31, 2018
Warning: the note is for reference only. It may contain typos. Read at your own risk.
The lecture is based on
Beezer, A first course in Linear algebra. Ver 3.5
Downloadable at [Link]
The print version can be downloaded at
[Link]

Textbook Reading:
Beezer, Ver 3.5 Section B (print version p233-238), Section D (print version p245-253)

Exercise
Exercises with solutions can be downloaded at
[Link]
Section B and Section D

1 Basis
Definition 1 Let V be a vector space. Then a subset S of V is said to be a basis for
V if
1. S is linearly independent.
2. hSi = V , i.e. S spans V .
Remark: Most of the time V is a subspace of Rm . Occasionally V is assumed to be a
subspace of Mmn or Pn . It does not hurt to assume V is a subspace of Rm .
Example 1 Let V = Rm , then B = {e1 , . . . , em } is a basis for V . (recall all the entries
of ei is zero, except the i-th entry being 1). It is called the standard basis:
Obviously B is linearly independent.
Also, for any v ∈ V , v = [v]1 e1 + · · · + [v]m em ∈ hBi. So hBi = V . 
2
Example 2 A vector   can have different bases. Example for V = R , S = {e1 , e2 }
 space
1 1
is a basis and S 0 = { , } is also a basis. 
0 1

2 Bases for spans of column vectors

Let S = {v1 , . . . , vn } be a subset of Rm Recall from lecture 14, that there are several
methods to find a subset T ⊆ S. Such that (i) T is linearly independent (ii) hT i = hSi.
So T is a basis for hSi.
Method 1
RREF
Let A = [v1 | · · · |vn ] −−−→ B. Suppose D = {d1 , . . . , dr } be the indexes of the pivot
columns of B. Let T = {vd1 , . . . , vdr }. Then T is a basis for hSi = C(A)

Method 2
RREF
Let A = [v1 | · · · |vn ]. Suppose At −−−→ B. Let T be the nonzero columns of B t . Then

1
T is a basis for hSi = C(A)

This is an example from Lecture 14.

Example 3 Column space from row operations
Let
             
1 4 0 −1 0 7 −9
2 8 −1 3 9 −13 7
 0  , v2 =  0  , v3 =  2  , v4 = −3 , v5 = −4 , v6 =  12  , v7 = −8}.
S = {v1 =              
−1 −4 2 4 8 −31 37

Find a basis for hSi.

 
1 4 0 −1 0 7 −9
2 8 −1 3 9 −13 7 
A = [v1 | · · · |v7 ] =  .
0 0 2 −3 −4 12 −8
−1 −4 2 4 8 −31 37
Method 1  
1 4 0 0 2 1 −3
RREF  0 0 1 0 1 −3 5 
A −−−→  
0 0 0 1 2 −6 6 
0 0 0 0 0 0 0
Let      
1 0 −1
 2  −1  3 
 0  ,  2  , −3}.
T = {v1 , v3 , v4 } = {     
−1 2 4
Then T is a basis for hSi = C(A).
Method 2 The transpose of A is
1 2 0 −1
 
4 8 0 −4 
 0 −1 2 2 
 
−1 3 −3 4  .
 
0
 9 −4 8  
 7 −13 12 −31
−9 7 −8 37
Row-reduced this becomes,
 
1 0 0 − 31
7
0 12
 1 0 7


0 13
 0 1 7


D=
0 0 0 .
0 
0 0 0 0 
 
0 0 0 0 
0 0 0 0

2
 Then we can take      
1 0 0
 0  1 0
T = {
 0 ,
  ,
0
 }.
1
− 31
7
12
7
13
7

T is a basis for C(A) = hSi. 

We have the following theorem
Theorem 2 Let S be a finite subset of Rm . Then basis for hSi exists.
In fact, there exists a subset T of S such that T is a basis for hSi (see Lecture 10
Theorem 2 or Lecture 14 Theorem 3).

3 Bases and nonsingular matrices

Theorem 3 Suppose that A is a square matrix of size m. Then the columns of A is a
basis for Rm if and only if A is nonsingular.
Proof. If columns of A is linearly independent, LS(A, 0) has only trivial solution. Hence
by Lecture 5 Theorem 12, A is nonsingular.
Next suppose A is nonsingular. Let b ∈ Rm . Then LS(A, b) has solution for any
b ∈ Rm . Hence b ∈ C(A). So C(A) = Rm . 
   
0 1 1
Example 4 S = {v1 = , v2 = } is a basis for R2 .
0 1
Let  
1 1
A = [v1 |v2 ] =
0 1
is nonsingular. Then S 0 is a basis for R2 . 
Example 5  
−7 −6 −12
A= 5 5 7 .
1 0 4
Because A is nonsingular, so the columns of A is a basis for R3 . 

4 Dimension
Definition 4 (Dimension) Let V be a vector space. Suppose {v1 , . . . , vt } is a basis
for V . Then t is called the dimension of V and is denoted by t = dim V and V is called
a finite dimensional vector space.
Warning: We need to show that the dimension is well-defined, i.e., suppose both
{v1 , . . . , vt } and {u1 , . . . , us } are bases for V , then s = t.
Theorem 5 Suppose that S = {v1 , v2 , v3 , . . . , vt } is a finite set of vectors which spans
the vector space V . Then any set of t + 1 or more vectors from V is linearly dependent.

3
Proof. Skip the proof
We want to prove that any set of t + 1 or more vectors from V is linearly dependent. So
we will begin with a totally arbitrary set of vectors from V , R = {u1 , u2 , u3 , . . . , um },
where m > t. We will now construct a nontrivial relation of linear dependence on R.
Each vector u1 , u2 , u3 , . . . , um can be written as a linear combination of the vectors
v1 , v2 , v3 , . . . , vt since S is a spanning set of V . This means there exist scalars aij ,
1 ≤ i ≤ t, 1 ≤ j ≤ m, so that

u1 = a11 v1 + a21 v2 + a31 v3 + · · · + at1 vt

u2 = a12 v1 + a22 v2 + a32 v3 + · · · + at2 vt
u3 = a13 v1 + a23 v2 + a33 v3 + · · · + at3 vt
..
.
um = a1m v1 + a2m v2 + a3m v3 + · · · + atm vt
Now we form, unmotivated, the homogeneous system of t equations in the m variables,
x1 , x2 , x3 , . . . , xm , where the coefficients are the just-discovered scalars aij ,
a11 x1 + a12 x2 + a13 x3 + · · · + a1m xm =0
a21 x1 + a22 x2 + a23 x3 + · · · + a2m xm =0
a31 x1 + a32 x2 + a33 x3 + · · · + a3m xm =0
..
.
at1 x1 + at2 x2 + at3 x3 + · · · + atm xm =0

This is a homogeneous system with more variables than equations (our hypothesis
is expressed as m > t), so there are infinitely many solutions. Choose a nontrivial
solution and denote it by x1 = c1 , x2 = c2 , x3 = c3 , . . . , xm = cm . As a solution to the
homogeneous system, we then have
a11 c1 + a12 c2 + a13 c3 + · · · + a1m cm =0
a21 c1 + a22 c2 + a23 c3 + · · · + a2m cm =0
a31 c1 + a32 c2 + a33 c3 + · · · + a3m cm =0
..
.
at1 c1 + at2 c2 + at3 c3 + · · · + atm cm =0

As a collection of nontrivial scalars, c1 , c2 , c3 , . . . , cm will provide the nontrivial re-

4
lation of linear dependence we desire,
c1 u1 + c2 u2 + c3 u3 + · · · + cm um
= c1 (a11 v1 + a21 v2 + a31 v3 + · · · + at1 vt )
+ c2 (a12 v1 + a22 v2 + a32 v3 + · · · + at2 vt )
+ c3 (a13 v1 + a23 v2 + a33 v3 + · · · + at3 vt )
..
.
+ cm (a1m v1 + a2m v2 + a3m v3 + · · · + atm vt )
= c1 a11 v1 + c1 a21 v2 + c1 a31 v3 + · · · + c1 at1 vt
+ c2 a12 v1 + c2 a22 v2 + c2 a32 v3 + · · · + c2 at2 vt
+ c3 a13 v1 + c3 a23 v2 + c3 a33 v3 + · · · + c3 at3 vt
..
.
+ cm a1m v1 + cm a2m v2 + cm a3m v3 + · · · + cm atm vt
= (c1 a11 + c2 a12 + c3 a13 + · · · + cm a1m ) v1
+ (c1 a21 + c2 a22 + c3 a23 + · · · + cm a2m ) v2
+ (c1 a31 + c2 a32 + c3 a33 + · · · + cm a3m ) v3
..
.
+ (c1 at1 + c2 at2 + c3 at3 + · · · + cm atm ) vt
= (a11 c1 + a12 c2 + a13 c3 + · · · + a1m cm ) v1
+ (a21 c1 + a22 c2 + a23 c3 + · · · + a2m cm ) v2
+ (a31 c1 + a32 c2 + a33 c3 + · · · + a3m cm ) v3
..
.
+ (at1 c1 + at2 c2 + at3 c3 + · · · + atm cm ) vt
= 0v1 + 0v2 + 0v3 + · · · + 0vt
= 0 + 0 + 0 + ··· + 0
=0

That does it. R has been undeniably shown to be a linearly dependent set.


Theorem 6 Suppose that V is a vector space with a finite basis B and a second basis
C. Then B and C have the same size.

Proof. Denote the size of B by t. If C has ≥ t + 1 vectors, then by the previous theorem,
C is linearly dependent. Contradict to the fact that C is a basis. Denote the size of C
by s. So s ≤ t.
Because C is a basis, if t ≥ s + 1, then B is linearly dependent. Contradict to the fact
that B is a basis. Hence t ≤ s. So s = t. 
The above theorem shows that the dimension is well-defined. No matter which basis we
choose, the size is always the same.
Example 6 dim Rm = m. See example 1. 

5
Lemma 7 Let V be a vector space and v1 , . . . , vk , u ∈ V . Suppose S = {v1 , . . . , vk } is
/ hSi. Then S 0 = {v1 , . . . , vk , u} is linearly independent.
linearly independent and u ∈
Proof. Let the relation of linear dependence of S 0 be
α1 v1 + · · · + αk vk + αu = 0.
Suppose α 6= 0, then
α1 αk
u=− v1 − · · · − vk ∈ hSi .
α α
Contradiction. So α = 0, then
α1 v1 + · · · + αk vk = 0.
By the linear independence of S, αi = 0 for all i. Hence the above relation of dependence
of S 0 is trivial. 

Theorem 8 Let V be a subspace of Rm . There exists a basis for V .

Proof. Skip the proof
If V is the zero vector space, i.e. V = {0}. Then the theorem is trivial.
Suppose V is not the zero vector space, let v1 be a nonzero vector in V .
If V = h{v1 }i, we can take S = {v1 }. Then obviously {v1 } is linearly independent and
hence S is a basis for V . Otherwise, let v2 ∈ V but not in h{v1 }i. By the previous
lemma, {v1 , v2 } is linearly independent.
If V = h{v1 , v2 }i, we can take S = {v1 , v2 }. So S is a basis for V . Otherwise, let v3 ∈ V
but not in h{v1 , v2 }i. By the previous lemma, {v1 , v2 , v3 } is linearly independent.
Repeat the above process, inductive we can define vk+1 as following:
If V = h{v1 , v2 , . . . , vk }i, we can take S = {v1 , v2 , . . . , vk }. Because {v1 , v2 , . . . , vk } is
linearly independent, S is a basis for V . Otherwise defined vk+1 6∈ h{v1 , v2 , . . . , vk }i.
By the previous lemma, {v1 , v2 , . . . , vk+1 } is linearly independent.
If the process stops, say at step k, i.e., V = h{v1 , v2 , . . . , vk }i. Then we can take
S = {v1 , v2 , . . . , vk }. Because {v1 , v2 , . . . , vk } is linearly independent, it is a basis for
V . This completes the proof. Otherwise, the process continues infinitely, in particular,
we can take k = m + 1 and V 6= h{v1 , v2 , . . . , vm+1 }i and {v1 , v2 , . . . , vm+1 } is linearly
independent.
Because {e1 , . . . , em } is independent, by theorem 5 {v1 , v2 , . . . , vm+1 } is linearly de-
pendent. Contradiction. 

Proposition 9 Let S = {v1 , . . . , vn } ⊆ Rm . Then

dim hSi ≤ n.
Proof. By Theorem 2, there exists a subset T of S such that T is a basis for hSi.
dim hSi = number of vectors in T ≤ number of vectors in S = k.


Remark: both Theorem 2 and Proposition 9 is value if we replace Rm by Pn , Mmn

or any finite dimensional vector space.

6
5 Rank and nullity of a matrix
Definition 10 (Nullity of a matrix) Suppose that A ∈ Mmn . Then the nullity of A
is the dimension of the null space of A, n (A) = dim(N (A)).

Definition 11 (Rank of a matrix) Suppose that A ∈ Mmn . Then the rank of A is

the dimension of the column space of A, r (A) = dim(C(A)).

Example 7 Rank and nullity of a matrix Let us compute the rank and nullity of
2 −4 −1 3 2 1 −4
 
 1 −2 0 0 4 0 1
−2 4 1 0 −5 −4 −8
 
A=
 1 −2 1 1 6 1 −3

 2 −4 −1 1 4 −2 −1
−1 2 3 −1 6 3 −1
To do this, we will first row-reduce the matrix since that will help us determine bases
for the null space and column space.
 
1 −2 0 0 4 0 1
0
 0 1 0 3 0 −2 
0
 0 0 1 −1 0 −3 

0 0 0 0 0 1 1
 
0 0 0 0 0 0 0
0 0 0 0 0 0 0

From this row-equivalent matrix in reduced row-echelon form we record D = {1, 3, 4, 6}

and F = {2, 5, 7}.
By Lecture 14, Theorem 3, for each index in D, we can create a single basis vector.
In fact T = {A1 , A3 , A4 , A6 } is a basis for C(A). In total the basis will have 4 vectors,
so the column space of A will have dimension 4 and we write r (A) = 4.
Lecture 9 Section 3, for each index in F , we can create a single basis vector. In total
the basis will have 3 vectors, so the null space of A will have dimension 3 and we write
n (A) = 3. In fact
2 −4 −1
     
1  0   0 
0 −3  2 
     
R = {0 ,  1  ,  3 }
     
0  1   0 
     
0  0  −1
0 0 1
is a basis for N (A). 
RREF
Theorem 12 (Computing rank and nullity) Suppose A ∈ Mmn and A −−−→ B.
Let r denote the number of pivot columns (= number of nonzero rows). Then r (A) = r
and n (A) = n − r.
Proof. Let D = {d1 , . . . , dr } be the indexes of the pivot columns of B. By Lecture 10
Theorem 2 or Lecture 14 Theorem 3, {Ad1 , . . . , Adr } is a basis for C(A). So r (A) = r.

7
By Lecture 9 Sect 3, each free variable corresponding to a single basis vector for the null
space. So n (A) is the number of free variables = n − r. 

Corollary 13 (Dimension formula) Suppose A ∈ Mmn , then

r (A) + n (A) = n.
Theorem 14 Let A be a m × n matrix. Then
r (A) = r At .

Equivalently
dim C(A) = dim R(A) .
RREF
Proof. Let A −−−→ B. Let r denote the number of pivot columns (= number of nonzero
rows). Then by the above discussion r = r (A). By Lecture 14 Theorem 7, the first r
columns of B t form a basis for R(A). Hence r = r (At ). This completes the proof. 

Let us take a look at the rank and nullity of a square matrix.

Example 8 The matrix
0 4 −1 2 2 3 1
 
2 −2 1 −1 0 −4 −3
−2 −3 9 −3 9 −1 9 
 
E = −3 −4 9 4 −1 6 −2
 
−3 −4 6 −2 5 9 −4
 
9 −3 8 −2 −4 2 4
8 2 2 9 3 0 9
is row-equivalent to the matrix in reduced row-echelon form,
 
1 0 0 0 0 0 0
0 1 0 0 0 0 0
 
0 0 1 0 0 0 0
 
0 0 0 1 0 0 0
 
 
0 0 0 0 1 0 0
 
0 0 0 0 0 1 0
0 0 0 0 0 0 1
With n = 7 columns and r = 7 nonzero rows tells us the rank is r (E) = 7 and the
nullity is n (E) = 7 − 7 = 0. 
The value of either the nullity or the rank are enough to characterize a nonsingular
matrix.
Theorem 15 (Rank and Nullity of a Nonsingular Matrix) Suppose that A is a
square matrix of size n. The following are equivalent.
1. A is nonsingular.
2. The rank of A is n, r (A) = n.
3. The nullity of A is zero, n (A) = 0.

8
Proof. (1 ⇒ 2) If A is nonsingular then C(A) = Rn . If C(A) = Rn , then the column
space has dimension n, so the rank of A is n.
(2 ⇒ 3) Suppose r (A) = n. Then the dimension formula gives

n (A) = n − r (A)
=n−n
=0
(3 ⇒ 1) Suppose n (A) = 0, so a basis for the null space of A is the empty set. This
implies that N (A) = {0} and hence A is nonsingular. 

With a new equivalence for a nonsingular matrix, we can update our list of equiva-
lences which now becomes a list requiring double digits to number.
Theorem 16 Suppose that A is a square matrix of size n. The following are equivalent.
1. A is nonsingular.
2. A row-reduces to the identity matrix.
3. The null space of A contains only the zero vector, N (A) = {0}.
4. The linear system LS(A, b) has a unique solution for every possible choice of b.
5. The columns of A are a linearly independent set.
6. A is invertible.
7. The column space of A is Rn , C(A) = Rn .
8. The columns of A are a basis for Rn .
9. The rank of A is n, r (A) = n.
10. The nullity of A is zero, n (A) = 0.