Math 54 Questions and Answers

----------------------------------------------------
Midterm I grading scheme:

> >  The median was 23, the mean 22.8. Here is the grading scheme
> > (\leq stands for less than or equal to)
> >
> > F  \leq 7
> > D  \leq 9
> > D+ \leq 11
> > C- \leq 14
> > C  \leq 16
> > C+ \leq 19
> > B- \leq 23
> > B  \leq 26
> > B+ \leq 29
> > A- \leq 32
> > A  \leq 36
> > A+ \leq 40

----------------------------------------------------
> Let's say you have an equation Ax=b which
> has no solution. I always thought multiplying both
> sides by something will not change the solution.
> So logically, if there's no solution to an
> equation, multiplying by something should not
> create a solution yet apparently it happens in
> this case.

What is true is that multiplying both sides of a
valid equation by something produces another valid
equation.  So yes, if you take an equation with no
solutions and multiply both sides by something
*invertible*, you won't get any new solutions,
because then you could go backwards from that valid
equation to the previous one.  But what about taking
something like

  x = x + 3

with no solutions and multiplying both sides by 0?

  0(x) = 0(x + 3)

has infinitely many solutions; it's true for every
value of x.  This may be a silly example, but for
scalars the only non-invertible thing is zero.

There are lots of non-invertible matrices, though,
and in particular, every matrix with more columns
than rows (such as the transpose of A) has a
non-trivial null space, and the very thing we are
trying to do is find an error vector (Ax-b) in the
null space of the transpose of A.

> I know that you still don't get a line that goes
> through all the points, but you're able to solve
> for x whereas before you couldn't. And I really
> don't understand why.Here's my second question:
> square matrices have inverses, and numbers have
> inverses. So if matrices also have transposes, do
> numbers have transposes?

A number (scalar) can actually be thought of as just
a 1 x 1 matrix--which is exactly what you do in the
"u transpose times v" version of the dot product.
The inverse of a 1 x 1 matrix (other than 0) is the
1 x 1 matrix with 1/ that entry, which you could
find, if you really wanted to, by row reducing.

The transpose of a 1 x 1 matrix just moves the
entry a_11 back to a_11; every number is a symmetric
matrix.  So the transpose of a number is itself.

That's for real numbers, though; there's a deeper
answer to your question for complex numbers.  When
working with matrices whose entries are complex,
the right thing to use instead of the transpose of
the matrix is the "conjugate transpose" of the
matrix, which is just the transpose but also taking
the complex conjugate of every entry--replace
a + bi with a - bi.  (This is what you need to do to
get the right complex inner product, for example.)
So the conjugate transpose of a complex number isn't
itself, it's the conjugate.

----------------------------------------------------
> Why is W(lambda) the same subspace of R^n as
> NS(lambda*I - A)?

I don't know how well it will come across in email,
but here's a try:

W(lambda)  consists of all those vectors v such that

  Av = lambda v

or equivalently

    lambda*v  - Av = 0

   lambda*Iv  - Av = 0

  (lambda*I)v - Av = 0

  (lambda*I - A) v = 0

which is the null space of lambda*I - A . . .
----------------------------------------------------
> When calculating eigenvectors, can
> you have more than one set? OFten times my answer
> is different from the back of the book, yet my
> answer still works. Is it possible to have more
> than one answer?

That's right--any time you're asked to find a basis
for a subspace, there are infinitely many different
correct answers.  (Although technically the zero-
dimensional subspace has only one basis, the empty
set.)  Since the set of vectors satisfying the
eigenvalue equation for any particular value of
lambda form a subspace, that's exactly what we're
doing--finding a basis for that eigenspace (which is
most often one-dimensional in the examples we've
seen).

It's still possible to check your answers, though--
your vector and the answer in the book should be
multiples of each other, when the eigenspace is just
a line, or, if the eigenspace is two-dimensional or
more, you should be able to write every vector in
the book's answer as a linear combination of the
vectors in your answer, and vice versa.
----------------------------------------------------
> Practice exam, Problem 7 part b
> (the question of finding the limit if it exist).
> 
> I don't think a limit exists because the numerator
> increases a lot faster than the denominator.

The limit does exist, since A is diagonalizable and
the eigenvalues are 0 and 2 -- those are the numbers
that go into the numerator.

