Is there an algorithmic way to compute the quotient of two subgroups of $\mathbb Z^n$?

45 Views Asked by At

In algebraic topology one sometimes has to compute the homology groups via CW complexes, reducing the problem to the calculation of $Z/B$ where $B \subseteq Z \subseteq \mathbb{Z}^n $. It is difficult enough for me sometimes if $B$ is complicated.

For instance the isomorphism $\mathbb Z \oplus \mathbb Z / \left<(2,0),(-1,2)\right> \cong \mathbb Z / 4 \mathbb Z $ is not trivial at all.

Is there a general algorithm to determine $Z/B$, as both of $Z$ and $B$ are represented as the subgroups generated by several elements of $\mathbb Z^n $? Thanks.

1

There are 1 best solutions below

0
On BEST ANSWER

Yes. For instance, you can use Smith normal form to do this. This amounts to doing Gaussian elimination over the integers.

https://en.wikipedia.org/wiki/Smith_normal_form

In somewhat more detail, any subgroup of $\mathbf{Z}^n$ can be thought of as the image of a $\mathbf{Z}$-linear (that is, additive) map $\mathbf{Z}^m \to \mathbf{Z}^n$ for some integer $m$, which in turn may be represented by a matrix $A$ with integer entries. Performing elementary row operations on $A$ amounts to gradually changing the chosen basis of the target $\mathbf{Z}^n$, and performing elementary column operations on $A$ amounts to gradually changing the chosen basis of the domain $\mathbf{Z}^m$. The relevant fact is therefore that you can use elementary row and column operations to reduce $A$ to a diagonal matrix of the form $$A=\left(\begin{matrix} a_1 & 0 & 0 & \cdots \\ 0 & a_2 & 0 & \cdots \\ 0 & 0 & a_3 & \cdots \\ \vdots & \vdots & \vdots \end{matrix} \right)$$ in which $a_i$ divides $a_{i+1}$ for all $i$.

This is a computationally effective form of the fundamental theorem of abelian groups, and shows that the cokernel of $A$ is isomorphic to $$\mathrm{coker}(A) \cong \mathbf{Z}/a_1 \mathbf{Z} \oplus \mathbf{Z}/a_2 \mathbf{Z} \oplus \cdots.$$

In your chosen example, the matrix $A$ is $$A=\left(\begin{matrix} -1 & 2 \\ 2 & 0 \end{matrix} \right)$$ and by first doing the row operation replace row two by row two plus twice row one and then the column operation replace column two by column two plus twice column one reduces it to $$A=\left(\begin{matrix} -1 & 0 \\ 0 & 4 \end{matrix} \right),$$ showing that the cokernel is $\mathbf{Z}/4 \mathbf{Z}$ as claimed.