6/20 meeting
===

1.13
(G is simple)

Let $A = A(G)$ be the adjacency matrix over $\mathbb{F}_2$ . Suppose all entries of $A^l$ are odd (i.e. all entries of $A^l$ are $1$'s).
Then the kernel of $A^l$ is the set of vectors $y$ which have an even number of ones. Since $A$ is symmetric matrix, $\ker(A) = \ker(A^l)$.
Let $S$ be a subset of vertices such that $S$ has an even number of elements. Define a vector $x$ as follow:
$$
x= \sum_{v_i \in S} e_i
$$,where $e_i$ is a vector that the i-th element of $e_i$ is 1 and the others are 0. Then $x \in \ker(A)$.
For any $i$, $e_i^TAx=0$.Then,
$$
\sum_{v_j \in S} e_i^TAe_j = 0
\implies \sum_{v_j \in S} A_{ij} = 0
$$
This show that the number of edge between $v_i$ and $v_j$ in $S$ is even. Since $G$ is simple, $v_i$ is adjacent to even number of vertices in $S$.

---

2.4

>

Let $\Delta = \{\delta \mid\omega(\delta) = 2\}$. Similar to the proof of the lemma above, $[\Phi_\Delta] = A(G)$.

>

By the above theorem, the eigenvalues is given by:
$$
\lambda_u = \sum_{w \in \Delta} (-1)^{u \cdot w}
$$ for some $u \in \mathbb{Z}_2^n$

Fix $u \in \mathbb{Z}_2^n$. The number of $w \in \Delta$ such that $u\cdot w = 1$ is
$$\binom{\omega(u)}{1}\binom{n-\omega(u)}{1} = n\omega(u) - [\omega(u)]^2$$
The number of $w \in \Delta$ such that $u\cdot w = 0$ is
$$
\binom{n}{2} - n\omega(u) - [\omega(u)]^2
$$
Thus,
$$
\lambda_u = \binom{n}{2} - 2 n\omega(u) - 2[\omega(u)]^2
$$

---
9.4

**Lemma** Let $G$ is $d$-regular graph with $n$ verteices. Suppose eigenvalues of $G$ are $\lambda_1 = d, \lambda_2 \cdots , \lambda_n$.Then its complement graph $\overline{G}$ has eigenvalues $n-1-\lambda_1, -(\lambda_2+1),\cdots,-(\lambda_n+1)$.
> *Proof*
> $\overline{A} = A(\overline{G}) = J-I - A(G)$
> Let $v_1,v_2,\cdots v_n$ be the eigenvectors of $A(G)$, corresponding to $\lambda_1 = d, \lambda_2 \cdots , \lambda_n$.
If $i=1$, $v_1$ is a vector of all ones,then
$$
\begin{align}
\overline{A}v_1 &= (J-I - A(G))v_1\\
&= Jv_1 - v_1 - \lambda_1v_1 \\
&= (n-1-\lambda_1)v_1
\end{align}
$$
> Thus, $(n-1-\lambda_1)$ is an eigenvalue of $\overline{G}$
If $i>1$,
$$
\begin{align}
\overline{A}v_1 &= (J-I - A(G))v_i\\
&= Jv_i - v_i - \lambda_iv_i \\
\end{align}
$$
Since $A(G)$ is symmetric matrix, $v_i$ and $v_1$ are orthogonal.Hence, $Jv_i =0$.
$$
\begin{align}
\overline{A}v_1 &= (J-I - A(G))v_i\\
&= - v_i - \lambda_iv_i \\
&= -(\lambda_i+1)v_i
\end{align}
$$

>

Since $C_n$ is $n$-regular graph, $\overline{C_n}$ is also regular of $(2^n-1-n)$ degree.
The eigenvalues of $C_n$ are $n-2i$ with multiplicity $\binom{n}{i}$ for $0\leq i \leq n$, so the eigenvalues of $\overline{C_n}$ are $(2^n -1-n)$ with multiplicity $1$ and $-(n-2i+1)$ with multiplicity $\binom{n}{i}$ for $1\leq i \leq n$.
By the corollary,
$$
\begin{align}
\kappa(\overline{C_n}) &= \frac{1}{2^n}\prod_{i=1}^{n} (2^n -1-n +n-2i+1)^\binom{n}{i}\\
&=\frac{1}{2^n}\prod_{i=1}^{n} (2^n-2i)^\binom{n}{i}
\end{align}
$$

---
---

Finitely generated abelian group
===

**Theorem** (Fundamental theorem of finitely generated abelian groups)
Suppose $G$ is finitely generated abelian groups. Then $G$ is isomorphic to a direct product of cyclic groups in the form
$$
\mathbb{Z}_{p_1^{e_1}} \times \mathbb{Z}_{p_2^{e_2}} \times \cdots \mathbb{Z}_{p_n^{e_n}} \times \mathbb{Z} \times \cdots \times \mathbb{Z}
$$ where $p_i$ are primes(not need distinct). The direct product is unqiue except for possible rearrangement of the factors.

---

**Theorem** (Fundamental theorem of finite abelian groups)
Suppose $G$ is finitely generated abelian groups. Then $G$ is isomorphic to a direct product of cyclic groups in the form
$$
\mathbb{Z}_{p_1^{e_1}} \times \mathbb{Z}_{p_2^{e_2}} \times \cdots \mathbb{Z}_{p_n^{e_n}}
$$ where $p_i$ are primes(not need distinct). The direct product is unqiue except for possible rearrangement of the factors.

**Theorem**
If $m$ divides the order of a finite abelian group $G$ , then $G$ has a subgroup of order $m$.
> ***proof***
> Suppose $G \cong \mathbb{Z}_{p_1^{e_1}}\times\mathbb{Z}_{p_2^{e_2}}\cdots \mathbb{Z}_{p_k^{e_k}}$. Since $m$ is divides $|G|$, $m = p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}$ for some non-negative integers $r_i$. Then the subgroup
>$$
\langle p^{e_1-r_1}\rangle \times \langle p^{e_2-r_2}\rangle \times \cdots \langle p^{e_k-r_1k}\rangle
$$
has order m.