For this particular example you could also show (by
multiplying it out) that A^2 = 2A, and thus
A^n = (2^(n-1) )A = (1/2) 2^n A, so the answer is
1/2 A.  (But this only works because the other
eigenvalue is 0).
----------------------------------------------------
> How do you find matrices when asked to, such as in
> Section 5.3, #14, and 5.4, numbers 18 and 20?

For problems like 5.3 #14, S and Lambda are always
going to be eigenvectors and values, so the only way
of changing them is to switch the order and/or take
scalar multiples of the eigenvectors.  (or linear
combinations, but only within the same eigenspace--
so in #16, you could find a different basis for the
span of the first two columns of S, but the only way
to change the third column is to take a scalar
multiple.  Then of course you can switch the order
of the columns of S, as long as you switch the order
of the eigenvalues in Lambda in exactly the same
way)

For problems 5.4 #18 and #20, the columns of Q have
to be come from the given eigenspaces--for #18,
since all the eigenvalues are distinct, the
eigenvectors are already orthogonal, and you just
have to divide each by its norm.  For #20--oh, I was
about to say you have to first apply Gramm-Schmidt
to the two vectors in the eigenspace corresponding
to the eigenvalue 5, but we're lucky; they've
already given us a pair which happen to be
orthogonal.

So none of these particular problems was actually
asking for much creativity, but we have seen
problems before of the type, "Find two matrices such
that . . ." with no numbers or anything given.
Usually in questions like these the thing there
looking for would be true for any matrices chosen at
random, so I'd try simple examples (with 1's and
0's, for example) and hope they're not _too_
simple--like, the identity matrix is usually no good
for finding counterexamples.

> Also, Section 5.2 used the term "Idempotent" as
> when a matrix C2=C (I mean squared, but I can't
> figure out superscript on BearMail).  I'm not
> certain what types of Matrices this could be,
> because the only numbers that work would be one,
> but that seems to be too direct of an answer.

Yes, an idempotent matrix is any matrix which is
equal to its own square, and there are more of them
than you might think.

A^2x = Ax  gives  l^2=l  when x is an eigenvector of A,

but l^2=l  =>  (l^2 - l) = 0  =>  (l-1)l

has two solutions, 1 and 0:  the only eigenvalues of
an idempotent matrix are 0 and 1.

----------------------------------------------------
>     My question deals with eigenvalues and
> eigenvectors.  I understand how it works, but I
> was just wondering if you could provide me with
> some common applications.  Other things we have
> dealt with so far seem to make sense in terms of a
> bigger picture, but I can't really guess some
> common uses for finding eigenvalues and
> corresponding vectors.  I wanted to know this
> because I want to remember this topic as more than
> just some rules to remember, and instead as an
> applicable tool.  Other than that, I have no other
> questions that I can think of...  thanks...

Hmm.  Say you have some complicated linear
transformation arising in some context.  For example
you have a system which can be described in terms
of, say, 17 parameters, and then you do something to
it, and want to understand how the parameters
change--they've been transformed in some way.

(In a real-world application, the transformation
isn't likely to be linear--but you'll most likely
model it by looking at a linear approximation, in
order to have any hope of understanding it.)

The simplest case would be if all the parameters
change independently:  no matter what the value of
the other parameters is, the pressure always doubles
when you pull the lever (for example).  In that
case, the matrix encoding your linear transformation
would be a diagonal matrix.

