# Relabeling/matching variables of big data (in MultiplicationTable)

Let A and B be two sets of tables (from multiplication tables of a group, 24 by 24 as rows by columns), how can we effectively (and possibly also efficiently) find a way to map between them, if two groups are indeed isomorphism, under the relabelling of group elements?

Based on the strategy given in this post

A={{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24}, {2, 1, 4, 3, 6, 5, 8, 7, 12, 11, 10, 9, 14, 13,
16, 15, 18, 17, 20, 19, 22, 21, 24, 23}, {3, 4, 1, 2, 7, 8, 5, 6,
10, 9, 12, 11, 16, 15, 14, 13, 20, 19, 18, 17, 24, 23, 22, 21}, {4,
3, 2, 1, 8, 7, 6, 5, 11, 12, 9, 10, 15, 16, 13, 14, 19, 20, 17, 18,
23, 24, 21, 22}, {5, 7, 6, 8, 1, 3, 2, 4, 18, 17, 20, 19, 24, 21,
22, 23, 10, 9, 12, 11, 14, 15, 16, 13}, {6, 8, 5, 7, 2, 4, 1, 3, 17,
18, 19, 20, 23, 22, 21, 24, 11, 12, 9, 10, 13, 16, 15, 14}, {7, 5,
8, 6, 3, 1, 4, 2, 19, 20, 17, 18, 21, 24, 23, 22, 9, 10, 11, 12, 15,
14, 13, 16}, {8, 6, 7, 5, 4, 2, 3, 1, 20, 19, 18, 17, 22, 23, 24,
21, 12, 11, 10, 9, 16, 13, 14, 15}, {9, 12, 11, 10, 23, 24, 21, 22,
1, 4, 3, 2, 20, 19, 17, 18, 15, 16, 14, 13, 7, 8, 5, 6}, {10, 11,
12, 9, 22, 21, 24, 23, 3, 2, 1, 4, 17, 18, 20, 19, 14, 13, 15, 16,
5, 6, 7, 8}, {11, 10, 9, 12, 21, 22, 23, 24, 4, 1, 2, 3, 18, 17, 19,
20, 13, 14, 16, 15, 6, 5, 8, 7}, {12, 9, 10, 11, 24, 23, 22, 21, 2,
3, 4, 1, 19, 20, 18, 17, 16, 15, 13, 14, 8, 7, 6, 5}, {13, 15, 16,
14, 19, 17, 18, 20, 22, 23, 21, 24, 1, 4, 2, 3, 6, 7, 5, 8, 11, 9,
10, 12}, {14, 16, 15, 13, 20, 18, 17, 19, 21, 24, 22, 23, 2, 3, 1,
4, 5, 8, 6, 7, 10, 12, 11, 9}, {15, 13, 14, 16, 17, 19, 20, 18, 24,
21, 23, 22, 4, 1, 3, 2, 7, 6, 8, 5, 9, 11, 12, 10}, {16, 14, 13, 15,
18, 20, 19, 17, 23, 22, 24, 21, 3, 2, 4, 1, 8, 5, 7, 6, 12, 10, 9,
11}, {17, 20, 19, 18, 15, 14, 13, 16, 6, 7, 5, 8, 10, 9, 11, 12, 21,
24, 22, 23, 1, 3, 2, 4}, {18, 19, 20, 17, 16, 13, 14, 15, 5, 8, 6,
7, 11, 12, 10, 9, 22, 23, 21, 24, 2, 4, 1, 3}, {19, 18, 17, 20, 13,
16, 15, 14, 7, 6, 8, 5, 12, 11, 9, 10, 23, 22, 24, 21, 4, 2, 3,
1}, {20, 17, 18, 19, 14, 15, 16, 13, 8, 5, 7, 6, 9, 10, 12, 11, 24,
21, 23, 22, 3, 1, 4, 2}, {21, 23, 22, 24, 11, 9, 10, 12, 14, 13, 15,
16, 7, 6, 5, 8, 1, 4, 3, 2, 17, 19, 20, 18}, {22, 24, 21, 23, 10,
12, 11, 9, 13, 14, 16, 15, 8, 5, 6, 7, 2, 3, 4, 1, 18, 20, 19,
17}, {23, 21, 24, 22, 9, 11, 12, 10, 16, 15, 13, 14, 6, 7, 8, 5, 4,
1, 2, 3, 19, 17, 18, 20}, {24, 22, 23, 21, 12, 10, 9, 11, 15, 16,
14, 13, 5, 8, 7, 6, 3, 2, 1, 4, 20, 18, 17, 19}};
B = FiniteGroupData[{"SymmetricGroup", 4}, "MultiplicationTable"];
n = Length@A;
perms = Permutations[Range@n];
FlB = Flatten[B];
subst[list_] := Table[A[[list[[i]], list[[j]]]], {i, n}, {j, n}]
lnght[A$_] := Length@Union@Transpose@{Flatten[A$], FlB}
Min[lnght[subst[#]] & /@ perms]

There is a limitation of the Permutations[Range[24]], perhaps the system size is too large? This results in an output:

question 1. Can we still find a way out to do Permutations[Range[24]]? Or is there a more efficient way to find the group isomorphism?

question 2. How do we suggest a map between the two tables, say from {1 to 1}, {2 to ...}, {3 to ...}? If the map can be found?

Note: This will be the table look like in Grid:

• p.s. There is so far not yet a complete answer. – wonderich Apr 13 '18 at 3:43

For a start, the order of an element is invariant under group isomorphisms. This boils the number of permutations to test from $24! = 620448401733239439360000$ down to $6! \, 8! \, 9! = 10534551552000$. The order of the $i$th element can actually determined from row A[[i]] alone. The following function getGroupElementOrder does that for you:

getGroupElementOrders = Compile[{{a, _Integer, 1}, {g, _Integer}},
Block[{i = g, c = 1},
While[i != 1, c++; i = Compile`GetElement[a, i]];
c
],
RuntimeAttributes -> {Listable},
Parallelization -> True
];

n = Length[A];
ordersA = getGroupElementOrders[A, Range[n]];
ordersB = getGroupElementOrders[B, Range[n]];
elementsInAOfOrder = GroupBy[Transpose[{ordersA, Range[n]}], First -> Last]
elementsInBOfOrder = GroupBy[Transpose[{ordersB, Range[n]}], First -> Last]

<|1 -> {1}, 2 -> {2, 3, 4, 5, 8, 9, 12, 13, 16}, 4 -> {6, 7, 10, 11, 14, 15}, 3 -> {17, 18, 19, 20, 21, 22, 23, 24}|>

<|1 -> {1}, 2 -> {2, 3, 6, 7, 8, 15, 17, 22, 24}, 3 -> {4, 5, 9, 12, 13, 16, 20, 21}, 4 -> {10, 11, 14, 18, 19, 23}|>

No, you are "only" left to match members of elementsInAOfOrder[k] with elementsInBOfOrder[k] for $k = 2,3,4$ ...

• @ Henrik Schumacher, thanks, +1, indeed I was thinking about the diagonal, too. However, there are still many choices, how can we pin down precisely to a single mapping? [there is at least a single mapping if it exists, and one can find perhaps 4!=24 distinct mapping in total. If we restrict 1 maps to 1, then there should be at most 3!=6 mappings.] – wonderich Apr 12 '18 at 21:07
• Oh, pinning down to one unique isomorphism is in general impossible. There are groups with nontrivial automorphisms, you know... – Henrik Schumacher Apr 12 '18 at 21:12
• yes, just give any one is fine, as said, there are 24 possible mappings. Does your algorithm give any map for checking isomorphism? (in order to accept as an answer) – wonderich Apr 12 '18 at 21:19
• That's not a complete answer at all, sorry. – Henrik Schumacher Apr 12 '18 at 21:23