zkd(1) - f31

1zkd(1)                           User Commands                          zkd(1)
2
3
4

NAME

6       zkd - condense a permutation
7

SYNOPSIS

9       zkd [OPTIONS] <Field> <Orbits> <Perm> <Kond>
10

DESCRIPTION

12       This  program reads an orbit file (Orbits) and a permutation from Perm.
13       It outputs the condensed form, i.e., a matrix over GF(q) to Kond.   The
14       field  must  be  specified  on the command line because the other input
15       data is all to do with permutations and the program would otherwise not
16       know which field was intended.  The orbit file must contain two integer
17       matrices containing the orbit numbers for  each  point  and  the  orbit
18       sizes, repectively. It is usually produced by the zmo program.
19
20       The  second  input  file,  Perm, must contain one or more permutations.
21       Notice that only the first permutation is read in  and  condensed.   If
22       there are more than one permutation, the others are ignored.  Unlike in
23       previous versions of this program, it is not assumed  that  the  orbits
24       are contiguous.
25
26   Integer condensation
27       If  Field  is the letter "Z", zkd condenses over the integers.  In this
28       case, Result is an integer matrix with the same dimensions  as  in  the
29       GF(q) case.
30

OPTIONS

32       -Q     Quiet, no messages.
33
34       -V     Verbose, more messages.
35
36       -T <MaxTime>
37              Set CPU time limit
38

IMPLEMENTATION DETAILS

40       Let  r  be  the  number  of  orbits,  O_1,...,O_r  the  orbits and, for
41       i=1,...,r, l_i:=|O_i| the size of the ith orbit.  The first step is  to
42       calculate  the largest power (m) of the characteristic that divides any
43       of the orbit sizes.  Zkd assumes that this is the order of the  Sylow-p
44       subgroup  of  the condensation subgroup, but it prints out its findings
45       with the message
46
47         p-part taken has order N
48
49       so the user can check it. If this is not the order of the Sylow-p  sub‐
50       group  of  the  condensation  group, the program will not know, so will
51       continue.  Normally, however, the condensation  subgroup  K  will  have
52       trivial Sylow-p subgroup, or at any rate the Sylow subgroup will have a
53       regular orbit, and in this case at least the  condensation  is  legiti‐
54       mate.
55
56       The  output  is  a  square  matrix with one row and one column for each
57       orbit of K.  Abstractly, the condensation can be described as  follows.
58       Let G be a permutation group of degree n, F a field of characteristic p
59       and K≤G a pʹ-subgroup.  Then, there is an idempotent
60
61         e = 1/|K| ∑_{hϵK} hϵFG
62
63       associated to K.  Now, let V be a FG-module, for example  (as  in  this
64       program)  the natural permutation module V=F^n, where G acts by permut‐
65       ing the entries of vectors.  Then, Ve is an e(FG)e-module, and for  any
66       πϵG, the condensed form is eπe, regarded as a linear map on Ve.
67
68       To calculate the action of eπe, let (v_1,...,v_n) be the standard basis
69       such that v_iπ=v_(iπ) for πϵG.  A basis of Ve is  given  by  the  orbit
70       sums
71
72         w_i = ∑_(kϵO_i) v_k (1≤i≤r)
73
74       and with respect to this basis we have
75
76         w_i (eπe) = ∑_(kϵO_i) 1/l_([kπ]) w_[kπ]
77
78       where [m] denotes the orbit containing m.
79
80       If  K  is not a pʹ-subgroup, e is no longer defined.  However, the last
81       formula can still be given a sense by replacing
82
83         1/l_([iπ])→λ_{[iπ]}:=
84
85           1/l_([iπ])/p^m} if p^m|l_([iπ])
86
87           0 otherwise
88
89       where m is the highest power of the characteristic which divides any of
90       the orbit sizes.  Thus, all but the orbits with maximal p-part are dis‐
91       carded, and the corresponding columns in the output matrix are zero.
92

INPUT FILES

94       Orbits Orbit file produced by zmo(1).
95
96       Perm   Permutation to be condensed.
97

OUTPUT FILES

99       Kond   Condensed permutation (square matrix).
100