Chain complexes¶

AUTHORS:

John H. Palmieri (2009-04)

This module implements chain complexes of free $R$ -modules, for any commutative ring $R$ (although the interesting things, like homology, only work if $R$ is the integers or a field).

Fix a ring $R$ . A chain complex over $R$ is a collection of $R$ -modules $\{C_n\}$ indexed by the integers, with $R$ -module maps $d_n : C_n \rightarrow C_{n+1}$ such that $d_{n+1} \circ d_n = 0$ for all $n$ . The maps $d_n$ are called differentials.

One can vary this somewhat: the differentials may decrease degree by one instead of increasing it: sometimes a chain complex is defined with $d_n : C_n \rightarrow C_{n-1}$ for each $n$ . Indeed, the differentials may change dimension by any fixed integer.

Also, the modules may be indexed over an abelian group other than the integers, e.g., $\ZZ^{m}$ for some integer $m \geq 1$ , in which case the differentials may change the grading by any element of that grading group.

In this implementation, the ring $R$ must be commutative and the modules $C_n$ must be free $R$ -modules. As noted above, homology calculations will only work if the ring $R$ is either $\ZZ$ or a field. The modules may be indexed by any free abelian group. The differentials may increase degree by 1 or decrease it, or indeed change it by any fixed amount: this is controlled by the degree parameter used in defining the chain complex.

class sage.homology.chain_complex.ChainComplex(data=None, **kwds)¶

Bases: sage.structure.sage_object.SageObject

Define a chain complex.

INPUT:

data - the data defining the chain complex; see below for more details.
base_ring - a commutative ring (optional), the ring over which the chain complex is defined. If this is not specified, it is determined by the data defining the chain complex.
grading_group - a free abelian group (optional, default ZZ), the group over which the chain complex is indexed.
degree - element of grading_group (optional, default 1), the degree of the differential.
check_products - boolean (optional, default True). If True, check that each consecutive pair of differentials are composable and have composite equal to zero.

OUTPUT: a chain complex

Warning

Right now, homology calculations will only work if the base ring is either ZZ or a field, so please take this into account when defining a chain complex.

Use data to define the chain complex. This may be in any of the following forms.

a dictionary with integers (or more generally, elements of grading_group) for keys, and with data[n] a matrix representing (via left multiplication) the differential coming from degree $n$ . (Note that the shape of the matrix then determines the rank of the free modules $C_n$ and $C_{n+d}$ .)
a list or tuple of the form $[C_0, d_0, C_1, d_1, C_2, d_2, ...]$ , where each $C_i$ is a free module and each $d_i$ is a matrix, as above. This only makes sense if grading_group is $\ZZ$ and degree is 1.
a list or tuple of the form $[r_0, d_0, r_1, d_1, r_2, d_2, ...]$ , where $r_i$ is the rank of the free module $C_i$ and each $d_i$ is a matrix, as above. This only makes sense if grading_group is $\ZZ$ and degree is 1.
a list or tuple of the form $[d_0, d_1, d_2, ...]$ where each $d_i$ is a matrix, as above. This only makes sense if grading_group is $\ZZ$ and degree is 1.

Note

In fact, the free modules $C_i$ in case 2 and the ranks $r_i$ in case 3 are ignored: only the matrices are kept, and from their shapes, the ranks of the modules are determined. (Indeed, if data is a list or tuple, then any element which is not a matrix is discarded; thus the list may have any number of different things in it, and all of the non-matrices will be ignored.) No error checking is done to make sure, for instance, that the given modules have the appropriate ranks for the given matrices. However, as long as check_products is True, the code checks to see if the matrices are composable and that each appropriate composite is zero.

If the base ring is not specified, then the matrices are examined to determine a ring over which they are all naturally defined, and this becomes the base ring for the complex. If no such ring can be found, an error is raised. If the base ring is specified, then the matrices are converted automatically to this ring when defining the chain complex. If some matrix cannot be converted, then an error is raised.

EXAMPLES:

sage: ChainComplex()
Chain complex with at most 0 nonzero terms over Integer Ring
sage: C = ChainComplex({0: matrix(ZZ, 2, 3, [3, 0, 0, 0, 0, 0])})
sage: C
Chain complex with at most 2 nonzero terms over Integer Ring
sage: D = ChainComplex([matrix(ZZ, 2, 2, [0, 1, 0, 0]), matrix(ZZ, 2, 2, [0, 1, 0, 0])], base_ring=GF(2)); D
Chain complex with at most 3 nonzero terms over Finite Field of size 2
sage: D == loads(dumps(D))
True

