## Exercise 1.1

#### (tricky) Find a combinatorial proof of Corollary 1.6, i.e., the number of closed walks of length $\ell$ in $K_p$ from some vertex to itself is given by $$\dfrac{1}{p}((p-1)^\ell+(p-1)(-1)^\ell)$$

**Solution.**

Define $a_n=$ number of closed walks of length $n$ in $K_p$ from vertex $v$ to itself.

因為

\begin{split}
第 \ n \ 次在 \ v \ 的方法數 \ &= \ 第 \ n-1 \ 次不在 \ v \ 的方法數 \times1\\\\ &= \ 前 \ n-1 \ 次的所有方法數 \ - \ 第 \ n-1 \ 次在 \ v \ 的方法數\\\\ &= (p-1)^{n-1}-a_{n-1}
\end{split}

So $a_n=(p-1)^{n-1}-a_{n-1}$ with $\ a_1=0,\ a_2=p-1$ . Thus we have
$$\tag{1} a_n+a_{n-1}=(p-1)^{n-1}$$ which is a linear **nonhomogeneous** recurrence relations with constant coefficients.

Although we can solve (1), but we try to make it easier (**homogeneous**).

By replacing $n$ by $n-1$ in (1), we get

$$a_{n-1}+a_{n-2}=(p-1)^{n-2}$$multiply $(p-1)$ on both sides to get
\begin{equation}
\tag{2} (p-1)a_{n-1}+(p-1)a_{n-2}=(p-1)^{n-1}
\end{equation}

(1) $-$ (2) ：$$\tag{3} a_n+(2-p)a_{n-1}+(1-p)a_{n-2}=0$$ which is a linear **homogeneous** recurrence relations with constant coefficients.

Solve the characteristic equation of (3), we have $$a_n=A(-1)^n+B(p-1)^n$$

Using the initial value $\ a_1=0,\ a_2=p-1$ ,we derive $A=\dfrac{p-1}{p}, \ B=\dfrac{1}{p}$ . Hence, $$a_n=\dfrac{p-1}{p}(-1)^n+\dfrac{1}{p}(p-1)^n=\dfrac{1}{p}((p-1)^n+(p-1)(-1)^n)$$

---
## Exercise 9.3

#### Let $p \geq 5$ and let $G_p$ be the graph on the vertex set $\mathbb{Z}_p$ with edges $\{i, i + 1\}$ and $\{i, i + 2\}$, for $i \in \mathbb{Z}_p$. Thus $G_p$ has $2p$ edges. Show that $\kappa(G_p) = p F_p^2$, where $F_p$ is a Fibonacci number ($F_1 = F_2 = 1, F_p = F_{p-1} + F_{p-2}$ for $p \geq 3$).

**Solution.**

* $G_8$、$G_9$

Consider the laplacian matrix $L=L(G_p)$, let $L_0$ denote $L$ with the last row and column removed. We want to use the Matrix-Tree Thorem, i.e., $\det L_0=\kappa(G_p)$.

Take $p=8$ for example,
$$L=\left(\begin{matrix}
4 & -1 & -1 & 0 & 0 & 0 & -1 & -1 \\
-1 & 4 & -1 & -1 & 0 & 0 & 0 & -1 \\
-1 & -1 & 4 & -1 & -1 & 0 & 0 & 0 \\
0 & -1 & -1 & 4 & -1 & -1 & 0 & 0 \\
0 & 0 & -1 & -1 & 4 & -1 & -1 & 0 \\
0 & 0 & 0 & -1 & -1 & 4 & -1 & -1 \\
-1 & 0 & 0 & 0 & -1 & -1 & 4 & -1 \\
-1 & -1 & 0 & 0 & 0 & -1 & -1 & 4
\end{matrix}\right)$$

