403 – HW 4 – Algebraic graph theory

April 28, 2014

This set is due Thursday, May 15, at 11am.

1. (Norman Biggs, Algebraic Graph Theory, Proposition 2.3) Let \Gamma be a (finite, simple) graph with n vertices, and let A be its adjacency matrix. Suppose that the characteristic polynomial of A is {\rm char}_A(x)=x^n+c_1x^{n-1}+c_2x^{n-2}+\dots+c_n. Verify that:

  1. c_1=0.
  2. -c_2 is the number of edges in \Gamma.
  3. -c_3 is twice the number of triangles in \Gamma.

2.  (Chris Godsil, Gordon F. Royle, Algebraic Graph Theory, Theorem 8.5.1) Let G be a finite simple graph on n vertices that is k-regular, that is, such that each vertex has degree k. Suppose G has n vertices and A is its adjacency matrix.

  1. Verify that k is an eigenvalue of A.
  2. Let \lambda_2,\dots,\lambda_n be the other eigenvalues of A. Let \bar G denote the complementary graph to G: This graph has the same vertices, but two vertices are joined by an edge iff they are not joined by an edge in G. Let B be the adjacency matrix of \bar G. Show that there is a basis of \mathbb R^n consisting of vectors that are common eigenvectors of B and A, and that the eigenvalues of B are n-k-1,-1-\lambda_2,\dots,-1-\lambda_n.

403 – HW 3 – Computing eigenvalues

April 16, 2014

This set is due Thursday, May 8, at the beginning of lecture. (There will be another homework set, due the scheduled day of the final exam, Thursday May 15, at 11am, so I recommend you try to complete this set earlier than the scheduled deadline.)

You can work on your own, or in groups of up to three members. In case you cannot find anybody to work with, and do not know how to program, let me know as soon as possible, and we will find an alternative. As usual, you can still collaborate with others not in your group, but please make sure to give appropriate credit and indicate clearly who you worked with, what references you consulted, etc.

1. Give an example of a matrix for which the power method fails. (Include a proof that this is indeed the case.)

2. Write a program that, given a square matrix A (diagonalizable and) with real entries, computes approximations to its eigenvalues using the QR-algorithm. Ideally, the user can decide the dimensions of the matrix and, more importantly, the (tolerance) error within which the approximations will be found. Apply your method to a 10\times 10 symmetric matrix, and check the number of iterations the process requires, as a function of the tolerance error.

Please turn in: The code (best if you email it to me), a write up explaining what your code does, the matrix you applied the method to, and the result. To help verify that your algorithm is proceeding correctly, at each step of the iteration have your program indicate clearly what the matrices Q and R are, and what the new (output) matrix is.

Please make the algorithm as explicit as possible. Meaning: Do not use shortcuts already built into the software; most CASs already have functions that perform the Gram-Schmidt process to a given set of vectors, or functions that give the QR decomposition of a matrix. Instead, I want you to program these subroutines as well.

The programming language you use is up to you. Maple, Mathlab, Sage are standard choices, but if you prefer a different language, it should be fine. Let me know, just in case.

3. Do the same, but now for Francis’s algorithm. Apply it to the same 10\times 10 matrix. (Here there are more matrices and some vectors the algorithm may want to display along the way. For instance, whenever a matrix is put into upper Heissenberg form, indicate what the reflectors used along the way are.)


314 – C+C=[0,2]

April 1, 2014

Recall that the Cantor set C is defined as the intersection \bigcap_n C_n where

C_0=[0,1]

and C_{n+1} is obtained by removing from each closed interval that makes up C_n its open middle third, so

C_1=[0,1/3]\cup[2/3,1],

C_2=[0,1/9]\cup[2/9,1/3]\cup[2/3,7/9]\cup[8/9,1],

etc. Each C_n is the union of 2^n closed intervals, each of length 1/3^n.

Let’s prove that C+C=\{x+y\mid x,y\in C\} is the interval {}[0,2]. (Cf. Abbott, Understanding analysis, Exercise 3.3.6.)

