Solving Pinter 7.B.4 with a program

Question

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} $

Answer 1

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:

Answer 2

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.

Answer 3

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.

Answer 4

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.