Linear Algebra in Euclidean Space

Elisa Bellah

Last Updated: January 6, 2026

Contents

Preface vii

Chapter 1. Systems of Linear Equations 1

1.1. Introduction to Systems of Linear Equations 1
1.2. The Matrix Representation of a Linear System 3
1.3. Equivalent Systems and Elementary Row Operations 5
1.4. Echelon Forms of a Matrix 6
1.5. Gauss-Jordan Elimination 8
1.6. The Number of Solutions to Systems of Linear Equations 14
1.7. Intersections of Lines and Planes 17
Exercises 18

Chapter 2. Vectors in Euclidean Space 21

2.1. Lower-dimensional vectors 21
2.2. Higher-dimensional Vectors 23
2.3. Linear Combinations and Spans 24
2.4. Linear Dependence and Independence 27
Exercises 29

Chapter 3. Vector Subspaces of Rn 31

3.1. Vector Spaces 31
3.2. Bases 35
3.3. Finding Bases 39
3.4. The Trivial Space 42
Exercises 43

Chapter 4. Linear Transformations 45

iii
iv Contents

4.1. Matrix Transformations 45

4.2. Linearity 47
4.3. Injective and Surjective Functions 51
4.4. Isomorphisms 54
Exercises 56
Chapter 5. [DRAFT - subject to revision] Fundamental Subspaces 57
5.1. The Kernel and Image 57
5.2. Rank-Nullity 60
5.3. Homogeneous Systems and the Geometry of Systems 63
5.4. The Row Space 65
Exercises 66

Chapter 6. [DRAFT - subject to revision] Matrix Algebra 67

6.1. Matrix Addition and Scalar Multiplication 67
6.2. The Matrix Product 68
6.3. Matrix Inverses 70
6.4. Elementary Matrices 73
Exercises 75
Chapter 7. [DRAFT - subject to revision] Determinants 77
7.1. Determinants in R2 77
7.2. Determinants in R3 79
7.3. Cofactor Expansion and Determinants in Rn 83
Exercises 84
Chapter 8. [DRAFT - subject to revision] Eigenvalues and Eigenvectors 85
8.1. Definitions 85
8.2. The Characteristic Polynomial 87
Exercises 88
Chapter 9. [DRAFT - subject to revision] Coordinate Systems and Change
of Basis 89
9.1. Coordinate Systems 89
9.2. Change of Basis Matrices 92
Exercises 95
Chapter 10. [DRAFT - subject to revision] Similarity and Diagonalization 97
10.1. Defining Matrices 97
10.2. Matrix Similarity 98
10.3. Diagonalization 100
10.4. Eigendecompositions 103
Exercises 104
Contents v

Chapter 11. [DRAFT - subject to revision] Orthogonality 107

11.1. The Dot Product 107
11.2. Orthonormal Bases and Orthogonal Matrices 109
11.3. The Gram-Schmidt Process 111
11.4. The Spectral Theorem 113
11.5. The Singular Value Decomposition 117
Exercises 121

Chapter Exercise Solutions 123

Preface

Linear algebra is the study of linear equations, vectors, vector spaces (which gen-
eralize “flat spaces” like lines and planes), and linear transformations (which are
functions between vector spaces which preserve linearity). The beauty of linear
algebra lies in the interplay between these objects: moving between algebraic and
geometric perspectives allows us to leverage the strengths of one to deepen our
understanding of another.

This course will focus on the fundamentals of linear algebra in Euclidean space. Fo-
cusing our study on Euclidean space allows the theory to develop naturally. We will
use geometric intuition from familiar two- and three-dimensional settings to build
“higher-dimensional” spaces by carrying forward formalized versions of properties
we observe. In the next course, MAT224, you will take this abstraction further,
removing the notion of vectors from Euclidean spaces entirely.

Abstraction is a hallmark of mathematics. We begin with something familiar and

intuitive—an idea or pattern we can see and understand in a concrete way—and
identify its most important features. We then describe these features in precise
mathematical language to create a theory that applies in the broadest possible set-
ting. This process builds a framework that can be used in many different contexts,
making it a powerful tool for applications. While this course will not focus on direct
applications of linear algebra, we will anchor key themes in intuitive examples to
give the reader an appreciation for where these problems arise.

Acknowledgments. These lecture notes have been shaped over multiple iter-
ations of this course, and have benefited from the valuable feedback of students,
TAs, and colleagues over the semesters. A special thank you to Noha ElGarem who
provided detailed feedback on a previous iteration of these notes, and wrote many
of the Lecture Activity and Chapter Exercise solutions. I would also like to thank
the authors of the listed additional resources for providing materials that inspired
portions of this text. Any errors or omissions are my own.

vii
viii Preface

How to use these notes. As a living document, these notes will continue to
evolve throughout the semester. Chapters which are currently under development
will be added to this public document as the course progresses. In the (hope-
fully rare) occasion that a section needs to be edited after it has been posted, an
announcement of the changes will be made on Quercus.

Additional resources. The following list of resources may be used to supple-

ment these lecture notes. It is highly recommended that students explore alternative
presentations of this material. While these notes will provide a thorough account of
what’s needed for the course, everyone processes information differently. Engaging
with supplemental resources, as well as participating in class activities, will help
develop your own personal understanding of the content.

Free resources:
(1) 3Blue1Brown, Linear Algebra.
- Builds geometric intuition with helpful visualizations.
(2) Pugh, Linear Algebra Lecture Videos.
- Lecture videos from MAT188 taught by UofT professor Mary Pugh
- Excellent speaker with clear and insightful exposition
(3) Strang, Linear Algebra Video Lectures.
- Lecture videos from MIT professor Gilbert Strang
- Another good resource for students who respond well to lecture.
(4) Siefken, Linear Algebra: MAT223 Workbook. Available on Quercus.
- Down-to-earth presentation of material with concrete examples.
(5) Alayont and Schlicker, Linear Algebra and Applications.
- Good for extra practice problems.
(6) Margalit and Rabinoff, Interactive Linear Algebra
- Consise presentation of material, interactive examples.
(7) Johnston, Introduction to linear and matrix algebra.
- Logical presentation of material, clear writing.
(8) Axler, Linear Algebra Done Right.
- Abstract presentation, often used as a resource for MAT224.
Paid resources (suggest you find used copies, or search for pdfs):
(1) Poole’s Linear Algebra: A Modern Introduction
- Concise account of material with clear writing.
(2) Strang’s Introduction to Linear Algebra
-Well-regarded textbook, accompanies lectures from item (6) above.
Preface ix

List of Notation. The following list can be used as a quick reference for nota-
tion that appears in these notes.

R the set of real numbers

C the set of complex numbers

Q the set of rational numbers

Z the set of integers

Rn n-dimensional Euclidean space

∈ is an element of

∀ for all

∃ there exists

dim(V ) the dimension of a vector space V

TA the linear transformation corresponding to the matrix A, given by TA (⃗x) = A⃗x.

MF the defining matrix of a linear transformation F

ker F the kernel of a function F

im F the image of a function F

Nul(A) the null space of a matrix A

Col(A) the column space of a matrix A

Row(A) the row space of a matrix A

A⊤ the matrix transpose

det(A) the determinant of A

Eλ the λ-Eigenspace

χA the characteristic polynomial of A

[⃗x]B the coordinates of a vector ⃗x with respect to the basis B

MC←B change of basis matrix from B to C

x Preface

MF,B the defining matrix of a transformation F with respect to the basis B

⃗x · ⃗y the dot product

∥⃗x∥ the norm

d(⃗x, ⃗y ) the distance between vectors ⃗x and ⃗y

proj⃗y ⃗x the orthogonal projection of ⃗x onto ⃗y .

 Chapter 1

Systems of Linear Equations

1.1. Introduction to Systems of Linear Equations

Our first topic in the course will be on systems of linear equations. We have the
following definitions.
Definition 1.1. A linear equation in variables x1 , x2 , . . . , xn is an equation of
the form a1 x1 + a2 x2 + · · · + an xn = b, where a1 , . . . , an and b are real numbers.
In this class, we will often work with systems of equations in four or less variables.
For notational convenience, we’ll often use the letters x, y, z, w and to indicate our
variables, rather than x1 , x2 , x3 , x4 .
Example 1.2. Observe that equations (1) and (3) below are linear, while (2) and
(4) are not.
(1) 2x + y + z = 3
(2) x2 − y = 3
z
(3) π 2 (x + y) =
2
√
(4) ex + y = z 3
Definition 1.3. A system of linear equations is a collection of one or more
linear equations in the same variables. A tuple (s1 , . . . , sn ) ∈ Rn is a solution to
a system of linear equations if (s1 , . . . , sn ) is a solution to every linear equation in
the system.
Example 1.4. Observe that (1, 0, 2, −1) is a solution to the system of linear equa-
tions
x+y−z−w =0


x − y + 2z + w = 4

Our goal in this chapter is to develop the mathematics needed to solve any system
of linear equations. Before we do this, let’s look at a few modeling examples to
motivate the types of problems these systems can represent.

1
2 1. Systems of Linear Equations

Lecture Activity 1.1. Find a system of linear equations that models each
of the problems below.
P1. Blending Problems arise in contexts where several inputs are combined
to produce a final product with specific desired properties. Given the
characteristics of each input, the goal is to determine how much of each
input is needed to meet the target requirements.
Suppose you are planning a meal using three foods. Each unit of food
contains a different combination of protein, carbohydrates, and fat, as
shown below:
Food Protein (g) Carbs (g) Fat (g)
Food A 2 3 1
Food B 1 1 2
Food C 4 2 3
If you want your meal to contain exactly 30 grams of protein, 25
grams of carbs, and 20 grams of fat, how many units of each food
should you include in your meal?

P2. Given a collection of data, it is often useful to find a mathematical

model that fits the data exactly. This process, called interpolation,
allows us to estimate missing values and understand the underlying
pattern of our data.
Find a cubic function f (x) = ax3 + bx2 + cx + d that passes through
all of the following points: (0, −2), (1, 1), (2, 6), and (3, 10).

P3. Flow conservation problems arise in systems where something moves

through a network so that at each junction, the total amount flowing
in must equal the total amount flowing out.
The University of Toronto supplies water to campus buildings from the
city system through a one-way distribution network. In this system,
the flow into each building must equal the flow out, unless some water
is used on-site. Three connected buildings are involved: ROB (Robarts
Library), SS (Sidney Smith Hall), and BA (Bahen Centre). Water is
delivered between the buildings as follows:
- The city sends 120 liters of water per minute to ROB,
- ROB uses 35 liters of water per minute and sends the rest to SS,
- SS uses 40 liters of water per minute and sends the rest to BA,
- BA uses 45 liters of water per minute and sends the rest to ROB.
Describe the rate at which water needs to flow between each of the
buildings in order for the system to be conserved (that is, no water is
lost or stored).

In Lecture Activity 1.1 you may have been able to solve the systems using “ad-
hoc” methods. This is fine for small examples, but is not feasible in real-world
application where the size of our systems could be very large. In the following
1.2. The Matrix Representation of a Linear System 3

section, we introduce some notation which will help us develop a systematic method
to handle any system of linear equations.

1.2. The Matrix Representation of a Linear System

Consider the system of linear equations


 x−y−z =1
2x − 3y − z = 3

 −x + y − z = −3

We can record the important information about this system in an array as follows

1 −1 −1 1
2 −3 −1 3
−1 1 −1 −3

Observe that the first three columns of this array correspond to the coefficients
of our variables x, y and z for each of our three equations, and the last column
corresponds to the constant on the right-hand side of our linear equations. This
array is called a matrix, and can be used as a bookkeeping device to help us solve
systems of linear equations. Let’s give some formal definitions.
Definition 1.5. A matrix is any rectangular array of quantities or expressions.
The quantities or expressions in a matrix are called its entries. If a matrix has m
rows and n columns, then we call this an m × n matrix.

In this class, our matrices will typically contain real number entries (or sometimes
variables working as placeholders for real number entries). Matrices are often writ-
ten using soft brackets, such as in the 2 × 2 matrix below
 
1 2
0 −3
or by using hard brackets, such as in the 3 × 2 matrix below
 
0 π
3 2 .
1 7
We’ll be using soft brackets throughout these notes, but either one is perfectly fine.
Definition 1.6. Consider a general system of linear equations
 a x + a x + ··· + a x = b
 11 1 12 2 1n n 1

 a21 x1 + a22 x2 + · · · + a2n xn = b2


..



 .
am1 x1 + am2 x2 + · · · + amn xn = bm .

4 1. Systems of Linear Equations

The coefficient matrix of this system is the m × n matrix given by

 
a11 a12 · · · a1n
 a21 a22 · · · a2n 
..  .
 
 .. .. ..
 . . . . 
am1 am2 · · · amn
The augmented matrix of this system is the m × (n + 1) matrix given by
 
a11 a12 · · · a1n b1
 a21 a22 · · · a2n b2 
..  .
 
 .. .. .. ..
 . . . . . 
am1 am2 · · · amn bm
Note that the augmented matrix accounts for the constants on the right-hand side
of our equations, while the coefficient matrix does not. Also note that sometimes
people do not draw the bar pictured above in an augmented matrix. The vertical
line is just an extra piece of decoration for the sake of clarity, it does not
change anything about the entries or size of the matrix.
Example 1.7. Consider again the system of linear equations


 x−y−z =1
2x − 3y − z = 3

 −x + y − z = −3

The coefficient matrix of this system is the 3 × 3 matrix

 
1 −1 −1
 2 −3 −1
−1 1 −1
and the augmented matrix of this system is the 3 × 4 matrix
 
1 −1 −1 1
 2 −3 −1 3  .
−1 1 −1 −3
Note that we could also write the augmented matrix of this system as
 
1 −1 −1 1
 2 −3 −1 3  .
−1 1 −1 −3
As mentioned above, the type of brackets used to enclose the matrix and the decision
to include the vertical line or not are just choices for how we decorate our matrix.
Two matrices with the same entries are equal, no matter how you decorate them.
Remark 1.8. Note that every matrix has an associated system of linear equations.
For example, consider the 3 × 3 augmented matrix
 
1 2 0
A = 3 −1 1 .
1 1 1
1.3. Equivalent Systems and Elementary Row Operations 5

Then, A is the augmented matrix of a system of three linear equations in two

variables 
x + 2y = 0

3x − y = 1

 x+y =1

Recall that the last column of an augmented matrix corresponds to the constant
coefficients of the corresponding system. This correspondence between systems of
linear equations and matrices is an important idea we’ll revisit many times through-
out the course.

1.3. Equivalent Systems and Elementary Row Operations

In order to generate an algorithm to solve any system of linear equations, it will be
convenient to restrict ourselves to just a few types of operations that we can use to
manipulate the system. Note that if we perform any of the following operations,
we’ll obtain a new system of linear equations, but with the same solution set:
(E1) Interchange two equations of the system;
(E2) Replace an equation by a nonzero multiple of itself;
(E3) Replace one equation by the sum of that equation and a scalar multiple of
another equation.
We introduce some terminology to streamline our conversation.
Definition 1.9. Two systems of linear equations are called equivalent if they
have the same solution sets.
Example 1.10. Consider the system of linear equations

 x−y−z =1

(1.1) 2x − 3y − z = 3

 −x + y − z = −3

We could apply (E3) to replace the third equation with the sum of the first and
third equations to obtain the new system of linear equations

 x−y−z =1

(1.2) 2x − 3y − z = 3

 −2z = −2
Observe that Systems (1.1) and (1.2) are equivalent (that is, they have the same
solution sets), but System (1.2) is simpler to solve since we’ve isolated one of our
variables.

Let’s look at this elementary operation with our new book keeping device. System
(1.1) has augmented matrix
 
1 −1 −1 1
 2 −3 −1 3 
−1 1 −1 −3
6 1. Systems of Linear Equations

Note that replacing the third equation with the sum of the first and third equations
is identical to replacing the third row of the augmented matrix above with the sum
of the first and third row, which yields
 
1 −1 −1 1
2 −3 −1 3  .
0 0 −2 −2
Note that this is precisely the augmented matrix for System (1.2).

More generally, our three elementary operations (E1), (E2), and (E3) can be viewed
as operations on the rows of the corresponding augmented matrix. We define the
following.
Definition 1.11. The elementary row operations are defined as follows:
(ER1) Interchange two rows;
(ER2) Replace a row by a nonzero scalar multiple of itself.
(ER3) Replace one row by the sum of that row and a scalar multiple of another
row;
We say that two matrices A and B are row equivalent if one can be obtained
from the other by a sequence of elementary row operations. In this case, we write
A ∼ B.

Noting again that applying an elementary row operation is the same as applying
an operation to a system of linear equations, which yields an equivalent system of
linear equations, we obtain the following key result:
Theorem 1.12. If two matrices are row equivalent, then the system of linear equa-
tions they represent are equivalent (that is, have the same solution sets).

In short order, we’ll see that these three elementary operations are enough to solve
any system of linear equations. To do this, let’s first think about which systems of
linear equations are “simplest” to solve.

1.4. Echelon Forms of a Matrix

Lecture Activity 1.2. Find all solutions to the the system of linear equa-
tions that have the following augmented matrices
 
1 1 1 1
P1. 0 1 −1 1
0 0 2 2
 
0 2 −1 1
P2.
0 0 0 1
 
2 2 1 2
P3.
0 0 3 6
1.4. Echelon Forms of a Matrix 7

In Lecture Activity 1.2, we were either able to directly detect that the system had
no solutions, or we were able to solve the system using back substitution. In the
latter case, we were able to carry this method through because each of the equations
in our system had at least one less variable than the equation above it. This feature
gave the corresponding augmented matrices an “inverted staircase” pattern. Let’s
give some definitions to make sense of this pattern more carefully.
Definition 1.13. The pivot of a row in a matrix is the leftmost nonzero entry in
that row.
Example 1.14. The matrix
 
0 1 −1 1
A = 0 0 0 2
3 0 1 3
has pivot 1 in the first row, 2 in the second row, and 3 in the third row.
Definition 1.15. A matrix is in row echelon form if
(1) all rows consisting only of zeros are at the bottom, and
(2) the pivot of each nonzero row in the matrix is in a column to the right of the
pivot of the row above it.
Definition 1.16. A matrix is in reduced row echelon form if
(1) the matrix is in echelon form,
(2) the pivot in each nonzero row is 1, and
(3) each pivot is the only nonzero entry in its column.

Lecture Activity 1.3. Determine which of the following matrices are in

row echelon form, reduced row echelon form, or neither.
   
1 0 0 1 0 0  
0 −1 0 0
A = 2 0 1  , B = 0 1 0 , C = ,
0 0 2 1
3 4 −1/2 0 0 1
   
0 1 0 2 0 0 1 0  
0 1 2
D = 0 0 1 3 , E = 0 0 0 0 , F =
0 0 0
0 0 0 1 0 0 0 1

Lecture Activity 1.4. Give an example of matrix A that satisfies all of

the following conditions:
- A is the augmented matrix for a system of 4 linear equations in 4
variables.
- A is in reduced row echelon form.
- A has exactly three pivots.
- A contains at least one entry other than 0 or 1.

Activity 1.2 demonstrate the following key observation.

8 1. Systems of Linear Equations

Observation 1.17. Any system of linear equations whose matrix is in (reduced)

row echelon form can be solved using back substitution.

So, one way to solve any system of linear equations is to find an equivalent system
whose augmented matrix is in (reduced) row echelon form (reduced row echelon
form simplifies the calculation by leaving everything in our matrix, but you can
use back substitution on either form). In the next section, we show that this can
always be done.

1.5. Gauss-Jordan Elimination

The following result is typically attributed to the two German mathematicians
Carl Friedrich Gauss and Wilhelm Jordan due to their work in the 1800s, but was
previously documented in a Chinese text dating back to around 150 BC.
Theorem 1.18 (Gauss-Jordan). Every matrix A is row equivalent to a matrix in
row echelon form B. Furthermore, if B is in reduced row echelon form, then B is
unique.

Let’s first look at an example to convince ourselves of this result. For convenience,
we’ll use the following shorthand to notate our elementary operations:
Ri ↔ Rj : interchange the ith and jth rows;
cRi : replace row i by row i times the nonzero constant c;
Ri + cRj : replace row i with row i plus the constant c times row j (note that
we’ve written the row which is being replaced first in the operation).
Example 1.19. Let
 
1 1 2 1
A = 1 3 6 1
2 4 8 2
Our first goal will be to get A into row echelon form. There are no rows of zeros,
so let’s look at the pivots of A, given in bold-face below
 
1 1 2 1
A = 1 3 6 1 .
2 4 8 2
Since position (1, 1) has a pivot, we cannot have any other pivots in the first column
of the rows below. We can use the pivot in the (1, 1) position to get rid of the other
pivots in that first column as follows:
 
1 1 2 1
A ∼ 0 2 4 0 , via R2 − R1
2 4 8 2
 
1 1 2 1
∼ 0 2 4 0 , via R3 − 2R1
0 2 4 0
1.5. Gauss-Jordan Elimination 9

We now repeat the process above with our new matrix, which has pivots given in
bold-face below  
1 1 2 1
 0 2 4 0
0 2 4 0
The pivot in position (1, 1) does not have any pivots in the rows below, so there’s
nothing left to do here. However, we have a pivot in the (2, 2) position, and so
we should not have any pivots in the second column of the rows below. We can
eliminate the pivot in the (3, 2) position by using the pivot in the row above, as
follows
   
1 1 2 1 1 1 2 1
0 2 4 0 ∼ 0 2 4 0 , via R3 − R2
0 2 4 0 0 0 0 0
and we see that our matrix is now in row echelon form. Next, let’s get our matrix
into reduced row echelon form. The matrix above has pivots given in bold-face
below  
1 1 2 1
 0 2 4 0
0 0 0 0
The pivot in the (1, 1) entry is the only nonzero entry in its column, so there’s
nothing to do here. However, the pivot in the (2, 2) entry has nonzero entries in its
column. We can use the pivot to eliminate the other pivots in the second column
as follows
   
1 1 2 1 1 0 0 1
0 2 4 0 ∼ 0 2 4 0 , via R1 − 1 R2
2
0 0 0 0 0 0 0 0
Finally, we need to make all of our pivots equal to 1, which we can achieve by
performing the operation 12 R2 to the second row. Putting this all together, we get
 
1 0 0 1
A ∼ 0 1 2 0
0 0 0 0
which is a matrix in reduced row echelon form, as desired.
Remark 1.20. There are many ways to reduce the matrix above. For example, we
could have first divided the third row by 2, and then proceeded similarly, to simplify
our calculations. In the proof below, we give a complete algorithm to prove Gauss-
Jordan for an arbitrary matrix A. However, it’s often easier to allow yourself some
flexibility when row reducing a matrix. Instead of following the algorithm below,
we suggest using the following general principles:
(1) First, find a matrix in row echelon form that’s row equivalent to your matrix.
To achieve this, eliminate pivots as needed using the pivots in the rows above.
(2) Once your pivots are in the correct location (i.e. your matrix is in row echelon
form), use the pivot in each row to eliminate all other pivots in its column.
(3) Divide your row by the appropriate scalar to make your pivots equal to 1.
(4) Whenever it makes sense, move rows of zeros to the correct location.
10 1. Systems of Linear Equations

(5) If you find yourself at a step where you can eliminate many entries at once,
do that (even if it takes you “off-algorithm”)

The uniqueness of the matrix in the Theorem 1.18 allows us to define the following.
Definition 1.21. If A is row equivalent to a matrix X which is in reduced row
echelon form, we call X the reduced row echelon form of A, and write
rref(A) = X.

The best way to become comfortable with this process is through practice, so let’s
look at one more example together.

Lecture Activity 1.5. Find rref(A), where

 
1 1 1 7 −1
A =  0 1 1 4 −1 .
−1 2 2 5 −2

The following proof of Gauss-Jordan is included for completeness. Interested read-

ers are encouraged to take a look, but note that understanding of this proof is not
required for this course.

Proof of Theorem 1.18. Suppose that A is an m×n matrix. Then, the following
algorithm will give us a matrix which is row equivalent to A and in reduced row
echelon form.
Step 1: Move all rows of zeros to the bottom. Suppose that A has a row of zeros in
row i where i ̸= m. Letting j be the largest index so that row j is not a row of zeros,
interchange Rows i and j. Repeating this process for all rows gives a row equiv-
alent matrix A1 so that all rows consisting entirely of zeros are at the bottom of A1 .

Step 2: Move pivots. For all i < j so that the pivot in Rj is in a column to the left
of the pivot in Ri in A1 , interchange row i with row j. This gives a row equivalent
matrix A2 so that all pivots are either to the right or below of the pivots in columns
above it. Furthermore, A2 still has all rows of zeros at the bottom of the matrix.

Step 3: Find a matrix in row echelon form. For all i, j so that the pivot in row
i is in the same column as the pivot in row j in A2 , perform the row operation
Rj − aj /bi Ri , where aj is the pivot in row j and bi is the pivot in row i. This gives
a row equivalent matrix A3 in row echelon form.

Step 4: Make all pivots equal to 1. For all rows Ri containing a pivot ai in A3 ,
replace Ri with (1/ai )Ri . This gives a row equivalent matrix A4 that is still in row
echelon form, and where every pivot is equal to 1.

Step 5: Remove nonzero nonpivot entries from pivot columns. Finally, letting ai be
the pivot in row i, if there exists a nonzero entry bi in position (j, i), that is in the
jth row and ith column, replace Rj with Rj − abii Ri . If necessary, repeat previous
1.5. Gauss-Jordan Elimination 11

steps until the matrix is in reduced row echelon form.

Next, we show that the matrix constructed above is unique. To do this, we will
induct on the number of columns of A (see Appendix A for a discussion on proof
by induction). For the base case, observe that there are only two m × 1 matrices
in reduced row echelon, given by
   
0 1
0 0
 ..  and  ..  .
   
. .
0 0
If these matrices are row equivalent, then so are
   
0 0 1 0
0 0 0 0
 and  .. .
   
 ..
.  . 
0 0 0 0
But, the first matrix is the augmented matrix for a system of linear equations where
x1 can be equal to any real number, while the second matrix is the augmented ma-
trix for a system of linear equations where x1 = 0. That is, these systems do not
have the same solution sets, and so the matrices above cannot be row equivalent
by Theorem 1.12.

Next, suppose that the result holds for any m × k matrix where k < n for an integer
n ≥ 1. Let A be m × n, and suppose that A ∼ B and A ∼ C where B and C are
both in reduced row echelon form. Write
   
b11 b12 · · · b1n c11 c12 · · · c1n
 b21 b22 · · · b2n   c21 c22 · · · c2n 
B= . and C = ..  .
   
. .. .  .. .. ..
 .. .. .. 

.  . . . . 
bm1 bm2 ··· bmn cm1 cm2 ··· cmn
For a contradiction, suppose that B ̸= C. Let B ′ be the matrix obtained by deleting
the nth column from B, and similarly let C ′ be the matrix obtained by deleting
the nth column from C. Observe that B ′ and C ′ are still in reduced row echelon
form, and so by induction we have B ′ = C ′ . That is, the entries of B and C are
equal except for possibly the last column. Since we’ve assumed B ̸= C we must
have bin ̸= cin for some i ∈ {1, . . . , m}. Let ℓ be the smallest such integer. Now,
consider the systems of linear equations which have B and C as their coefficient
matrices, respectively
 b x + b x + ··· + b x = 0
 11 1 12 x 1n n

 b21 x1 + b22 x2 + · · · + b2n xn = 0


..


 .

bm1 x1 + bm2 x2 + · · · + bmn xn = 0,

12 1. Systems of Linear Equations

 c x + c x + ··· + c x = 0
 11 1 12 x 1n n

 c21 x1 + c22 x2 + · · · + c2n xn = 0


..


 .

cm1 x1 + cm2 x2 + · · · + cmn xn = 0.


If we subtract the ℓth equations of these two systems, we obtain

