Practice problems for midterm #2 (this Friday)

7.2 # 13,23,29,37,49
7.6 # 17,22,24
7.7 # 15,28,34
9.1 # 9,20,33,43
9.2 # 6
9.5 # 9,13

Monday and Wednesday May 12 & 14

5/12
9.2 Exponential growth and decay. Newton's law of cooling.
Nibbling on basil example of exponential growth (possibly negative).
9.4 What the logistic equation means, above carrying capacity.
9.5 First-order linear homogeneous equations.
A derivation of the integrating factor, based on the idea that one solves the homogeneous first and uses it as a stepping-stone.

5/14
Rederivation of the general solution.
Applied to a nonmotivated example from the book.
Then we thought about filling up a bathtub, initially half-full of cold water, with warm water, while it's draining (more slowly than it fills). During this process the water draining becomes warmer and warmer. What's the temperature at the time the bath is full?
This turned out to be a linear inhomogeneous first-order DE.

10.1 Infinite sequences. The definition of "this sequence converges to x", with epsilons and large Ns.

HW #6 due Monday May 19

9.2 #8,23,24
9.3 #4,7,13
9.5 #1,4,8,20,27

Wednesday & Friday May 7 & 9

9.1 Differential equations.

Separability.
Straight lines through the origin.
Circles around the origin.
Initial value problems.
Growth of a cell.
The logistic equation.

Linear homogeneous & inhomogeneous.
The spring equation (2nd order homogeneous).
The spring equation in presence of gravity (inhomogeneous).

HW #5 due Monday May 12

9.1 #5,6,7,11,19,21,42,52,53

Monday May 5

Comparison theorem for improper integrals.
With proper integrals, we don't have to worry about whether the answer is actually finite; it is. With improper ones sometimes we can't calculate them exactly, but we still want to know the answer is finite. The comparison theorem lets us do that; it's much more important than in the proper-integral situation.

9.1 Diff-eqs.
We just started this, and solved y' = y/x (the solutions are straight lines through the origin, which makes sense).

Friday May 2

I pointed out that step 1 of the partial fractions expansion algorithm -- long division of the numerator by the denominator, leaving a remainder term -- can be thought of as "peeling off the terms that blow up at x = infinity". Which can be done almost the same way as we do the rest of the algorithm; divide by the highest power of x, then look at the limit as x->infinity.
Not that there's much reason to do it that way; I was just sayin'.

Then we did improper integrals. I spent a long time on one example: integral₀^picot(x) dx. This is improper at both ends, and there's no best way to evaluate it, in that different approaches give different answers. So one should declare this to have no answer.

Wednesday April 2

We saw the general rule for doing partial fraction expansion, i.e. what to do if the polynomial in the denominator has repeated roots.
Then we touched upon improper integrals.

Second midterm Friday May 23

The second midterm will be on Friday May 23.

HW #4 due Monday May 5

7.6 #4,12,15,19,47
7.7 #1,2,5,6,19,30,33,78

Monday April 28

More partial fractions.
Long division of polynomials (i.e. the usual long division algorithm, but with polynomials).
Factoring the denominator using complex roots.
We haven't yet addressed the possibility that the denominator has repeated factors; that will be next time.

Friday April 25

Section 7.5. Hyperbolic trig functions.
We talked a bit about why the word "hyperbolic" is there. Both circles and hyperbolae are conic sections.

Section 7.6. Partial fractions.
So far we did a couple of examples. The basic trick, to figure out the coefficient on some term, is to multiply through by that denominator THEN set the once-denominator equal to 0. All other terms die, exposing the one you're trying to compute.

Midterm #1 breakdown

In the extremely unlikely event that your final letter grade were to be determined from only the midterm #1 grade, it would be as follows:

80-100 A
60-80 B
45-60 C
30-45 D
<30 F

We will not be figuring out your final grade using this letter, but rather the raw number, so don't worry if e.g. you got 79 rather than 80.

HW #3 due Wednesday April 30

6.3 #9,15,23,25
7.2 #2,3,7,20,36,45,66

Read 7.3 and looking heavenward, reflect internally upon the value of complex exponentials.

Integrate exp(2x) sin(x).

Wednesday April 23

Last time I introduced complex numbers, and how to think about multiplying them: they scale and rotate.
This time we studied pure rotations (i.e. scaling by 1), and showed that if there's any justice, the complex number z such that multiplying by z implements rotation by theta, should be z = exp(i theta).

This gave us formulae for sin and cos in terms of complex exponentials, which is good because the latter are much easier to work with.

Midterm with answers

The midterm answers are here.

Office hours Thursday

I am traveling and will be back tomorrow; the Tuesday office hour is moved to Thursday.
Answers to the first midterm will be up soon.

Answers to practice midterm

Here. There were a couple of other mistakes, also fixed.

Tiny mistake in practice midterm

In question #9, the integral over t should have a dt, not a dx. It's fixed now.

I'll put up answers tomorrow.

Monday April 14

We talked about linear density along a rod, and mass as the integral of density.
Using the linear density, you can compute not just the total mass (integral of rho(x) dx),
but also the rotational inertia (integral of x rho(x) dx).

We also talked about population density. If the density per square mile is only a function of the distance from the origin, then total population = integral_r=0^r=D rho(r) 2 pi r dr, where the extra factor of 2 pi r accounts for the length of the circle at radius r.

Then we talked about change in energy as
integral of (force(t) times speed(t) times cos(angle between force and velocity) dt).
So if the force is pushing the same direction as the moving object, it gains energy;
if it's the opposite direction, it loses energy;
if it's perpendicular (like whirling something around your head on a string) it stays the same.

Practice midterm #1 (which is next Monday)

It's here, in PDF.

If this gives you a sense that you'd better know your sine from cosine -- you're right! You can draw them on your cheat sheet, of course.

The case of the missing TA

While I don't have the complete story at this time on why the 2-4 PM TA was missing in action, a replacement has been obtained. He is Michael Scullard, and will indeed be at section tomorrow. I apologize deeply to the people left floundering in those sections, and hope and believe that things will run smoothly from here on out.

Friday April 11

We computed the volume of ball, using the area of a disk.
Then we tried to compute it using the area of a sphere.
Since we (pretended we) didn't know that area, we worked backwards, differentiating the volume formula w.r.t. radius to get the area of the sphere.

We computed the volume of a cube by slicing it into equal squares. Pretty silly.
Then we computed it again, by slicing at 45 degrees, into rectangles all of the same height. Sillier.
Then I described what the slices look like lengthwise: triangles, then hexagons, then triangles again, and left it to the masochists to confirm that the volume is still 1.

Definition: the average value of a function. Statement of the Mean Value Theorem in this context.

Wednesday April 9

We did a number of examples of substitution. Basic principle: look deep into your complicated function for the smallest substitution you can make.
For example, when integrating 1 / x (ln x)^1/2, let u = ln x not (ln x)^1/2 or anything more complicated.

6.1 Area between two curves.
6.2 Volume = integral of areas
We set up the integral for computing the volume of a sphere.

HW #2 due Monday April 14

Section 5.6: Turn in: 26, 38, 40, 60, 90; Additional: 13, 17, 19, 25, 85
Section 6.1: Turn in: 4, 30, 32, 50; Additional: 17, 37, 41
Section 6.2: Turn in: 6, 10, 52, 56; Additional: 7, 9, 13, 57

