📂Topological Data Analysis

Homomorphism Smith Normal Form

Theorem ¹

Let free Abelian group $G$ and $G'$ have bases $a_{1} , \cdots , a_{n}$ and $a_{1}' , \cdots , a_{m}'$, respectively. If function $f : G \to G'$ is a homomorphism, then there exists a unique set of integers $\left\{ \lambda_{ij} \right\} \subset \mathbb{Z}$ satisfying the following. $$f \left( a_{j} \right) = \sum_{i=1}^{m} \lambda_{ij} a_{i}'$$ The matrix $\left( \lambda_{ij} \right) \in \mathbb{Z}^{m \times n}$ is referred to as the matrix of $f$ (with respect to the bases of $G$ and $G'$).

If free Abelian groups $G$ and $G'$ have ranks $n,m$, and $f : G \to G'$ is a homomorphism, then there exists a homomorphism $g$ with the following matrix. $$\begin{bmatrix} d_{1} & 0 & 0 & 0 & \cdots & 0 \\ 0 & \ddots & 0 & 0 & \cdots & 0 \\ 0 & 0 & d_{r} & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 \end{bmatrix} \in \mathbb{Z}^{m \times n}$$ Here, $d_{1} , \cdots, d_{r} \in \mathbb{N}$ and $d_{1} \mid \cdots \mid d_{r}$, meaning $d_{k}$ has to be a divisor of $d_{k+1}$.

Description

The matrix mentioned in the theorem is known as the Smith normal form, given $f$ and $\lambda_{ij}$, the $d_{1} , \cdots, d_{r}$ can be found using the Gauss elimination method and thus are a linear combination of $\lambda_{ij}$. Row operations involved in obtaining the Smith normal form affect the basis of $G'$, and column operations affect the bases of $G$.

In essence, this theorem suggests that when considering two free groups $G, G'$, it is sufficient to have only $r \le \min \left( m,n \right)$ of the $d_{1} , \cdots , d_{r}$ instead of all $\lambda_{ij}$. These can be seen as the most succinct summary of information from $G$ to $G'$.

$$\begin{align*} f(a) =& x + y - z \\ f(b) =& x - y + z \end{align*}$$ For example, if $f: F[a,b] \to F[x,y,z]$ is defined as above, it is naturally a homomorphism and the matrix of $f$ is as follows. $$\begin{bmatrix} 1 & 1 & -1 \\ 1 & -1 & 1 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \end{bmatrix}$$ The right side is the Smith normal form of the left side. Once a homomorphism’s matrix takes on the form of the Smith normal form, that form is unique.

Theorem

Choose any bases for $G$ and $G'$, and define any homomorphism $f \left( a_{j} \right) = \sum_{i=1}^{m} \lambda_{ij} a_{i}'$. The matrix of $f$, $\left( \lambda_{ij} \right)$, belongs to the set of matrices made of integers $\mathbb{Z}^{m \times n}$.

Smith normal form calculation algorithm: When $R$ is a principal ideal domain, for every matrix $A \in R^{m \times n}$, there exists a uniquely determined Smith normal form.

Since $\mathbb{Z}$ is a principal ideal domain, for matrix $\left( \lambda_{ij} \right)$, there exists a Smith normal form where all elements except for $r$ diagonal elements $d_{1} , \cdots , d_{r}$ are $0$.

■