pdf_input2.txt

EECS 16A Designing Information Devices and Systems I
Fall 2018 Lecture Notes Note 10
10.1 Change of Basis for Vectors
Previously, we have seen that matrices can be interpreted as linear transformations between vector spaces.
In particular, an m×n matrix A can be viewed as a function A :U →V mapping a vector~u from vector space
U ∈ R
n
to a vector A~u in vector space V ∈ R
m. In this note, we explore a different interpretation of square,
invertible matrices: as a change of basis.
Let’s first start with an example. Consider the vector ~u =
"
u1
u2
#
=
"
4
3
#
. When we write a vector in this
form, implicitly we are representing it in the standard basis for R
2
, ~e1 =
"
1
0
#
and ~e2 =
"
0
1
#
. This means
that we can write ~u = 4~e1 +3~e2. Geometrically, ~e1 and ~e2 defines a grid in R
2
, and ~u is represented by the
coordinates in the grid, as shown in the figure below:
What if we want to represent ~u as a linear combination of another set of basis vectors, say ~a1 =
"
1
1
#
and
~a2 =
"
0
−1
#
? This means that we need to find scalars ua1
and ua2
such that ~u = ua1
~a1 +ua2
~a2. We can write
EECS 16A, Fall 2018, Note 10 1this equation in matrix form:



| |
~a1 ~a2
| |



"
ua1
ua2
#
=
"
u1
u2
#
"
1 0
1 −1
#"ua1
ua2
#
=
"
4
3
#
Thus we can find ua1
and ua2
by solving a system of linear equations. Since the inverse of "
1 0
1 −1
#
is
"
1 0
1 −1
#
, we get ua1 = 4 and ua2 = 1. Then we can write ~u as 4~a1 +~a2. Geometrically, ~a1 and ~a2 defines a
skewed grid from which the new coordinates are computed.
From this example, we can see that the same vector ~u can be represented in multiple ways! In the standard
basis ~e1,~e2, the coordinates for ~u are 4,3. In the skewed basis ~a1,~a2, the coordinates for ~u are 4,1. It’s the
same vector geometrically, but with different coordinates.
In general, suppose we are given a vector~u ∈ R
n
in the standard basis and want to change to a different basis
with linearly independent basis vectors ~a1,··· ,~an. If we denote the vector in the new basis as ~ua =




ua1
.
.
.
uan




,
we solve the following equation A~ua = ~u, where A is the matrix h
~a1 ··· ~an
i
. Therefore the change of
basis is given by:
~ua = A
−1
~u
EECS 16A, Fall 2018, Note 10 2I f we already have a vector ~ua in the basis ~a1,··· ,~an, how do we change it back to a vector ~u in the standard
basis? We can reverse the change of basis transformation, thus ~u = A~ua.
Pictorially, the relationship between any two bases and the standard basis is given by:
Basis ~a1,··· ,~an
A
✛✲
A
−1
Standard Basis
B
−1
✛✲
B
Basis~b1,··· ,~bn
For example, consider a vector in the basis of ~a1,··· ,~an:
~u = ua1
~a1 +···+uan
~an = A~ua
Suppose we would like to represent it as a linear combination of different basis vectors~b1,··· ,~bn. In other
words, we’d like to write it as:
~u = ub1
~b1 +···+ubn
~bn = B~ub
Setting these equal gives the following relationship:
B~ub = ub1
~b1 +···+ubn
~bn =~u = ua1
~a1 +···+uan
~an = A~ua
B~ub = A~ua
~ub = B
−1A~ua
Thus the change of basis transformation from basis ~a1,··· ,~an to basis~b1,··· ,~bn is given by B
−1A.
10.2 Change of Basis for Linear Transformations
Now that we know how to change the basis of vectors, let’s shift our attention to linear transformations.
We will answer these questions in this section: how do we change the basis of linear transformations and
what does this mean? First let’s review linear transformations. Suppose we have a linear transformation T
represented by a n×n matrix that transforms ~u ∈ R
n
to v ∈ R
n
:
~v = T~u
Although T is represented by a matrix, we can think of it as a geometric transformation on vectors. Implicit
in this representation is the choice of a coordinate system. Unless stated otherwise, we always assume that
vectors lie in the coordinate system defined by the standard basis vectors~e1,~e2,...,~en.
But what if our vectors represented in a different basis? Suppose we have basis vectors ~a1,··· ,~an ∈ R
n
, and
the vectors ~u,~v above are represented in this basis:
~u =ua1
~a1 +···+uan
~an
~v =va1
~a1 +···+van
~an
Can we also represent the transformation T above, such that~va = Ta~ua? Let’s start by defining the matrix A:
A =



