notes for 10.01.02 (courtesy of Amanda Beeson) I. Promises: -Amanda will ask about UROP funding from MIT -Alice will look into VIGRE funding from Harvard -Jim will check on citizen v. resident question -Gabriel will still look into new room for the hour of 3-4 -various people will email Amanda (beeson@mit.edu) about html sites II. Bureaucracy: 1. Outside funding: a. Brandeis doesn't have any money for us. b. Amanda will ask about UROP funding from MIT c. Alice will look into VIGRE funding from Harvard 2. Bilinear Forum -- front.math.ucdavis.edu/ ../math.CO xxx.lanl.gov/ (interfaces to large databases of pre-printed math papers) 3. Web pages a. reminder that you can just copy html from other pages (going to the view menu and choose source to see a page's html source code b. web sources for learning html/making pages: -www.htmlgoodies.com :q ultra12 [O]% nmail reach "minutes for Tuesday" ultra12 [O]% cat ~/deleted/reach.tmp notes for 10.01.02 (courtesy of Amanda Beeson) I. Promises: -Amanda will ask about UROP funding from MIT -Alice will look into VIGRE funding from Harvard -Jim will check on citizen v. resident question -Gabriel will still look into new room for the hour of 3-4 -various people will email Amanda (beeson@mit.edu) about html sites II. Bureaucracy: 1. Outside funding: a. Brandeis doesn't have any money for us. b. Amanda will ask about UROP funding from MIT c. Alice will look into VIGRE funding from Harvard 2. Bilinear Forum -- front.math.ucdavis.edu/ ../math.CO xxx.lanl.gov/ (interfaces to large databases of pre-printed math papers) 3. Web pages a. reminder that you can just copy html from other pages (going to the view menu and choose source to see a page's html source code b. web sources for learning html/making pages: -www.htmlgoodies.com -math.harvard.edu: local-->overview-->html c. can make a private page if you want, but don't have to 4. Jim collected some overseas students' papers (and promised to check on citizen v. resident question) 5. We are still undecided about meeting at 3:15 instead of 3 III. The good stuff: 1. The Cayley-Hamilton Theorem: given an nxn matrix A whose characteristic polynomial is P(t)=det(A-tI), P(A) = 0, where A interpreted as a linear operator. a.example#1: P(t) = t^2 - 3t + 2 => (by C-H thrm) P(A) = A^2 -3A + 2 = 0 what this says is that (A^2 -3A + 2)v = 0 for all v in R^n 2. Now, we can encode the tilings/matchings we've been looking at in the following way: (we looked at the encoding of the 2xn case, but then followed the 1xn case through) a. 2xn: Each vertex is labeled with a symbol E, L, R, B, T (empty, left, right, bottom, top) depending on the edge leaving it. this gives a 2xn array of these symbols that encodes that specific matching. b. 1xn: Now our code alphabet only contains E, L, and R. The possible one-step transitions are: E-->E, E-->L, L-->R, R-->E, and R-->L. Construct the following matrix where entry in for (A,B) is the number of ways to get from A to B in one step. (A and B are some symbols from among the encoding alphabet.) TO: E L R so A = 1 1 0 E 1 1 0 0 0 1 FROM: L 0 0 1 1 1 0 R 1 1 0 c. The possible begin/end states give us the entries we are interested in. In this case, those are: (E,E), (L,E), (E,R), and (L,R). We can see easily that the sum over these entries in A give the total number of matchings of the 1X2 case. d. We can see then that these entries in higher powers of A will give us the total number of ways to get from the given start position to the given end position. Hence, the sum over these entries is the total number of matchings. e. Cayley-Hamilton is helpful then because it given a recursion formula for the powers of A. Namely, if P(t) = a_n t^k + ... + a_1 t + a_0, then a_n A^(n+k-1) + ... + a_1 A^(n+1) + a_0 A^n = 0. f. This gives us a recursion for each individual entry and hence for the sum of the important entries (which gives the number of matchings). g. It also provides insight into why we always get a rational function describing the behavior of objects we can describe with sequences of symbols as we did in the "encoding" above. h. for more info on this: -Math 192 notes -Concrete Math - Knuth, Graham and Patashnik -Generating Functionology - Wilf (linked off reach site) 3. There are programs that will find generating functions for you so don't spend too much time focusing on this type of "one dimensional combinatorics." A good programming project would be to better these programs - make them more efficient - make them more adaptable (e.g. to non-constant height strips, mutilated strips) 4. Generating functions for cases we've seen: a. 1xn 1/(1 - x - x^2) for irreducibles: x + x^2 b. 2xn (1-x)/(1-3x-x^2+x^3) for irreducibles: (2x + x^2-x^3)/(1-x) c. 3xn (-1+x+4x^2-x^3-x^4)/(x^6-10x^4+14x^2+4x-1) for irreducibles: (whatever)/(1-x-4x^2+x^3+x^4) 5. 1xn run in reverse: ....-8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8.... can't run irreducible rel'ns backwards so they're not that interesting to us (perhaps they are of use in extending the capabilities of the generating function program though?) 6. OBSERVATIONS: a. coeff. of most significant power of x and constant term both = +/- 1 in denom. b. deg(denominator) > deg(numerator) (=> can extend backwards...) c. sign(coeff. of most significant power of x) = sign(constant term) <=> n even (Gabriel) 7. observation (a) is important because it means we will always get integers, even when extending backwards => combinatorially interesting! 8. QUESTIONS: a. Is it true that for fixed k, the denominator of the generating function for tilings of kxn strips is monic? b. if so, why? III. In the computer lab: 1. went over viewing html source code 2. String Tiling software: a. went through monomer-dimer program and how to input desired tiles dominoes <--> "dimers" <--> non-empty matchings single blocks <--> "monomers <--> empty matching on a dot b. get a generating function in w and t. the coeffient of t^i w^j tells you the number of matchings of a length i strip with j pieces/tiles. c. set w=1 to get the generating function that we were interested in (not paying attention to how many tiles got used) 3.general computer notes: a. changing size in netscape: view --> text size --> largest b. changing size of font in secure CRT: options --> session options --> appearance --> font --> font style IV. Assignment: skim/start reading front.math.ucdavis.edu/math.CO/0104011 note the method of proof using a combinatorial model to guide and inform an algebraic proof.