Note that when a chain complex is defined in Sage, new differentials may be created: every nonzero module in the chain complex must have a differential coming from it, even if that differential is zero:

sage: IZ = ChainComplex({0: identity_matrix(ZZ, 1)})
sage: IZ.differential()  # the differentials in the chain complex
{0: [1], 1: []}
sage: IZ.differential(1).parent()
Full MatrixSpace of 0 by 1 dense matrices over Integer Ring
sage: mat = ChainComplex({0: matrix(ZZ, 3, 4)}).differential(1)
sage: mat.nrows(), mat.ncols()
(0, 3)

Defining the base ring implicitly:

sage: ChainComplex([matrix(QQ, 3, 1), matrix(ZZ, 4, 3)])
Chain complex with at most 3 nonzero terms over Rational Field
sage: ChainComplex([matrix(GF(125, 'a'), 3, 1), matrix(ZZ, 4, 3)])
Chain complex with at most 3 nonzero terms over Finite Field in a of size 5^3

If the matrices are defined over incompatible rings, an error results:

sage: ChainComplex([matrix(GF(125, 'a'), 3, 1), matrix(QQ, 4, 3)])
...
TypeError: unable to find a common ring for all elements

If the base ring is given explicitly but is not compatible with the matrices, an error results:

sage: ChainComplex([matrix(GF(125, 'a'), 3, 1)], base_ring=QQ)
...
TypeError: Unable to coerce 0 (<type 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>) to Rational

base_ring()¶

The base ring for this simplicial complex.

EXAMPLES:

sage: ChainComplex().base_ring()
Integer Ring

betti(dim=None, **kwds)¶

The Betti number of the homology of the chain complex in this dimension.

That is, write the homology in this dimension as a direct sum of a free module and a torsion module; the Betti number is the rank of the free summand.

INPUT:

dim - an element of the grading group for the chain complex or None (optional, default None). If None, then return every Betti number, as a dictionary indexed by degree. If an element of the grading group, then return the Betti number in that dimension.
base_ring - a commutative ring (optional, default is the base ring for the chain complex). Compute homology with these coefficients. Must be either the integers or a field.

OUTPUT: the Betti number in dimension dim - the rank of the free part of the homology module in this dimension.

EXAMPLES:

sage: C = ChainComplex({0: matrix(ZZ, 2, 3, [3, 0, 0, 0, 0, 0])})
sage: C.betti(0)
2
sage: [C.betti(n) for n in range(5)]
[2, 1, 0, 0, 0]
sage: C.betti()
{0: 2, 1: 1}

category()¶

Return the category to which this chain complex belongs: the category of all chain complexes over the base ring.

EXAMPLES:

sage: C = ChainComplex({0: matrix(ZZ, 2, 3, [3, 0, 0, 0, 0, 0])}, base_ring=GF(7))
sage: C.category()
Category of chain complexes over Finite Field of size 7

differential(dim=None)¶

The differentials which make up the chain complex.

INPUT:

dim - element of the grading group (optional, default None). If this is None, return a dictionary of all of the differentials. If this is a single element, return the differential starting in that dimension.

OUTPUT: either a dictionary of all of the differentials or a single differential (i.e., a matrix)

EXAMPLES:

sage: D = ChainComplex({0: matrix(ZZ, 2, 2, [1,0,0,2])})
sage: D.differential()
{0: [1 0]
[0 2], 1: []}
sage: D.differential(0)
[1 0]
[0 2]
sage: C = ChainComplex({0: identity_matrix(ZZ, 40)})
sage: C.differential()
{0: 40 x 40 dense matrix over Integer Ring, 1: []}

dual()¶

The dual chain complex to self.

Since all modules in self are free of finite rank, the dual in dimension $n$ is isomorphic to the original chain complex in dimension $n$ , and the corresponding boundary matrix is the transpose of the matrix in the original complex. This converts a chain complex to a cochain complex and vice versa.

EXAMPLES:

sage: C = ChainComplex({2: matrix(ZZ, 2, 3, [3, 0, 0, 0, 0, 0])})
sage: C._degree
1
sage: C.differential(2)
[3 0 0]
[0 0 0]
sage: C.dual()._degree
-1
sage: C.dual().differential(3)
[3 0]
[0 0]
[0 0]

free_module()¶

The free module underlying this chain complex.

