[GAP Forum] RE: Finding the maximal subgroup of S_n such that a
subpace V of R^n is invariant
Bulutoglu Dursun A Civ AFIT/ENC
Dursun.Bulutoglu at afit.edu
Fri Oct 22 20:54:41 BST 2004
Dear GAP-Forum and Jan,
In my problems n is large (1000<n). I can convert the suggested
algorithm into random heuristic search algorithm that would work for
1000<n. I am not sure how good this converted algorithm would perform. I
was wondering if there are any theoretical results I could use that
would make my search more efficient. I was wondering whether people ever
considered this problem theoretically.
Thank you for your attention.
Dursun.
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
More information about the Forum
mailing list