1.

The usual proof consists in showing inductively that C_n+C_n=[0,2] for all n. This is easy: Note first that

\displaystyle C_{n+1}=\frac13 C_n+\left(\frac13C_n+\frac23\right),

where

\displaystyle \frac13C_n=\left\{\frac x3\mid x\in C_n\right\}

and

\displaystyle\frac13 C_n+\frac23=\left\{\frac{x+2}3\mid x\in C_n\right\}.

This equality is verified by induction. Using this, we can use induction again to verify that, indeed, C_n+C_n=[0,2] for all n.

We clearly have that C+C\subseteq \bigcap_n C_n+C_n=[0,2]. To prove the converse, for each z\in[0,2] and each n, pick x_n,y_n\in C_n such that x_n+y_n=z_n. The sequence of x_n is bounded, so it has a convergent subsequence x_{n_k}. The corresponding subsequence y_{n_k} has itself a convergent subsequence y_{n_{k_m}}. One argues that their limit values x,y belong to C, because they belong to each C_n, since these sets are nested and closed. Finally, it follows immediately that x+y=z as well.

2.

A very elegant different argument is obtained by using an alternative characterization of C: Note that each x\in[0,1] can be written in base three as

\displaystyle x=0.x_1x_2x_3\dots=\sum_{n=1}^\infty\frac {x_n}{3^n}

where each x_i is 0, 1, or 2. By induction, one easily verifies that x\in C_n iff it admits such an expansion with x_n\ne1. It follows that x\in C iff it admits an expansion where no x_i is 1.

Given z\in[0,2], we have z/2\in[0,1], so we can write z/2=a+b where the ternary expansion of a has only 0s and 2s (so a\in C), and the expansion of b has only 0s and 1s: If

z/2=0.t_1t_2\dots,

we can set a=0.a_1a_2\dots where a_i=0 unless t_i=2, in which case a_i=2 as well, and similarly b=0.b_1b_2\dots where b_i=0 unless t_i=1, in which case b_i=1 as well.

We then have that z=2(a+b)=(a+2b)+a, and both a+2b and a are in C.

This construction has the further advantage of making clear that the typical z admits continuum many (=|\mathbb R|) representations as sum of two members of C: If we can split b=c+d (where the expansions of c,d only have 0s and 1s), we can set

z=(a+2c)+(a+2d).

This gives us as many representations as subsets of \{n\in\mathbb N\mid b_n=1\}.

3.

The related problem of describing C\cdot C appears to be much more complicated. See here and here.


BEST 2014, First Announcement

March 26, 2014

BOISE EXTRAVAGANZA IN SET THEORY (BEST)
http://diamond.boisestate.edu/~best/
June 18 – 20, 2014
University of California, Riverside

The 21-st meeting of BEST will be hosted at University of California, Riverside, as a symposium of the 95th annual meeting of the American Association for the Advancement of Science – Pacific Division (AAAS-PD). Contributed and invited talks at BEST will be held on Wednesday, Thursday and Friday.

In addition to four invited speakers, the conference program has reserved speaking slots for students, post docs and pre-tenure tenure track faculty. NSF supported funding to assist up to eight student speakers, four post-doc speakers and two pre-tenure tenure track faculty speakers is available. For details on applying to the BEST program committee for these, please visit the conference website. In addition, the AAAS-PD provides up to $150 in travel funding for students. Please see the BEST conference website for more details on these also. There are a number of deadlines associated with applications for a travel grant.

The four invited speakers at BEST 2014 are:

Dr. Joel Hamkins, CUNY Graduate Center
Dr. Dima Sinapova, University of Illinois at Chicago
Dr. Nam Trang, Carnegie Mellon University
Dr. Andrew Marks, Caltech University

Special features of BEST 2014 include:

The BEST 2014 conference marks the end of three weeks of intensive set theory meetings in California. In addition to the BEST symposium there are several other symposia and workshops of interest offered at the AAAS-PD annual meeting. On Thursday, June 19, the AAAS-PD hosts a banquet at which awards of excellence are given to student speakers selected by a panel of judges. On Friday, June 20, Dr. Joel Hamkins will deliver a plenary lecture from 12:15 to 1:15 about our field to the general audience of the AAAS-PD annual meeting.

Important deadlines:

DEADLINE 1: REGISTRATION: Please consult http://diamond.boisestate.edu/~best/ for registration costs and deadlines. Registration fees depend on date of registration. We kindly request that tenure track mathematicians planning to participate in BEST 2014 consider acting as judges for the student presentations. The registration form has a place where willingness to act as a judge can be indicated. There are also a number of excursions available that can be indicated on the registration form. Also consider attending the award banquet in support of our student speakers – meal choices are available on the registration form.

DEADLINE 2: ABSTRACTS: Atlas Conferences, Inc. is providing abstract services for BEST 2014. Abstracts submitted by the deadline will appear in the proceedings of the annual conference of the AAAS-PD. The deadline for submitting an abstract is APRIL 16. The url for the abstract submission is available at the BEST 2014 website.

Organized by Liljana Babinkostova, Andres Caicedo, Sam Coskey and Marion Scheepers.

For any questions, please contact an organizer or e-mail best@math.boisestate.edu


403 – Some references on Geršgorin’s theorem

March 24, 2014

I am posting here some references on Geršgorin’s theorem.

(Marsli and Hall have published recently a series of papers further exploring extensions of the theorem. Varga’s book is highly recommended.) If you want to practice some of the topics we have been covered, work through some of the exercises in the posted chapter, and turn them in for some extra credit, by April 8.

Related, though of a different nature, is the following. Geršgorin’s theorem is discussed in section 6:

Here I briefly review the result:

Theorem (Geršgorin, 1931). Let A=(a_{ij})_{i,j=1}^n be a complex-valued matrix. For 1\le i\le n let r_i(A)=\sum_{j\ne i}|a_{ij}|. If \lambda is an eigenvalue of A, then {}|\lambda-a_{ii}|\le r_i(A) for at least one i.

To prove this, let x be an eigenvector of A with eigenvalue \lambda, say x=(x_1,\dots,x_n)^T, and let i be such that |x_i|=\max\{|x_k|\mid 1\le k\le n\}. Since Ax=\lambda x, we have that \sum_j a_{ij}x_j=\lambda x_i, so (\lambda-a_{ii})x_i=\sum_{j\ne i}a_{ij}x_j. From this, the triangle inequality gives us that

|\lambda-a_{ii}||x_i|\le\sum_{j\ne i}|a_ij||x_j|\le\sum_{j\ne i}|a_{ij}||x_i|,

and the result follows since x_i\ne0.


314 – Suggested reading

March 19, 2014

This is a (somewhat expanding) list of suggested additional references. Some cover topics discussed in lecture, others add new material that complements what we covered. The level varies: Some are basic, others are more advanced and portions of them may require knowledge beyond this course.

For the group project: Choose one of these articles. Inform me by email, to make sure it has not already been chosen. Feel free to suggest different papers or other topics, I’ll see whether we can use them.

Write (type) a note on the topic discussed in the paper you have chosen, include details of some of the results discussed there. Make sure the proofs you include contain all needed details (typically proofs in articles are more sketchy than what we are aiming for through the course), and that the write up is your own, even if modeled on the arguments in the paper. Include references as usual. Turn this in by Thursday, May 15, at 10:30 am. Feel free to turn it in earlier, of course. I encourage you, as you work through the paper, to share your progress with me during office hours, so I can give you some feedback before your final submission.

