permute-sage.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section5.4Sage

¶

A good portion of Sage's support for group theory is based on routines from GAP (Groups, Algorithms, and Programming) at www.gap-system.org, which is included in every copy of Sage. This is a mature open source package, dating back to 1986. (Forward reference here to GAP console, etc.)

As we have seen, groups can be described in many different ways, such as sets of matrices, sets of complex numbers, or sets of symbols subject to defining relations. A very concrete way to represent groups is via permutations (one-to-one and onto functions of the integers $1$ through $n$), using function composition as the operation in the group, as described in this chapter. Sage has many routines designed to work with groups of this type and they are also a good way for those learning group theory to gain experience with the basic ideas of group theory. For both these reasons, we will concentrate on these types of groups.

SubsectionPermutation Groups and Elements

The easiest way to work with permutation group elements in Sage is to write them in cycle notation. Since these are products of disjoint cycles (which commute), we do not need to concern ourselves with the actual order of the cycles. If we write (1,3)(2,4) we probably understand it to be a permutation (the topic of this chapter!) and we know that it could be an element of $S_4\text{,}$ or perhaps a symmetric group on more symbols than just 4. Sage cannot get started that easily and needs a bit of context, so we coerce a string of characters written with cycle notation into a symmetric group to make group elements. Here are some examples and some sample computations. Remember that Sage and your text differ on how to interpret the order of composing two permutations in a product.

G = SymmetricGroup(5)
sigma = G("(1,3)(2,5,4)")
sigma*sigma

rho = G("(2,4)(1,5)")
rho^3

If the next three examples seem confusing, or “backwards”, then now would be an excellent time to review the Sage discussion about the order of permutation composition in the subsection Groups of symmetries.

sigma*rho

rho*sigma

rho^-1*sigma*rho

There are alternate ways to create permutation group elements, which can be useful in some situations, but they are not quite as useful in everday use.

sigma1 = G("(1,3)(2,5,4)")
sigma1

sigma2 = G([(1,3),(2,5,4)])
sigma2

sigma3 = G([3,5,1,2,4])
sigma3

sigma1 == sigma2

sigma2 == sigma3

sigma2.cycle_tuples()

[sigma3(x) for x in G.domain()]

The second version of $\sigma$ is a list of “tuples”, which requires a lot of commas and these must be enclosed in a list. (A tuple of length one must be written like (4,) to distinguish it from using parentheses for grouping, as in 5*(4).) The third version uses the “bottom-row” of the more cumbersome two-row notation introduced at the beginning of the chapter — it is an ordered list of the output values of the permutation when considered as a function.

So we then see that despite three different input procedures, all the versions of $\sigma$ print the same way, and moreso they are actually equal to each other. (This is a subtle difference — what an object is in Sage versus how an object displays itself.)

We can be even more careful about the nature of our elements. Notice that once we get Sage started, it can promote the product $\tau\sigma$ into the larger permutation group. We can “promote” elements into larger permutation groups, but it is an error to try to shoe-horn an element into a too-small symmetric group.

H = SymmetricGroup(4)
sigma = H("(1,2,3,4)")
G = SymmetricGroup(6)
tau = G("(1,2,3,4,5,6)")
rho = tau * sigma
rho

sigma.parent()

tau.parent()

rho.parent()

tau.parent() == rho.parent()

sigmaG = G(sigma)
sigmaG.parent()

It is an error to try to coerce a permutation with too many symbols into a permutation group employing too few symbols.

tauH = H(tau)

Better than working with just elements of the symmetric group, we can create a variety of permutation groups in Sage. Here is a sampling for starters:

Sage Command	Description
SymmetricGroup(n)	Permutations on $n$ symbols, $n!$ elements
DihedralGroup(n)	Symmetries of an $n$-gon, $2n$ elements.
CyclicPermutationGroup(n)	Rotations of an $n$-gon (no flips), $n$ elements
AlternatingGroup(n)	Alternating group on $n$ symbols, $n!/2$ elements
KleinFourGroup()	A non-cyclic group of order 4

Table5.30Some Sage permutation groups

You can also locate Sage permutation groups with the groups catalog. In the next cell place your cursor right after the final dot and hit the tab-key. You will get a list of methods you can use to create permutation groups. As always, place a question-mark after a method and hit the tab-key to get online documentation of a method.

groups.permutation.

