403/503 – Determinants

April 30, 2010

Here is a problem that you may enjoy thinking about. Given an n\times n matrix A, define a new n\times n matrix e^A by the power series


This means, of course, the matrix whose entries are the limit of the corresponding entries of the sequence of matrices \sum_{k=0}^n\frac{1}{k!}A^k as n\to\infty.

(This limit actually exists. Those of you who have seen Hilbert spaces should see a proof easily: Recall we defined the norm \|A\| of A as \sup_{\|v\|=1}\|Av\|, where in this supremum \|v\| and \|Av\| denote the usual norm  (of v or Av, respectively) in {\mathbb C}^n defined in terms of the usual inner product. One checks that a series of vectors \sum_{k=0}^\infty v_k converges (in any reasonable sense) in a Banach space if it converges absolutely, i.e., if \sum_{k=0}^\infty \|v_k\| converges. Since \|A^k\|\le\|A\|^k, the series defining e^A clearly converges absolutely.)

The matrix e^A is actually a reasonable object to study. For example, the function f(t)=e^{tA}v_0 is the unique solution to the differential equation f'(t)=Af(t), f(0)=v_0. Here, v_0\in{\mathbb C}^n is a fixed vector.

Note that, for any A, the matrix e^A is invertible, since e^Ae^{-A}=I, as a direct computation verifies.

Anyway, the problem: Show that for any matrix A, we have \det(e^A)=e^{{\rm tr}(A)}. Note this is not completely unreasonable to expect: A direct computation shows that if v is an eigenvector of A with eigenvalue \lambda, then e^Av=e^\lambda v, so the formula is true whenever A is diagonalizable.


187 – Information about the final exam, grades

April 29, 2010

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 \displaystyle \frac{5}{4}. 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

April 27, 2010

Here is quiz 11.

This pdf file contains the solutions.

The life digital

April 23, 2010

Nowadays, this is my web presence:

Although I keep quiet in most of them.

Defining non-empty small sets from families of infinite sets

April 23, 2010

John Clemens, Clinton Conley, Benjamin Miller, and I have just submitted to Fundamenta Mathematicae the second part of a paper I mentioned here a while ago. The preprint is available at my papers page.

This paper deals with families of infinite sets, typically given in some definable way in the descriptive set theoretic sense. In analogy with the results in our companion paper, that deals with finite sets, we show here how in a first-order way we can define intersecting families, and how we can extract from them small sets, at least under reasonable restrictions.

These results have been in the works for a while, but it is only very recently that we have been able to state them in their current generality, thanks to recent advances due to Ben Miller. In the mean time, Richard Ketchersid and I have proved some results in models of {\sf AD}^+ (continuing the work reported here) that have also allowed the four of us to find a few extensions of the results in this paper to models of {\sf AD}^+.

Here is a sample result, a generalization of the perfect set theorem: 

Theorem. Suppose that A\subseteq\omega^\omega is \kappa-Suslin. Then either

  1. A contains a pairwise disjoint perfect subset, i.e., for any two sequences f,g in the subset, for all n we have f(n)\ne g(n), or else
  2. A is the union of \kappa many graph intersecting \kappa^+-Borel sets, i.e.,  for any two sequences f,g in any of these sets, there is some n such that f(n)=g(n).

Here, a set is \kappa-Borel iff it comes from basic open sets by taking unions and complements, where we now allow the unions to have size \kappa rather than just countable.

An interesting side effect of our arguments is that the results are provable in {\sf ZF}. We also consider a few extensions that use the axiom of choice, but have decided to indicate explicitly whenever choice is required.

187 – Quiz 10

April 21, 2010

Here is quiz 10. 

Problem 1 asks to solve in {\mathbb Z}_{37} the equation 17x+12=5

This equation is equivalent to 17x=-7. Since {\rm gcd}(17,37)=1, there is a b such that 17b=1, and multiplying by b both sides of 17x=-7 gives us x=-7b. To finish the problem, it then suffices to find b. For this, we use the Euclidean algorithm:

37=17\times 2+3.

17=3\times 5+2.

3=2\times 1+1.

Now we work backwards from these equalities:



1=17\times(-1)+(37-17\times2)\times 6=37\times 6+17\times(-13).

This means that, in {\mathbb Z}_{37}, if we let b=-13=24, then 17\otimes b=1.

(In effect, 17\otimes 24=(408\mod37)=1, because 408=37\times 11+1.)

And the value of x we are looking for is x=-7\otimes(-13)=(91\mod37)=17.

Problem 2 asks for a solution to the equation x^2=-1 in {\mathbb Z}_{13}.

This can be done by direct computation. We have that 5 and 8 are solutions, since 5^2=25\equiv-1\mod13, and 8^2=64\equiv-1\mod13.

Remark: This is related to the fact, that you may have conjectured through the homework, that an odd prime p is a sum of two squares iff p\equiv1\mod4. We have 13=3^2+2^2. The relation with the problem is that, in {\mathbb Z}_{13}, this equation becomes

3^2\oplus2^2=0, or 3^2=-2^2, or (3\oslash2)^2=-1, where 3\oslash2=3\otimes b for the b such that 2b=1, namely b=7. Note that 3\otimes7=8. 

Similarly, 3^2\oplus2^2=0 gives 2^2=-3^2 or (2\oslash3)^2=-1. But 2\oslash3=2\otimes c, where 3\otimes c=1, i.e., c=9. Note that 2\otimes9=5.

Problem 3 asks to find o(3), the order of 3, in {\mathbb Z}_{100}, i.e., the smallest n such that 3^n=1.

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

3,9,27,81,43,29,87,61,83,49,47,41,23,69,7,21,63,89,67,1. This means that o(3)=20.

The other way is perhaps less computational, but it requires a bit more theory. Recall form lecture Euler’s theorem stating that if {\rm gcd}(a,n)=1, then o(a)|\varphi(n), where \varphi(n) is the number of numbers k with 0\le k<n such that k and n are relatively prime.

From the formula mentioned in lecture, \displaystyle \varphi(100)=100\left( 1-\frac12\right)\left(1-\frac15\right)=100\cdot\frac12\cdot\frac45=40.

This means that o(3) is a divisor of 40, so it is one of 1,2,4,5,8,10,20,40. These are the only powers we need to compute. This is faster than computing all the powers since, for example, 3^8=(3^4)^2. We have:

3^1=3, 3^2=9, 3^4=(3^2)^2=81, 3^5=81\otimes3=43, 3^8=(3^4)^2=61, 3^{10}=3^8\otimes3^2=49=50-1, 3^{20}=(50-1)^2=1, and we have o(3)=20.

403/503 – Homework 6

April 16, 2010

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

April 13, 2010

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 2^a3^b with a,b\in{\mathbb N}. A number of this form is a square if and only if both a and b are even. 

To a number 2^a3^b we associate its “pattern of parities,” the pair (a\mod2,b\mod 2). Note that if n has pattern (p,q) and m has pattern (r,s), then their product has pattern ((p+r)\mod2,(q+s)\mod2).

If one of the three numbers has pattern (0,0), 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 (0,1), (1,0), and (1,1). But then the product of the three of them is a square.

More generally, one can check that if r+1 positive integers are given (r\ge1), and their prime factorizations together involve only r 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 {\mathbb R}^3, 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 (a,b,c) its pattern of parity, (a\mod2,b\mod2,c\mod2). Note that the midpoint of the segment joining (a,b,c) and (d,e,f) is \displaystyle \bigl(\frac{a+d}2,\frac{b+e}2,\frac{c+f}2\bigr). It follows that this midpoint is a lattice point iff (a,b,c) and (d,e,f) 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, 2,1,4,3.

403/503 – Factorizations

April 12, 2010

This is the problem I mentioned today:

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

187 – Handout

April 7, 2010

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.)