(bℓ1 − cℓ1 )x1 + · · · + (bℓn − cℓn )xn = 0
but by our inductive step we know that all coefficients above are equal to 0 except
for the last one. This gives
(bℓn − cℓn )xn = 0,
and since we’ve assumed bℓn ̸= cℓn we must have xn = 0. But, since xn is equal to
a fixed value, B and C must both contain a pivot in the nth column (otherwise the
variable xn will be “free”, allowing it to equal any real number, as we’ll see at the
end of this section). Since ℓ was the smallest integer so that bin ̸= cin we must have
bℓn , cℓn nonzero, and since B and C are in reduced row echelon form with a pivot
in the nth column, then bℓn and cℓn are pivots in B and C, respectively. But this
gives bℓn = cℓn = 1, a contradiction (we assumed these entries were not equal!).
Hence, we must have B = C as needed. □
Remark 1.22. Observe that we now have an algorithm to find all solutions to any
system of linear equations. We summarize the method below.
(1) Given a system of linear equations, write down its corresponding augmented
matrix A.
(2) Use Gauss-Jordan elimination to find its reduced row echelon form X. We
will often refer to this step as “row reducing A”.
(3) Using back substitution, find all solutions to the system of linear equations
represented by X. Since X and A are row equivalent, the system of linear
equations they represent have the same solution sets.

We saw an example of how to handle step (3) in Activity 1.3. We give a few more
definitions to algorithmatize this step further.
Definition 1.23. A system of linear equations is called consistent if it has at
least one solution. If the system has no solutions, it is called inconsistent.
Definition 1.24. Let C be the coefficient matrix for a consistent system of linear
equations in variables x1 , . . . , xn .
(1) We say that xi is a basic variable for the system if the ith column of rref(C)
has a pivot.
(2) We say that xi is a free variable of the system if the ith column of rref(C)
does not have a pivot.

In the next section, we’ll see that a system has a free variable if and only if the
system has infinitely many solutions (see Theorem 1.27). In this case we can pa-
rameterize the solution set using our free variables. We demonstrate this method
by example below.
1.5. Gauss-Jordan Elimination 13

Example 1.25. Consider the system of linear equations


 x + y + 2z = 1

x + 3y + 6z = 1

2x + 4y + 8z = 2

Recall from Example 1.19 that augmented matrix for this system
 
1 1 2 1
A = 1 3 6 1
2 4 8 2
has reduced row echelon form
 
1 0 0 1
rref(A) = 0 1 2 0 .
0 0 0 0
Since rref(A) does not have a pivot in the last column, it’s consistent (i.e. has a
solution), and furthermore the coefficient matrix of our system C satisfies
 
1 0 0
rref(C) = 0 1 2 .
0 0 0
Note that the pivots of rref(C) are in columns 1 and 2, and so x and y are basic
variables, while z is free. Let’s look at what this tells us about our solution set.
The system of linear equations that rref(A) represents is given by


 x=1
y + 2z = 0

 0=0
Now, if we let z (our free variable) be any real number then our solution set can
be described parametrically as {(1, −2z, z) : z ∈ R}. Note that the existence of
a free variable guarantees our solution set has infinitely many solutions, and those
solutions may be parameterized by the free variables.
Remark 1.26. It is also completely valid for us to instead choose y to vary over
the real numbers instead, and have z be controlled by y. In this case, our solution
set could be described parametrically as {(1, y, −y/2) : y ∈ R}. We’ll see later on
that it’s convenient to choose our free variables as the variables corresponding to
the non-pivot columns of our coefficient matrix, as demonstrated in the example
above, but you’re welcome to describe your solution sets in whatever way makes
the most sense to you.

Lecture Activity 1.6. Let A be the matrix from Lecture Activity 1.5, and
consider the system of linear equations in variables x, y, z, w which has A as
its augmented matrix.
P1. Determine the free variables and basic variables of the system.
P2. Give a parametric description of the solution set to this system.
14 1. Systems of Linear Equations

1.6. The Number of Solutions to Systems of Linear Equations

Our work in the previous sections not only tells us how to describe the solution set to
any system, but also gives a quick method to detect the number of solutions to any
given system. The result below is often attributed to the mathematicians Eugéne
Rouché and Alfredo Capelli. As this will end up being one of our most referenced
results this semester, we’ll refer to it as the Rouché-Capelli Theorem.
Theorem 1.27 (Rouché-Capelli). Suppose that a system of linear equations has
augmented matrix A and coefficient matrix C. Then,
(1) The system is inconsistent if and only if the last column of rref(A) has a pivot.
(2) The system has exactly one solution if and only if the last column of rref(A)
does not have a pivot, and every column of rref(C) has a pivot.
(3) The system has infinitely many solutions if and only if the last column of
rref(A) does not have a pivot and rref(C) has a column without a pivot.
Example 1.28. Let’s look at several examples to convince ourselves of this result.
(1) Suppose that a system of linear equations has augmented matrix A with
 
1 0 1 0
rref(A) = 0 1 1 0 .
0 0 0 1
Observe that the last column has a pivot, and it is precisely the row containing
this pivot that represents the equation 0 = 1. Since this equality never holds,
our system must have no solutions.

(2) Suppose that a system of linear equations has augmented matrix A with
 
1 0 2
rref(A) = 0 1 3 .
0 0 0
Note that rref(A) does not have a pivot in the last column, and so we do not
end up with an equation as in the previous part. Also note that the coefficient
matrix of this system C satisfies
 
1 0
rref(C) = 0 1 ,
0 0
which has a pivot in every column. This tells us that all of our variables
are basic. In other words, we have no free variables, and hence no choice for
solutions. We see that this system has exactly one solution given by x = 2
and y = 3.
(3) Suppose that a system of linear equations has augmented matrix A with
 
1 2 −1 0 1
rref(A) = .
0 0 0 1 0
Note that rref(A) does not have a pivot in the last column, and so the system
is consistent (i.e. has a solution). Also note that the coefficient matrix of this
1.6. The Number of Solutions to Systems of Linear Equations 15

system C satisfies
 
1 2 −1 0
rref(C) = ,
0 0 0 1

which does not have a pivot in the second or third column. Hence, when we
write the parametric form for the solution set to this system, the variables
x2 , x3 will be free (as seen in Example 1.25). That is, we can find a solution
for our system for any choice of real numbers for x2 and x3 . Hence, the system
has infinitely many solutions.

The proof of Rouché-Capelli rests on our observations from the previous example.
We include the proof below for completeness.

Proof. Suppose that we have a system of m linear equations in n variables. Then,

A is an m × (n + 1) matrix, and C is an m × n matrix.

For part (1), suppose that rref(A) has a pivot in the last column. Then, rref(A)
contains a row of the form


0 ··· 0 1

which represents the linear equation 0 = 1. Since this equation can never have
a solution, the system of linear equations represented by A has no solutions, as
needed. Now, since rref(C) either contains a pivot in every column or not, the case
where rref(A) does not have a pivot in every column will be handled in parts (2)
and (3).

For part (2), suppose that rref(A) does not have a pivot in the last column, and
every column of rref(C) has a pivot. By Chapter Exercise P1.1 observe that we
must have m ≥ n, and so rref(A) is of the form
 
1 0 · · · 0 a1
 0 1 · · · 0 a2 
 
 .. .. . . ..
,

. .
 . . 
 0 0 · · · 1 an 
0 0 ··· 0 0

where the bold-face 0’s indicate that the remaining n − m rows are rows of zeros.
Hence, our system has one solution, given by (x1 , . . . , xn ) = (a1 , . . . , an ). Con-
versely, if our system of linear equations has exactly one solution (a1 , . . . an ) then
our system is equivalent to
x = a
 1 1

 x2 = a2


..


 .


xn = an
16 1. Systems of Linear Equations

and so  
1 0 · · · 0 a1
 0 1 · · · 0 a2 
 
A ∼  ... ... . . . ... ..  .

 . 

 0 0 · · · 1 an 
0 0 ··· 0 0
Furthermore, noting that the elementary row operations preserve columns, we get
 
1 0 ··· 0
0 1 · · · 0
 
C ∼  ... ... . . . ...  .
 
 
0 0 · · · 1
0 0 ··· 0
Since the matrices above are in reduced row echelon form, then rref(A) and rref(C)
are as needed.

Finally, for part (3), suppose that rref(A) does not have a pivot in the last column,
and rref(C) has a column without a pivot. Then, either the variable xn is free, or
there must be two consecutive rows in rref(A) of the form
!
0 ··· 1 ··· * ··· ∗ ··· bi
,
0 ··· 0 ··· 0 ··· 1 · · · bi+1
where the bold-face 0 indicates possibly more than one zero entry in this row.
Supposing the jth column has no pivot, we see using back substitution that the
variable xj can be taken to be any real number, which gives a system with infinitely
many solutions, as needed. Conversely, if our system has infinitely many solutions,
then one of our variables must be free, which yields two consecutive rows in rref(A)
as above. □

Since every matrix either does or does not have a pivot in the last column, we
obtain the following corollary.
Corollary 1.29. Every system of linear equations either has no solutions, exactly
one solution, or infinitely many solutions.