[It's hard to see the relation between $\det L_0$ and Fibonacci number.](https://drive.google.com/file/d/1R4M5syFheZDn71LUVFWjomGcTC9OjT8o/view?usp=sharing)

* [D. J. Kleitman and B. Golden, Counting trees in a certain class of graphs, *Amer. Math. Monthly* **82** (1975), 40–44.](https://drive.google.com/file/d/1cUWdA71YG1x0RtqI_3x8-tUHNIrr7N_b/view?usp=sharing)

We first compute the number of trees in a simpler graph, namely that for which, on the same vertices, we allow only edges between pairs whose differences (not mod $n$) are one or two.

* Such a graph for $n = 10$.

We will refer above to graphs defined by this property as "strip graphs." We show that the number, $F(n)$, of spanning trees in a strip graph on $n$ vertices is the $(2n - 2)$nd Fibonacci number, $f_{2n-2}$. We then show that the answer to the "strip graph" question supplies an answer to our original question.

**Lemma 1：$F(n) = f_{2n-2}$**

*proof.* Let $G(n)$ be the number of spanning trees in the $n$ vertex "strip graph" that contain the edge $(n-1, n)$. Since every tree must connect the vertex $(n)$ to the rest of the graph, if a tree fails to contain the edge $(n-1, n)$ it must contain the edge $(n-2, n)$ and must contain a tree on the vertices other than $n$. Thus we have
$$F(n) = G(n) + F(n-1)$$

where the first term counts the trees containing $(n-1, n)$ and the second counts the rest.

A tree containing the edge $(n-1, n)$ that fails to contain $(n-2, n)$ will likewise be a tree on the $n-1$ vertices other than $n$. On the other hand, a tree containing both $(n-1, n)$ and $(n-2, n)$ will look, as far as the first $n-1$ vertices are concerned, just like a tree containing the edge $(n-2, n-1)$. We therefore have

$$G(n) = F(n-1) + G(n-1)$$

where the first term counts trees not containing $(n-2, n)$ and the second trees containing it.

The $F$'s and $G$'s together arranged in the sequence $$\cdots, F(n), G(n+1), F(n+1), G(n+2), F(n+2), G(n+3), \cdots$$ therefore obey the well-known Fibonacci recursion, $f_n = f_{n-1} + f_{n-2}$, and by examining the small $n$ cases ($F(2) = G(2) = 1$) we can deduce that $F(n)$ is the $(2n-2)$nd Fibonacci number $f_{2n-2}$, while $G(n)$ is the $(2n-3)$rd. $\square$

We now relate this result, in the even $n$ case, to the desired tree counting for our original class of graphs. We show that for even $n$, the number of spanning trees in our original $n$ vertex graph, is given by $$n \left(F(n) + F(n-2) + \cdots + F(2) \right)$$

**Lemma 2.** For even $n$, $\kappa(G_n) = n \left(F(n) + F(n-2) + \cdots + F(2) \right) = n \left( f_2 + f_6 + \cdots + f_{2n-2} \right)$

*proof. (sketch)*

Given any tree $T$ there must be a path in the plane from the interior of the diagram (A) to the outside region (B) which intersects no edge of $T$. Consider any two such A-B paths. If we reverse one and join their ends at (A) and also their ends at (B), we obtain a circuit in the plane which does not intersect any edge of the tree.

* Any two such A-B paths for any tree $T$ must cross exactly the same edges an **odd** number of times. Therefore, each tree $T$ is uniquely associated with the set of edges that such paths cross an odd number of times.

* Let us call an edge which bounds A an interior edge (red), an edge which bounds B an exterior edge (black), and all other edges straight edges (blue).


* Now at interior to exterior path must cross
(1) some interior edge
(2) a sequence of an odd number, $(2k + 1)$, of successive straight edges
(3) an exterior edge

* For each interior-exterior path characterized by parameter $k$, there will thus be $F(n - 2k)$ associated trees

* We therefore have $nF(n - 2k)$ trees for each value of $k$, and the number of trees in the entire graph is therefore the sum over all $k$ of this quantity.

Hence, for even $n$, the desired number of spanning trees $\kappa(G_n)$ is
\begin{split}
\displaystyle \sum_{k=0}^{(n/2)-1}nF(n - 2k)&=n(F(n)+F(n-2
)+\cdots+F(2))\\&=n(f_2 + f_6 + \cdots + f_{2n-2}) \quad \square
\end{split}

It remains to prove $f_2 + f_6 + \cdots + f_{2n-2}=f_n^2$ for even $n$.

*proof.* When $n=2$, $f_2=1=f_2^2$. Suppose that for $n$ even, we have $$f_2 + f_6 + \cdots + f_{2(n-2)-2}=f_2 + f_6 + \cdots + f_{2n-6}=f_{n-2}^2$$ We need to show that $f_2 + f_6 + \cdots + f_{2n-2}=f_n^2$. By the Fibonacci formula $$f_{n+m}=f_{n-1}f_m+f_nf_{m+1}$$ we have
\begin{split}
f_{2n}&=f_{n-1}f_n+f_nf_{n+1}\\\\
&=f_n(f_{n-1}+f_{n+1})\\\\
&=(f_{n+1}-f_{n-1})(f_{n+1}+f_{n-1})\\\\
&=f_{n+1}^2-f_{n-1}^2
\end{split}Hence $f_2 + f_6 + \cdots + f_{2n-2}=f_{n-2}^2+f_{n}^2-f_{n-2}^2=f_n^2$. $\quad \square$

As for the case $n$ is odd, we would have $\kappa(G_n)=n(1+f_4 + f_8 + \cdots + f_{2n-6}+f_{2n-2})$.
By induction again, we derive $1+f_4 + f_8 + \cdots + f_{2n-6}+f_{2n-2}=f_n^2$, i.e., $$\kappa(G_n)=nf_n^2 \quad \square$$

---
## Cayley graph

### Exercise 2.5

#### This problem is devoted to the graph $Z_n$ with vertex set $\mathbb{Z}_n$ (the cyclic group of order $n$, with elements $0, 1,\cdots, n-1$ under the operation of addition modulo $n$) and edges consisting of all pairs $\{i, i+1 \}$ (with $i + 1$ computed in $\mathbb{Z}_n$ , so $(n-1)+1=0$). The graph $Z_n$ is called an $n$-*cycle*. We will develop properties of its adjacency matrix analogously to what was done for the $n$-cube $C_n$. It will be necessary to work over the complex numbers $\mathbb{C}$. Recall that there are exactly $n$ complex numbers $z$ (called $n$th roots of unity) satisfying $z^n=1$. They are given by $\zeta^0=1, \zeta^1=\zeta, \zeta^2, \cdots, \zeta^{n-1}$ , where $\zeta=e^{2\pi i/n}$.

---

**Definition**

Let $G$ be a group and $S$ be a inverse-closed generating set of $G$. Then the Cayley graph of $G$ with respect to $S$, denoted by $\text{Cay}(G, S)$, is constructed as follows.
* $V(\text{Cay}(G, S))=G$
* $E(\text{Cay}(G, S))=\{ \{ g, h \}:gs=h \text{ for some } s\in S \}$

> There are different ways to define Cayley graphs.
> * *Directed* Cayley graphs: these do not require $S$ to be inverse-closed.
> * *Colored, directed* Cayley graphs: edges $(g, h)$ are colored/labeled based on which $s \in S$ satisfies $gs=h$.

**Examples**
* $G=\mathbb{Z}_6, S=\{ 1, 2, 3, 4, 5 \}$：complete graph $K_6$


* $G=\mathbb{Z}_2^3, S=\{ (1, 0, 0), (0, 1, 0), (0, 0, 1) \}$：$n$-cube $C_3$


* $G=\mathbb{Z}_8, S=\{ 1, -1\}=\{ 1, 7\}$：$n$-cycle $Z_8$


* $G=A_5, S=\{ (12345), (12345)^{-1}, (23)(45), ((23)(45))^{-1}\}=\{ (12345), (15432), (23)(45)\}$：Buckyball


$$ $$

* [Fitzgerald, C. A. I. L. E. Y. (2020). Cayley Graphs and Representation Theory. accessed in June.](https://drive.google.com/file/d/1Nz8XGwy2Ql77szZyuqgqFdG0dr1Sj3LJ/view?usp=sharing)

### Establishing a vector space

**Definition**
Let $S$ be a finite set. Define the complex vector space $L^2(S)$ by $$L^2(S) = \{ f : S \to \mathbb{C} \}$$ Let $f, g \in L^2(S)$ and $\alpha \in \mathbb{C}$. Addition in $L^2(S)$ is given by $(f + g)(x) = f(x) + g(x)$ and scalar multiplication in $L^2(S)$ is given by $(\alpha f)(x) = \alpha f(x)$.

Standard inner product and norm are given by
$$
\langle f, g \rangle = \sum_{x \in S} f(x)\overline{g(x)} \quad \text{and} \quad \| f \| = \sqrt{\langle f, f \rangle}
$$ We now use this definition to define the standard basis for $L^2(S)$. Consider the finite set $S = \{x_1, x_2, \ldots, x_n\}$. Let $\Omega = \{\omega_{x_1}, \omega_{x_2}, \ldots, \omega_{x_n}\} \subset L^2(S)$, where $\omega_{x_i}(x_j) = 1$ if $i = j$ and $\omega_{x_i}(x_j) = 0$ if $i \ne j$.

If $f \in L^2(S)$, we have
$$
f(x) = f(x_1) \omega_{x_1}(x) + \cdots + f(x_n) \omega_{x_n}(x),
$$ thus $\Omega$ spans the vector space $L^2(S)$. This, accompanied with the observation that $\omega_{x_i}$ are mutually orthogonal and therefore linearly independent, yields that $\Omega$ is a basis for $L^2(S)$. We call this the standard basis for $L^2(S)$, and we can see that the dimension of $L^2(S)$ as a vector space over $\mathbb{C}$ is $n$.

### Defining the adjacency operator

Suppose we have a graph $X$ and ordered vertex set $V$, as before, with $A$ being the adjacency matrix of $X$. Given $f \in L^2(V)$, we can can then multiply

$$Af =
\begin{pmatrix}
A_{1,1} & A_{1,2} & \cdots & A_{1,n} \\
A_{2,1} & A_{2,2} & \cdots & A_{2,n} \\
\vdots & \vdots & \ddots & \vdots \\
A_{n,1} & A_{n,2} & \cdots & A_{n,n}
\end{pmatrix}
\begin{pmatrix}
f(v_1) \\
f(v_2) \\
\vdots \\
f(v_n)
\end{pmatrix}=
\begin{pmatrix}
\sum_{j=1}^n A_{1,j} f(v_j) \\
\sum_{j=1}^n A_{2,j} f(v_j) \\
\vdots \\
\sum_{j=1}^n A_{n,j} f(v_j)
\end{pmatrix}
$$

In this way, we can think of $A$ as a linear transformation from $L^2(V)$ to itself, given by the equation$$(Af)(v) = \sum_{w \in V} A_{v,w} f(w)$$ $A$ defined in this manner is the *adjacency operator* of $X$.

When looking at how adjacency operators act with regard to Cayley graphs of the form $X = \text{Cay}(G, \Gamma)$, a simple formula arises, which describes the action of an operator $A$ on a function $f \in L^2(G)$. The action is given by
$$
(Af)(x) = \sum_{\gamma \in \Gamma} f(x\gamma)
$$

**Example**
Consider the cycle graph $Z_4$. Fix a cyclical ordering of the vertices as $0, 1, 2, 3$. Define the function $f : V(Z_4) \to \mathbb{C}$ by
$$
f(v) =
\begin{cases}
-1, & \text{if } v = 0 \text{ or } v = 2 \\
1, & \text{if } v = 1 \text{ or } v = 3
\end{cases}
$$ We may think of the $f$ as vector $(f(0), f(1), f(2), f(3))^t = (-1, 1, -1, 1)^t$. If $A$ is the adjacency matrix associated with this ordering, then
$$
A f = \begin{pmatrix}
0 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & 1 & 0
\end{pmatrix}
\begin{pmatrix}
-1 \\
1 \\
-1 \\
1
\end{pmatrix}=
\begin{pmatrix}
2 \\
-2 \\
2 \\
-2
\end{pmatrix}
= -2 f
$$Thus, $f$ is an eigenfunction of $A$ associated with the eigenvalue $-2$.

If we see the cycle graph $Z_4$ as $\text{Cay}(\mathbb{Z}_4, \{ 1, 3\})$, then $$(Af)(x) = \sum_{\gamma \in \{1, 3\}} f(x\gamma)=f(x+1)+f(x+3)=-2f(x)$$

### Finding Eigenvalues of Cayley Graphs

It's about Representation Theory...

Let $G$ be a finite group and $\Gamma$ a subset of $G$ such that $g\Gamma g^{-1} = \{g\gamma g^{-1} \mid \gamma \in \Gamma\} = \Gamma$ for all $g \in G$, that is, where $\Gamma$ is the union of conjugacy classes. Let $X = \text{Cay}(G, \Gamma)$ and $A$ be the adjacency operator of $X$.

As before, let $\rho_1, \ldots, \rho_k$ be the complete set of inequivalent irreps of $G$. Let $\chi_i$ be the character of $\rho_i$ and $d_i$ the dimension of $\rho_i$. Then the eigenvalues of the adjacency operator $A$ are given by
$$
\mu_i = \frac{1}{d_i} \sum_{\gamma \in \Gamma} \chi_i(\gamma), \quad i = 1, \ldots, r,
$$where each eigenvalue $\mu_i$ occurs with multiplicity $d_i^2$.