| |
~a1 ··· ~an
| |



EECS 16A, Fall 2018, Note 10 3Since our vectors ~u and ~v are linear combinations of the basis vectors we can write them as ~u = A~ua and
~v = A~va. This is exactly the formula defined in the previous section to change a vector back to the standard
basis! Now, starting with our transformation T in the standard basis, we can plug in these relationships:
T~u =~v
TA~ua = A~va
A
−1TA~ua =~va
By pattern matching, we see that if we set Ta = A
−1TA, we get our desired relationship, Ta~ua =~va.
The correspondences stated above are all represented in the following diagram:
~u
T ✲ ~v
~ua
A
−1
❄
A
✻
Ta
✲ ~va
A
✻
A
−1
❄
For example, there are two ways to get from ~ua to ~va. First is the transformation Ta. Second, we can trace
out the longer path, applying transformations A, T and A
−1
in order. This is represented in matrix form as
Ta = A
−1TA (Recall that matrices act from right to left: the closest matrix to the vector will be applied first.)
By the same logic, we can go in the reverse direction: T = ATaA
−1
. Let’s look at whats happing at each
step. First, A
−1
transforms a vector in the standard basis into the A basis. Then, Ta then acts on it, returning
a new vector which also in the A basis. Finally, multiplying by A returns a weighted sum of the columns of
A, in other words, transforming the vector back into the original standard basis.
10.3 A Diagonalizing Basis
We just saw that transformations are different in different bases. Is there a special basis under which a
transformation attains a particularly nice form? Making our transformation into a diagonal matrix is very
useful since diagonal matrices are easily invertible, they can be raised to high powers without a lot of
computation, and multiplication between diagonal matrices is commutative.
Suppose that we choose our basis vectors ~a1,··· ,~an to be the eigenvectors of the transformation matrix T,
which have associated eigenvalues λ1,··· ,λn. What does T~u look like now? Recall that ~u can be written in
the new basis: ua1
~a1 +···+uan
~an.
T~u = T(ua1
~a1 +···+uan
~an)
= ua1T~a1 +···+uanT~an
EECS 16A, Fall 2018, Note 10 4By the definition of eigenvectors and eigenvalues:
= ua1λ1~a1 +···+uanλn~an
=



| ··· |
~a1 ··· ~an
| ··· |







λ1
.
.
.
λn








ua1
.
.
.
uan




= AD~ua
= ADA−1
~u,
where D is the diagonal matrix of eigenvalues and A is a matrix with the corresponding eigenvectors as its
columns. Thus we have proved that in an eigenvector basis, T = ADA−1
. In particular, Ta, the counterpart
of T in the eigenvector basis, is a diagonal matrix.
How is transforming T into a diagonal matrix useful? Say we want apply our transformation T many
times. We might be interested in calculating T
k where k could be quite large. Although you could do this
calculation with repeated matrix multiplication, it would quite tedious and even with a computer is slow for
large matrices.
However, we just showed that we can write T = ADA−1 where D is diagonal. Consider raising this to the
power of k:
T
k =(ADA−1
)
k
We can expand this out k times and then regroup the terms:
T
k =(ADA−1
)(ADA−1
)...(ADA−1
)(ADA−1
)
=AD(A
−1A)D(A
−1
...A)D(A
−1A)DA−1
=AD(I)D(I...)D(I)DA−1
=ADD...DDA−1
)
=ADkA
−1
To raise a diagonal matrix to a power, one can raise each element to that power (try proving this to yourself by
writing out the multiplication element by element). This is a much simpler calculation that repeatedly doing
the full matrix multiplication! In addition, this formulation better allows us to write equations describing
how the transformation changes with k – having equations will help us better understand and design systems.
10.4 Diagonalization
Under what circumstances is a matrix diagonalizable? We’ve seen that our change of basis matrix A must
be invertible, so its columns must be linearly independent. Therefore, a n×n matrix T is diagonalizable
if it has n linearly independent eigenvectors. If it has n linearly independent eigenvectors ~a1,··· ,~an with
eigenvalues λ1,···λn, then we can write:
T = ADA−1
EECS 16A, Fall 2018, Note 10 5Where A =
h
~a1 ··· ~an
i
and D is a diagonal matrix of eigenvalues. Note that the eigenvalues must be
arranged to match the arrangement of eignevectors in A. For example, the eigenvalue associated with ~a1
should be in the first column on D, the eigenvalue associated with ~a2 should be in the second column on D,
and so on.
Example 10.1 (A matrix that is not diagonalizable): Let T =
"
1 0
−1 1#
. To find the eigenvalues, we
solve the equation:
det(T −λI) = 0
(1−λ)
2 = 0
λ = 1
The eigenvector corresponding to λ = 1 is ~a =
"
0
1
#
. Since this matrix only has 1 eigenvector but exists in
R
2×2
, it is not diagonalizable.
Example 10.2 (Diagonalization of a 3×3 matrix):
T =



