Draw some simple dynamical systems...
Solution.
Rather than manually finding these presentations, I’m going to build a Python script that does it for me. I leveraged some common libraries, includeing NetworkX for the "digraph" object, NumPy for linear algebra. I used Matplotlib for visuals during development, but I’ll map to LaTeX for this document. Our endomap \(\alpha\) might be defined as follows:
2
networkx.org3
numpy.org4
matplotlib.orgimport numpy as np
import networkx as nx
import matplotlib.pyplot as plt
x_nodes = ["X"+str(i) for i in range(9)]
x_edges = [
(x_nodes[0],x_nodes[4]),
(x_nodes[1],x_nodes[5]),
(x_nodes[2],x_nodes[6]),
(x_nodes[3],x_nodes[8]),
(x_nodes[4],x_nodes[5]),
(x_nodes[5],x_nodes[6]),
(x_nodes[6],x_nodes[7]),
(x_nodes[7],x_nodes[5]),
(x_nodes[8],x_nodes[3])
]
XG = nx.DiGraph()
XG.add_nodes_from(x_nodes)
XG.add_edges_from(x_edges)
Since this directed graph represents an endomap, each node should have precisely one "successor". We can use this property to implent our endomap as a function on the graph:
def follow_endomap(G,n):
return list(G.successors(n))[0]
We can then use the algorithm described in the text to produce a "presentation" from a given endomap. I tried
def make_presentation(G):
G_nodes = list(G.nodes())
ones_G = np.full((len(G_nodes),),1)
GA = nx.adjacency_matrix(G)
G_arrows_in = np.matmul(ones_G,GA.toarray())
G_arrows_by_node = sorted(zip(range(len(G_nodes)),G_arrows_in), key=lambda x: x[1])
G_presentation = {}
G_relations = {}
for k,v in G_arrows_by_node:
print(f"Checking node {k} with {v} arrows in")
if v == 0:
print(f"Adding root generator {G_nodes[k]}")
G_presentation[G_nodes[k]] = (G_nodes[k],v)
next_node = follow_endomap(G,G_nodes[k])
steps = 1
while not next_node in G_presentation:
print(f"Adding follow up node {next_node}: {steps} from {G_nodes[k]}")
G_presentation[next_node] = (G_nodes[k],steps)
next_node = follow_endomap(G,next_node)
steps += 1
print(f"next node {next_node} already has presentation")
G_relations[G_nodes[k]] = ((G_nodes[k],steps),G_presentation[next_node])
elif v == 1:
print(f"Only 1 way into node {k}")
if G_nodes[k] in G_presentation:
print("already has a presentation")
else:
print("Found potential loop")
G_presentation[G_nodes[k]] = (G_nodes[k],0)
next_node = follow_endomap(G,G_nodes[k])
steps = 1
while not next_node in G_presentation:
print(f"Adding follow up node {next_node}: {steps} from {G_nodes[k]}")
G_presentation[next_node] = (G_nodes[k],steps)
next_node = follow_endomap(G,next_node)
steps += 1
print(f"next node {next_node} already has presentation")
G_relations[G_nodes[k]] = ((G_nodes[k],steps),G_presentation[next_node])
else:
print(f"More than 1 way in")
return {
"generators":list(G_relations.keys()),
"relations":list(G_relations.values())
}
endomap_alpha = make_presentation(XG)
print(endomap_alpha)
This code produced the following output:
Checking node 0 with 0 arrows in
Adding root generator X0
Adding follow up node X4: 1 from X0
Adding follow up node X5: 2 from X0
Adding follow up node X6: 3 from X0
Adding follow up node X7: 4 from X0
next node X5 already has presentation
Checking node 1 with 0 arrows in
Adding root generator X1
next node X5 already has presentation
Checking node 2 with 0 arrows in
Adding root generator X2
next node X6 already has presentation
Checking node 3 with 1 arrows in
Only 1 way into node 3
Found potential loop
Adding follow up node X8: 1 from X3
next node X3 already has presentation
Checking node 4 with 1 arrows in
Only 1 way into node 4
already has a presentation
Checking node 7 with 1 arrows in
Only 1 way into node 7
already has a presentation
Checking node 8 with 1 arrows in
Only 1 way into node 8
already has a presentation
Checking node 6 with 2 arrows in
More than 1 way in
Checking node 5 with 3 arrows in
More than 1 way in
{
'generators': ['X0', 'X1', 'X2', 'X3'],
'relations': [
(('X0', 5), ('X0', 2)),
(('X1', 1), ('X0', 2)),
(('X2', 1), ('X0', 3)),
(('X3', 2), ('X3', 0))
]
}
This matches up with our expected presentation for \(X^{\circlearrowright \alpha}\) with the substitions \(a = X_1\text{,}\) \(b = X_2\text{,}\) \(c = X_3\text{,}\) and \(d = X_4\text{.}\) The relations are expressed as a ordered pair based on the number of "presses" from a specified generator. This the equation \(\alpha^5 a = \alpha^2 a\) becomes
(('X0', 5), ('X0', 2)), \(\alpha b = \alpha^2 a\) becomes (('X1', 1), ('X0', 2)), \(\alpha c = \alpha^3 a\) becomes (('X2', 1), ('X0', 3)), and \(\alpha^2 d = d\) becomes (('X3', 2), ('X3', 0)).We can use a similar process to find a presentation for \(Y^{\circlearrowright \beta}\) as well with the following code.
y_nodes = ["Y"+y for y in ["p", "q", "r", "s", "t", "v", "u", "m", "l", "w", "x", "y", "z"]]
y_edges = [
(y_nodes[0],y_nodes[2]),
(y_nodes[1],y_nodes[2]),
(y_nodes[2],y_nodes[4]),
(y_nodes[3],y_nodes[4]),
(y_nodes[4],y_nodes[5]),
(y_nodes[5],y_nodes[6]),
(y_nodes[6],y_nodes[3]),
(y_nodes[7],y_nodes[8]),
(y_nodes[8],y_nodes[7]),
(y_nodes[9],y_nodes[10]),
(y_nodes[10],y_nodes[11]),
(y_nodes[11],y_nodes[9]),
(y_nodes[12],y_nodes[11])
]
YG = nx.DiGraph()
YG.add_nodes_from(y_nodes)
YG.add_edges_from(y_edges)
endomap_beta = make_presentation(YG)
print(endomap_beta)
The output of the above code is the following presentation:
{
'generators': ['p', 'q', 'z', 'm'],
'relations': [
(('p', 6), ('p', 2)),
(('q', 1), ('p', 1)),
(('z', 4), ('z', 1)),
(('m', 2), ('m', 0))
]
}
Using the notation in the text, our corresponding relations would be \(\beta^6 p = \beta^2 p\text{,}\) \(\beta q = \beta p\text{,}\) \(\beta^4 z = \beta z\text{,}\) and \(\beta^2 m = m\text{.}\)
It seems like this method would be characterized as depth first search for the presentation. Depending on what order the nodes of the nodes used to express the maps, the above algorithm may produce a different result.
For example, suppose we defined X with the nodes in reverse:
XG2 = nx.DiGraph() x2_nodes = [x_nodes[-1-i] for i in range(len(x_nodes))] print(x2_nodes) XG2.add_nodes_from(x2_nodes) XG2.add_edges_from(x_edges) endomap_alpha_prime = make_presentation(XG2) print(endomap_alpha_prime)
We get the following output:
['X8', 'X7', 'X6', 'X5', 'X4', 'X3', 'X2', 'X1', 'X0']
Checking node 6 with 0 arrows in
Adding root generator X2
Adding follow up node X6: 1 from X2
Adding follow up node X7: 2 from X2
Adding follow up node X5: 3 from X2
next node X6 already has presentation
Checking node 7 with 0 arrows in
Adding root generator X1
next node X5 already has presentation
Checking node 8 with 0 arrows in
Adding root generator X0
Adding follow up node X4: 1 from X0
next node X5 already has presentation
Checking node 0 with 1 arrows in
Only 1 way into node 0
Found potential loop
Adding follow up node X3: 1 from X8
next node X8 already has presentation
Checking node 1 with 1 arrows in
Only 1 way into node 1
already has a presentation
Checking node 4 with 1 arrows in
Only 1 way into node 4
already has a presentation
Checking node 5 with 1 arrows in
Only 1 way into node 5
already has a presentation
Checking node 2 with 2 arrows in
More than 1 way in
Checking node 3 with 3 arrows in
More than 1 way in
{
'generators': ['X2', 'X1', 'X0', 'X8'],
'relations': [
(('X2', 4), ('X2', 1)),
(('X1', 1), ('X2', 3)),
(('X0', 2), ('X2', 3)),
(('X8', 2), ('X8', 0))
]
}
This is an "equivalent presentation" for \(X^{\circlearrowright \alpha}\text{.}\) We have the same generators still, but they’re listed in different order and our relations are slightly different. The equivalent expressions are \(\alpha^4 c = \alpha^1 c\text{,}\) \(\alpha b = \alpha^3 c\text{,}\) \(\alpha^2 a = \alpha^3 c\text{,}\) and \(\alpha^2 d = d\text{.}\)
I’m thinking that my task for Exercise 9 will be a little easier if I can standardize my relations and generators in a unified manner that makes these "equivalent presentations" easier to identify. I’m wondering if using a "breadth first search" instead of a "depth first search" might allow me to more readily identify the cylces of each length.
