Second Year Linear Algebra Notes
Uploaded by
kibonzobrighioSecond Year Linear Algebra Notes
Uploaded by
kibonzobrighioNOTES FOR SECOND YEAR LINEAR ALGEBRA
JESSE RATZKIN
1. Introduction and Background
We begin with some motivational remarks and then outline a list (not necessarily
complete!) of things you should already know.
1.1. Motivations. In these notes we will explore the algebra and geometry of a
certain family of very nice transformations: the linear transformations. In previ-
ous classes, you’ve seen that one can add together vectors in space, and multiply a
vector by a number (i.e. scalar). This gives three-dimensional space (in fact, any
finite dimensional Euclidean space) a certain degree of algebraic structure. The
2LA module is all about the transformations of Euclidean space which preserve
this structure. Along the way we will also explore some abstract properties of lin-
ear transformations and the natural spaces they act on, which are vector spaces.
The material in this course will seem very abstract at times, but it has a wealth of
applications to mathematical modeling, dynamical systems, differential equations,
and many many other areas. For instance, it turns out that linear algebra greatly
simplifies the classification of isometries of the plane and of three-dimensional Eu-
clidean space (and of any dimensional Euclidean space). Some of you will take the
2DE module next semester, and there you will see many applications of eigenvalues
and eigenvectors (which we will learn about in this module).
1.2. Background. Here we list some topics you should already be familiar with
from MAM1000. This is by no means a complete list!
• vectors in two and three dimensions
• the dot product
• the cross product
• matrices, and operations on them (e.g. matrix addition and multiplication)
• systems of linear equations; in particular, you should know how to solve a
system of linear equations by converting it to a matrix equation and then
row-reducing the matrix.
• the complex numbers
• some elementary linear mappings of the plane (particularly rotations and
reflections)
If you don’t already know an item listed above, please review it as soon as
possible.
Date: 2013.
1
1.3. Other resources. I have more or less cribbed these notes from the book
Linear Algebra by S. Friedberg, A. Insel, and L. Spence. I have placed this book
on short loan, and you can borrow it for 3 hours at a time.
There are many other great books on linear algebra, and you can find them under
the call number 512.5 in the main library. I’d encourage you to page through several
of them until you find one you like. Here are some others I like:
• Elementary Linear Algebra by H. Anton
• Linear Algebra with Applications by O. Bretscher
• Introduction to Linear Algebra by G. Strang
1.4. Notation. For future reference, we collect here a table of some common no-
tation.
N the set of all natural numbers 1, 2, 3, . . .
Z the set of all integers
Q the set of all rational numbers
R the set of all real numbers
C the set of all complex numbers
Mm×n (R) the set of all matrices with m rows and n columns,
whose entries are real numbers
Mm×n the set of all matrices with m rows and n columns,
whose entries are real numbers
Mm×n (C) the set of all matrices with m rows and n column,
whose entries are complex numbers
Rn [x] the set of all polynomials of degree at most n
and real coefficients in the variable x
R[x] ∪∞n=1 Rn [x]
det(A) the determinant of the matix A
At the transpose of a matrix A
2. Revision: matrices and transformations of Euclidean space
We will discuss transformations T : Rn → Rm which are linear. That is, they
have the property
T (av + bu) = aT (v) + bT (u)
for all vectors v, u ∈ Rn and real numbers a, b ∈ R.
Remark 1. • Most of this section is revision of material from MAM1000,
so we will not cover it in lecture. However, it is left in the notes for your
convenience.
• Throughout the discussion below, we will always use the standard basis
{e1 , . . . , en } for Rn , where ej ∈ R is the vector with 1 in the jth component
and 0 everywhere else. Strictly speaking, we should denote this somehow
in writing down the matrix associated with a linear transformation, for in-
stance writing [T ]B instead of [T ]. However, this would introduce a great
amount of clutter into our formulas, so we suppress the basis dependence.
2
See section 4.5 below for a discussion of how changing the basis in the do-
main and/or target effects the matrix involved.
We’ll begin by considering linear transformations T : R2 → R2 , and (with a tiny
bit more generality) linear transformations T : Rn → Rm , where n, m are positive
integers.
Scaling: The simplest sort of linear transformation of the plane we can write
down is a rescaling (which is also called a dilation). If a is a positive number, we can
send (x, y) to a(x, y) = (ax, ay). Geometrically, we can imagine this transformation
as taking the unit square {0 ≤ x ≤ 1, 0 ≤ y ≤ 1} to a simliar square {0 ≤ x ≤
a, 0 ≤ y ≤ a}, which we represent in the following picture.
a
1 -
1 a
Actually, if we adopt the convention that we always start with the unit square
{0 ≤ x ≤ 1, 0 ≤ y ≤ 1}, we really only need to draw the square on the right to have
a geometric picture of or transformation. If we want to write this transformation
in terms of matrices, we can write
x a 0 x ax
7→ = .
y 0 a y ay
In the previous example, we scaled the horizontal and vertical axes by the same
factor, but there’s no reason we have to do this. More generally, we might scale the
horizontal axis by a > 0 and the vertical axis by b > 0. This time, we can write
the transformation as
x a 0 x ax
7→ = .
y 0 b y by
As before, we can represent this transformation with a picture.
b
1 -
1 a
3
Rotations and reflections: Let’s suppose we want to write down a formula for
a 30◦ counterclockwise rotation in the plane; call this rotation R30 . For instance,
we may have a collection of data points we’d like to put into a database, but the
coordinates of these datapoints are all rotated by 30◦ in the clockwise direction,
and so we want to undo this rotation, by rotating through the same angle in the
opposite direction. So let’s find out how to write down a formula for the rotation.
We start with a picture of the vectors (1, 0) and (0, 1) rotated by 30◦ .
y
A
K 6
A
A
A
A
A *
A
A $
A
30◦
A
A - x
?
We see that (1, 0) gets mapped to the point
√
cos(30◦ )
1 3/2
R30 = = ,
0 sin(30◦ ) 1/2
and that (0, 1) gets mapped to the point
− sin(30◦ )
0 −1/2
R30 = = √ .
1 cos(30◦ ) 3/2
Next observe that we can rescale the vectors (1, 0) and (0, 1), and, because
rotations don’t change lengths, the rotation will carry these scalings along:
√
x 3x/2 0 −y/2
R30 = , R30 = √ .
0 x/2 y 3y/2
Finally, we can put this all together, because
acts independently
on the vectors
1 0
(1, 0) and (0, 1). This means R30 rotatates and independently, which
0 1
we can write as
1 0 1 0
Rθ + = Rθ + Rθ .
0 1 0 1
4
(You can verify this formula geometrically, by seeing where the rotation carries the
top right corner of the unit square.) Adding these two vectors together, we have
√ √
x 3x/2√− y/2 3/2 √−1/2 x
R30 = = .
y x/2 + 3y/2 1/2 3/2 y
In this last step we used the rule for multiplying matrices we stated previously in
the notes, which starts to explain why we defined matrix multiplication the way
we did.
We can redo this whole discussion with a rotation through any angle. Let Rθ
be the rotation through angle θ in the counterclockwise direction, whose action on
the vectors (1, 0) and (0, 1) is drawn below.
y
A
K 6
A
A
A
A
A
*
A
A $
A
A θ
A - x
?
Then, just as before, we have
1 cos θ 0 − sin θ
Rθ = , Rθ = ,
0 sin θ 1 cos θ
and, by the same argument we have above,
x x cos θ − y sin θ cos θ − sin θ x
Rθ = = .
y x sin θ + y cos θ sin θ cos θ y
In this way, we can say that the rotation Rθ is given by multiplication (on the left)
by the matrix
cos θ − sin θ
[Rθ ] = .
sin θ cos θ
Exercise: Verify that
cos θ sin θ
[R−θ ] = .
− sin θ cos θ
Exercise: Verify that [Rθ ]2 = [R2θ ]. (You’ll need to remember double angle
formulas from trigonometry.)
5
Exercise: Verify that [Rθ ][Rφ ] = [Rθ+φ ]. (You’ll need to remember the angle
addition formulas from trigonometry.) Notice that rotation matrices commute!
That is, [Rθ ][Rφ ] = [Rφ ][Rθ ].
Now that we’ve figured out how to write any rotation as multiplication by a
matrix, let’s be a little ambitious and see what else we can write. The next natural
thing to consider is a reflection. The reflection through the x axis sends (x, y) to
(x, −y). We can write this as a matrix product by
x x 1 0 x
7→ = .
y −y 0 −1 y
Now that we know how to write reflection through the y axis and any rotation,
we can write down any reflection through a line that intersections the origin (0, 0).
Indeed, let l be a line passing through the origin making an angle θ with the positive
x axis, and let rl be reflection through the line l. We build the matrix for rl by
performing three transformations in succession. We first rotate our coordinates by
−θ, then reflect through the x axis, and then rotate back by the angle θ. The result
is a reflection fixing the line l, so it must be rl , and it has the matrix representation
cos θ − sin θ 1 0 cos θ sin θ
[rl ] =
sin θ cos θ 0 −1 − sin θ cos θ
cos2 θ − sin2 θ
2 cos θ sin θ
= .
2 cos θ sin θ sin2 θ − cos2 θ
cos(2θ) sin(2θ)
= .
sin(2θ) − cos(2θ)
Let’s check quickly that we have the right matrix for the reflection through the
line l. This line l is uniquely determined by the two points (0, 0) and (cos θ, sin θ),
so we only need to check that [rl ] fixes these two vectors. It is quite easy to check
that
0 cos(2θ) sin(2θ) 0 0
[rl ] = = .
0 sin(2θ) − cos(2θ) 0 0
Now we check that [rl ] fixes (cos θ, sin θ):
cos2 θ − sin2 θ
cos θ 2 cos θ sin θ cos θ
[rl ] =
sin θ 2 cos θ sin θ sin2 θ − cos2 θ sin θ
cos3 θ − sin2 θ cos θ + 2 sin2 θ cos θ
=
2 cos2 θ sin θ − cos2 θ sin θ + sin3 θ
cos θ(cos2 θ + sin2 θ)
cos θ
= = .
sin θ(cos2 θ + sin2 θ) sin θ
Sheers: The next sort of transformation we’ll talk about is a sheer, which you
can imagine as what happens to a deck of cards (as viewed from the side) when
you push the top card to the side and hold the bottom
card still. This means a
1
sheer will fix one direction, say the direction of , but it will move the other
0
6
directions. We draw a picture of what this transformation does the unit square
{0 ≤ x ≤ 1, 0 ≤ y ≤ 1} below.
(1, 1)
1 -
1 (1, 0)
We’ll call this sheer S.
We’ll construct the matrix
for this
sheer
mapping S by seeing what it does to the
1 0
two coordinate vectors and , which, in a way, is how we constructed the
0 1
1
rotation matrix. We can see from the picture that keeps the same direction,
0
so we can rescale in the horizontal direction to make
1 1
S = ,
0 0
which tells us
1 ∗
[S] = .
0 ∗
Here the ∗’s can stand for any number, because we haven’t figured out yet what
these parts of [S] are.
0
On the other hand, the vector gets tilted in the clockwise direction, and
1
it looks like it gets stretched as well. If we look a little more closely, we see
0 1
S = ,
1 1
which tells us
1 1
[S] = .
0 1
We can check this last formula by separating out the components:
x 0 x 1 1 x
S + =S = .
0 y y 0 1 y
We’ve just constructed the matrix of a particular sheer which fixes the horizontal
direction. In general, the vertical direction will go to some other direction, so that
0 a
7→ ,
1 1
7
where a 6= 0 is a number. Notice that we have the second component equal to
1, which we can arrange by rescaling if necessary. We always have the second
component nonzero, because otherwise the sheer would collaps the unit square
down to a (horizontal) line segment. Now, following the same reasoning as we did
above, we find the matrix of this sheer is
1 a
[S] = .
0 1
Exercise: Notice that a can be negative in the formula just above. What does
the paralellogram which is the image of the unit square {0 ≤ x ≤ 1, 0 ≤ y ≤ 1}
look like in this case? In particular, what can you say about the angle at the origin
(0, 0)?
Exercise: Show that the general sheer which fixes the y axis is given by a matrix
of the form
1 0
[S] = ,
a 1
where a 6= 0 is a number.
1
Exercise: Construct the general sheer which fixes the direction. Hint:
1
you might want to apply a rotation.
General matrices as mappings: We just saw how to construct the matrix
associated
to a sheer
by tracking where the sheer transformation sends the basis
1 0
vectors and . In fact, this technique is exactly how we can produce the
0 1
matrix associated to any linear transformation. Let T : R2 → R2 be any linear
transformation, which means T (v + w) = T (v) + T (w) for all vectors v, w ∈ R2
and T (av) = aT (v) for all scalars
a.
0 0
Exercise: Prove that T = for any linear mapping. Hint: sup-
0 0
0
pose otherwise; then what is T 2 ?
0
We can construct a matrix
associated to T , which we call [T ], as
follows.
The
1 0
first column of [T ] is T , and the second column of [T ] is T .
0 1
Let’s check this is actually the right matrix. Suppose we have a linear mapping
T : R2 → R2 with
1 a 0 b
T = , T = .
0 c 1 d
In this case we’d like to check that the matrix associated with T is
a b
[T ] = .
c d
8
Indeed,
x x 0
T = T +
y 0 1
1 0
= xT + yT
0 1
a b
= x +y
c d
ax + by
=
cx + dy
x a b x
[T ] =
y c d y
ax + by
= .
cx + dy
In both computations we end up with the same answer, regardless of which x and
y we choose, so this matrix must be the correct choice.
Let’s look at an example. Suppose we want to find the linear map which takes
the unit square {0 ≤ x ≤ 1, 0 ≤ y ≤ 1} to the parallelogram with the vertices
(0, 0), (2, 1), (1, 2), (3, 3).
Here’s a picture.
(1, 2)
(2, 1)
-
In fact, we have two choices for this linear mapping; we can either have
1 2 0 1
T = , T = ,
0 1 1 2
or we can have
1 1 0 2
T = , T = .
0 2 1 1
In the first case we have
2 1
[T ] = ,
1 2
and in the second case we have
1 2
[T ] = .
2 1
9
Notice that we can get from one of these matrices to the other
by swapping
the
1 0
columns, which geometrically corresponds to the swapping and . We
0 1
can write this in terms of matrix multiplication as
2 1 1 2 0 1
= .
1 2 2 1 1 0
(Youshouldcheck the matrix product.) This should not surprise you. The ma-
0 1
trix corresponds to the reflection through the line y = x, which maps
1 0
1 0
our parallelogram to itself and interchanges the vectors and . Thus
0 1
we see that we represent the composition of linear mappings as matrix
multiplication. We will return to this important
idea later on in these
notes.
1 3 1 0
Exercise: Why can’t we have T = ? Hint: what is + ?
0 3 0 1
In fact, we can reverse this process. Suppose we have a matrix, let’s say
1 −3
[T ] = ,
4 1
and we want to understand the linear transformation associated to this matrix. We
can draw the parallelogram that T sends the unit square {0 ≤ x ≤ 1, 0 ≤ y ≤ 1}
onto, which gives us all the geometric information about T . We see from the matrix
that
1 1 0 −3
T = , T = .
0 4 1 1
To draw
the parallelogram, all we need to do is draw in these two edges starting
0
at and connect them. We end up with the following picture.
0
P
PP
PP P
P
(1, 4)
(−3, 1)PPP
- PP
PP
Exercise: Can you explain why the image of a square is always a parallelogram?
(Or a line segment, which is really a degenerate parallelogram, with one pair of
opposite angles collapsed to 0 . . . )
Beyond two dimensions: So far we’ve seen how to write down the matrix of a
linear transformation taking the unit square to an arbitrary parallelogram, and how
to draw the parallelogram which is the image of the unit square under an arbitrary
10
linear mapping. However, nothing we’ve done so far is special to two dimensions,
and everything works in higher dimensions. Let’s suppose T : Rn → Rm is a linear
mapping. Also let {e1 , e2 , e3 , . . . , en } be the vectors in Rn where ei has a 1 in the
ith component and 0 elsewhere. (This is known as the standard basis of Rn .) Then
we can write down a matrix [T ], where the ith column of T is T (ei ). We have
.
...
..
[T ] = T (e1 ) T (e2 ) · · · T (en ) .
.. ..
. .
We can do a quick example, and write down the linear mapping T : R3 → R3
taking the unit cube {0 ≤ x ≤ 1, 0 ≤ y ≤ 1, 0 ≤ z ≤ 1} to the parallelpiped which
has the vertices
(0, 0, 0) (3, 1, 1) (1, 3, 1) (1, 1, 3)
.
(4, 4, 2) (4, 2, 4) (2, 4, 4) (5, 5, 5)
This time there are actually six such examples; we’ll write one of them down, and
leave the other five to you. If we want
1 3 0 1 0 1
T 0 = 1 , T 1 = 3 , T 0 = 1 ,
0 1 0 1 1 3
then we must have
3 1 1
[T ] = 1 3 1 .
1 1 3
Exercise: Write down the matrices of the other five possible linear mappings
which carry the unit cube onto this parallelpiped.
Composition of mappings and matrix multiplication: There is one very
important thing we mentioned above, which we emphasize here. Namely, the com-
position of linear transformations is given by matrix multiplication. More precisely,
if T1 : Rn → Rk and T2 : Rk → Rm are linear mappings, then the composition
T2 ◦ T1 : Rn → Rm , T2 ◦ T1 (v) = T2 (T1 (v))
is also linear, and the matrix associated to the composition is the product of the
matrices:
[T2 ◦ T1 ] = [T2 ][T1 ].
This explains why the definition of matrix multiplication is the way it is. As a
quick check, it’s good to see that the matrix product is well-defined. We have
T1 : Rn → Rk , so that [T1 ] is a k × n matrix, and (similarly) [T2 ] is a m × k
matrix. Then the product [T2 ][T1 ] is well-defined, and it is an m × n matrix. Also,
the composition T2 ◦ T1 : Rm → Rn corresponds to an m × n matrix. And so
everything fits together nicely.
11
3. Vector spaces
This section is going to seem for a while as if it has nothing to do with the
previous (revision) section, but in fact the two are very much related. We would like
to generalize much of what we wrote out for matrices with m rows and n columns
corresponding to nice transformation from Rn to Rm . In our generalization, we’d
like to replace our Euclidean spaces Rn and Rm with other objects, and it turns
out that the correct objects are vector spaces. In order to formulate the theory
correctly, we must first define important properties of vector spaces, so please be
patient while we do this.
We begin with the definition of a vector space.
3.1. Definitions and examples.
Definition 1. A vector space V over the real numbers R is a set equipped with
two operations: vector addition and scalar multiplication. Moreover, addition and
multiplication obey the following rules, where u, v, w ∈ V are vectors and a, b ∈ R
are scalars (numbers).
• av + bw is a well-defined vector in V
• v + w = w + v and (u + v) + w = u + (v + w)
• (a + b)v = av + bv and a(v + w) = av + aw
• (ab)v = a(bv)
• There is a vector 0 ∈ V , the additive identity, such that 0 + v = v for all
v ∈V.
• For any v ∈ V we have v + (−1) · v = 0, where the 0 on the right hand side
of this equation is the vector 0.
• For any v ∈ V we have 1 · v = v, where 1 ∈ R.
Remark 2. One can replace the real numbers R with the complex numbers C, and
then one gets a vector space over the complex numbers. We will see that every
vector space over C is also a vector space over R, but the reverse is not generally
true. In fact, vector spaces over C inherit additional structure.
Example: We use the rules of a vector space to show that for all v ∈ V we have
0 · v = 0, where the 0 on the left hand side of the equation is the scalar 0 and the
0 on the right hand side is the vector 0. Indeed,
0 · v = (1 + (−1)) · v = 1 · v + (−1) · v = v + (−1) · v = 0.
It isuseful to keep in mind some examples.
•the real line, with the usual addition and multiplication
•the complex numbers, with complex addition and multiplication
•The set of vectors in the plane, with usual vector addtion and scalar mul-
tiplication is a real vector space.
• The usual set of vectors in three-dimensional space, with the usual vector
addtion and scalar multiplication, is a real vector space.
• In fact, there is nothing special about two or three dimensions. The set of
vectors in any dimension, with the usual vector addition and scalar multi-
plication, is a real vector space.
12
• Let n = 0, 1, 2, 3, . . . and let Rn [x] be the set of polynomials of degree at
most n. We can write any such polynomial as
p(x) = a0 + a1 x + a2 x2 + · · · + an xn .
This is a vector space, where the vector addition is the sum of two polyno-
mials and scalar multiplication is the multiplication of a polynomial by a
number.
• Let V = {v ∈ R3 : v ⊥ (1, 1, 1)} = {v = (x, y, z) : x + y + z = 0}. This
is a vector space sitting inside R3 , which you might recognize as a plane
passing through the origin.
This last example is a particular kind of vector space.
Definition 2. Let V be a vector space. A (vector) subspace W of is a subset of V
which is itself a vector space, with vector addition and scalar multiplication in W
being the restrict of those operations in V .
Proposition 1. Let V be a vector space and let W ⊂ V be a subset. Then W is
a subspace if and only if it is closed under addition and scalar multiplication and
0 ∈ W.
Proof. First suppose that W is a subspace of V . Then by definition, 0 ∈ W and,
for any w1 , w2 ∈ W and a, b ∈ R we have aw1 + bw2 ∈ W .
Now suppose that W ⊂ V contains 0 and is closed under addition and scalar
multiplication. Then W inherits all the algebraic properties of V , such as the
associative and distributive laws. Thus it is a straigtforward exercise to check that
W satisfies all the conditions of being a vector space.
Proposition 2. Let W1 and W2 be subspaces of a vector space V . Then W1 ∩ W2
is also a subspace.
Proof. We only need to show that W1 ∩ W2 contains 0 and is closed under linear
combinations. Indeed, 0 ∈ W1 and 0 ∈ W2 , so 0 ∈ W1 ∩ W2 . Let u, v ∈ W1 ∩ W2
and let a, b ∈ R. Then au + bv ∈ W1 and au + bv ∈ W2 , so au + bv ∈ W1 ∩ W2 .
Example: It is not always true that the union of two subspaces is a subspace.
Let V = R2 , let W1 = {(x, 0) : x ∈ R}, and let W2 = {(0, y) : y ∈ R}. Then
W1 and W2 are subspaces of V , but W1 ∪ W2 is not. Indeed, (1, 0) ∈ W1 and
(0, 1) ∈ W2 , but (1, 1) = (1, 0) + (0, 1) 6∈ W1 ∪ W2 . Thus W1 ∪ W2 is not closed
under vector addition, so it cannot be a subspace.
Exercise: Prove that W1 ∪ W2 is a subspace if and only if either W1 ⊂ W2 or
W2 ⊂ W1 .
In the next chapter we will see many very important examples of subspaces in
vector spaces, but there two large families of examples you already know.
• Any line through the origin in either the plane or three-space is a vector
subspace.
• Any plane through the origin in three-space is vector subspace.
13
3.2. Linear dependence and independence. We return to vector spaces over
R.
Definition 3. Let V be a vector space over R and let v1 , v2 , . . . , vk ∈ V . We say
{v1 , . . . , vk } are linearly dependent if there is a choice of scalars a1 , a2 , . . . , ak , not
all of which are zero, such that
a1 v1 + a2 v2 + · · · + ak vk = 0.
Otherwise, we say {v1 , . . . , vk } are linearly independent.
The left hand side of this equation above,
a1 v1 + a2 v2 + · · · + ak vk ,
is called a (finite) linear combination of the vectors v1 , . . . , vk , and the scalars
a1 , . . . , ak are called the coefficients of the linear combination. Thus we can say
a set A = {v1 , . . . vk } is linearly dependent if and only if there is some linear
combination, not all of whose coefficients are zero, where the linear combination
itself is zero.
Example: We prove that {v1 , . . . , vk } are linearly independent if and only if
a1 v1 + a2 v2 + · · · + ak vk = 0
implies a1 = a2 = · · · = ak = 0. Suppose there exist coefficients a1 , a2 , . . . , ak , not
all of which are zero, such that
a1 v1 + a2 v2 + · · · + ak vk = 0.
Then by definition {v1 , v2 , . . . , vk } is linearly dependent, so it is not a linearly
independent set. Now suppose the only set of coefficients a1 , a2 , . . . , ak such that
a1 v1 + a2 v2 + · · · + ak vk = 0
is a1 = a2 = · · · = ak = 0. Then by definition {v1 , v2 , . . . , vk } cannot be linearly
dependent, so it must be linearly independent.
Example: Consider the sets A = {v1 , v2 , v3 } and B = {v1 , v2 , v3 , v4 }. We prove
that if A is linearly dependent then so is B, and that if B is linearly independent
then so is A. First suppose that A is linearly dependent. Then there must exist
coefficients a1 , a2 , a3 , not all of which are zero, so that
a1 v1 + a2 v2 + a3 v3 = 0.
Setting b1 = a1 , b2 = a2 , b3 = a3 , b4 = 0, we now have coefficients b1 , b2 , b3 , b4 , not
all of which are zero, such that
b1 v1 + b2 v2 + b3 v3 + b4 v4 = 0,
which proves that B is linearly dependent. Now suppose that B is linearly inde-
pendent, and suppose that
a1 v1 + a2 v2 + a3 v3 = 0
for some coefficients a1 , a2 , a3 . Again, choose b1 = a1 , b2 = a2 , b3 = a3 , b4 = 0, and
we have coefficients such that
0 = b1 v 1 + b2 v 2 + b3 v 3 + b4 v 4 .
14
However, B is linearly independent, so we must have b1 = b2 = b3 = b4 = 0, so in
particular we must have a1 = a2 = a3 = 0. Thus A is also linearly indenpendent.
One can use exactly the same reasoning to prove the following result.
Proposition 3. Let V be a vector space and let A ⊂ B ⊂ V be subsets. If A is
linearly dependent then so is B, and if B is linearly independent then so is A.
3.3. Span and basis.
Definition 4. If A = {v1 , v2 , . . . , vk } is a subset of a vector space V , we define the
span of A as
span(A) = {a1 v1 + a2 v2 + · · · + ak vk : a1 , a2 , . . . , ak ∈ R}.
By convention, the span of the empty set ∅ is the singleton set {0}. We also say
that the span of A is the linear combination of all vectors in A.
Observe, that, by definition, the span of any set A contains sums of only finitely
many elements of A, and not infinite sums. This is not an important distinction
for finite-dimensional vector spaces, but it is important when the vector space is
infinite-dimensional (e.g. the space of all polynomials).
We have already seen some examples. For instance,
2 1 0
R = span{e1 , e2 } = span ,
0 1
and
R2 [x] = span{1, x, x2 }.
Definition 5. Let V be a vector space. A basis for V is a set of vectors {v1 , v2 , . . . }
which is linearly independent and whose span is all of V . If V has a basis B =
{v1 , v2 , . . . , vn } with finitely many elements, then we say V is finite dimensional,
and has dimension n = #(B). Otherwise, we say V is infinite dimensional.
We will see below that, if V is finite dimensional, then the number of elements
in a basis for is it fixed, and so the dimension of V is well-defined.
Observe that the choice of basis is definitely not unique. Any vector space will
have many different bases. For instance, we can observe that
1 0 1 1
B1 = , , B2 = ,
0 1 −1 1
are both perfectly fine bases for R2 . Can you find other (distinct) bases for R2 ?
Example: We show that a set B = {v1 , v2 , . . . } is a basis for the vector space
V if and only if it satisfies the following two conditions:
• the vectors v1 , v2 , . . . in B are linearly independent
• one can write any w ∈ V as a linear combination
X
w= aj vj , where only finitely many aj are nonzero.
vj ∈B
15
If B is a basis then by definition the vectors v1 , v2 , . . . form a linearly independent
set which spans V . The fact that B spans V says exactly that, given any w ∈ V ,
there are coefficients a1 , a2 , . . . such that
X
w= aj vj .
vj ∈B
Now suppose we can write any w as a finite linearly combination of elements of B.
This means B spans V . If, in addition, B is also linearly independent, then it must
be a basis. Notice that in this example we should not take an infinite sum. A good
example to keep in mind here is that of V = R[x], the space of polynomials of and
(finite) degree, and B = {1, x, x2 , . . . }. In this case, any finite sum of elements of
B is a polynomial in R[x], but infinite sums are not.
Above we defined the dimension of a vector space as the number of elements in
a basis. To show this is a consistent definition, we need to show that any two bases
have the same number of elements, which we will prove in two steps.
Theorem 4. (The Replacement Theorem) Let V be a vector space and let B =
{v1 , . . . , vn } be a basis for V with n elements. Choose an integer m ≤ n and let
S = {w1 , . . . , wm } be a finite set of linearly independent vectors. Then there is a
subset Ŝ ⊂ B containing exactly n − m elements such that span({S ∪ Ŝ}) = V .
Remark 3. Some people like to call this theorem the ”Exchange Theorem.”
We will prove theorem by induction. As you might recall from MAM1000, the
general idea behind induction is that you first prove a base case (in this case,
m = 0). Next you prove that if the theorem is true for some integer m it is also
true for m + 1. This completes the proof in the following way. If you want to
conclude the statement of the theorem when m = 2, you only need to know it’s
true for m = 1. However, if you want to conclude the statement of the theorem
when m = 1, you only need to know it’s true when m = 0, which is the base case
we proved in the first place. The statement of the theorem is true for m = 0, which
implies it’s true for m = 1, which in turn implies it’s true for m = 2.
Proof. First consider the case of m = 0. Then S = ∅, and we choose Ŝ = B.
Now we suppose the statement of the theorem holds for some value of m < n, and
we wish to prove it for m + 1. Let S = {w1 , . . . , wm+1 } be a linearly independent
set with m + 1 elements, and let S1 = {w1 , . . . , wm }. By the induction hypothesis
(i.e. our assumption that the statement of the theorem is true for m), there is a
subset Ŝ1 = {v1 , . . . , vn−m } ⊂ B such that span({S1 ∪ Ŝ1 )} = V . In particular, we
can write
wm+1 = a1 w1 + a2 w2 + · · · + am wm + b1 v1 + b2 v2 + · · · + bn−m wn−m ,
for some coefficients a1 , . . . , am , b1 , . . . , bn−m . Observe that, because S is linearly
independent, wm+1 is not in the space of S1 = {w1 , . . . , wm }. This means at least
one of the coefficients b1 , . . . , bn−m is non-zero; without loss of generality, we take
16
that coefficient to be b1 . This means we can now rewrite the equation above as
1
v1 = − [a1 w1 + a2 w2 + · · · am wm − wm+1 + b2 v2 + b3 v3 + · · · + bn−m vn−m ] .
b1
We conclude that
v1 ∈ span{w1 , . . . , wm , wm+1 , v2 , . . . , vn−m },
and so
V = span{w1 , . . . , wm , v1 , . . . , vn−m } ⊂ span{w1 , . . . , wm+1 , v2 , . . . , vn−m }.
However, this latter space span{w1 , . . . , wm+1 , v2 , . . . , vn−m } is formed by linear
combination of vectors in V , so it must be contained in V . We conclude that
span{w1 , . . . , wm+1 , v2 , . . . , vn−m } = V,
as we claimed.
Theorem 5. Let V be a vector space and let B = {v1 , . . . , vn } be a basis for V
with n elements. If S is any linearly independent set with exactly n elements, then
S is also a basis.
Proof. Let S = {w1 , . . . , wn } be a linearly independent set with exactly n elements.
Applying the replacement theorem, we see there is a set Ŝ with n − n = 0 elements
such that span(S ∪ Ŝ) = V . However, since Ŝ has zero elements, we conclude that
span(S) = V , and so (by definiton) S is a basis.
Theorem 6. If V is a vector space with a basis B = {v1 , . . . , vn } then any set
S = {w1 , . . . , wn+1 } of n + 1 elements is linearly dependent. As a result, any
linearly independent set in V has at most n elements.
Proof. Suppose that S = {w1 , . . . , wn+1 } is linearly independent, and let S1 =
{w1 , . . . , wn }. By the previous theorem, S1 must be a basis, and so (in particular)
we can write
wn+1 = a1 w1 + · · · + an wn ,
which contradicts the assumption that S is linearly independent.
Theorem 7. If V is a vector space with a basis B = {v1 , . . . , vn } then any basis of
V will have n elements.
Proof. Let C = {w1 , · · · , wm } be another basis. Then the previous theorem implies
that both m ≤ n and n ≤ m, which is only possible if m = n.
Example: Recall that Rn [x], the set of polynomials of degree at most n, is a
vector space. We form the basis B = {1, x, x2 , . . . , xn }. First oberve that each
element of B is in Rn [x]. Next, each is a polynomial of different degree, so if
0 = a0 + a1 x + a2 x 2 + · · · an x n
for all x then we must have a0 = a1 = a2 = · · · = an = 0, so B is linearly
independent. Finally, we can write any polynomial of degree at most n as
p = a0 + a1 x + · · · + an x n
17
for some coefficients a0 , a1 , . . . , an , which means B spans Rn [x]. Therefore B is a
basis for Rn [x], and so dim(Rn [x]) = #(B) = n + 1.
Exercise: Recall that the space R2 [x] = {a0 + a1 x + a2 x2 } of quadratic poly-
nomials is a vector space. Show that
{p1 (x) = 1 − x2 , p2 (x) = 1 + x2 , p3 (x) = x + x2 }
is a basis for R2 [x]. Find the three numbers a1 , a2 , a3 such that
q(x) = x2 + 4x + 4 = a1 p1 (x) + a2 p2 (x) + a3 p3 (x).
1 0 t
Exercise: Let v1 = 0 , v2 = 1 , and v3 = t . Find necessary and
1 1 1
sufficient conditions on t so that {v1 , v2 , v3 } are linearly independent, and prove
that in this case span(v1 , v2 , v3 ) = R3 . (Hint: it might be easier to find conditions
that v1 , v2 , v3 are linearly dependent.)
Exercise: Let v1 , v2 , v3 be vectors in R2 . Is is possible that they are all linearly
independent? Find a necessary and sufficient condition that span(v1 , v2 , v3 ) = R2 .
Example: Let V = Mm×n be the space matrices with real entries with m rows
and n columns. We show that V is a vector space, and dim(V ) = mn. Indeed, we
construct a basis
ij ij 1 i = k and l = j
B = {A : 1 ≤ i ≤ m, 1 ≤ j ≤ n}, [A ]kl =
0 i 6= k or l 6= j
In other words, Aij is the matrix which has a 1 in the ith row, jth column, and
0 elsewhere. It is now a straightforward exercise (which you should do!) to verify
that B is a basis for Mm×n .
The previous exercises highlight the connection between abstract vector spaces
and matrices. Indeed, we just saw that in order to express the polynomial q(x) as
a linear combination of the three basis vectors p1 , p2 , p3 , we had to solve a system
of three linear equation in three unknowns. You probably solved that system of
equations by setting up a matrix equation, where the matrix was 3 × 3.
We will return to this point later, but here are some questions to keep in the
back of your mind.
• If you’re given a basis B = {v1 , . . . , vn } and another set S = {w1 , . . . , wm },
can you always solve the system of equations to find the coefficients bi1 , . . . , bin ,
so that
wi = bi1 v1 + bi2 v2 + · · · + bin vn ?
• If you can solve the system of equations above, is the solution unique?
• Suppose I have some set B = {v1 , . . . , vn } and another vector w. When can
I solve the system of equations to find the coefficients cj so that
w = c1 v1 + c2 v2 + · · · + cn vn ?
• In the above question, when is the solution unique?
The answer to all the questions immediately above is encoded in the following
theorem.
18
Theorem 8. Let V be a vector space and let B = {v1 , . . . , vn } be a basis for V .
Given any other vector w ∈ V , there is a unique choice of coefficients a1 , a2 , . . . , an
such that
Xn
w= ai vi = a1 v1 + a2 v2 + · · · + an vn .
i=1
Proof. The fact that B spans V implies that there is some choice of coefficients
a1 , . . . , an such that
w = a1 v1 + · · · + an vn .
It remains to show uniqueness. Suppose that there are some other coefficients
b1 , . . . , bn such that
w = b1 v1 + · · · bn vn .
Subtracting, we then have
0 = (a1 v1 + · · · + an vn ) − (b1 v1 + · · · + bn vn ) = (a1 − b1 )v1 + · · · + (an − bn )vn .
We have now produced a linear combination of v1 , . . . , vn which sums to zero.
However, B is linearly independent, so all the coefficients ai − bi = 0, for i =
1, 2, 3, . . . , n, which in turn implies ai = bi for i = 1, 2, 3, . . . , n.
If we’re given a vector space and a basis, we can now define an element in Rn
associated to any v ∈ V as follows.
Definition 6. Let V be a vector space with basis B = {v1 , . . . , vn }. Given v ∈ V
we define [v]B = (a1 , a2 , . . . , an ) ∈ Rn , where v = a1 v1 + a2 v2 + · · · an vn . We call
the coefficients a1 , a2 , . . . , an the coordinates of V with respect to the basis B, and
call [v]B the coordinate representation to v.
The previous theorem tells us this choice of coefficients is unique, so [v]B is
well-defined.
We close this section with two examples. First, we reconsider the complex num-
bers as 2 × 2 matrices. Recall that z ∈ C has the form z = x + iy, where x, y ∈ R
and i2 = −1. Also, complex multiplication is defined as
z · w = (x + iy)(u + iv) = (xu − yv) + i(yu + xv).
If we consider the complex numbers as two copies of the real numbers, we can write
(using vector notation)
x u xu − yv
z= , w= , z·w = .
y v yu + xv
Observe that, if we fixe z = x + iy, this gives us a set of two linear equation for u
and v, and we can rewrite this as
xu − yv x −y u
z·w = = · .
yu + xv y x v
19
(You might want to check the computation is correct.) This means we can identify
the complex number z = x + iy with the 2 × 2 matrix
x −y
.
y x
p
We can rewrite this matrix further if we let r = x2 + y 2 = |z|, cos θ = xr , and
sin θ = yr . Now we
x −y cos θ − sin θ
z' =r ,
y x sin θ cos θ
and we can recognize complex multiplication as nothing more than a (counterclock-
wise) rotation followed by a dilation. This is a that the complex numbers carry
some special algebraic structure.
For our second example, we discuss the Lagrange interpolation formula. You
know that two points determine a line (in the plane), and if I hand you two points
you can find the line passing through both of them. You’d probably imagine that
three points determine a parabola, and that if I hand you three points then (with
a little more work) you can find the parabola passing through all three of them.
What if I hand you 17 points and ask you to find the degree 16 polynomial passing
through them. Can you do that?
It turns out this is not too hard, if you use the following clever basis for R16 [x],
the space of degree 16 polynomials. We will outline the process for a polynomial
of some arbitrary (fixed) degree n. Start by choosing n + 1 distinct real numbers
c0 , c1 , . . . , cn ; these are the points where you will evaluate the polynomial (i.e. the
x-coordinates of the n + 1 points I hand to you). Now define the polynomials
(x − c0 ) · · · (x − ci−1 )(x − ci+1 ) · · · (x − cn ) x − cj
pi (x) = = Πj=n
j=0,j6=i .
(ci − c0 ) · · · (ci − ci−1 )(ci − ci+1 ) · · · (ci − cn ) ci − cj
(Here the Π means take a product of all those terms.) For instance,
(x − c1 ) · · · (x − cn ) (x − c0 ) · · · (x − cn−1 )
p0 (x) = , pn (x) = .
(c0 − c1 ) · · · (c0 − cn ) (cn − c0 ) · · · (cn − cn−1 )
Observe that
0 i 6= j
pi (cj ) =
1 i = j.
We will use this property to show that B = {p0 , . . . pn } is a basis for Rn [x], the
degree n polynomials in the variable x. First suppose that there are coefficients
a0 , a1 , . . . , an such that
a0 p0 (x) + a1 p1 (x) + · · · + an pn (x) = 0
for all x. Evaluate this expression at each cj , so we get
0 = a0 p0 (cj ) + · · · + an pn (cj ) = aj
for each j, which implies (by definition) that {p0 , . . . , pn } are linearly independent.
We already know that dim(Rn [x]) = n + 1, and B = {p0 , . . . , pn } contains exactly
n + 1 elements, so B must be a basis.
20
Now we return to the original problem. We have n + 1 points of the form
(c0 , y0 ), (c1 , y1 ), . . . , (cn , yn ), and we want to find the polynomial q(x) of degree n
such that
q(c0 ) = y0 , q(c1 ) = y1 , · · · , q(cn ) = yn .
This is simple now, we must have
q(x) = y0 p0 (x) + y1 p1 (x) + · · · + yn pn (x).
Exercise: Show that the graph of the polynomial q(x) given above passes
through all the points (c0 , y0 ), . . . , (cn , yn ).
Exercise: Show that the polynomial q(x) given above is the only degree n
polynomial passing through all the points (c0 , y0 ), . . . , (cn , yn ).
This is the Lagrange interpolation formula, and it is very useful for finding nice
functions passing through a given set of points.
Exercise: Show the following: if f ∈ Rn [x] is a degree n polynomial and
f (c0 ) = f (c1 ) = · · · = f (cn ) = 0 for n + 1 distinct numbers c0 , . . . , cn then f is the
zero function.
3.4. Subspaces revisited.
Proposition 9. Let V be a finite dimensional vector space and let W ⊂ V be a
subspace. Then W is also finite dimensional, and dim(W ) ≤ dim(V ). Moreover,
if dim(W ) = dim(V ) then W = V .
One can find a quick proof of this result using Theorem 6, but we offer another
proof for the readers enlightenment.
Proof. Let dim(V ) = n. If W = {0}, then by inspection W is finite-dimensional,
and dim(W ) = 0. If W 6= {0} then it contains a nonzero vector w1 , and so
{w1 } is a linearly independent set. If W = span{w1 }, then we stop, and conclude
dim(W ) = 1. Otherwise, we continue to add elements w2 , w3 , . . . , wk to our list,
until W = span{w1 , w2 , . . . , wk }, all the while maintaining that {w1 , . . . , wk } is a
linearly independent set. Moreover, by the replacement theorem, we cannot have
k ≥ n, because otherwise we’d have a linearly independent set in V with more than
n elements. We have just shown that dim(W ) = k ≤ n, and in particular that W
is finite dimensional.
Finally, if dim(W ) = n then we have a basis {w1 , . . . , wn } for W with n elements.
By the replacement theorem, this is also a basis for V , and so W = V .
Example: Let W ⊂ R5 be defined by
W = {(x1 , . . . , x5 ) : x1 + x3 + x5 = 0, x2 = x4 }.
First we show that W is a subspace. Indeed, by inspection 0 ∈ W . If x, y ∈ W
then we have
x1 + x3 + x5 = 0 = y1 + y3 + y5 , x 2 = x4 , y2 = y4 .
This implies
(x1 +y1 )+(x3 +y3 )+(x5 +y5 ) = (x1 +x3 +x5 )+(y1 +y3 +y5 ) = 0, x2 +y2 = x4 +y4 ,
21
and so x + y ∈ W . Similarly, ax + by ∈ W for any a, b ∈ R.
Next we find a basis for W . We can find 3 linearly independent vectors in W :
w1 = (0, 1, 0, 1, 0), w2 = (1, 0, 0, 0, −1), w3 = (0, 0, 1, 0, −1).
Suppose B = {w1 , w2 , w3 } were not a linearly independent set. Then we could find
three numbers a1 , a2 , a3 , not all of which are zero, such that
(0, 0, 0, 0, 0) = a1 w1 + a2 w2 + a3 w3 = (a2 , a1 , a3 , a1 , −a2 − a3 ).
However, we can read off from the first three coefficients that a1 = a2 = a3 = 0.
We conclude that B is linearly independent.
Does B = {w1 , w2 , w3 } span W ? Write some element of W as w = (a1 , a2 , a3 , a4 , a5 );
we claim that
w = a2 w1 + a1 w2 + a3 w3 = (a1 , a2 , a3 , a2 , −a1 − a3 ).
Indeed, the first three components match, so we only need to verify the fourth and
fifth components. We check that, because w ∈ W we must have a2 = a4 , and so
the fourth component matches. Similarly, we must have a5 = −a1 − a3 , and so the
fifth component matches.
In particular, we see that dim(W ) = 3.
Exercise: Is it an accident that dim(W ) = 3 = 5 − 2 and W is a subspace of
R5 determined by 2 linear equations?
Example: We already know that the set of n × n matrices is a vector space of
dimension n2 . Let V be the set of symmetric n×n matrices. That is, A = [aij ] ∈ V
if and only if aij = aji , i.e. At = A (here At is the transpose of A, the matrix you
get by swapping rows and columns). First we show V is a subspace. First of all, if
Z = [zij ] is the zero matrix, that is zij = 0 for all i, j, then we have zij = 0 = zji .
Thus the zero vector (in the vector space of n × n matrices) is also in V . Next let
A = [aij ] ∈ V and B = [bij ] ∈ V , and observe aij = aji , bij = bji . Then, for any
α, β ∈ R we have
(αA + βB)ij = αaij + βbij = αaji + βbji = (αA + βB)ji ,
and so αA + βB ∈ V . Thus V is a vector subspace of the space of n × n matrices.
Now we find a basis for V . For i ≥ j we define the n × n matrix
1 i = k, j = l
Aij = [(aij )kl ], (aij )kl = 1 i = l, j = k
0 otherwise.
0 0
If i 6= i0 or j 6= j 0 then Aij and Ai j have 1’s in different entries, and so the set
B = {Aij : 1 ≤ i ≤ n, 1 ≤ j ≤ n, i ≥ j}
is linearly independent. Now let A = [aij ] ∈ V . It is easy to check that
n X
X i
A= aij Aij ,
i=1 j=1
22
and so V = span(B). Thus B is a basis for V , and, in particular,
n(n + 1)
dim(V ) = #B = n + (n − 1) + · · · + 2 + 1 = .
2
Exercise: Repeat the exercise directly above with W , the set of skew-symmetric
matrices. That is, A = [aij ] ∈ W if and only if aij = −aji .
4. Linear Transformations
By themselves, vector spaces are boring. This subject only becomes alive when
we talk about linear transformations, which are precisely those transformations
between vector spaces that preserve the vector space structure.
4.1. Definitions and examples.
Definition 7. Let V and W be vector spaces. A transformation (i.e. mapping,
i.e. function) T : V → W is linear if for all v1 , v2 ∈ V and a1 , a2 ∈ R we have
T (a1 v1 + a2 v2 ) = a1 T (v1 ) + a2 T (v2 ).
Example: We use induction to show that if T : V → W is linear then
T (a1 v1 + a2 v2 + · · · + ak vk ) = a1 T (v1 ) + a2 T (v2 ) + · · · + ak T (vk ).
As our base case, we have
T (a1 v1 + a2 v2 ) = a1 T (v1 ) + a2 T (v2 )
by definition. Now suppose
T (a1 v1 + · · · + ak vk ) = a1 T (v1 ) + · · · + ak T (vk )
for some k ≥ 2. Then
T (a1 v1 + · · · ak vk + ak+1 vk+1 ) = T ((a1 v1 + · · · + ak vk ) + ak+1 vk+1 )
= T (a1 v1 + · · · ak vk ) + ak+1 T (vk+1 )
= a1 T (v1 ) + · · · + ak+1 T (vk+1 ).
This completes the induction step, so we’ve proved the result we wanted to prove.
Example: Let V and W be vector spaces. There are two very simple, yet
important, examples of linear transforms which we should mention to begin. First,
I : V → V, I(v) = v
is the identity transformation. This mapping always sends a vector v to itself. The
second example is
Z : V → W, Z(v) = 0,
is the zero mapping. This sends every vector v to the zero vector 0 (in W ). We
verify this quickly:
I(a1 v1 + a2 v2 ) = a1 v1 + a2 v2 = a1 I(v1 ) + a2 I(v2 )
and
Z(a1 v1 + a2 v2 ) = 0 = a1 · 0 + a2 · 0 = a1 Z(v1 ) + a2 Z(v2 ).
Lemma 10. Let T : V → W be a linear transformation. Then T (0) = 0.
23
Proof.
T (0) = T (0 + 0) = T (0) + T (0) ⇒ 0 = T (0)
Example: Let Rn [x] be the set of polynomials in the variable x of degree at
most n. The transformation
T : Rn [x] → Rn−1 [x], T (p) = p0
is linear. Indeed, for any two polynomials p and q and real numbers a and b we
have
T (ap + bq) = (ap + bq)0 = ap0 + bq 0 = aT (p) + bT (q).
Example: Let C[0, 1] be the space of continuous function on the interval [0, 1];
that is, any continuous function f (x), defined for 0 ≤ x ≤ 1, is in the space C[0, 1].
we saw in class that this is a vector space. The map
Z 1
T : C[0, 1] → R, T (f ) = f (x)dx
0
is linear. Indeed, for any two continuous functions f and g and real numbers a and
b we have
Z 1 Z 1 Z 1
T (af + bg) = (af (x) + bg(x))dx = a f (x)dx + b g(x)dx = aT (f ) + bT (g).
0 0 0
2
Example: Let C [0, 1] be the space of functions f (x) defined for 0 ≤ x ≤ 1 such
that f 00 exists and is continuous. The map
T : C 2 [0, 1] → C[0, 1], T (f ) = f 00 − 3f 0 + 2f
is a linear transformation
4.2. Kernel and range. There are two important vector subspaces associated to
any linear transformation. We define them now.
Definition 8. Let T : V → W be a linear transformation. Define the sets
ker(T ) = {v ∈ V : T (v) = 0}, R(T ) = {w ∈ W : w = T (v) for some v ∈ V }.
We call ker(T ) the ”kernel” of T and R(T ) the ”range” of T . (The range is not
to be confused with the target W , which in general is a larger vector space.)
Theorem 11. If T : V → W is linear then ker(T ) is a subspace of V and R(T ) is
a subspace of W .
Proof. First, we have T (0) = 0, which implies 0 ∈ ker(T ) and 0 ∈ R(T ). Next,
suppose v1 , v2 ∈ ker(T ). Then, for any a1 , a2 ∈ R, we have
T (a1 v1 + a2 v2 ) = a1 T (v1 ) + a2 T (v2 ) = a1 · 0 + a2 · 0 = 0,
and so a1 v1 + a2 v2 ∈ ker(T ). We conclude that ker(T ) is a subspace of V . Finally,
suppose that w1 , w2 ∈ R(T ). Then there are v1 , v2 ∈ V such that T (v1 ) = w1 and
T (v2 ) = w2 . Now, for any a1 , a2 ∈ R, we have
a1 w1 + a2 w2 = a1 T (v1 ) + a2 T (v2 ) = T (a1 v1 + a2 v2 ) ∈ R(T ),
24
because a1 v1 + a2 v2 ∈ V .
Remark 4. In general, this is the most useful tool to prove something is a vector
space.
Example: We know one can write the equation of any plane passing through
the origin in R3 as
n1 x1 + n2 x2 + n3 x3 = 0,
where n = (n1 , n2 , n3 ) is the normal vector to the plane. This formulation tells us
immediately that any plane through the origin is a subspace of R3 , because it is
the kernel of the linear transformation
T : R3 → R, T (x1 , x2 , x3 ) = n1 x1 + n2 x2 + x3 x3 .
Exercise: Mimic the example above to show that any line passing through (0, 0)
in the plane is a vector space. Also, prove that any line passing through the origin
in three-space is a vector space.
Example: Above we considered the linear transformation
Z 1
T : C[0, 1] → R, T (f ) = f (x)dx.
0
It is easy to check that R(T ) = R. Indeed, the target R is a one-dimensional vector
space, so we must either have R(T ) = R or R(T ) = {0}. Also, T (2x) = 1 6= 0,
so R(T ) 6= {0}. Thus we must have R(T ) = R. The kernel ker(T ) is the space of
functions on [0, 1] with average value 0.
Example: Recall that C 2 [0, 1], the space of functions f (x), for 0 ≤ x ≤ 1, with
continuous second derivatives, is a vector space. We define the linear transforma-
tion
T : C 2 [0, 1] → C[0, 1], T (f ) = f 00 + (1 + x2 )f = 0.
The set of functions
ker(T ) = {f ∈ C 2 [0, 1] : T (f ) = f 00 + (1 + x2 )f = 0}
is the kernel of a linear transformation, so it is a vector space.
Exercise: Use the same technique to prove that the set of solutions to any
homogeneous, second order ordinary differential equation,
K = {f ∈ C 2 [0, 1] : f 00 + p(x)f 0 + q(x)f = 0}
is a vector space. Can you generalize this result at all?
Theorem 12. Let T : V → W be linear and let B = {v1 , . . . , vn } be a basis for V .
Then
R(T ) = span{T (v1 ), T (v2 ), . . . , T (vn )}.
Proof. Each T (vi ) ∈ R(T ), and R(T ) is a subspace of W , so we must have
span{T (v1 ), . . . , T (vn )} ⊂ R(T ).
Conversely, suppose w ∈ R(T ). Then w = T (v) for some v ∈ V , but
v = a1 v1 + · · · + an vn .
25
Therefore,
w = T (a1 v1 + · · · + an vn ) = a1 T (v1 ) + · · · + an T (vn ) ∈ span{T (v1 ), . . . , T (vn )},
and so
R(T ) ⊂ span{T (v1 ), . . . , T (vn )}.
Example: Let M2×2 be the vector space of 2 × 2 matrices and let R2 [x] be the
space of quadratic polynomials. Consider
p(1) − p(2) 0
T : R2 [x] → M2×2 , T (p) = .
0 p(0)
We wish to find R(T ). Recall that B = {1, x, x2 } is a basis for R2 [x], so we can
find R(T ) by finding taking the span of the image of our basis elements under T .
Thus we have
R(T ) = span{T (1), T (x), T (x2 )}
0 0 −1 0 −3 0
= span ,
0 1 0 0 0 0
0 0 −1 0
= span , .
0 1 0 0
In fact, the computation above finds a basis of two elements for R(T ), and so
dim(R(T )) = 2.
Theorem 13. Let T : V → W be a linear transformation. Then T is one-to-one
if and only if ker(T ) = {0}.
Proof. First suppose ker(T ) = {0} and let T (v1 ) = T (v2 ). Then
0 = T (v1 ) − T (v2 ) = T (v1 − v2 ) ⇒ v1 − v2 ∈ ker(T ) = {0}.
We conclude v1 − v2 = 0, i.e. that v1 = v2 , and so T is one-to-one.
Conversely, suppose that T is one-to-one, and let v ∈ ker(T ). We already know
that T (0) = 0, and so (because T is one-to-one) we must have v = 0.
The following theorem is the most important theorem you will learn in this linear
algebra class; it is called the Rank-Nullity Theorem.
Theorem 14. (Rank-Nullity Theorem) Let T : V → W be linear and suppose V
is finite dimensional. Then
dim(ker(T )) + dim(R(T )) = dim(V ).
Remark 5. • Notice that we do not require W to be finite dimensional.
• This is called the rank-nullity theorem because one can call dim(R(T )) the
rank of T and dim(ker(T )) the nullity of T . Then the rank-nullity theorem
reads
rank(T ) + nullity(T ) = n.
• Some people like to call this result ”the dimension theorem.”
26
Proof. Let dim(V ) = n, and choose a basis {v1 , . . . , vk } for ker(T ). Notice that
ker(T ) is a subspace of V , so we necessarily have k ≤ n, and k = n if and only if
ker(T ) = V . If ker(T ) = V , we must have R(T ) = {0}, which is 0-dimensional.
Otherwise, we have k < n, and (by the replacement theorem) we can choose
n − k linearly independent vectors {vk+1 , . . . , vn } such that {v1 , . . . , vn } forms a
basis of V . Once we show that
B = {T (vk+1 ), T (vk+2 ), . . . , T (vn )}
is a basis for R(T ), we’re done, because in this case we show that
dim(ker(T )) + dim(R(T )) = k + n − k = n = dim(V ).
Let w ∈ R(T ), and write w = T (v). Then there are coefficients a1 , . . . , an such
that
v = a1 v1 + a2 v2 + · · · + an vn .
Use the fact that T (vi ) = 0 for i = 1, 2, . . . , k to see
n
! n n
X X X
w = T (v) = T ai vi = ai T (vi ) = ai T (vi ),
i=1 i=1 i=k+1
which implies (together with the previous theorem) that
R(T ) = span{T (vk+1 ), . . . , T (vn )} = span(B).
Finally, we show that B is linearly independent. Suppose there are coefficients
bk+1 , . . . , bn such that
n n
!
X X
0= bi T (vi ) = T bi vi .
i=k+1 i=k+1
Pn
This means i=k+1 bi vi ∈ ker(T ), and so we can find coefficients a1 , a2 , . . . , ak such
that
n
X k
X k
X n
X
bi vi = aj vj ⇔ 0 = − aj v j + bi vi .
i=k+1 j=1 j=1 i=k+1
However, {v1 , . . . , vk , vk+1 , . . . , vn } is a basis for V , and in particular it is a linearly
independent set, so we must have bk+1 = 0, bk+2 = 0, . . . , bn = 0. We have just
shown that B is basis for R(T ), completing the proof.
Corollary 15. Let V and W be finite dimensional vector spaces of equal dimension,
and let T : V → W be linear. Then T is one-to-one if and only if T is onto.
Compare this to the case of nonlinear functions f : R → R. It is quite easy to
find such functions that are one-to-one but not onto (such as f (x) = ex ) or onto
but not one-to-one (such as f (x) = x3 − x).
Proof. Let n = dim(V ) = dim(W ). If T is one-to-one, then dim(ker(T )) = 0, and
so by the rank-nullity theorem we have dim(R(T )) = n = dim(W ). However, the
only way R(T ) can be a subspace of W of the same dimension is if R(T ) = W ,
i.e. if T is onto. Conversely, suppose T is onto. Then dim(R(T )) = n, and so
27
by the rank-nullity theorem dim(ker(T )) = 0, which means ker(T ) = {0}. This is
equivalent to T being one-to-one.
Example: In the example above we considered
p(1) − p(2) 0
T : R2 [x] → M2×2 , T (p) = .
0 p(0)
We found that dim(R(T )) = 2, and we know that dim(R2 [x]) = 3. Thus the
rank-nullity theorem tells us dim(ker(T )) = 1.
Exercise: Find a nonzero vector in the kernel of the map T above. (Hint:
T (x2 ) = 3T (x).)
Example: Let R2 [x] be the space of quadratic polynomials and R3 [x] the space
of cubic polynomials. Define
Z x
0
T : R2 [x] → R3 [x], T (p) = 2p + 3p(t)dt.
0
We have
3
R(T ) = span{T (1), T (x), T (x2 )} = span{3x, 2 + x2 , 4x + x3 },
2
and so dim(R(T )) = 3. By the rank-nullity theorem
dim(ker(T )) + 3 = dim(R2 [x]) = 3 ⇒ dim(ker(T )) = 0,
which implies T is one-to-one. On the other hand, dim(R3 [x]) = 4 > dim(R(T )),
and so T is not onto.
The following theorem and its corollary describe how a linear transformation is
uniquely determined by its action on a basis. In practical terms, this means you
only need to compute what a linear transformation does to basis vectors; once
you’ve done that you know everything about it.
Theorem 16. Let V and W be vector spaces, and suppose V is finite dimensional
with a basis B = {v1 , v2 , . . . , vn }. Then, for any choice of vectors {w1 , w2 , . . . , wn } ⊂
W there is a unique linear transformation T : V → W such that
T (v1 ) = w1 , T (v2 ) = w2 , · · · , T (vn ) = wn .
Proof. If v ∈ V there is a unique choice of coefficients a1 , . . . , an such that v =
P n
i=1 ai vi , and then define
n
! n
X X
T (v) = T ai vi = ai wi .
i=1 i=1
It is clear that with this definition T (vi ) = wi , as required. It remains to check
that T is linear and that T is the only linear transformation such that maps vi to
wi for all i = 1, 2, . . . , n.
We first check that T is linear. Let
n
X Xn
v= ai v i , u= bi v i .
i=1 i=1
28
Then
n
! n
X X
T (αv + βu) = T (αai + βbi )vi = (αai + βbi )wi = αT (v) + βT (u).
i=1 i=1
Now suppose there is another linear transformation U : V → W such that
U (vi ) = wi for all i = 1, 2, . . . , n. Writing
n
X
v= ai vi
i=1
again, we have (because U is linear)
n
X n
X
U (v) = ai U (vi ) = ai wi = T (v),
i=1 i=1
and so T = U .
Corollary 17. Let V and W be vector spaces , and suppose V is finite dimensional
with a basis {v1 , . . . , vn }. If T, U : V → W are two linear transformations such
that T (vi ) = U (vi ) for all i = 1, 2, . . . , n then T = U .
Example: We consider two bases in R3 :
B = {e1 = (1, 0, 0), e2 = (0, 1, 0), e3 = (0, 0, 1)}
B̃ = {v1 = (1, 0, −1), v2 = (1, 0, 1), v3 = (0, 1, 0)}.
We wish to find a linear transformation such that T (e1 ) = v1 , T (e2 ) = v2 , T (e3 ) =
v3 . By the theorem above, we must have
a a1 + a2
T b = T (a1 e1 + a2 e2 + a3 e3 ) = a1 v1 + a2 v2 + a3 v3 = a3 .
c −a1 + a2
In fact, if you multiply the matrices out, you’ll find that
a1 1 1 0 a1
T 12 = 0 0 1 a2 .
a3 −1 1 0 a3
We have already seen this relationship between linear transformations and matrices
in the case of linear transformations mapping Rn to Rm . We will see in the next
section that, after choosing bases for the domain and target of a linear transforma-
tion, one obtains the same sort of matrix representation of a linear mapping.
However, before we do that, we need several more terms.
Definition 9. Let V, W be vector spaces. A linear transformation T : V → W
which is both one-to-one and onto is called a (linear) isomorphism. Two vector
spaces V, W are isomorphic if there exists a (linear) isomorphism T : V → W . We
write this condition as V ' W .
Isomorphic is a Greek word; it means ”same structure.”
29
Corollary 18. Let V, W be vector spaces and let T : V → W be linear. Then the
restriction T : V → R(T ) is an isomorphism if and only if dim(ker(T )) = 0.
This follows from the fact that T is one-to-one if and only if dim(ker(T )) = 0.
Corollary 19. Let V, W be finite dimensional vector spaces of the same dimension,
and let T : V → W be linear. Then T is an isomorphism if and only if T is one-
to-one if and only if T is onto.
Example: Let V and W be finite dimensional vector spaces, and let dim(V ) 6=
dim(W ). Then V and W cannot be isomorphic. Indeed, suppose that T : V → W
is an isomorphism. Then, because T would have to be both one-to-one and onto,
we must have
dim(V ) = dim(R(T )) + dim(ker(T )) = dim(W ) + 0,
which is impossible.
Corollary 20. Let V be a finite dimensional vector space with dim(V ) = n. Then
V is isomorphic to Rn .
Proof. Choose a basis B = {v1 , v2 , . . . , vn } for V and let {e1 , e2 , . . . , en } be the
standard basis for Rn ; that is, ei is the vector with a 1 in the ith component and
a 0 everywhere else. By Theorem 16 there is a linear map T : Rn → V with
T (ei ) = vi for i = 1, 2, . . . , n. The map T is onto because B spans V , and it is
one-to-one because B is linearly independent.
Remark 6. If all finite dimensional are the same (i.e. isomorphic) to some Eu-
clidean space, as we have just shown, then why do we study abstract vector spaces
at all? The answer has to do with the way we constructed the isomorphism in the
proof above. To prove our corollary, we had to choose a basis. Indeed, if we choose
a different basis for V then we will get a different isomorphism Rn → V . This free-
dom to choose the representation of our vector space is very powerful, and changing
the representation can turn a difficult problem into an easy one. Geometrically and
physically, you can think of the following analogy. Some problems are easier in
the usual Euclidean coordinates, and some are easier in rotated coordinates. For
instance, if you’re tracking the motion of a planet around a star, you’d certain
want to choose coordinates so that the motion of the planet lies in a coordinate
plane. This choice of a particular coordinate system is (at least locally) the same
as choosing a basis for the vector space R3 .
4.3. Matrix representations of general linear transformations. In fact, one
can represent a linear transformation between any two finite dimensional vector
space as a matrix, after one chooses bases.
Let V and W be finite dimensional vector spaces, and choose a basis B =
{v1 , v2 , . . . , vn } for V and a basis A = {w1 , w2 , . . . , wm } for W . By Theorem 16 we
can represent any linear transformation
T :V →W
30
as
m
X
T (vj ) = aij wi = a1j w1 + · · · + amj wm .
i=1
We have now represented T by the m × n matrix [T ]A B = [aij ], which has aij as the
entry in its ith row and jth column. This is a straight-forward generalization of the
previous subsection, using the fact that V ' Rn and W ' Rm . In fact, choosing
the bases {v1 , . . . , vn } and {w1 , . . . , wm } realizes these isomorphisms, which in turn
determines the matrix [T ]A B . In the next section we will consider the effect changing
basis has on [T ]A B , but first we will write out some examples. We will also say
something brief about the set of linear transformations between V and W .
Example: Above we considered
p(1) − p(2) 0
T : R2 [x] → M2×2 , T (p) = .
0 p(0)
In order to find the matrix [T ] we need to choose bases for R2 [x] and M2×2 . We
choose
B = {p0 (x) = 1, p1 (x) = x, p2 (x) = x2 }
as a basis for R2 [x] and
1 0 0 1 0 0 0 0
A = e11 = , e12 = , e21 = , e22 =
0 0 0 0 1 0 0 1
as a basis for M2×2 . Notice we have
0 0 −1 0 −3 0
T (1) = = e22 , T (x) = = −e11 , T (x) = = −3e11 ,
0 1 0 0 0 0
which implies
0 −1 −3
0 0 0
[T ]A
B = 0
.
0 0
1 0 0
Example: We also considered the linear map
Z x
0
T : R2 [x] → R3 [x], T (p) = 2p + 3p(t)dt.
0
We choose bases
B = {p0 (x) = 1, p1 (x) = x, p2 (x) = x2 }
for R2 [x] and
A = {q0 (x) = 1, q1 (x) = x, q2 (x) = x2 , q3 (x) = x3 }
for R3 [x]. We computed above that
3 3
T (1) = 3x = 3q1 , T (x) = 2 + x2 = 2q0 + q2 , T (x2 ) = 4x + x3 = 4q1 + q3 ,
2 2
31
so that
0 2 0
[T ]A 3 0 4
B = 0 3 0
.
2
0 0 1
There is a nice correspondence between the range of T and the span of the
column vectors of [T ]A
B.
Proposition 21. Let V and W be vector spaces of dimesion n and m, respectively,
and let T : V → W be linear. Choose bases B = {v1 , . . . , vn } for V and A =
{w1 , . . . , wm } for W , and let [T ]A
B be the matrix corresponding to T under these
choices of bases. Then we can identify the range of T with the span of the columns
of [T ]AB.
Proof. We know that R(T ) = span{T (v1 ), . . . , T (vn )}, and that the jth column of
[T ]A
B is T (vj ), written in terms of {w1 , . . . , wm }. The result follows.
4.4. Systems of linear equations and linear transformations. We have just
seen how one can represent a linear transformation T : V → W as an m × n
matrix, where dim(V ) = n and dim(W ) = m. Before, you also saw m × n matrices
as tools to solve m linear equations in m unknowns. In this section we describe
the connection between these two phenomena.
For the rest of the section, we take A ∈ Mm×n to be a matrix with m rows
and n columns, whose entries are real numbers. We will also regard A as a linear
transformation A : Rn → Rm . In the context of linear equations, we’re used to
solving the matrix equation Ax = b for the unknown x, given the matrix A and
the right hand side b.
It will be convenient to isolate the homogeneous case, where the right hand side
b is zero, first.
Lemma 22. Let A ∈ Mm×n . Then x solves the equations Ax = 0 if and only if
x ∈ ker(A).
Proof. By definition, ker(A) = {x ∈ Rn : Ax = 0}, so the lemma follows.
Lemma 23. Let A ∈ Mm×n with m < n. Then the set of solutions to the homoge-
neous equation, which is {x : Ax = 0} has positive dimension.
Proof. By the rank-nullity theorem,
dim(ker(T )) = n − dim(R(T )) ≥ n − m > 0.
Next we proceed to the general case, where the right hand side b of the equation
Ax = b can be any vector in Rm .
Lemma 24. Let A ∈ Mm×n . One can solve the matrix equation Ax = b for x if
and only if b ∈ R(T ).
Proof. By definition, b ∈ R(T ) if and only if there exists a vector x ∈ Rn such that
Ax = b, that is, if and only if there is a solution to the equation Ax = b.
32
Lemma 25. Let A ∈ Mm×n and let b ∈ R(T ). The solution x to the matrix
equation Ax = b is unique if and only if ker(T ) = {0}.
Proof. Suppose ker(T ) = {0}, and let x1 and x2 both solve Ax = b. Then
Ax1 = b = Ax2 ⇔ 0 = Ax1 − Ax2 = A(x1 − x2 ) ⇔ x1 − x2 = 0,
and so the solution to the equation Ax = b is unique. Conversely, suppose there
are two distinct solutions x1 6= x2 to Ax = b. Then
Ax1 = b = Ax2 ⇔ 0 = A(x1 − x2 ) ⇔ x1 − x2 ∈ ker(T ),
and so ker(T ) 6= {0}.
Theorem 26. Let A ∈ Mm×n .
(1) A : Rn → Rm is onto if and only the matrix equation Ax = b admits at
least one solution x for every choice of b on the right hand side.
(2) A : Rn → Rm is one-to-one if and only if the matrix equation Ax = b
admits at most one solution x for every choice of b on the right hand side.
Proof. The first statement follows from the first lemma above, and the second
statement follows from the second lemma above.
Corollary 27. Let A ∈ Mm×n .
(1) If m > n then there are b ∈ Rm such that one cannot find a solution x for
Ax = b.
(2) if m < n then there are b ∈ Rm such that one can find many solutions x to
the equation Ax = b.
Proof. By the rank-nullity theorem, A cannot be onto if m > n, and so the first
statement follows from the previous theorem. Similarly, A cannot be one-to-one if
m < n, and so the second statement follows.
The case of n = m bears specific mention, and we can summarize it here. Recall
(from MAM1000) that A ∈ Mn×n is invertible if there exists a matrix B = A−1
such that AB = BA = I. (See also Definition 10.)
Theorem 28. Let A ∈ Mn×n . Then the following statements are equivalent.
• A : Rn → Rn is invertible.
• A is an invertible matrix.
• One can find a unique solution x to the equation Ax = b for any b.
• One can find at least one solution x to the equation Ax = b for any b.
• One can find at most one solution x to the equation Ax = b for any b.
Proof. This theorem follows from the previous theorem and the fact that A is
invertible if and only if A is onto if and only if A is one-to-one. (This latter part is
particular to n × n matrices.)
33
4.5. Isomorphisms, invertibility, and the effect of changing basis. In this
section we relate isomorphisms and the invertibility of a matrix, and discuss how
the matrix representing a linear transformation changes if one changes the basis of
the vector space. We begin with some general properties of linear transformations
and use this to discuss inversion of matrices, leading to the effect of a change of
basis.
Theorem 29. Let V and W be vector spaces and let T : V → W be linear and
invertible. Then T −1 : W → V is also linear.
Proof. Let w1 , w2 ∈ W and let a1 , a2 ∈ R. Since T is both one-to-one and onto,
there are unique vectors v1 , v2 ∈ V such that T (v1 ) = w1 and T (v2 ) = w2 , which
implies v1 = T −1 (w1 ) and T −1 (w2 ) = v2 . Thus
T −1 (a1 w1 + a2 w2 ) = T −1 (a1 T (v1 ) + a2 T (v2 )) = T −1 (T (a1 v1 + a2 v2 ))
= a1 v1 + a2 v2 = a1 T −1 (w1 ) + a2 T −1 (w2 ).
Using our identification of a matrix as a linear transformation, we can now define
the inverse of an n × n matrix.
Definition 10. Let A ∈ Mn×n . Then A is invertible if there exists B ∈ Mn×n such
that
AB = BA = I,
where I is the n × n identity matrix (with 1’s on the leading diagonal, and 0’s in
every other entry).
Example: If
5 7 3 −7
A= ,
2 3 −2 5
it is easy to check that AB = BA = I, so B = A−1 .
Theorem 30. Let V and W be finite dimensional vector spaces, and choose bases
B = {v1 , . . . , vn } for V and A = {w1 , . . . , wn } for W . Let T : V → W be linear.
Then T is an isomorphism if and only if [T ]A B is an invertible matrix. In this case,
[T −1 ]BA = ([T ]AB ) −1
.
Proof. We already know (by the rank-nullity theorem) that T can be an isomor-
phism if and only if dim(V ) = dim(W ) = n, so [T ]A
B must be an n × n matrix.
We have also seen that we can represent the composition of linear transforma-
tions as the product of matrices. Thus, if T is an isomorphism then we have
T ◦ T −1 = IW : W → W and T −1 ◦ T = IV : V → V . Thus
I = [IV ]BB = [T −1 ◦ T ]BB = [T −1 ]BA [T ]A
B, I = [IW ]A
A = [T ◦ T
−1 A
]A = [T ]A
B [T
−1 B
]A ,
so ([T ]A
B)
−1
= [T −1 ]BA . In particular, if T is an isomorphism then [T ] must be an
invertible matrix.
Now we suppose A = [T ]A B be an invertible matrix and prove that T is an
isomorphism. There must be B ∈ Mn×n such that AB = BA = I, and write the
34
components of A as aij and the components of B as bij . There is a unique linear
transformation U : W → V such that
n
X
U (wj ) = bij vi
i=1
for each j = 1, 2, . . . , n. By construction, [U ]BA = B. Moreover,
[U T ]BB = [U ]BA [T ]A B
B = BA = I = [IV ]B , [T U ]A A B A
A = [T ]B [U ]A = AB = I = [IW ]A ,
and so U is the inverse transformation of T . In particular, T must be an isomor-
phism.
Example: Consider T : R1 [x] → R2 defined by T (a + bx) = (a, a + b). We can
check directly that T is an isomorphism, and the inverse transformation is given
by T −1 (c, d) = c + (d − c)x. Indeed,
T −1 (T (a + bx)) = T −1 (a, a + b) = a + (a + b − a)x = a + bx
and
T (T −1 (c, d)) = T (c + (d − c)x) = (c, d − c + c) = (c, d).
Now choose the bases B = {1, x} for R1 [x] and A = {e1 = (1, 0), e2 = (0, 1)} for
R2 . With respect to these bases, it is easy to check that
A 1 0 −1 B 1 0
[T ]B = , [T ]A = .
1 1 −1 1
A straightforward computation gives
1 0
[T ]A
B [T
−1 B
]A = [T −1 ]BA [T ]A
B = .
0 1
We have seen before that an n-dimensional vector space V is isomorphic to Rn ,
where the particular isomorphism depends on the choice of basis B = {v1 , . . . , vn }
for V . We have written this isomorphism as
ΦB : V → R n , v 7→ ΦB (v) = [v]B .
We can call [v]B the coordinate representation of the vector v with respect to
the basis B. However, we do need to be a bit careful, because if we change our basis
the coordinate representation will certainly change! Below we will track exactly
how [v]B changes if we change B.
Example: We define T : R3 [x] → R2 [x] by T (p)(x) = p0 (x). Now choose bases
B = {1, x, x2 , x3 } for R3 [x] and A = {1, x, x2 } for R2 [x]. With respect to these
bases, we have
0 1 0 0
[T ]A
B =
0 0 2 0 .
0 0 0 3
35
If we let p(x) = 2 + x − 3x2 + 5x3 then
2
1
−3 ,
ΦB (p) = [p]B =
5
and so
2
0 1 0 0 1
[T (p)]A = [T ]A 0 0 2 0 1 = −6 ,
B ΦB (p) = −3
0 0 0 3 15
5
which we can verify by noticing
T (p) = 1 − 6x + 15x2 .
At this point, we turn our attention to the effect of changing basis. As a way of
motivating this discussion, we begin by considering the plane curve in R2 given by
{(x, y) ∈ R2 : 2x2 − 4xy + 5y 2 = 1}. It might be difficult to recognize this plane
curve as an ellipse in the standard coordinates, but if we make the substitution
x = √2 x0 − √1 y 0
5 5
√1 x0 √2 y 0
,
y = 5
+ 5
then the equation of the curve becomes {(x0 , y 0 ) ∈ R2 : (x0 )2 + 6(y 0 )2 = 1}. This
is rather obviously an ellipse. In fact, all we are doing in changing from the (x, √ y)
0 0
coordinates to the (x , y ) coordinates is rotating by the angle θ = − arcsin(1/ 5).
It is a useful exercise to write out the change of variables matrix for the coordinate
transformation we have just done. Implicitly, we have two bases for R2 in the
computation we have just done. The first is the standard basis
B = {e1 = (1, 0), e2 = (0, 1)},
and the second is
2 1 2 1 −1 2 −1 2
A = v1 = √ , √ = √ e1 + √ e2 , v2 = √ , √ = √ e1 + √ e2 .
5 5 5 5 5 5 5 5
The matrix representing the change of basis between these two bases is the ma-
trix representing the identity linear transformation, written with respect to two
different bases. We have
B 1 2 −1
Q = [I]A = √ ,
5 1 2
and so 0
x B x 1 2 −1 x
= [v]A = [I]A [v]B = Q =√ .
y0 y 5 1 2 y
We call Q = [I]BA the change of basis matrix, because it changes the coordinates
of a vector from the coordinates from the A coordinates to the B coordinates.
There is in fact nothing particular about the change of coordinates we chose above,
36
and the entire process carries through with any change of basis. We summarize
this with the following theorem.
Theorem 31. Let B and A be two bases for a finite dimensional vector space V ,
and let Q = [IV ]BA , the matrix representing the identity map from V to itself, written
with respect to the basis A in the domain and the basis B in the target. Then
(1) Q is invertible.
(2) For any v ∈ V we have [v]B = Q[v]A .
Proof. We have seen that the matrix representing a linear transformation is invert-
ible if and only if the linear transformation is an isomorphism, and the identity
map is certainly an isomorphism. Thus the first statement holds. We verify the
second statement as follows:
[v]B = [IV (v)]B = [IV (v)]BA [v]A = Q[v]A .
Example: Take V = R2 , and choose the two bases
B = {(1, 1); (1, −1)}, A = {(2, 4), (3, 1)}.
Observe that
(2, 4) = 3(1, 1) − 1(1, −1), (3, 1) = 2(1, 1) + 1(1, −1),
so in this case the change of basis matrix is
3 2
Q= .
−1 1
If T : V → V is linear, we can write a matrix [T ]BB representing T with respect
to the basis B or a matrix [T ]A
A with respect to A. How are these two matrices
related?
Theorem 32. Let T : V → V be linear, let B and A be two bases for V , let [T ]BB
be the matrix of T with respect to B, and let [T ]A
A be the matrix of T with respect
to A. Then
[T ]A −1 B
A = Q [T ]B Q.
Proof. Let I be the identity transformation on V , so that T = I ◦ T = T ◦ I. Then
Q[T ]A B A
A = [I]A [T ]A = [IT ]A
B
= [T I]BA = [T ]BB [I]BA = [T ]B Q.
The result now follows if we multiply this equation on the left by Q−1 .
Example: Let V = R3 and define
T : R3 → R3 , T (a1 , a2 , a3 ) = (2a1 + a2 , a1 + a2 + a3 , −a2 ).
We choose B = {e1 , e2 , e3 } to be the standard basis of R3 and choose a second
basis
A = {v1 = (−1, 0, 0), v2 = (2, 1, 0), v3 = (1, 1, 1)}.
37
We have
2 1 0 −1 2 1 −1 2 −1
[T ]BB = 1 1 3 , Q = 0 1 1 , Q−1 = 0 1 −1 ,
0 −1 0 0 0 1 0 0 1
and if we multiply these matrices out we see
0 2 8
[T ]A −1 B
A = Q [T ]B Q =
−1 4 6 .
0 −1 −1
We can verify that the columns of [T ]A
A given the image of {v1 , v2 , v3 }, written as
linear combinations of themselves. For instance,
T (v2 ) = T (2, 1, 0) = (5, 3, −1) = 2v1 + 4v2 + (−1)v3 .
The coefficients 2, 4, and −1 are indeed the second column of [T ]AA.
Observe, that we now have many different ways of writing down a matrix rep-
resenting the same linear transformation, but they are all related by the change of
basis matrix. Thus it makes sense to have the following definition.
Definition 11. Let A, B ∈ Mn×n . We say that B is similar to A if there is an
invertible matrix Q ∈ Mn×n such that B = Q−1 AQ.
This definition says that two matrices are similar precisely when they represent
the same linear transformation written with respect to two different bases.
5. Determinants
Area and mappings from the plane to itself: Recall that in Section 2 we
found a linear mapping to take the unit square S = {0 ≤ x ≤ 1, 0 ≤ y ≤ 1} to any
parallelogram P with one corner at the origin. We can write the parallelogram P
as
P = {xv + yw : 0 ≤ x ≤ 1, 0 ≤ y ≤ 1},
where v and w are the two vectors which form the edges of P starting at the origin
(0, 0). Then we can write the linear transformation as
x v1 w1
T = xv + yw, [T ] = ,
y v2 w2
where v = (v1 , v2 ) and w = (w1 , w2 ) in components. Notice that the mapping T is
invertible precisely when it does not collapse S down to a line segment (or a point),
which happens precisely when the area of the parallelogram P is non-zero.
You might recall that in MAM1000 you defined an object called the determinant,
written det([T ]) = v1 w2 − w1 v2 , and were told
det([T ]) 6= 0 ⇔ T invertible ⇔ Area(P ) 6= 0.
We’ll see next that det([T ]) is the area of P , up to a sign.
38
This is easiest to see with the shear map we examined in the last set of notes.
Start with the sheer map T whose matrix representation is
1 b
[T ] = .
0 1
(In the earlier set of notes we wrote the entry in the upper right corner of [T ] as
a, but it will turn out to be convenient to call it b for our later discussion.) In this
case, T maps the unit square S = {0≤ x ≤ 1, 0≤ y≤ 1} to the parallelogram P
1 b
spanned by the two vectors v = and w = ; in other words,
0 1
1 b
T (S) = P = {xv+yw : 0 ≤ x ≤ 1, 0 ≤ y ≤ 1} = x +y : 0 ≤ x ≤ 1, 0 ≤ y ≤ 1 .
0 1
We reproduce a picture here:
Area = 1 (1, 1) Area = 1
1 -
1 (1, 0)
We already know that the unit square S has area 1, but let’s see that P also has
area 1. The area of a parallelogram is equal to its base times its height, and the
height and base of P are both 1, so the area of P is 1 · 1 = 1. On the other hand,
1 b
det([T ]) = det = 1 · 1 − 0 · b = 1 = Area(P ).
0 1
Now we can rescale the sheer T by a in the horizontal direction and by d and
vertical direction, to have something more general. This time we have
a b
[T ] = ,
0 d
and
a b
T (S) = P = {xv+yw : 0 ≤ x ≤ 1, 0 ≤ y ≤ 1} = x +y : 0 ≤ x ≤ 1, 0 ≤ y ≤ 1 ,
0 d
and the picture looks like
39
(b, d)
Area = 1
Area = ad
1 -
1 (a, 0)
(In this particular picture a = 1/2 and d = 2, but this choice of scaling factors is
not important.) This time the height of the parallelogram P is d while its base is
a, so Area(P ) = base · height = ad. Again, we have
a b
| det([T ])| = det = |a · d − b · 0| = |ad| = Area(P ).
0 d
Notice that the absolute value here is necessary, because a and d could have opposite
signs.
know | det([T ])| gives the area of the image of the unit square if
Now that we
a b
[T ] = , it’s not too hard to see this is true for any linear map. We’ll first
0 d
need a technical fact.
Example: Choose any angle θ. Then
cos θ − sin θ
det([Rθ ]) = det
sin θ cos θ
= cos2 θ − (− sin2 θ) = cos2 θ + sin2 θ = 1.
Geometrically, this computation says that a rotation leaves area unchanged.
Example: We prove det(AB) = det(A) det(B) for 2 × 2 matrices A and B. We
have
a b e f ae + bg af + bh
det(AB) = det = det
c d g h ce + dg cf + gh
= (ae + bg)(cf + dh) − (ce + dg)(af + bh) = adeh + bcf g − bceh − adf g
and
a b e f
det(A) det(B) = det det = (ad − bc)(eh − f g)
c d g h
= adeh − bceh − adf g + bcf g.
Notice that this means det(AB) = det(A) det(B) = det(B) det(A) = det(BA) for
any pair of 2 × 2 matrices. In fact, this is true for A, B ∈ Mn×n , though the proof
is a little bit messier.
Now let T : R2 → R2 be a linear mapping of the plane to itself, and suppose
a b
[T ] = .
c d
40
a b 1 0
This means T (e1 ) = and T (e2 ) = , where e1 = and e2 =
c d 0 1
a
as before. Now, the vector T (e1 ) = makes some angle θ with the positive x
c
axis, so we apply the rotation R−θ to T to get a new mapping
cos θ sin θ a b ã b̃
T̃ = R−θ ◦ T, [T̃ ] = [R−θ ][T ] = = ,
− sin θ cos θ c d 0 d˜
and
det([T̃ ]) = det([R−θ ][T ]) = det([R−θ ]) det([T ]) = det([T ]).
By the computation we did above, Area(P̃ ) = | det([T̃ ])|. We also have that T
sends the unit square S to a parallelogram P , and T̃ sends S to a parallelogram
P̃ . These two parallelograms P and P̃ differ by a rotation, so they have the same
area. Thus we see
Area(P ) = Area(P̃ ) = | det([T̃ ])| = | det([T ])|.
In particular, we have just proven that det([T ]) 6= 0 precisely when T is invertible,
because this is precisely when the image parallelogram P has nonzero area.
Orientation and the sign of the determinant: As we saw in the previous
notes, there are actually two linear transformations which map the unit square S
onto this parallelogram P , we can also have
1 b 0 a b a
T = , T = , [T ] = .
0 d 1 0 d 0
In this case we see that
det([T ]) = −ad = − Area(P ).
Why do we have the minus sign? To understand what’s going on, it will help to
label the corners of the unit square S and the parallelogram P as in the picture
below.
ii’ iii’
iv iii
-
i ii i’ iv’
What does this labeling mean? The mapping T sends the vector e1 , which goes
b
from i to ii in the square on the left to the vector , which also goes from i’ to
d
ii’ in the parallelogram on the right. Similarly, the mapping T sends
the vector e2 ,
a
which goes from i to iv in the square on the left to the vector , which also goes
0
41
from i’ to iv’ in the parallelogram on the right. Now, if we follow the labeling of
the corners of the square in order, as in i to ii to iii to iv, then we traverse along the
boundary of the square counter-clockwise. However, if we follow the labeling of the
corners of the parallelogram in order, as in i’ to ii’ to iii’ to iv’, we traverse along
the boundary of the parallelogram clockwise. This means the mapping T reversed
the direction we traversed along the boundary of the shape. In other words, T
reversed the orientation. We have discovered the following general principle:
det([T ]) < 0 ⇔ T reverses orientation.
This principle is exactly why we wrote | det([T ])| = Area(P ) before. In general,
if T : R2 → R2 preserves orientation then det([T ]) = Area(P ), but if T reverses
orientation then det([T ]) = − Area(P ).
Higher dimensions: So far we’ve seen that the determinant of a 2 × 2 matrix
is the area (up to a sign) of the parallelogram which is the image of the unit square.
In fact, a similar thing is true in higher dimensions. Let [T ] be an n × n matrix,
which we’ve seen corresponds to a linear map T : Rn → Rn . Then T sends the unit
cube S = {0 ≤ xi ≤ 1 : i = 1, 2, . . . , n} to a parallelepiped P , which is spanned by
the columns of [T ]. Then | det([T ])| = Vol(P ), where Vol gives the n-dimensional
volume.
We begin with a quick illustrative example. Consider
a b 0
[T ] = c d 0 , e > 0.
0 0 e
Then the image of the unit cube S under T is
P = {(x, y, z) : (x, y) ∈ P̄ , 0 ≤ z ≤ e},
where
a b
[T̄ ] = , S̄ = {0 ≤ x ≤ 1, 0 ≤ y ≤ 1}, P̄ = T (S̄).
c d
By slicing P with horizontal slices, we see
Vol(P ) = e Area(P̄ ) = e| det([T̄ ])|.
So, by any reasonable definition of the determinant for 3 × 3 matrices which fits
with our definition for 2 × 2 matrices, we must have
det([T ]) = e det([T̄ ]) = e(ad − bc).
Exercise: Let [T ] be a 3 × 3 matrix. Show that you can always perform a
rotation to make the last row of [T ] into 0 0 e . (Hint: geometrically, you
want to rotate the parallelepiped so that one of its faces lies in a coordinate plane.
What are the columns of [T ]?)
At this point, we can write down a reasonable formula for the determinant of a
3 × 3 matrix. Let
a b c
[T ] = d e f ,
g h i
42
then
b c a c a b
det[T ] = g det − h det + i det .
e f d f d e
Here we’ve singled out the last row, but we can do the same thing by picking out
any row or column. To do this properly, we need some notation. Let [T ] = [Aij ],
so that the entry of [T ] in the ith row, jth column is Aij . Also, let [T̄ij ] be the
2 × 2 matrix you get from [T ] by crossing out the ith row and jth column. Then
for any choice of j = 1, 2, 3 we can write
det([T ]) = (−1)1+j A1j det([T̄1j ]]) + (−1)2+j A2j det([T̄2j ]) + (−1)3+j A3j det([T̄3j ]),
which computes det([T ]) by expanding along the jth column. Alternatively, for
any choice of i = 1, 2, 3 we can write
det([T ]) = (−1)i+1 Ai1 det([T̄i1 ]) + (−1)i+2 Ai2 det([T̄i2 ]) + (−1)i+3 Ai3 det([T̄i3 ]),
which computes det([T ]) by expanding along the ith row.
The same idea will compute the determinant of any square matrix inductively.
That is, you write the determinant of an n × n matrix as a sum of determinants
of (n − 1) × (n − 1) matrices. We write the general formula as follows. Again,
we let Aij be the entry of [T ] in the ith row, jth column, and we let [T̄ij ] be the
(n − 1) × (n − 1) matrix you get from [T ] by crossing out the ith row and the jth
column. The for any choice of j = 1, 2, . . . , n we compute det([T ]) by expanding
along the jth column using the formula
det([T ]) = (−1)1+j A1j det([T̄1j ])+(−1)2+j A2j det([T̄2j ])+· · ·+(−1)n+j Anj det([T̄nj ]).
Alternatively, for any choice of i = 1, 2, . . . , n we compute det([T ]) by expanding
along the ith row using the formula
det([T ]) = (−1)i+1 Ai1 det([T̄i1 ])+(−1)i+2 Ai2 det([T̄i2 ])+· · ·+(−1)i+n Ain det([T̄in ]).
We summarize some important properties of the determinant here.
(1) The determinant is linear in each row and column. That is, if A is an n × n
matrix and à is the same as A except that you multiply the ith row by c,
then det(Ã) = c det(A). Also, A1 and A2 are the same except at the ith
row and A is what you get by adding together the ith row of A1 and A2
then det(A) = det(A1 ) + det(A2 ). The same goes for columns.
(2) Consequently, if A is an n × n matrix and c is a number then det(cA) =
cn det(A).
(3) An n × n matrix A is invertible if and only if det(A) 6= 0.
(4) In fact, | det(A)| is the n-dimensional volume of the parallelpiped P which
is the image of the unit cube S = {0 ≤ x1 ≤ 1, . . . , 0 ≤ xn ≤ 1} under the
linear transformation associated to A. (You can prove this by induction, in
a very similar way we got the geometric interpretation for three dimensions
from the two-dimensional version.)
(5) Let A and B be n × n matrices, then det(AB) = det(A) det(B).
(6) Let A be an n × n matrix and let à be the matrix you get by swapping two
rows of A (or by swapping two columns). Then det(Ã) = − det(A)
43
6. Eigenvalues and eigenvectors
In this section we discuss eigenvalues and eigenvectors of a linear transformation.
The bulk of this section is concerned with linear transformations T : Rn → Rn ,
and so we can work entirely in terms of n × n matrices. However, the situation is
really no more complicated for a general linear transformation T : V → V , where
V is an arbitrary finite-dimensional vector space. So we will close with some more
general examples.
6.1. Eigenvalues of linear transformations from Rn to itself.
6.1.1. Some motivation. We saw in the last section that the determinant of a 2 × 2
matrix tells us the effect the associated linear map has on area. In other words,
if det([T ]) = 2 then T : R2 → R2 will scale the areas of squares by a factor of 2.
It’s not to hard to show that T scales the areas of all shapes by the same factor.
(Hint: cut whatever shape you’re interested in into a bunch of little tiny squares.
You won’t be able to do this exactly, but what you have left over has a negligible
area.) However, it’s easy to find a linear map which preserves area but distorts
lengths by a lot. For instance, consider the linear
1
2 2 0
T :R →R , [T ] = 2 .
0 2
We draw a picture of what T does to the unit square below.
2
1 -
1
1 2
This map preserves area, but it changes lengths by a lot. It shrinks length in some
directions by a factor of 1/2 and it stretches lengths in other directions by a factor
of 2. We can make this picture much worse by choosing , for instance, a horizontal
scale factor of 1/100 and a vertical scale factor of 100. This example tells us we
need at least two numbers to keep track of how a linear map T : R2 → R2 deforms
lengths. We’ll see in a bit that, at least in some special cases, we only need two
numbers, and that these numbers are (essentially) the eigenvalues.
6.1.2. Definitions. If you know a little about the German language, you might be
able to guess what an eigenvector is. The German word eigen means own, and an
44
eigenvector of a linear transformation keeps its own direction. It can get rescaled,
but the direction remains the same.
Definition 12. Let T : Rn → Rn be a linear transformation. Then a nonzero
vector v ∈ Rn is an eigenvector with eigenvalue λ if T (v) = λv. Notice that, even
though v is not allowed to be zero, it’s possible that λ = 0.
Exercise: Why is it necessary to have v 6= 0 in the definition of an eigenvector
v?
This definition is a little awkward for doing computations, so the first thing we’ll
do is reformulate it a little. Let v be an eigenvector of T with eigenvalue λ. Then
[T ][v] = λ[v] = λ[I][v] ⇔ ([T ] − λ[I])[v] = 0.
Now, v 6= 0, so the linear transformation T − λI sends a nonzero vector to 0, which
means it can’t be one-to-one. This means T − λI isn’t invertible, and so
det([T ] − λ[I]) = 0.
This last equation is an n-th degree polynomial equation for the unknown λ. We
know that any n-th degree polynomial has exactly n roots in the complex numbers
C (so long as we remember to count repeated roots), which means we’ve just proved
the following
Theorem 33. Let T : Rn → Rn be linear. Then a complex number λ ∈ C is an
eigenvalue of T if and only if
det([T ] − λ[I]) = 0.
Moreover, every n × n matrix has precisely n complex numbers λ1 , . . . , λn (counted
with multiplicity) which are eigenvalues.
The polynomial det([T ] − λ[I]) is called the characteristic polynomial of T ;
it is a polynomial of degree n if T ∈ Mn×n , and carries much important informa-
tion about T . The Cayley-Hamilton theorem states that T is a root of its own
characteristic polynomial.
This theorem tells us how to compute eigenvalues of a square matrix: we write
down the polynomial det([T ] − λ[I]) and find its roots. In practice this can be
a little sticky, for instance, if we want to find the eigenvalues of a 5 × 5 matrix.
However, for the case of 2 × 2 matrices, which is most of what we’ll discuss in this
class, the eigenvalues are the roots of a second order polynomial, which we can
always find using the quadratic formula. So, for the time being at least, let’s say
we can find eigenvalues and continue, to see how to find the eigenvectors.
Let [T ] be an n × n matrix, and let λ be an eigenvalue of [T ]. We want to find
the associated eigenvector(s), that is the nonzero vectors v such that T (v) = λv.
We write this equation as a matrix equation
[T ][v] = λ[v]
and try to solve it using our favorite method (like row reduction).
45
Exercise: Show that if v is an eigenvector of the matrix A with eigenvalue λ,
then 2v is also an eigenvector of A, with the same eigenvalue λ. Is there anything
special about the scale factor of 2?
Exercise: Show that the linear system [T ][v] = λ[v] for finding an eigenvector
will always have many many solutions. Usually, this system will have one free
variable, so it might be convenient to set one of the components of v to 1. However,
it is possible that this linear system has more than one free variables.
6.1.3. Some properties of eigenvalues and eigenvectors. Here we list some proper-
ties of the eigenvalues and eigenvectors.
Recall that v is an eigenvector of A with eigenvalue λ if Av = λv. If λ is a
real number as well, this means A(v) is colinear with v, i.e. either A(v) points in
the same direction or the opposite direction as v. In other words, if λ is a real
eigenvalue of A then, considered as a linear map, A preserves the direction of the
associated eigenvector v.
Exercise: Recall that we constructed the 2 × 2 rotation matrices
cos θ − sin θ
[Rθ ] = .
sin θ cos θ
Show that [Rθ ] has a real eigenvalue if and only if the angle θ is an integer multiple
of π (when measured in radians).
Exercise: We also constructed reflection matrices. Show that 1 is an eigenvalue
of any reflection matrix.
Exercise: Let A be the 3 × 3 matrix associated to a rotation of 3-dimensional
space. Show that 1 is an eigenvalue of A, and describe the relation between this
associated eigenvector and the rotation.
Exercise: Show that 0 is an eigenvalue of an n × n matrix A if and only if A is
not invertible. (This is completely general.)
Now we consider an n × n matrix A with real entries Aij in the ith row, jth
column. We have that λ is an eigenvalue of A precisely when
det(A − λI) = 0.
This is an nth degree polynomial, and the coefficients of this polynomial are sums
of products of the entries of A. This means λ is a root of a polynomial with real
coefficients. Now, it can happen that λ is not a real number, but it is a complex
number, but these complex roots occur in conjugate pairs. We have the following
Proposition 34. Let A be an n × n matrix with real entries. Then a non-real
complex number λ = a+ib is an eigenvalue of A if and only if its complex conjugate
λ̄ = a − ib is also an eigenvalue. In fact, in this case the eigenvectors are also
complex conjugates. That is, if v is an eigenvector associated to the eigenvalue λ
then v̄ is an eigenvector associated to the eigenvalue λ̄.
The last sentence of the proposition follows immediately from taking the complex
conjugate of the equation Av = λv to get Av̄ = λ̄v̄.
46
Exercise: Let A be an n × n matrix with real entries, and let λ = a + ib be a
non-real eigenvalue. Show that the components of the associated eigenvector v are
also non-real.
Some times we can find n independent eigenvectors v1 , . . . , vn for an n×n matrix
A. This means we can find n linearly independent vectors v1 , . . . , vn such that
A(vj ) = λj vj , and that we can’t write vj as the weighted sum of the other vi ’s. In
this case, we say that A is diagonalizable, for the following reason. We can write
any vector w as a sum w = c1 v1 + c2 v2 + · · · cn vn , and then
(1) A(w) = A(c1 v1 + · · · cn vn ) = c1 A(v1 ) + · · · cn A(vn ) = c1 λ1 v1 + · · · cn λn vn .
In other words, if we let B = {v1 , . . . , vn } be a basis of Rn consisting of eigenvectors
of A then we have
λ1 0 · · · 0
0 λ2 · · · 0
[A]BB = ... .. ;
.
0 · · · 0 λn
in other words, [A] is a diagonal matrix in the right coordinates. We see immedi-
ately from equation (1) that, at least if A is diagonalizable, that the eigenvalues
λ1 , . . . , λn encode the stretch factors we were looking for at the beginning of this
section.
We need to know the facts that the determinant and the trace of a matrix do
not depend on the basis; that is, if you change coordinates as we just did the
determinant and the trace remain the same.
Exercise: Show that, for a diagonalizable, n × n matrix, the determinant is the
product of the eigenvalues and the trace is the sum of the eigenvalues.
1 1
Exercise: Not all matrices are diagonalizable. In fact, show that is
0 1
not diagonalizable.
We saw above that if A is diagonalizable then det(A) is the product of all the
eigenvalues and tr(A) is their sum. In fact, this is true for any n × n matrix,
as you’ll see in a second year linear algebra course when you discuss the Jordan
cannonical form of a matrix.
Proposition 35. For any n × n matrix A, it holds that det(A) is the product of
the eigenvalues of A, and tr(A) is their sum.
Exercise: Let A be a 2 × 2 matrix with complex eigenvalues λ± = a ± ib. Show
that tr(A) = 2a and det(A) = a2 + b2 . In particular, det(A) ≥ 0.
Exercise: Let A be a 2 × 2 matrix with real eigenvalues λ1 and λ2 . Show that
det(A) > 0 if and only if λ1 and λ2 have the same sign. Then show that λ1 and λ2
are both positive if and only if both det(A) > 0 and tr(A) > 0.
Finally, we mention symmetric matrices, that is matrices such that Aij = Aji
where Aij is the entry of A in the ith row, jth column. These are particularly nice,
as we see from the following theorem (which we will not prove here).
Theorem 36. A symmetric n × n matrix is diagonalizable and has n real eigen-
values λ1 ≤ λ2 ≤ · · · ≤ λn ∈ R.
47
6.1.4. Examples. We’ll compute the eigenvalues and eigenvectors of some 2 × 2
matrices here, just so we have some examples written down.
First let
4 −2
A= .
3 −3
We want to find the eigenvalues of A, so we set
4−λ −2
0 = det(A − λI) = det
3 −3 − λ
= λ2 − λ − 6 = (λ − 3)(λ + 2),
and we see that the eigenvalues of A are λ1 = −2 and λ2 = 3.
Now we find the eigenvector associated to the eigenvalue λ1 = −2. We want to
solve the linear equation
4 −2 v1 −2v1
Av = −2v ⇔ = .
3 −3 v2 −2v2
Of course, you can solve this using row reduction, but I find that for a small system
like this, it’s easier to just write out the equations. We have
4v1 − 2v2 = −2v1 , 3v1 − 3v2 = −2v2 ,
and both these equations reduce to v2 = 3v1 . (You might want to think about why
you’ll always reduce from two equations to one when you’re finding the eigenvectors
of a 2 × 2 matrix.) So, up to a scale factor, the eigenvector of A associated to
λ1 = −2 is
1
v= .
3
Finally we find the eigenvector associated to λ2 = 3. This time the linear equa-
tion is
4 −2 w1 3w1
Aw = 3w ⇔ = ,
3 −3 w2 3w2
which we rewrite as
4w1 − 2w2 = 3w1 , 3w1 − 3w2 = 3w2 .
This reduces to w1 = 2w2 , and so the eigenvector is (again, up to scale)
2
w= .
1
For our next example, we take the matrix
1 −1
A= .
1 1
Again, we find eigenvalues of A by setting
1 − λ −1
0 = det(A − λI) = det
1 1−λ
= λ2 − 2λ + 2.
48
Using the quadratic formula we see that the eigenvalues are λ+ = 1 + i and λ− =
1 − i. Notice that, just as we said earlier, the eigenvalues occur in conjugate pairs.
We set up the equation for the eigenvector associated to λ+ = 1 + i as before,
and get
1 −1 v1 (1 + i)v1
Av = (1 + i)v ⇔ = ,
1 1 v2 (1 + i)v2
which reduces to
v1 = iv2 ⇔ −v2 = iv1 .
1
(You might want to recall here that i
= −i.) So we see that the eigenvector
associated to λ+ = 1 + i is
i
v= .
1
There’s a short cut to finding the other eignevector w: since
Aw = λ− w = λ̄+ w
and Ā = A we must have
−i
w = v̄ = .
1
We can also do this computation directly:
1 −1 w1 (1 − i)w1
= ⇔ w2 = iw1 ⇔ w1 = −iw2
1 1 w2 (1 − i)w2
and we recover
−i
w= .
1
6.2. Eigenvalues of linear transforms from V to itself. In fact, there is abso-
lutely nothing special about the case V = Rn in everything we have done regarding
eigenvalues and eigenvectors.
Definition 13. Let T : V → V be a linear transformation. A nonzero vector v ∈ V
is an eigenvector of T , with eigenvalue λ, if T (v) = λv.
As before, T (v) = λv if and only if v ∈ ker(T − λI), which in particular implies
T −λI is not invertible. If V is finite dimensional, we can choose a basis {v1 , . . . , vn }
for it and construct the associated matrix [T ], and then compute the eigenvalues
by setting det([T ] − λ[I]) = 0 as before. Below we carry this exercise out for two
examples involving R2 [x], the space of quadratic polynomials.
Example: Let T : R2 [x] → R2 [x] be given by T (p)(x) = p(x)−2xp0 (x). Observe
that
T (1) = 1, T (x) = −x, T (x2 ) = −3x2 ,
so our three eigenvectors are p0 = 1 with eigenvalue λ0 = 1, p1 = x with eigenvalue
λ1 = −1, and p2 = x2 with eigenvalue λ2 = −3. We can verify all this by choosing
49
the usual basis B = {1, x, x2 }; with respect to this basis, we have
1 0 0
[T ] = 0 −1
0 .
0 0 3
Example: This time we take T : R2 [x] → R2 [x] given by T (p)(x) = 2p(x) +
3p0 (x) − 2x2 p00 (x). We can find one eigenvalue-eigenvector pair immediately by
observing T (1) = 2; so p0 = 1 is an eigenvector with eigenvalue λ0 = 2. To find
the others, we choose the usual basis B = {1, x, x2 } for R2 [x]; with respect to this
basis, the matrix of T is
2 5 0
[T ] = 0 0 6 ,
0 0 −2
so eigenvalues are roots of the characteristic polynomial
2−λ 5 0
0 = det 0 −λ 6 = −λ(λ − 2)(λ + 2).
0 0 −2 − λ
We can now read off that the three eigenvalues are λ0 = 2 (which we already knew),
λ1 = −2, and λ2 = 0. Finally, we find the eigenvectors. To find the eigenvector p1
associated to λ1 = −2, we solve the system of equations
2 5 0 a 2a + 5b a
0 0 6 b = 6c = −2 b .
0 0 −2 c −2c c
The general solution is a = − 45 b, c = − 13 b, with b being a free variable. We can set
b = 1, to get the eigenvector p1 = − 54 + x − 31 x2 . Similarly, we find the eigenvector
p2 associated to λ2 = 0 by solving the system of equations
2 5 0 a 2a + 5b 0
0 0 6 b = 6c = 0 .
0 0 −2 c −2c 0
This time the general solution is c = 0, a = − 25 b. We can take b = 1 to get the
eigenvector p2 = − 52 + x.
7. Spaces of linear transformations
7.1. Generalities. We have seen now that we can associate a matrix to any linear
transformation. We also learned (last year) that one can perform some operations
on matrices, particularly addition, multiplication by scalars, and matrix multiplica-
tion. We’ve already seen that matrix multiplication corresponds to the composition
of linear transformation, but what does the linear combination of matrices corre-
spond to?
50
Definition 14. Let V, W be vector spaces, and let T, U : V → W both be linear
transformations. Then, for any a, b ∈ R, we can define the linear transformation
(aT + bU ) : V → W, (aT + bU )(v) = aT (v) + bU (v).
The following proposition is easy to prove, so we will sketch part of the proof
and leave the rest to the reader.
Proposition 37. Let V, W be vector spaces, and let T, U : V → W be linear
transformations. Then, for any a, b ∈ R the map aT + bU defined above is linear.
In fact, the set L(V, W ) of linear transformations from V to W is a vector space,
with this notion of addition and scalar multiplication.
Remark 7. Be careful that you do not confuse L(V, W ) with L(W, V ). They are
the same space if and only if V = W .
Proof. Let v1 , v2 ∈ V and α1 , α2 ∈ R. Then
(aT +bU )(α1 v1 +α2 v2 ) = aT (α1 v1 +α2 v2 )+bU (α1 v1 +α2 v2 ) = α1 (aT +bU )(v1 )+α2 (aT +bU )(v2 ),
and so aT + bU is indeed a linear transformation.
The zero transformation Z : V → W which sends everything to zero, plays the
role of the zero vector. It is now easy to check all the vector space axioms. For
instance, for any T : V → W and v ∈ V we have
(T + Z)(v) = T (v) + Z(v) = T (v) = Z(v) + T (v) = (Z + T )(v).
We have now shown the following theorem.
Theorem 38. Let V, W be finite dimension vector spaces, with dim(V ) = n,
dim(W ) = m. Choosing bases {v1 , . . . , vn } for V and {w1 , . . . , wm } for W iden-
tifies L(V, W ) with Mm×n , the set of matrices with m rows and n columns. This
identification is a linear isomorphism.
Remark 8. • In fact, in your next algebra course, you will learn that this
identification is an isomorphism of rings precisely when m = n and one
uses the same basis for both the domain and the target.
• The particular isomorphism L(V, W ) ' Mm×n depends very much on our
choice of the bases {v1 , . . . , vn } for V and {w1 , . . . , wm } for W .
We check one thing quickly. Let T, U : V → W be linear, choose bases B =
{v1 , . . . , vn } and A = {w1 , . . . , wm } for V and W respectively, and let α, β ∈ R.
Then we claim
[αT + βU ]A A A
B = α[T ]B + β[U ]B .
Indeed, we only need to check this formula on the basis vectors v1 , . . . , vn in B. We
must have numbers aij , bij ∈ R such that
m
X m
X
T (vj ) = aij wi , U (vj ) = bij wi .
i=1 i=1
51
Now,
m
X
(αT + βU )(vj ) = (αaij + βbij )wi ,
i=1
which shows
[αT + βU ]A A A
B = α[aij ] + β[bij ] = α[T ]B + β[U ]B .
7.2. Dual spaces. Given two vector spaces V and W , we have just seen the vector
space L(V, W ), the vector space of linear transformations from V to W . In the
special case that the target W = R, we obtain something called the dual space to
V.
Definition 15. Let V be a vector space. The dual space V ∗ to V is the vector
space V ∗ = L(V, R).
An element φ ∈ V ∗ is a linear function φ : V → R; such a linear map is often
called a linear functional. In the special case that B = {v1 , . . . , vn } is a basis for
V , we have a particular set of n linear functionals B ∗ = {φ1 , . . . , φn }, which are
defined by the relation
1 i=j
φi (vj ) =
0 i 6= j.
The main content of the proof of the theorem below is to show that B ∗ is a basis
of V ∗ ; it is called the dual basis to B.
Theorem 39. Let V be a finite dimensional vector space. Then V ∗ is isomorphic
to V .
Proof. We pick a basis B = {v1 , . . . , vn } and prove the theorem. In fact, we al-
ready know that V is isomorphic to Rn , so we only need to prove that V ∗ is also
isomorphic to Rn as well. To show this, we only need to show that V ∗ is an n-
dimensional vector space, i.e. that V ∗ has a basis with n elements. We already
have an excellent candiate for this basis, namely the dual basis B ∗ = {φ1 , . . . , φn }.
Let φ ∈ V ∗ . We show that there is a unique choice of coefficients a1 , . . . , an such
that
φ = a1 φ1 + a2 φ2 + · · · + an φn ;
as we have seen before, this shows both that B ∗ spans V ∗ (by the existence of a
solution) and that it is linearly independent (by the uniqueness of the solution).
Given our choice of φ ∈ V ∗ , we can pick
a1 = φ(v1 ), a2 = φ(v2 ), ..., an = φ(vn ).
Now we compare φ to the map
φ̃ = a1 φ1 + a2 φ2 + · · · + an φn .
We have, by definition, φ(vj ) = aj = φ̃(vj ), which implies φ = φ̃. Thus we
have represented our arbitrary φ ∈ V ∗ as a linear combination of elements of B ∗ .
Furthermore, if there is some other choice of coefficients b1 , . . . , bn such that
φ = b1 φ1 + · · · bn φn ,
52
then for any j = 1, . . . , n we have
bj = (b1 φ1 + · · · + bn φn )(vj ) = φ(vj ) = (a1 φ1 + · · · + an φn )(vj ) = aj .
Thus the choice of coeffients is unique, completing the proof.
Remark 9. • Notice that isomorphism V → V ∗ depends quite heavily on the
choice of basis B (or, equivalently, on the choice of dual basis B ∗ ). If we
change basis in V , we will obtain a very different isomorphism V → V ∗ .
• Also notice that in order to construct the dual basis B ∗ , we need to first
pick the basis B. We cannot pick them simultaneously, say choosing the
first two elements of B, then the elements of B ∗ , then the rest of B. This
is because in order to describe even the first linear functional φ1 ∈ B ∗ , we
need to know what it does to each and every basis vector in B.
Example: As our first example, we take V = Rn with the standard basis
B = {e1 , . . . , en }, and we denote the elements of the dual basis by {e∗1 , . . . , e∗n }. By
definition we must have
e∗i (x1 , x2 , . . . , xn ) = xi ,
and we can write the matrix of e∗i (with respect to the standard basis) as the row
with n element, which has a 1 in the ith column and 0’s everywhere else.
Example: Let V = R3 and choose the basis B = {e1 − e2 , e1 + e2 , e3 }. Then
the dual basis is
∗ 1 ∗ ∗ 1 ∗ ∗ ∗
B = (e − e2 ), (e1 + e2 ), e3 .
2 1 2
3
Exercise: Let V = R , and choose the basis
B = {e1 − e2 , e1 + e2 , e1 + e2 + e3 }.
Find the dual basis B ∗ .
We have seen that the isomorphism V → V ∗ depends very much on our choice of
basis. Thus it is remarkable that the isomorphism V → (V ∗ )∗ = V ∗∗ is canonical;
that is, this isomorphism doesn’t depend on anything at all.
Theorem 40. Let V be a finite dimensional vector space. Then V is canonically
isomorphic to its double-dual V ∗∗ . In other words, the isomorphism V → V ∗∗ does
not depend on anything at all.
Proof. Given a vector v ∈ V , we define v̂ ∈ V ∗∗ by v̂(φ) = φ(v) for all φ ∈ V ∗ .
This now defines a mapping
Ψ : V → V ∗∗ , Ψ(v) = v̂,
which, it turns out, will be our isomorphism. Observe that we have now defined v̂
and Ψ without choosing anything at all, and so Ψ is canonically defined.
We first check that Ψ is linear. Let v1 , v2 ∈ V and choose two real numbers
a1 , a2 ∈ R. Then, for any φ ∈ V ∗ we have
Ψ(a1 v1 + a2 v2 )(φ) = φ(a1 v1 + a2 v2 ) = a1 φ(v1 ) + a2 φ(v2 ) = a1 Ψ(v1 )(φ) + a2 Ψ(v2 )(φ).
Since this formula holds for all φ ∈ V ∗ , we conclude that
Ψ(a1 v1 + a2 v2 ) = a1 Ψ(v1 ) + a2 Ψ(v2 ).
53
Next we check that ker(Ψ) = {0}. Suppose that Ψ(v) = 0 ∈ V ∗∗ . This means
that for all φ ∈ V ∗ we must have
0 = Ψ(v)(φ) = φ(v).
If v 6= 0 then we could choose an ordered basis {v1 = v, v2 , . . . , vn }, and choosing
φ = φ1 to be the first element of the dual basis would force φ(v) = 1 6= 0. Clearly
this is impossible in light of φ(v) = 0 for all φ ∈ V ∗ .
In fact, we’re done with the proof now. We know that dim(V ) = dim(V ∗ ) =
dim(V ∗∗ ), and we’ve just shown that Ψ : V → V ∗∗ is a one-to-one linear trans-
formation. By our previous theorems we know this is only possible if Ψ is an
isomorphism.
Remark 10. Some people call the isomorphism Ψ the tautological isomorphism
between V and V ∗∗ .
Remark 11. We have done everything here for finite dimensional vector spaces.
Some of these ideas extend to infinite dimensions (e.g. the idea of constructing a
dual vector space), but many of the proofs don’t carry through in higher dimensions.
In particular, the dual space to an infinite dimensional vector space is bigger than
the original.
8. Inner products and other quadratic forms
In this section we discuss inner products, which generalize the usual dot product
in Euclidean space.
8.1. Definitions, examples, and basic properties. We begin with some defi-
nitions, examples, and basic properties.
Definition 16. Let V be a vector space over R. An inner product is a function
h·, ·i : V × V → R.
which satisfies the following rules for any choice u, v, w ∈ V and a, b ∈ R.
(1) hau + bv, wi = ahu, wi + bhv, wi
(2) hv, wi = hw, vi
(3) hv, vi ≥ 0, with equality if and only if v = 0.
As stated, this definition applies only to vector spaces over the real numbers.
There is a similar notion for an inner product on a vector space over the complex
numbers C. For the sake of completeness, we mention this definition now, even
though we will mostly only work with vector spaces over R and real-valued inner
products.
Definition 17. Let V be a vector space over the complex numbers C. A hermitian
inner product is a function
h·, ·i : V × V → C
which satisfies the following rules for any choice of u, v, w ∈ V and a, b ∈ C.
(1) hau + bv, wi = ahu, wi + bhv, wi
54
(2) hv, wi = hw, vi, where the over-bar denotes the complex conjugate
(3) hv, vi ≥ 0, with equality if and only if v = 0
Notice that, in particular, hv, vi is a non-negative real number for any v ∈ V .
At this point, we describe some examples.
Example: We take V = Rn and h·, ·i to be the usual dot product. In the usual
coordinates, we have
h(x1 , x2 , . . . , xn ), (y1 , y2 , . . . , yn )i = x1 y1 + x2 y2 + · · · + xn yn = Σnj=1 xj yj .
With a little more generality, we can take V = Cn and define the standard hermit-
ian inner product on Cn by
h(z1 , z2 , . . . , zn ), (w1 , w2 , . . . , wn )i = z1 w̄1 + z2 w̄2 + · · · + zn w̄n = Σnj=1 zj w̄j ,
where z = (z1 , . . . , zn ), w = (w1 , . . . , wn ) ∈ Cn . For instance, if we take z =
(1 + i, 4) ∈ C2 and w = (2 − 3i, 4 + 5i) ∈ C2 we have
hz, wi = (1 + i)(2 + 3i) + (4)(4 − 5i) = 15 − 15i.
Example: If A ∈ Mn×n we have already seen that we can define the transpose
of A as At , the matrix we obtain by swapping the rows and the columns. In
components, if aij is the entry in the ith row, jth column of A, then At has aij in
the ith column, jth row. Now we can define an inner product
h·, ·i : Mn×n × Mn×n → R, hA, Bi = tr(B t A).
We check this is actually an inner product; we need to recall that tr(c1 T1 + c2 T2 ) =
c1 tr(T1 ) + c2 tr(T2 ), that tr(T t ) = tr(T ) and the formula for transposes and matrix
products. If A1 , A2 ∈ Mn×n and c1 , c2 ∈ R then
hc1 A1 +c2 A2 , Bi = tr(B t (c1 A1 +c2 A2 )) = c1 tr(B t A1 )+c2 tr(B t A2 ) = c1 hA1 , Bi+c2 hA2 , Bi.
Also,
hB, Ai = tr(At B) = tr((B t A)t ) = tr(B t A) = hA, Bi.
Finally, if A = [aij ] then
hA, Ai = Σni=1 (At A)ii = Σni=1 Σnj=1 aji aji .
This is a sum of non-negative numbers, so it must be non-negative. Moreover, it
is only zero if all the entries of A are zero, namely only if A is the zero matrix.
Example: Let V = C[0, 2π], the space of continuous, real-valued functions on
[0, 2π]. We can define the inner product
Z 2π
1
h·, ·i : C[0, 2π] × C[0, 2π] → R, hf, gi = f (x)g(x)dx.
2π 0
1
This is an important inner product for defining Fourier series, and the factor of 2π
in front of the integral makes many of the formulas come out nicely.
It will be useful to have two more notions for the rest of this chapter: the notion
of a length (or a norm), and the notion of an orthogonal set.
p product h·, ·i. Then
Definition 18. Let V be a vector space over R with an inner
we can define the length of any vector v ∈ V to be kvk = hv, vi
55
It is immediate from the definitions that kvk ≥ 0 for any vector v ∈ V , with
equality if and only if v = 0. By convention, we say that v ∈ V is a unit vector
if kvk = 1.
Definition 19. Let V be a vector space over R with an inner product h·, ·i. A set
S = {v1 , v2 , . . . , vk } is orthogonal if hvi , vj i = 0 whenever i 6= j. If in addition
kvi k = 1 for each i = 1, 2, . . . , k then we say S is an orthonormal set.
We will revisit orthonormal sets in the next subsection.
We close this section by listing some basic properties of inner products.
Theorem 41. Let V be a vector space over R with an inner product h·, ·i. Then
for any u, v, w ∈ V and a, b ∈ R we have
(1) hu, av + bwi = ahu, vi + bhu, wi
(2) If hu, vi = hu, wi for all u ∈ V then v = w.
Proof. The first statement follows from the properties of the inner product and
the fact that hu, vi = hv, ui. Suppose that hu, vi = hu, wi for all u ∈ V . We can
rearrange this equation to read
0 = hu, vi − hu, wi = hu, v − wi
for all u. Now substitute u = v − w into this equation to get hv − w, v − wi = 0,
which implies v − w = 0, i.e. v = w.
Theorem 42. Let V be a vector space over R with an inner product h·, ·i. Then
for any u, v ∈ V and c ∈ R we have
(1) kcvk = |c|kvk
(2) |hu, vi| ≤ kukkvk
(3) ku + vk ≤ kuk + kvk
The second statement is called the Cauchy-Schwarz inequality, and the third
statement is the familiar triangle inequality.
Proof. The first equation follows from the fact that hcv, cvi = c2 hv, vi.
Next we prove the Cauchy Schwarz inequality. If v = 0 then both sides of the
equation are zero, so the inequality holds. If v 6= 0 then we have, for any c,
0 ≤ ku − cvk2 = hu − cv, u − cvi = kuk2 + c2 kvk2 − 2chu, vi
Now choose
hu, vi
c=
kvk2
and plug this into the inequality we have just derived to get
|hu, vi|2
0 ≤ kuk2 − ,
kvk2
which we can rearrange to give the Cauchy-Schwarz inequality.
56
Finally we use Cauchy-Schwarz to prove the triangle inequality.
ku + vk2 = hu + v, u + vi = kuk2 + 2hu, vi + kvk2
≤ kuk2 + 2|hu, vi| + kvk2 ≤ kuk2 + 2kukkvk + kvk2
≤ (kuk + kvk)2
Taking square roots of both sides of this inequality gives the triangle inequality.
8.2. Gram-Schmidt orthogonalization. For many applications it is convenient
to have an orthonormal basis for a vector space with an inner product. However,
when one originally picks a basis for a vector space it is usually not orthogonal, so
it is useful to have a process to turn an arbitrary basis into an orthonormal basis.
This subsection will outline an algorithm for doing so, and present some examples.
Recall that an orthogonal set S = {v1 , . . . , vk } ⊂ V is a set such that hvi , vj i = 0
if i 6= j. We say that S is orthonormal if we also have kvi k2 = hvi , vi i = 1 for
i = 1, 2, . . . , k. Thus an orthonormal basis for V is a basis {v1 , v2 , . . . , vn } such
that
1 i=j
hvi , vj i =
0 i 6= j.
Example: We list some orthonormal bases for R2 equipped with the usual dot
product. The first such basis is the familiar standard basis
{e1 = (1, 0), e2 = (0, 1)}.
We can rotate this basis through an angle π/4 to get
1 1
{v1 = √ (1, 1), v2 = √ (1, −1)},
2 2
or through an angle π/6 to get
1 √ 1 √
{v1 = ( 3, 1), v2 = (−1, 3),
2 2
or (for a general angle θ)
{v1 = (cos θ, sin θ), v2 = (− sin θ, cos θ)}.
Before outlining the Gram-Schmidt process we should see why an orthonormal
basis is useful.
Theorem 43. Let V be a vector space over R with an inner product h·, ·i, and let
S = {v1 , . . . , vk } be an orthogonal set of nonzero vectors. If w = Σkj=1 aj vj then
hw,v i
aj = kvj kj2 for all j = 1, 2, . . . , k.
Proof. We take some inner products. For i = 1, . . . , k we have
hw, vi i = Σkj=1 aj vj , vi = Σkj=1 aj hvj , vi i = ai kvi k2 .
The theorem follows.
Corollary 44. Under the hypotheses of the last theorem, if S is also orthonormal
then
w = Σkj=1 hw, vj ivj .
57
Corollary 45. Let V be a vector space over R with an inner product h·, ·i, and
let S = {v1 , v2 , . . . , vk } be an orthogonal set of nonzero vectors. Then S is also
linearly independent.
Proof. Suppose there exist coefficients a1 , . . . , ak such that
a1 v1 + a2 v2 + · · · + ak vk = 0.
h0,vi i
Then, by the theorem above, for each i = 1, 2, . . . , k we have ai = kvi k2
= 0. We
conclude that S must be linearly independent.
The following theorem is the main tool we will use to construct an orthonormal
basis from an arbitrary basis.
Theorem 46. Let V be a vector space over R with an inner product h·, ·i and let
S = {w1 , w2 , . . . , wn } ⊂ V be a linearly independent subset. If we define
k−1 hwk , vj i
v1 = w1 , vk = wk − Σj=1 vj for k = 2, 3, . . . , n
kvj k2
then S 0 = {v1 , v2 . . . , vn } is an orthogonal set with span(S 0 ) = span(S).
If we want to complete the process of finding an orthonormal basis, we apply the
above theorem to a basis to get an orthogonal basis {v1 , . . . , vn }, and then replace
vj with kv1j k vj . Thus the main difficulty lies in achieving hvi , vj i = 0 for i 6= j.
Proof. We prove this by induction on n. If n = 1 then there is nothing to check,
and so the theorem holds. Assume now that the statement of the theorem holds
for Sn = {w1 , . . . , wn }, namely that we can construct Sn0 = {v1 , . . . vn } using the
formulas above to find an orthogonal set such that span(Sn ) = span(Sn0 ). Now
suppose we have Sn+1 = {w1 , . . . , wn , wn+1 } which is linearly independent; we wish
0
to construct Sn+1 = {v1 , . . . vn , vn+1 } according to our formula, and see that we get
0
an orthogonal set with span(Sn+1 ) = span(Sn+1 ).
By the induction hypothesis, we already have {v1 , . . . , vn } which are orthogonal
(namely, hvi , vj i = 0 for i 6= j so long as 1 ≤ i ≤ n and 1 ≤ j ≤ n), so we only
need to check that
hwn+1 , vj i
vn+1 = wn+1 − Σnj=1 vj
kvj k2
is nonzero and orthogonal to v1 , v2 , . . . , vn . If vn+1 = 0 then
hwn+1 , vj i
wn+1 = Σnj=1 vj ∈ span{v1 , . . . , vn } = span{w1 , . . . , wn }.
kvj k2
However, this contradicts the fact that Sn+1 is linearly independent, so it is im-
possible that vn+1 = 0. Next we check the inner products. Using the fact that
{v1 , . . . , vn } are already orthogonal, for 1 ≤ k ≤ n we have
hwn+1 , vj i hwn+1 , vk i
hvn+1 , vk i = hwn+1 , vk i−Σnj=1 2
hvj , vk i = hwn+1 , vk i− hvk , vk i = 0
kvj k kvk k2
58
0
We conclude that Sn+1 is indeed orthogonal. By our formula for {v1 , v2 , . . . , vn+1 }
0 0
we have span(Sn+1 ) ⊂ span(Sn+1 ). However, we also know that Sn+1 is linearly
independent, so
0
dim(span(Sn+1 )) = n + 1 = dim(span(Sn+1 )),
0
which implies span(Sn+1 ) = span(Sn+1 ).
We can combine the previous theorems to see the following.
Theorem 47. Let V be a finite dimensional vector space over R with an inner
product. Then V has an orthonormal basis B = {v1 , . . . , vn }. Moreover, if v ∈ V
then we can represent
Xn
v= ai vi , ai = hv, vi i.
i=1
Proof. Let A1 = {w1 , . . . , wn } be any basis for V and apply Gram-Schmidt to A1
to obtain A2 = {u1 , . . . , un }. This is now an orthogonal basis, so we let
ui
vi = , B = {v1 , . . . , vn }.
kui k
This completes the proof.
Corollary 48. Let V be an n-dimensional vector product space over R with an
inner product, and let B = {v1 , . . . , vn } be an orthonormal basis for V . Also, let
T : V → V be a linear transformation. Then
[T ]BB = [aij ], aij = hT (vi ), vj i.
9. New vector spaces from old
In this section we describe some ways to create new vector spaces from old ones,
namely the direct sum construction and the quotient construction. The key tool
in each construction is a general notion of a projection.
Definition 20. Let V be a vector space. A linear map P : V → V is a projection
if P 2 = P .
It is worthwhile to check that the usual coordinate projections
P1 : R 2 → R 2 , P1 (x1 , x2 ) = (x1 , 0)
and
P2 : R 2 → R 2 , P2 (x1 , x2 ) = (0, x2 )
satisfy P12 = P1 and P22 = P2 .
59
9.1. Direct sums. We begin with some definitions and basic properties.
Definition 21. Let V be a vector space, and let W1 , W2 ⊂ V be subspace. Then
W1 + W2 = {w1 + w2 : w1 ∈ W1 , w2 ∈ W2 }.
Proposition 49. The sum W1 + W2 is a subspace of V . In fact, it is the smallest
subspace containing both W1 and W2 .
Proof. We need first to verify that if w, w̃ ∈ W1 + W2 and a, ã ∈ R then aw + ãw̃ ∈
W1 + W2 . We have w = w1 + w2 , where w1 ∈ W1 and w2 ∈ W2 . Similarly,
w̃ = w̃1 + w̃2 , where w̃1 ∈ W1 and w̃2 ∈ W2 . Then
aw + ãw̃ = a(w1 + w2 ) + ã(w̃1 + w̃2 ) = (aw1 + ãw̃1 ) + (aw2 + ãw̃2 ),
and we have now written aw + ãw̃ as the sum of a vector in W1 and a vector in
W2 . Thus W1 + W2 is closed under linear combinations, so it must be a subspace.
Now suppose U is another subspace of V containing both W1 and W2 , and choose
w = w1 +w2 ∈ W1 +W2 . However, w1 and w2 must both be elements of U , and U is
closed under addition, so w1 + w2 ∈ U . We have just shown that W1 + W2 ⊂ U .
Definition 22. A vector space V is said to be the direct sum of the subspaces W1
and W2 if W1 ∩ W2 = {0} and V = W1 + W2 . In this case we write V = W1 ⊕ W2 .
Example: We can write Rn = W1 ⊕ W2 where W1 = {(x1 , x2 , . . . , xn ) : xn = 0}
and W2 = {(x1 , x2 , . . . , xn ) : x1 = x2 = · · · = xn−1 = 0}. We can write any vector
in Rn as
(x1 , . . . , xn ) = (x1 , . . . , xn−1 , 0) + (0, . . . , 0, xn ),
and so Rn = W1 + W2 . Moreover, the only vector in common with W1 and W2
must have all its components equal to zero, so W1 ∩ W2 = {0}.
Example: Let V = Mn×n , let W1 = {A ∈ Mn×n : At = A} be the set of
symmetric matrices, and let W2 = {A ∈ Mn×n : At = −A} be the set of skew-
symmetric matrices. Then V = W1 ⊕ W2 . Indeed, for any matrix A ∈ Mn×n we
have
1 1 1 1
(A + At ) ∈ W1 , (A − At ) ∈ W2 , A = (A + At ) + (A − At ),
2 2 2 2
so V = W1 + W2 . Now suppose A ∈ W1 ∩ W2 . Then
A ∈ W1 ⇒ A = A t , A ∈ W2 ⇒ A = −At .
Putting these last two equations together we get A = −A, which is only possible
if A = 0.
Exercise: Let V = Rn [x], the space of polynomials of degree at most n. Define
W1 = {p = a0 + a1 x + · · · + an xn : ak = 0 if k is even},
and
W2 = {p = a0 + a1 x + · · · + an xn : ak = 0 if k is odd}.
Prove that V = W1 ⊕ W2 .
60
Theorem 50. Let W1 and W2 be finite-dimensional subspaces of the vector space
V . Then W1 + W2 is also finite dimensional, and
dim(W1 + W2 ) = dim(W1 ) + dim(W2 ) − dim(W1 ∩ W2 ).
In particular, V = W1 ⊕ W2 if and only if
dim(V ) = dim(W1 ) + dim(W2 ).
Proof. Let B1 = {v1 , . . . vk } be a basis for W1 and let B2 = {w1 , . . . wm } be a basis
for W2 . Then
W1 + W2 ⊂ span(B1 ∪ B2 ) = span{v1 , . . . , vk , w1 , . . . , wm },
so in particular
dim(W1 + W2 ) ≤ k + m = dim(W1 ) + dim(W2 ),
which implies W1 + W2 is finite dimensional.
If W1 ∩ W2 = {0} then span(B1 ) and span(B2 ) cannot contain any vectors in
common, and so B1 ∪ B2 must be linearly independent. In this case, we have shown
dim(W1 +W2 ) = dim(W1 )+dim(W2 )−dim{0} = dim(W1 )+dim(W2 )−dim(W1 ∩W2 )
as desired.
Otherwise, we still have that W1 ∩ W2 is a subspace of W2 . (It is also a subspace
of W1 and of V , but for the purposes of the proof we will work with W1 ∩ W2 as
a subspace of W2 .) By the replacement theorem, we can re-order {w1 , . . . , wm } so
that {w1 , w2 , . . . , wm0 } span W1 ∩ W2 , for some m0 ≤ m. As each of w1 , w2 , . . . , wm0
must also be in W1 = span(B1 ), each must be a linear combination of v1 , v2 , . . . , vk .
Removing these vectors w1 , . . . , wm0 from B2 we still have a set
B 0 = {v1 , . . . , vk , wm0 +1 , . . . , wm }
such that W1 + W2 = span(B 0 ). If we show B 0 is linearly independent then we’re
done, because in this case
dim(W1 +W2 ) = k +(m−m0 ) = k +m−m0 = dim(W1 )+dim(W2 )−dim(W1 ∩W2 ).
So, suppose there is some choice of coefficients a1 , . . . , ak , bm0 +1 , . . . , bm ∈ R, not
all of which are zero, such that
0 = a1 v1 + a2 v2 + · · · + ak vk + bm0 +1 wm0 +1 + bm0 +2 wm0 +2 + · · · + bm wm .
If one of the aj ’s is non-zero, we can re-order the vectors v1 , . . . , vk so that a1 6= 0.
Then we rearrange our equation to read
1
v1 = − (a2 v2 + · · · + ak vk + bm0 +1 wm0 +1 + · · · + bm wm ).
a1
However, we know that {v1 , . . . , vk } are linearly independent, and wm0 +1 , . . . , wm
are not in W1 at all, so this is impossible. Similarly, assuming that one of the bj ’s
is nonzero will also give a contradiction. We have just proven that B 0 is linearly
independent, completing the proof of our theorem.
61
If we have V = W1 ⊕ W2 then we can examine two natural projection operators:
Π1 : V → W1 , Π2 : V → W2 .
To understand these operators, we need some preliminaries. First observe that we
can write any v ∈ V as v = w̃1 + w̃2 , where w̃1 ∈ W1 and w̃2 ∈ W2 . In fact, this
choice of w̃1 and w̃2 is unique. To see this, choose bases B1 = {v1 , . . . , vk } for W1
and B2 = {w1 , . . . , wm } for W2 . By the proof of the theorem immediately above,
we know that B1 ∪ B2 is a basis for V = W1 ⊕ W2 , which means that for any v ∈ V
there is a unique choice of coefficients a1 , . . . , ak , b1 , . . . , bm such that
v = a1 v1 + · · · ak vk + b1 w1 + · · · bm wm ,
and so
w̃1 = a1 v1 + · · · + ak vk , w̃2 = b1 w1 + · · · + bm wm .
Because B1 = {v1 , . . . , vk } is a basis for W1 and B2 = {w1 , . . . , wm } is a basis
for W2 , these representations of w̃1 and w̃2 uniquely determine them. Then our
projection formulas read
Π1 (v) = Π1 (w̃1 + w̃2 ) = w̃1 , Π2 (v) = Π2 (w̃1 + w̃2 ) = w̃2 .
Remark 12. It is a straight-forward exercise to extend everything in this section
to finite sums (or finite direct sums) of subspaces W1 , W2 , . . . , Wk ⊂ V using in-
duction.
9.2. Quotients. To define quotients we will need to introduce equivalence rela-
tions.
Definition 23. If X is any set, a relation R on X is a subset R ⊂ X × X. If
x1 , x2 ∈ X and (x1 , x2 ) ∈ R we write x ∼ y. An equivalence relation is a relation
such that
(1) For all x ∈ X we have x ∼ x (reflexivity).
(2) If x ∼ y then y ∼ x (symmetry).
(3) If x ∼ y and y ∼ z then x ∼ z (transitivity).
Also, if X is a set with an equivalence relation R then the equivalence class of
an element x ∈ X, written [x], is the set of everything equivalent to x. That is,
[x] = {x̃ ∈ X : x̃ ∼ x}.
The first example of an equivalence relation you should think of is the following.
Let X = Z, the set of integers, and fix a positive integer n. We say x ∼ y if x − y
is an integer multiple of n. For instance, if n = 2, then x ∼ y if x − y is an even
integer, and x 6∼ y if x − y is odd.
We’ll verify transitivity here, the other two properties are easier to check. If
x ∼ y and y ∼ z then there are integers a and b such that
x − y = an, y − z = bn,
and so
x − z = (an + y) − (−bn + y) = (a + b)n
is indeed a multiple of n.
62
We write
nZ = 0, ±n, ±2n, ±3n, . . .
for the set of all integer multiples of n, and we see that we can identify the set of
equivalence classes
Zn = Z/ ∼= Z/nZ = {0, 1, 2, . . . , n − 1}.
This means that for any integer x we can find another integer y ∈ {0, 1, 2, . . . , n−1}
such that x ∼ y, and that this choice of y is unique. Indeed, we can write any integer
x as x = an + y, where y is the remainder of x divided by n. By definition, we have
x ∼ y, and that y ∈ {0, 1, 2, . . . , n − 1}. Also, if y ∼ z and y, z ∈ {0, 1, 2, . . . , n − 1}
then y − z = an for some integer a. However, this is only possible if a = 0, which
implies y = z.
Now we are ready to define the quotient of a vector space V by a subspace W .
Definition 24. Let V be a vector space and let W ⊂ V be a subspace. For any
v ∈ V we define the coset v + W = {v + w : w ∈ W }, and define an equivalence
relation on the set of cosets by saying
v1 + W ∼ v2 + W ⇔ v1 − v2 ∈ W.
Then the quotient space V /W is the vector space formed by the set of equivalence
classes.
In order for this to be a sensible definition, we must check some things.
Theorem 51. The equivalence relation
v1 + W ∼ v2 + W ⇔ v1 − v2 ∈ W
is indeed and equivalence relation. Moreover, the set of equivalence relations V /W
inherits a vector space structure from V .
Proof. We first check that ∼ is an equivalence relation. First of all, v + W ∼ v + W
because v − v = 0 ∈ W , as W is a subspace. Second, if v1 + W ∼ v2 + W then
v1 − v2 ∈ W , which implies v2 − v1 = −(v1 − v2 ) ∈ W . Third, if v1 + W ∼ v2 + W
and v2 + W ∼ v3 + W , then v1 − v2 = w1 ∈ W and v2 − v3 = w2 ∈ W . Thus
v1 − v3 = (v1 − v2 ) − (v2 − v3 ) = w1 − w2 ∈ W,
and so v1 + W ∼ v3 + W .
At this point, it will be convenient to notice that v + W = 0 + W = W (with
equality as equivalence classes) if and only if v ∈ W . To see this, observe that
v + W = 0 + W = W ⇔ v = v − 0 ∈ W.
Next we define the vector addition and scalar multiplication on the cosets. Let
v1 + W, v2 + W ∈ V /W and let a1 , a2 ∈ R. Then we define
a1 (v1 + W ) + a2 (v2 + W2 ) = (a1 v1 + a2 v2 ) + W.
63
We need to check that this definition of vector addition and scalar multiplication
does not depend on the choice we have made, namely, the representatives v1 and
v2 we chose for the cosets. Let
v1 + W ∼ v10 + W ⇔ v1 − v10 = w1 ∈ W, v2 + W = v20 + W ⇔ v2 − v20 = w2 ∈ W
Then
(a1 v1 + a2 v2 ) − (a1 v10 + a2 v20 ) = a1 (v1 − v10 ) + a2 (v2 − v20 ) = a1 w1 + a2 w2 ∈ W,
so the coset we get by choosing a representative to do the vector addition and
scalar multiplication does not in fact depend on our choice of representative.
It is now quite easy to see that V /W inherits all its vector space structure from
that of V .
Just as was the case with direct sums, there is a natural projection operator
associated to any quotient, which we define with the following theorem.
Theorem 52. Let V be a vector space and let W ⊂ V be a subspace. Define the
map
η : V → V /W, η(v) = v + W.
Then η is a linear transformation, ker(η) = W , and dim(V ) = dim(W )+dim(V /W ).
Proof. Let v1 , v2 ∈ V and a1 , a2 ∈ R. Then
η(a1 v1 + a2 v2 ) = (a1 v1 + a2 v2 ) + W = a1 (v1 + W ) + a2 (v2 + W ) = a1 η(v1 ) + a2 η(v2 ),
and so η is linear. We have already noticed in the middle of the previous proof that
v + W = 0 + W = W if and only if v ∈ W , which (by the definition of η) proves
that ker(η) = W . The last statement of the theorem now follows immediately from
the rank-nullity theorem.
64
You might also like
- (Jimmie Gilbert and Linda Gilbert (Auth.) ) LinearNo ratings yet(Jimmie Gilbert and Linda Gilbert (Auth.) ) Linear393 pages
- Linear Transformations and Matrices GuideNo ratings yetLinear Transformations and Matrices Guide16 pages
- Lecture Notes Linear Algebra Version 20-01-2025No ratings yetLecture Notes Linear Algebra Version 20-01-202535 pages
- Linear Algebra (The Sally Series - Pure and Applied - Meighan I - Dillon - 2022 - American Mathematical Society - 9781470469863 - Anna's ArchiveNo ratings yetLinear Algebra (The Sally Series - Pure and Applied - Meighan I - Dillon - 2022 - American Mathematical Society - 9781470469863 - Anna's Archive395 pages
- Multi-variable Calculus & Linear AlgebraNo ratings yetMulti-variable Calculus & Linear Algebra52 pages
- Understanding 2D Linear TransformationsNo ratings yetUnderstanding 2D Linear Transformations28 pages
- Introduction to Linear Algebra ConceptsNo ratings yetIntroduction to Linear Algebra Concepts47 pages
- Lecture Notes Linear Algebra - Version - 12!02!2025No ratings yetLecture Notes Linear Algebra - Version - 12!02!202553 pages
- Lecture Notes on Multivariable CalculusNo ratings yetLecture Notes on Multivariable Calculus116 pages
- Matrix Multiplication in Rotations and DeterminantsNo ratings yetMatrix Multiplication in Rotations and Determinants9 pages
- Introduction - Applied Mathematics For Data ScienceNo ratings yetIntroduction - Applied Mathematics For Data Science127 pages
- Vector Spaces and Linear TransformationsNo ratings yetVector Spaces and Linear Transformations7 pages
- Quantum Cryptography Overview and ApplicationsNo ratings yetQuantum Cryptography Overview and Applications22 pages
- Business Continuity Management & Disaster Recovery Capabilities in Saudi Arabia ICT Businesses100% (1)Business Continuity Management & Disaster Recovery Capabilities in Saudi Arabia ICT Businesses29 pages
- AI in Digital Forensics & CybersecurityNo ratings yetAI in Digital Forensics & Cybersecurity15 pages
- Update On Developer Access and Platform Security - Spotify For DevelopersNo ratings yetUpdate On Developer Access and Platform Security - Spotify For Developers2 pages
- CPGET 2022 M.A. Public Administration ExamNo ratings yetCPGET 2022 M.A. Public Administration Exam73 pages
- Zero Trust Security Guide for Hybrid CloudNo ratings yetZero Trust Security Guide for Hybrid Cloud29 pages
- Software Testing Best Practices ChecklistNo ratings yetSoftware Testing Best Practices Checklist1 page
- Web Application Security Incident DetectionNo ratings yetWeb Application Security Incident Detection7 pages