In most interesting applications, though, the
parameters all affect each other:  what happens to
the pressure depends not only on the starting
pressure, but on the pre-lever-pull elasticity and
foofle reading.  (I'm making this up, of course--can
you tell I'm not an applied mathematician?)

Then someone clever comes along and says, "We're
having trouble understanding what exactly this
process does, but that's only because we've chosen
the wrong parameters" and hands you a list.  From
then on, instead of measuring pressure, elasticity,
foofle reading, etc., you measure "property alpha",
which is defined to be twice the pressure plus the
elasticity minus the foofle reading, and "property
beta", "property gamma", etc.: a list of 17 new
parameters, each of which happens to be a linear
combination of the old parameters.  Now the process
is easier to understand:  it doubles property alpha,
triples property beta, leaves property gamma
unchanged, etc., and so we can predict exactly what
is going to happen by measuring all of those
properties beforehand.

Pulling a lever actually performs a linear
transformation on the 17-dimensional vector space of
possible combinations of parameters.  Pressure,
elasticity, etc.--the old list of parameters--
corresponds to the standard basis vectors, and the
new list of properties are its eigenvectors:
"property alpha" is an eigenvector corresponding to
the eigenvalue 2, "property beta" corresponds to the
eigenvalue 3, etc.  By using the new parameters
instead of the old, we have diagonalized the matrix
encoding the original transformation, and S and S
inverse are how we translate between the two methods
of measurement.

I don't know how helpful this is--I know there are
all kinds of actual applications, but like I say,
I'm a pure mathematician--I study these things for
their own sake without worrying too much about the
applications.
----------------------------------------------------
> What is the algorithm for the least squares problem?

The setup:  you have a collection of vectors v_1,
v_2, ..., v_k and a vector y.  You want to find the
projection of y onto the subspace spanned by the
vectors v_1, ..., v_k.

Method 1:  Apply Gramm-Schmidt to the vectors v_1,
..., v_k to obtain an orthogonal basis for their
span.  Then p is the projection of y onto v_1 plus
the projection of y onto v_2 plus ... plus the
projection of y onto v_k.

Method 2:  Put the vectors v_1, ..., v_k into the
columns of a matrix A.  Then

        T   -1 T
p = A (A  A)  A y.

> For the gram schmidt process, when we start
> out with w1 = v1 how are they all normal since the
> first value (v1 is not normalized => isn't u1 the
> normalized vector of v1?)

Start with v_1, v_2, ..., v_k

w_1 = v_1
W_2 = v_2 - projection of v_2 onto w_1
etc.

u_1 = w_1 divided by norm of w_1
u_2 = w_2 divided by norm of w_2
etc.

The vectors w_1
through w_k are not unit vectors, but the vectors
u_1 through u_k are.
----------------------------------------------------
> Is there any
> good way to quickly tell (i.e.  just by looking at
> the matrix) how many eigenvalues and eigenvectors
> it has, and hence, whether or not it is
> diagonalizable?

In general, no.  But there are a few special cases
that are fairly easy:

First of all, you have to have some idea of what the
eigenvalues actually are.  If the matrix happens to
be diagonal, upper triangular, or lower triangular,
you can just read them directly off of from the
diagonal entries.

If the matrix is singular / non-invertible (for
example, if there's a zero row or column, or if one
row or column is a multiple of another, or in
general if the determinant = 0), then at least one
of the eigenvalues is 0.

For a 2 x 2 matrix, there are only two eigenvalues,
say lambda_1 and lambda_2.  To find them, it's
enough to know that their product is the determinant
and their sum is the trace.  That is, if

    [ a b ]
A = [     ]
    [ c d ]

then

  (lambda_1)(lambda_2) = ad-bc

and

  lambda_1 + lambda_2 = a + d.

Okay, so now for determining whether or not the
matrix is diagonalizable:

First of all, if the matrix is real symmetric, then
it's automatically diagonalizable, which you know
even before calculating the eigenvalues.

The next easiest case is that you've found the
eigenvalues and they're all distinct--no number
appears more than once as a root of the
characteristic polynomial.  Then each of these
eigenvalues gives an eigenvector, and (this is a
theorem in the book) the eigenvectors from different
eigenvalues are linearly independent, so the matrix
is diagonalizable.

If any of the eigenvalues is repeated, then you have
to actually find the dimensions of the various
eigenspaces--each eigenspace has to have the same
dimension as the multiplicity of the eigenvalue in
the factored characteristic equation.  Sometimes you
can tell this quickly; for example

  [ 3  5  7 ]
  [         ]
  [ 0  3  2 ]
  [         ]
  [ 0  0  1 ]

is not diagonalizable: that "5" entry means that
when you subtract the matrix from 3I and row reduce,
you'll only get one row of zeros, not two: the
dimension of the eigenspace corresponding to 3 is
only one, not two, so you can't get 3 linearly
independent eigenvectors.
----------------------------------------------------
> Is this true? an nxn matrix has an
> infinite number of distinct eigenvectors, but at
> most n linearly independent eigenvectors. that's
> because given at least one eigen vector, any
> scalar multiple of that eigenvector is also an
> eigenvector. it's just that eigenvectors obtained
> this way are not linearly independent because they
> are a scalar multiple of the original.

Yes, if you allow for complex eigenvectors.  (For
example, the matrix

[ 0 -1 ]
[      ]
[ 1  0 ]

doesn't have any real eigenvectors at all.)  And of
course, what we're really interested in is whether
it has n linearly independent eigenvectors.
----------------------------------------------------
> I had a question which is
> problem 32 on the ch 5.3 homework:
>
> if A and B are square, diagonalizable, and have
> the same eigenvectors, how do u show that A and B
> commute, that is AB =BA

The same eigenvectors means the same "S" matrix--but
the "Lambda" matrices are different, say L_1 and L_2.

          -1      -1           -1
AB = S L S   S L S   =  S L L S
        1       2          1 2

          -1      -1           -1
AB = S L S   S L S   =  S L L S
        2       1          2 1

but the diagonal matrices L_1 and L_2 commute
(why?), so these are the same.
----------------------------------------------------
>   After plugging in the eigen values for the the
> (lambda)(I) - A and row reducing, if that reduced
> matrix is row equivalent to the Identity then the
> only null space is the zero vector and thus the
> eigen vector is the zero vector.  Is this correct?

If that ever happens, it means you've made an
arithmetic error--an eigenvalue's not an eigenvalue
unless there's at least one corresponding non-zero
eigenvector.  Put differently, if (lambda)(I) - A is
row equivalent to the identity, then it's
invertible, which means it's determinant is nonzero,
which means lambda is not a solution to
det (  (lambda)(A) - A  ) = 0, which means lambda is
not an eigenvalue.
----------------------------------------------------
> #30 section 5.2
>
> " a square matrix C is
> called idempotent if C^2=C.  what are the possible
> eigenvalues of an idempotent matrix?"
>
> What I did was to try and come up with easy models
> that fit into that category... I realized matrices
> involving zeros and + or - 1, hold the above
> requirements.  since when you square them you
> still get the same values...

That's right.  To prove it, start with the
definition:

lambda is an eigenvalue of C if and only if

  Cx = (lambda)x for some non-zero vector x

and try to use this to show that

  (lambda)(lambda - 1) = 0

which implies that every eigenvalue of an idempotent
matrix is 0 or 1.

> ps what's zworksi's website, i need to get a hold
> of the practice midterm?

http://math.berkeley.edu/~zworski
----------------------------------------------------
> I have a question about pratice midterm number
> 2.b).  I have a defintion for the coordinate
> matrix [x]s.  For b) i tested T(u+v)=T(u)+T(v),
> and T(ru)=rT(u). My conclusion was that it is a
> linear transformation.  However i m not sure about
> the domain and range.  I was thinking it is
> probabaly R^k to R^k.  Could you explain how i can
> determine the domain and range for this type of
> case?  In Hw questions, we have done some problems
> to figure out the domain and range.  However this
> problem is not clear for me.  Thank you..

