MOISE - A TOPOLOGY PACKAGE FOR MAPLE
version 2.0
R. Andrew Hicks
ahicks@math.drexel.eduThu Jul 27 11:24:29 EDT 2006
<Text-field style="_cstyle276" layout="Heading 1"><Font bold="true" size="18">Introduction</Font></Text-field>Welcome to to MOISE 0.2, a Maple worksheet for doing calculations with simplicial complexes. MOISE started out as just the procedure "homology", which computes the homology of a simplicial complex. The algorithm used by "homology" follows the one given in James Munkres' book "Algebraic Topology". It is an old and straightforward method for computing homology groups, but one that is hard to do by hand. In addition to computing the homology groups of a complex, MOISE also contains a number of functions that operate on simplicial complexes:
1) simplx(n) - create an n-dimensional simplex.
2) sphere(n) - create an n-sphere.
3) cone(C, p) - create the cone over the complex C with p as the cone point.
4) suspension(C, p, q) - create the suspension of C over p and q.
5) conn_sum(X, Y) - create the connected sum of X and Y.
6) oiler(C) - compute the Euler characteristic of C.
7) prod(X, Y) - compute a simplicial complex homeomorphic to the product of X and Y.
Currently there are a number of important operations missing - notably quotients. Quotients can of course be done by hand (using subs!), as is illustrated by the below example of the construction of the cylinder from the square.
Regarding efficiency: there are many ways in which the procedures below could be optimized. I wanted the code to closely follow the mathematics to keep everything clear. This is another reason that I want to stay in the simplicial category for now. A next step is to improve the algorithm for computing homology.If you have any questions about the routines or are interested in talking about algorithms in topology and algebra, please don't hesitate to contact me at ahicks@math.drexel.edu.
R. Andrew Hicks
How to use the procedure "homology":
What you need to know is what to feed into the procedure "homology" and how to interpret what comes out of it. The output is easy to understand - it is a pair of lists. The first list is a list of the betti numbers, from the lowest dimension to the highest. The second list is a list of the torsion coefficients in each dimension, again from the lowest to the highest.
To specify a simplicial complex to "homology", we use the same definition of an abstract simplicial complex that most people are familiar with, namely a set of sets satisfying certain properties. So, for example,
homology({{}, {1},{2}, {1,2}});
will compute the homology of a line segment. This data structure can be awkward if the space is just a little complicated, so I have a few tricks to make life easier. First of all, you really should only have to give the set consisting of the highest dimensional simplices, since this determines the complex completely. The routine "complx", the first one below, will take such a set and add to it what is need to make it an official simplicial complex.
This is part of the homology procedure, so you don't have to do it. If you do input a valid complex into homology, then that is ok too - complx won't mess it up. A few more tricks and procedures for building complexes are given in the examples at the end of the worksheet.
If you want to use "homology" now, just enter the section below keep hitting enter until you get to the bottom of the worksheet, where the examples are. You can ignore all of the code and the comments and start computing.
WARNING - each section below assumes that you have executed the code that occurs prior to it. So if you jump ahead to a section you will get errors from maple since it won't recognize the names of the procedures and spaces.
<Text-field style="_cstyle282" layout="Heading 1"><Font bold="true" size="18">The procedures with explanations</Font></Text-field>
A few routines need to be loaded: from linalg, we need "Smith", which is applied to the boundary operators to put them in normal form. "powerset" is used in the procedure "complx". Then there are four list operations I like to use: "card" is the cardinality of a list or set, append appends an element to the back of a list, "replace(l, i, x)" replaces the ith element of l with x, and "delete(l, i)" deletes the ith element of a list l.
with(linalg):
with(combinat, powerset, choose):
card := l -> nops(l):
append := (l, x) -> [op(l), x]:
delete := (l,i) -> subsop(i=NULL,l):
replace := (l,i,x) -> subsop(i=x,l):
The rountine "complx" will take a set of simplices and make it into a simplicial complex by adding whatever simplices are needed. The basic data structure used for computation in this worksheet is a simplicial complex, but a complex is determined by the simplices that are maximal with respect to inclusion, so it the user may define a complex that way, and homology will use "complx" to fill it out.
complx := proc(l)
local simplices, i:
simplices := {{}}:
for i from 1 to card(l) do
simplices := simplices union {op(powerset(l[i]))}:
od:
simplices:
end:
For example, the simplicial complex { {}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, {1, 4} }, which represents a topological disc with a line segment stuck to it, is determined by { {1, 2, 3}, {1, 4}}:
X := complx({ {1, 2, 3}, {1, 4}});
"chains" takes a simpicial complex and a natural number n and creates a list of the n-dimensional simplices of l. This is important because these simplices form the basis of a vector space (module) of n-chains, and to write down matrices one needs for the basis vectors to be ordered. (The ordering is arbitrary.)
THIS IS A TECHNICAL FUNCTION NEEDED FOR "Homology".
chains := proc(l,n)
local simplices, i:
simplices := []:
for i from 1 to card(l) do
if card(l[i])=n+1
then
simplices := append(simplices, sort(l[i])):
fi:
od:
simplices:
end:
For example:
chains(X, 1);
"stratify" takes a complex and applies "chains" to it for each dimension of the complex, producing a list of ordered bases for the chains in each dimension.
THIS IS A TECHNICAL FUNCTION NEEDED FOR "Homology".
stratify := proc(X)
local i, Y, b, fin:
Y := []:
fin := false:
i := -1:
while fin<>true do
b := chains(X, i):
if b=[]
then
fin := true:
else
Y := append(Y, b):
i := i+1:
fi:
od:
Y:
end:
stratify(X);
"wherein" is just for finding what position in a list l the element x occurs.
THIS IS A TECHNICAL FUNCTION NEEDED FOR "Homology".
wherein := proc(l, x)
local i, entry:
for i from 1 to card(l) do
if l[i]=x
then entry :=i:
fi:
od:
entry:
end:
"boundary" takes as input a SINGLE n dimensional simplex and the list of n-1 dimensional simplices of a complex and produces the matrix of the associated boundary operator. "boundary" is used in "d".
THIS IS A TECHNICAL FUNCTION NEEDED FOR "Homology".
boundary := proc(sim, nmos)
local i, v, sign, temp, j:
v := array(1..card(nmos)):
for i from 1 to card(nmos) do
v[i] := 0:
od:
sign := -1:
for i from 1 to card(sim) do
temp := delete(sim, i):
j := wherein(nmos, temp):
v[j] := (-1)^(i+1):
od:
evalm(v):
end:
For example:
boundary({1,3},[{3}, {1}, {2}, {4}]);d produces the normal form of a boundary operator. The boundary operator from the n-chains to the (n-1)-chains is a matrix with respect to the bases given to it. We put the boundary operator is Smith normal form, so that we can read off the topological data. The imput to d is a pair of basis, one for the n simplices and one for the n-1 simplices, and the output is a matrix.
THIS IS A TECHNICAL FUNCTION NEEDED FOR "Homology".
d := proc(ns, nmos)
local i, bo:
bo := []:
for i from 1 to card(ns) do
bo := append(bo,boundary(ns[i], nmos));
od:
ismith(transpose(matrix(bo))):
end:
For example:
d(stratify(X)[4], stratify(X)[3]);
"dgnl" is for pulling off the torsion coefficents from the boundary operators.
THIS IS A TECHNICAL FUNCTION NEEDED FOR "Homology".
dgnl := proc(A)
local i, torsion:
torsion := []:
for i from 1 to min(coldim(A), rowdim(A)) do
if A[i,i] > 1
then
torsion := append(torsion, A[i,i]):
fi:
od:
torsion:
end:
Here is the main routine:
"bops" is just a list of the boundary operators.
"basislist" is a list of bases for the chains in each dimension.
Homology := proc(X)
local i, dim, bops, basislist, mats, Betti, Torsion, C:
Betti := []:
Torsion := []:
bops := []:
C := complx(X):
basislist := stratify(C):
dim := card(basislist):
for i from 1 to dim-1 do
bops := append(bops , d(basislist[i+1], basislist[i])):
od:
mats := bops:
for i from 1 to card(mats)-1 do:
Betti := append(Betti, rowdim(transpose(mats[i]))
- rank(transpose(mats[i])) - rank(mats[i+1])):
od:
Betti:= append(Betti, coldim(mats[card(mats)])
- rank(transpose(mats[card(mats)]))):
Betti := replace(Betti, 1, Betti[1] + 1 ):
for i from 2 to card(mats) do
Torsion := append(Torsion, dgnl(mats[i])):
od:
Torsion := append(Torsion, []):
[Betti, Torsion]:
end:
<Text-field style="_cstyle283" layout="Heading 1"><Font bold="true" size="18">Basic examples</Font></Text-field>
The homology of a point:
Homology({{0}});
The homology of a line segment:
Homology({{1, 2}});
The homology of S^1:
S1 := { {1,2},{2,3},{3,1} }:
Homology( S1 );
The figure 8 space has two generators for H1:
figure8 := { {1,2},{2,3},{3,1}, {3,a}, {a,b}, {b,3} };
Homology(figure8);
The zeroth homology group counts the number of connected components:
Homology( S1 union { {a}, {b}, {c} } );
Here is a rountine that will make a simplex of any dimension for you:
simplx := proc(n)
local i:
{seq(i,i=1..n+1)}:
end: simplx(3);Homology(simplx(3));
A square:
squar := { {1,2,5}, {2,5,6}, {2,3,6}, {3,6,7}, {3,4,7}, {4,7,8} };
Now compute the homology: It should have only one non-trivial group, the zeroth group, with is isomorphic to Z, the integers and hence has rank 1. It has no torsion.
Homology(squar);
"subs"is a cute way to make quotient spaces! Here we glue the edges of the square together.
cylinder := subs(4=1,8=5,squar);
The cylinder is not simply, connected: the first homology group is Z.
Homology(cylinder);
A "famous" topological space!:
mobius_strip := subs(4=5,8=1,squar);Homology(mobius_strip);
Next we want to build a torus. But careful - we don't have enough triangles in squar to form a torus as a quotient. So we make a few copies and glue them together.
squar2 := subs(1=5,2=6,3=7,4=8,subs(5=9,6=10, 7=11, 8=12, squar));squar3:= subs(5=9,6=10,7=11,8=12,subs(9=13,10=14, 11=15, 12=16, squar2));bigsquare := squar3 union squar union squar2;bigcylinder := subs(13=1, 14=2,15=3,16=4, bigsquare);Homology(bigcylinder);torus := subs(4=1,8=5,12=9, bigcylinder);Homology(torus);klein := subs(4=1,8=9,12=5, bigcylinder);
The Klein bottle has torsion:
Homology(klein);
S2 is not hard to triangulate:
tetrahedron := { {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}};Homology(tetrahedron);
There is a better way to build spheres - use the "choose" function to generate the faces of the n dimensional tetrahedron:
(Note - in the older version of Maple, choose only applies to lists. If you in this situation, use the function defined below called "setchoose".)
S3 := choose({1,2,3,4,5},4);Homology(S3);
It is handy to have this a a function:
sphere := n -> choose(simplx(n+1),n+1):
S2 := sphere(2);
The one point union of S^1 and S^2: just make sure they have a point in common.
newS2 := choose({1,b,c,d},3);Homology(newS2);Homology(S1 union newS2);
<Text-field style="_cstyle306" layout="Heading 1"><Font bold="true" size="18">Operations on spaces and some more examples</Font></Text-field>
Here are some of the spaces that appear above:
S1 := { {1,2},{2,3},{3,1} }:
figure8 := { {1,2},{2,3},{3,1}, {3,a}, {a,b}, {b,3} }:
squar := { {1,2,5}, {2,5,6}, {2,3,6}, {3,6,7}, {3,4,7}, {4,7,8} }:
cylinder := subs(4=1,8=5,squar):
mobius_strip := subs(4=5,8=1,squar):
bigsquare := {{4, 7, 8}, {5, 6, 9}, {6, 9, 10}, {7, 10, 11}, {6, 7, 10}, {8, 11, 12}, {7, 8, 11}, {10, 13, 14}, {9, 10, 13}, {11, 14, 15}, {10, 11, 14}, {12, 15, 16}, {11, 12, 15}, {1, 2, 5}, {2, 5, 6}, {2, 3, 6}, {3, 6, 7}, {3, 4, 7}}:
bigcylinder := subs(13=1, 14=2,15=3,16=4, bigsquare):
torus := subs(4=1,8=5,12=9, bigcylinder):
klein := subs(4=1,8=9,12=5, bigcylinder):
tetrahedron := { {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}}:
S2 := {{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}:
S3 := {{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}}:
A new operation: "cone" constructs the simpicial complex of a given complex and cone point.
cone := proc(C, conepoint)
local i, cone:
cone := {{}}:
for i from 1 to card(C) do
cone := cone union {{conepoint} union C[i]}:
od:
cone:
end:
cone(S1, N);
Another way to compute the homology of S2: write it as a union of cones.
Homology(cone(S1, N) union cone(S1, S));
This leads to the notion of suspension:
suspension := proc(C, p, q)
cone(C, p) union cone (C, q):
end:
Here is an interesting space :
Homology(suspension(torus, N, S));
The Euler characteristic:
oiler := proc(C)
local i, eulerchar, X:
eulerchar := 0:
X := stratify(complx(C)):
for i from 2 to card(X) do
eulerchar := eulerchar + card(X[i])*((-1)^i):
od:
eulerchar:
end: oiler(torus);S2 := choose({1,2,3,4},3);
oiler(S2);oiler(klein);
The connected sum of two spaces is formed by removing a solid ball from each space and gluing the spaces along the boundaries of the ball. In dimensions > 2 how you glue matters.
WARNING - this connected sum chooses the gluing arbitrarily. Two simplices are removed and their vertices indentified, but how they are ordered is random at this time. Also, no checking is done to see if both of the manifolds have the same dimension.
tag0 := C -> map( S-> map(x->[x, 0],S),C):
tag1 := C -> map( S-> map(x->[x, 1],S),C):
conn_sum := proc(X, Y)
local i, A, B, asimplex, bsimplex, alist, blist:
A := complx(tag0(X)):
B := complx(tag1(Y)):
alist := stratify(A):
blist := stratify(B):
asimplex := alist[card(alist)][1]:
bsimplex := blist[card(blist)][1]:
A := A minus {asimplex}:
B := B minus {bsimplex}:
for i from 1 to card(asimplex) do
B := subs(bsimplex[i]=asimplex[i], B):
od:
A union B:
end:
conn_sum(S1, S1);Homology(conn_sum(S1, S1));C := conn_sum(torus, torus):
Homology(C);
oiler(C);C:= conn_sum(S2, S2):
Homology(C);
oiler(C);C := conn_sum(torus, S2):
Homology(C);oiler(C);C := conn_sum(torus, klein):
Homology(C);oiler(C);"bin" is a routine that takes a set and a subset and produces the corresponding binary string. THIS IS A TECHNICAL FUNCTION NEEDED FOR "prod".
bin := proc(A, B)
local ii, bs;
bs := []:
for ii from 1 to card(A) do
if member(A[ii], B) then
bs := append(bs, 1)
else
bs := append(bs, 0):
fi:
od:
bs:
end proc:
"sproduct" computes the product of two simplices.THIS IS A TECHNICAL FUNCTION NEEDED FOR "prod".
sproduct := proc(s1, s2)
local ii, p, subsets, bs, simplices,
sim, m, n, Mi, S, i1, i2, j1, j2, jj,
S1, S2;
n := card(s1) - 1:
m := card(s2) - 1:
S := [seq(jj, jj=1..(m+n))]:
Mi := min(m,n):
subsets := choose(S, Mi):
if Mi=m then S1 := s2: S2 := s1: fi:
if Mi=n then S1 := s1: S2 := s2: fi:
simplices := {}:
for ii from 1 to card(subsets) do
bs := bin(S, subsets[ii]):
sim := [[S1[1], S2[1]]]:
i1 := 1: i2 := 1:
j1 := 1: j2 := 1:
for jj from 1 to card(bs) do:
i1 := i1 + bs[jj]:
i2 := i2 + 1-bs[jj]:
sim := append(sim, [S1[i1],S2[i2]]):
od:
simplices := simplices union {sim}
od:
simplices:
end proc:sproduct({1,2},{4,5,6});prod := proc(A, B)
local simplices, Atop, Btop, ii, jj, Astrat, Bstrat:
Astrat := stratify(complx(A)):
Bstrat := stratify(complx(B)):
simplices := {}:
Atop := Astrat[card(Astrat)]:
Btop := Bstrat[card(Bstrat)]:
for ii from 1 to card(Atop) do
for jj from 1 to card(Btop) do
simplices := simplices union sproduct(Atop[ii], Btop[jj]):
od:
od:
simplices:
end proc:
prod := proc(A, B)
local simplices, ii, jj:
simplices := {}:
for ii from 1 to card(A) do
for jj from 1 to card(B) do
simplices := simplices union sproduct(A[ii], B[jj]):
od:
od:
simplices:
end proc:
S1xS1 := prod(S1,S1);Homology(S1xS1);S1xS2 := prod(S1, S2):
Homology(S1xS2);S2xS2 := prod(S2, S2):
card(S2xS2);Homology(S2xS2);card(complx(S2xS2));