EXAMPLES:

sage: C = ChainComplex({0: matrix(ZZ, 2, 3, [3, 0, 0, 0, 0, 0]), 1: matrix(ZZ, 0, 2)})
sage: C.free_module()
Ambient free module of rank 5 over the principal ideal domain Integer Ring

This defines the forgetful functor from the category of chain complexes to the category of free modules:

sage: FreeModules(ZZ)(C)
Ambient free module of rank 5 over the principal ideal domain Integer Ring

homology(dim=None, **kwds)¶

The homology of the chain complex in the given dimension.

INPUT:

dim - an element of the grading group for the chain complex (optional, default None): the degree in which to compute homology. If this is None, return the homology in every dimension in which the chain complex is possibly nonzero.
base_ring - a commutative ring (optional, default is the base ring for the chain complex). Must be either the integers $\ZZ$ or a field.
generators - boolean (optional, default False). If True, return generators for the homology groups along with the groups. NOTE: this is only implemented if the CHomP package is available.
verbose - boolean (optional, default False). If True, print some messages as the homology is computed.
algorithm - string (optional, default ‘auto’). The options are ‘auto’, ‘dhsw’, ‘pari’ or ‘no_chomp’. See below for descriptions.

OUTPUT: if dim is specified, the homology in dimension dim. Otherwise, the homology in every dimension as a dictionary indexed by dimension.

ALGORITHM:

