[GAP Forum] Fw: Finding the maximal subgroup ...

[Steve Linton]

This came to the old address.

Begin forwarded message:

Date: Fri, 22 Oct 2004 12:46:11 +0200
From: Jan Draisma <Jan.Draisma at unibas.ch>
To: GAP Forum <GAP-Forum at dcs.st-and.ac.uk>
Subject: Re: Finding the maximal subgroup ...


Dear GAP-Forum and Dursun,


> Let V be an m dimensional subspace of R^n. Let S_n act on R^n and on V
> by permuting the coordinates of each vector in R^n. Thus S_n acts on R^n
> regularly.
> 	I was wondering whether there is any tool in GAP that I could
> use to find the maximal subgroup G of S_n such that V remains invariant
> under this action.  Obviously one can fix a basis for V and compute the
> symmetry group of the matrix formed by putting these basis vectors into
> a matrix. This symmetry group would be a subgroup of of G but I would
> like to be able to compute G or some subgroup of G that has as many
> elements of G as possible.

The brute force code below will work for those n for which listing all
elements of S_n is feasible. There should be more efficient algorithms,
though, using (the code for) `Stabiliser'. Over finite fields, one may
try to implement Grassmannians and compute the stabiliser of V there.

Syms:=function(V)
# V is a subspace of F^n for some field F, and this returns the
# subgroup of S_n stabilising V.
local B,Ann,Zo,L,n;

if Dimension(V)=0 then return(SymmetricGroup(Length(AsSet(V)[1])));
fi;

B:=List(Basis(V));
n:=Length(B[1]);
Ann:=TransposedMat(NullspaceMat(TransposedMat(B)));     #eqs defining
V;
Zo:=B*Ann;                                              #zero matrix
L:=Filtered(SymmetricGroup(n),pi->
        (List(B,v->Permuted(v,pi))*Ann = Zo));
return Group(L);

end;

Example:
n:=7;
Rn:=Rationals^n;
V:=Subspace(Rn,[[1,2,0,4,0,1,0],[2,2,0,0,2,0,1],
	[2,1,0,0,4,1,0],[2,2,0,2,0,0,1]]);
Syms(V);

Answer:
Group([ (), (1,2), (4,5), (1,2)(4,5) ])

Best wishes,

  Jan


-- 
Steve Linton	School of Computer Science  &
      Centre for Interdisciplinary Research in Computational Algebra
	     University of St Andrews 	 Tel   +44 (1334) 463269
http://www.dcs.st-and.ac.uk/~sal	 Fax   +44 (1334) 463278