7
$\begingroup$

I want to compute the automorphism group of a matroid. This reduces to the following (more general) problem:

Suppose I have a list of sets $\{\{b_{11},\dots,b_{1k}\},\dots,\{b_{k1},\dots,b_{kk}\}\}$ where each $b_{ij}$ is in $\{1,\dots,n\}$. The symmetric group $S_n$ acts on this set by: $$\begin{align}&s\cdot\{\{b_{11},\dots,b_{1k}\},\dots,\{b_{k1},\dots,b_{kk}\}\} \\ &= \{\{sb_{11},\dots,sb_{1k}\},\dots,\{sb_{k1},\dots,sb_{kk}\}\}\end{align}$$

I want to find those elements of the symmetric group on $n$ elements that stabilize the entire set $\{\{b_{11},\dots,b_{1k}\},\dots,\{b_{k1},\dots,b_{kk}\}\}$.

The command GroupSetwiseStabilizer seems relevant but doesn't quite do what I want.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I think this does it by brute force. Not sure if there is a better way: $\endgroup$
    – Madeline Brandt
    Commented Mar 18, 2021 at 17:44
  • $\begingroup$ By the way, are these bona fide sets (orderless), or are they Mathematica lists (where order matters)? Just checking, since it says "list of sets"! $\endgroup$
    – thorimur
    Commented Mar 18, 2021 at 20:07
  • $\begingroup$ (I prettified the post (as is usual practice—hope that's ok) using latex, but if they're Mathematica lists, I'd go for either tuples in latex, or code fences instead!) $\endgroup$
    – thorimur
    Commented Mar 18, 2021 at 20:10
  • $\begingroup$ These are just orderless sets, thanks for the clarification! And thanks for fixing the post :) $\endgroup$
    – Madeline Brandt
    Commented Mar 19, 2021 at 13:32

2 Answers 2

Reset to default
7
$\begingroup$

I think this does it by brute force. Not sure if there is a better way:

matroidauts[M_] := Module[{n, symgp, i, goodguys, M2},
n = Max[Flatten[M]];
symgp = GroupElements[SymmetricGroup[n]];
goodguys = {};
M2 = Sort[Sort /@ M];
For[i = 1, i <= Length[symgp], i = i + 1,
If[M2 == Sort[Sort /@ PermutationReplace[M2, symgp[[i]]]], 
AppendTo[goodguys, symgp[[i]]]]
 ];
PermutationGroup[goodguys]
]

Here are two examples (I also edited the code a bit to accommodate lists that don't come in a nice order to start).

Uniform matroid (2,4) -- the bases are all subsets of {1,2,3,4} of size 2:

basesu24 = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}};

And, it's automorphism group is the symmetric group on 4 elements:

Length[GroupElements[matroidauts[basesu24]]]
24

Fano matroid -- it is equivalent to work with the non-bases, which are listed below:

nonbasesFANO = {{7, 1, 4}, {7, 2, 5}, {7, 3, 6}, {1, 2, 6}, {2, 3, 
4}, {4, 5, 6}, {1, 3, 5}};

It's automorphism group is PSL(2,7) which has order 168:

Length[GroupElements[matroidauts[nonbasesFANO]]]
168
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ A working algorithm is always a good thing for testing purposes. Would you please also provide a test data set? $\endgroup$
    – Henrik Schumacher
    Commented Mar 18, 2021 at 19:28
  • $\begingroup$ Note: you don't need Return at the end of the function! Return is used to exit control structures like ; prematurely. When something comes at the end of the evaluation, you can simply leave it as is, and the function will evaluate to that. $\endgroup$
    – thorimur
    Commented Mar 18, 2021 at 20:34
  • $\begingroup$ I've updated to include 2 examples! Thanks for the tip about Return-- I've been using Mathematica for about 10 years and I'm still shocked at the "basic" things I don't know! $\endgroup$
    – Madeline Brandt
    Commented Mar 19, 2021 at 14:11
  • $\begingroup$ Slightly change code to avoid For, matroidauts[M_]:=Module[{n,symgp,i,goodguys,M2},n=Max[Flatten[M]]; symgp=GroupElements[SymmetricGroup[n]]; M2=Sort[Sort/@M]; goodguys=Select[M2==Sort[Sort/@PermutationReplace[M2,#]]&]@GroupElements[SymmetricGroup[n]]; PermutationGroup[goodguys]] $\endgroup$
    – AsukaMinato
    Commented Mar 19, 2021 at 15:19
4
$\begingroup$

GroupStabilizer allows you to include an action function f via GroupStabilizer[group, {p1, p2, ...}, f]! The syntax GroupStabilizer[group, {p1, p2, ...}, f] asks for the simultaneous stabilizer of all of the points {p1, p2, ...}, but here we just want the stabilizer of a single point blists, so we'll expect to use GroupStabilizer[group, {blists}, f].

If these are bona-fide sets at both levels (and not lists), we can canonicalize the form of a set by using Sort[Sort /@ blists] (sorting each inner list, then the whole list of lists). (You already have this in your solution implicitly, but just to put this here for the general audience; likewise for some of the following!)

So, our action function can be defined as follows. It expects to take in a point (here, blists) as first argument, and a group element g as a second argument. Luckily, the usual action PermutationReplace replaces at every level of the expression, so we can just apply it to the entire blists and then canonicalize:

f[blists_, g_] := Sort[Sort /@ PermutationReplace[blists, g]]

Then

matroidAuts[blists_] :=
    GroupStabilizer[SymmetricGroup[Max@Flatten[blists]],
                    {Sort[Sort /@ blists]}, f]

should work, but I haven't been able to test it. Let me know if it does!

Update: benchmarking

Using

RandomM[n_] := Sort[Sort /@ RandomInteger[{1, n}, {n, n}]]
m = M[8];

your code finishes in about half a second, whereas mine takes about 17 (!). I'm honestly pretty surprised that the built-in function is worse than brute-forcing it—what is the built-in function even doing?!

They seem to give the same (trivial group) answer. I don't know how they'd fare in the nontrivial case yet, but I can't imagine it'd be much different!

I tried speeding up your code by using Sow and Reap, and (separately) by using Select, but only shaved off a tiny bit. Select seemed faster by a hair. In general, though, when you're building big lists (which we're not in this benchmark, since the automorphism group is often trivial), AppendTo is slow. I'll put my code here in case it's of any use!

matroidauts2[M0_] := With[{M = Sort[Sort /@ M0]},
  PermutationGroup @
   Select[GroupElements[SymmetricGroup[Max[Flatten[M]]]], 
    (M == Sort[Sort /@ PermutationReplace[M, #]]) &]]

matroidauts3[M0_] := With[{M = Sort[Sort /@ M0]},
  PermutationGroup @
   First[Last[
     Reap[
       If[M == Sort[Sort /@ PermutationReplace[M, #]], Sow[#]] & /@       
         GroupElements[SymmetricGroup@Max@Flatten[M]];]]]]
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ For the examples above, your function matroidAuts is a bit faster! $\endgroup$
    – Madeline Brandt
    Commented Mar 19, 2021 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.