Friday April 4 and Monday April 7

4/4.
5.2. When a function has a different formula on different intervals, you're better off integrating it separately on the different intervals and adding them together.

5.3,4. The Fundamental Theorem of Calculus, in two versions:
v2. if you integrate something continuous then differentiate, you get back the function you started with.
v1. if you differentiate something differentiable then integrate, you almost get back the function you started with; you get it up to an additive constant.

An example of an integral to compute total food eaten by a pet hamster and lion.

An example with the Baby Name Wizard of computing the number of Allens between the ages of 30 and 40, as an integral. I drew the graphs of Beulah, Brianna, Adolf, and Monica.

4/7.
Definite integrals vs. indefinite. Definite integrals are numbers; indefinite integrals are lazily written (by everyone) as functions, when really they're "functions up to an additive constant". So make sure you include that "+ C" when indefinitely integrating something.

5.6. Recall that the chain rule of differentiation (f(g(x)))' produces a product f'(g(x)) g'(x). So when faced with an integral of a product, see if you can recognize the product as being the derivative of a composite function.

Why is the dx so important to remember in integrals? Because you need to change it, too, when you do change of variable. Otherwise you get the wrong answer, as I demonstrated.

Shortening HW #1

As we've gotten off to a slow start I'm moving the 5.6 questions to next week's homework. Don't turn them in this week. What remains:



HOMEWORK 1: Due Monday, April 7

* Section 5.2: Turn in: 14, 76; Additional: 13, 53
* Section 5.3: Turn in: 10, 20, 32, 46; Additional: 11, 19
* Section 5.4: Turn in: 4, 10, 18, 28; Additional: 19, 23
* Section 5.5: Turn in: 8, 14; Additional: 9

PLEASE PLEASE PLEASE

Ask questions in class! I said it on Monday, and I guess I should have said it again today.

I didn't even notice that I'd used epsilon and "is an element of", two different mathematical symbols that look very similar, and that there might be confusion. If you have a question of the form "what is so-and-so / what does so-and-so mean?" it (1) is surely a question somebody else has in this 200-strong class and (2) is very easy to answer quickly, no trouble at all!

There were maybe 5 questions in class today. I'd be happier with 50, even -- especially -- if they're as simple as the above. Even if they're complicated, go for it.

Wednesday April 2

Though in general we'll be computing integrals in terms of their interpretation as areas, I gave the definition as a limit of Riemann sums. Since the limit in question is a limit over refinements of partitions (not the simple sort of limit of real numbers one uses to compute derivatives), I talked about limits in general for a while first.

Most substantively going forward, I stated a few of the nice properties integrals have, like the integral of a sum being the sum of the integrals, the integral of C*f being C * the integral of f (for C a constant), and that one can break the interval being integrated over into two pieces and add them up.

This motivates the definition we'll use for integrating "from a to b" when b < a, namely the negative of integrating from b to a.

Monday March 31

We discussed briefly the topics we'll cover: integration, applications thereof, techniques for integrating, differential equations. I mentioned infinite series, but we didn't get to talk about them yet.

Welcome to Math 20b / Monday, March 31

The main course webpage is here, where one finds syllabus, hours, dates, that sort of thing.

HOMEWORK 1: Due Monday, April 7

* Section 5.2: Turn in: 14, 76; Additional: 13, 53
* Section 5.3: Turn in: 10, 20, 32, 46; Additional: 11, 19
* Section 5.4: Turn in: 4, 10, 18, 28; Additional: 19, 23
* Section 5.5: Turn in: 8, 14; Additional: 9
* Section 5.6: Turn in: 26, 38, 40, 60, 90; Additional: 13, 17, 19, 25, 85
moved to next week

This iswas the same homework as in Dr. Stevens' 20B, so you have a week to look around.

Answers to the final exam

You can view the questions and answers here.

Answers, and what to bring to the final

One twist:
To the final you may bring one double-sided sheet of handwritten notes, and your midterms. One question from the midterms will make a surprise appearance!


1a. Let a,b be integers such that a² = b³.
Is b necessarily a square?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

ANSWER. Yes, it's true. Write out the prime factorizations, and look at the power of a prime p occurring in the equation: 2a_p = 3b_p. Hence each b_p must be even. Then the product over all p of p^(b_p/2) is an integer, and a square root of b.

1b. Let a,b be integers such that a¹⁰ = b¹⁵.
Is b necessarily a 10th power?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

ANSWER. No. In fact this equation is just the 5th power of the one above! For a small solution to the equation above, take b = 2² = 4, a = 2³ = 8. Then this second equation holds but b=4 is not a 10th power of an integer.

1c. Let a,b be integers such that a³²³ = b³⁹¹.
Then a,b are both powers of some other integer. What are those powers?

ANSWER. Follow the same analysis as in 1a to get 323a_p = 391b_p. To simplify this equation, divide by the gcd of 323 and 391, which we can calculate with Euclid's algorithm. 391-323 = 68, 323-4*68 = 323-272 = 51, 68-51 = 17, 51-3*17 = 0. So 17 is the gcd, and dividing we get 19a_p = 23b_p. Hence each b_p is a multiple of 19, and b is a 19th power of some guy, where a is the 23rd power of that same guy.

2. Prove by induction that sum_i=1...n 1/i(i+1) = 1 - 1/(n+1).

