6/28 meeting
===

Jacobain
---


### Remark

---

Example
---

---

---

---
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
:::

e.g.

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

:::

**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}$

---


---

Algorithm
---

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

8

---

9