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

$\displaystyle\sum_{k=0}^\infty\frac{1}{k!}A^k.$

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.

187 – Quiz 11

April 27, 2010

Here is quiz 11.

This pdf file contains the solutions.

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=3-2.$

$1=3-(17-3\times5)=17\times(-1)+3\times6.$

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