403/503 – Determinants

Here is a problem that you may enjoy thinking about. Given an matrix define a new matrix by the power series

This means, of course, the matrix whose entries are the limit of the corresponding entries of the sequence of matrices as

(This limit actually exists. Those of you who have seen Hilbert spaces should see a proof easily: Recall we defined the norm of as where in this supremum and denote the usual norm  (of or respectively) in defined in terms of the usual inner product. One checks that a series of vectors converges (in any reasonable sense) in a Banach space if it converges absolutely, i.e., if converges. Since the series defining clearly converges absolutely.)

The matrix is actually a reasonable object to study. For example, the function is the unique solution to the differential equation Here, is a fixed vector.

Note that, for any the matrix is invertible, since as a direct computation verifies.

Anyway, the problem: Show that for any matrix we have Note this is not completely unreasonable to expect: A direct computation shows that if is an eigenvector of with eigenvalue then so the formula is true whenever is diagonalizable.

187 – Information about the final exam, grades

Please remember the final exam is Monday, May 10, 10:30 am- 12:30 pm, in M/G 120. Please bring a blue book. The exam is cumulative.

This is how to compute your current grade:

1. There were 11 quizzes. Each quiz was graded out of 5 points (there were some extra credit points built in in some quizzes, so you may have scored higher than 5 sometimes). If you turned in the self-referential test, and your score was higher than your score in quiz 4, then this new score replaces what you obtained for quiz 4. Remove the 3 lowest scores, and add the other 8, for a number that represents 40% of your total score.

However, if you turned in any extra credit problems (remember that the deadline is Friday, May 7, during lecture), they will be used to  replace your lowest scores in the remaining 8 quizzes (before you add), and then, if there are still any additional points left, they will be added directly to your 40% score.

2. There were 2 midterms, each worth 20% of your total score. The highest of the two scores should be counted twice. This gives you another 40% of your total score.

3. The remaining 20% will be your score in the final exam.

If you want to have a reasonable idea of your current grade so far, compute the 80% you have so far, according to items 1 and 2, and multiply it by If this number is 90 or higher, your current grade is an A. If it is 80 or higher, your current grade is at least a B. If it is 70 or higher, your current grade is a C. If it is 60 or higher, your current grade is a D.

However, there will be a curve at the end, so your grade may be higher than the one obtained by following the instructions above.

Please email me or post a comment in case you have any questions.

187 – Quiz 11

Here is quiz 11.

This pdf file contains the solutions.

187 – Quiz 10

Here is quiz 10. 

Problem 1 asks to solve in the equation . 

This equation is equivalent to Since , there is a such that and multiplying by both sides of gives us . To finish the problem, it then suffices to find . For this, we use the Euclidean algorithm:

Now we work backwards from these equalities:

This means that, in , if we let then

(In effect, because )

And the value of we are looking for is

Problem 2 asks for a solution to the equation in

This can be done by direct computation. We have that 5 and 8 are solutions, since and

Remark: This is related to the fact, that you may have conjectured through the homework, that an odd prime is a sum of two squares iff We have The relation with the problem is that, in this equation becomes

or or where for the such that namely Note that  

Similarly, gives or But where i.e., Note that

Problem 3 asks to find the order of in i.e., the smallest such that

 There are two ways of solving this problem. One is to simply write down the powers of 3 until we reach 1:

This means that

The other way is perhaps less computational, but it requires a bit more theory. Recall form lecture Euler’s theorem stating that if then where is the number of numbers with such that and are relatively prime.

From the formula mentioned in lecture,

This means that is a divisor of 40, so it is one of These are the only powers we need to compute. This is faster than computing all the powers since, for example, We have:

and we have

403/503 – Homework 6

Due Friday, April 23, unless you convince me to move it to a later date. From the textbook, Chapter 8, exercises 3, 14, 15, 18, 20, 22, 25, 26, 27, 28.

187 – Quiz 9

Here is quiz 9.

Problem 1 asks to show that if three numbers are given, each a power of 2 or of 3, or a product of powers of 2 and 3, then either one of these three numbers is a square, or else the product of some of them is a square.

Each of these numbers, and their products, can be written in the form with A number of this form is a square if and only if both and are even. 

To a number we associate its “pattern of parities,” the pair Note that if has pattern and has pattern then their product has pattern

If one of the three numbers has pattern we are done. If two of the numbers have the same pattern, their product is a square, and we are done. So we may assume that the numbers have patterns and But then the product of the three of them is a square.

More generally, one can check that if positive integers are given (), and their prime factorizations together involve only primes, then there is a (non-empty) subset of these integers whose product is a square. Try to show this as an extra credit problem. 

Problem 2 asks to show that if 9 lattice points are given in there are two such that the midpoint of the segment they determine is also a lattice point. Here, a lattice point is a point all of whose coordinates are integers.

As before, associate to each lattice point its pattern of parity, Note that the midpoint of the segment joining and is It follows that this midpoint is a lattice point iff and have the same pattern of parity. 

But there are only 8 possible patterns: each of the three coordinates is either 0 or 1. Since 9 points are given, two must have the same pattern, and we are done.

Problem 3 asks for a list of 4 distinct integers without an increasing or decreasing subsequence of length 3. 

There are many possible ways of doing this. For example,

403/503 – Factorizations

This is the problem I mentioned today:

The prime factorizations of positive integers () together involve only primes. Prove that there is a subset of these integers whose product is a perfect square.

187 – Handout

If you need today’s handout on the pigeonhole principle and g.c.d.s, let me know and I’ll bring extra copies to lecture. 

The exercises in the handout are extra-credit. All extra-credit problems, other than the two due this Friday, are due the last day of lecture. (I may change this date, if need be, but let’s try it for now.)

187 – Quiz 8

Here is quiz 8.

Problem 1 asks to find integers such that  

One way of doing this is to follow the Euclidean algorithm to compute the g.c.d. of 13 and 8:

Now we work from these equations, starting with the last one and going up, expressing the remainders as linear combinations of the other two numbers:

Since we have

Since we have

Since we have

We have found that satisfy  

There are, of course, other ways we could have found these numbers, including trial and error: Simply list the multiples of 13 in order: 13, 26, 39, …, and note that 39 is 1 shy of a multiple of 8: giving the same solution as before.

Problem 2 asks for integers neither of which is 0, and such that

Perhaps the easiest solution is to make

Problem 3 asks for integers different from those in problem 1, such that

One way of finding these numbers is by adding the solutions to problems 1 and 2:

so

We could have also subtracted the solution to problem 2 from the solution to problem 1, to obtain

Or we could have squared the solution to problem 1: or

or

Problem 4 asks  for the number of injective functions from into

Let be 1-1. There are 5 possibilities for the value Whatever it is, can take any value in other than so there are 4 possibilities for The value can be anything in other than or so there are 3 possibilities for Finally, can take any of the remaining 2 values. This gives a total of injective functions.

Note that this is the same as the number of lists of length 4 without repetitions with values taken from the set