Abstract Algebra IBL Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
[[Definition: The Order Of A Permutation]]
{{page>Definition: The Order Of A Permutation#definition}}

[[Problem: When Do Two Simple Shifts Span The SameSet]]
{{page>Problem: When Do Two Simple Shifts Span The Same Set#problem}}

(:include Definition.TheGameOfPermutationScoring:)


(:include Problem.TheGameOfPermutationScoringOnASquare:)

----

It would be nice if we could create a way to visually keeping track of which elements of $H$ have been taken.  Let me describe how we can do this with an example. Suppose you are playing the game on a square (as above).  Player one takes the permutation $(1,2,3,4)$.  Then player $2$ chooses the element $(1,2)(3,4)$.  Here's how we make the graph.  
*Each element in $H$ will represent a vertex.
*When player 1 chooses $(1,2,3,4)$, pick a color (I'll choose red) and then draw a red arrow from each permutation $\sigma\in H$ to the permutation $(1,2,3,4)\circ \sigma$.  In other words, we're going to draw a graph that shows what happens if we apply the automorphism $(1,2,3,4)$ after doing any other automorphism. If we start at the identity permutation $()=(1)(2)(3)(4)$, then we have $(1,2,3,4)\circ ()=(1,2,3,4)$, so we draw a red arrow from $()$ to $(1,2,3,4)$.  Similarly, starting at $(1,2,3,4)$ we draw an arrow to $(1,2,3,4)\circ(1,2,3,4)=(1,3)(2,4)$. Continuing in this fashion for each permutation gives us the graph below, with two red cycles of 4. 
%center%http://bmw.byuimath.com/aa/lib/exe/fetch.php?media=firststepincayleygraph.png
*The elements that are removed after choosing $(1,2,3,4)$ are any elements that we can get to by following a path  that contains $(1,2,3,4)$. These are the 4 automorphisms in the cycle on the left. 
*Now player 2 chooses $(1,2)(3,4)$. We now use a different color (I chose blue in the example below), and then at each vertex draw an arrow starting at $\sigma\in H$ and ending at $(1,2)(3,4)\circ \sigma$. The tricky part is finding a nice way to draw the graph without to many edge crossings (do you see how the outer circle flipped directions).  Both of the examples below are ways to represent this graph.  We can use an edge with an arrow on each end to illustrate that there is an arrow going both ways.
%center%http://bmw.byuimath.com/aa/lib/exe/fetch.php?media=cayleygraphsofd4byhand.png
*The arrows in the graph above represent composition by either $(1,2,3,4)$ or $(1,2)(3,4)$.  If you start at $(1,3)$ and want to compute $(1,2,3,4)\circ(1,2)(3,4)\circ(1,3)$, then you just have to start at $(1,3)$, follow the blue arrow to get to $(1,2)(3,4)\circ(1,3)=(1,4,3,2)$, and then follow the red arrow to get to $(1,2,3,4)\circ(1,4,3,2)$.

The mathematical program Sage can also help with the computations. The command PermutationGroup() below creates the span of the permutations listed. The command cayley_graph() creates the graph described above, but only shows the part of the graph that contains the permutations listed. Try executing the block of code below.
<sage>
g1 = PermutationGroup(["(1,2,3,4)"])   #The set g1 is the span of the permutations listed.
d1=g1.cayley_graph()                   #This creates the Cayley graph of the g1. 
d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True) #This shows the Cayley graph. 
print(g1.list())                       #This print a list of the elements in g1. 

g2 = PermutationGroup(["(1,2,3,4)", "(1,2)(3,4)"])
d2=g2.cayley_graph()
d2.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)
print(g2.list())
</sage>



(:include Problem.ComposingPermutationsUsingDisjointCycleNotation:)
----
(:include Problem.CreatingCayleyGraphsOfSimpleShiftPermutations:)
----
When we create graphs with Sage, it always creates a graph of the span of the permutations given.  These graphs have a lot of really nice symmetry properties, and these properties are central to abstract algebra.

(:include Problem.PermutationScoringOnS3:)
----
(:include Definition.AClosedSetOfPermutations:)

(:include Problem.TheSpanOfASetOfPermutationsIsClosed:)
----










{{tag>bmwoodruff}}
Abstract Algebra IBL Wiki

User Tools

Site Tools

Page Tools
