## 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 $0$s and $2$s (so $a\in C$), and the expansion of $b$ has only $0$s and $1$s: 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 $0$s and $1$s), 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.