ANSWER. The easiest base case is n=0, where this says 0=0. (If you wanted to do the base case n=1 where this says 1/1*2 = 1 - 1/2, that's not so hard either, but it is harder.)

Then for n>0, the LHS can be rewritten as (sum_i=1...n-1 1/i(i+1)) + 1/n(n+1) by separating out the last term. (When n=0, there is no term at all, much less a last term.) By induction, the first part of that adds up to 1-1/n. Then we check that
1-1/n + 1/n(n+1) = 1 - 1/(n+1)
which is easy.

3. Let k,n be natural numbers, such that n! > kⁿ. Show that for all N > n, N! > k^N.

ANSWER. By induction on N. The base case is N=n, which is given to us. (So in fact we're going to show it for all N greater than or equal to n.)

Now we can assume that it's true for N, and wish to prove it for N+1. Look first at (N+1)! = (N+1) N! > (N+1) k^N. We would like for that to be > k^N+1, i.e. we would like N+1 > k.

We know N+1 > n. Do we know n > k? If not, then n is less than or equal to k, in which case n! is a product of n numbers less than or equal to k, and this product is therefore less than or equal to kⁿ. But we were told that isn't true.

Having reached that contradiction, we learn n > k, so N+1 > k, which was the remaining step in showing that (N+1)! > k^N+1. This completes the induction step.

4. Let R,S be two equivalence relations on the same set X.

a. Show that R intersect S is an equivalence relation (where "intersect" means as sets of ordered pairs).

ANSWER. Let x,y,z denote elements of X.
Reflexive: since R,S are reflexive, (x,x) is in R and S, hence in the
intersection.
Symmetric: if (x,y) is in R intersect S, it's in both R and S. Since R and S are symmetric, that implies (y,x) is in both R and S. Hence it's in the intersection.
Transitive: same deal as symmetric. If (x,y) and (y,z) are in R intersect S, they're in both R and S. Since R and S are transitive, (x,z) is in both R and S. Hence it's in the intersection.

b. Let RuS denote the union of R and S. Of the three conditions required of an equivalence relation, which ones does RuS automatically satisfy? For each condition {reflexive, symmetric, transitive}, either show that RuS satisfies it, or give an example of X,R,S where RuS doesn't satisfy it.

Reflexive. Yes. Since for any x we know (x,x) is in R, it's in RuS.
Symmetric. Yes. Say (x,y) is in RuS. Then it's in either R or S. If it's in R, then (y,x) is in R since R is symmetric, so (y,x) is in RuS. Same proof for "in S".
Transitive. No. Say X has three elements {x,y,z}, and R has the associated partition { {x,y}, {z} }, whereas S has the associated partition { {x}, {y,z} }. Then (x,y) is in R, and (y,z) is in S, so both elements are in RuS, but (x,z) is not in RuS.

5. "Let b,c,n be integers, such that bⁿ > cⁿ. Then for all N>n, b^N > c^N." State the negation of this statement and prove that.

ANSWER. Rewrite with quantifiers explicit:
"For all b,c,n integers, such that bⁿ > cⁿ, for all N>n, b^N > c^N."
To negate:
"There exists b,c,n integers, such that bⁿ > cⁿ,
and there exists N>n, where b^N is less than or equal to c^N."
Proof: let n=2, b=-3, c=2, N=3. Then (-3)² > 2², but (-3)³ is less than 2³.

Basically a trick question, in that it had silly negative numbers to confuse you, but at least it wasn't a "Prove or disprove" gotcha question.

Office hours and practice final

I will be available for office hours from 10-1 on Tuesday and Wednesday. HOWEVER these are not drop-in times -- if you want to see me, email me (ideally the night before, or at least half an hour in advance).

I will be putting up practice final questions tonight, with answers posted tomorrow night. Here are the first few:

1a. Let a,b be integers such that a² = b³.
Is b necessarily a square?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

1b. Let a,b be integers such that a¹⁰ = b¹⁵.
Is b necessarily a 10th power?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).

1c. Let a,b be integers such that a³²³ = b³⁹¹.
Then a,b are both powers of some other integer. What are those powers?

2. Prove by induction that sum_i=1...n 1/i(i+1) = 1 - 1/(n+1).

3. Let k,n be natural numbers, such that n! > kⁿ. Show that for all N > n, N! > k^N.

4. Let R,S be two equivalence relations on the same set X.

a. Show that R intersect S is an equivalence relation (where "intersect" means as sets of ordered pairs).

b. Let RuS denote the union of R and S. Of the three conditions required of an equivalence relation, which ones does RuS automatically satisfy? For each condition {reflexive, symmetric, transitive}, either show that RuS satisfies it, or give an example of X,R,S where RuS doesn't satisfy it.

5. "Let b,c,n be integers, such that bⁿ > cⁿ. Then for all N>n, b^N > c^N." State the negation of this statement and prove that.

Friday Nov 17 and Mon Nov 20

Inversions of a permutation = number of pairs (i < j) such that pi(i) > pi(j).
Neighborly transpositions = (i i+1), in cycle notation.
Theorem: pi can be written as a product of invs(pi) many neighborly transpositions.
Theorem: if pi is written as a product of k neighborly transpositions, then k is greater than or equal to invs(pi), and k is congruent to invs(pi) mod 2.
Definition. An even permutation is one with invs(pi) even, similar def for odd permutations.
Theorem: invs(pi) + invs(rho) is congruent to invs(pi o rho) mod 2.
Theorem: invs(any transposition) is odd.
Theorem: if pi is written as a product of k transpositions, then k is congruent to invs(pi) mod 2.
Theorem: the Sam Loyd 14-15 puzzle is insoluble.

Last HW, due Wednesday Nov 29

1. Let w0 denote the permutation of {1..n} with the most inversions. Show that w0 o w0 = identity.

2. For any pi, show that invs(pi) + invs(w0 o pi) = invs(w0). Also show invs(w0 o pi) = invs(pi o w0).

[More coming in a couple of days]

Wednesday Nov 15

Midterm review.
Chinese Remainder Theorem.
Permutations: one-line notation and cycle notation.

HW due Monday (short)

1. Let pi be a permutation of {1..n}. When written out in cycle notation (including each i s.t. pi(i)=i as a cycle of length 1), let k be the number of cycles.

Let (i j) be the permutation that switches i and j, and leaves the other elements alone. (So this permutation has n-1 cycles, according to the definition above.)

Show that the product pi * (i j) has either k-1 or k+1 cycles, and explain when it's k-1 and when it's k+1.

5.3 #34,35,38

Midterm results

The midterm, with answers, is here.

Grade histogram:

100-80	A	******
80-60	B	****
60-40	C	******
40-20	D	**
20-0	F

Answers to the real midterm

We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.

Answers to the actual midterm

We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.

Answers to the actual midterm

We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.

Answers to the practice midterm

1. Say that p is prime, and p | a. Show that for some integer m,
p² | ma.


Let m=p. Then p | a
=> a = pb for some b
=> ma = mpb = p²b for some b
=> ma is a multiple of p²
=> p² | ma.


2. Let X be a set with 5 elements, and Y a set with 0 elements.
Show that every function from X to Y is 1:1.


It is impossible to make a function from X to Y, since the elements in X have nowhere to go. So indeed, every function from X to Y is raining frogs1:1.


3. Let S be a subset of X, where S has m>0 elements and X has n elements.
We already showed that the number of functions from X to S is mⁿ.
How many f:X->S have the property that f(s)=s for all s in S? Prove your answer.


To specify a function from X to S, we need to say where each element of X goes. We already know where the m elements of S go: to themselves. It remains to specify where the other n-m elements of X go, in S. Each has m independent possibilities, giving m^n-m, just as when we counted all functions X->S.


4. Let X be a set. How big can X be, if

every relation is symmetric?

every relation is transitive?

every relation is reflexive?

Each one of these has an answer, like "17 elements, no more". In which case give an example with 18 elements that doesn't have the property.


Sym: 1. The relation {(a,b)} on {a,b} is not symmetric.
Trans: 1. The relation {(a,b),(b,a)} is not transitive.
Ref: 0. The relation {} on {a} is not reflexive.


5. Let X={red,green,blue}, Y={0,1,2}, and Z={even,odd}. Let p:Y->Z be the parity function, so p(0)=p(2)=even, p(1)=odd. Describe the functions f:X->Y such that the composite p o f:X->Z is not onto. Show there are nine of them. How many of those f are 1:1? Draw three of them (put X, Y in columns, and draw arrows from each x to f(x)).


For p o f to not be onto, either everything in X goes to even, or to odd.
If X all goes to odd, then f:X->Y has to take everything to 1. One function so far.
If X all goes to even, then f:X->Y is really a function to {0,2}, and there are 2³ such functions. Eight more.

Forgive me for not drawing these in ASCII.


6. (The "Freshman's Dream".) Let a,b be integers. Show that
(a+b)³ is congruent to a³+b³ mod 3.


(a+b)³ = a³ + 3a²b + 3ab² + b³.
So the difference between that and a³ + b³ is 3(a²b + ab²), a multiple of 3.


7. Is the same true with each 3 replaced by 4?
(I shouldn't have to add:) If true, prove it; if false, provide a counterexample.

No; let a,b=1. Then (a+b)⁴ is 0 mod 4, but a⁴+b⁴ is 2 mod 4.
(In fact it holds for all prime exponents.)

Some practice midterm questions

If having thought about a question you decide you're really stuck, leave a comment asking for a hint. Conversely, if you have a hint to suggest, leave that comment!

1. Say that p is prime, and p | a. Show that for some integer m,
p² | ma.

2. Let X be a set with 5 elements, and Y a set with 0 elements.
Show that every function from X to Y is 1:1.

Yes, really. This question is written correctly, and means exactly what it says.

3. Let S be a subset of X, where S has m>0 elements and X has n elements.
We already showed that the number of functions from X to S is mⁿ.
How many f:X->S have the property that f(s)=s for all s in S? Prove your answer.

(I'll leave the actual number in the comments, but then you still should think about proving it.)

4. Let X be a set. How big can X be, if

every relation is symmetric?

every relation is transitive?

every relation is reflexive?

Each one of these has an answer, like "17 elements, no more". In which case give an example with 18 elements that doesn't have the property.

5. Let X={red,green,blue}, Y={0,1,2}, and Z={even,odd}. Let p:Y->Z be the parity function, so p(0)=p(2)=even, p(1)=odd. Describe the functions f:X->Y such that the composite p o f:X->Z is not onto. Show there are nine of them. How many of those f are 1:1? Draw three of them (put X, Y in columns, and draw arrows from each x to f(x)).

6. (The "Freshman's Dream".) Let a,b be integers. Show that
(a+b)³ is congruent to a³+b³ mod 3.

7. Is the same true with each 3 replaced by 4?
(I shouldn't have to add:) If true, prove it; if false, provide a counterexample.

Office hour today 3-4 / Midterm topics

Usually it's 4-5 (after class), but there being no class I'm moving
it up an hour.

This midterm will be run the same as the last one. Focus on number theory, equivalence relations, and 1:1/onto properties of functions.

Wednesday Nov 1

Properties of functions: injective AKA 1:1, surjective AKA onto, bijective.
Functions have inverses iff they're 1:1 and onto.
If f,g are injective, so is g o f.
If g o f is injective, so is f (maybe not g).

Statement: every function X -> Y can be factored as a surjection X -> X/~, then a bijection X/~ -> S, then the inclusion of a subset S -> Y.
We'll prove it next time.

Monday Oct 30

Equivalence relations vs. "partitions" of a set.
From a partition, we built an equivalence relation, and vice versa.
(There's lots to check about these recipes, and it took the whole hour, without even getting to prove that each recipe was the other's inverse.)

HW due Nov 6

4.3 #33,37,43,47
4.4 #54
5.1 #1,6,7

HW due Monday Oct 30

[FP]
3.5 #102,106
4.1 #16
4.3 #29
4.5 #69,73,82

IMPORTANT REMINDER

No class or office hour on Friday Oct 27.

Wed Oct 25

Ordered pairs. Cartesian product. Relations. Functions. Equivalence relations.

Monday Oct 23

Congruence notation and some applications (divisibility by 9,3,37,11).

Friday Oct 20

Finished proving unique factorization.
Noted that in other contexts, like Z[i] and Z[sqrt{-5}], the primes may be different, and unique factorization may fail.
Used unique factorization to study the following question: what fraction of integer points in the plane are visible from the origin? Answer: 6/pi².
Notation: p^a || n if p is prime and p^a|n but p^a+1 doesn't |n.

Wednesday Oct 18

Midterm review.
We proved existence of factorization of natural numbers into primes (by strong induction).
We started proving uniqueness.

HW #3 due Monday Oct 23

From [FP]:

3.1 #2,7,9,13
3.2 #20,35
3.4 #84,92,93

Results of midterm #1 -- LINK CORRECTED

The midterm with answers is available here in PDF. (Really this time!)

The grading is done. The number -> letter correspondence is as follows:

0- 20 F	1 of these
20- 40 D	4 of these
40- 55 C	5 of these
55- 75 B	5 of these
75-100 A	4 of these

What do these letters mean?

If the term ended today, and all records of your homework disappeared so that only midterm #1 could form the basis of your grade, that's what I'd give you. It's only here so that your final grade won't be a big surprise.

I am not going to toss out the number and average together the letters you get, at the end of the course. So there is no point worrying about "I got a 74 instead of a 76 -- please give me two more points!" It's exactly like someone with a 76 looking for a 78.

Topics of midterm #1

From [FP]: sections 1.2-1.6, 2.2, 3.1-3.2.
From class: definitions from class related to graphs. (They'll be written on the test, too, but better if you already know them!)

There will be problems of the form

"Here is an English statement.
Which of the following statements follow from it?
[big mess of for-alls vs. there-exists in various different orders]."

You should be able to write out a proof by weak induction -- base cases, induction step, everything in place.

Wednesday Oct 11

We finished proving that Euclid's algorithm works. This required strong, not just weak, induction.
The main consequence: the GCD of A and B can be written as mA+nB for some integers m,n. With this we'll eventually prove that integers have unique factorizations into primes.

Next time (Friday) we'll review the course to date, in preparation for the first midterm, on Monday October 16. See the course web page for details.

HW #2 solutions (non-book problems)

1. Show that n³-n is a multiple of 6, for any integer n.

Answer. Write n = 6m + r, where r is one of 0,1,2,3,4,5.
Then n³-n = (6m+r)³ - (6m+r) = some multiple of six plus r³ - r.
Then we check r³-r for each possible r, getting 0,0,6,24,60,120, each of which is a multiple of six.

---

2. Let G be a connected graph and v a vertex of degree 1. Using the
vertex-based definition we came up for of connectedness, prove that
the deletion G\v is also connected.
("Let w,x be any two vertices of G\v. We want to show that there
exists a chain in G\v...")

---

A. Let w,x be any two vertices of G\v. We want to show that there
exists a chain in G\v of vertices v_1..v_n such that v_1=w, v_n=x,
and {v_i,v_{i+1}} is an edge for each i=1..n-1.

Since G is assumed connected, we know there exists such a chain
of vertices in G, call it (w_1..w_m). (So w_1=w, w_m=x.)
(If for all i, w_i is not v, then this chain is also in G\v,
but we have to deal with the possibility that some w_i=v.)

Let u be the unique vertex such that {u,v} in E_G (unique by the
assumption that degree(v)=1).

For each i such that w_i=v, the only possibility for w_{i-1},w_{i+1} are
that each is equal to u. (Note that i is not 1 or n, since w,x are not v.)
Remove w_i, w_{i+1} from the chain, so that the new, shorter chain
goes ...,w_{i-1},w_{i+2},... We need to be sure that this still
has each vertex adjacent to the next one:
{w_{i-1},w_{i+2}} = {u,w_{i+2}} = {w_{i+1},w_{i+2}} in E_G. Voila.

In this way, we have constructed a chain of vertices connecting w to x,
none of which are equal to v. So this new, shorter chain is in G\v.
Since w,x were any two vertices of G\v, this shows G\v is connected.

---

3. Let G be a graph and v a vertex of degree 1. Assume that the
deletion G\v has a nontrivial decomposition. Construct a decomposition of G.
("Let V1, V2 be a nontrivial decomposition of G\v. We will use this to
build one of G itself...")

---

A. Let V1, V2 be a nontrivial decomposition of G\v. We will use this to
build one of G itself.

As in #2, let u be the unique element of V_G to which v is connected.
Note that u is not equal to v, so u is a vertex of G\v.

There are then two cases: u in V1, or u in V2, since V1 union V2 = V_(G\v).

Assume u in V1. Let V1' = V1 union {v}.
Then we claim that (V1', V2) is a decomposition of G.
There are several things to prove:
1. V1' union V2 = V_G
2. V1' intersect V2 = {}
3. For any vertex a in V1' and b in V2, {a,b} is not in E_G.
We take them in order.

1. V1' union V2 = {v} union V1 union V2 = {v} union V_{G\v} = V_G,
by the definition of V_{G\v} as V_G with only v ripped out.
Also, we know V1 union V2 = V_{G\v} by the assumption that
they form a decomposition of G\v.
2. We know V1 intersect V2 = {}, by the assumption that they form
a decomposition of G\v. So the only chance for V1' to
share an element with V2 is if v is in both. But since
V1 union V2 = V_{G\v} doesn't contain v, V2 doesn't.
So V1' intersect V2 is empty.
3. a is either in V1, or a=v. Since V1,V2 is a decomposition,
if a is in V1 then there is no b in V2 with {a,b} in E_G.
So the other case is a=v. But then the only b in V_G such that
{a,b} is in E_G is b=u. And u is in V1, by assumption.
Hence u is not in V2, since V1 intersect V2 = {}.
So there is no b in V2 such that {a,b} is in E_G.

The other case, u in V2 instead of V1, is exactly the same except
with "V1","V2" switched throughout the proof.

---

4. What's the relation between #2 and #3?

---

A. We proved (mostly) in class that a graph has a decomposition iff it
is not connected. In light of that, #2 is equivalent to the
contrapositive of #3.

G connected ===> G\v connected
has contrapositive
G\v disconnected ===> G disconnected
or equivalently
G\v has a nontrivial decomposition ===> G has a nontrivial decomposition

Monday Oct 9

Weak induction proof of the "division algorithm".
GCDs. Euclid's algorithm for computing GCDs.
We started proving, by strong induction, that this does actually compute GCDs, but didn't finish it.

Friday Oct 6

Examples of weak induction proofs.
Thm: 1 + 2 + ... + n = (n+1 choose 2).
Thm: The number of subsets of X is 2^|X|, for X finite.
Thm: If G is a finite graph, the sum of the degrees is even.

Next time: Euclid's algorithm for computing GCDs, and a proof that it works, using strong induction.

Wedneday Oct 4

Two properties we will need of the naturals: only 0 is not a successor, and every nonempty subset has a least element (Well-Ordering). Examples of non-well-ordered sets.
Weak induction. Strong induction.
Theorem about theorems: weak induction proofs are actually proofs. Proof: uses Well-Ordering.
Sample weak induction proof: If n>4, then 2ⁿ > n².

Monday Oct 2

Basic proof technique: splitting into cases.
Sample theorem: For any integer n, n(n-1)/2 is an integer too.
Proofs by contradiction are "really" splits into the cases "what I want to be true is true vs. what I want to be true is false."
When a proof by contradiction is silly.
Why proofs by contradiction are dangerous.

HW #2: due Oct 9

1. Let n be an integer. Prove that n³-n is a multiple of 6.

2. Let G be a connected graph and v a vertex of degree 1. Using the vertex-based definition we came up for of connectedness, prove that the deletion G\v is also connected.
("Let w,x be any two vertices of G\v. We want to show that there exists a chain in G\v...")

3. Let G be a graph and v a vertex of degree 1. Assume that the deletion G\v has a nontrivial decomposition. Construct a decomposition of G.
("Let V₁, V₂ be a nontrivial decomposition of G\v. We will use this to build one of G itself...")

4. What's the relation between #2 and #3?

From [FP]:

1.4 #56,58,59,67
1.5 #84,90
1.6 #93,99,100,102

Friday Sep 29

Last time we defined a graph to be "connected" if there were a series of edges connecting any two vertices. But the graph with just one vertex has no edges. Surely we'd like it to be connected, though.

Fix #1: ask instead for a series of vertices.
Fix #2: ask for a series of edges connecting any two different vertices.

Union of sets, intersection, subset.

Def. A decomposition of a graph.

We started proving
Thm. A graph is connected iff it has no nontrivial decompositions.
Proof. => Assume G is connected. If it has a nontrivial decomposition... well, no it doesn't.
Next time: we'll go the other direction, and discuss proofs by contradiction; sections 1.4-1.6 of [FP].

Wednesday Sep 27

Converse, inverse, contrapositive. CAPalert example: "If it's not suitable for children, it's not suitable for adults!"

Definition. The deletion of a vertex from a graph.
Definition. A graph is connected if...
Question. Say G is regular, and v in V_G. When is the deletion again regular?
Answer (we didn't prove yet): iff v is connected to all, or to no, other vertices.

Monday Sep 25

Reiteration: "A => B" meaning more in English (actual causation) than it does in mathematese.

First taste of sets: they are determined by their elements, with no concept of order or repetition. Just in or out.
So {3,7} = {7,3} or {3,7,3,3,7}, but not {7} or {3,{7}}.
Set-forming notation.
Definition. A graph G is a pair of sets V_G, E_G where each element of E_G is a pair of (two different) elements of V.
(Frequent construction: "Definition. An X (noun) is a Y that Z.")
Definition. The degree of a vertex... a couple of versions.
Definition. A graph is regular if all vertices have the same degree... also a couple of versions.
(Frequent construction: "Definition. An X is Y (adjective) if it does Z.")

HW #1 due Monday Oct 2

1. Consider the following propositions about a function f(x,y) of two real numbers:

P1. for all x and y, f(x,y)=0

P2. for all x, there exists a y such that f(x,y)=0

P3. for all y, there exists an x such that f(x,y)=0

P4. there exists an x such that for all y, f(x,y)=0

P5. there exists a y such that for all x, f(x,y)=0

P6. there exist x and y such that f(x,y)=0.

a. For the following functions f, which of P1-P6 are true?

i. f(x,y) = 0 everywhere. ANSWER: "P1,P2,P3,P4,P5,P6 are all true."
ii. f(x,y) = x+y.
iii. f(x,y) = x³-xy²
iv. f(x,y) = y-x².
v. f(x,y) = x+y².
vi. f(x,y) = x²+y²-1

b. How do things change in part (a) if we allow x,y to be complex numbers?

2. Consider the following propositions about a function f(x,y,z) of three real numbers:

P1. for all x, there exists a y such that for all z, f(x,y,z)=0

P2. there exists an x such that for all y, there exists a z such that f(x,y,z)=0

a. Write down a function f(x,y,z) that satisfies P1 but not P2. Explain how to find the y required in P1, and why the x in P2 doesn't exist.

b. Write down a function f(x,y,z) that satisfies P2 but not P1. Explain how to find the x and z required in P2, and in P1 give an x for which there is no good y.

Warning: the reason this question is hard is that it has a bajillion possible answers, all equally good. Answering this question is more art than science.

3. Definition. A graph G is vague-ular if for all {v,w} in E_G, degree(v) = degree(w).

a. Prove that if a graph G is regular, it is vague-ular.

b. Show that the converse, "if a graph G is vague-ular, it is regular" is not true.

(What does this mean, "show this implication is not true"? It means give an explicit example of a graph that is vague-ular but not regular.)

The rest are from [FP], meaning, Fletcher and Patty. They're not as hard -- more just to help you check that you know what's going on.

1.1 #2, 3, 4, 8, 11
1.2 #21 (true, false, sometimes), 27
1.3 #52 (write these out with quantifiers)

Friday Sep 22

First class, partly about logistics, and the main goals.

And, or, implies (chapter 1.1, 1.2). The main thing to know about how mathematicians use the phrase "X implies Y" is that they don't really care about causality -- just that whenever X is true, Y will definitely also be true.

Quantifiers (chapter 1.3). The perils of reordering them, and how they interact with "not".

Fall 2006: Math 109, Mathematical Reasoning

Here's the web page for Math 109, where one finds the slower-changing facts about it. On this blog I'll keep a description of day to day occurrences, including homework assignments.

While I may enable commenting on some of these posts, it's not the surest way to get a rapid response from me -- much better to email me, "allenk", at the ucsd address. (Parse that, spambots!)

Last class!

Plucker embedding, Veronese map, Segre embedding.
Line bundles and sections. Sections of O(m) on projective space. Contravariance in spaces of sections.
Associated bundle construction.
Statement of the Borel-Weil theorem.

Extra class Monday 12:30 PM

We'll have an extra class Monday 12:30-2 PM, location still to be determined.

Thursday June 8

Some puzzle stuff: through four generic lines in space, two pass.

Proj of a graded algebra over C. The special case that the ring is generated in degree 1.

Lemma we didn't prove.
1) If G an algebraic group acts on R, hence on Proj R, the stabilizers have finitely many connected components.
2) If a point x is not G-fixed, then the G-orbit through x isn't closed, and the extra stuff in the closure is of lower dimension.

Borel's theorem. If B is the group of upper triangular matrices, acting on R hence on Proj R, then B has a fixed point in Proj R.

Proposition. Let V be a rep of GL_n. Then each closed orbit X of GL_n on the projective space PV is a GL_n-equivariant image of GL_n/B. If V is irreducible, then it is the linear span of the affine cone over X.

GL_n/B is a flag manifold, which embeds in a product of Grassmannians. The Plucker embedding of a Grassmannian.

Tuesday 6/6/6

Grassmannians. The Stiefel manifold. Orbits of N on the Grassmannian. Schubert varieties, which give a basis for homology. An intersection calculation in the cohomology ring of a Grassmannian. Factoid: the cohomology ring of the Grassmannian, with the Schubert basis, is isomorphic to the puzzle ring with its statuatory basis.

Tuesday May 30

The hive -> honeycomb bijection.
The puzzle -> honeycomb injection, and its image.

c_lambda,mu^nu nonzero
<=> there exist integral hives with that boundary
=====> there exist real hives with that boundary
<=> that boundary satisfies all puzzle inequalities
<=> for certain smaller integer honeycombs, the boundary satisfies certain inequalities
<=> for certain smaller (lambda',mu',nu') with c_lambda',mu'^nu' nonzero, (lambda,mu,nu) satisfy certain inequalities.

This becomes a recurrence once one can reverse the long arrow, which is now called the saturation theorem. The recursion was conjectured by Horn, in the context of the sums of Hermitian matrices.

Exercises #7

1. Show that the number of rhombi pointing at one side of a puzzle is the number of inversions on that side (counting counterclockwise).

2. Break a puzzle into regions by joining two pieces if they are of the same shape and share an edge, so there are 0-regions, 1-regions, and rhombus regions. Show that each region is convex, and that rhombus regions are parallelograms.

3. Orient the edges in a puzzle that separate regions; clockwise around 0-regions, counterclockwise around 1-regions. (Erase the other edges.) Classify the possible local pictures this directed graph can take around an interior or exterior vertex.

4. Let alpha,beta be two strings of k 1s and n-k 0s, labeling the SW and SE edges of a puzzle triangle read left to right.
a) If there is a puzzle, filling in this triangle, show that the last i entries of alpha have as many or more 1s as the first i entries of beta (for each i=1..n), a sort of dominance condition.
b) Show the converse -- if this dominance holds, then there is a filling.

Thursday May 18

Every overlapping combination of rhombus inequalities with no dependence on the interior is a positive combination of nonoverlapping ones, and every nonoverlapping combination can be uniquely labeled to make a puzzle. (We didn't, and won't, prove these.)
Harder fact: the only puzzles that give important inequalities are the ones that can filled in uniquely given their boundary.
Deflation of puzzles. Consequences for the number of each kind of piece.
The puzzle ring for (n,k), and its relation to the hive ring. (We have yet to prove that the natural map is a ring homomorphism.)
Definition of honeycombs.

Exercises #6

1. There is a better RSK correspondence:
{matrices of natural numbers with row sums mu₁ and column sums mu₂}
correspond to
{pairs (A,B) of two semistandard Young tableaux of the same shape, A content mu₁ and B content mu₂}
(semistandard means weakly increasing in each row, strictly in each column).
a. Show how the RSK we defined in class is a special case.
b. Show how to derive this from the hive associator, by tensoring with Altⁱ Cⁿ at each step (for various i) rather than just Cⁿ as we did.

2. Find all the puzzles of size 3.

3. Assume that a puzzle has only one 1 on one side. Give a description of all such puzzles. Show that for each size n, there are {n+1 choose 2} of them.

4. Consider a positive linear combination of rhombus inequalities where no two rhombi overlap in a triangle. If the dependence on the interior all cancels, show that the coefficients on the rhombi are all equal (so may as well be scaled to 1).

Tuesday May 16

An application of hive associativity: the RSK correspondence, which says that
words <-> pairs consisting of a GC pattern and a standard Young tableau.

Puzzles. Each puzzle gives an inequality on the possible boundary values of a hive.

Thursday May 11

Hives define an associative ring; the octahedron recurrence provides an associator.
Henriques' theorem (statement only): the associator satisfies the pentagon identity.
The accessibility lemma from linear programming (statement only).
Consequence for hives: if we can figure out all the ways to add up rhombus functionals such that the dependence on the interior vertices cancels, we'll learn the possible boundaries of real hives.

Tuesday May 9

For Sasha Postnikov's talk:
Schur polynomials. Schur functions. Schur positivity.

Example of a tensor product calculation using hives.
Definition of the hive not-necessarily-associative ring.
Proposition: as a ring, Rep(GL(n)) = Z[the fundamental reps, and det^-1].

Exercises #5

1. Use the Steinberg rule to prove the Pieri rule.
2. Show that the hive theorem is true for the following cases:

tensoring with the trivial representation

the case V_(2,1,0)^@2

the Pieri cases.

3. A hive is defined by its convexity. Hence, if we add a linear function to a hive we get another one. What is the corresponding statement about tensor products?
4. Fix lambda,mu,nu. Show that the space of real hives with this boundary is bounded (hence compact).
5*. Fix lambda,mu,kappa. What does the Steinberg rule say about the limit of
c_{N lambda,mu}^{N lambda + kappa} as N -> infinity? (We dealt with the case that lambda is regular dominant, i.e. has no repeats.)

Thursday May 4

The Steinberg tensor product formula. The flopping-and-subtraction interpretation. Statement of the Pieri rule. Certain limits of tensor product multiplicities are weight multiplicities. Decomposing a double tensor product vs. computing the invariant space in a triple tensor product.
Definition of hives. Statement of the theorem: hives compute tensor products.

Thursday April 27 - no class next Tuesday

Side note: to compute the character of a GL(n) rep on an arbitrary element of GL(n), take its eigenvalues and feed that diagonal matrix into the WCF.

Given the multiplicity diagram of a G-rep V, apply difference operators in the direction of the negative roots, and the result (in the dominant Weyl chamber) tells you the multiplicities of the irreps in V.
The branching rule from GL(n) to GL(n-1).
The weight of a Gel'fand-Cetlin pattern is the list of differences in the row sums.
Theorem: there is a basis of V_lambda indexed by Gel'fand-Cetlin patterns, where each basis vector is a T-weight vector whose weight is that of the GC pattern.

I am away next Tuesday.

Tuesday April 25

Statement of the Weyl character formula (WCF) with a single denominator, Den.
The Kostant partition function.
The Kostant multiplicity formula, as the Fourier transform of WCF.
Pictures of the weight multiplicity diagrams as given by the Kostant multiplicity formula, for the GL(3) case.
Proof that the WCF is actually a Laurent polynomial with integer coefficients (given by the Kostant multiplicity formula).
Weyl's proof that the WCF is the character of an irrep, indeed of V_lambda.

Gel'fand-Cetlin patterns, the integer points in the (compact, convex) Gel'fand-Cetlin polytope.
Example: Gel'fand-Cetlin polytopes for GL(3).

No office hour next Tuesday

There's a special combinatorics seminar next Tuesday at 2:30, so no office hour after class that day.

Thursday April 20

Lemma. Let D be an S_n-invarant weight multiplicity diagram with some D^mu > 0. Then D defines a class function Chi_D:U(n) -> C. If the integral over U(n) of |Chi_D|² = 1, then D is the weight diagram of an irrep.
Weyl integration formula, in terms of volumes of conjugacy classes.
Volumes of conjugacy classes of U(n). (statement, no proof; look in the notes on the class web page for full details)
The Weyl denominator Den, as a sort of square root of the volume of the conjugacy class.
Statement of the Weyl character formula (WCF), manifestly S_n-invariant version.
Theorem. GL(2) acting on Sym^k C² is an irrep.
The WCF for GL(2).
The rho-shifting in Den * WCF.

Exercises #4

1. Figure out how to compute the Sym² and Alt² of a weight multiplicity diagram. Do so for the diagram for Sym³ C³ = V_(3,0,0). In particular, show that Sym² Sym³ C³ contains Sym⁶ C³ plus one other irrep, and Alt² Sym³ C³ contains Sym³ Alt² C³ plus one other irrep. Write down all the high weights in this example.

2. Give an example of a group homomorphism in which the center doesn't go to the center.

3. Using our construction of the irreps of GL(n), show that in an irrep GL(n) -> GL(m) the center does go to the center. More concretely, how does the center of GL(n) act on V_lambda?

4. Using Schur's lemma, show that in any irrep G -> GL(m) the center goes to the center.

Tuesday April 18

Define V_lambda as the irrep of high weight lambda we already constructed.
Lemma. There are finitely many dominant weights dominated by a given weight.
Corollary. Every S_n-invariant multiplicity diagram is a Z-linear combination of characters of V_lambdas.
Theorem. The V_lambdas are all the irreps of U(n).
Lemma. If a polynomial on M_n vanishes on U(n), it vanishes everywhere.
Def. Rational rep of GL(n).
Thm. Every rep of U(n) extends uniquely to a rational rep of GL(n).

Then we described (without proof) the multiplicity diagrams of irreps of U(3), and computed the decomposition of the tensor square of V_(2,1,0).

Exercises #3

1. Show that dominance order is indeed a partial order.

2. Let lambda be dominant, and mu a convex combination of the permutations of lambda.
(This means: let x_pi be a nonnegative real number for each permutation pi in S_n, with \sum_pi x_pi = 1. Let mu = \sum_pi x_pi pi.lambda . Then mu is a "convex combination".)
Show that lambda is more than mu in dominance order.

3. Call a weight multiplicity diagram D "saturated" if the conditions
a) mu is integral
b) mu is a convex combination of weights in D
together imply that mu is itself a weight of D.
Show that Symⁿ C² is the smallest S₂-symmetric saturated multiplicity diagram with high weight (n,0), for some appropriate definition of "smallest".

4. Show that the reducible representations we made by tensoring fundamental representations together are saturated.

Thursday April 13

Gah! I'm already slipping on keeping this blog up-to-date.

Lemma (b). The "fundamental representations" Alt^k Cⁿ have weights all of multiplicity 1. The high weight is (1,...,1,0,...,0) with k 1s and n-k 0s. The other weights are permutations thereof, and all other weights are less than the high weight in dominance order.

Lemma (c). Call a rep "good" if the high weight is multiplicity one, and all other weights are smaller in dominance order. (So the high weight is unique.) Then the tensor product of two such reps is again "good", and the new high weight is the sum of the two individual high weights.

Theorem 1. Every irrep has a dominant high weight.

Theorem 2. For every dominant weight, there is an irrep with that high weight, and it's "good".

Tuesday April 11

We won't prove that compact Lie groups have finite, positive, left-invariant measures -- leave that for a differential topology class. With that, our character theorems apply to any continuous representations.

Weight lattices of tori. Weight multiplicity diagrams. Ex: Symⁿ C².

Theorem. Two reps of U(n) are isomorphic iff when restricted to T = diagonals, they're isomorphic. (This is why we did character theory.) So we can study reps by their multiplicity diagrams.

Ex: Symⁿ C² @ Sym^m C² ~ \sum_{k satisfying triangle inequalities, same parity as m+n} Sym^k C² @ det^@(m+n-k).

Highest weight of a rep. Dominant weight. Dominance order.

Stated the classification of irreps of U(n) in terms of their highest weights; will prove it next time.

Lemma (a): if V is a U(n)-rep, its multiplicity diagram is S_n-invariant.

Exercises #2 (corrected)

I'll write tensor product as @.

1. If V,W are two reps of G, show that Chi_{V @ W} = Chi_V Chi_W.

2. If V,W are two reps of G, and |Chi_V(g)| < dim V except for g=1, show that W is isomorphic to a subrepresentation of V@V@....@V for some number of factors.

3. Show that the condition in #2 holds for G simple, V not zeroa trivial representation.

4. If V is a rep, compute the character of G on the symmetric tensors Sym²V and the alternating tensors Alt²V, in terms of the character of V. For each irrep W of S₄, confirm that the characters of Sym²W and Alt²W are nonnegative integer combinations of the irreducible characters.

Thursday April 6

We defined the averaging operator pi_V on a representation, and proved it to be a projection onto V's invariant subspace. Schur's lemma. Orthonormality of irreducible characters. Class functions. Reps are isomorphic iff they have the same character. Some character table stuff, with S₃, S₄ as examples.

We didn't prove that irreducible characters give an orthonormal basis of class functions; you can find that in the notes on the course web page.

Main results of the survey

Surprisingly, noone circled "Combinatorics is a scourge" without also circling "is fun, interesting, and instructive". I suppose such people were scared off by the course description, as is probably best.

Almost everybody circled "Pretty solid" or "Please, don't bore me" for tensor products. As such, I'm not going to do them in class. You can find them in any book entitled "Algebra", e.g. Hungerford, Artin, Lang.

People liked having office hours directly after class.

Exercises #1 (corrected)

I'm putting these here so you can check that you're keeping up. If you find something weird, or want a (nother) hint, post a comment. (If you've got a hint, you can post that too.) Or you can just come and ask me about them after class.

1. Let V be a finite-dimensional irrep of an abelian group A (possibly infinite, even infinitely generated!). Show that V is 1-dimensional.
Hint: either every group element acts a multiple of the identity, or some element doesn't.

2. Let G be a finite abelian group. Show that the number of distinct irreps of G is |G|. (Hint: start with the cyclic case.)

3. Let G be a group, and Rep(G) resp. Irr(G) the set of {reps resp. irreps of G up to isomorphism}. Let Pic(G) be the set of {1-d reps of G up to isomorphism}. Show that Pic(G) is a group under tensor product (which includes checking some well-definedness), and that Pic(G) acts on Rep(G) by tensor product, preserving the subset Irr(G).

4. Calculate Pic(S₃), and find an element of Rep(S₃) that is fixed under the action from #3.

5. Generalizing #2 & #3, show that Irr(G)Pic(G) is isomorphic to G/[G,G]. Warning: there is no natural isomorphism!

Tuesday April 4

I outlined the main topics I hope to cover (as on the course web page), and for each one a key result that I hope to get to. Those results were

1. irreps of compact groups are determined by their characters
2. classification and construction of irreps of U(n) & GL_n(C)
3. Weyl character formula and Kostant multiplicity formula for GL_n, Gel'fand-Cetlin patterns, Young tableaux
4. hives compute tensor product multiplicities
5. the Borel-Weil theorem for GL(n)
6. the link between tensor products and sums of Hermitian matrices.

Then we discussed finite-dimensional complex representations. Isomorphisms, intertwiners, subreps. Decomposable vs. reducible. Unitary reps are direct sums of irreps. Reps of finite groups (or groups with left-invariant measures) are unitarizable.

Next time: characters and their orthonormality. Representation rings.

Spring quarter 2006: Representations of GL(n)

This quarter I'm teaching a topics-in-algebra graduate class, Representations of GL(n). The course web site is here.

Grades on the final exam

The answers to the final exam are up. The curve for the final is as follows:
55+ A
40-55 B
25-40 C
15-25 D
0-15 F

Solutions to those practice problems

1. Let A be a square matrix with A*A = Identity. Let M be a square matrix, such that AMA = M. Let v be an eigenvector of M with eigenvalue e.

a) Show that Av is one too.

ANSWER.
We want to show MAv = eAv.
We don't know much about MA, but we do about AMA:
AMAv = Mv = ev.
That's ev on the right, but we want eAv or Aev. So left multiply by A:
AAMAv = Aev = eAv.
Now we use A*A = identity to cancel the AA at the beginning.

b) Assuming that, show that v+Av, v-Av are too.

ANSWER. This is easier.
M(v+Av) = Mv + MAv = ev + eAv = e(v+Av)
Same thing with minuses.

2. Find the exponential of t times the matrix M

[2 0 3 9 0]
[0 2 1 6 0]
[0 0 2 0 0]
[0 0 0 2 0]
[0 0 0 0 3]

Hint: it would be easier if you subtracted 2 * Identity... how do you make use of that?

ANSWER.
exp(A+B) = exp(A)exp(B) if A and B commute. For example if A = 2t * Identity.
Breaking this up that way, and looking at exp(B) = 1 + B + B^2/2! + B^3/3! + B^4/4!

exp(Bt) = [please ignore the periods, only there to keep Blogger from collapsing the line]

[1 0 0 0 0] . [0 0 3 9 0] .. [0 0 0 0 0] ....... [0 0 0 0 0]
[0 1 0 0 0] . [0 0 1 6 0] .. [0 0 0 0 0] ....... [0 0 0 0 0]
[0 0 1 0 0] + [0 0 0 0 0]t + [0 0 0 0 0]t^2/2! + [0 0 0 0 0]t^3/3! + ...
[0 0 0 1 0] . [0 0 0 0 0] .. [0 0 0 0 0] ....... [0 0 0 0 0]
[0 0 0 0 1] . [0 0 0 0 1] .. [0 0 0 0 1] ....... [0 0 0 0 1]

Higher powers only contribute in the lower right corner, giving exactly
the exponential series for exp(t). So the total is

1	0	3t	9t	0
0	1	t	6t	0
0	0	0	1	0
0	0	0	0	exp(t)

Q. Solve the ODE system y' = My for arbitrary initial conditions.

ANSWER. y = exp(tM)c. So if c =
[f]
[g]
[h]
[j]
[k],

then exp(tM)y = exp(2t) times
[f + 3th + 9tj]
[g + th + 6tj]
[h]
[j]
[exp(t)k].

3. Let y' = f(t,y).

a) What is the general form of f, if this equation is separable and linear homogeneous?

ANSWER. If it's linear homogeneous, then f(t,y) = g(t)y. In which case it's
automatically separable.

b) What is the general form of f, if this equation is separable and linear but not necessarily homogeneous?

ANSWER. If it's linear inhomogeneous, then f(t,y) = g(t)y + h(t) = g * (y + h/g).
To be separable, that h(t)/g(t) should only depend on y, not on t. So it doesn't depend on y, nor on t; it must be some constant C. Hence f(t,y) = g(t) * (y+C).


4. Let c_0 = 0, c_{n+1} = c_n + 2n + 1. Find c_0,c_1,c_2,c_3,c_4,c_5 and guess a general formula for c_n. Then determine the radius of convergence of the power series \sum_n c_n x^n.

ANSWER.
c_0..5 = 0,1,4,9,16,25. By the way, one way to prove that c_n = n^2 (though you weren't asked to) is to think of the numbers being added on like this:

1

12 22

123 223 333

1234 2234 3334 4444

...

or if you weren't taking a test, you could look it up here.

Anyway, the ratio test or the root test tell you that the radius of convergence is 1.

5. Assume that
f(x) y dx + (x+y) dy = 0
is exact. Determine the possibilities for f, and solve this ODE. (You should have two constants in your answer: one because you don't know f precisely, and the other from solving the ODE.)

ANSWER. Oops, actually you do know f precisely; I was thinking of a slightly harder problem. Probably a good one for the final.

Anyway, exactness says partial/partial_y (f(x) y) = partial/partial_x (x+y),
or f(x) = 1.

Now we do the integrals to determine F(x,y) such that y dx + (x+y) dy = dF:

	integral_{t=0}^x P(t,0) dt	+	integral_{s=0}^y Q(x,s) ds
=	integral_{t=0}^x 0 dt	+	integral_{s=0}^y (x+s) ds
=	0	+	(xs + 1/2 s^2) from s=0 to y

= xy + 1/2 y^2.

So the solutions are given by xy + 1/2 y^2 = C.