The domain is just "the things that get plugged into
the transformation" and range is just "the sort of
things that come out as the result".  The
transformation takes elements of V and returns
column vectors, so the domain is V and the range is
R^k.
----------------------------------------------------
> i still don't get why you can multiply by the
> transpose of a matrix describing an inconsistent
> equation and make the equation consistent.  whats
> so special about a matrix's transpose that this is
> possible?

Hmm...let's see if I can do this question justice
without a chalkboard.

We've got our vectors v_1 through v_k, and we're
trying to project y onto the span of these vectors
to produce p.  If we put v_1 through v_k into the
columns of a matrix A, then the span of the vectors
is just the possible results of multiplying A by a
k-dimensional vector.  So define an "error vector"
as

  Ax-y

in other words, the vector from a point in the span
of v_1 through v_k to the point given by y.

The goal is to minimize the length of the error
vector, which happens when the error vector is
perpendicular to the space spanned by v_1 through
v_k, which is also the column space of A.

The only thing special about the transpose of A is
this:  the row space of a transpose is the same as
the column space of A, which is the space we're
trying to project onto.

Now we use the fact that, for any matrix at all, the
row space is perpendicular to the null space.  (Why?)
So anything in the null space of A transpose is
perpendicular to the span of v_1 through v_k, and we
can find our projection by making sure that the
error vector is in the null space of A transpose, or
in other words

   T
  A  (Ax-y) = 0.