3 2 4
2 0 2
4 2 3



To find the eigenvalues, we solve the equation:
det(T −λI) = 0
λ
3 −6λ
2 −15λ −8 = 0
(λ −8)(λ +1)
2 = 0
λ = −1,8
If λ = −1, we need to find ~a such that:



4 2 4
2 1 2
4 2 4


~a = 0 =⇒



2 1 2
0 0 0
0 0 0


~a = 0
Thus the dimension of the nullspace of T −(−1)I is 2, and we can find two linearly independent vectors in
this basis:
~a1 =



1
0
−1


 ~a2 =



1
−2
0



If λ = 8, we need to find ~a such that:



−5 2 4
2 −8 2
4 2 −5


~a = 0 =⇒



1 0 −1
0 2 −1
0 0 0


~a = 0
EECS 16A, Fall 2018, Note 10 6Thus the dimension of the nullspace of T −(8)I is 1, and we find the vector in the nullspace:
~a3 =



2
1
2



Now we define:
A =



1 1 2
0 −2 1
−1 0 2



D =



−1 0 0
0 −1 0
0 0 8



A
−1 =
1
9



4 2 −5
1 −4 1
2 1 2



Then T can be diagonalized as T = ADA−1
.
Additional Resources For more on diagonalization, read Strang pages 304 - 309. In Schuam’s,
read pages 299 - 301 and try Problems 9.9 to 9.21, and 9.45 to 9.51.
10.5 A Proof with Diagonalization
Not only can diagonalization help us raise matrices to powers, it can also help us understand some un￾derlying properties of matrices. In this example, we use diagonalization to understand when matrices are
commutative.
Show that if two n×n diagonalizable matrices A and B have the same eigenvectors, then their matrix
multiplication is commutative (i.e. AB = BA)
Let~v1,...,~vn be the eigenvectors of A and B, and P = [~v1,...,~vn] be a matrix constructed from the
eigenvectors of A and B. Also let λa1,...,λan be the eigenvalues of A, and λb1,...,λbn be the eigenvalues of
B.
Using diagonalization, we can decompose A and B such that A = PDAP
−1
and B = PDBP
−1
, where DA is
the diagonal matrix of A, and DB is the diagonal matrix of B:
DA =




λa1
.
.
.
λan




DB =




λb1
.
.
.
λbn




Now we can write
AB = (PDAP
−1
)(PDBP
−1
)
= PDA(P
−1P)DBP
−1
= PDA(I)DBP
−1
= PDADBP
−1
Because DA and DB are both diagonal matrices, DADB = DBDA. To see why this is the case, let’s look at it
element by element:
EECS 16A, Fall 2018, Note 10 7DADB =




λa1
.
.
.
λan








λb1
.
.
.
λbn




(1)
=




λa1λb1
.
.
.
λanλbn




(2)
=




λb1λa1
.
.
.
λbnλan




(3)
=




λb1
.
.
.
λbn








λa1
.
.
.
λan




= DBDA (4)
Thus:
PDADBP
−1 = PDBDAP
−1
= PDBIDAP
−1
= (PDBP
−1
)(PDAP
−1
)
= BA
We’ve now shown that A and B are commutative if they have the same eigenvectors. We can use this to
design matrices that commute!
10.6 Practice Problems
These practice problems are also available in an interactive form on the course website.
1. If~v =



1
2
3


 is in the standard basis, what is~v in the basis of ~a1 =



1
0
1


,~a2 =



0
1
0


,~a3 =



1
1
0



?
2. True or False: A 3×3 matrix with the following eigenvectors is diagonalizable:



1
1
2


,



0
2
4


,



0
1
0


.
3. Which of the following matrices is equivalent to "
1 0
0.5 0.5
#k
?
(a) "
1 0
0 0.5
k
#
EECS 16A, Fall 2018, Note 10 8(b) "
1 0
1−0.5
k 0.5
k
#
(c) "
0.5
k 0
0.5
k −1 1#
(d) "
1 0
1+0.5
k 0.5
k
#
EECS 16A, Fall 2018, Note 10 9