Orbit-construction in SYMMETRICA Actions of the form GX Action on the domain of functions

Action on the domain of functions

A permutation group G on the set X induces a group action on the set of all functions from X to a set Y.

For the following routines you have to specify the operating group G by giving a system of generators. The cardinality n of the set X is the degree of the permutations in G. In some cases you furthermore have to input the cardinality m of the set Y. In some cases, when we are dealing with characteristic functions, the cardinality of Y is already set to 2.

A very simple routine generating a set of all representatives of G-orbits on the set of all functions from {1,...,n} to {1,...,m} is  

INT all_orbits_right(g,m,reps) OP g,m,reps;
where g is a VECTOR of generators of the acting group G, m is the cardinality of Y and reps is a VECTOR object consisting of the representatives of the G-orbits. Such a representative f is written as a VECTOR of the form
[f(1),f(2),...,f(n)].
This routine does not use the homomorphism principle, the surjective method and the Read method for minimizing the number of minimality tests needed.

At first the Sims chain of the acting group is computed by  

INT strong_generators(a,b)  OP a,b;
where a is a VECTOR of generators of the permutation group G of degree n. b becomes an (n+1) × (n+1) MATRIX which is an upper triangular matrix. For i∈ {1,...,n} let CG(i) be the pointwise stabilizer of {1,...,i}, then the PERMUTATIONs in the i-1-th row of b are representatives of the cosets CG(i-1)/CG(i). For j≥ i the entry S_M_IJ(b,i-1,j-1) is a PERMUTATION π such that π(i)=j. The elements in S_M_IJ(b,i-1,i-1) are the identity permutation of degree n.

Then some minimality tests are applied, as described in the last chapter of [11].

The routine  

INT all_orbits_ksubsets(g,k,vec) OP g,k,reps;
computes a transversal of representatives of characteristic functions of k-subsets of X. g is a VECTOR of generators of G, k is an INTEGER object, indicating the cardinality of the subsets, reps is again a VECTOR of representatives. If k>n/2 (where n is the cardinality of X), then it computes the number of orbits of n-k-subsets of X.

There is a recursive routine  

INT all_orbits_ksubsets_rec(g,k,reps)  OP g,k,reps;
which uses the Read method in order to minimize the number of minimalityt tests needed. It computes a transversal of the characteristic functions of all s-sets 1≤ s≤ k. Again g is a system of generators of G, k indicates k and reps is a transversal of these representatives.
harald.fripertinger "at" uni-graz.at, May 26, 2011

Orbit-construction in SYMMETRICA Actions of the form GX Uni-Graz Mathematik Action on the domain of functions Valid HTML 4.0 Transitional Valid CSS!