---
# System prepended metadata

title: 6/25 meeting

---

6/25 meeting
===
---
The dollar game 
---
[The dollar game](https://thedollargame.io/game/level/100/100/1)

---
### Definition

A *multigraph* $G = (V,H)$ is a pair of a set of *vertices* $V$ ans a multiset of *edges* $E$ comprised of unordered pairs $\{v,u\}$ of vertices.

Here we only consider a graph to be finite, connected, undirected multigraph without loop.

---
![image](https://hackmd.io/_uploads/rkbQ1mBUR.png)
Divisors represent distributions of wealth on $G$: if $D=\sum_{v \in V} D(v)v$, then each vertex(person) has $D(v)$ dollars.

---

![image](https://hackmd.io/_uploads/B1y51QSL0.png)
The colection of divisors of degree $k$ is denote $\text{Div}^k(G)$.

**Note.** For $v \in V$, $deg_G(v)$ denote its number of incident edges. If think of $v$ as a divisor, $deg(v)$.

---
![image](https://hackmd.io/_uploads/H1njkmB8C.png)

Let $D \in \text{Div}(G)$ and $v,w \in V$.
$$
    D \xrightarrow{v} D' \xrightarrow{w} D''' \\
$$$$
\begin{align}
    D''' &= D' - \sum_{wu \in V}(w-u) \\
        &= D - \sum_{vu \in V}(v-u) - \sum_{wu \in V}(w-u)
\end{align}
$$$$
    D \xrightarrow{w} D'' \xrightarrow{v} D''' \\
$$
![image](https://hackmd.io/_uploads/SyVHzXSUC.png)
This show that the order of lending and borrowing moves does not matter.

---
![image](https://hackmd.io/_uploads/r1k9LmB8C.png)
![image](https://hackmd.io/_uploads/H1qjCNSL0.png)
For $v \in V$, consider $D \xrightarrow{V\backslash\{v\}} D'$
$$
\begin{align}
    D' &= D - \sum_{u \in V\backslash\{v\}}\sum_{uw \in E}(u-w)\\
    &= D - \sum_{uv \in E}(u-v)\\
    &= D + \sum_{uv \in E}(v-u)
\end{align}
$$
It show that $D \xrightarrow{-v} D'$.

Borring from $v \in V$ is the same as set-lending by $V\backslash\{v\}$, and a set-lending by $V$ has not net effect.

---
![image](https://hackmd.io/_uploads/r1EYmBS80.png)
![image](https://hackmd.io/_uploads/rJ6iQHSIR.png)
![image](https://hackmd.io/_uploads/SkiWVrH8A.png)

For $D,D' \in \text{Div}(G)$, define $D \geq D'$ if $D(v) \geq D'(v)$ for all $v \in V$, 
$D \geq 0$ if $D(v) \geq 0$ for all $v \in V$ 

![image](https://hackmd.io/_uploads/HJ7eBBBU0.png)

![image](https://hackmd.io/_uploads/BymODHrL0.png)
![image](https://hackmd.io/_uploads/rJzBdHrIA.png)

---
![image](https://hackmd.io/_uploads/S1_iwBBUA.png)

**Corollary** If $\text{deg}(D) < 0$, then D is unwinnable

---
### Picard and Jacobian group

The sum of $D,F \in \text{Div}(G)$ is defined vertex-wise:
$$
    D+F = \sum_{v\in V}(D(v)+F(v))v
$$ 
If $D' \sim D$ and $F' \sim F$, then $D+F \sim D'+F'$ 

![image](https://hackmd.io/_uploads/B1Q9loBL0.png)

![image](https://hackmd.io/_uploads/BJ1SfjBUR.png)
> *Proof*
> Homomorphic: Trivial
> Injective: Suppose $\phi([A]) = (0,[e])$. Then $\text{deg}(A)=0$ and $[A - \text{deg}(A)q] = [e]$. So, $[A]=[e]$
> Surjective: Given $(n,[x]) \in \mathbb{Z}\times\text{Jac}(G)$. Let $D=x+nq$.
> Then $\phi([D]) = (n,[D - \text{deg}(D)q]) = (n,[x])$

![image](https://hackmd.io/_uploads/SJZlrsHI0.png)

![image](https://hackmd.io/_uploads/Sy2GrjBLC.png)

---
Laplacian
---
![image](https://hackmd.io/_uploads/HJXYBsSLR.png)

---
![image](https://hackmd.io/_uploads/B1xHx3S8R.png)
**Note.** $\mathcal{M}(G) = \mathbb{Z}^V$
![image](https://hackmd.io/_uploads/SJrhf2BLC.png)
(we write $\chi_v$ for $\chi_{\{v\}}$)

Given any firing script $\sigma$, the result of applying the correspomding collection of lending moves to a divisor $D$ will be the divisor $D'$ given by:
![image](https://hackmd.io/_uploads/ryUSQhBUC.png)

![image](https://hackmd.io/_uploads/HyrlVhH8A.png)

$D' = D - \text{div}(\sigma)$. We see that $D'$ is linearly equivalent to  $D$, denote $D \xrightarrow{\sigma} D'$.

![image](https://hackmd.io/_uploads/SkFQB3SLR.png)
:::spoiler proof
![image](https://hackmd.io/_uploads/ryaCYnBLA.png)
:::

**Definition.** 
Divisors of the form $\text{div}(\sigma)$ is called *principal*.
The set of of principlal divisors forms a subgroup $\text{Prin}(G) < \text{Div}^0{G}$

If $D$ is linerly equialence to $D'$, then $D' = D - \text{div}(\sigma)$. Thus, $D -D' \in \text{Prin}(G)$

Hence, we can expressthe Picard and Jacobian groups as quotients:
![image](https://hackmd.io/_uploads/rJP65nSUR.png)

---
---

Now we show that $\text{div}:\mathcal{M}(G) \rightarrow \text{Div}(G)$ and  $L:\mathbb{Z}^V \rightarrow \mathbb{Z}^V$ are essentially the same.
![image](https://hackmd.io/_uploads/H1Ka62r8A.png)
Note that the mapping $v \mapsto \chi_v$ determines an isomorphis of $\text{Div}(G)$ with $\mathbb{Z}^V$.
:::spoiler proof
![image](https://hackmd.io/_uploads/Bya3lTB8A.png)
:::

---
To realize $L$ as a single matrix, fix an ordering $v_1,....v_n$ of the vertices of $G$, providing an ordered vasis for the free abelian group $\text{Div}(G)$ and a corresponding isomorphism with $\mathbb{Z}^n$. Writing $\chi_j := \chi_{v_j}$, it follows that $\{\chi_1,...,\chi_n\}$ is the dual basis of the free abelian group $\mathcal{M}(G) = \mathbb{Z}^V$.
$$
    \chi_j(v_i) = \begin{cases}
    1 \quad i = j\\
    0 \quad i \neq j
    \end{cases}
$$
![image](https://hackmd.io/_uploads/HyW_-lPU0.png)

$L$ is the $n \times n$ integer matrix with $ij$-entry
$$
    L_{ij} = L(\chi_j)(v_i) = \begin{cases}
        \text{deg}_G(v_i) & i =j \\
        -(\# \text{ of edges between } v_i \text{ and } v_j) & i\neq j
    \end{cases}
$$
![image](https://hackmd.io/_uploads/HyHazxvIR.png)
![image](https://hackmd.io/_uploads/SkoV7xP8A.png)
![image](https://hackmd.io/_uploads/BJAsXgPIR.png)
**Proof**
Suppose $D' \sim D$. Then $D' = D + \sigma$ for some $\sigma \in \text{Prin}(G)$. Thus,
$$
\begin{align}
    &(D'(v1),\cdots,D'(v_n)) = (D(v1)+\sigma(v_1),\cdots,D(v_n)+\sigma(v_n)) \\
\\
    &(D(v1),\cdots,D(v_n)) - (D'(v1),\cdots,D'(v_n)) = (-\sigma(v_1),\cdots,-\sigma(v_n))    \in \text{im}(L)
\end{align}
$$

Isomorphism $\phi: \text{Pic}(G) \rightarrow \mathbb{Z}^n/\text{im}(L)$
$$
    [D] \mapsto (D(v_1),\cdots,D(v_n))+\text{im}(L)
$$
![image](https://hackmd.io/_uploads/HyZxwevLR.png)
![image](https://hackmd.io/_uploads/HkitoxPUC.png)

Example
---
![image](https://hackmd.io/_uploads/BJFiqawU0.png)
![image](https://hackmd.io/_uploads/ryno96w8A.png)

---
![image](https://hackmd.io/_uploads/HJy29pDUR.png)
![image](https://hackmd.io/_uploads/rJN2qTv8R.png)

---

![image](https://hackmd.io/_uploads/BJxn10P80.png)


---
Fundamental theorem of finitely generated abelian groups
---

### Primary decomposition

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.

### Invariant factor decomposition
We can also write any finitely generated abelian group G as a direct sum of the form
$$\mathbb {Z} ^{n}\times \mathbb {Z}_{k_{1}} \times \cdots \times \mathbb {Z} _{k_{u}}$$ where $k_1$ divides $k_2$, which divides $k_3$ and so on up to $k_u$. 

---
Let $A$ be abelian group. An element $a \in A$ is said to be a **torsion** element if it has finite order. The subset of all torsion elements of $A$ is a subgroup of $A$ is called the **torsion sugroup** of $A$, denote by $A_\text{tor}$ or $A_t$. 

A abelian gourps is called a **torsion group** if $A =A_t$, that is all elements of $A$ are of finite order.

A group $G$ is said to be **torsion free** if whenever an element $x$ of $G$ has finite order, then $x# is the identity.

If $A$ is an abelian group and $p$ is a prime number, we denote by $A(p)$ the subgroup of all elements $x \in A$ whose order is a power of $p$. 

Proof:  method 1

Let $A$ be finitely generated abelian groups. 

1. The finitely genrated torsion abelian group is finite.
2. $p$ is a primes such that $A(p) \neq 0$. Then
    $$A_t \cong \prod_{p} A_t(p)$$
3. Every finite abelian $p$-group is isomorphic to a product of cyclic $p$-group.
4. $A/A_t$ is torsion-free, so it is free (abelian group).
5. $A \cong A_t \times A/A_t$


Proof: method 2

Let $A$ be abelian group generated by $\{a_1,\cdots,a_m\}$
Definie $\phi: \mathbb{Z}^m \rightarrow \ A$ by 
$$
    (x_1,\cdots,x_m) \mapsto \sum x_1a_1
$$
By the isomorphism theorems, $A \cong \mathbb{Z}^m/\ker(\phi)$
Suppose $\ker(\phi)$ is generated by 
$$
    \{(a_{1i},\cdots,a_{mi}) \mid  i = 1 \sim n\}
$$
Let 
$$
    M = \begin{pmatrix}
    a_{11} & a_{12} & \cdots & a_{1n}\\
    a_{21} & a_{22} & \cdots & a_{2n}\\
    \vdots & \cdots & \cdots & \vdots \\
    a_{m1} & a_{m2} & \cdots & a_{mn}\\ 
    \end{pmatrix}_{m\times n}
$$
Thus,$A \cong \mathbb{Z}^m/\ker(\phi) \cong \mathbb{Z}^m/\text{im}(M)$

Consider the inetger row/column operations on an integer matrix:
• Switch two rows/columns.
• Multiply an invertible integer (which means ±1) to one row/column.
• Add an integer multiple of a row/column to another row/column.

Every operations is invitible.
Every row opertaions can be written as an invertible matrix $P_{n\times n}$, every column opertaions can be written as an invertible matrix $Q_{m \times m}$.

If a squence of inetger row/column operations transforming $M$ into $N$.
,then $PMQ = N$ where $P_{m\times m }$ and $Q_{n \times n}$ are invertible matrice.

**Theorem** $\mathbb{Z}^m/\text{im}(M) \cong \mathbb{Z}^m/\text{im}(N)$
:::    spoiler proof 
![image](https://hackmd.io/_uploads/ByfMPGw8C.png)
:::

![image](https://hackmd.io/_uploads/BJHf55v8R.png)
e.g.
![image](https://hackmd.io/_uploads/SyiiT5w8A.png)

For any $M \in M_{m\times n}(\mathbb{Z})$, one cay apply a sequence of row and column operations to obtain a unique Smith normal form.
::: spoiler proof
![image](https://hackmd.io/_uploads/BJDxMjPL0.png)
![image](https://hackmd.io/_uploads/SyqmgoP80.png)
![image](https://hackmd.io/_uploads/r1BBljvLR.png)

:::

**Lemma** : $\mathbb{Z}^m/\text{im}(N) \cong \mathbb{Z}_{s_1} \times \cdots \mathbb{Z}_{s_k} \times \mathbb{Z}^{m-k}$, where $N$ is Smith normal  form and $s_1,\cdots,s_k$ is invariant factors of $N$
*proof*
Define $f: \mathbb{Z}^m \rightarrow \mathbb{Z}_{s_1} \times \cdots \mathbb{Z}_{s_k} \times \mathbb{Z}^{m-k}$ by
$$
    (a_1,a_2,\cdots,a_k,\cdots,a_m) \mapsto (a_1\mod s_1,\cdots,a_k\mod s_k,a_{k+1}\cdots,a_m)
$$
Then $\ker(f) = \text{im}(N)$
Hence, $\mathbb{Z}^m/\text{im}(N) \cong \mathbb{Z}_{s_1} \times \cdots \mathbb{Z}_{s_k} \times \mathbb{Z}^{m-k}$