---
# System prepended metadata

title: 6/28 meeting

---

6/28 meeting
===


Jacobain
---



![image](https://hackmd.io/_uploads/S1DQtjc8C.png)
![image](https://hackmd.io/_uploads/SyrK0no8A.png)
![image](https://hackmd.io/_uploads/Hke3oTcLR.png)


### Remark
![image](https://hackmd.io/_uploads/ByCEJcjUR.png)
![image](https://hackmd.io/_uploads/S14Cj9j8R.png)



---
![image](https://hackmd.io/_uploads/SJUWhqjIA.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/r12ATcoL0.png)
![image](https://hackmd.io/_uploads/rJb105sLR.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}$


---

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



---

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


[Greedy](https://github.com/justinvulz/dollar_game/blob/main/greedy.cpp)

8
![image](https://hackmd.io/_uploads/B1zNQlsI0.png)
![image](https://hackmd.io/_uploads/Sy5G7xjLC.png)

---

9
![image](https://hackmd.io/_uploads/SkapHls80.png)
![image](https://hackmd.io/_uploads/ByP5NloUC.png)