SubsectionProperties of Permutation Elements

Sometimes it is easier to grab an element out of a list of elements of a permutation group, and then it is already attached to a parent and there is no need for any coercion. In the following, rotate and flip are automatically elements of G because of the way we procured them.

D = DihedralGroup(5)
elements = D.list(); elements

rotate = elements[2]
flip = elements[3]
flip*rotate == rotate* flip

So we see from this final statement that the group of symmetries of a pentagon is not abelian. But there is an easier way.

D = DihedralGroup(5)
D.is_abelian()

There are many more methods you can use for both permutation groups and their individual elements. Use the blank compute cell below to create a permutation group (any one you like) and an element of a permutation group (any one you like). Then use tab-completion to see all the methods available for an element, or for a group (name, period, tab-key). Some names you may recognize, some we will learn about in the coming chapters, some are highly-specialized research tools you can use when you write your Ph.D. thesis in group theory. For any of these methods, remember that you can type the name, followed by a question mark, to see documentation and examples. Experiment and explore — it is really hard to break anything.

Here are some selected examples of various methods available.

A4 = AlternatingGroup(4)
A4.order()

A4.is_finite()

A4.is_abelian()

A4.is_cyclic()

sigma = A4("(1,2,4)")
sigma^-1

sigma.order()

A very useful method when studying the alternating group is the permutation group element method .sign(). It will return 1 if a permutation is even and -1 if a permutation is odd.

G = SymmetricGroup(3)
sigma = G("(1,2)")
tau = G("(1,3)")
rho = sigma*tau
sigma.sign()

rho.sign()

We can create subgroups by giving the main group a list of “generators.” These elements serve to “generate” a subgroup — imagine multiplying these elements (and their inverses) together over and over, creating new elements that must also be in the subgroup and also become involved in new products, until you see no new elements. Now that definition ends with a horribly imprecise statement, but it should suffice for now. A better definition is that the subgroup generated by the elements is the smallest subgroup of the main group that contains all the generators — which is fine if you know what all the subgroups might be.

With a single generator, the repeated products just become powers of the lone generator. The subgroup generated then is cyclic. With two (or more) generators, especially in a non-abelian group, the situation can be much, much more complicated. So let us begin with just a single generator. But do not forget to put it in a list anyway.

A4 = AlternatingGroup(4)
sigma = A4("(1,2,4)")
sg = A4.subgroup([sigma])
sg

sg.order()

sg.list()

sg.is_abelian()

sg.is_cyclic()

sg.is_subgroup(A4)

We can now redo the example from the very beginning of this chapter. We translate to elements to cycle notation, construct the subgroup from two generators (the subgroup is not cyclic), and since the subgroup is abelian, we do not have to view Sage's Cayley table as a diagonal reflection of the table in the example.

G = SymmetricGroup(5)
sigma = G("(4,5)")
tau = G("(1,3)")
H = G.subgroup([sigma, tau])
H.list()

text_names = ['id', 'sigma', 'tau', 'mu']
H.cayley_table(names=text_names)

SubsectionMotion Group of a Cube

¶

We could mimic the example in the text and create elements of $S_4$ as permutations of the diagonals. A more obvious, but less insightful, construction is to view the 8 corners of the cube as the items being permuted. Then some obvious symmetries of the cube come from running an axis through the center of a side, through to the center of the opposite side, with quarter-turns or half-turns about these axes forming symmetries. With three such axes and four rotations per axis, we get 12 symmetries, except we have counted the identity permutation two extra times.

Label the four corners of the square top with $1$ through $4\text{,}$ placing $1$ in the left-front corner, and following around clockwise when viewed from above. Use $5$ through $8$ for the bottom square's corner, so that $5$ is directly below $1\text{,}$ $6$ below $2\text{,}$ etc. We will use quarter-turns, clockwise, around each axis, when viewed from above, the front, and the right.

G = SymmetricGroup(8)
above = G("(1,2,3,4)(5,6,7,8)")
front = G("(1,4,8,5)(2,3,7,6)")
right = G("(1,2,6,5)(3,7,8,4)")
cube = G.subgroup([above, front, right])
cube.order()

cube.list()

Since we know from the discussion in the text that the symmetry group has $24$ elements, we see that our three quarter-turns are sufficient to create every symmetry. This prompts several questions which you can find in Exercise 5.5.4.