Groups:

  • Booker Ahl, Dorthee Berman, and Stephanie Potter: Russ’s translation of Bolzano’s paper.
  • Tim Deidrick, Justin Durflinger, and Ariel Farber: Calkin-Wilf and Malter-Schleicher-Zagier on enumerating the rationals.
  • Carrie Smith, and Jordan Wilson: Fleron’s note on the history of the Cantor set and function.
  • Caleb Richards, and Chris VanDerhoff: McShane’s paper on the Henstock–Kurzweil integral.
  • Kenny Ballou, Sarah Devore, and Luke Warren: Nitecki’s paper on subseries.
  • Farrghun Abdulrahim, and Kenneth Coiteux: Burns and Hasselblatt’s paper on Sharkovsky’s theorem.
  • Tyler Clark: Niven’s paper on formal power series.
  • Joe Magdaleno, and Piper Gutridge: Bruckner and Bruckner-Leonard  on derivatives.

314 – On √n

March 10, 2014

Let’s prove that if n\in\mathbb N, then either \sqrt n is an integer, or else it is irrational. (Cf. Abbott, Understanding analysis, Exercise 1.2.1.) There are many proofs of this fact. I present three.

1.

The standard proof of this fact uses the prime factorization of n: There is a unique way of writing n as \prod_{i=1}^k p_i^{\alpha_i}, where the p_i are distinct primes numbers, and the \alpha_i are positive integers (the number n=1 corresponds to the empty product, but since 1 is a square, we may as well assume in what follows that n>1).

We show that if \sqrt{n} is rational, then in fact each \alpha_i is even, so \sqrt n is actually an integer. Write \sqrt n=a/b where a,b are integers that we may assume relatively prime. This gives us that b^2n=a.

Consider any of the primes p=p_i in the factorization of n. Let p^\beta and p^\gamma be the largest powers of p that divide a and b, respectively, say a=p^\beta c and b=p^\gamma d where p does not divide either of c and d. Similarly, write n=p^{\alpha}m, where p does not divide m (\alpha is what we called \alpha_i above). We have

p^{2\gamma} p^{\alpha}d^2m=p^{2\beta}c^2.

The point is that since p is prime, it does not divide c^2 or d^2m: If q is a prime and q divides a  product hj (where h,j are integers), then q divides h or it divides j.

This means that either \alpha is even (as we wanted to show), so that 2\gamma+\alpha=2\beta, or else (upon dividing both sides of the displayed equation by the smaller of p^{2\gamma+\alpha} and p^{2\beta}), p divides one of the two sides of the resulting equation, but not the other, a contradiction.

2.

The above is the standard proof, but there are other arguments that do not rely on prime factorizations. One I particularly like uses Bézout theorem: If c is the greatest common divisor of the positive integers a and b, then there are integers x,y such that ax+by=c.

Suppose \sqrt n=a/b. We may assume that a,b are relatively prime, and therefore there are integers x,y such that ax+by=1. The key observation is that \sqrt n=n/\sqrt n=nb/a. This, coupled with elementary algebra, verifies that

\displaystyle \sqrt n= \frac ab=\frac{nb}a=\frac {ay+nbx}{by+ax},

but the latter is an integer, and we are done.

3.

Another nice way of arguing, again by contradiction, is as follows: Suppose that \sqrt n is not an integer, but it is rational. There is a unique integer m with m<\sqrt n<m+1, so 0<\sqrt n -m<1. Let a be the least positive integer such that (\sqrt n-m)a is an integer, call it b. Note that 0<b<a, which gives us a contradiction if ({\sqrt n}-m)b is again an integer. But this can be verified by a direct computation:

(\sqrt n-m)b=(\sqrt n-m)^2a=(n+m^2)a-2m\sqrt n a =(n-m^2)a-2m(\sqrt n-m)a.

4.

As a closing remark, the three arguments above generalize to show that \root k\of n is either an integer or irrational, for all positive integers n,k. Similarly, if \displaystyle\root k\of {\frac ab} is rational for some positive integers a,b, then both a,b are kth powers. (It is a useful exercise to see precisely how these generalizations go.)

Pdf source.


Follow

Get every new post delivered to your Inbox.

Join 44 other followers