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

3 Comments | 403/503: Linear Algebra II | Permalink
Posted by andrescaicedo

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

1 Comment | 403/503: Linear Algebra II | Permalink
Posted by andrescaicedo

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.

1 Comment | 314: Foundations of Analysis | Permalink
Posted by andrescaicedo