Note that Corollary 1.29 is a special property of linear systems. For example, the
nonlinear system
x2 + y 2 = 1
(

(x − 1)2 + y 2 = 1
can be seen to have exactly two solutions.

Lecture Activity 1.7. Suppose that we’re given a set of n data points
that lie exactly on the graph of some unknown cubic function. What’s the
minimum number of points needed to guarantee there’s exactly one cubic
function passing through them? Explain your answer.
1.7. Intersections of Lines and Planes 17

1.7. Intersections of Lines and Planes

So far, we’ve been working with systems of linear equations completely algebraically.
Let’s start looking at some of the geometric implications of what we’ve learned so
far. Note that a linear equation in two variables ax + by = c defines a line in R2 ,
and a linear equation in three variables ax + by + cz = d defines a plane in R3 . This
leads to the following observation.

Observation 1.30. Solutions to systems of linear equations in two variables corre-

sponds to intersection points of lines in R2 . Similarly, solutions to systems of linear
equations in three variables corresponds to intersection points of planes in R3 .

Let’s look first at the two dimensional case. Note that two lines in R2 can either
be the same line, distinct and parallel, or distinct and not parallel

We see geometrically that these cases correspond to systems of linear equations

which have infinitely many solutions, no solutions, or exactly one solution.

Let’s also look at the geometry of systems in three variables. Suppose that we have
three linear equations in three variables that correspond to three distinct planes in
R3 . In this case, we could have two of the planes being distinct and parallel, as in
the picture below

or no two of our planes are parallel, in which case our planes can intersect at a line
18 1. Systems of Linear Equations

or at a point

Again we see geometrically that these cases correspond to systems of linear equa-
tions which have no solutions, infinitely many solutions, or exactly one solution,
which matches what we found in our corollary to Rouché-Capelli.

Exercises

P1.1 Suppose that A is an m × n matrix. Show that rref(A) can have at most
min{m, n} pivots, where min{m, n} is the smallest of m and n; that is,
(
m if m ≤ n
min{m, n} =
n if m ≥ n.
P1.2 List all possible reduced row echelon forms of a 3 x 4 matrix with a pivot in
exactly two rows. Use ‘∗’ to denote entries which can be equal to any real
number. Make sure to justify how you know you’ve checked all possible cases.
P1.3 We call a system of linear equations homogeneous if the constant term in
each equation is zero. For example, the system
2x + 3y − z = 0
−x + 5y + 2z = 0
is homogeneous.
Exercises 19

(a) Is it possible for a homogeneous system of linear equations to have no

solutions? If so, provide an example. If not, provide reasoning.
(b) Is it possible for a homogeneous system of linear equations to have exactly
one solution? If so, provide an example. If not, provide reasoning.
(c) Is it possible for a homogeneous system of linear equations to have infin-
itely many solutions? If so, provide an example. If not, provide reason-
ing.
P1.4 Give an example of systems of linear equations satisfying the properties below
(you should give a different system for each part). If such a system does not
exist, explain why not.
(a) A system of linear equations with a unique solution for which the reduced
row echelon form of the augmented matrix of the system has a row of
0’s.
(b) A system of linear equations with a unique solution that has fewer equa-
tions than variables.
(c) A system of linear equations with a unique solution that has more equa-
tions than variables.
(d) A consistent system in two variables whose augmented matrix has exactly
three pivot columns.
(e) An inconsistent system whose coefficient matrix has a pivot in every row.
P1.5 Show that if ad − bc ̸= 0 then the system of linear equations
ax + by = r
cx + dy = s
has a unique solution.
 Chapter 2

Vectors in Euclidean Space

In this chapter, we introduce vectors in Euclidean space. We will first introduce

vectors in familiar lower-dimensional spaces using geometric notions, and then use
algebraic properties we observe to define vectors in higher dimensions.

2.1. Lower-dimensional vectors

In dimensions no more than 3, we can define vectors as mathematical objects,
typically drawn as arrows, that capture displacement. In this section, we’ll look
at vectors geometrically in two-dimensional space, and note that our observations
work identically in one and three dimensions.
Note that displacement is uniquely defined by magnitude (i.e. length or distance)
and direction. There are a few ways that we can indicate the magnitude and direc-
tion of a vector. One common way to do this is to keep track of the displacement
along the axes of a standard coordinate grid. For example, consider the vector in
two-dimensional space drawn below

⃗v

Observe that the displacement this vector represents can be understood by dis-
placement in the x-direction by 3 units and displacement in the y-direction by 2
units. We typically denote this by listing the 
displacement
 in each direction, and
3
then wrapping that list up in brackets: ⃗v = . This is called the standard
2
coordinate representation of ⃗v .

21
22 2. Vectors in Euclidean Space

Remark 2.1 (Unrooted Vectors). Note that in the example above, we drew our
vector starting from the origin (0, 0). However, it’s possible to shift a vector around
the plane without changing its direction and magnitude. That is, our vectors are
“unrooted”, meaning they can “start anywhere.” Recall that our vector ⃗v is the
vector which represents displacement in the x direction by 3 and displacement in
the y direction by 2, which can be represented as an arrow starting at (0, 0), or at
(−1, 1), or anywhere else we’d like

⃗v

⃗v

Remark 2.2 (Correspondence Between Vectors and Points). In this course, we’ll
be studying how certain sets of vectors behave together. One convenient way to do
this is to correspond each vector to a point. This will allow us to think of sets of
vectors as familiar geometric objects.
 
x
Our correspondence will associate each vector in R2 to the point (x, y) in R2 .
y
Graphically, we can visualize this as our vectors corresponding to the point the tip
sits at when rooted at the origin. In the example below, we see that the vector ⃗v
corresponds to the point (3, 2), which is simpler to see visually when we root ⃗v at
the origin (0, 0).

⃗v

⃗v (3, 2)
x

Lecture Activity 2.1. Let’s look at how to calculate total displacement.

P1. Suppose that someone gave you the following directions: (1) from your
starting point, walk two blocks east and one block north, then (2) walk
2.2. Higher-dimensional Vectors 23

one block east and three blocks north. Find the standard coordinate
representation of your total displacement.
P2. On the graph below, sketch the path you would take by following the
directions from P1. On the same graph, sketch the total displacement
vector you found in P1.

P3. Suppose that someone gave you the following directions: (1) from your
starting point, walk v1 blocks east and v2 blocks north, then (2) walk
w1 blocks east and w2 blocks north. Find the standard coordinate rep-
resentation of your total displacement. In this problem, v1 , v2 , w1 , w2
are unknown real numbers.

2.2. Higher-dimensional Vectors

We now generalize our work from the previous section to “n-dimensional Euclidean
space”. While this generalization doesn’t have an immediate geometric meaning
when n ≥ 4 (at least for those of us that exist in 3-dimensional space), we will often
continue to think of these spaces geometrically since they were defined by “carrying
forward” geometric properties from lower dimensions.
Definition 2.3. An n-dimensional vector is a list of n (real) numbers in a
specified order, which we’ll write in the form
 
v1
 v2 
⃗v =  .  .
 
 .. 
vn
We call the entries vi the standard coordinates of the vector ⃗v .
Definition 2.4. The set of all n-dimensional vectors with real number coordinates
is called n-dimensional Euclidean space, and is denoted by Rn .

We have the following operations.

24 2. Vectors in Euclidean Space

Definition 2.5. Let    

v1 w1
 v2   w2 
⃗v =  .  and w
⃗ = . 
   
 ..   .. 
vn wn
be vectors in Rn and let c be a real number scalar. We define vector addition
⃗v + w
⃗ and scalar multiplication c⃗v as follows:
   
v1 + w1 cv1
 v2 + w2   cv2 
⃗v + w
⃗ :=   , and c⃗v =  ..  .
   
..
 .   . 
vn + wn cvn
Remark 2.6. As we saw in Lecture Activity 2.1, in lower-dimensions vector ad-
dition ⃗v + w
⃗ captures the total displacement obtained from the displacement of ⃗v
followed by w.⃗ Similarly, scalar multiplication c⃗v captures the total displacement
obtained from performing the displacement of ⃗v consecutively c times.

2.3. Linear Combinations and Spans

The following activity will motivate two key problems we’ll investigate together this
semester.

Lecture Activity 2.2 (Flight Navigation I). You are piloting an airplane
equipped with two fixed-direction thrusters that assist in maneuvering. Each
thruster provides thrust in a specific, constant direction and can be fired
forward or in reverse for any number of seconds. In this scenario, we assume
the airplane is already at cruising altitude, and the two thrusters only affect
horizontal position.
• Firing Thruster A for one second in the forward direction moves the
airplane 17 meters East and 7 meters North; firing Thrusters A for one
second in the backward direction moves the airplane 17 meters West
and 7 meters South.
• Firing Thruster B for one second in the forward direction moves the
airplane 5 meters East and 18 meters North; firing Thruster B for one
second in the backward direction moves the airplane 5 meters West
and 18 meters South.
In this problem, we explore what these thruster directions imply about the
airplane’s maneuverability at its current fixed altitude.
P1. Suppose you’re instructed to reach a waypoint located 235 meters East
and 33 meters North of your current position. Can you reach the
waypoint using only Thruster A or only Thruster B? If yes, determine
how many seconds you need to fire the thruster to reach the waypoint.
If not, explain why not.
2.3. Linear Combinations and Spans 25

P2. Can you reach the waypoint from P1 using a combination of both
thrusters? If yes, determine how many seconds you need to fire each
thruster to reach the waypoint. If not, explain why not.
P3. Can you reach every possible waypoint at your current elevation (i.e.,
in the same horizontal plane) using a combination of Thrusters A and
B? Explain your answer.

In Lecture Activity 2.2, we were able to solve the given vector equations by cor-
responding them to a system of linear equations. Note that for each system of
linear equations, we also have a corresponding vector equation. We summarize this
observation below.
Proposition 2.7. The vector equation
x1⃗v1 + x2⃗v2 + · · · + xn⃗vn = w
⃗
has the same solution set as the system of linear equations with augmented matrix


⃗v1 ⃗v2 · · · ⃗vn w ⃗ .
We include the proof of this Proposition below for completeness.

Proof. Consider the vectors

     
v11 v1n w1
 ..   ..   .. 
⃗v1 =  .  , . . . , ⃗vn =  .  , w
⃗ = . 
vm1 vmn wm
m
in R . Using our definition of vector addition and scalar multiplication, we can
rewrite the vector equation
x1⃗v1 + x2⃗v2 + · · · + xn⃗vn = w
⃗
in the form    
x1 v11 + · · · + xn v1n w1
..   .. 
 =  . .

 .
x1 vm1 + · · · + xn vmn wn
Since a vector is uniquely determined by its standard coordinates, solutions to our
vector equation are precisely solutions to the following system of linear equations
x1 v11 + · · · + xn v1n = w1



..

 .

x1 vm1 + · · · + xn vmn = wn ,


which has the following augmented matrix

 
v11 · · · v1n w1
 .. .. .. ..  = ⃗v

 . . . .  1 ⃗v2 ··· ⃗vn w
⃗ ,
vm1 ··· vmn wn
as needed.
□
26 2. Vectors in Euclidean Space

Lecture Activity 2.3. Find the augmented matrix for the system of linear
equations that has the same solution set as the following vector equations.
Then, find all solutions to the vector equation.
     
1 −1/2 3
P1. x +y =
2 5 4
     
1 3 2
P2. x 1 + y 4 = 5
1
   1 1   
2 5 −1 4
P3. x +y +z =
1 3 0 2

Let’s add some terminology to the vector equations we encountered in the Lecture
Activity 2.1.
Definition 2.8. A linear combination of vectors ⃗v1 , ⃗v2 , . . . , ⃗vn in Rm is a vector
of the form
w⃗ = c1⃗v1 + c2⃗v2 + · · · + cn⃗vn
where the c1 , c2 , . . . , cn are scalars called the coefficients of the linear combina-
tion.
Given a collection of vectors ⃗v1 , . . . , ⃗vn in Rm , we want to be able to:
(1) Determine whether a fixed vector w
⃗ is a linear combination of ⃗v1 , . . . , ⃗vn , and
(2) Describe the set of all linear combinations of the vectors ⃗v1 , . . . , ⃗vn .
Proposition 2.7 resolves the first problem, since we have a method to solve any
system of linear equations from our work in Chapter 2. The second problem will
take a little more work. We define the following.
Definition 2.9. The span of vectors ⃗v1 , ⃗v2 , . . . , ⃗vn in Rm is the set
Span(⃗v1 , . . . , ⃗vn ) = {c1⃗v1 + · · · + cn⃗vn | c1 , c2 , . . . , cn ∈ R}.
That is Span(⃗v1 , . . . , ⃗vn ) is the set of all linear combinations of vectors ⃗v1 , . . . , ⃗vn .
Let’s revisit our flight navigation problem.

Lecture Activity 2.4 (Flight Navigation II). You are piloting an air-
plane equipped with four fixed-direction thrusters that assist in maneuver-
ing. Each thruster provides thrust in a specific, constant direction and can
be fired forward or in reverse for any number of seconds.
• Firing Thruster A for one second in the forward direction moves the
airplane 10 meters East, 9 meters North, and 2 meters Up. Firing
Thruster A for one second in the backward direction has the opposite
effect; that is, moves the airplane 10 meters West, 9 meters South, and
2 meters Down.
• Firing Thruster B for one second in the forward direction moves the
airplane 4 meters East, 7 meters North, and 1 meters Up. Firing B in
reverse has the opposite effect.
2.4. Linear Dependence and Independence 27

• Firing Thruster C for one second in the forward direction moves the
airplane 0 meters East, 2 meter North, and 3 meter Up. Firing C in
reverse has the opposite effect.
• Firing Thruster D for one second in the forward direction moves the
airplane 2 meter East, 5 meters South, and 0 meters Up. Firing D in
reverse has the opposite effect.
In this problem, we will explore what these thruster directions imply about
the airplane’s maneuverability in 3 dimensional space.
P1. Show that you can reach any waypoint using all four thrusters.
P2. Show that you can reach any waypoint using only Thrusters A, B, C.
P3. Do you think it’s possible to reach any waypoint using only two
Thrusters?

2.4. Linear Dependence and Independence

Let ⃗a, ⃗b, ⃗c, d⃗ be the vectors associated to Thrusters A, B, C and D from Lecture
Activity 2.4, respectively. In our investigation, we found that d⃗ ∈ Span(⃗a, ⃗b, ⃗c) and
so including Thruster D was “redundant”. That is, Thruster D didn’t really help
with our navigation, since we could just use a combination of Thrusters A, B and
C to reach the same waypoints. Understanding redundancies of this type will turn
out to be key to understanding spans. Let’s add a new definition to help develop
this theory further.
Definition 2.10. A set of vectors {⃗v1 , ⃗v2 , . . . , ⃗vn } in Rm is called linearly de-
pendent if at least one of the vectors is a linear combination of the others. That
is, for at least one i ∈ {1, . . . , n} we have
⃗vi ∈ Span(⃗v1 , ⃗v2 , . . . , ⃗vi−1 , ⃗vi+1 , . . . , ⃗vn ).
Otherwise, the vectors are called linearly independent.

Lecture Activity 2.5. Use the definition of linear dependence to determine

which of the sets are linearly dependent and which are linearly independent.
For the sets that are linearly dependent, demonstrate how to write one of
the vectors
as
 a linear
  combination
   ofthe others.
 −1 1 −1 
P1. S =  4  ,  2  ,  0  ,
 0  −3 2
 
  
 1 −1 3 
P2. T = 1 ,  2  , 1 .
0 0 2
 

Checking for linear dependence using the definition can lead to long calculations.
The following result will simplify this calculation significantly.
Theorem 2.11. A set of vectors {⃗v1 , ⃗v2 , . . . , ⃗vn } in Rm is linearly dependent if and
only if the vector equation
x1⃗v1 + x2⃗v2 + · · · + xn⃗vn = ⃗0
28 2. Vectors in Euclidean Space

has a “nontrivial” solution; that is, a solution other than (x1 , x2 , . . . , xn ) = (0, 0, . . . , 0).

Proof. Suppose that the set {⃗v1 , ⃗v2 , . . . , ⃗vn } is linearly dependent. By relabeling,
we may assume that ⃗v1 ∈ Span(⃗v2 , . . . , ⃗vn ). So, there are real numbers c2 , . . . , cn
so that
⃗v1 = c2⃗v2 + · · · + cn⃗vn .
Subtracting both sides by ⃗v1 gives
−⃗v1 + c2⃗v2 + · · · + cn⃗vn = ⃗0.
Hence, the vector equation
x1⃗v1 + x2⃗v2 + · · · + xn⃗vn = ⃗0
has (x1 , . . . , xn ) = (−1, c2 , . . . , cn ) as a solution. Since x1 = −1 ̸= 0, this solution
is nontrivial, as needed.

Conversely, suppose that the vector equation

x1⃗v1 + x2⃗v2 + · · · + xn⃗vn = ⃗0
has a nontrivial solution (c1 , c2 , . . . , cn ). Then, one of the ci is nonzero. By rela-
beling, we may assume that c1 ̸= 0. This gives
c1⃗v1 = −c2⃗v2 − · · · − cn⃗vn
and so dividing on both sides by c1 (which we can do since we know c1 is nonzero)
gives
c2 cn
⃗v1 = − ⃗v2 − · · · − ⃗vn ∈ Span(⃗v2 , . . . , ⃗vn ).
c1 c1
Hence, ⃗v1 ∈ Span(⃗v2 , . . . , ⃗vn ), and so the set {⃗v1 , ⃗v2 , . . . , ⃗vn } is linearly dependent.
□

Lecture Activity 2.6. Use Theorem 2.11 to determine which of the fol-
lowing sets are linearly dependent and which are linearly independent.
      
 1 −1 −1 
P1. S =  2  ,  4  ,  0 
−3 0 2
 
    
 1 3 −1 
P2. T = 1 , 1 ,  2 
0  2   0  
 

 1 1 0 1 
       
0 0 0 −1

P3. U =  , , , 
0 1 1  0 

 
0 0 1 0
 

We can summarize our strategy from Lecture Activity 2.6 as follows.

Proposition 2.12. A set of vectors {⃗v1 , ⃗v2 , . . . , ⃗vn } in Rm is linearly independent
if and only if the reduced row echelon form of the matrix


⃗v1 ⃗v2 · · · ⃗vn
has a pivot in every column.
Exercises 29

Proof. Suppose that the set {⃗v1 , ⃗v2 , . . . , ⃗vn } is linearly independent. Then, by
Theorem 2.11 the vector equation
x1⃗v1 + x2⃗v2 + · · · + xn⃗vn = ⃗0
only has the trivial solution. This equation has the same solution set as the system
of linear equations with augmented matrix
⃗v1 ⃗v2 · · · ⃗vn ⃗0 .

Since this equation has the trivial solution (x1 , x2 , . . . , xn ) = (0, 0, . . . , 0), it is
consistent. Hence, by Rouché-Capelli, the reduced row echelon form of the matrix


⃗v1 ⃗v2 · · · ⃗vn
must have a pivot in every column, as needed.

Conversely, suppose that the reduced row echelon form of the matrix


⃗v1 ⃗v2 · · · ⃗vn
has a pivot in every column. Then, by Rouché-Capelli, the system of linear equa-
tions with augmented matrix
⃗v1 ⃗v2 · · · ⃗vn ⃗0

only has one solution. Since (0, 0, . . . , 0) is always a solution to this equation, it
must be the only solution. So, the vector equation
x1⃗v1 + x2⃗v2 + · · · + xn⃗vn = ⃗0
only has the trivial solution. Therefore, by Theorem 2.11, the set {⃗v1 , . . . , ⃗vn } is
linearly independent. □

In the following Chapter, we’ll continue investigating our second motivating prob-
lem: how can we describe the span of a set of vectors?

Exercises
P2.1 True or False: For vectors ⃗u and ⃗v in R2 , if Span(⃗u, ⃗v ) = R2 then
Span(⃗u, ⃗u + ⃗v ) = R2 .
If true, provide a proof. If false, provide a counterexample and justify why
this is a counterexample.
⃗ in R3 , if Span(⃗u, ⃗v , w)
P2.2 True or False: For vectors ⃗u, ⃗v , w ⃗ = R3 then
⃗ = R3 .
Span(⃗u + ⃗v , ⃗v + w)
If true, provide a proof. If false, provide a counterexample and justify why
this is a counterexample.
P2.3 Give an example for each of the following, if possible. If it is not possible to
construct an example, explain why not.
(a) Three linearly independent vectors in R4 .
(b) Three linearly dependent vectors in R4 .
(c) Three linearly independent vectors in R2 .
30 2. Vectors in Euclidean Space

(d) Four linearly independent vectors in R3 .

(e) A 4 × 3 matrix with linearly independent columns.
(f) A 3 × 4 matrix with linearly independent columns.
P2.4 True or False: if m < n, then any set of vectors ⃗v1 , . . . , ⃗vn in Rm are linearly
dependent. If true, provide a proof. If false, provide a counterexample and
justify why this is a counterexample.
P2.5 True or False: If ⃗v1 , ⃗v2 , ⃗v3 , ⃗v4 are linearly dependent vectors in Rn , then
⃗v1 , ⃗v2 , ⃗v3 are also linearly dependent. If true, provide a proof. If false, provide
a counterexample and justify why this is a counterexample.
⃗ be a set of linearly independent vectors in Rn . Determine
P2.6 Let {⃗u, ⃗v , w}
whether the following sets of vectors are linearly dependent or independent,
and justify your answer.
(a) {⃗u − ⃗v , ⃗v − w,
⃗ w⃗ − ⃗u}
(b) {⃗u + ⃗v , ⃗v + w,
⃗ w⃗ + ⃗u}
 Chapter 3

Vector Subspaces of Rn

3.1. Vector Spaces

Let’s look at our flight navigation problem through a geometric lens. Note that
the images below have been captured from this this Desmos example. In Lecture
Activity 2.4, our airplane had four thrusters represented by the vectors
       
10 4 0 2
⃗a =  9  , ⃗b = 7 , ⃗c = 2 , and d⃗ = −5 .
2 1 3 0
Let’s use geometric reasoning to see what waypoints we can reach with these
thrusters. Our thruster vectors are graphed below on the xyz-plane, where the
positive x axis is pointing East, the positive y axis is pointing North, and the
positive z-axis is pointing Up.

If we use only one thruster, we see that we’re restricted to traveling along the
line pointing in that thruster’s direction. If we use two thrusters, we can argue
geometrically that we’re restricted to traveling in a plane. For example, we see
that Span(⃗a, ⃗b) gives the plane drawn below

31
32 3. Vector Subspaces of Rn

We can see that d⃗ is contained in this plane, which is why Thruster D doesn’t
contribute anything to our flight.

But when we include Thruster C, we get an extra direction that allows us to traverse
all of 3-D space

Observe in the examples above that our spans gave us either a line, a plane, or
all of R3 . One could use geometric reasoning to argue that the span of any set of
nonzero vectors in R3 is either a line, a plane, or all of R3 . However, in higher
dimensions, we don’t have geometric notions of lines and planes. In order to extend
3.1. Vector Spaces 33

this reasoning, we need to algebraically capture these subsets of R3 .

Note the following.

• Lines in R3 look like “copies of” R1 – that is, a line in R3 looks a lot like 1-D
space, placed somewhere in R3
• Planes in R3 look like “copies of” R2 – that is, a plane in R3 looks a lot like
2-D space, placed in R3
That is, spans in R3 all look a lot like “copies of” Euclidean space. To formalize
what we mean by “copies of” Euclidean space, let’s recall our definitions.
Recall that we defined n-dimensional Euclidean space Rn to be the space consisting
⃗ ∈ Rn and
of all n-dimensional vectors, and furthermore for each pair of vectors ⃗v , w
n n
scalar c ∈ R we defined new vectors ⃗v + w ⃗ ∈ R and c⃗v ∈ R . So, if we want a
subset of Rn to “behave” like Euclidean space, it better be well-defined with respect
to these operations. We define the following.

Definition 3.1. A vector space (over the real numbers) is any set of vectors V
in Rn that satisfies all of the following properties:
(1) V is nonempty;
⃗ ∈ V we have ⃗v + w
(2) V is closed under vector addition: for all ⃗v , w ⃗ ∈V;
(3) V is closed under scalar multiplication: for all ⃗v ∈ V and c ∈ R we have
c⃗v ∈ V .
If V is a subset of Rn and is also a vector space, we call V a vector subspace of
Rn . In this case, we refer to Rn as the ambient space.

Lecture Activity 3.1. Determine which of the following sets are vector
subspaces of the given ambient space and which are not. Justify your answer.
P1. The subsets of R2 drawn below (note that the set S2 in the second
image is meant to extend infinitely in all directions)

S1 S2

S3 S4
34 3. Vector Subspaces of Rn

  
2 x
P2. The subset U of R defined by U = :x∈R
1
  
2x
P3. The subset V of R2 defined by V = :x∈R
0
  
 x−y 
P4. The subset W of R3 defined by W = x + y + 2z  : x, y, z ∈ R
y+z
 

The following proposition tells us that the span of a set of vectors satisfies the “self
containment” properties that the Euclidean spaces satisfy.
Proposition 3.2. The span of any set of vectors in Rn is a vector subspace of Rn .

Proof. Suppose that V = Span (⃗v1 , ⃗v2 , . . . , ⃗vm ) for vectors ⃗v1 , ⃗v2 , . . . , ⃗vm in Rn .
Observe that ⃗0 ∈ V since we can write
⃗0 = 0⃗v1 + · · · + 0⃗vm ,
and so V is not empty. Next, take any ⃗v , w
⃗ in V . Then we can write
⃗v = a1⃗v1 + · · · + am⃗vm
⃗ = b1⃗v1 + · · · + bm⃗vm
w
for scalars ai , bi ∈ R and so
⃗ = (a1 + b1 )⃗v1 + · · · + (am + bm )⃗vm ∈ Span(⃗v1 , . . . , ⃗vm ).
⃗v + w
⃗ ∈ V and so V is closed under vector addition. Finally, for any scalar
Hence, ⃗v + w
c ∈ R we have
c⃗v = (ca1 )⃗v1 + · · · + (cam )⃗vm ∈ Span(⃗v1 , . . . , ⃗vm ).
Hence, c⃗v ∈ V and so V is closed under scalar multiplication. Therefore, V is a
vector space. To see that V is a subset of Rn , note that each ⃗vi ∈ Rn and since Rn
is closed under scalar multiplication we know that ci⃗vi ∈ Rn for all i = 1, . . . , m.
Hence,
⃗v = c1⃗v1 + · · · + cm⃗vm ∈ Rn
for all ⃗v ∈ V and so V ⊆ Rn . □

The converse of Proposition 3.2 also turns out to be true.

Theorem 3.3. Every vector subspace of Rn is equal to the span of a set of vectors
in Rn .

Proof. Suppose that V is a vector subspace of Rn . Let B = {⃗v1 , ⃗v2 , . . . , ⃗vm } be a

linearly independent subset of V . By Chapter Exercise P3.1, we must have m ≤ n.
So, we may choose such a set B to be maximal with respect to linear independence.
That is, we can choose a large enough linearly independent set B so that if we add
any additional vectors from V to B, the set would be linearly dependent. We will
show that V = Span(B). First, observe that
Span(⃗v1 , ⃗v2 , . . . , ⃗vm ) ⊆ V,
3.2. Bases 35

since V is a vector space. For the opposite set inclusion, take any ⃗v ∈ V . If
⃗v = ⃗vi ∈ B then certainly ⃗v ∈ Span(⃗v1 , ⃗v2 , . . . , ⃗vm ) by writing
⃗v = 0⃗v1 + · · · + 1 · ⃗vi + · · · + 0⃗vm .
So, suppose that ⃗v ̸∈ Span(⃗v1 , ⃗v2 , . . . , ⃗vm ). Since we chose our set B to be maximal
with respect to linear independence, the set {⃗v1 , ⃗v2 , . . . , ⃗vm , ⃗v } must be linearly de-
pendent. So, by Theorem 2.11 there exists a nontrivial solution (c1 , . . . , cm , cm+1 )
to the vector equation
(3.1) x1⃗v1 + · · · + xm⃗vm + xm+1⃗v = ⃗0.
Note that, if cm+1 = 0 then we would have a nontrivial solution (c1 , . . . , cm ) to the
vector equation
x1⃗v1 + · · · + xm⃗vm = ⃗0,
which contradicts the fact that B = {⃗v1 , . . . , ⃗vm } was chosen to be linearly inde-
pendent. So, we must have cm+1 ̸= 0. Plugging (c1 , . . . , cm , cm+1 ) into Equation
(3.1) gives
−cm+1⃗v = c1⃗v1 + c2⃗v2 + · · · + cm⃗vm ,
and so dividing by −cm+1 (which we can do since cm+1 ̸= 0) gives
−1
⃗v = (c1⃗v1 + c2⃗v2 + · · · + cm⃗vm ) .
cm+1
Hence, V = Span(⃗v1 , . . . , ⃗vm ), as needed. □

We define the following.

Definition 3.4. Let V be a vector subspace of Rn . A spanning set (also known
as a generating set) for V is any subset B of V so that V = Span(B).

Observe that Theorem 3.3 gives us another method to detect whether a subset of
Rn is a vector space.

Lecture Activity 3.2. Show that the following sets are vector spaces by
finding a generating set. Compare with your work in Lecture Activity 3.1
  
2x
P1. V = :x∈R
0
  
 x−y 
P2. W = x + y + 2z  : x, y, z ∈ R
y+z
 

3.2. Bases
In the flight navigation problem from Lecture Activity 2.4, we saw that the set
V = Span(⃗a, ⃗b, d)
⃗ described a plane in R3 , even though it was generated by three
vectors. The reason for this was that the vector d⃗ is a linear combination of the
others, and so the smaller set {⃗a, ⃗b} was sufficient to define the same space. This
highlights a key observation: to understand vector spaces, it is useful to find a
minimal spanning set. We define the following.
36 3. Vector Subspaces of Rn

Definition 3.5. A subset B of a vector space V is called a basis if

(1) B is a spanning set for V , and
(2) B is linearly independent.

Lecture Activity 3.3. Determine which of the following sets are bases
for R3 .
     
 1 0 1 
B1 = 1 , 1 , 2
1 1 2
 
   
 1 0 
B2 = 0 , 1
0 0
 
     
 1 0 0 
B3 = 0 , 1 , 0
0 0 1
 
     
 1 1 0 
B4 = 0 , 1 , 0
1 0 1
 

Observe that the bases for R3 in Lecture Activity 3.3 all contain three elements.
Let’s show that this is always the case.
Proposition 3.6. If B is a basis for R3 , then B contains three elements.

Proof. Let B be any basis for R3 . First, let’s show that B can contain at most
three elements. To see this, suppose that B = {⃗b1 , . . . , ⃗bd } contains d elements.
Since B is linearly independent, the vector equation
x1⃗b1 + x2⃗b2 + · · · + xn⃗bn = ⃗0
only has the trivial solution. This vector equation has the same solution set as a
consistent system of linear equation with coefficient matrix
 
A = ⃗b1 ⃗b2 · · · ⃗bd .
By Rouché-Capelli, we know that rref(A) must have a pivot in all d columns. Fur-
thermore, since ⃗bi ∈ R3 , we know that A has size 3 × d. Since a matrix can have at
most one pivot in every row, we must have d ≤ 3.

Next, let C = {⃗c1 , ⃗c2 , ⃗c3 } be a basis for R3 which is known to contain three elements
(note that such a basis exists by our work in Lecture Activity 3.3). For a contra-
diction, suppose that B = {⃗b1 , ⃗b2 } contains two elements. Since B is a basis, it is a
spanning set for R3 and so ⃗ci ∈ Span(B) for i = 1, 2, 3. So, we can write
⃗c1 = a1⃗b1 + a2⃗b2
3.2. Bases 37

⃗c2 = a3⃗b1 + a4⃗b2

⃗c3 = a5⃗b1 + a6⃗b2
where the ai are real numbers. Now, consider the vector equation
(3.2) x1⃗c1 + x2⃗c2 + x3⃗c3 = ⃗0.
Substituting our expression for ⃗ci in terms of the ⃗bi into the equation above gives
⃗0 = x1 (a1⃗b1 + a2⃗b2 )

+ x2 (a3⃗b1 + a4⃗b2 )
+ x3 (a5⃗b1 + a6⃗b2 )

Rearranging this equation to collect the coefficients of the ⃗bi gives

⃗0 = (x1 a1 + x2 a3 + x3 a5 )⃗b1

+ (x1 a2 + x2 a4 + x3 a6 )⃗b2 .
But since B is a basis, the coefficients of the equation above must be equal to zero.
That is, we must satisfy the system of linear equations
x1 a1 + x2 a3 + x3 a5 = 0


x1 a2 + x2 a4 + x3 a6 = 0
which is a consistent system with coefficient matrix
 
a1 a3 a5
A= .
a2 a4 a6
But, since A has more columns than rows, rref(A) must have a column without a
pivot. Hence, by Rouché-Capelli, this system has infinitely many solutions. That
is, Equation (3.2) has a nontrivial solution. But this contradicts the fact that C is
a basis! So, we cannot have a basis for R3 containing two elements.

We leave it as an exercise to the reader to show that R3 cannot have a basis with
one element, and so B must contain exactly three elements, as needed. □

The fact that we need three basis elements for 3-D space is no accident, and should
match our geometric intuition. The following theorem will move us toward our
understanding of vector spaces as sets that “behave like” Euclidean space.
Theorem 3.7. Let V be a nonzero vector subspace of Rn with basis B. If B contains
d elements, then any other basis for V also contains d elements.

The proof of this Theorem will follow similarly to Proposition 3.6. While the follow-
ing proof is not required material for the course, interested students are encouraged
to read through it in detail.

Proof. Suppose that V is a vector subspace of Rn with bases

B = {⃗b1 , ⃗b2 , . . . , ⃗bd }, and C = {⃗c1 , ⃗c2 , . . . , ⃗ck }.
38 3. Vector Subspaces of Rn

We need to show that k = d. Since B is a basis, we know that ⃗ci ∈ V = Span(B)

for all i = 1, . . . , k. So, we can write

⃗c1 = a11⃗b1 + a12⃗b2 + · · · + a1d⃗bd

⃗c2 = a21⃗b1 + a22⃗b2 + · · · + a2d⃗bd
..
.
⃗ck = ak1⃗b1 + ak2⃗b2 + · · · + akd⃗bd .

Since {⃗c1 , . . . , ⃗ck } is also a basis for V , we know that this set is linearly independent.
So, the vector equation

(3.3) x1⃗c1 + · · · + xk⃗ck = ⃗0

only has the trivial solution. Substituting our expression for ⃗ci in terms of the
elements of B into the equation above gives
⃗0 = x1 (a11⃗b1 + a12⃗b2 + · · · + a1d⃗bd )

+ x2 (a21⃗b1 + a22⃗b2 + · · · + a2d⃗bd )

..
.
+ xk (ak1⃗b1 + ak2⃗b2 + · · · + akd⃗bd ).

Rearranging this equation to collect the coefficients of ⃗b1 , . . . , ⃗bd gives

⃗0 = (x1 a11 + x2 a21 + · · · + xk ak1 )⃗b1

+ (x1 a12 + x2 a22 + · · · + xk ak2 )⃗b2

..
.
+ (x1 a1d + x2 a2d + · · · + xk akd )⃗bd .

But since {⃗b1 , . . . , ⃗bd } is a basis, this set is linearly independent, and so the coef-
ficients of ⃗b1 , . . . , ⃗bd in the equation above must all be equal to 0. This gives the
following system of linear equations
x a + x a + · · · + x a = 0
 1 11 2 21 k k1

 x1 a12 + x2 a22 + · · · + xk ak2 = 0


..


 .

x1 a1d + x2 a2d + · · · + xk akd = 0.


This system of linear equation has coefficient matrix of size d × k given by

 
a11 a21 · · · ak1
a12 a22 · · · ak2 
A= . ..  .
 
.. ..
 .. . . . 
a1d a2d ··· akd
3.3. Finding Bases 39

Observe that if k > d then rref(A) would have a column without a pivot, and so
by Rouché-Capelli we would have a nontrivial solution to Equation 3.3. This con-
tradicts the fact that C is linearly independent, and so we must have k ≤ d.

The argument above can be repeated by writing the elements of B in terms of C to

conclude that d ≤ k as well. So, we must have k = d as needed. □

Theorem 3.7 gives rise to the following definition.

Definition 3.8. Let V be a nonzero vector subspace of Rn . Then, the dimension
of V , denoted dim V , is equal to the size of any basis for V .

Note that Proposition 3.3 guarantees every vector space V has a spanning set. In
the next section, we’ll show that every nonzero vector space in fact has a basis,
and hence the dimension is well-defined. Furthermore, we’ll develop a method to
find the basis for any given vector space. Before we do that, let’s make sure our
notion of dimension matches our expectations for Euclidean space. We define the
following.
Definition 3.9. The standard basis for Rn is the set E := {⃗e1 , ⃗e2 , . . . , ⃗en } where
⃗ei is the vector with 1 in the ith coordinate and 0 in all other coordinates. That is,
     
1 0 0
0 1 0
⃗e1 =  .  , ⃗e2 =  .  , . . . , ⃗en =  .  .
     
 ..   ..   .. 
0 0 1

Lecture Activity 3.4. Show that the standard basis E is a basis for Rn .
Conclude that dim(Rn ) = n.

3.3. Finding Bases

By Proposition 3.3 we saw that every vector space has a generating set, and we saw
one strategy for finding generating sets for the vector spaces in Lecture Activity
3.2. In this section we develop a method to find a basis for a vector space given a
generating set.

Lecture Activity 3.5. In this problem we’ll find a basis for the vector
space W from Lecture Activities 3.1 and 3.2, defined by
  
 x−y 
W = x + y + 2z  : x, y, z ∈ R .
y+z
 

P1. Use your work from Lecture Activity 3.2 to observe that we can write
W = Span(⃗u, ⃗v , w).
⃗
40 3. Vector Subspaces of Rn

P2. Let A = ⃗u ⃗v w
⃗ and observe that
 
1 0 1
rref(A) = 0 1 1 .
0 0 0
Use this calculation to show that w ⃗ ∈ Span(⃗u, ⃗v ).
P3. Use P2 to show that Span(⃗u, ⃗v , w)
⃗ = Span(⃗u, ⃗v ).
P4. Use your work in the previous parts to find a basis for W . Then, find
the dimension of W .

The following result generalizes our observations from Activity 3.5.

Lemma 3.10. Let A be an m × n matrix of the form

A = ⃗v1 ⃗v2 · · · ⃗vn

where the ⃗vi are vectors in Rm . If the nth column of rref(A) does not have a pivot,
then the vector ⃗vn is in Span(⃗v1 , ⃗v2 , . . . , ⃗vn−1 ).

Proof. Consider the vector equation

(3.4) x1⃗v1 + +x2⃗v2 + · · · + xn−1⃗vn−1 = ⃗vn .

Note that A = ⃗v1 · · · ⃗vn is the augmented matrix of the corresponding system
of linear equations. Since there is no pivot in the nth column of rref(A), then by
Rouché-Capelli (Theorem 1.27) we know this system is consistent. That is, there
exists (at least one) real number solution (c1 , . . . , cn−1 ) to Equation 3.4, which gives

⃗vn = c1⃗v1 + · · · + cn−1⃗vn−1 ∈ Span(⃗v1 , . . . , ⃗vn−1 ),

as needed. □

By repeated use of Lemma 3.10 we obtain the following.

Theorem 3.11 (Finding Bases). Let V be the vector subspace of Rm given by

V = Span(⃗v1 , . . . , ⃗vn ).


and let A = ⃗v1 · · · ⃗vn . If columns i1 , i2 , . . . , ik of rref(A) have a pivot, then
the set {⃗vi1 , ⃗vi2 , . . . , ⃗vik } is a basis for V . Furthermore, if rref(A) has k pivots, then
dim(V ) = k.

Proof. By relabeling, we may assume that rref(A) has a pivot in the first k
columns. If k = n then we’re done, so suppose that k < n. Then rref(A) does
not have a pivot in the last column, and hence by Lemma 3.10 we have

⃗vn ∈ Span(⃗v1 , . . . , ⃗vn−1 ).

Hence, we can write

⃗vn = c1⃗v1 + · · · + cn−1⃗vn−1 .
3.3. Finding Bases 41

We claim that Span(⃗v1 , . . . , ⃗vn ) = Span(⃗v1 , . . . , ⃗vn−1 ). First, take any ⃗v ∈ Span(⃗v1 , . . . , ⃗vn ).
Then there are real numbers di ∈ R so that
⃗v = d1⃗v1 + · · · + dn−1⃗vn−1 + dn⃗vn
= d1⃗v1 + · · · + dn−1⃗vn−1 + dn (c1⃗v1 + · · · + cn−1⃗vn−1 )
= (d1 + c1 )⃗v1 + · · · + (dn−1 + cn−1 )⃗vn−1
∈ Span(⃗v1 , . . . , ⃗vn−1 ),
Hence, Span(⃗v1 , . . . , ⃗vn ) ⊆ Span(⃗v1 , . . . , ⃗vn−1 ). Conversely, take any w
⃗ ∈ Span(⃗v1 , . . . , ⃗vn−1 ).
Then, there are real numbers ai ∈ R so that
⃗ = a1⃗v1 + · · · + an−1⃗vn−1
w
= a1⃗v1 + · · · + an−1⃗vn−1 + 0⃗vn
∈ Span(⃗v1 , . . . , ⃗vn ).
Hence, Span(⃗v1 , . . . , ⃗vn−1 ) ⊆ Span(⃗v1 , . . . , ⃗vn ) and so we obtain the desired set
equality. Next, if k > 1 we can repeat the argument above n − k times to obtain
Span(⃗v1 , . . . , ⃗vn ) = Span(⃗v1 , . . . , ⃗vn−1 )
= Span(⃗v1 , . . . , ⃗vn−2 )
..
.
= Span(⃗v1 , . . . , ⃗vk ).
Thus, {⃗v1 , . . . , ⃗vk } is a generating set for V . Finally, note that


rref ⃗v1 · · · ⃗vk
has a pivot in every column, and so {⃗v1 , . . . , ⃗vk } is linearly independent, and hence
is a basis for V , which gives dim V = k. □

Lecture Activity 3.6. Find a basis for the following vector spaces, and
state their dimension.

    
2 1 0
P1. V = Span  1  ,  0  , 1
−1   −1  1 

1 3 1 7
0 0 1  2 
P2. W = Span 
2 , 6 , 1 , 12
       

1 3 1 7

Note that Theorem 3.11 gives us one strategy to find a basis for a vector space.
The following result tells us that if we know the dimension of a given vector space,
any set of linearly independent elements containing that many elements will yield
a basis.
Theorem 3.12. Let V be a vector space with dim V = d. If B is a linearly inde-
pendent subset of V containing d elements, then B is a basis for V .
42 3. Vector Subspaces of Rn

The proof of this result rests on the following key Lemma.

Lemma 3.13. If W ⊆ V then dim W ≤ dim V .

Proof. Let {w ⃗ k } be a basis for W and {⃗v1 , . . . , ⃗vd } be a basis for V . We

⃗ 1, . . . , w
need to show that k ≤ d. Since W ⊆ V , we have that w ⃗ i ∈ W for i = 1, . . . , k. So,
there are real numbers aij ∈ R so that
⃗ 1 = a11⃗v1 + · · · + a1d⃗vd
w
..
.
⃗ k = ak1⃗v1 + · · · + akd⃗vd .
w
Now, consider the vector equation
(3.5) x1 w ⃗ k = ⃗0.
⃗ 1 + · · · + xk w
Substituting the w
⃗ i with their expressions in terms of the ⃗vi and rearranging gives
(x1 a11 + · · · + xk ak1 )⃗v1 + · · · + (x1 a1d + · · · + xk akd )⃗vd = ⃗0.
But since {⃗v1 , . . . , ⃗vd } is a basis, this set must be linearly independent, and so the
coefficients of the vector equation above must all be equal to 0. This yields the
system of linear equations
x a + · · · + xk ak1 = 0

 1 11

..

 .

x1 a1d + · · · + xk akd = 0.


Observe that this is a consistent system of linear equations with d × k coefficient

matrix  
a11 · · · ak1
A =  ... .. ..  .

. . 
a1d ··· akd
Now, if k > d then this matrix would have more columns than rows, and hence
rref(A) would have a column without a pivot. By Rouché-Capelli, this would give
a nontrivial solution to the system above, which yields a nontrivial solution to
Equation (3.5). But this contradicts the fact that {w ⃗ k } is a basis. Hence,
⃗ 1, . . . , w
we must have k ≤ d, as desired. □

Lemma 3.13 will yield Theorem 3.12, and is scaffolded as a Chapter Exercise.

3.4. The Trivial Space

We define the following.
Definition 3.14. The trivial vector subspace of Rn is the vector space {⃗0}
containing only the zero vector in Rn . When the ambient space Rn is understood
to be fixed, we just call {⃗0} the trivial space.
Exercises 43

Observe that the trivial space only has one spanning set given by {⃗0}. Unfortu-
nately, this set is not linearly independent. Indeed, we see that the vector equation
x⃗0 = ⃗0
has the nontrivial solution x = 2, for example. Hence, the trivial space does not
have a basis. For convenience, we set the following convention.
Definition 3.15. We define the dimension of the trivial space to be equal to zero,
and we define a basis for the trivial space to be the empty set ∅ = {}.

Exercises
P3.1 Let B = {⃗v1 , ⃗v2 , . . . , ⃗vm } be a set of vectors in Rn . Show that if m > n then
the set B is linearly dependent. (Note: you may not use Lemma 3.13 for
this problem).
P3.2 Show that a vector space V is nonempty if and only if ⃗0 ∈ V .
P3.3 Determine which of the following sets W is a subspace of Rn for the indicated
value of n. If W is a subspace, provide a proof. If not, explain why not.
  
 2x + y 
(a) W =  x − y  : x, y ∈ R in R3
x+y
 

  
x+1
(b) W = : x ∈ R in R2
x−1
  
 xy 
(c) W = xz  : x, y, z ∈ R in R3
yz
 

P3.4 Suppose that V and W are both vector subspaces of Rn . Let V + W be the
subset of Rn defined by
V + W = {⃗v + w
⃗ | ⃗v ∈ V and w
⃗ ∈ W }.
Show that V + W is a vector subspace of Rn
P3.5 True or False: if W and V are subspaces of Rn , then
W ∩ V := {⃗x ∈ Rn : ⃗x ∈ W and ⃗x ∈ V }
is a subspace of Rn . If true, provide a proof. If false, provide a counterexample
and justify why this is a counterexample.
P3.6 True or False: if W and V are subspaces of Rn , then
W ∪ V := {⃗x ∈ Rn : ⃗x ∈ W or ⃗x ∈ V }
is a subspace of Rn . If true, provide a proof. If false, provide a counterexample
and justify why this is a counterexample.
 44 3. Vector Subspaces of Rn

P3.7 In this problem, we’ll see how to use Lemma 3.13 to prove Theorem 3.12.
Throughout the problem, we assume that V is a vector space with dim V = d
and that {⃗v1 , . . . , ⃗vd } is a linearly independent subset of V .
(a) Show that Span(⃗v1 , . . . , ⃗vd ) ⊆ V .
(b) Take any ⃗v ∈ V and consider the subspace W = Span(⃗v1 , . . . , ⃗vd , ⃗v ). Let


A = ⃗v1 ⃗v2 · · · ⃗vd ⃗v .
Show that if rref(A) does not have a pivot in the last column, then
⃗v ∈ Span(⃗v1 , . . . , ⃗vd ).
(c) Let A be the matrix from part (b). Show that if rref(A) has a pivot in
the last column, then dim(W ) > d.
(d) Use Lemma 3.13, along with your work in the previous parts, to conclude
that V = Span(⃗v1 , . . . , ⃗vd ).
(e) Explain how your conclusion from part (d) proves Theorem 3.12.
P3.8 Let V be a vector subspace of Rn . Show that if V contains a nonzero element,
then V contains infinitely many elements. Conclude that the trivial space is
the only finite vector subspace of Rn .
P3.9 Let V be a vector subspace of Rn of dimension 1 ≤ m < n and suppose that
B is a basis for V . Show that if ⃗v in Rn is not an element of V , then the set
B ∪ {⃗v } is linearly independent. (Note: you may not use Lemma 3.13 for
this problem).
P3.10 Let V be a vector subspace of Rn of dimension m ≥ 1. Show that any basis
B for V can be extended to a basis for Rn . That is, if B is a basis for V , show
that there exist a basis C for Rn with B ⊆ C.
P3.11 Let V and W be vector subspaces of R5 with V ∩ W = {⃗0}. Suppose that
V has basis {⃗v1 , ⃗v2 } and W has basis {w ⃗ 2 }. Find a basis for the vector
⃗ 1, w
space V + W , and justify how you know this is a basis.
P3.12 True or False: If V and W are vector subspaces of Rn , then
dim(V + W ) = dim(V ) + dim(W ).
If true, provide a proof. If false, provide a counterexample and justify why
this is a counterexample.
P3.13 Is it possible to find two vector subspaces V and W of R3 with V ∩ W = {⃗0}
so that dim V = dim W = 2? If it is possible, give an example and justify
that your example satisfies these conditions. If it is not possible, explain why
not.
 Chapter 4

Linear Transformations

4.1. Matrix Transformations

In this section, we introduce some new notation which will add a key perspective
to our story this semester. We define the following.


Definition 4.1. Let A be an m×n matrix with column vectors A = ⃗v1 ⃗v2 · · · ⃗vn .
Then, for a vector ⃗x in Rn the matrix-vector product of A and ⃗x is the vector
in Rm defined by
A⃗x := x1⃗v1 + x2⃗v2 + · · · + xn⃗vn .

Observe that the matrix-vector product gives us a new way to write linear combi-
nations of vectors. Let’s practice using this new notation.

Lecture Activity 4.1. Consider the matrices

 
1 2  
3 −1 1
A =  0 1 and B = .
2 0 1
−1 1
 
2
P1. Calculate the matrix-vector product A⃗x where ⃗x = .
1
 
1
P2. Calculate the matrix-vector product B⃗y where ⃗y = 2 .
3
P3. Let ⃗x and ⃗y be as in the previous problems. Explain why the matrix-
vector products A⃗y and B⃗x are not defined.
P4. Let ⃗z be a vector in R2 . How many components does the vector A⃗z
have?
P5. Let w⃗ be a vector in R3 . How many components does the vector B w ⃗
have?

45
46 4. Linear Transformations

Observe that if A is an m × n matrix, then for the matrix-vector product A⃗x to be

defined (as in Definition 4.1) we must have ⃗x ∈ Rn . Furthermore, for ⃗x ∈ Rn the
matrix-vector product A⃗x is a linear combination of the column vectors of A (which
has m rows), and hence is a vector in Rm . This tells us that every m × n matrix
has an associated function mapping from Rn to Rm . We define the following.
Definition 4.2. Let A be an m × n matrix. Then, the matrix transformation
associated to A is the function TA : Rn → Rm defined by TA (⃗x) := A⃗x.
Example 4.3. Observe that the matrix A from Lecture Activity 4.1 defines the
matrix transformation TA : R2 → R3 given by
 
  x + 2y
x
TA =  y .
y
−x + y
Note that the words “transformation” and “function” are synonyms, but our choice
of language here is intentional. It will be useful for us to imagine how our functions
transform the domain space.

Lecture Activity 4.2. In the images below, we’ve plotted where the in-
dicated function sends the standard coordinate grid for R2 . What do you
notice?
     
2 1 x x + sin(y)
TA where A = F =
1 2 y y

√ √ 
2 −√ 2   
x + y2

TB where B = √ G
x
=
2 2 y y

 
1 1    
TC where C = x x + |y|
1 1 H =
y y
4.2. Linearity 47

4.2. Linearity
In the last section, we saw that a matrix defines a function between Euclidean
spaces, and through example we conjectured that these functions “preserve lines”.
Let’s explore the family of functions with this property. We define the following.
Definition 4.4. A function F : Rn → Rm is called linear if it satisfies the
⃗ ∈ Rn and scalars c ∈ R:
following two properties for all vectors ⃗v , w
(1) F (⃗v + w)
⃗ = F (⃗v ) + F (w),
⃗ and
(2) F (c⃗v ) = cF (⃗v )
Remark 4.5. Let’s make sure this is the right definition to capture our geometric
observations, staying in 2-dimensional space for clarity. Note that a line in R2 can
be written in vector form as L = {⃗ p + td⃗ : t ∈ R} as demonstrated in the image
below
L

d⃗

p⃗

If F : R2 → R2 is linear, observe that F sends the line L to

{F (⃗ ⃗ : t ∈ R}
p) + tF (d)
which is either a line or a point (depending on whether F (d) ⃗ = ⃗0 or not). Hence,
linear functions “preserve lines”. Note that we’ll allow lines to be sent to points (as
we saw with TC from Lecture Activity 4.2), but we do not want to introduce kinks
or curves to lines. Furthermore, observe that our linearity property guarantees the
origin stays fixed (which you’ll show in Chapter Exercise 4.1).

Lecture Activity 4.3. Determine which of the following are linear trans-
formations. Give a formal justification for your answer by showing that the
function does or does not satisfy the conditions of Definition 4.4.
P1. F : R2 → R2 defined by
   2 
x x
F =
y y2
P2. G : R2 → R2 defined by
   
x x+y
G = .
y x


P3. TA : R2 → R2 where A = ⃗v1 ⃗v2 is any 2 × 2 matrix.

The following observation will formally capture our geometric observations from
Lecture Activity 4.2, and will generalize what we showed in P3 above.
48 4. Linear Transformations

Proposition 4.6. Every matrix transformation is a linear transformation.

Proof. Let A be an m × n matrix, and write A = ⃗v1 · · · ⃗vn . Take any vectors
   
x1 y1
 x2   y2 
⃗v =  .  and w ⃗ = . 
   
 ..   .. 
xn yn
in Rn . Then we have
TA (⃗v + w)
⃗ = A(⃗v + w)
⃗
 
x1 + y1
 x2 + y2 
= A
 
.. 
 . 
xn + yn
= (x1 + y1 )⃗v1 + (x2 + y2 )⃗v2 + · · · + (xn + yn )⃗vn
= (x1⃗v1 + x2⃗v2 + · · · + xn⃗vn ) + (y1⃗v1 + y2⃗v2 + · · · + yn⃗vn )
= A⃗v + Aw
⃗ = TA (⃗v ) + TA (w).
⃗

Now, take any c ∈ R. Then we have

TA (c⃗v ) = A(c⃗v )
 
cx1
 cx2 
= A . 
 
 .. 
cxn
= cx1⃗v1 + cx2⃗v2 + · · · + cxn⃗vn
= c(x1⃗v1 + x2⃗v2 + · · · + xn⃗vn )
= c(A⃗v ) = cTA (⃗v ),
as needed. □

Example 4.7. Our goal for the remainder of this section is to show that the
converse of Proposition 4.6 also holds. Let’s first look at an example where this
can be done without too much effort. Consider the function G : R2 → R2 from P2
of Lecture Activity 4.2. Observe that we can write
   
x x+y
G =
y x
   
x y
= +
x 0
   
1 1
=x +y
1 0
  
1 1 x
= .
1 0 y
4.2. Linearity 49

Hence, G = TM is the matrix transformation with

 
0 1
M= .
1 1
Note that the strategy from Example 4.7 only works when we’re provided with
an equation for a given linear function. Unfortunately, we currently don’t have
a method to detect whether a function is linear based solely on its equation. To
show that every linear transformation is in fact a matrix transformation, we’ll use
a slightly different strategy than what was demonstrated above.

Lecture Activity 4.4. Suppose that F : R2 → R2 is a linear transforma-

tion satisfying
       
1 1 0 1
F = and F = .
0 −1 1 2
   
1 2
P1. Find F and F .
1 3
 
x
P2. Find a formula for F .
y
P3. Find a 2 × 2 matrix M so that F (⃗x) = M⃗x for all vectors ⃗x ∈ R2 .

We have the following.

Theorem 4.8. Every linear transformation is a matrix transformation. In partic-
ular, if F : Rn → Rm is linear, then F = TM where


M = F (⃗e1 ) F (⃗e2 ) · · · F (⃗en )
and {⃗e1 , . . . , ⃗en } is the standard basis for Rn defined in Definition 3.9.

Proof. Suppose that F : Rn → Rm is a linear transformation. Since {⃗e1 , ⃗e2 , . . . , ⃗en }

forms a basis for Rn we can write ⃗x = x1⃗e1 + x2⃗e2 + · · · + xn⃗en . This gives
F (⃗x) = F (x1⃗e1 + x2⃗e2 + · · · + xn⃗en )
= x1 F (⃗e1 ) + x2 F (⃗e2 ) + · · · + xn F (⃗en ) by linearity of F
 
x1
 x2 
= M  . ,
 
 .. 
xn


where M = F (⃗e1 ) F (⃗e2 ) · · · F (⃗en ) . Furthermore, observe that ⃗x has stan-
dard coordinate representation  
x1
 x2 
⃗x =  . 
 
 .. 
xn
Hence, F (⃗x) = M⃗x for every vector ⃗x ∈ Rn and so F = TM as needed. □

We define the following.

50 4. Linear Transformations

Definition 4.9. Let F : Rn → Rm be a linear transformation. Then, the defining

matrix of F is the m × n matrix M satisfying

F (⃗x) = M⃗x

for all vectors ⃗x in Rn .

Remark 4.10. We will often use the notation MF to denote the defining matrix
of a linear transformation F . Observe that MTM = M and TMF = F .

Lecture Activity 4.5. Let F : R2 → R2 be the transformation which

rotates every vector θ◦ counterclockwise about the origin.
P1. Use geometric reasoning to argue that F is a linear transformation.
P2. Find the defining matrix MF when θ = 90◦ .
P3. Find the defining matrix MF for any value of θ. Note that your matrix
will depend on the unknown angle θ.

Remark 4.11. Observe that we now have several representations for problems
with equivalent solution sets, as outlined in the diagram below.

Systems of Linear Equations Vector Equation

(      
x+y =a 1 1 a
x +y =
x−y =b 1 −1 b

Matrix transformation
Matrix-vector equation
   
x a
TA : R2 → R2 , 7→ ,
y b
    
1 1 x a
=
1 −1 y b
 
1 1
where A =
1 −1

Each of these representations offers a different perspective, and moving between

them will be a key strategy in this course. In particular, building a geometric un-
derstanding of how linear functions transform the domain space will be especially
helpful for solving the kinds of problems we’ve encountered. We’ll spend a signifi-
cant amount of time in the remainder of the course developing the tools needed to
do this effectively. In the next section, we take the first such step.
4.3. Injective and Surjective Functions 51

4.3. Injective and Surjective Functions

Example 4.12. Recall the example fromLecture
 Activity 4.3, where we saw that
1 1
the matrix transformation TC with C = transforms the domain space R2
1 1
as follows

Observe that TC appears to “compress” the domain space R2 down to a line. This
behavior is different from the other examples, where no such compression occurred.
In this section, we introduce some definitions that will help us distinguish between
these two kinds of transformations. These definitions will also allow us to extend
this geometric intuition to higher-dimensional spaces.

Let’s explore the behavior of our function TC more precisely. Observe that TC
sends many distinct points to the origin. For example, we have
       
1 0 2 0
TC : 7→ and 7→
−1 0 −2 0

   
a 0
and in fact TC : 7→ for any real number a. So, we see that all points
−a 0
on the line y = −x are “compressed” to the point ⃗0.

The following definition will help us capture this geometric feature of “compres-
sion”. Since you will likely encounter this definition in other contexts, we state it
in general for functions between arbitrary sets.
Definition 4.13. A function f : X → Y is called one-to-one (or injective) if
the following property holds: for every y ∈ Y , there is at most one input x ∈ X so
that f (x) = y. We often use the arrow f : X ,→ Y to indicate when a function is
injective.

Lecture Activity 4.6. Determine which of the following functions are

injective. Give a formal justification for your answer by showing that the
function does or does not satisfy the conditions of Definition 4.13.
P1. TA : R2 → R2 where  
1 0
A= .
0 1
52 4. Linear Transformations

P2. TB : R3 → R2 where
 
1 0 0
B= .
0 1 1
P3. TD : R2 → R3 where  
1 0
D = 0 1 .
0 0

Let’s generalize our observations from Lecture Activity 4.6.

Theorem 4.14. A linear transformation F is injective if and only if every column
of rref(MF ) has a pivot.

Proof. Let M = MF be the defining matrix of a linear transformation F : Rn →

Rm . By definition of the defining matrix, for any ⃗y ∈ Rm , the set of vectors ⃗x ∈ Rn
satisfying
F (⃗x) = ⃗y
is precisely the set of vectors satisfying the matrix-vector equation M⃗x = ⃗y . Ob-
serve that the matrix-vector equation M⃗x = ⃗y has the same solution set as the
system of linear equations with augmented matrix


M ⃗y .


By Rouché-Capelli, rref M ⃗y has a pivot in the last column if and only if the
system has no solutions. Otherwise, the system has exactly one solution if and only
if rref(M ) has a pivot in every column. Therefore, the system has at most one
solution if and only if rref(M ) has a pivot in every column, as needed. □
Example 4.15. Let’s explore one more geometric feature of our function TC from
Lecture Activity 4.3. Observe that TC maps vectors from R2 to R2 , but there are
many points in the codomain which are not mapped to. That is, TC “misses” many
of the points
  in the codomain.
  For  example, observe that there does not exist a
x x 1
vector so that T = . Indeed, we have
y y 2
   
1 1 1 1 1 1
rref = ,
1 1 2 0 0 1
 
1
and so the matrix-vector equation C⃗x = ⃗y does not have a solution when ⃗y = .
2

The following definition will help us capture this feature of “missing points” in the
codomain. Since you will likely encounter this definition in other contexts, we state
it in general for functions between arbitrary sets.
Definition 4.16. A function f : X → Y is called onto (or surjective) if the
following property holds: for every y ∈ Y , there is at least one input x ∈ X so
that f (x) = y. We often use the arrow f : X ↠ Y to indicate when a function is
surjective.
4.3. Injective and Surjective Functions 53

Lecture Activity 4.7. Determine which of the following functions are

surjective. Give a formal justification for your answer by showing that the
function does or does not satisfy the conditions of Definition 4.16.
(1) TA : R2 → R2 where  
1 0
A= .
0 1
(2) TB : R3 → R2 where
 
1 0 0
B= .
0 1 1
(3) TD : R2 → R3 where  
1 0
D = 0 1 .
0 0

Let’s generalize our observations from Lecture Activity 4.8.

Theorem 4.17. A linear transformation F is surjective if and only if every row

of rref(MF ) has a pivot.

This result can be proven using a pivot argument similar to Theorem 4.14. However,
there’s a slightly more intuitive way to see this which we will discuss in the next
Chapter after we develop a little more machinery. We will omit the proof below
from our class discussion, but we record it here for completeness.

Proof. Let M = MF be the defining matrix of a linear transformation F : Rn →

Rm . By definition of the defining matrix, for any ⃗y ∈ Rm , the set of vectors ⃗x ∈ Rn
satisfying
F (⃗x) = ⃗y
is precisely the set of vectors satisfying the matrix-vector equation M⃗x = ⃗y . Fur-
thermore, this equation has the same solution set as the system of linear equations
with augmented matrix


M ⃗y .

Since M is m × n, this tells

Suppose first that rref(M ) has a pivot in every row.
us that rref(M ) has m pivots. Now, if rref M ⃗y had a pivot in the last column,
then this matrix
would have m + 1 pivots. But this can’t take

place, since the ma-
trix rref M ⃗y still only contains m rows. So, rref M ⃗y does not have a pivot
in the last column, and hence the corresponding system has at least one solution
by Rouché-Capelli.

Conversely, suppose that rref(M ) does not have a pivot in every row. Then, the
last row of rref(M

) is a row of zeros, and hence we can find a vector ⃗y ∈ Rn so that
rref M ⃗y has a pivot in the last column, as needed. □
54 4. Linear Transformations

Lecture Activity 4.8. Use Theorems 4.14 and 4.17 to determine which of
the following functions are injective, surjective, or neither.
 
  x
x
P1. F : R2 → R3 , 7→ y 
y
  0 
x x−y
P2. G : R3 → R3 , y  7→  y + z 
z  x + z 
x x−y
P3. H : R3 → R3 , y  7→  y + z 
z z

4.4. Isomorphisms
We introduce one more general definition for an arbitrary function between sets.
Definition 4.18. A function f : X → Y is called bijective if it is both injective
and surjective.

Observe that if the sets X and Y are finite, a bijection can only exist between them
if they have precisely the same number of elements. This idea can be extended
to give a more nuanced way to discuss the “number” of elements in an infinite
set, called its cardinality. When we insist that our function satisfy the additional
property that it maps linearly between Euclidean spaces, we obtain an even stronger
result.

Lecture Activity 4.9. Show that a linear tranformation F : Rn → Rm

can be bijective if and only if n = m.

This proposition tells us that bijective linear functions can only map between “iden-
tical” Euclidean spaces. This idea applies to bijective linear maps between vector
spaces more generally. We define the following.
Definition 4.19. Let V be a subspace of Rn and W a subspace of Rm . An
isomorphism between V and W is any linear bijective map F : V → W . If an
isomorphism exists between two vector spaces, we say these spaces are isomorphic,
and we write V ∼
= W.

The following generalizes our observation from Lecture Activity 4.9.

Theorem 4.20. Let V and W be vector subspaces. Then V ∼
= W if and only if
dim(V ) = dim(W ).

We include the proof of this result below for completeness, but note that the proof
is not required material for the course.

Proof. Suppose that F : V → W is an isomorphism, and suppose that V has

basis {⃗v1 , . . . , ⃗vd }. Note that this implies dim(V ) = d. Let’s show that the set
4.4. Isomorphisms 55

{F (⃗v1 ), . . . , F (⃗vd )} is a basis for W . To see that this set is linearly independent,
suppose that
x1 F (⃗v1 ) + · · · + xd F (⃗vd ) = ⃗0.
Since F is linear, this gives

F (x1⃗v1 + · · · + xd⃗vd ) = ⃗0.

But since F is one-to-one and F (⃗0) = ⃗0 we must have

x1⃗v1 + · · · + xd⃗vd = ⃗0.

Since the ⃗vi are linearly independent, we must have x1 = · · · = xd = 0. Hence,

F (⃗v1 ), . . . , F (⃗vd ) are linearly independent as well. Next, to see that this set spans
W , take any w ⃗ ∈ W . Since F is onto, there exists ⃗v ∈ V so that F (⃗v ) = w.
⃗ Since
the ⃗vi form a basis for V we can write ⃗v = c1⃗v1 + · · · + cd⃗vd and so

⃗ = F (c1⃗v1 + · · · + cd⃗vd )
w
= c1 F (⃗v1 ) + · · · + cd F (⃗vd )
∈ Span(F (⃗v1 ), . . . , F (⃗vd )),

where the second equality follows by linearity of F . Hence, W = Span(F (⃗v1 ), . . . , F (⃗vd ))
and so the F (⃗vi ) form generating set. Hence, {F (⃗v1 ), . . . , F (⃗vd )} is a basis for W ,
and so dim(W ) = d.

Conversely, suppose that dim(V ) = dim(W ). Let

{⃗v1 , . . . , ⃗vd }

be a basis for V and

{w ⃗ d}
⃗ 1, . . . , w
be a basis for W . Define the map F : V → W by

F (x1⃗v1 + · · · + xd⃗vd ) = x1 w
⃗ 1 + · · · + xd w
⃗ d.

(that is, F : ⃗vi 7→ w

⃗ i and we extend linearly). It can be checked by definition that
F is an isomorphism. □

Example 4.21. Consider the spaces

   
    1 0
1 0
V = Span , and W = Span 0 , 1 .
0 1
0 0

Then dim(V ) = dim(W ) and so V ∼ = W . Furthermore, both V and W are isomor-

phic to R2 . In this case V = R2 , and while W isn’t equal to R2 on the nose (since it
contains three-dimensional vectors) it “looks like” R2 (which is what isomorphisms
are meant to capture).
56 4. Linear Transformations

Exercises

P4.1 Let F be a linear transformation. Show that F (⃗0) = ⃗0.

P4.2 Let V be a vector subspace of Rn and suppose that F : Rn → Rm is a linear
transformation. Show that
F (V ) := {f (v) | v ∈ V }
is a vector subspace of Rm . (Note that this generalizes our geometric obser-
vations from two-dimensional space that linear transformations send lines to
lines or points).
P4.3 Show that the composition of linear functions is linear. That is, if
F : Rn → Rk and G : Rk → Rm
are linear functions, show that G ◦ F : Rn → Rm is also linear.
P4.4 True or False: If a linear transformation from Rn to Rn is one-to-one, then it
is also onto. If true, provide a proof. If false, provide a counterexample and
justify why this is a counterexample.
P4.5 Let F : Rn → Rm be a linear transformation. If n < m, show that F cannot
be surjective.
P4.6 Let F : Rn → Rm be a linear transformation. If n > m, show that F cannot
be injective.
P4.7 Let F : Rn → Rm be an injective linear transformation with n ≤ m, and
suppose that V is a vector subspace of Rn with dim(V ) = k. Show that F (V )
is isomorphic to Rk , where F (V ) = {F (⃗v ) : ⃗v ∈ V }.
 Chapter 5

[DRAFT - subject to revision]

Fundamental Subspaces

5.1. The Kernel and Image

Example 5.1. Recall again our example from Lecture Activity 4.3, where we saw
that the matrix transformation TC : R2 → R2 transforms the domain space R2 as
follows

In the previous chapter, we introduced two definitions to capture that TC “com-

presses” the domain space (see Definition 4.13), and that not every vector in the
codomain space is mapped to by TC (see Definition 4.16). In this chapter, we intro-
duce two subspaces which will help us detect how the function is compressing the
domain space, and what subspace the function maps to. We define the following.

Definition 5.2. Let F : Rn → Rm be a linear transformation.

(1) The kernel of F is the subset ker(F ) ⊆ Rn defined by

ker(F ) := {⃗x ∈ Rn | F (⃗x) = ⃗0}.

(2) The image of F is the subset im(F ) ⊆ Rm defined by

im(F ) := {F (⃗x) | ⃗x ∈ Rn }.

57
58 5. [DRAFT - subject to revision] Fundamental Subspaces

Domain Rn Codomain Rm

F Im F

ker F
⃗0

Figure 1. Visual representation of the kernel and image

That is, the kernel is the set of vectors in the domain Rn that are mapped to the
zero vector, and the image is the set of elements in the codomain that are mapped
to by F , as represented in the graphic below.

Lecture Activity 5.1. Let F = TC where C is our matrix from Lecture

Activity 4.3  
1 1
C= .
1 1
P1. Find a vector ⃗x ∈ ker(F ).
P2. Find a vector ⃗y ∈ im(F ).
P3. Find a vector ⃗v so that ker(F ) = Span(⃗v ). Conclude that ker(F ) is a
vector space.
P4. Find a vector w⃗ so that im(F ) = Span(w).
⃗ Conclude that im(F ) is a
vector space.

The following result generalizes our observations from Lecture Activity 5.1. We
will leave the proof of this result as a chapter exercise.

Proposition 5.3. Let F : Rn → Rm be a linear transformation. Then, ker(F ) is

a vector subspace of Rn and im(F ) is a vector subspace of Rm .

Proposition 5.3 allows us to define the following.

Definition 5.4. Let F : Rn → Rm be a linear transformation.

(1) The rank of F is the dimension of im(F ), and is denoted by rank(F ).

(2) The nullity of F is the dimension of ker(F ), and is denoted by nullity(F ).

Let’s look at an example.

5.1. The Kernel and Image 59

Lecture Activity 5.2. Let F : R3 → R2 be given by

 
x  
x+y
F   y  = .
x+z
z
P1. Calculate rank(F ).
P2. Calculate nullity(F ).

In Lecture Activity 5.2, we saw that our kernel and image calculations involved the
defining matrix MF . Let’s add two more definitions to capture this observation
more precisely.


Definition 5.5. Let A be an m×n matrix with column vectors A = ⃗v1 · · · ⃗vn .
Then, the column space of A is the subspace of Rm given by
Col(A) := Span(⃗v1 , . . . , ⃗vn ).
The null space of A is the subspace of Rn given by
Nul(A) := {⃗x ∈ Rm | A⃗x = ⃗0}.

With this new terminology, we can now generalize our calculations from Lecture
Activity 5.2.
Proposition 5.6. Let F : Rn → Rm be a linear transformation with defining
matrix MF . Then, ker(F ) = Nul(MF ) and im(F ) = Col(MF ).

Proof. Let F have defining matrix M = MF . Then,

n o
ker(F ) = ⃗x ∈ Rn : F (⃗x) = ⃗0 , by definition of ker(F )
n o
= ⃗x ∈ Rn : M⃗x = ⃗0 , since M is the defining matrix of F
= Nul(M ), by definition of Nul(M ).


Next, suppose that M has column vectors M = ⃗v1 · · · ⃗vn . Then,
     

 x1 x1 

 ..   ..  n
im(F ) = F  .  :  .  ∈ R , by definition of im(F )
 
xn xn
 
   

 x1 

= M  ...  : x1 , . . . , xn ∈ R , since M is the defining matrix of F
 
 
xn
 
   

 x1 


 . 

= ⃗v1 · · · ⃗vn  ..  : x1 , . . . , xn ∈ R , since M = ⃗v1 · · · ⃗vn
 
xn
 

= {x1⃗v1 + · · · + xn⃗vn : x1 , . . . , xn ∈ R} , by definition of the matrix-vector product

= Span (⃗v1 , . . . , ⃗vn ) , by definition of span
= Col(M ), by definition of the column space. □
60 5. [DRAFT - subject to revision] Fundamental Subspaces

In light of Proposition 5.6, we have the following definitions.

Definition 5.7. Let A be a matrix.
(1) The nullity of A is the dimension of Nul(A), and is denoted by nullity(A).
(2) The rank of A is the dimension of Col(A), and is denoted by rank(A).

Let’s practice using our new notation.

Lecture Activity 5.3. Calculate the rank and nullity of

 
1 −1 0
A = 0 0 1 .
2 1 1

5.2. Rank-Nullity
The kernel and image of a linear transformation give us key information about how
our function behaves. Let’s develop some geometric
 intuition by looking again at
1 1
our linear transformation F = TC where C = .
1 1

In Lecture Activity 5.1, we found that

 
−1
ker(F ) = Span ,
1
which tells us that all points along the line y = −x will be collapsed to ⃗0 under F ,
as visualized below.

But since F is linear we can see that all lines parallel to ker(F ) will also be collapsed
down to a single point. Indeed, if we take any ⃗y ∈ ker(F ) then for any ⃗x ∈ R2 we
have
F (⃗y + ⃗x) = F (⃗y ) + F (⃗x), since F is linear
= ⃗0 + F (⃗x), since ⃗y ∈ ker(F )
= F (⃗x).
5.2. Rank-Nullity 61

That is, the line obtained by shifting ker(F ) by ⃗x also gets collapsed to a single
point, as visualized below.

Repeating this argument, we can see that all lines parallel to the kernel are collapsed
to a point, as visualized below.

This leads to a key geometric observation: it appears that our transformation F

collapses the domain exactly by the dimension of the kernel to produce the image.
In other words, our geometric argument above suggests that
dim(R2 ) − dim(ker(F )) = dim(im(F )),
which can be rewritten using our notation from the previous section as
2 − nullity(C) = rank(C),
recalling that MF = C. In the following activity, we will generalize this observation
to higher dimensions. Because we cannot visualize how these transformations act
in higher-dimensional spaces, we will rely on our algebraic characterizations to
rigorously establish what we observed geometrically in the example above.

Lecture Activity 5.4. Let A and B be m × 3 matrices.

P1. Suppose that A has exactly two pivot columns, which are located in
columns 1 and 3. Show that rank(A) = 2 and nullity(A) = 1.
62 5. [DRAFT - subject to revision] Fundamental Subspaces

P2. Suppose that B has exactly one pivot column, which is located in
column 1. Show that rank(B) = 1 and nullity(B) = 2.

The following result generalizes our work from Lecture Activity 5.4.
Theorem 5.8. Let A be an m×n matrix with r pivot columns. Then, rank(A) = r
and nullity(A) = n−r. That is, the rank of A is equal to the number of pivot columns
of A, and the nullity of A is the number of non-pivot columns of A.


Proof. Suppose that rref(A) = ⃗v1 · · · ⃗vn . Without loss of generality, suppose
that ⃗v1 , . . . , ⃗vr contain pivots, and ⃗vr+1 , . . . , ⃗vn do not contain pivots. Then Col(A)
has dimension r by Theorem 3.11, as needed.

Next, observe that

 
x1
 .. 
 .  ∈ Nul(A) if and only if x1⃗v1 + · · · + xn⃗vn = ⃗0.
xm
In the vector equation above, xr+1 , . . . , xn are free, and so we can write
x1 = a1,r+1 xr+1 + a1,r+2 xr+2 + · · · + a1,n xn
x2 = a2,r+1 xr+1 + a2,r+2 xr+2 + · · · + a2,n xn
..
.
xr = ar,r+1 xr+1 + ar,r+2 xr+2 + · · · + ar,n xn .
So, we have
      
a1,r+1 a1,r+2 a1,n
a2,r+1  a2,r+2  a2,n  
 ..   ..   ..  
      
 .   .   .  
      
ar,r+1  ar,r+2  ar,n  
      
 1  ,  0  , . . . ,  0  . .
Nul(A) = Span       
 0   1   0  
      
 0   0   0  
      
 .   .   .  
 ..   ..   ..  
0 0 1
Finally, observe that the m − r vectors above are linearly independent, since the
matrix with the vectors above as its columns has a pivot in every column. □

We have the following consequence to Theorem 5.8, often referred to as the rank-
nullity theorem.
Corollary 5.9 (The Rank-Nullity Theorem). Let A be an m × n matrix. Then,
rank(A) + nullity(A) = n.

Proof. Suppose that the matrix A has r pivot columns. By Theorem 3.11 we know
that rank(A) = r. So the result follows by Theorem 5.8. □
5.3. Homogeneous Systems and the Geometry of Systems 63

5.3. Homogeneous Systems and the Geometry of Systems

Now that we’ve developed some machinery, we can return to our problem of de-
scribing the solution set to a system of linear equations. We define the following.
Definition 5.10. A system of linear equations is called homogeneous if the
constant coefficients are all equal to zero.

In the next activity, we’ll see how our work from the previous section gives us a
geometric understanding for the solution set to a homogeneous system.

Lecture Activity 5.5. Consider the homogeneous system of linear equa-

tions 
x + 2y + 4z = 0

x+y−z =0

 y + 5z = 0
P1. Find a matrix C so that the solution set to this system is equal to
Nul(C).
P2. Calculate nullity(C).
P3. Recall from Section 1.7 that the solution set to this system is equal to
the set of intersection points of planes in R3 . Given your work in the
previous parts, do these planes intersect at a point, a line, or a plane
in R3 ?

Remark 5.11. Observe that the solution set to any homogeneous system of linear
equations can be represented as a null space. Indeed, if a system of m linear
equations has coefficient matrix C, then the vector form of the solution set to this
system is equal to
{⃗x ∈ Rm : C⃗x = ⃗0}
which is precisely equal to Nul(C). As we saw in the previous activity, this tells
us that we can quickly detect what the solution set to a homogeneous system of
linear equations looks like. In the following theorem, we extend this to any system
of linear equations.
Theorem 5.12. The vector representation for the solution set to a consistent sys-
tem of linear equations in n variables with coefficient matrix C is equal to
p⃗ + Nul(C) := {⃗
p + ⃗v | ⃗v ∈ Nul(C)}
where p⃗ is any particular vector solution to the system of linear equations.

Proof. Suppose that our system of linear equations has coefficient matrix C and
particular solution p⃗. Then, the system has the same solution set as the matrix-
vector equation C⃗x = ⃗b for a vector ⃗b ∈ Rn . Let ⃗s be any solution to this matrix-
vector equation. Since ⃗s and p⃗ are solutions to the matrix-vector equation C⃗x = 0
we have C⃗s = ⃗0 and C⃗ p = ⃗0. So, C(⃗s −⃗
p) = C⃗s −C⃗p = ⃗0, and hence ⃗s −⃗
p ∈ Nul(C).
That is, ⃗s − p⃗ = ⃗v for some ⃗v ∈ Nul(C) and so adding p⃗ to both sides gives
⃗s = p⃗ + ⃗v ∈ p⃗ + Nul(C).
64 5. [DRAFT - subject to revision] Fundamental Subspaces

Conversely, take any p⃗ + ⃗v ∈ p⃗ + Nul(C). Since p⃗ is a solution to C⃗x = ⃗b we have

p = ⃗b. Furthermore, since ⃗v ∈ Nul(C) we have C⃗v = ⃗0. So,
C⃗
C(⃗ p + C⃗v = ⃗b + ⃗0 = ⃗b,
p + ⃗v ) = C⃗
and so p⃗ + ⃗v is a solution to C⃗x = ⃗b, as needed. □
Remark 5.13. Geometrically, the sets p⃗ + Nul(C) look like a vector space “trans-
lated” by some fixed vector p⃗ from the origin. For example, suppose that C is a
3 × 3 matrix.

If nullity(C) = 1, then p⃗ + Nul(C) is a line in R3 , as pictured below

If nullity(C) = 2, then p⃗ + Nul(C) is a plane in R3 , as pictured below

5.4. The Row Space 65

Lecture Activity 5.6. Use Theorem 5.12 to determine whether the solu-
tion set for each of the following systems is empty, a point, a line, or a plane
in R3 . 
x + 2y + 4z = 1

P1. x+y−z =2

y + 5z = −1



x + 2y + 2z = 5

P2. x+y+z =0

3x + 3z = 1



x + 2y + 4z = 1

P3. x+y−z =2

y + 5z = 1


5.4. The Row Space

To define our third fundamental subspace, it will be convenient to define a matrix
operation. We have the following.
Definition 5.14. Let A be the m × n matrix
 
a11 a12 · · · a1n
 a21 a22 · · · a2n 
A= . ..  .
 
.. ..
 .. . . . 
am1 am2 ··· amn
Then, the transpose of A is the n × m matrix A⊤ given by
 
a11 a11 · · · am1
 a12 a22 · · · am2 
A⊤ =  . ..  .
 
.. ..
 .. . . . 
a1n a2n · · · amn
That is, A⊤ is the matrix with column vectors equal to the rows of A.
Example 5.15. Let  
1 2
A = 3 4 .
5 6
Then  
1 3 5
A⊤ = .
2 4 6
Definition 5.16. The row space of an m × n matrix A is the vector subspace
Row(A) of Rn given by
Row(A) = Col(A⊤ ).
That is, Row(A) is the subspace of Rn spanned by the row vectors of A.
66 5. [DRAFT - subject to revision] Fundamental Subspaces

Note that the row space of a matrix doesn’t have much geometric meaning for us
at the moment, but (time permitting) we will see a geometric interpretation of this
space later on in the course. So let’s bookmark this story for now and come back
to this once we’ve developed a bit more machinery. In the meantime, we record the
following result.
Theorem 5.17. Let A be an m × n matrix. Then,
dim(Col(A)) = dim(Row(A)).

Time permitting, we’ll give a cleaner of this fact later on in the course, but for
completeness we also include an elementary proof of this result below.

Proof. First, observe that if A is row equivalent to B, then Row(A) = Row(B).

To see this, note that two matrices being row equivalent means that the rows of
one can be written as linear combinations of rows of the other. Now, suppose that
X is the reduced row echelon form of A. By above, we have that dim(Row(A)) =
dim(Row(X)). Observe, by definition of a matrix being in reduced row echelon
form, that the dimension of Row(X) is precisely the number of nonzero rows of
X (since these rows are linearly independent). The result follows because there is
exactly one pivot in every nonzero row of X, and the number of pivots of X is the
dimension of the column space of A. □

Exercises

P5.1 Prove Proposition 5.3.

P5.2 Let F : Rn → Rm be a linear transformation. Show that F is surjective if
and only if im(F ) = Rm .
P5.3 Let F : Rn → Rm be a linear transformation. Show that F is injective if and
only if ker(F ) = {⃗0}.
P5.4 Let F : V → W be a linear transformation between vector spaces V and W .
Show that F is injective if and only if ker(F ) = {⃗0}.
P5.5 Let F : Rn → Rm be a linear transformation, and {⃗v1 , . . . , ⃗vn } a basis for Rn .
Show that F is injective if and only if the set {F (⃗v1 ), . . . , F (⃗vn )} is linearly
independent.
P5.6 True or False: There exists a 3 × 3 matrix whose column space and null space
have the same dimension. If such a matrix exists, give an example of one and
justify why this is an example. If it is not possible to construct this matrix,
explain why not.
P5.7 Let F : R7 → R3 be a surjective linear transformation. Find the dimension
of ker(F ).
P5.8 Let F : R5 → R4 be a linear transformation with nullity(F ) = 2. Show that
im(F ) is isomorphic to R3 .
P5.9 Give an alternate proof of Theorem 4.17 that uses Proposition 5.3 and The-
orem 3.12.
 Chapter 6

[DRAFT - subject to revision]

Matrix Algebra

In this Chapter, we’ll see how our usual operations on functions correspond to
algebraic operations on matrices.

6.1. Matrix Addition and Scalar Multiplication

Given functions f : Rn → Rm and g : Rn → Rm , recall that we can define a new
function via function addition f + g : Rn → Rm which is defined by

(f + g)(x) = f (x) + g(x).

Let’s look at how function addition behaves for linear transformations.

Lecture Activity 6.1. Let F : Rn → Rm and G : Rn → Rm be linear

transformations.
P1. Show that F + G is a linear transformations.
P2. Let F = TA and G = TB where
   
1 2 −1 3
A= and B = .
3 4 1 2
By P1, we know that F + G is linear. Find the defining matrix MF +G .

Our work in Lecture Activity 6.1 leads to the following definitions, noting that we
could work similarly to to find the defining matrix for the scalar multiple of any
linear transformation.



Definition 6.1. Let A = ⃗v1 · · · ⃗vn and B = w ⃗1 · · · w ⃗ n be m×n matrices
and c ∈ R be a scalar.

67
68 6. [DRAFT - subject to revision] Matrix Algebra

(1) The sum of A and B is the m × n matrix given by

A + B := ⃗v1 + w
⃗1 ··· ⃗vn + w
⃗n .
(2) The scalar product of A with c is the m × n matrix given by


cA := c⃗v1 · · · c⃗vn .
Note that, as we saw in Lecture Activity 6.1, if F and G are linear transformations,
then MF +G = MF + MG .
Proposition 6.2. For all m × n matrices A and B and scalars c ∈ R, the matrix
product satisfies the following properties:
(i) associative; that is, (A + B) + C = (A + B) + C,
(ii) commutative; that is, A + B = B + A, and
(iii) distributive; that is, c(A + B) = cA + cB.
We leave the proof of this result as an exercise to the reader. Note that Proposition
6.2 implies that we can work with our new matrix operations algebraically, as
demonstrated in the example below.
 
1 2
Lecture Activity 6.2. Let B = . Find the matrix A given that
3 4
2(A + (B + 3A)) = 7A − (B + A).

6.2. The Matrix Product

Given sets X, Y, and Z and functions f : Y → Z and g : X → Y , recall that the
composite function f ◦ g : X → Z is defined by
(f ◦ g)(x) = f (g(x)).
Let’s look at how function composition behaves for linear transformations.

Lecture Activity 6.3. Let F : Rk → Rm and G : Rn → Rk be linear

transformations with defining matrices
A = MF and B = MG .
Recall from Chapter Exercise 4.3 that the composition of linear functions is
 defining matrix M = MF ◦G of thecomposition F ◦G is
linear. Show that the
given by MF ◦G = A⃗b1 A⃗b2 · · · A⃗bn where B = ⃗b1 ⃗b2 · · · ⃗bn .

Our work in Lecture Activity 6.3 leads to the following definition.

 
Definition 6.3. Let A be an m × k matrix and B = ⃗b1 · · · ⃗bn be a k × n
matrix. Then, the matrix product of A and B is the m × n matrix
 
B = A⃗b1 · · · A⃗bn .
As we saw in Lecture Activity 6.3, note that TAB = TA ◦ TB .
6.2. The Matrix Product 69

Let’s look at an example to illustrate how we can more quickly perform this calcu-
lation.
Example 6.4. Let
 
  1 2
1 0 3
A= and B =  0 3 .
1 1 −1
−1 1
Since A is 2 × 3 and B is 3 × 2, the matrix product AB is a 2 × 2 matrix. We have


AB = ⃗a1 ⃗a2
where    
 1   2 
1 0 3   1 0 3  
⃗a1 = 0 , and ⃗a2 = 3 .
1 1 −1 1 1 −1
−1 1
So,  
−2 5
AB =
,
2 4
With practice, we can perform this computation a bit more quickly. Let’s perform
the steps above by just keeping track of how we’re generating each entry:
 
  1 2  
1 0 3  −2 5
0 3 =
1 1 −1 2 4
−1 1
 
  1 2  
1 0 3  −2 5
0 3 =
1 1 −1 2 4
−1 1
 
  1 2  
1 0 3  −2 5
0 3 =
1 1 −1 2 4
−1 1
 
  1 2  
1 0 3  −2 5
0 3 =
1 1 −1 2 4
−1 1
Let’s practice a few more examples.

Lecture Activity 6.4. Let

 
0 −1  
  1 1 2 0
1 0 1 −1 3 0
0
A= ,B= and C = 1 4 1 .
0 2 3 1 1 0
0 0 −2 1
−1 4
Calculate the matrix products AB, BA, AC, CA, BC, CA. If a matrix prod-
uct is not defined, explain why not.

Remark 6.5. Note that if A is an m × k matrix and B is ℓ × n matrix, the matrix

product AB is only defined when k = ℓ. In this case, AB is a m × n matrix.
70 6. [DRAFT - subject to revision] Matrix Algebra

6.3. Matrix Inverses

Let f : X → Y be a function between two sets X and Y . Recall that the inverse
of f , if it exists, is the function f −1 : Y → Z so that
(f ◦ f −1 )(y) = y and (f −1 ◦ f )(x) = x
for all x ∈ X and y ∈ Y . Furthermore, note that the inverse f −1 exists if and only
if f is bijective.

Let’s look at how inverses behave for linear transformations.

Lecture Activity 6.5. Let F : Rn → Rm be a linear transformation, and

suppose that the inverse function F −1 : Rm → Rn is known to exist.
P1. Use Lecture Activity 4.9 to show that m = n.
P2. Show that F −1 is a linear transformation.
P3. Suppose that F has defining matrix MF = A and F −1 has defining
matrix MF −1 = B. What matrix does AB need to be equal to? What
about BA?

Our work in Lecture Activity 6.5 leads to the following definitions.

Definition 6.6. The identity matrix In is the n × n matrix In = ⃗e1 ··· ⃗en .
That is,  
1 0 ··· 0
0 1 ··· 0
In =  . . ..  .
 
 .. .. ..
. .
0 0 ··· 1
Definition 6.7. Let A be an n × n matrix. Then inverse of A, if it exists, is the
matrix B so that AB = BA = In . In this case, we write B = A−1 .
Example 6.8. Consider the matrix
 
1 1 1
A = 0 2 1 .
0 1 1
To verify that  
1 0 −1
A−1 = 0 1 −1 ,
0 −1 2
we check that
    
1 1 1 1 0 −1 1 0 0
AA−1 = 0 2 1 0 1 −1 = 0 1 0
0 1 1 0 −1 2 0 0 1
and     
1 0 −1 1 1 1 1 0 0
A−1 A = 0 1 −1 0 2 1 = 0 1 0 ,
0 −1 2 0 1 1 0 0 1
6.3. Matrix Inverses 71

and so AA−1 = A−1 A = I3 , as needed.

Since matrix multiplication is not commutative (see Lecture Activity 6.4, for exam-
ple), Definition 6.7 implies that we needed to check both A−1 A = In and AA−1 = In
are satisfied. The following result shows that in fact it suffices to only check one of
these equalities, which will simplify our future calculations.
Lemma 6.9. For n × n matrices A, B, if AB = In then B = A−1 .

Proof. Observe that Nul(B) ⊆ Nul(AB), since if B⃗x = ⃗0 then

(AB)⃗x = A(B⃗x) = A⃗0 = ⃗0.
So, by Lemma 3.13 we have nullity(B) ≤ nullity(AB) = nullity(In ) = 0. Hence, by
Theorem 5.8, every column of rref(B) has a pivot, and so by Theorem 4.14 we have
that TB is injective. But since B is square this implies that every row of rref(B)
must also have a pivot, and so TB is surjective by Theorem 4.17. Hence, TB is
bijective and so B is invertible. So, we have
A = AIn = A(BB −1 ) = (AB)B −1 = In B −1 = B −1
which gives A = B −1 . □

Example 6.10. Let’s look at how we could find the inverse of the matrix A from
Example 6.8. Observe that for A−1 to exist, it must satisfy
 
1 0 0
AA−1 = 0 1 0
0 0 1

and so A−1 must have column vectors ⃗b1 , ⃗b2 , ⃗b3 satisfying the matrix-vector equa-
tions      
1 0 0
A⃗b1 = 0 , A⃗b2 = 1 , and A⃗b3 = 0 .
0 0 1
We can use row reduction to solve the first matrix-vector equation, as below
   
1 1 1 1 1 1 1 1
0 2 1 0 ∼ 0 1 0 0 , subtracting R3 from R2
0 1 1 0 0 1 1 0
 
1 0 0 1
∼ 0 1 0 0 , subtracting R3 from R1
0 1 1 0
 
1 0 0 1
∼ 0 1 0 0 , subtracting R2 from R3
0 0 1 0
This gives
 
1
⃗b1 = 0 .
0
72 6. [DRAFT - subject to revision] Matrix Algebra

Observe that we can use exactly the same row operations to solve for ⃗b2 and ⃗b3 :
   
1 1 1 0 1 1 1 0
0 2 1 1 ∼ 0 1 0 1 , subtracting R3 from R2
0 1 1 0 0 1 1 0
 
1 0 0 0
∼ 0 1 0 1 , subtracting R3 from R1
0 1 1 0
 
1 0 0 0
∼ 0 1 0 1  , subtracting R2 from R3
0 0 1 −1
 
0
so that ⃗b2 =  1  and similarly we compute
−1
   
1 1 1 0 1 1 1 0
0 2 1 0 ∼ 0 1 0 −1 , subtracting R3 from R2
0 1 1 1 0 1 1 1
 
1 0 0 −1
∼ 0 1 0 −1 , subtracting R3 from R1
0 1 1 1
 
1 0 0 −1
∼ 0 1 0 −1 , subtracting R2 from R3
0 0 1 2
 
−1
so that ⃗b3 = −2, which gives
1
 
1 0 −1
A−1 = 0 1 −1 .
0 −1 2

Note that, since we performed the same row operations for every matrix-vector
equation, we could performed
the same operations as above by instead looking at
the augmented matrix A I3 , as follows
   
1 1 1 1 0 0 1 1 1 1 0 0
0 2 1 0 1 0  ∼ 0 1 0 0 1 −1  , subtracting R3 from R2
0 1 1 0 0 1 0 1 1 0 0 1
 
1 0 0 1 0 −1
∼ 0 1 0 0 1 −1  , subtracting R3 from R1
0 1 1 0 0 1
 
1 0 0 1 0 −1
∼ 0 1 0 0 1 −1  , subtracting R2 from R3
0 0 1 0 −1 2
6.4. Elementary Matrices 73

Now, if we let
 
1 0 −1
B = 0 1 −1
0 −1 2
the from our work above we know that AB = I3 . We can also check that BA = I3
and so B = A−1 .



Theorem 6.11. Let A be an n×n matrix. If A In is row equivalent to In B
for an n × n matrix B, then then A is invertible with A−1 = B.



Proof. Suppose that A In is row equivalent to In B for an n × n matrix B,
and and write  
B = ⃗b1 ⃗b2 ··· ⃗bn

Let ⃗ui be the vector in Rn with 1 in the ith component

 and 0s
 everywhere else. From
above, we have that A ⃗ui is row equivalent to In bi , and so ⃗bi is a solution
⃗

to the matrix-vector

equation A⃗x = ⃗ui .
This gives AB = In .
Next, observe that
A In being
row equivalent to In B implies that B In is row equivalent
to In A (this is not immediate, you may try convincing yourself of this with
some examples). This proof will then be completed with the following lemma. □

Lecture Activity 6.6. Use Theorem 6.11 to find the inverse of

 
1 2 3
A = 0 1 4  .
0 0 −1

6.4. Elementary Matrices

In this section, we show thatGauss-Jordan elimination can be captured using our
new algebraic operations. We define the following.
Definition 6.12. An n × n matrix is called elementary if it can be obtained by
performing exactly one row operation to the identity matrix.

Lecture Activity 6.7. Consider the matrix

 
1 2 3
A = 4 5 6 .
7 8 9
P1. Let E1 be the elementary matrix obtained by performing the row op-
eration R1 ↔ R3 to I3 . Find E1 , and then calculate E1 A. What do
you notice?
P2. Let E2 be the elementary matrix obtained by performing the row op-
eration 5R2 to I3 . Find E2 and then calculate E2 A. What do you
notice?
74 6. [DRAFT - subject to revision] Matrix Algebra

P3. Let E3 be the elementary matrix obtained by performing the row op-
eration R1 + 2R2 to I3 . Find E3 and then calculate E3 A. What do
you notice?

Our observation from Lecture Activity 6.7 generalizes. We omit the proof of this
result here, since the the idea is intuitive, but the notation to prove this in general
is quite messy.
Proposition 6.13. Let E be the elementary matrix obtained by performing row
operation (∗) to In , and let B be any n×n matrix. Then EB is the matrix obtained
by performing elementary row operation (∗) to B.

Lecture Activity 6.8. Let’s see how we can capture Gauss-Jordan via
matrix products. Consider the matrix
 
1 2 3
A = 0 1 4 
0 0 −1
from Lecture Activity 6.6.
P1. Use your work in Lecture Activity 6.6 to find elementary matrices
E1 , . . . , Ek so that E1 · · · Ek A = I3 .
P2. Reverse your work from Lecture Activity 6.7 to show that I3 ∼ A.
That is, find a sequence of elementary operations to perform to I3 to
obtain A.
P3. Find elementary matrices Ẽ1 , . . . , Ẽk so that Ẽk · · · Ẽ1 I3 = A. Con-
clude that A is a product of elementary matrices.

Our observation from Lecture Activity generalizes.

Proposition 6.14. A matrix is invertible if and only if it’s a product of elementary
matrices.

Proof. Suppose first that A is invertible. Then the function TA is invertible, and
so by Proposition 4.14 and 4.17, rref(A) has a pivot in every row and column. Since
A must be n × n (as we saw in Lecture Activity 6.5), we see that A ∼ In . But this
means that In ∼ A as well, and so by repeated use of Proposition 6.13 we have
E1 E2 · · · Em In = A ⇒ A = E1 E2 · · · Em ,
for elementary matrices E1 , . . . , Em .

Conversely, suppose that A = E1 E2 · · · Em for elementary matrices Ei . Observe

that if E is elementary, then E is invertible. Indeed, if E obtained by performing
operation (*) to In , then E −1 is obtained by performing the opposite operation to
In . So, by repeated use of Chapter Exercise 6.3 we have
A−1 = Em
−1
· · · E1−1 ,
and so A is invertible (since the inverse exists!). □
Exercises 75

In the Theorem below, we compile the results we’ve seen so far that guarantee a
given matrix is invertible. Using the correspondences discussed in Remark 4.11,
several more equivalent conditions can be found, and will be included in the Chap-
ter Exercises. Note that you may reference the conditions in the Theorem below
without proof, but all other conditions that appear in the chapter exercises must
be proven on quizzes, tests, and exams.
Theorem 6.15 (The Invertible Matrix Theorem). Let A be an n×n matrix. Then,
the following are equivalent:
(1) A is invertible;
(2) rref(A) = In ;
(3) A is a product of elementary matrices.

Exercises
 
a b
P6.1 Let A = . Use Theorem 6.11 to show that A is invertible if and only
c d
if ad − bc ̸= 0, and in this case we have
 
1 d −b
A−1 = .
ad − bc −c a
P6.2 Show that if a matrix A is invertible, then its inverse A−1 is unique. That is,
if there exist matrices B and C satisfying
AB = BA = In and AC = CA = In
show that B = C.
P6.3 Show that for n × n invertible matrices A, B we have
(AB)−1 = B −1 A−1
P6.4 Let A be an n × n matrix. Prove that the following conditions are equivalent.
(a) A is invertible;
(b) The matrix-vector equation A⃗x = ⃗b has a unique solution for any ⃗b ∈ Rn ;
(c) rref(A) has n pivots;
(d) Nul(A) = {⃗0};
(e) Col(A) = Rn ;
(f) The columns of A are linearly independent;
(g) TA is an isomorphism;
(h) TA is injective;
(i) TA is surjective.
P6.5 True or False: If A2 is equal to the zero matrix, then A is equal to the zero
matrix. If true, provide a proof. If false, provide a counterexample and justify
why this is a counterexample.
P6.6 A matrix is called nilpotent if there exists a positive integer m so that
Am is equal to the zero matrix. True or False: if A and B are both nilpo-
tent, then AB is also nilpotent. If true, provide a proof. If false, provide a
counterexample and justify why this is a counterexample.
 Chapter 7

[DRAFT - subject to revision]

Determinants

In this chapter we’ll define a powerful tool called the determinant. To understand
why this tool is so powerful, we’ll build the determinant completely geometrically
in R2 and R3 , and then extend our definition algebraically to higher dimensions.

7.1. Determinants in R2
Recall from Theorem 4.8 that a linear transformation is completely determined by
where we send the standard basis. That is, if we know where a linear function F
sends ⃗e1 , . . . , ⃗en (or any other basis for that matter) then we know how the function
behaves on all of Rn . Let’s use the observation to visualize how a function behaves
on its entire domain space. We define the following.
Definition 7.1. The unit square is the subset of R2 given by
S := {α1⃗e1 + α2⃗e2 : 0 ≤ α1 , α2 ≤ 1}.

Lecture Activity 7.1. Let F : R2 → R2 be the linear transformation

defined by
F (⃗e1 ) = 3⃗e1 and F (⃗e2 ) = 2⃗e2 .
P1. Sketch a picture of the unit square S.
P2. Sketch a picture of F (S) := {F (⃗v ) : ⃗v ∈ S} as a subset of R2 .
P3. Sketch the image of the “standard coordinate grid” for R2 under F .

Lecture Activity 7.2. Let G : R2 → R2 be the linear transformation

defined by
G(⃗e1 ) = ⃗e1 + ⃗e2 and G(⃗e2 ) = 2⃗e2 .

77
78 7. [DRAFT - subject to revision] Determinants

P1. Sketch a picture of G(S) as a subset of R2 .

P2. Sketch the image of the “standard coordinate grid” for R2 under G.

Observation 7.2. If F : R2 → R2 is a linear transformation, then

F (S) = {F (α1⃗e1 + α2⃗e2 ) : 0 ≤ α1 , α2 ≤ 1}

= {α1 F (⃗e1 ) + α2 F (⃗e2 ) : 0 ≤ α1 , α2 ≤ 1}.

So, as we saw in Lecture Activity 7.2, the image of the unit square F (S) is a
parallelogram in R2 .

Let’s add one more piece of geometric information to this story.

Definition 7.3. An ordered basis {⃗b1 , ⃗b2 } for R2 is called positively oriented
if we can rotate ⃗b1 counterclockwise to reach ⃗b2 without crossing the line spanned
by ⃗b2 . Otherwise, the basis is called negatively oriented.

Lecture Activity 7.3. Find the orientation for the following ordered bases
for R2 .
P1. B = {⃗b1 , ⃗b2 } where
   
⃗b1 = 2 and ⃗b2 = 2 .
0 1
P2. C = {⃗c1 , ⃗c2 } where
   
1 1
⃗c1 = and ⃗c2 = .
1 −1

We are now prepared to define the determinant in R2 .

Definition 7.4. Let F : R2 → R2 be a linear transformation. Then, the deter-

minant of F , denoted by det(F ), is the oriented area of F (S). That is,

area(F (S))
 if {F (⃗e1 ), F (⃗e2 )} is positively oriented
det(F ) := −area(F (S)) if {F (⃗e1 ), F (⃗e2 )} is negatively oriented

0 if area(F (S)) = 0.


If A is a 2 × 2 matrix, the determinant of A, denoted by det(A), is the deter-

minant of the matrix transformation TA . That is, det(A) := det(TA ).

Lecture Activity 7.4. Find the determinant of matrices

   
2 2 1 1
A= and B = .
0 1 1 −1
7.2. Determinants in R3 79

Lecture Activity 7.5. In this activity, we develop a method to calculate

the determinant of a 2 × 2 matrix completely algebraically. Let
 
a b
A= .
c d
   
a c
For simplicity we’ll assume that the set , is a positively oriented
b d
ordered basis with d ̸= 0 and both vectors are in the first quadrant.
P1. Recall that the area of a parallelogram can be computed as the prod-
uct of its base times its height. Use this observation to calculate the
determinant of  
e b
.
0 d
a − bc
   
a b d b
P2. Show that det = det .
c d 0 d
P3. Use the previous two parts to conclude that
 
a b
det = ad − bc.
c d

With the appropriate casework, we could use a similar argument to Lecture Activity
7.5 to show this formula holds more generally. We’ll allow ourselves to use this result
without completing the remaining cases.
 
a b
Proposition 7.5. det = ad − bc for any a, b, c, d ∈ R.
c d

Lecture Activity 7.6. Calculate the determinant of the following func-

tions. Given your calculation, what can be said about how the function
defined by the given matrix transforms the domain space R2 ?
 
2 4
P1. A =
1 5/2
 
1/2 5
P2. B =
4 2
 
4 1/2
P3. C =
8 1
 
3 1/2
P4. D =
2 1/2

7.2. Determinants in R3
Note that we can extend all of our definitions from the previous section to three
dimensions. We have the following.
Definition 7.6. The unit cube is the subset of R3 given by
C := {α1⃗e1 + α2⃗e2 + α3⃗e3 : 0 ≤ α1 , α2 , α3 ≤ 1}.
80 7. [DRAFT - subject to revision] Determinants

Similar to the two-dimensional case, we can make the following observation.

Observation 7.7. If F : R3 → R3 be a linear transformation, then

F (C) = {F (α1⃗e1 + α2⃗e2 + α3⃗e3 ) : 0 ≤ α1 , α2 , α3 ≤ 1}

= {α1 F (⃗e1 ) + α2 F (⃗e2 ) + α3 F (⃗e3 ) : 0 ≤ α1 , α2 ≤ 1}.

So, F (C) is a parallelepiped with sides given by F (⃗e1 ), F (⃗e2 ), F (⃗e3 ).

Definition 7.8. An ordered basis {⃗b1 , ⃗b2 , ⃗b3 } for R3 is called positively oriented
if it satisfies the right-hand rule. That is, if we point our right hand in the
direction of ⃗b1 , and curl our fingers in toward ⃗b2 , then our thumb should be pointing
in the “direction of ⃗b3 ”– that is, we can rotate our vector ⃗b3 to reach the direction
of our thumb without crossing the plane spanned by ⃗b1 , ⃗b2 . Otherwise, the basis is
called negatively oriented.

Figure 1. The right-hand rule demonstrating the standard basis is positively

oriented (image from PASCO).

Lecture Activity 7.7. Find the orientation of the following ordered bases
for R3 .
P1. B = {⃗b1 , ⃗b2 , ⃗b3 } where
     
3 0 0
⃗b1 = 0 , ⃗b2 = 2 , and ⃗b3 = 2 .
0 0 1
7.2. Determinants in R3 81

P2. C = {⃗c1 , ⃗c2 , ⃗c3 } where

     
0 0 2
⃗c1 = 1 , ⃗c2 =  1  , ⃗c3 = 0 .
1 −1 0

We can now define the determinant in R3 similarly to before.

Definition 7.9. Let F : R3 → R3 be a linear transformation. Then, the deter-
minant of F , denoted by det(F ), is the oriented volume of F (C). That is,

volume(F (C))
 if {F (⃗e1 ), F (⃗e2 ), F (⃗e3 )} is positively oriented
det(F ) := −volume(F (C)) if {F (⃗e1 ), F (⃗e2 ), F (⃗e3 )} is negatively oriented

0 if volume(F (C)) = 0.


If A is a 3 × 3 matrix, we define the determinant of A, denoted by det(A), to

be the determinant of the matrix transformation TA . That is, det(A) := det(TA ).

To calculate the determinant of 3×3 matrices, we’ll need to explore how to calculate
volumes of parallelepipeds. We first note that the volume of a parallelepiped is
equal to the area of its base multiplied by the height. In the image below (which
taken from Wiki), this corresponds to the area of the parallelogram shaded in blue,
multiplied by h.

Let’s first see how our work in the previous section can help us calculate determi-
nants of special types of matrices.

Lecture Activity 7.8. Calculate the determinant of the matrices

   
3 0 0 0 0 2
A = 0 2 2 , and B = 1 1 0
0 0 1 1 −1 0

Our strategy from Lecture Activity 7.8 generalizes to give us a key property. There
are two more properties we’ll need to complete our calculation, which are included
in the proposition below. Note that this proposition can be developed geometrically,
but would take more time than we have available together this semester. So, on
this rare occassion, we will ask you to accept the following result as true.
Proposition 7.10. The determinant satisfies the following properties.
82 7. [DRAFT - subject to revision] Determinants

(1) Reduction Property:

 
c 0 0  
a a3
det a1 a2 a3 = c det 2

b2 b3
b1 b2 b3
(2) Column Swapping Property:



det ⃗v1 ⃗v2 ⃗v3 = − det ⃗v2 ⃗v1 ⃗v3 .
(3) Row linearity Property:
       
α β γ α 0 0 0 β 0 0 0 γ
det a1 a2 a3  = det a1 a2 a3  +det a1 a2 a3  +det a1 a2 a3 
b1 b2 b3 b1 b2 b3 b1 b2 b3 b1 b2 b3

Example 7.11. Let’s calculate the determinant of the 3 × 3 matrix

 
a b c
A =  1 2 3 .
4 5 6
using Proposition 7.10. First, we the Row Linearity Property to get
     
a 0 0 0 b 0 0 0 c
det(A) = det 1 2 3 + det 1 2 3 + det 1 2 3
4 5 6 4 5 6 4 5 6

Next, we use the Column Swapping Property, which gives

     
a 0 0 b 0 0 c 0 0
det(A) = det 1 2 3 − det 2 1 3 + det 3 1 2 .
4 5 6 5 4 6 6 4 5

Finally, we can use the Reduction Property to get

     
2 3 1 3 1 2
det(A) = a det − b det + c det
5 6 4 6 4 5
= −3a + 6b − 3c .

Lecture Activity 7.9. Use Proposition 7.10 to calculate det(A), where

 
1 2 −1
A = 1 3 1 .
1 −1 −1
Given this calculation, what can you say about the matrix transformation
TA : R3 → R3 ?
7.3. Cofactor Expansion and Determinants in Rn 83

7.3. Cofactor Expansion and Determinants in Rn

Example 7.11 will help us extend the definition of the determinant to any n × n
matrix. We first need a definition.


Definition 7.12. For an n × n matrix A = aij , the ij-minor of A is defined to
be the (n − 1) × (n − 1) matrix Aij with the ith row and jth column deleted.
Definition 7.13. Let A be the n × n matrix with ij-entry equal to aij . Then we
define the determinant of A by the following cofactor expansion formula:
det(A) := a11 det(A11 ) − a12 det(A12 ) + · · · + (−1)n+1 a1n det(A1n ).

Lecture Activity 7.10. Find the determinant of the following matrix

 
1 0 1 0
0 2 0 0
A=  .
1 0 −1 0
0 1 1 2

Remark 7.14. From our work in the previous section, we see that Definition 7.13
agrees with our definitions of the determinant in the two and three-dimensional
cases. For this reason, the determinant is often used to define volumes in higher
dimensions.

The following result will help simplify our determinant calculations. Justifying
these claims is a bit more technical than we have time to explore together this
semester, so we record these results without proof. Interested readers can find
proofs of these results throughout Poole’s text (which is referenced in the preface
of these notes).
Proposition 7.15 (Determinant Properties). Let A be an n × n matrix.
(1) If B = A⊤ is the transpose of A, then det(A) = det(B);
(2) If B is obtained by interchanging two rows of A, then
det(B) = − det(A);
(3) If B is obtained by multiplying one row of A by a constant c, then
det(B) = c det(A);
(4) If B is obtained by replacing a row of A by that row and a scalar multiple of
another row of A, then det(B) = det(A).
(5) If B is any n × n matrix, then det(AB) = det(A) det(B).

Lecture Activity 7.11. Use Proposition 7.15 to calculate the determinant

of the following matrix  
1 0 3 0
1 0 2 0
A= 4 0 0 1


1 2 3 0
84 7. [DRAFT - subject to revision] Determinants

Proposition 7.15 will also help us prove the following result, which we observed
geometrically in lower-dimensions.
Theorem 7.16. Let A be an n × n matrix. Then, A is invertible if and only if
det(A) ̸= 0.

Proof. Suppose first that A is not invertible. Then TA is not surjective, and so by
Theorem 4.17, rref(A) has a row without a pivot. Hence, A is row equivalent to a
matrix B where the first row of B is a row of zeros. Hence, by cofactor expansion
along with Proposition 7.15, we obtain det(A) = c det(B) = c · 0 = 0, where c
is some real number constant. So, if det(A) ̸= 0 it must be the case that A is
invertible.

Conversely, suppose that A is invertible. Then, by the Invertible Matrix Theorem

(Theorem 6.15) we can write
A = E1 E2 · · · Ek
where E1 , . . . , Ek are elementary matrices. Observe that det(In ) = 1 and so by ??
we see that det(Ei ) ̸= 0 for i = 1, . . . , k. Hence, by repeated use of Proposition
7.15 (5) we have
det(A) = det(E1 ) det(E2 ) · · · det(Ek ) ̸= 0,
as needed. □

Exercises
1
P7.1 Let A be an invertible matrix. Show that det(A−1 ) = .
det(A)
P7.2 True or False: For any n×n matrix A, det(−A) = − det(A). If true, provide
a proof. If false, provide a counterexample and justify why this is
a counterexample.
P7.3 True or False: For any two n × n matrices, det(A + B) = det(A) + det(B). If
true, provide a proof. If false, provide a counterexample and justify
why this is a counterexample.
P7.4 True or False: if A and B are square matrices and AB is invertible, then both
A and B are invertible. If true, provide a proof. If false, provide a
counterexample and justify why this is a counterexample.
P7.5 Show that if A and B are n × n matrices with rank(A) = rank(B) = n then
rank(AB) = n.
P7.6 An n × n matrix A is called skew-symmetric if A = −A⊤ . Show that when
n is odd, any n × n skew-symmetric matrix is not invertible.
P7.7 An n × n matrix A is called nilpotent if Am is equal to the zero matrix for
some positive integer m. Show that nilpotent matrices are not invertible.
 Chapter 8

[DRAFT - subject to revision]

Eigenvalues and Eigenvectors

8.1. Definitions
In this Chapter, we’ll investigate the “stretch factors” of a linear transformation,
which will help us gain a further geometric understanding of how a linear function
transforms a vector space. We have the following definition.

Definition 8.1. Let A be an n×n matrix. A non-zero vector ⃗v is an eigenvector

of A if there is a real number scalar λ such that A⃗v = λ⃗v . The scalar λ is called an
eigenvalue of A.

Geometrically, this means that when we apply the matrix transformation TA to an

eigenvector ⃗v , this is the same thing as stretching the vector ⃗x by the eigenvalue λ,
as visualized in this 3Blue1Brown video.

Lecture Activity 8.1. For each of the following matrix-vector pairs, de-
termine whether ⃗v is an eigenvector of the matrix A. If it is, find the
corresponding eigenvalue λ.
   
3 2 −2
P1. A = and ⃗v = .
 3 8   1
3 2 1
P2. B = and ⃗v =
3 8 1
   
1 2 −2
P3. C = and ⃗v =
2 4 1

Let’s develop a method to calculate the eigenvalues and eigenvectors of a given

matrix. We have the following.

85
86 8. [DRAFT - subject to revision] Eigenvalues and Eigenvectors

Proposition 8.2. For an n×n matrix A, the set of eigenvectors of A corresponding

to an eigenvalue λ is equal to the nonzero vectors in Nul(A − λIn ).

Proof. Observe ⃗v ∈ Nul(A − λIn ) if and only if

(A − λIn )⃗v = ⃗0

⇔ A⃗v − λ⃗v = ⃗0
⇔ A⃗v = λ⃗v ,
as needed. □

Definition 8.3. Let A be an n × n matrix with eigenvalue λ.

(1) The λ-Eigenspace of A is the vector subspace of Rn defined by
Eλ := Nul(A − λIn ).
(2) The geometric multiplicity of λ is the dimension of the λ-eigenspace Eλ .

 
3 2
Lecture Activity 8.2. Let A = , and recall from Lecture Activity
3 8
8.1 that λ = 2 is an eigenvalue of A
P1. Find the 2-Eigenspace of A.
P2. Find the geometric multiplicity of λ = 2.

Remark 8.4. By Proposition 8.2, the nonzero vectors in Eλ is equal to the set of
all eigenvectors with corresponding eigenvalue λ. Since we know how to find bases
for null spaces, we thus know how to find all eigenvectors with a fixed eigenvalue.
So what’s left is to find a method to calculate the eigenvalues of a matrix. We have
the following.
Proposition 8.5. A real number λ is an eigenvalue of A if and only if
det(A − λIn ) = 0.

Proof. Consider the vector equation

(8.1) (A − λIn )⃗x = ⃗0.
By definition, ⃗v is an eigenvector of A with eigenvalue λ precisely when A⃗v = λ⃗v ,
which can be rewritten as
(A − λIn )⃗v = ⃗0.
Since eigenvalues are nonzero, we know that λ is an eigenvalue of A if and only
if there is a nonzero solution ⃗v to Equation (8.1). Since ⃗0 is also a solution to
Equation (8.1), λ is an eigenvalue of A if and only if Equation (8.1) has infinitely
many solutions. By Rouché-Capelli, this takes places precisely when rref(A − λIn )
has a column without a pivot, which is equivalent to the matrix A − λIn not being
invertible by Theorem 6.15. Thus, the result follows by Theorem 7.16. □
8.2. The Characteristic Polynomial 87

8.2. The Characteristic Polynomial

We define the following.
Definition 8.6. For an n × n matrix A,
χA (x) = det(A − xIn ).
is called the characteristic polynomial of A.

Lecture Activity 8.3. Find the characteristic polynomial of the following

matrices. Then, use Proposition 8.5 to find the eigenvalues of each matrix.
 
  1 0 1  
1 1 1 −1
A= ,B = 0 1 1 ,C =
  .
1 1 1 1
0 0 2

In Lecture Activity 8.3, we saw that χA (x) was a polynomial of degree 2. This
turns out to hold more generally.
Proposition 8.7. For any n × n matrix A, the characteristic polynomial χA (x) is
a polynomial of degree n.

The formal proof of Proposition 8.7 would use an inductive argument, along with
the cofactor expansion formula for the determinant. Instead of worrying about
understanding this proof formally, note that:
(1) If we look at the cofactor formula for the determinant, we see that the only
operations happening are addition and multiplication, and so we end up with
some algebraic expression made up of sums and products of real numbers and
our unknown x, which precisely defines a polynomial.
(2) If an n×n matrix A has diagonal entries d1 , d2 , . . . , dn , then the highest degree
term coming out of the cofactor exapansion will be (d1 − x)(d2 − x) · · · (dn − x)
(convince yourself of this in the 3 × 3 case). So, the degree of χA (x) will be at
most n, and in fact in can be argued that the degree is equal to n (by noting
that the remaining summands each have degree strictly smaller than n).
Remark 8.8. Proposition 8.5 and Proposition 8.2 give us the following strategy
for finding the eigenvectors of a matrix A:
(1) Find all eigenvalues of A by solving the polynomial equation χA (x) = 0.
(2) For each eigenvalue λ, calculate the λ-Eigenspace Eλ = Nul(A − λIn )
(3) The set of all eigenvalues is the union of the λ-Eigenspaces in part (2).

In Chapter 10, we’ll return to our eigen-story to see how these “stretch-factors” can
give key geometric information about how a linear function transforms the domain
space. First, we need to develop a bit more machinery.
88 8. [DRAFT - subject to revision] Eigenvalues and Eigenvectors

Exercises

P8.1 Let F : R2 → R2 be a linear transformation which rotates every vector in R2

counterclockwise by anangle of θ. 
cos θ − sin θ
(a) Show that AF = .
sin θ cos θ
(b) Show that AF does not have any (real) eigenvalues unless θ is an integer
multiple of 180◦ .
P8.2 Show that for any n × n matrix A we have χA = χA⊤ . Conclude that A and
A⊤ have the same eigenvalues.
P8.3 True or False: for any n × n matrix A, A and A⊤ have the same eigenvectors.
If true, provide a proof. If false, provide a counterexample and
justify why this is a counterexample.
P8.4 Show that a matrix A is invertible if and only if 0 is not an eigenvalue of A.
P8.5 An n × n matrix is called idempotent if A2 = A.
(a) Show that an idempotent matrix A is invertible if and only if A = In .
(b) Show that if A is a nonzero idempotent matrix that’s not equal to the
identity then A has eigenvalues 0 and 1.
 Chapter 9

[DRAFT - subject to revision]

Coordinate Systems and
Change of Basis

9.1. Coordinate Systems

While the number of elements in a basis is fixed, we’ve seen that there are many
(in fact, infinitely many) choices for a basis of a given vector space. In this section,
we look at how our choice of basis impacts our geometric understanding of a given
vector space.

Lecture Activity 9.1. The standard coordinate grid for R2 is drawn below.
P1. Explain how we can use the standard basis E = {⃗e1 , ⃗e2 } to draw the
grid lines below.

⃗e2
⃗e1

89
90 9. [DRAFT - subject to revision] Coordinate Systems and Change of Basis

P2. Draw the vectors ⃗u = 4⃗e1 + ⃗e2 and ⃗v = −⃗e1 + 5⃗e2 on the coordinate
grid above.

Lecture Activity 9.2. Let B = {⃗b1 , ⃗b2 }

   
⃗b1 = 1 and ⃗b2 = −2 .
1 1
Observe that B is a basis for R2 . The image below shows how we can use B
to create a “nonstandard” coordinate grid for R2 .
P1. Explain how the vectors ⃗b1 , ⃗b2 can be used to draw the grid lines below.

⃗b2 ⃗b1

(0, 0)

P2. The following graph includes the standard coordinate grid defined by
the standard basis E (drawn with solid lines) and the “nonstandard”
coordinate grid defined by the basis B (drawn with dashed lines). Draw
the following vectors on the graph below
⃗u = 4⃗e1 + ⃗e2 , ⃗v = −⃗e1 + 5⃗e2
⃗ = 2⃗b1 − ⃗b2 , ⃗z = 3⃗b1 + 2⃗b2
w
What do you notice?

(0, 0)
9.1. Coordinate Systems 91

P3. Consider the vector ⃗v = 3⃗e1 + 6⃗e2 . Use the graph from the previous
activity to find real numbers x1 , x2 so that ⃗v = x1⃗b1 + x2⃗b2 .

In the activities above, we observed that different bases give different coordinate
grids for R2 , and that coordinate grids give instructions for the location of a vector.
Let’s introduce some terminology to generalize these observations to Rn .

Definition 9.1. Let B = {⃗v1 , ⃗v2 , . . . , ⃗vn } be an ordered basis for a vector space V .
Recall that every vector ⃗x in V can be written in the form
⃗x = x1⃗v1 + · · · + xn⃗vn .
The B-coordinates of ⃗x is the vector in Rn given by
 
x1
[⃗x]B :=  ...  .
 

xn

Lecture Activity 9.3. Let B = {⃗b1 , ⃗b2 , ⃗b3 } be the ordered basis for R3
where      
1 2 0
⃗b1 = 1 , ⃗b2 =  1  , and ⃗b3 = 1 .
0 −1 3
 
1
Find the B-coordinates of the vector ⃗v = 3.
4

Note that, in Lecture Activity 9.3 there was precisely one way to write ⃗v as a linear
combination of ⃗b1 , ⃗b2 and ⃗b3 since the vector equation represented by
 
⃗b1 ⃗b2 ⃗v

had exactly one solution. This turns out to be true in general (and is what allows
us to define the coordinates of a vector with respect to a basis). We have the
following.

Theorem 9.2. Let V be a vector subspace of Rn and B a basis for V . Then,

every vector in V has a unique representation in terms of the basis B. That is, if
B = {⃗b1 , ⃗b2 , . . . , ⃗bm }, then for every ⃗v ∈ V there are unique real numbers x1 , . . . , xm
so that
⃗v = x1⃗b1 + x2⃗b2 + · · · + xm⃗bm

Proof. Let ⃗v ∈ V . Since {⃗b1 , . . . , ⃗bm } is a basis for V , this set is linearly indepen-
dent, and so we know that reduced row echelon form of the matrix
 
⃗b1 · · · ⃗bm
92 9. [DRAFT - subject to revision] Coordinate Systems and Change of Basis

has a pivot in every column. Furthermore, since V = Span(⃗b1 , . . . , ⃗bm ) we know

that the system  
⃗b1 · · · ⃗bm ⃗v

must be consistent. Hence, the reduced row echelon form of the matrix above has
a pivot in every column except for the last column, and so by Theorem 1.27 there
is exactly one solution to the vector equation
⃗v = x1⃗b1 + x2⃗b2 + · · · + xm⃗bm
as needed. □

We give an alternate proof below to see how we could instead use our algebraic
definition of linear independence.

Proof of Theorem 9.2 (version 2). Let ⃗v ∈ V and suppose that we can write
⃗v = x1⃗b1 + · · · + xm⃗bm
and
⃗v = y1⃗b1 + · · · + ym⃗bm .
Subtracting these two equations gives
⃗0 = (x1 − y1 )⃗v1 + · · · + (xm − ym )⃗vm .

Since our vectors ⃗b1 , . . . , ⃗bm are linearly independent, we must have
xi − yi = 0 ⇒ xi = yi
for all i. So, our two representations of ⃗v as a linear combination of the vectors
⃗v1 , . . . , ⃗vm are the same. □

Remark 9.3. Observe that if E = {⃗e1 , . . . , ⃗en } is the standard basis for Rn , then
 
x1
 .. 
[x1⃗e1 + · · · + xn⃗en ]E =  .  .
xn
That is, when we talk about the coordinates of a vector without referencing any
specific basis, we really mean the coordinates of that vector with respect to the
standard basis.

9.2. Change of Basis Matrices

Observe that we can think of the translation between different coordinate systems as
a linear transformation. More precisely, if C = {⃗c1 , . . . , ⃗cn } and B = {⃗b1 , . . . , ⃗bn } are
ordered bases for a vector space V , we can define a linear transformation F : V → V
by mapping ⃗ci 7→ ⃗bi and “extending linearly”; that is
F (x1⃗c1 + · · · xn⃗cn ) = x1⃗b1 + · · · xn⃗bn .
Observe that F transforms the coordinate grid defined by C into the coordinate grid
defined by B. In this section, we find the defining matrix of such a transformation.
9.2. Change of Basis Matrices 93

Definition 9.4. Let C and B be bases for a vector space V . Then, the change
of basis matrix MC←B is the matrix satisfying
MC←B [⃗x]B = [⃗x]C
for every vector ⃗x in V .

Lecture Activity 9.4. Consider the basis B = {⃗b1 , ⃗b2 } for R2 where
   
⃗b1 = 2 , and ⃗b2 = 5 .
1 3
P1. Find ME←B .
−1
P2. Show that ME←B is invertible with MB←E = ME←B .
P3. Use your work in P2 to find MB←E .

Our method from the previous activity generalizes. We have the following.
Theorem 9.5. Suppose that B = {⃗b1 , . . . , ⃗bn } is a basis for Rn . Then, for any
vector ⃗x ∈ Rn we have
 
ME←B = [⃗b1 ]E · · · [⃗bn ]E .
−1
Furthermore, ME←B is invertible and we have ME←B = MB←E .

Proof. Thisproof  will generalize what we did in the previous examples. Suppose
x1
that [⃗x]B =  ...  . Then we have ⃗x = x1⃗b1 + · · · + xn⃗bn . Writing this equation in
 

xn
standard coordinates gives
 
x1
 .. 
 
[⃗x]E = [⃗b1 ]E ··· [⃗bn ]E  . 
xn
 
= [⃗b1 ]E · · · [⃗bn ]E [⃗x]B ,
 
and so ME←B = [⃗b1 ]E · · · [⃗bn ]E , as needed. Next, since B is linearly inde-
pendent, by the Invertible Matrix Theorem (Theorem 6.15), the matrix ME←B is
invertible, and so we have
−1
[⃗x]E = ME←B [⃗x]B ⇒ [⃗x]B = ME←B [⃗x]E .
−1
Hence, ME←B = MB←E . □

This result tells us how to change between the standard basis for Rn and a non-
standard basis. To generalize this idea to changing between two arbitrary bases,
we need the following lemmas, whose proofs will be left to a Chapter Exercise.
Lemma 9.6. Let C be a basis for a vector space V . Then, for any ⃗x, ⃗y ∈ V and
scalar k ∈ R we have
[⃗x + ⃗y ]C = [⃗x]C + [⃗y ]C and [k⃗x]C = k[⃗x]C .
94 9. [DRAFT - subject to revision] Coordinate Systems and Change of Basis

Lemma 9.7. Let {⃗b1 , . . . , ⃗bn } be a linearly independent subset of a vector space V .
Then, for any basis C of V , the set {[⃗b1 ]C , . . . , [⃗bn ]C } is linearly independent.

We are now prepared to show the following.

Theorem 9.8. Let V be a vector space with basis  C = {⃗c1 , . . . , ⃗cn }. Then,
 a subset
⃗ ⃗ ⃗ ⃗
B = {b1 , . . . , bn } of V is a basis for V if and only if [b1 ]C · · · [bn ]C is invertible.
In this case, we have  
MC←B = [⃗b1 ]C ··· [⃗bn ]C .
−1
and furthermore MC←B = MB←C .
 
x1
Proof. Suppose first that B is a basis. Then, for any ⃗x in V , let [⃗x]B =  ... .
 

xn
⃗ ⃗
Then we have ⃗x = x1 b1 + · · · + xn bn . Writing this equation in C-coordinates gives
[⃗x]C = [x1⃗b1 + · · · + xn⃗bn ]C .
By Lemma 9.6 this gives
[⃗x]C = x1 [⃗b1 ]C + · · · + xn [⃗bn ]C
 
 x1
= [⃗b1 ]C · · · [⃗bn ]C  ... 

 

xn
 
= [⃗b1 ]C · · · [⃗bn ]C [⃗x]B ,
 
and so MC←B = [⃗b1 ]C · · · [⃗bn ]C . Now, by Lemma 9.7 we know that the
columns of MC←B are linearly independent, and so by the Invertible Matrix Theo-
rem (Theorem 6.15) MC←B is invertible. So,
−1
[⃗x]C = MC←B [⃗x]B ⇒ [⃗x]B = MC←B [⃗x]C .
−1
Hence, we have MC←B = MB←C .
 
Conversely, suppose that the matrix [⃗b1 ]C · · · [⃗bn ]C is invertible. To see that
B is linearly independent, consider the vector equation
α1⃗b1 + · · · + αn⃗bn = ⃗0.
Writing this equation in C-coordinates and applying Lemma 9.6 gives
 
0
⃗ ⃗  .. 
α1 [b1 ]C + · · · + αn [bn ]C =  .  .
0
 
Since [⃗b1 ]C · · · [⃗bn ]C is invertible, its columns must be linearly independent,
and so α1 = · · · = αn = 0, as needed. Finally, if B did not span V , then by
Chapter Exercise P3.9, we would have a basis for V of dimension larger than n.
This contradicts the fact that V is n-dimensional, and so B is a basis as needed. □
Exercises 95

Lecture Activity 9.5. Let V be the plane in R3 spanned by

   
 1 2 
C = 1 , 0 .
1 1
 

(1) Show that B is also a basis for V , where

   
 3 4 
B = 1 , 2 .
2 3
 

(2) Find the change of basis matrices MC←B and MC←B .

(3) Find a new basis D for V that’s not equal to B or C.

Exercises
P9.1 Prove Lemma 9.6.
P9.2 Prove Lemma 9.7.
P9.3 True or False: If B = {⃗b1 , . . . , ⃗bm } is a spanning set for a vector space V , then
every vector ⃗v in V has a unique representation in terms of B (that is, there
are unique real numbers x1 , . . . , xm so that ⃗v = x1⃗b1 + · · · + xm⃗bm ). If true,
provide a proof. If false, provide a counterexample and justify why this is a
counterexample.
P9.4 Let B, C and D be bases for a vector space V . Show that
MC←B MB←D = MC←D .
Note that this justifies our choice of notation for the change of basis matrix
(that is, why we’ve chosen to draw our arrows facing left instead of right).
P9.5 Let V be a vector subspace of Rn of dimension d, and let B and C be bases
for V . What is the size of the change of basis matrix MC←B ? Justify your
answer.
 Chapter 10

[DRAFT - subject to revision]

Similarity and Diagonalization

10.1. Defining Matrices

Recall that for any linear transformation F : Rn → Rm there’s a matrix MF so that
F (⃗x) = MF ⃗x, which we called the defining matrix of F . Furthermore, in Theorem
4.8 we found that


MF = F (⃗e1 ) · · · F (⃗en ) .
Note that this story was told in terms of the standard basis. That is,
[F (⃗x)]E = MF [⃗x]E ,


where MF = [F (⃗e1 )]E · · · [F (⃗en )]E . Let’s look at what happens if we instead
consider our transformation with respect to a basis other than the standard one.
Theorem 10.1. Let F : Rn → Rn be a linear transformation and B be any basis
for Rn . Then, there exists a unique n × n matrix M so that [F (⃗x)]B = M [⃗x]B .
Furthermore, we have M = [F (⃗b1 )]B · · · [F (⃗bn )]B .

Proof. This proof will follow similarly to Theorem 4.8. Take any ⃗x ∈ Rn and write
⃗x = x1⃗b1 + · · · + xn⃗bn . Then,
[F (⃗x)]B = [F (x1⃗b1 + · · · + xn⃗bn )]B
= [x1 F (⃗b1 ) + · · · + xn F (⃗bn )]B since F is linear
= x1 [F (⃗b1 )]B + · · · + xn [F (⃗bn )]B by Lemma 9.6
 
 x1
= [F (⃗b1 )]B · · · [F (⃗b1 )]B  ... 

 

xn
 
= [F (⃗b1 )]B · · · [F (⃗b1 )]B [⃗x]B ,

97
98 10. [DRAFT - subject to revision] Similarity and Diagonalization

as needed. □

Definition 10.2. Let F : Rn → Rn be a linear transformation, and B be any basis

for Rn . Then, the defining matrix of F with respect to the basis B is the
matrix M so that
[F (⃗x)]B = M [⃗x]B .
We use the notation M = MF,B . By Theorem 10.1 we have
 
MF,B = [F (⃗b1 )]B · · · [F (⃗bn )]B .

Lecture Activity 10.1. Let B = {⃗b1 , ⃗b2 } be the basis with

   
⃗b1 = 1 , ⃗b2 = −2 .
1 1
P1. Let F : R2 → R2 be the linear transformation which stretches vectors
in the ⃗b1 direction by 2 and leaves vectors in the ⃗b2 direction fixed.
That is,
F (x1⃗b1 + x2⃗b2 ) = 2x1⃗b1 + x2⃗b2 .
Find the defining matrix MF,B .
P2. Let G : R2 → R2 be a linear transformation with linearly independent
eigenvectors ⃗v and w ⃗ with corresponding eigenvalues λ1 , λ2 . Letting
B = {⃗v , w},
⃗ find the defining matrix MG,B .

10.2. Matrix Similarity

Note that the defining matrix of a function depends on our choice of basis. Usually,
if B and C are distinct bases for Rn , then MF,B and MF,C will be different matrices.
However, we don’t want to lose track of the fact that these two matrices are related
to each other. We define the following.
Definition 10.3. Two n × n matrices B and C are called similar if they represent
the same function, but in possibly different bases. That is, there is a single linear
function F : Rn → Rn so that
MF,B = B and MF,C = C,
where B and C are bases for Rn .

 
1 2
Lecture Activity 10.2. Let B = . Find a matrix C that’s similar
3 4
to B, but not equal to B.

In the following proposition, we derive an algebraic method to detect matrix simi-

larity using our results from the previous section.
Theorem 10.4. Two n × n matrices B and C are similar if and only if there exists
an invertible n × n matrix P so that B = P −1 CP.
10.2. Matrix Similarity 99

Proof. Suppose that B and C are similar n × n matrices. Then, by definition,

there exists a linear transformation F : Rn → Rn and bases B, C for Rn so that
MF,B = B and MF,C = C.
Recalling our definition of defining matrices from the previous section, we have
[F (⃗x)]C = C[⃗x]C .
Now, let’s use our change of basis matrix: we have MC←B [F (⃗x)]B = [F (⃗x)]C and
MC←B [⃗x]B = [⃗x]C . Replacing this into the equation above yields
MC←B [F (⃗x)]B = CMC←B [⃗x]B .
Setting P := MC←B we have
P [F (⃗x)]B = CP [⃗x]B .
Recall that P is invertible, and so we can multiply the left-hand side of the equality
above to get
[F (⃗x)]B = P −1 CP [⃗x]B .
But then, by definition of defining matrices, B = P −1 CP .

Conversely, suppose that B = P −1 CP for an invertible matrix P . Let F : Rn →

Rn be the linear transformation with standard defining  matrix MF = C. Let
⃗ ⃗
B = {b1 , . . . , bn } be the set of vectors so that P = [b1 ]E · · · [⃗bn ]E . Since P is
⃗
invertible, by Theorem 9.8 we have that B is a basis for Rn with P = ME←B and
P −1 = MB←E . So,
B[⃗x]B = P −1 CP [⃗x]B
= MB←E C ME←B [⃗x]B
= MB←E C [⃗x]E
= MB←E [F (⃗x)]E
= [F (⃗x)]B .
Hence, B = MF,B is the defining matrix of F with respect to the basis B. So, we’ve
found a single linear transformation F : Rn → Rn so that C = MF,E and B = MF,B .
Therefore, B and C are similar. □

Lecture Activity 10.3. .

P1. Show that if matrices B and C are similar, then B is invertible if and
only if C is invertible. (Hint: use Proposition 10.4 and determinants.)

P2. Use P1 to show that the matrices

   
1 2 0 1 1 1
B = 0 0 1 and C = 0 2 2
1 0 1 1 −1 −1
are not similar
100 10. [DRAFT - subject to revision] Similarity and Diagonalization

Remark 10.5. With the tools we currently have, it is generally challenging for us
to determine whether two matrices are similar. In the following section, we develop
a method to detect matrix similarity for a special families of matrices.

10.3. Diagonalization
Let’s return to our eigen-story from Chapter 9, and generalize what we found in
Lecture Activity 10.1.

Lecture Activity 10.4. Let A be an n×n matrix. Show that if {⃗v1 , . . . , ⃗vn }
is a linearly independent set of eigenvectors, then A is similar to a matrix
of the form
 
λ1 0 · · · 0
 0 λ2 · · · 0 
..  .
 
 .. .. ..
. . . . 
0 0 · · · λn

We define the following.

Definition 10.6. A matrix D is called diagonal if the only nonzero entries in
the matrix appear on the diagonal. That is,
 
d1 0 · · · 0
 0 d2 · · · 0 
D=. ..  .
 
.. . .
 .. . . .
0 0 ··· dn
In this case, we write D = diag(d1 , d2 , . . . , dn ).

Note that if D = diag(d1 , d2 , . . . , dn ) then

   
x1 d1 x1
 x2   d2 x2 
D .  =  . ,
   
 ..   .. 
xn dn xn
and so the matrix transformation TD can be understood as the transformation
which stretches each coordinate of a vector by a of factor di , for i = 1, . . . , n. We’ll
describe this as a dilation transformation.

Definition 10.7. An n × n matrix A is called diagonalizable if it is similar to

a diagonal matrix.

Observe that a matrix A is diagonalizable if it’s the defining matrix for a function
F : Rn → Rn with respect to some basis B of Rn . So, if we view Rn with respect
to B-coordinates, we see that F behaves as a dilation transformation.

The following result will help us characterize which matrices are diagonalizable.
10.3. Diagonalization 101

Theorem 10.8 (The Diagonalization Theorem). An n × n matrix A is diago-

nalizable if and only if A has n linearly independent eigenvectors. In this case,
there are linearly independent eigenvectors ⃗v1 , . . . , ⃗vn with corresponding eigenval-
ues λ1 , . . . , λn for A so that then D = C −1 AC where


D = diag(λ1 , . . . , λn ) and C = ⃗v1 · · · ⃗vn .

Proof. Observe that we showed the backward direction in Lecture Activity 10.4.
For the forward direction, suppose that A is diagonalizable.

Then, by Theorem
10.4, there’s an invertible matrix C = ⃗v1 · · · ⃗vn and diagonal matrix D =
diag(d1 , . . . , dn ) so that
D = C −1 AC
Since C is invertible, we know that B = {⃗v1 , . . . , ⃗vn } is a linearly independent set,
and hence forms a basis for Rn . So, we just need to show that ⃗vi is an eigenvector
with eigenvalue di for all i = 1, . . . , n. Observe that
(10.1) C⃗ei = ⃗vi ⇒ ⃗ei = C −1⃗vi
and so we have
A⃗vi = CDC −1⃗vi
= CD⃗ei , by Equation (10.1)
= Cdi⃗ei , since the ith column of D is di⃗ei
= di C⃗ei
= di⃗ci , by Equation (10.1)
So, ⃗vi is an eigenvector of A with eigenvalue di . □

Lecture Activity 10.5. Determine which of the following matrices Ai are

diagonalizable. For those that are, find an invertible matrix Ci and diagonal
matrix Di so that Di = Ci−1 Ai Ci .
 
0 1
P1. A1 =
2 1
 
0 1 0
P2. A2 = 0 0 1
2 −5 4
 
4 −3 0
P3. A3 = 2 −1 0 .
1 −1 1

To use the Diagonalization Theorem more efficiently, it would be useful to have

methods to detect when A has enough linearly independent eigenvectors. The
following Proposition will help with this.
Proposition 10.9. Let λ1 , . . . , λk be distinct eigenvalues of a matrix A, and sup-
pose that ⃗vi ∈ Eλi for each i ∈ {1, . . . , k}. Then {⃗v1 , . . . , ⃗vk } is a linearly indepen-
dent set.
102 10. [DRAFT - subject to revision] Similarity and Diagonalization

Proof. This result follows by induction. We give the idea for the induction step be-
low, and leave the details as a suggested exercise for the interested reader. Suppose
that ⃗v1 , ⃗v2 , . . . , ⃗vn are eigenvectors of a matrix A with corresponding eigenvalues
λ1 , λ2 , . . . , λn , where the eigenvalues are all distinct. Consider the vector equation
(10.2) x1⃗v1 + · · · + xn⃗vn = ⃗0.
Multiplying Equation (10.2) by λ1 gives
x1 λ1⃗v1 + x2 λ1⃗v1 + · · · + xn λ1⃗vn = ⃗0.
Multiplying Equation (10.2) by A, and using that A⃗vi = λi⃗vi , gives
x1 λ1⃗v1 + x2 λ2⃗v2 + · · · + xn λn⃗vn = ⃗0.
Subtracting these two equations yields
x2 (λ2 − λ1 )⃗v2 + · · · + xn (λn − λ1 )⃗vn = ⃗0.
Note that {(λ2 − λ1 )⃗v2 , . . . , (λn − λ1 )⃗vn } is a set of n − 1 distinct eigenvectors
(noting that none of these vectors are nonzero, since our eigenvalues are distinct).
Hence, the proof follows by induction. □

This gives one strategy to more quickly detect whether a matrix is diagonalizable.
Proposition 10.10. An n × n matrix A is diagonalizable if and only if the sum of
the geometric multiplicities of A is equal to n.

The proof of this result is a bit more technical than we have time for together. We
include the details of this result below for interested students, but note that this
proof is not required material for the course.

Proof. Let λ1 , . . . , λm be the distinct eigenvalues of A, and let the λi -Eigenspace

Eλi have basis Bi for each i ∈ {1, . . . , m}. Suppose first that A is diagonalizable.
Then, by the Diagonalization Theorem (Theorem 10.8), we know that A has n
linearly independent eigenvectors which we label so that
{⃗v11 , . . . , ⃗v1k1 } ⊆ Eλ1
{⃗v21 , . . . , ⃗v2k2 } ⊆ Eλ2
..
.
{⃗vm1 , . . . , ⃗vmkm } ⊆ Eλm
where k1 + · · · + km = n. This gives
dim(Eλ1 ) + · · · + dim(Eλm ) ≥ k1 + · · · km = n.
That is, the sum of the geometric multiplicities is at least n. To see that this sum
is no larger than n, note that B1 ∪ · · · ∪ Bm is a linearly independent set. Indeed,
let Bi = {⃗bi1 , . . . , ⃗bidi } and consider the vector equation
m 
X 
(10.3) xi1⃗bi1 + · · · + xidi⃗bidi = ⃗0.
i=1
For each i = 1, . . . , m let
⃗ i = xi1⃗bi1 + · · · + xidi⃗bidi .
w
10.4. Eigendecompositions 103

Replacing this into Equation (10.3) yields

⃗ m = ⃗0.
⃗1 + · · · + w
w
But since w ⃗ i ∈ Eλi , then by Proposition 10.9 we must have w⃗ i = ⃗0 for all i =
1, . . . , m (otherwise we would have a nontrivial linear combination of eigenvectors
with distinct eigenvalues, contradicting linear independence). Hence, this gives
xi1⃗bi1 + · · · + xidi⃗bidi = ⃗0
and so xi1 = · · · = xidi = 0 for all i = 1, . . . , m, since Bi is a linearly independent set.
Thus, Equation (10.3) only has the trivial solution, which gives that B1 ∪ · · · ∪ Bm
is a linearly independent independent subset of Rn , which by Lemma 3.13 is no
larger than n. That is,
#(B1 ∪ · · · ∪ Bm ) ≤ n.
Furthermore, since the Bi do not intersect, then the inclusion-exclusion principle
gives
#(B1 ∪ · · · ∪ Bm ) = #B1 + · · · + #Bm = dim(Eλ1 ) + · · · + dim(Eλm ).
The two results above yield
dim(Eλ1 ) + · · · + dim(Eλm ) ≤ n,
as needed. Conversely, suppose that the sum of the geometric multiplicities of A is
equal to n. Since dim(Eλi ) = #Bi then using the same reasoning as above, we see
that B1 ∪ · · · ∪ Bm is a linearly independent subset of eigenvectors containing
dim(E1 ) + · · · + dim(Em ) = n
elements, as needed. □

Lecture Activity 10.6. Use Proposition 10.10 to more quickly determine

which of the matrices from Lecture Activity 10.5 are diagonalizable.
 
0 1
P1. A1 =
2 1
 
0 1 0
P2. A2 = 0 0 1
2 −5 4
 
4 −3 0
P3. A3 = 2 −1 0 .
1 −1 1

10.4. Eigendecompositions
Note that if A is diagonalizable with D = C −1 AC we can write A = CDC −1 . This
gives a useful decomposition of our matrix A. We have the following definition.
Definition 10.11. Suppose that A is an n × n diagonalizable matrix with eigen-
values λ1 , . . . , λn and corresponding linearly independent

eigenvectors ⃗v1 , . . . , ⃗vn .
Let D = diag(λ1 , . . . , λn ) and C = ⃗v1 · · · ⃗vn . We call the equality
A = CDC −1
104 10. [DRAFT - subject to revision] Similarity and Diagonalization

the eigendecomposition of the matrix A.

Lecture Activity 10.7. Find a 2 × 2 matrix A so 

that
 the linear transfor-
2 2 1
mation TA : R → R stretches every vector in the direction by 2 and
  1
0
in the direction by 3.
−1

Note that the eigendecomposition can also help us compute large powers of a matrix.
We have the following.
Proposition 10.12. Let A be a diagonalizable matrix with eigendecomposition
A = CDC −1 . Then,
An = CDn C −1
for any integer n.

Proof. We have
An = (CDC −1 )n
= (CDC −1 )(CDC −1 ) · · · (CDC −1 )
| {z }
n times
−1 −1
= CD(C C)DC · · · CDC −1
| {z }
n times
= C DD · · · D} C −1
| {z
n times
n −1
= CD C . □

Lecture Activity 10.8. Let

 
4 −3 0
A3 = 2 −1 0 .
1 −1 1
Use your work from Lecture Activity 10.5 to calculate A10
3 by hand (noting
that 210 = 1024).

In Chapter Exercise 10.9, you’ll see how eigendecompositions can help us study
other mathematical objects, such as the Fibonacci sequence.

Exercises

P10.1 Show that if A and B are similar matrices, then χA = χB . Conclude that
similar matrices have the same eigenvalues.
P10.2 Show that if A is diagonalizable, then An is diagonalizable for any positive
integer n.
Exercises 105

P10.3 Show that if A is diagonalizable, then A⊤ is diagonalizable.

P10.4 Show that if an n × n matrix A has n distinct eigenvalues, then A is diago-
nalizable.
P10.5 True or false: if A is diagonalizable, then A must have n distinct eigenvalues.
If true, provide a proof. If false, provide a counterexample and justify why
this is a counterexample.
P10.6 Recall that a matrix A is called nilpotent if Am is equal to the zero matrix
for some positive integer m. True or False: If A is nilpotent and diagonaliz-
able, then A must be equal to the zero matrix. If true, provide a proof. If
false, provide a counterexample and justify why this is a counterexample.
P10.7 True or False: If A is diagonalizable, then A must be invertible. If true,
provide a proof. If false, provide a counterexample and justify why this is a
counterexample.
P10.8 A horizontal shear is a function F : R2 → R2 defined by
   
x x + my
F =
y y
and a vertical shear is a function G : R2 → R2 defined by
   
x x
G = .
y y + mx
Show that the shear functions are not diagonalizable when m ̸= 0.
P10.9 The Fibonacci sequence is the linear recurrence sequence {fn } defined by
f0 = 0, f1 = 1, and fn+2 = fn+1 + fn .
In this problem, we’ll observe how eigendecompositions can help us study
this sequence.
(a) Find f12 by hand (don’t look it up, use the recurrence definition)
(b) Explain why the following identity holds for any integer n
    
fn 0 1 fn−1
=
fn+1 1 1 fn
(c) Use the previous part to show that
   n  
fn 0 1 0
=
fn+1 1 1 1
for every integer n. (Note: you do not need to show this formally)
(d) Use the eigendecompositions to show that
αn − β n
fn =
α−β
where √ √
1+ 5 1− 5
α= and β = .
2 2
(Note that α, β are the eigenvalues of the matrix above).
(e) Use part (d) to compute f12 again (we suggest using wolfram alpha)
and check that it matches what you found in part (a). Also compute
f20 , f50 and f100 .
 Chapter 11

[DRAFT - subject to revision]

Orthogonality

11.1. The Dot Product

In this chapter, we’ll add some geometric information to our story, in order to gain
a further understanding of a linear transformation behaves. Our first goal will be
to generalize notions of distance and angles to higher dimensions. Let’s first recall
how to calculate these quantities in two-dimensional space.

Lecture Activity 11.1. Let ⃗u and ⃗v be the vectors drawn below.

 
u1
⃗u =
u2

 
v1
⃗v =
v2

P1. Find a formula for the length of ⃗u and ⃗v .

P2. Find a formula for the distance between ⃗u and ⃗v . That is, find the
distance between the points (u1 , u2 ) and (v1 , v2 ).

To generalize our formulas from Lecture Activity 11.1 to higher-dimensional spaces,

we define the following operation.

Definition 11.1. Let ⃗u and ⃗v be vectors in Rn with standard-basis coordinates

   
u1 v1
 u2   v2 
⃗u =  .  and ⃗v =  .  .
   
 ..   .. 
un vn

107
108 11. [DRAFT - subject to revision] Orthogonality

The dot product of ⃗u and ⃗v is the scalar

⃗u · ⃗v := u1 v1 + u2 v2 + · · · + un vn .
Example 11.2. We have
   
1 −1
2 ·  0  = 1(−1) + 2(0) + 3(2) = 5.
3 2
Keep in mind that the dot product of two vectors produces a scalar.
In the following activity, we’ll that the dot product can help us capture our geo-
metric notions of distance and angle. We first need the following lemma, whose
proof is left as a Chapter Exercise.
Lemma 11.3. Let ⃗u, ⃗v and w ⃗ be vectors in Rn and let c ∈ R be a scalar. Then,
the dot product satisfies the following properties:
(1) Commutativity: ⃗u · ⃗v = ⃗v · ⃗u
(2) Distributivity with Addition: (⃗u + ⃗v ) · w
⃗ = ⃗u · w
⃗ + ⃗v · w
⃗
(3) Distributivity with Scalar Multiplication: (c⃗u) · ⃗v = c(⃗u · ⃗v )

Lecture Activity 11.2.√Let ⃗u and ⃗v be vectors in R2 , and define the

following notation ∥⃗u∥ := ⃗u · ⃗u. Use your work from Lecture Activity 11.1
to show the following.
P1. Show that the length of ⃗u is equal to ∥⃗u∥.
P2. Show that the distance between ⃗u and ⃗v is equal to ∥⃗u − ⃗v ∥
P3. Show that the angle between ⃗u and ⃗v is equal to
⃗u · ⃗v
θ = arccos .
∥⃗u∥∥⃗v ∥
Conclude that ⃗u and ⃗v are perpendicular if and only if ⃗u · ⃗v = 0.

Our work in Lecture Activity 11.2 leads to the following definitions.

Definition 11.4. Let ⃗u and ⃗v be vectors in Rn .
(1) The norm of a vector ⃗u in Rn is defined by
√
∥⃗u∥ := ⃗u · ⃗u.
(2) The distance between vectors ⃗u and ⃗v is defined by
d(⃗u, ⃗v ) := ∥⃗u − ⃗v ∥.
(3) We say that ⃗u and ⃗v are orthogonal if ⃗u · ⃗v = 0.

Lecture Activity 11.3. Determine which of the following pairs of vectors

⃗u and ⃗v are orthogonal.
   
2 −1
P1. ⃗u = and ⃗v =
1 2
11.2. Orthonormal Bases and Orthogonal Matrices 109

   
−1 2
P2. ⃗u =  0  and ⃗v = 1
1 1
   
1 1
2 −1
3 and ⃗v =  0 
P3. ⃗u =    

1 1

11.2. Orthonormal Bases and Orthogonal Matrices

In the previous chapters, we saw that the fundamental object needed to understand
a vector space is a basis. We learned that real vector spaces of dimension n are all
isomorphic to Rn , and we saw how different bases define coordinate systems on our
vector spaces which can help us better understand certain linear transformations.
In this section, we look at how bases interact with the dot product.
Definition 11.5. A basis B = {⃗v1 , ⃗v2 , . . . , ⃗vn } is orthogonal if ⃗vi · ⃗vj = 0 for
every i ̸= j. A basis B is called orthonormal if it’s orthogonal and ∥⃗vi ∥ = 1 for
every ⃗vi in B.

Lecture Activity 11.4. Consider the bases B, C and D for R2 given by

( ! !)
√1 √1
       
1 1 1 1 2 2
B= , ,C = , and D = √1
, ,
2 1 1 −1 2
− √12
P1. Determine which of the bases above are orthogonal and which are or-
thonormal.  
u1
P2. Calculate ⃗u · ⃗u given that [⃗u]B = .
 u2
v
P3. Calculate ⃗v · ⃗v given that [⃗v ]C = 1 .
v2 
w1
P4. Calculate w⃗ ·w ⃗ given that [w]⃗D= .
w2
P5. What did you notice in your calculations?

The following Proposition tells us that orthonormal bases preserve dot products,
and as a consequence preserve distances and angles.
Proposition 11.6. Let B be an orthonormal basis for Rn and take any vectors
⃗x, ⃗y in Rn . Then
[⃗x]B · [⃗y ]B = ⃗x · ⃗y .
In particular, we have ∥⃗x∥ = ∥[⃗x]B ∥.

Proof. Suppose that B = {⃗v1 , ⃗v2 , . . . , ⃗vn } is an orthonormal basis for Rn and write
   
x1 y1
 ..   .. 
[⃗x]B =  .  and [⃗y ]B =  .  .
xn yn
110 11. [DRAFT - subject to revision] Orthogonality

That is,
⃗x = x1⃗v1 + · · · + xn⃗vn
⃗y = y1⃗v1 + · · · + yn⃗vn .
Then we have
⃗x · ⃗y = (x1⃗v1 + · · · + xn⃗vn ) · (y1⃗v1 + · · · + yn⃗vn )
Using the distributive properties of the dot product (Proposition 11.3), we’ll end
up with a sum of terms of the form
xi yj ⃗vi⃗vj .
But, since we know that ⃗vi · ⃗vj = 0 whenever i ̸= j then we have
⃗x · ⃗y = x1 y1⃗v1 · ⃗v1 + · · · xn yn⃗vn · ⃗vn .
But we also know that ⃗vi · ⃗vi = ∥⃗v ∥2 = 1, since our basis is orthonormal. So, we
have
⃗x · ⃗y = x1 y1 + · · · + xn yn
as desired. □

⃗ ⃗
Lecture Activity 11.5. Suppose that B = {b1 , b2 } is an orthonormal basis
2 ⃗ ⃗
for R , and consider the matrix Q = b1 b2 .
P1. Show that !
⃗b · ⃗b ⃗b · ⃗b
Q⊤ Q = ⃗ 1 ⃗ 1 ⃗ 1 ⃗ 2 .
b2 · b1 b2 · b2
P2. Use P1 to show that Q⊤ Q = I2 .
P3. Conclude that Q is invertible with Q−1 = Q⊤ .

Our work from Lecture Activity 11.5 generalizes.

Proposition 11.7. Let B = {⃗v1 , . . . , ⃗vn } be a basis for Rn and let Q be the matrix
with column vectors ⃗v1 , . . . , ⃗vn . Then B is orthonormal if and only if Q−1 = Q⊤ .

Proof. Let Q be the matrix with column vectors ⃗vi . Then Q⊤ is the matrix with
rows ⃗vi , and so we can observe that
 
⃗v1 · ⃗v1 ⃗v1 · ⃗v2 · · · ⃗v1 · ⃗vn
⃗v2 · ⃗v1 ⃗v2 · ⃗v2 · · · ⃗v2 · ⃗vn 
Q⊤ Q =  . ..  .
 
.. ..
 .. . . . 
⃗vn · ⃗v1 ⃗vn · ⃗v2 ··· ⃗vn · ⃗vn
So, Q⊤ Q = In if and only if
(
0 if i ̸= j
⃗vi · ⃗vj =
1 if i = j.
which occurs precisely when {⃗v1 , . . . , ⃗vn } forms an orthonormal basis for Rn . □

This gives rise to the following (somewhat annoying) definition.

11.3. The Gram-Schmidt Process 111

Definition 11.8. We call an n × n matrix Q orthogonal if its column vectors

form an orthonormal basis for Rn . Equivalently, Q is called orthogonal if Q⊤ =
Q−1 .
Remark 11.9. This definition is a little annoying, because orthogonal matrices
aren’t just those matrices with orthogonal column vectors, but rather with or-
thonormal column vectors. I don’t know why we don’t just call them orthonormal
matrices. My guess is because matrices with column vectors that are orthogonal,
but not orthonormal, don’t have many nice properties so they don’t get their own
name.

Just for fun and in case you’re interested, Hadamard matrices are matrices with
orthogonal (but not orthonormal) column vectors which only have entries equal to
±1. It can be shown that for an n × n Hadamard matrix H we have HH ⊤ = nIn
so that H −1 = (1/n)H ⊤ .

11.3. The Gram-Schmidt Process

In this section, we’ll show that every vector space has an orthonormal basis, and in
fact that we can produce an orthonormal basis algorithmically given any generating
set for our space. To do this, we’ll need to develop the notion of “orthogonal
projections”.

Lecture Activity 11.6. Let ⃗x and ⃗y be vectors in R2 , and let ⃗z be the

closets point in Span(⃗y ) to ⃗x. That is, ⃗z is the point in Span(⃗y ) so that
d(⃗x, ⃗z) is as small as possible.
P1. Use the picture below to argue that ⃗y is orthogonal to ⃗x − ⃗z.

⃗x

⃗y
⃗z

P2. Since ⃗z is in Span(⃗y ), we can write ⃗z = c⃗y for some real number c. Use
the previous part to show that
⃗x · ⃗y
c= .
⃗y · ⃗y
P3. Conclude that the closest point on Span(⃗y ) to ⃗x is given by
⃗x · ⃗y
⃗z = ⃗y .
⃗y · ⃗y

Using our work in R2 , we can define the following.

Definition 11.10. For vectors ⃗x, ⃗y in Rn , the orthogonal projection of ⃗x onto
⃗y is given by
⃗x · ⃗y
proj⃗y ⃗x := ⃗y .
⃗y · ⃗y
112 11. [DRAFT - subject to revision] Orthogonality

As we saw in Activity 11.7, when our vectors are in R2 or R3 , the orthogonal

projection proj⃗y ⃗x is the closest point on Span(⃗y ) to ⃗x. We are now prepared to
prove the following.
Theorem 11.11 (The Gram-Schmidt Process). Every vector space has an orthog-
onal basis. Furthermore, if V is a vector subspace of Rn with basis {⃗v1 , ⃗v2 , . . . , ⃗vm },
and we let
⃗u1 = ⃗v1
⃗u2 = ⃗v2 − proj⃗u1 ⃗v2
⃗u3 = ⃗v3 − proj⃗u1 ⃗v3 − proj⃗u2 ⃗v3
..
.
⃗um = ⃗vm − proj⃗u1 ⃗vm − proj⃗u2 ⃗vm − · · · − proj⃗um−1 ⃗vm ,
then, {⃗u1 , . . . , ⃗um } is an orthogonal basis for V . Furthermore,
⃗u1 ⃗um
{ ,..., }
∥⃗u2 ∥ ∥⃗um ∥
is an orthonormal basis for V .

The proof for Gram-Schmidt needs induction. Instead of working out these techni-
cal details, let’s take a look at an example to understand why the result holds.
Example 11.12. Let V = Span(⃗v1 , ⃗v2 , ⃗v3 ) be the subspace of R3 with
     
1 1 2
⃗v1 = 1 , ⃗v2 =  1  , and 0 .
0 −1 2
Note that V = R3 in this case, and we know that the standard basis forms an
orthonormal basis, but let’s look at how Gram-Schmidt edits the given basis.
 
1
First, set ⃗u1 := ⃗v1 = 1. Then we let
0

0
⃗u2 := ⃗v2 − proj⃗u1 ⃗v2 =  0  .
−1
Observe that ⃗u1 is orthogonal to ⃗u2 . We can see why this step works geometrically
(as in P1 of Lecture Activity 11.6), or algebraically as demonstrated below
 
⃗v2 · ⃗u1 ⃗v2 · ⃗u1
⃗u1 · ⃗u2 = ⃗u1 ⃗v2 − ⃗u1 = ⃗u1 · ⃗v2 − ⃗u1 · ⃗u1 = 0.
⃗u1 · ⃗u1 ⃗u1 · ⃗u1
Furthermore, since proj⃗u1 ⃗v2 ∈ Span(⃗u1 ) = Span(⃗v1 ) then we can write ⃗u2 = ⃗v2 −c⃗v1
for some c ∈ R and so ⃗u2 ∈ V . Next, we let
 
1
⃗u3 := ⃗v3 − proj⃗u1 ⃗v3 − proj⃗u2 ⃗v3 = −1 .
0
11.4. The Spectral Theorem 113

Observe that ⃗u3 is orthogonal to ⃗u1 and ⃗u2 . We can see why this step works by
noting the following:
• ⃗u1 is orthogonal to ⃗v3 − proj⃗u1 ⃗v3 , using an argument similar to above;
• Since ⃗u1 is orthogonal to ⃗u2 from the previous step, and proj⃗u2 ⃗v3 is in
Span(⃗u2 ), then ⃗u1 is orthogonal to proj⃗u2 ⃗v3 .
Combining these observations gives
⃗u1 · ⃗u3 = ⃗u1 · (⃗v3 − proj⃗u1 ⃗v3 − proj⃗u2 ⃗v3 )
= ⃗u1 · (⃗v3 − proj⃗u1 ⃗v3 ) − ⃗u1 · proj⃗u2 ⃗v3 )
= 0 − 0 = 0.
We can argue similarly to show that ⃗u2 ·⃗u3 = 0 and so B = {⃗u1 , ⃗u2 , ⃗u3 } is an orthog-
onal set. Now, we need to check that it’s still a basis for V . By Chapter Exercise
P11.9, the set is linearly independent, and from above we know that {⃗u1 , ⃗u2 , ⃗u3 } is
a subset of V . Since dim(V ) = 3, then by Theorem 3.12 we have that B forms a
basis.
Finally, now that we have an orthogonal set, we can make it orthonormal by dividing
each vector by its norm. This gives the orthonormal basis
 √     √ 
 1/√2 0 1/ √2 
1/ 2 ,  0  , −1/ 2 .
0 −1 0
 

The key point we should take away from this section is that every vector space
has an orthonormal basis, and moreover that such a basis can be found algo-
rithmically as demonstrated above.

11.4. The Spectral Theorem

Let’s return to our discussion on orthogonal matrices. Using our work in Proposition
11.7, we can see that these matrices have a particularly nice geometric interpreta-
tion.
Theorem 11.13. Let Q be an n × n orthogonal matrix. Then, for any ⃗u, ⃗v in Rn
we have
Q⃗u · Q⃗v = ⃗u · ⃗v .
In particular, ∥Q⃗u∥ = ∥⃗u∥ and ⃗u is orthogonal to ⃗v if and only if Q⃗u is orthogonal
to Q⃗v .

Proof. Suppose that Q is orthogonal. Observe first that Q−1 is also orthogonal.
Indeed, by Proposition 11.13 we know that Q−1 = Q⊤ and so Q⊤ Q = In . This
gives (Q⊤ )−1 = Q ⇒ (Q⊤ )−1 = (Q⊤ )⊤ and so Q−1 = Q⊤ is orthogonal by Propo-
sition 11.13.
 
Next, let Q−1 = ⃗b1 · · · ⃗bn , and observe that Q−1 is the change of basis matrix
Q−1 = ME←B where B = {⃗b1 , . . . , ⃗bn }. So, we have Q = MB←E and since B is an
114 11. [DRAFT - subject to revision] Orthogonality

orthonormal basis, then by Proposition 11.7 we have

Q⃗u · Q⃗v = [⃗u]B · [⃗v ]B = ⃗u · ⃗v ,
as needed. Thus, we have
∥Q⃗u∥ = ⃗u · ⃗u = ∥⃗u∥,
and since Q⃗u · Q⃗v = ⃗u · ⃗v then we have ⃗u · ⃗v = 0 ⇔ Q⃗u = Q⃗v .

Note that the could also prove this algebraically – we include this version as well
for completeness. We have
⃗ = (Q⃗v )⊤ Qw
Q⃗v · Qw ⃗
= ⃗v ⊤ Q⊤ Qw
⃗
= ⃗v ⊤ w,
⃗ since Q⊤ = Q−1
= ⃗v · w,
⃗
as needed. □
Remark 11.14. Theorem 11.13 tells us that when Q is orthogonal, TQ is a trans-
formation that preserves distances and angles. So, we can reason geometrically
that Q must be either a rotation or reflection transformation. In Chapter Exercise
P11.8, you’ll prove this formally in the 2 × 2 case.

We define the following special family of matrices.

Definition 11.15. An n×n matrix A is orthogonally diagonalizable if there
exists an orthogonal matrix Q and a diagonal matrix D so that Q⊤ AQ = D.
Remark 11.16. Note that an n × n matrix A being orthogonally diagonalizable is
equivalent to the existence of an orthonormal basis for Rn consisting of eigenvectors
of A. This is a particularly nice situation, since orthonormal bases preserve the dot
product, and bases consisting of eigenvectors help us understand the linear trans-
formation TA . The Spectral Theorem will completely characterizes when we’re in
this situation.

Let’s first make an observation, which will be useful in our calculations throughout
the remainder of this chapter. Note that if ⃗x, ⃗y are vectors in Rn with standard
coordinate representations
   
x1 y1
 ..   .. 
⃗x =  .  and ⃗y =  .  ,
xn yn
then we can think of these as n × 1 matrices. This allows us to take the matrix
product  
y1
⊤

 . 

⃗x ⃗y = x1 · · · xn  ..  = x1 y1 + · · · + xn yn ,
yn
which gives the following useful identity
(11.1) ⃗x · ⃗y = ⃗x⊤ ⃗y .
11.4. The Spectral Theorem 115

Theorem 11.17 (The Spectral Theorem). An n × n matrix A is orthogonally

diagonalizable if and only if it is symmetric (that is, A = A⊤ ).

We first need the following lemma.

Lemma 11.18. Let A be symmetric. Then,
(1) A has at least one real eigenvalue, and
(2) if λ, µ are distinct eigenvalues of A, then for any ⃗x ∈ Eλ and ⃗y ∈ Eµ we have
that ⃗x and ⃗y are orthogonal.

Proof. Suppose that A is an n × n symmetric matrix. By the Fundamental Theo-

rem of Algebra, we know that the polynomial equation χA (x) = 0 has at least one
complex solution λ. Using similar methods to our discussion of eigenvectors in the
real case, it can be shown that there’s a nonzero vector ⃗v ∈ Nul(A − λIn ). Using
our identity stated after Remark 11.16 (Equation 11.1), we have
A⃗v · A⃗v = (A⃗v )⊤ (A⃗v )
= ⃗v ⊤ A⊤ A⃗v
= ⃗v ⊤ A2⃗v
= ⃗v ⊤ λ2⃗v
= λ2⃗v · ⃗v
= λ2 ∥⃗v ∥.
Hence, λ2 = ∥A⃗v ∥2 /∥⃗v ∥ > 0 and so λ is real.

Next, suppose that A has eigenvalues λ ̸= µ and let ⃗x ∈ Eλ and ⃗y ∈ Eµ . Then we

have
λ⃗x · ⃗y = A⃗x · ⃗y
= (A⃗x)⊤ ⃗y
= ⃗x⊤ A⊤ ⃗y
= ⃗x⊤ A⃗y , since A = A⊤
= ⃗x · µ⃗y
= µ⃗x · ⃗y ,
and so (λ − µ)⃗x · ⃗y = 0 ⇒ ⃗x · ⃗y = 0 since we’ve assumed that λ ̸= µ. □

We are now prepared to prove the Spectral Theorem.

Proof of Theorem 11.17. Suppose first that A is orthogonally diagonalizable.

Then, there exists an orthogonal matrix Q and diagonal matrix D so that
Q⊤ AQ = D ⇒ A = QDQ⊤ .
This gives
A⊤ = (Q⊤ )⊤ D⊤ Q⊤ = QDQ⊤ = A
noting that diagonal matrices are symmetric.
116 11. [DRAFT - subject to revision] Orthogonality

Conversely, suppose that A is symmetric. By Lemma 11.18 we know that A has a

real eigenvalue, and that eigenvectors of A with distinct eigenvalues are orthogonal.
Furthermore, by Gram-Schmidt we know that we can find an orthonormal basis for
each λ-eigenspace. So, what’s left to show is that our matrix is diagonalizable. To
do this, we’ll need proof by induction. We sketch the rest of this proof below for
completeness, but note that this method is beyond the scope of this course.

Note that any 1 × 1 matrix is diagonalizable. So, suppose that A is n × n and

symmetric. Let λ be a real eigenvalue of A with eigenvector ⃗v1 . By Gram-Schmidt,
we can extend this to an orthonormal basis {⃗v1 , . . . , ⃗vn } for Rn . So, if we let


Q = ⃗v1 · · · ⃗vn ,
then Q is orthogonal. Observe that Q⊤ AQ is of the form
 
⊤ λ1 0
Q AQ = ,
0 A1
where A1 is (n − 1) × (n − 1). Observing that A1 is symmetric, by induction it’s
diagonalizable, and so the result follows. □

Lecture Activity 11.7. Determine which of the following matrices are

orthogonally diagonalizable. For those that are, find an orthonormal basis
of eigenvectors.
 
3 2
P1. A = , given that χA (x) = (x − 2)(x − 7)
2 6 
1 1
P2. B = , given that χB (x) = (x + 1)(x − 2)
2 0 
2 1 1
P3. C = 1 2 1, given that χC (x) = −(x − 4)(x − 1)2
1 1 2

We define the following.

Definition 11.19. Suppose that A is an n × n symmetric matrix with eigenvalues
λ1 , . . . , λn and orthonormal basis of eigenvectors {⃗v1 , . . . , ⃗vn }. We call the equality
A = QDQ⊤
a spectral decomposition of A, where


D = diag(λ1 , . . . , λn ), and Q = ⃗v1 ··· ⃗vn .

Remark 11.20. When a matrix A has a spectral decomposition A = QDQ⊤ ,

the transformation TA : Rn → Rn can be decomposed into a rotation/reflection,
followed by a dilation, followed by the opposite rotation/reflection. Let’s look at an
example of how this decomposition can help us understand a matrix transformation
explicitly.
11.5. The Singular Value Decomposition 117

 
3 2
Lecture Activity 11.8. Consider the matrix A = from Lecture
2 6
Activity 11.7.
P1. Find a spectral decomposition for A. That is, find an orthogonal matrix
Q and diagonal matrix D so that A = QDQ⊤ .
P2. Use Chapter Exercise P11.8 to show that Q is a rotation matrix. Re-
calling that we can write
 
cos θ − sin θ
Q= ,
sin θ cos θ
find the angle θ.
P3. Using your work in the previous parts, give a geometric description of
how TA transforms R2 .

While the Spectral Theorem might seem like a special edge case, we can actually
use this result to obtain a similar geometric understanding of any matrix transfor-
mation. We explore this in our final section of the semester.

11.5. The Singular Value Decomposition

In this section, we’ll derive an important decomposition for any m × n matrix.
Geometrically, this decomposition will show as that any linear transformation can
be decomposed into a composition of three transformations: a rotation/reflection,
followed by a dilation, followed by another rotation/reflection (not necessarily in-
verse to the original rotation/reflection).

This decomposition will rest on the following result.

Proposition 11.21. Let A be an m×n matrix. Then, there exists an orthonormal
basis for Rn of eigenvectors of A⊤ A so that {A⃗v1 , . . . , A⃗vn } is an orthogonal subset
of Rm . Furthermore, if we reindex our basis so that A⃗v1 , . . . , A⃗vr are nonzero, and
A⃗vr+1 = · · · = A⃗vn = ⃗0, then {A⃗v1 , . . . , A⃗vr } forms an orthogonal basis for Col(A).

Proof. Observe first that A⊤ A is symmetric. Indeed, we have

(A⊤ A)⊤ = A⊤ (A⊤ )⊤ = A⊤ A.
So, by the Spectral Theorem, there there exists an orthonormal basis for Rn of
eigenvectors of A⊤ A. Suppose that the eigenvectors ⃗vi of A⊤ A have corresponding
eigenvalues λi . Then, for any i ̸= j we have
(A⃗vi ) · (A⃗vj ) = (A⃗vi )⊤ (A⃗vj )
= ⃗vi⊤ A⊤ A⃗vj
= ⃗vi⊤ (λj ⃗vj )
= ⃗vi · (λj ⃗vj )
= λj (⃗vi · ⃗vj )
= 0,
118 11. [DRAFT - subject to revision] Orthogonality

where the final equality follows because ⃗vi and ⃗vj are orthogonal when i ̸= j. Hence,
{A⃗v1 , . . . , A⃗vm } is an orthogonal subset of Rm .

Next, if we reindex as in the theorem statement, we see that A⃗y ∈ Col(A) if and
only if A⃗y = A(x1⃗v1 + · · · + xn⃗vn ) = x1 A⃗v1 + · · · + xr A⃗vr + ⃗0, and so

Col(A) = Span(A⃗v1 , . . . , A⃗vr ).

Since {A⃗v1 , . . . , A⃗vr } is orthogonal, then by Chapter Exercise P11.9 this set is
linearly independent, and hence is a basis as needed. □

Let’s look at an example to see what this Proposition gives us.

Lecture Activity 11.9. Consider the 3 × 2 matrix

 
1 1
A = 1 2  .
1 −1
Throughout this activity, we assume that all vectors are written with respect
to the standard basis.  
3 2
P1. Verify that A⊤ A = .
2 6
P2. Use your work from Lecture Activity 11.7 to find an orthonormal basis
for R2 of eigenvectors {⃗v1 , ⃗v2 } for A⊤ A.
P3. Use Proposition 11.21 to verify that B = {⃗u1 , ⃗u2 } where
A⃗v1 A⃗v2
⃗u1 = , ⃗u2 =
∥A⃗v1 ∥ ∥A⃗v2 ∥
is an orthonormal basis for im(TA ).
P4. Find a vector ⃗u3 so that {⃗u1 , ⃗u2 , ⃗u3 } is an orthonormal basis for R3 .
P5. Let’s use our work from the previous parts to decompose our transfor-
mation TA into three steps.


Step 1: Rotate/reflect. Let Q = ⃗v1 ⃗v2 where {⃗v1 , ⃗v2 } is
the orthogonal basis for R2 of eigenvectors for A⊤ A found in P2.
Find the angle θ so that TQ transforms R2 by rotating the plane
by θ degrees clockwise. Then, observe that
TQ⊤ : ⃗v1 7→ ⃗e1 , ⃗v2 7→ ⃗e2
by rotating the plane by θ degrees counter clockwise.

Step 2: Dilate and embed. Consider the “block-diagonal ”

matrix  
σ1 0
Σ =  0 σ2 
0 0
11.5. The Singular Value Decomposition 119

where σ1 = ∥A⃗v1 ∥ and σ2 = ∥A⃗v2 ∥. Give a geometric description

for the matrix-tranformation TΣ : R2 → R3 .

Step 3: Rotate/reflect. Let

U = ⃗u1 ⃗u2 ⃗u3
where {⃗u1 , ⃗u2 , ⃗u3 } is the orthonormal basis for R3 found in P4.
Show that det(U ) = 1. Use geometric reasoning to convince
yourself that U is a rotation matrix. Bonus: think about how
could you describe this rotation matrix explicitly.

P6. Use geometric reasoning, along with your work from P4, to show that
A = U ΣQ⊤ ,
where U and Q are orthogonal matrices, and Σ is a block diagonal
matrix. Discuss how this decomposition describes the transformation
TA : R2 → R3 as a rotation, followed by dilation/embedding, followed
by another rotation.

The singular value decomposition guarantees that every linear transformation can
be understood in this way. We have the following.
Theorem 11.22 (The Singular Value Decomposition). Let A be an m × n matrix.
Then, there exists an orthogonal m × m matrix U , an orthogonal n × n matrix Q
and a “block diagonal” matrix Σ so that
A = U ΣQ⊤ .

Proof. Suppose that A is an m × n matrix, and let {⃗v1 , . . . , ⃗vn } be the eigenvalues
of A⊤ A which form an orthonormal basis for Rn . By Proposition 11.7 we know
that


Q = ⃗v1 · · · ⃗vn
is an orthogonal matrix. Furthermore, we have


AQ = A⃗v1 ··· A⃗vn .
By Proposition 11.24 if we set A⃗vi = σi ⃗ui , then (up to reindexing) we know that
{⃗u1 , . . . , ⃗ur }
forms an orthonormal basis for Col(A). By Gram-Schmidt, we can extend this to an
orthonormal basis of Rm , say {⃗u1 , . . . , ⃗um }. Since we have σ⃗i = 0 for i = r+1, . . . , n
we get that A⃗vi = σi ⃗ui for all i. We have a few cases.

If n = m, then we have


AQ = σ1 ⃗u1 ··· σn ⃗un = U Σ,
where


U = ⃗u1 ··· ⃗un and Σ = diag(σ1 , . . . , σn ).
120 11. [DRAFT - subject to revision] Orthogonality

Next, if n > m then we have

AQ = A⃗v1 ··· A⃗vn = U Σ

where
 
σ1 0 ··· 0 0 ··· 0

0 σ2 ··· 0 0 ··· 0
U = ⃗u1 ··· ⃗um and Σ =  .
 
.. .. .. .. . . .. 
 .. . . . . . .
0 0 ··· σm 0 ··· 0

where there are an additional n − m columns of zeros at the end of the matrix Σ.

Finally, if n < m then we have

AQ = A⃗v1 ··· A⃗vn = U Σ

where
 
σ1 0 ··· 0
0 σ2 ··· 0 
 .. .. ..
 
.. 
.
 . . . 

0
Σ= 0 ··· σm 
0
 0 ··· 0 
. .. .. .. 
 .. . . . 
0 0 ··· 0

where there are an additional n − m rows of zeros at the bottom of the matrix Σ.

In all cases, we have that AQ = U Σ ⇒ A = U ΣQ⊤ , as needed. □

We define the following.

Definition 11.23. Let A be an m × n matrix and ⃗v1 , . . . , ⃗vn be an orthonormal

basis for Rn of eigenvectors for A⊤ A, as above. The singular values of A are
given by σi := ∥A⃗vi ∥.

Given our work with the singular value decomposition, we can extract geometric in-
formation by calculating the singular values of a matrix. The following Proposition
gives a more practical method to calculate these values.

Proposition 11.24. Let A be an m × n matrix and λ1 , . . . , λn be the√eigenvalues

of A⊤ A. Then, λi > 0 and the singular values of A are given by σi = λi .
Exercises 121

Proof. We have
σi2 = ∥A⃗vi ∥2
= (A⃗vi ) · (A⃗vi )
= (A⃗vi )⊤ (A⃗vi )
= ⃗vi⊤ A⊤ A⃗vi
= ⃗vi⊤ λi⃗vi
= λi⃗vi · ⃗vi
= λi ∥⃗vi ∥2
= λi ,
where the final equality follows √
because the ⃗vi form an orthonormal set. Hence,
σi2 = λi and so λi > 0 and σi = λi . □

Lecture Activity 11.10. Find the singular values of the following matri-
ces. Given your calculations, what can you say about the corresponding
transformations?
 
2 0
(1) A = 0 2
1 0
 
1 2 1
(2) B = 0 1 −1
1 1 2
 
1 1
(3) C =
1 −1

Exercises
P11.1 Prove Lemma 11.3.
P11.2 True or False: If ⃗x and ⃗y are vectors in Rn and ⃗x · ⃗y = 0 then either ⃗x = ⃗0
or ⃗y = ⃗0. If true, provide a proof. If false, provide a counterexample and
justify why this is a counterexample.
P11.3 True or False: For a vector ⃗x in Rn we have that ∥⃗x∥ = 0 if and only if ⃗x = ⃗0.
If true, provide a proof. If false, provide a counterexample and justify why
this is a counterexample.
P11.4 True or False: For any vectors ⃗x, ⃗y in Rn we have ∥⃗x + ⃗y ∥ = ∥⃗x∥ + ∥⃗y ∥. If
true, provide a proof. If false, provide a counterexample and justify why this
is a counterexample.
P11.5 For vectors ⃗x, ⃗y in Rn show that d(⃗x, ⃗y ) = d(⃗y , ⃗x).
P11.6 Show that if A and B are orthogonal matrices, then the product AB is also
orthogonal.
P11.7 Show that if Q is orthogonal, then det(Q) = ±1.
 122 11. [DRAFT - subject to revision] Orthogonality

P11.8 In this problem, we’ll show that the 2 × 2 orthogonal matrices transform R2
by either reflection or rotation.
(a) Show that for a vector ⃗v ∈ R2 , ∥⃗v ∥ = 1 if and only if ⃗v is of the form
cos θ
⃗v = , where θ is the angle ⃗v makes with the positive x-axis.
sin θ
(b) Suppose that Q is orthogonal. Use the previous part to show that
   
cos θ − sin θ cos θ sin θ
Q= or Q = .
sin θ cos θ sin θ − cos θ


(Hint: note that if Q = ⃗v w ⃗ is orthogonal, then the angle w ⃗ makes
with the positive x-axis is θ ± π/2, and then apply trig identities.)
(c) Conclude that if Q is a 2 × 2 orthogonal matrix, then Q is a rotation
matrix when det(Q) = 1 and a reflection matrix when det(Q) = −1.
P11.9 Show that any orthogonal set of nonzero vectors {⃗v1 , . . . , ⃗vm } in Rn is linearly
independent. That is, if ⃗vi · ⃗vj = 0 for all i ̸= j, then the set {⃗v1 , . . . , ⃗vm } is
linearly independent.
P11.10 Show that the rank of a matrix A is equal to the number of nonzero singular
values of A.
P11.11 Show that a square matrix A is invertible if and only if 0 is not a singular
value of A.
P11.12 Show that A and A⊤ have the same nonzero singular values.
Chapter Exercise Solutions

123