Using the Smith normal form to compute homology
Table of Contents
If the homology calculations start to feel onerous, use a computer! You just need a program that can compute the Smith normal form of an integer matrix. Sage is a good choice and can conveniently be used from a web browser, without intalling any software.
The Smith normal form and homology
The Smith normal form of an integer matrix \(A \in \mathrm{Mat}_{m \times n}(\mathbb{Z})\) is a factorization \(A = U D V\) where:
- \(D \in \mathrm{Mat}_{m \times n}(\mathbb{Z})\) is “diagonal”1, meaning that \(D_{ij} = 0\) whenever \(i \neq j\).
- Each diagonal entry of \(D\) divides the next: \(D_{ii} | D_{i+1,i+1}\). These diagonal entries are called the elementary divisors of \(A\).
- \(U \in \mathrm{Mat}_{m \times m}(\mathbb{Z})\) and \(V \in \mathrm{Mat}_{n \times n}(\mathbb{Z})\) are invertible over \(\mathbb{Z}\), or equivalently \(\det U\) and \(\det V\) are \(\pm 1\).
The main result about Smith normal form, of course, is that every integer matrix has one. It is unique up to signs. There is an algorithm to compute it which is cross between row reduction and the Euclidean algorithm for computing greatest common divisors.
The Smith normal form even exists for matrices over arbitrary prinicpal ideal domains \(R\). There \(U\) and \(V\) are required to be invertible over \(R\), so their determinants can be any units in \(R\) (not necessarily \(\pm 1\)). The form is unique up to multiplication by units of \(R\).
We can use this to calculate homology of a chain complex of abelian groups.
Let the non-zero elementary divisors of an \(m\times n\) integer matrix \(A\) be \(a_1, a_2, \ldots, a_r\) (so that \(r\) is the rank of \(A\)). Then \(\mathrm{coker}(A) := \mathbb{Z}^{m}/\mathrm{im}(A) \cong \bigoplus_{i=1}^{r} \mathbb{Z}/a_i \oplus \mathbb{Z}^{m-r}\).
Let \(A = UDV\) be the Smith normal form of \(A\), then \(\mathrm{coker}(A) \cong \mathrm{coker}(D)\) via \(x + \mathrm{im}(A) \mapsto U^{-1} x + \mathrm{im}(D)\). The cokernel of \(D\) is easy to compute: if \(e_1, \ldots, e_m\) is the standard basis of \(\mathbb{Z}^m\), then the image of \(D\) is spanned by \(a_1 e_1, \ldots, a_r e_r\), from this the result is clear.
Now on to computing homology:
Given a complex \(\mathbb{Z}^n \xrightarrow{A} \mathbb{Z}^m \xrightarrow{B} \mathbb{Z}^k\) (so \(BA=0\)), the homology at the middle term is given by \(\ker(B)/\mathrm{im}(A) \cong \bigoplus_{i=1}^{r} \mathbb{Z}/a_i \oplus \mathbb{Z}^{m-r-s}\) where \(r = \mathrm{rank}(A)\), \(s = \mathrm{rank}(B)\) and \(a_1, \ldots, a_r\) are the non-zero elementary divisors of \(A\).
Because \(B\) is zero on \(\mathrm{im}(A)\), it descends to a homomorphism \(\bar{B} : \mathbb{Z}^m/\mathrm{im}(A) \to \mathbb{Z}^k\). It’s not hard to see that the homology group \(\ker(B)/\mathrm{im}(A)\) is isomorphic to \(\ker(\bar{B})\).
Now, by the previous proposition, \(\mathbb{Z}^m/\mathrm{im}(A) \cong \bigoplus_{i=1}^{r} \mathbb{Z}/a_i \oplus \mathbb{Z}^{m-r}\). Since the target of \(\bar{B}\) is free, all of the torsion of its domain group must be in the kernel, so we see that \[ \ker(\bar{B}) = \bigoplus_{i=1}^{r} \mathbb{Z}/a_i \oplus \ker(\bar{B}|_{\mathbb{Z}^{m-r}}.)\] The kernel of the restriction of \(\bar{B}\) to the free part must also be free (any subgroup of a free abelian group is free) and its rank is \(m - r - s\), because \(s\) is the rank of \(\mathrm{im}(B) = \mathrm{im}(\bar{B}) = \mathrm{im}(\bar{B}|_{\mathbb{Z}^{m-r}})\).
Computer calculations
You can use Sage to compute Smith normal forms, or just elementary divisors if that’s all you need. You don’t even need to install anything or even create some sort of online account thanks to the single cell server!
You can create a matrix and ask for its Smith normal form or just its elementary divisors (either piece of information includes the rank, of course) as follows:
A = matrix([[1,3,-1],[-1,2,1],[0,-1,1],[2,-1,0]]) A.smith_form() # or A.elementary_divisors()
Here’s a link to a Sage cell with the above computation, just modify the matrix and you’re set!
The scare quotes are in case, like me, you are used to diagonal matrices being square.