Command Line

zkd Options Field Orbits Perm Kond

Options: Standard options, see Standard Command Line Options

Field: The field order or "Z" for integer condensation.

Orbits: Orbits and orbit sizes.

Perm: Permutation to be condensed.

Kond: Condensed permutation.

Input Files

Orbits: Orbits and orbit sizes.

Perm: Permutation to be condensed.

Output Files

Kond: Condensed permutation.

Description

This program reads an orbit file (Orbits) and a permutation from Perm. It outputs the condensed form, i.e., a matrix over GF(q) to Result. The field must be specified on the command line because the other input data is is all to do with permutations and the program would otherwise not know which field was intended. The orbit file must contain two integer matrices containing the orbit numbers for each point and the orbit sizes, repectively. It is usually produced by the zmo program.

The second input file, Perm, must contain one or more permutations. Notice that only the first permutation is read in and condensed. If there are more than one permutation, the others are ignored. Unlike in previous versions of this program, it is not assumed that the orbits are contiguous.

Integer condensation: If Field is the letter "Z", zkd condenses over the integers. In this case, Result is an integer matrix with the same dimensions as in the GF(q) case.

Implementation Details

Let r be the number of orbits, $O_1,\ldots,O_r$ the orbits and, for $i=1,\ldots,r$ , $l_i:=|O_i|$ the size of the i-th orbit. The first step is to calculate the largest power (m) of the characteristic that divides any of the orbit sizes. ZKD assumes that this is the order of the Sylow-p subgroup of the condensation subgroup, but it prints out its findings with the message

p-part taken has order N

so the user can check it. If this is not the order of the Sylow-p subgroup of the condensation group, the program will not know, so will continue. Normally, however, the condensation subgroup K will have trivial Sylow-p subgroup, or at any rate the Sylow subgroup will have a regular orbit, and in this case at least the condensation is legitimate.

The output is a square matrix with one row and one column for each orbit of K. Abstractly, the condensation can be described as follows. Let G be a permutation group of degree n, F a field of characteristic p and K≤G a p'-subgroup. Then, there is an idempotent

$e = \frac{1}{|K|} \sum_{h\in K} h \in FG$

associated to K. Now, let V be a FG-module, for example (as in this program) the natural permutation module $V=F^n$ , where G acts by permuting the entries of vectors. Then, Ve is an e(FG)e-module, and for any π∈G, the condensed form is eπe, regarded as a linear map on Ve.

To calculate the action of eπe, let $(v_1,\ldots,v_n)$ be the standard basis such that $v_i\pi=v_{i\pi}$ for π∈G. A basis of Ve is given by the orbit sums

$w_i = \sum_{k\in O_i} v_k \qquad(1\leq i\leq r)$

and with respect to this basis we have

$w_i (e\pi e) = \sum_{k\in O_i} \frac{1}{l_{[k\pi]}} w_{[k\pi]}$

where [m] denotes the orbit containing m.

If K is not a p'-subgroup, e is no longer defined. However, the last formula can still be given a sense by replacing

$\frac{1}{l_{[i\pi]}} \to \lambda_{[i\pi]}:= \left\{\begin{array}{ll} \frac{1}{l_{[i\pi]}/p^m} & \mbox{if~}p^m|l_{[i\pi]}\\ 0 & \mbox{otherwise} \end{array}\right.$

where m is the highest power of the characteristic which divides any of the orbit sizes. Thus, all but the orbits with maximal p-part are discarded, and the corresponding columns in the output matrix are zero.