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

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.

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.

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

## 187 – Quiz 8

April 6, 2010

Here is quiz 8.

Problem 1 asks to find integers $x,y$ such that $13 x+8y=1.$

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

${\mathbf 13}={\mathbf 8}\times1+{\mathbf 5},$

${\mathbf 8}={\mathbf 5}\times1+{\mathbf 3},$

${\mathbf 5}={\mathbf 3}\times1+{\mathbf 2},$

${\mathbf 3}={\mathbf 2}\times1+{\mathbf 1}.$

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:

$1=3-2.$

Since $2=5-3,$ we have $1=3-(5-3)=3\times2-5.$

Since $3=8-5,$ we have $1=(8-5)\times2-5=8\times 2-5\times3.$

Since $5=13-8,$ we have $1=8\times 2-(13-8)\times3=8\times 5-13\times3.$

We have found that $x=-3,$ $y=5$ satisfy $13x+8y=1.$

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: $13\times 3=8\times 5-1,$ giving the same solution as before.

Problem 2 asks for integers $x,y,$ neither of which is 0, and such that $13x+8y=0.$

Perhaps the easiest solution is to make $x=8,$ $y=-13.$

Problem 3 asks for integers $x,y$ different from those in problem 1, such that $13x+8y=1.$

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

$13\times(-3)+8\times 5=1,$

$13\times8+8\times(-13)=0,$

so

$13\times 5+8\times(-8)=1.$

We could have also subtracted the solution to problem 2 from the solution to problem 1, to obtain $13\times(-11)+8\times18=1.$

Or we could have squared the solution to problem 1: $(13\times(-3)+8\times 5)^2=1^2=1,$ or

$13^2\times 9+2\times13\times(-3)\times8\times5+8^2\times25=1,$ or

$13\times(13\times9+2\times-3\times8\times5)+8\times(8\times25)=1.$

Problem 4 asks  for the number of injective functions from $A=\{a,b,c,d\}$ into $B=\{1,2,3,4,5\}.$

Let $f:A\to B$ be 1-1. There are 5 possibilities for the value $f(a).$ Whatever it is, $f(b)$ can take any value in $B$ other than $f(a),$ so there are 4 possibilities for $f(b).$ The value $f(c)$ can be anything in $B$ other than $f(a)$ or $f(b),$ so there are 3 possibilities for $f(c).$ Finally, $f(d)$ can take any of the remaining 2 values. This gives a total of $5\times4\times 3\times 2=120$ injective functions.

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