----------------------------------------------------
> Given W a set of polynomials P_3, and W is the set of {p(x) | p(0) =
> p'(1) and p'(0) = p(1)}.  Do I say that since W is a subset of P_3, I
> simply have to prove that it is a subspace?  And if it is a subspace,
> addition and scalar multiplication must hold:
>
>
>
> Let p(x) and q(x) be in W.
>
> (p + q)(0) = p(0) + q(0) = p'(1) + q'(1) = (p + q)'(1)
>
> (p + q)'(0) = p'(0) + q'(0) = p(1) + q(1) = (p + q)(1)
>
> (p + q)'(1) is in the subspace, as is (p + q)(1), therefore it is closed
> under vector addition.
>
>
>
> Let p(x) be in W and c an element of the Reals.
>
> (cp)(0) = cp(0) = cp'(1) = (cp)'(1)
>
> (cp)'(0) = cp'(0) = cp(1) = (cp)(1)
>
> (I'm not sure here, would c*p(1) still be an element of W?)


Yup, that's a correct solution.

----------------------------------------------------
> I have been thinking about degenerate no-element
> matrices (n x 0 and 0 x n matrices, including the
> 0 x 0 matrix). Since the set of all of any of
> these types of matrices has only one member
> (namely, the matrix with nothing in it), we can
> define addition and scalar multiplication to be
> equal to itself (and it makes sense too). Then it
> satisfies all the axioms to be a vector space.
> Interesting.

Yes, each of these is technically a vector space
with one element, which is therefore a
zero-dimensional vector space.  Since every vector
space contains a zero vector, that one element is
necessarily the zero vector in the space.

> An m x 0 matrix multiplied by a 0 x n matrix
> produces an m x n matrix with what in it?

To answer this question we need to make sense of the
"empty sum"--what do you get when you add up
nothing?  The only consistent answer is zero.  Since
every entry in the result of multiplying an m x 0
matrix by a 0 x n matrix is an empty sum, the result
is the m x n zero matrix.

> Is the 0 x 0 matrix invertible? (Isn't it its own
> inverse?) I think it should be since all its
> (nonexistent) rows are "linearly independent" and
> that its rank (namely, 0) is equal to its
> dimension.

Yes, the empty set is linearly independent, and
spans any zero-dimensional vector space (since the
empty sum is the zero vector).  The 0 x 0 matrix is
both the zero matrix and the identity matrix, which
is kind of odd but necessarily true--it's the only
zero matrix which is invertible.  So all of the
axioms and theorems still apply to degenerate
matrices, but in this class there's not much
emphasis on the completely abstract (and hence
useless) so we don't really consider them.

I almost brought up the empty sum during one of
Professor Zworski's lectures, but quickly decided it
would generate a lot more confusion than
clarification.  In this particular lecture, he
defined a dependent set to be one where there was a
vector in the set which could be expressed as a
linear combination of the others.  He also mentioned
that any set containing the zero vector is
dependent.  So what about the set consisting of the
zero vector and nothing else?  Does it satisfy the
definition of "dependent"?  Yes:  there is a vector
in the set (the zero vector) which is a linear
combination of the "other vectors" (the empty set)
because every linear combination of vectors in the
empty set is an empty sum, and hence equal to the
zero vector.

----------------------------------------------------
> Hey Tracy, what does it mean to calculate e^A?
> is e the row operator here? And A simply an nxn
> matrix?  And is this even covered in 54? Thanks...

I'm not sure where you came across the term, but I'm
pretty sure that e is not a row operator, but the
real number approximately equal to 2.718 . . . One
definition of

   x
  e

for a real (or complex) number x is

          /           2      3              n  \
   lim    |          x      x              x   |
n->infty  | 1 + x + ---- + ---- + . . . + ---- |
          \          2!     3!             n!  /.

Apply the same definition to an n x n matrix A, and
you get the matrix exponential--so e^A is some n x n
matrix.

This is not something we'll cover in 54, although I
think we will cover diagonalization, which is a
useful method for actually calculating such things.
Any time you have an infinite series expression for
a function, you can try to apply the same series to
a square matrix, like sin(A), cos(A), etc.
----------------------------------------------------