---
In general, if the prime factorization of a positive integer n is $n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$
where $p_i$ are distinct primes, then the number of all abelian groups of order $n$, up to isomorphism, is equal to
$$p(e_1)p(e_2) \cdots p(e_n)$$,where $p(e)$ is the number of ways to write an integer e as a sum of positive integers

---

**Example**
Let $n=200=2^3\cdot5^2$. Then there are $2 \times 3$ non-isomorphic abelian groups of order 200.
$$
\begin{align}
\mathbb{Z}_8 \times \mathbb{Z}_{25} \\
\mathbb{Z}_8 \times \mathbb{Z}_{5} \times \mathbb{Z}_{5}\\
\mathbb{Z}_{4} \times \mathbb{Z}_{2} \times \mathbb{Z}_{25} \\
\mathbb{Z}_{4} \times \mathbb{Z}_{2} \times \mathbb{Z}_{5} \times \mathbb{Z}_{5} \\
\mathbb{Z}_{2} \times \mathbb{Z}_{2} \times \mathbb{Z}_{2} \times \mathbb{Z}_{25} \\
\mathbb{Z}_{2} \times \mathbb{Z}_{2} \times \mathbb{Z}_{2} \times \mathbb{Z}_{5} \times \mathbb{Z}_{5} \\
\end{align}
$$

**Example**
$$
\begin{align}
(\mathbb{Z}_{60})^\times &\cong (\mathbb{Z}_{4})^\times \times (\mathbb{Z}_{15})^\times \\
&\cong (\mathbb{Z}_{4})^\times \times (\mathbb{Z}_{3})^\times \times (\mathbb{Z}_{5})^\times \\
&\cong \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_4
\end{align}
$$

---