If algorithm is set to ‘auto’ (the default), then use CHomP if available. (CHomP is available at the web page http://chomp.rutgers.edu/. It is also an experimental package for Sage.)

CHomP computes homology, not cohomology, and only works over the integers or finite prime fields. Therefore if any of these conditions fails, or if CHomP is not present, or if algorithm is set to ‘no_chomp’, go to plan B: if self has a _homology method – each simplicial complex has this, for example – then call that. Such a method implements specialized algorithms for the particular type of cell complex.

Otherwise, move on to plan C: compute the chain complex of self and compute its homology groups. To do this: over a field, just compute ranks and nullities, thus obtaining dimensions of the homology groups as vector spaces. Over the integers, compute Smith normal form of the boundary matrices defining the chain complex according to the value of algorithm. If algorithm is ‘auto’ or ‘no_chomp’, then for each relatively small matrix, use the standard Sage method, which calls the Pari package. For any large matrix, reduce it using the Dumas, Heckenbach, Saunders, and Welker elimination algorithm: see sage.homology.chain_complex.dhsw_snf() for details.

Finally, algorithm may also be ‘pari’ or ‘dhsw’, which forces the named algorithm to be used regardless of the size of the matrices and regardless of whether CHomP is available.

As of this writing, CHomP is by far the fastest option, followed by the ‘auto’ or ‘no_chomp’ setting of using the Dumas, Heckenbach, Saunders, and Welker elimination algorithm for large matrices and Pari for small ones.

Warning

This only works if the base ring is the integers or a field. Other values will return an error.

EXAMPLES:

sage: C = ChainComplex({0: matrix(ZZ, 2, 3, [3, 0, 0, 0, 0, 0])})
sage: C.homology()
{0: Z x Z, 1: Z x C3}
sage: C.homology(dim=1, base_ring = GF(3))
Vector space of dimension 2 over Finite Field of size 3
sage: D = ChainComplex({0: identity_matrix(ZZ, 4), 4: identity_matrix(ZZ, 30)})
sage: D.homology()
{0: 0, 1: 0, 4: 0, 5: 0}

Generators (only available via CHomP): generators are given as a list of cycles, each of which is an element in the appropriate free module, and hence is represented as a vector:

sage: C.homology(1, generators=True)  # optional: need CHomP
(Z x C3, [(1, 0), (0, 1)])

torsion_list(max_prime, min_prime=2)¶

Look for torsion in this chain complex by computing its mod $p$ homology for a range of primes $p$ .

INPUT:

max_prime - prime number: search for torsion mod $p$ for all $p$ strictly less than this number.
min_prime - prime (optional, default 2): search for torsion mod $p$ for primes at least as big as this.

Return a list of pairs ( $p$ , dims) where $p$ is a prime at which there is torsion and dims is a list of dimensions in which this torsion occurs.

The base ring for the chain complex must be the integers; if not, an error is raised.

Algorithm: let $C$ denote the chain complex. Let $P$ equal max_prime. Compute the mod $P$ homology of $C$ , and use this as the base-line computation: the assumption is that this is isomorphic to the integral homology tensored with $\GF{P}$ . Then compute the mod $p$ homology for a range of primes $p$ , and record whenever the answer differs from the base-line answer.

EXAMPLES:

sage: C = ChainComplex({0: matrix(ZZ, 2, 3, [3, 0, 0, 0, 0, 0])})
sage: C.homology()
{0: Z x Z, 1: Z x C3}
sage: C.torsion_list(11)
[(3, [1])]
sage: C = ChainComplex([matrix(ZZ, 1, 1, [2]), matrix(ZZ, 1, 1), matrix(1, 1, [3])])
sage: C.homology(1)
C2
sage: C.homology(3)
C3
sage: C.torsion_list(5)
[(2, [1]), (3, [3])]

sage.homology.chain_complex.HomologyGroup(n, invfac=None)¶

Abelian group on $n$ generators. This class inherits from AbelianGroup; see that for more documentation. The main difference between the classes is in the print representation; also, this class does not accept a names argument.

EXAMPLES:

sage: from sage.homology.chain_complex import HomologyGroup
sage: G = AbelianGroup(5,[5,5,7,8,9]); G
Multiplicative Abelian Group isomorphic to C5 x C5 x C7 x C8 x C9
sage: H = HomologyGroup(5,[5,5,7,8,9]); H
C5 x C5 x C7 x C8 x C9
sage: AbelianGroup(4)
Multiplicative Abelian Group isomorphic to Z x Z x Z x Z
sage: HomologyGroup(4)
Z x Z x Z x Z
sage: HomologyGroup(100)
Z^100

class sage.homology.chain_complex.HomologyGroup_class(n, invfac)¶

Bases: sage.groups.abelian_gps.abelian_group.AbelianGroup_class

Abelian group on $n$ generators. This class inherits from AbelianGroup; see that for more documentation. The main difference between the classes is in the print representation; also, this class does not accept a names argument.

EXAMPLES:

sage: from sage.homology.chain_complex import HomologyGroup
sage: G = AbelianGroup(5,[5,5,7,8,9]); G
Multiplicative Abelian Group isomorphic to C5 x C5 x C7 x C8 x C9
sage: H = HomologyGroup(5,[5,5,7,8,9]); H
C5 x C5 x C7 x C8 x C9
sage: G == loads(dumps(G))
True
sage: AbelianGroup(4)
Multiplicative Abelian Group isomorphic to Z x Z x Z x Z
sage: HomologyGroup(4)
Z x Z x Z x Z
sage: HomologyGroup(100)
Z^100

sage.homology.chain_complex.dhsw_snf(mat, verbose=False)¶

Preprocess a matrix using the “Elimination algorithm” described by Dumas et al., and then call elementary_divisors on the resulting (smaller) matrix.

‘dhsw’ stands for ‘Dumas, Heckenbach, Saunders, Welker,’ and ‘snf’ stands for ‘Smith Normal Form.’

INPUT:

mat - an integer matrix, either sparse or dense.

(They use the transpose of the matrix considered here, so they use rows instead of columns.)

Algorithm: go through mat one column at a time. For each column, add multiples of previous columns to it until either

it’s zero, in which case it should be deleted.

its first nonzero entry is 1 or -1, in which case it should be kept.

its first nonzero entry is something else, in which case it is deferred until the second pass.

Then do a second pass on the deferred columns.

At this point, the columns with 1 or -1 in the first entry contribute to the rank of the matrix, and these can be counted and then deleted (after using the 1 or -1 entry to clear out its row). Suppose that there were $N$ of these.

The resulting matrix should be much smaller; we then feed it to Sage’s elementary_divisors function, and prepend $N$ 1’s to account for the rows deleted in the previous step.

EXAMPLES:

sage: from sage.homology.chain_complex import dhsw_snf
sage: mat = matrix(ZZ, 3, 4, range(12))
sage: dhsw_snf(mat)
[1, 4, 0]
sage: mat = random_matrix(ZZ, 20, 20, x=-1, y=2)
sage: mat.elementary_divisors() == dhsw_snf(mat)
True

REFERENCES:

Dumas, Heckenbach, Saunders, Welker, “Computing simplicial homology based on efficient Smith normal form algorithms,” in “Algebra, geometry, and software systems” (2003), 177-206.

Chain complexes¶

Previous topic

Next topic

This Page

Navigation

Chain complexes¶

Previous topic

Next topic

This Page

Quick search

Navigation