Solving Pinter 7.B.4 with a program

Here is exercise 7.B.4 from 'A Book of Abstract Algebra' by Charles C. Pinter.

A solution to this using a C# program is posted.

Is there another good approach using a computer program?

Any language is welcome.

The subgroup of $S_5$ generated by

$f = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\2 & 1 & 3 & 4 & 5\end{pmatrix} \qquad g = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\1 & 2 & 4 & 5 & 3\end{pmatrix}$

has six elements. List them, then write the table of this group:

$\varepsilon = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\1 & 2 & 3 & 4 & 5\end{pmatrix}$

$f = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\2 & 1 & 3 & 4 & 5\end{pmatrix}$

$g = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\1 & 2 & 4 & 5 & 3\end{pmatrix}$

$h = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\ \, \end{pmatrix}$

$k = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\ \,\end{pmatrix}$

$l = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\ \,\end{pmatrix}$

$\begin{array}{c|ccc} \circ & \varepsilon & f & g & h & k & l \\ \hline \varepsilon \\ f \\ g \\ h \\ k \\ l \end{array}$

• I feel like there's a MATLAB solution to this - I just can't quite pin it down. We could define two anon functions to act as the generators. – Sean Roberson Jul 5 '17 at 0:04

You don't need to use a computer program for the computation. The two given maps act nontrivially on disjoint subsets of $\{1, \dots, 5\}$, so the map $\langle{f, g\rangle} \to \mathbb{Z}_2 \oplus \mathbb{Z}_3$ given by $f \to (1,0)$ and $g\to (0, 1)$ is a well-defined isomorphism.

SageMath provides built-in methods for such computations

sage: S5 = SymmetricGroup(5)
sage: f = S5( (1,2)); g = S5( (3,4,5)) #cycle notation
# or  f = S5([2,1,3,4,5]); g = S5( [1,2,4,5,3])
sage: S5fg = S5.subgroup([f,g])
sage: S5fg.multiplication_table(names='elements')


$$\scriptsize{ \begin{array}{c|*{6}{c}} {\ast}&()&(3,4,5)&(1,2)&(3,5,4)&(1,2)(3,4,5)&(1,2)(3,5,4)\\\hline {}()&()&(3,4,5)&(1,2)&(3,5,4)&(1,2)(3,4,5)&(1,2)(3,5,4)\\ {}(3,4,5)&(3,4,5)&(3,5,4)&(1,2)(3,4,5)&()&(1,2)(3,5,4)&(1,2)\\ {}(1,2)&(1,2)&(1,2)(3,4,5)&()&(1,2)(3,5,4)&(3,4,5)&(3,5,4)\\ {}(3,5,4)&(3,5,4)&()&(1,2)(3,5,4)&(3,4,5)&(1,2)&(1,2)(3,4,5)\\ {}(1,2)(3,4,5)&(1,2)(3,4,5)&(1,2)(3,5,4)&(3,4,5)&(1,2)&(3,5,4)&()\\ {}(1,2)(3,5,4)&(1,2)(3,5,4)&(1,2)&(3,5,4)&(1,2)(3,4,5)&()&(3,4,5)\\ \end{array}}$$

But as @anomaly says in their comment, you don't have to use a computer to do such problems.

• I learned GAP a few years ago to make such a table for the Frobenius group of order 21 (iirc). Wish I'd known about Sage then. I appreciate the GAP project's efforts immensely. (In fact, I'd bet Sage's algebra library is a wrapper around it.) They've made some really useful software, but it is not easy to use. – Tyler Jul 5 '17 at 2:56

Here's a solution in C#:

using System.Collections.Generic;
using System.Linq;

using static System.Console;

namespace pinter_7.A._1_permutations
{
class Program
{
static void display(Dictionary<int,int> f)
{
foreach (var key in f.Keys.OrderBy(elt => elt)) Write($"{key} "); WriteLine(); foreach (var key in f.Keys.OrderBy(elt => elt)) Write($"{f[key]} "); WriteLine();
}

static Dictionary<int,int> compose(Dictionary<int,int> f, Dictionary<int,int> g)
{
var result = new Dictionary<int, int>();

foreach(var kv in g) result[kv.Key] = f[kv.Value];

return result;
}

static bool equal(Dictionary<int,int> f, Dictionary<int,int> g) => f.Keys.All(x => f[x] == g[x]);

static bool check_and_add(Dictionary<string, Dictionary<int,int>> items, List<string> names)
{
foreach (var x in items)
{
foreach (var y in items)
{
var result = compose(x.Value, y.Value);

if (items.Values.ToList().Any(elt => equal(result, elt)))
{
var item = items.First(elt => equal(result, elt.Value)).Key;
}
else
{
WriteLine($"adding {names.First()} = {x.Key} ∘ {y.Key}"); items.Add(names.First(), result); names.RemoveAt(0); return true; } } } return false; } static void table(Dictionary<string, Dictionary<int,int>> items) { Write("∘ |"); foreach (var y in items) Write($"{y.Key,-5}|"); WriteLine();
Write("-----|");   foreach (var y in items) Write("-----|");       WriteLine();

foreach (var x in items)
{
Write($"{x.Key,-5}|"); foreach (var y in items) { var result = compose(x.Value, y.Value); if (items.Values.ToList().Any(elt => equal(result, elt))) { var item = items.First(elt => equal(result, elt.Value)).Key; Write($"{item,-5}|");
}
else
{
Write("{0,-5}|", \$"{x.Key} ∘ {y.Key}");
}
}
WriteLine();
}
}

static void Main(string[] args)
{
{
// Pinter 7.B.4

var ε = new Dictionary<int, int> { { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 }, { 5, 5 } };
var f = new Dictionary<int, int> { { 1, 2 }, { 2, 1 }, { 3, 3 }, { 4, 4 }, { 5, 5 } };
var g = new Dictionary<int, int> { { 1, 1 }, { 2, 2 }, { 3, 4 }, { 4, 5 }, { 5, 3 } };

var items = new Dictionary<string, Dictionary<int, int>>() { { "ε", ε }, { "f", f }, { "g", g } };

var names = new List<string>() { "h", "k", "l" };

while (true)
{
WriteLine();

table(items);

WriteLine();

if (check_and_add(items, names) == false) break;
}

foreach (var elt in items)
{
WriteLine(elt.Key);
display(elt.Value);
WriteLine();
}
}
}
}
}


The program shows the intermediate tables and the elements it adds along the way:

It then lists the elements of the subgroup:

This should be easy to do without a computer, as mentioned.

With a computer, you should be able to do this with any language. Using something designed for algebraic computation is easiest.

In MAGMA, I would type

{x : x in sub<Sym(5)|(1, 2), (3, 4, 5)>};


and it would list out all of the elements (I have them is cycle notation). You can easily form the table from here. You can do something very similar in Sage, GAP, even in Python there is the SymPy package that lets you work with permutation groups.