% Make headline containing the date of the license agreement (see COPYING) \def\makeheadline{\vbox to 0pt{\vskip-45pt \line{\vbox to 8.5pt{}\hskip-40pt\fiverm{04}/{17}/{2007}\hfil}\vss} \nointerlineskip} % \def\makeactive#1{\catcode`#1 = \active\ignorespaces}% \chardef\letter = 11 \chardef\other = 12 \catcode`@=\letter \def\alwaysspace{\hglue\fontdimen2\the\font\relax}%
{\makeactive\^^M \makeactive\ % \gdef\obeywhitespace{% \makeactive\^^M\def^^M{\par\indent}% \aftergroup\@removebox% \makeactive\ \let =\alwaysspace}}% \def\@removebox{\setbox0=\lastbox} % \font\titlefont=cmbx10 scaled\magstep4 \font\authorfont=cmr12 scaled\magstep1 \font\sectionheaderfont=cmbx12 scaled\magstep1 \font\subsectionheaderfont=cmbx12 \def\filenamefont{\tt} % \long\def\section#1{\bigbigbreak{\sectionheaderfont #1}\nobreak\medskip\nobreak} \long\def\subsection#1{\bigbreak{\subsectionheaderfont #1}\hskip0.75em} \def\twocols#1#2{\hskip0.45truein\hbox to 3.0truein{#1\hfil}\hskip0.4truein\relax \hbox to 2.45truein{#2\hfil}\hfil} \long\def\objectfile#1{{\elevenpoint\obeylines\obeyspaces\tt\ttraggedright
#1\vskip0pt}} \newdimen\optionIndent\optionIndent=1.1in \long\def\defoption#1#2{{\advance\leftskip by1em\advance\leftskip by\optionIndent \noindent\llap{\hbox to\optionIndent{\tt #1\hfil}}#2\vskip0pt}} % \def\germR{\underline{{\rm R}}} \def\bfgermR{\underline{{\bf R}}} % \def\options{{\rm [}{\it options\/}{\rm ]}} % \newskip\bigbigskipamount\bigbigskipamount=20pt plus 7pt minus 5pt \def\bigbigskip{\vskip\bigbigskipamount} \def\bigbigbreak{\par\ifdim\lastskip<\bigbigskipamount \removelastskip\penalty-300\bigbigskip\fi} \multiply\smallskipamount by4\divide\smallskipamount by3 \multiply\medskipamount by4\divide\medskipamount by3 \multiply\bigskipamount by4\divide\bigskipamount by3 \multiply\bigbigskipamount by4\divide\bigbigskipamount by3 % \pageno=1 \centerline{{\titlefont PARTITION BACKTRACK PROGRAMS:}} \vskip10pt \centerline{{\titlefont USER'S MANUAL}} \vskip35pt \centerline{{\authorfont JEFFREY S. LEON}} \vskip6pt \centerline{Mathmatics Dept, m/c 249} \centerline{University of Illinois at Chicago} \centerline{Box 4348} \centerline{Chicago, IL 60680} \vskip40pt % \section{I.\quad INTRODUCTION} %
This document describes a collection of programs for permutation group
computations employing the partition backtrack method, as described in a
recent article by the author (Leon, 1991). At present, these programs
perform the following computations: \medskip \twocols{set stabilizers,}{set images (see below),} \vskip4pt \twocols{ordered partition stabilizers,}{ordered partition images,} \vskip4pt \twocols{intersections,}{} \vskip4pt \twocols{centralizers (of elements),}{conjugacy (of elements),} \vskip4pt \twocols{centralizers (of subgroups),}{} \vskip4pt \twocols{automorphism groups of designs,}{isomorphism of designs,} \vskip4pt \twocols{automorphism groups of matrices,}{isomorphism of matrices,} \vskip4pt \twocols{monomial automorphism groups of}{monomial isomorphism of matrices} \vskip-1.5pt \twocols{matrices over small fields,}{over small fields,} \vskip4pt \twocols{automorphism groups of linear codes,}{isomorphism of linear codes.} \medbreak
The term {\it set image} problem is used here to refer to the following
problem: Given a permutation group
$G$ and subsets $\Lambda$ and $\Phi$ of the domain, determine if there exists
$g \in G$ such that $\Lambda^g = \Phi$. The ordered partition image problem is
defined analogously. The term {\it design\/} is used here to refer to any
collection of points and blocks. An automorphism of a matrix is any permutation
of the rows and columns that leaves the matrix invariant; two matrices are
isomorphic if one may be transformed to the other by permutation of rows and
columns. For monomial automorphism groups and monomial isomorphism, the matrix entries
must be taken from a finite field; in addition to permutation of rows and
columns, we allow each row and each column to be multiplied by a nonzero
field element. % \medbreak
Note that each of the problems in the first column above involves
computation of a subgroup; these problems will be referred to
as {\it subgroup computations}. For each problem
in the second column, the set of permutations having the desired property
either is empty or forms a right coset of an appropriate subgroup; we are
seeking one coset representative (if it exists). These problems
will be referred to as {\it coset representative computations}. % \medbreak
Some of the programs described here can be used to compute in groups of
relatively high degree, considerably higher than those that can be
handled by programs based on conventional algorithms.
However, it should be kept mind that the programs are new.
All appear to work correctly, but most have not
been thoroughly tested, especially on intransitive groups. (The set
stabilizer program has been tested the most thoroughly, and in general those
for subgroup computations have received more testing than those for coset
representative calculations.) The author would appreciate any reports of errors; they
may be sent to {\tt leon@turing.math.uic.edu}. \medbreak
Work on programs for the following computations is in progress: \medskip \twocols{unordered partition stabilizers,}{unordered partition images,} \vskip4pt \twocols{normalizers,}{conjugacy (of subgroups),} \vskip4pt \twocols{}{coset intersections,} \medbreak
In the course of constructing test cases for the partition backtrack programs
and verifying their output,
the author has developed several other programs, not based on backtrack search.
These programs are described briefly in Section~IX. Many of these programs
were put together quickly, with a view toward simplicity rather than
efficiency and ease of use. \medbreak
At present, the programs run on the following machines: The Sun/3, the Sun/4,
the IBM~3090, and the IBM~PC. Two versions are available for the IBM~PC: a standard version,
which is limited to groups of degree no more than 1000 (roughly) due
to the 640K memory limitation, and a 386/486 version using a DOS extender, that
can handle larger groups. The source code for all programs is written
entirely in C and, with very minor exceptions, conforms to the ANSI
standard. The programs should compile, with minimal changes, with
any C compiler fully supporting the ANSI standard. The Sun/3 and Sun/4
versions have been compiled with the GNU C compiler, the IBM~3090 version with the
Waterloo~C compiler, and the IBM/PC versions with the Borland C++ and
Zortech C++ compilers (both configured as C compilers). % % \section{II.\quad OBJECTS AND FILE FORMATS} %
At present, the programs compute with objects of seven types: Permutation
groups, permutations, point sets, partitions (ordered or unordered),
block designs, matrices, and linear codes. Each object used as input by the programs is read from a file. Likewise, each object constructed
by the programs is written to a file. All of these files
are ordinary text files. The format of the files is designed for
compatibility with Cayley (Cannon, 1984); it is that of a Cayley library,
with certain restrictions added. Essentially, the restrictions say that
the library may contain only statements defining the object, and (at present)
that only certain attributes of the object may specified in the library.
(Many of the permutation group libraries distributed with Cayley conform
to these restrictions.) Thus objects constructed by these programs
described here may be read into Cayley for further investigation.
Likewise, objects defined in existing Cayley libraries may, in many cases,
be used as input to the programs described here. An alternative format,
compatible with Gap, may be added at a later date. \medbreak
The examples which follow illustrate the correct format for these object files.
Note that the contents of the files is case--insensitive; upper and lower case
letters may be used interchangeably. (However, the names of the files may
be case--sensitive, depending on the operating system.) Also, the
use of white space (blanks, tabs, newline characters) is optional: Except
within integers and identifiers, any number of whitespace characters may
occur. Text enclosed by ampersands or quotation marks is treated as a comment. % \subsection{a)\enskip Permutation groups:}The format for permutation group files
is illustrated by following file, named {\filenamefont psp62}, which defines
${\rm PSp}_6(2)$ as a permutation group
on nonzero vectors (degree 63). \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
LIBRARY psp62; " PSp(6,2) acting on nonzero vectors, degree 63."
psp62: permutation group(63);
psp62.forder: 2^9 * 3^4 * 5 * 7;
psp62.generators:
a = (1,2)(3,5)(4,7)(8,12)(11,16)(13,19)(17,18)(20,26)(21,28)(23,30)(24,32)
(25,34)(29,37)(31,40)(33,43)(36,46)(38,41)(39,49)(42,44)(45,52)(48,51)
(53,58)(57,62)(59,61),
b = (1,3,6,10,15,22)(2,4,8,13,20,27)(5,9,14,21,29,38)(7,11,17,23,31,41)
(12,18,24,33,44,34)(16,19,25)(26,35,45,53,32,42)(28,36,47)(30,39,50,
56,61,58)(37,48)(40,51,46,54,59,62)(49,55,60,63,52,57);
FINISH;\vskip0pt}} \medbreak
The line specifying the factored group order may be omitted; however, since the
random Schreier method is currently used to construct a base and strong
generating set for the group, there is a possibility (probably small) that
the group may be generated incorrectly if this line is removed.
When generators are written in cycle format, as above, inclusion of cycles
of length one is optional. (For compatibility with Cayley, they should be
omitted.)
It is also
possible to write the generators in image (rather than cycle) format; in
this case, the file shown above would become: \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
LIBRARY psp62; " PSp(6,2) acting on nonzero vectors, degree 63."
psp62: permutation group(63);
psp62.forder: 2^9 * 3^4 * 5 * 7;
psp62.generators:
a = /2,1,5,7,3,6,4,12,9,10,16,8,19,14,15,11,18,17,13,26,28,22,30,
32,34,20,27,21,37,23,40,24,43,25,35,46,29,41,49,31,38,44,33,42,
52,36,47,51,39,50,48,45,58,54,55,56,62,53,61,60,59,57,63/,
b = /3,4,6,8,9,10,11,13,14,15,17,18,20,21,22,19,23,24,25,27,29,1,
31,33,16,35,2,36,38,39,41,42,44,12,45,47,48,5,50,51,7,26,43,34,
53,54,28,37,55,56,46,57,32,59,60,61,49,30,62,63,58,40,52/;
FINISH;\vskip0pt}} \medbreak
Finally, if a base and strong generating set for the group are already
known, they may be included in the file. This eliminates the need for
the programs to first construct a base and strong generating set for
the input group. The file format is then as follows. \nobreak\medskip\nobreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
LIBRARY psp62; " PSp(6,2) acting on nonzero vectors, degree 63."
psp62: permutation group(63);
psp62.forder: 2^9 * 3^4 * 5 * 7;
psp62.base: seq(1,3,6,2,4,5);
psp62.strong generators: [
x01 = (1,3)(4,27)(5,9)(7,45)(10,48)(11,17)(12,34)(13,20)(14,25)(15,
39)(16,63)(19,60)(21,55)(22,58)(23,28)(24,37)(31,53)(32,47)(33,
61)(36,42)(38,49)(44,50)(51,62)(54,59),
x02 = (2,16)(3,6)(5,55)(8,21)(9,40)(13,51)(14,46)(15,47)(17,44)(19,
59)(20,29)(22,36)(23,58)(24,61)(25,63)(26,37)(27,60)(31,50)(32,
48)(33,41)(34,56)(38,57)(43,45)(52,62),
.
.
x12 = (5,51)(7,12)(8,29)(9,62)(10,42)(13,55)(15,23)(18,35)(20,21)
(22,32)(28,39)(34,45)(36,48)(40,52)(43,56)(47,58)];
FINISH;\vskip0pt}} \medbreak
(The vertical dots indicated that part of the file has been omitted.)
When a base and strong generating set are given, inclusion of the factored
order of the group is purely optional.
At present it is {\it not} possible to specify both generators and a base and
strong generating set for a group. (This obviously undesirable restriction
will be removed eventually.) % \subsection{b)\enskip Permutations:}The format for permutation files
is illustrated by following file, named {\filenamefont g}, which defines a permutation of
$g$ of degree 63 and order 4, which turns out to lie in the group
${\rm PSp}_6(2)$ given above. \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
LIBRARY g; " An element of order 4 in the group psp62 above."
g = (1,40,50,6)(2,58,18,34)(3,8,44,30)(4,10,15,48)(5,11)(7,60,38,32)
(12,46,22,56)(13,62,20,61)(16,42,36,63)(19,49,47,45)(21,53,31,
55)(24,33,37,51)(25,28)(26,52)(27,59,39,54)(29,41);
FINISH;\vskip0pt}} \medbreak
As with generators for permutation groups, permutations may be written in
image format, rather than cycle format. Note that, when cycle format is used,
the file contains no explicit indication of the degree of the permutation.
Thus, for example, the permutation {\tt g} above could be used wherever a
permutation of degree 63 (the largest point appearing explicitly) or greater
is expected. \medbreak
Given the files above, the centralizer in ${\rm PSp}_6(2)$ of $g$ could be
computed by the command \smallskip \hskip0.45truein{\tt cent\quad psp62\quad g\quad C} \smallskip
which would save the centralizer (in the format described in part~(a) above)
in the file {\filenamefont C}. % \subsection{c)\enskip Point sets:}The format for point sets is illustrated
by following file, named {\filenamefont lambda}, which defines a subset $\Lambda$ of
$\{1,\ldots,63\}$. \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
LIBRARY lambda; " A subset of {1,...,63} of size 31."
lambda = [10,16,44,3,5,33,48,63,56,50,6,52,55,19,34,25,2,35,17,40,21,
58,49,36,39,12,60,30,15,29,37];
FINISH;\vskip0pt}} \medbreak
Note that there is no explicit indication of the size
of the base set. Thus the set {\tt lambda} above could be used wherever
a subset of $\{1,\ldots,m\}$ is expected for any $m$ with $m \geq 63$
(the largest point appearing explicitly). \medbreak
The set stabilizer in ${\rm PSp}_6(2)$ of $\Lambda$ could be computed
by the command \smallskip \hskip0.45truein{\tt setstab\quad psp62\quad lambda\quad S} \smallskip
which would save the stabilizer in the file {\filenamefont S}. % \subsection{d)\enskip Partitions:}The format for partitions (ordered or
unordered) is illustrated
by following file, named {\filenamefont pi}, which defines a partition
$\Pi$ of $\{1,\ldots,63\}$. \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
LIBRARY pi; " An (ordered or unordered) partition of 1,...,63 having four " " cells of sizes 15, 20, 13, and 15. respectively."
pi = seq([1,34,28,48,37,41,13,54,57,51,4,38,8,46,16],[2,40,21,
18,6,53,30,56,42,12,3,11,33,15,32,5,60,31,55,63],[7,
36,25,29,35,9,26,49,14,47,10,24,43],[17,58,52,50,59,
45,20,61,23,39,44,19,22,62,27]);
FINISH;\vskip0pt}} \medbreak
Note that the individual cells are delimited by square brackets.
Note also that the file contains no indication whether the partition is ordered
or unordered; rather each program operating on partitions interprets the
partition as ordered or unordered, whichever is appropriate for the the
program. \medbreak
The stabilizer in ${\rm PSp}_6(2)$ of $\Pi$, interpreted as an ordered
partition, could be computed by the command \smallskip \hskip0.45truein{\tt parstab\quad psp62\quad pi\quad T} \smallskip
which saves the stabilizer in the file {\filenamefont T}. % \subsection{e)\enskip Block designs:}Here a block design refers to any
collection of subsets of $\{1,\ldots,n\}$; it is even possible to have
repeated blocks, i.e., two different blocks containing exactly the same points.
(If repeated blocks occur, we require that an automorphism preserve
multiplicities.) The file format for block designs
is illustrated by following file, named {\filenamefont d17}, which defines
a block design $D_{17}$ with 17 points and with 34 blocks, each of size 5. \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
LIBRARY d17; " The design with 17 points and 34 blocks, each containing " " 5 points, obtained from the codewords of weight 5 in the " " quadratic residue code of length 17 and dimension 9."
d17 = seq( 17, 34,
[3,6,8,15,17], [1,4,7,9,16], [1,4,5,11,17],
[2,5,8,10,17], [3,4,7,8,14], [1,2,5,6,12],
[1,4,6,13,15], [1,3,6,9,11], [1,3,10,12,15],
[3,5,8,11,13], [2,8,9,12,13], [1,7,13,14,17],
[6,8,11,14,16], [4,5,8,9,15], [2,5,7,14,16],
[2,3,6,7,13], [3,4,10,16,17], [3,5,12,14,17],
[1,7,8,11,12], [5,7,10,13,15], [6,12,13,16,17],
[2,4,7,10,12], [2,9,11,14,17], [2,3,9,15,16],
[2,4,11,13,16], [6,7,10,11,17], [4,6,9,12,14],
[5,11,12,15,16], [1,8,10,13,16], [1,2,8,14,15],
[5,6,9,10,16], [4,10,11,14,15], [7,9,12,15,17],
[3,9,10,13,14] );
FINISH;\vskip0pt}} \medbreak
Note that the file contains the number of points, followed by the number
of blocks, followed by a listing of the blocks. Each block is delimited
by square brackets. \medbreak
The automorphism group of this block design could be computed by the command \smallskip \hskip0.45truein{\tt desauto\quad d17\quad A} \smallskip
which saves the automorphism group in the file {\filenamefont A}. % \subsection{f)\enskip Matrices:}Here a matrix is merely a $k\times n$
array of integers, each in the set $\{0,\ldots,q-1\}$ for some $k$, $n$, and
$q$. (At present, $q$ cannot exceed 256; this limit could be raised, at the
cost of additional space, by minor changes to the source code.)
The file format for matrices is
illustrated by following file, named {\filenamefont m17},
which represents incidence matrix $M_{17}$ for the block design $D_{17}$
in part~(e) above. (In the incidence matrix, rows correspond to points and
columns to blocks.) \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
LIBRARY m17; " The incidence matrix of d17."
m17 = seq( 2, 17, 34, seq(
0,1,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,
0,0,0,1,0,1,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,
1,0,0,0,1,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,
0,1,1,0,1,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0,
0,0,1,1,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,
1,0,0,0,0,1,1,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,
0,1,0,0,1,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,1,0,
1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,
0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,1,0,1,1,
0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,1,0,1,
0,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,
0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0,
0,0,0,0,0,0,1,0,0,1,1,1,0,0,0,1,0,0,0,1,1,0,0,0,1,0,0,0,1,0,0,0,0,1,
0,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,0,1,0,1,
1,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,1,0,
0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,0,0,
1,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0,1,0
));
FINISH;\vskip0pt}} \medbreak
Note that the file contains the set size $q$, followed by the number $k$ of rows,
followed by the number $n$ of columns, followed by the entries of the matrix
listed in row--major order. Note that matrix entries are not, in general,
limited to 0 and 1; if $q$ is the set size, matrix entries may be integers
in the range 0 through $q-1$. \medbreak
The automorphism group of this matrix could be computed by the command \smallskip \hskip0.45truein{\tt matauto\quad m17\quad B} \smallskip
which saves the automorphism group in the file {\filenamefont B}. \medbreak
Matrices may also be specified using an alternate format, which is not
compatible with Cayley, but which saves considerable space for large
matrices.\footnote{${}^{\dag}$}{\elevenpoint At time of writing, the alternate format does not work
correctly on some machines.} This alternate format is available only when the set size $q$ is
at most 9. Using the alternate format, the matrix $M_{17}$ would be
specified by a file as follows: \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
m17
2 17 34
0110011110010000001000000000110000
0001010000100011000001111000010000
1000100111000001110000010000000001
0110101000000100100001001010000100
0011010001000110010100000001001000
1000011100001001000010000110001000
0100100000010011001101000100000010
1001100001101100001000000000110000
0100000100100100000000110010001011
0001000010000000100101000100101101
0010000101001000001000101101000100
0000010010100000011011000011000010
0000001001110001000110001000100001
0000100000011010010000100010010101
1000001010000100000100010001010110
0100000000001010100010011001101000
1011000000010000110010100100000010 \vskip0pt}} \medbreak
With the alternate format, blanks may occur between matrix entries, but
are not required. The first line of the file is reserved for the matrix
name; nothing else may be placed on this line. % \subsection{g)\enskip Linear codes:}
The file format for lines codes is
illustrated by following file, named {\filenamefont q17}, which represents the
binary (17,9)--quadratic residue code $Q_{17}$ mentioned in part~(e) above.
This file gives a generator matrix for the code, in the format of
part~(f) above. \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
LIBRARY q17; " The (17,9) binary quadratic residue code."
q17 = seq( 2, 9, 17, seq(
1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1,
1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,
1,1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,
0,1,1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,
1,0,1,1,1,1,1,0,1,0,0,0,1,1,0,0,0,
0,1,0,1,1,1,1,1,0,1,0,0,0,1,1,0,0,
0,0,1,0,1,1,1,1,1,0,1,0,0,0,1,1,0,
0,0,0,1,0,1,1,1,1,1,0,1,0,0,0,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
));
FINISH;\vskip0pt}} \medbreak
Note that the file contains the size of the field for the code, followed by the
dimension of the code, followed by the
length of the code, followed by a generator matrix whose entries are
listed in row--major order. At present, the field size is restricted to
a prime integer (less than 255) or to 4; automorphism group and isomorphism
calculations are practical only when the field size is quite small.
In the case of a prime, the field
is taken as the integers modulo that prime. \medbreak
The automorphism group of this code could be computed by the command \smallskip \hskip0.45truein{\tt codeauto\quad q17\quad v17\quad H} \smallskip
which saves the automorphism group as the group {\filenamefont H}.
(Here file {\filenamefont v17} defines a matrix $V_{17}$ which is the
transpose of the matrix $M_{17}$ of part~(f) above; the role of
$V_{17}$ will be explained later.) \medbreak
As with matrices, an alternate (not Cayley--compatible) format is provided
for codes over field of size at most 9.\footnote{${}^{\dag}$}{\elevenpoint As with matrices, this
alternate format at present fails to work correctly on some machines.}
With the alternate format, the file defining the code $Q_{17}$
would be as follows: \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
q17
2 9 17
11101000110001011
11110100011000101
11111010001100010
01111101000110001
10111110100011000
01011111010001100
00101111101000110
00010111110100011
11111111111111111 \vskip0pt}} \bigbreak \hrule \bigbigbreak
In the examples above, it was assumed that the name of file matched the
name of the Cayley library that it contained. Although this is
recommended for simplicity, it need not be the case. When the names
do not match, an object is specified using the format \hbox{{\it fileName\/}{\tt ::}{\it libraryName\/}}. For example, if the file
{\filenamefont psp62} in part~(a) above were renamed {\filenamefont psp}
and the file {\filenamefont g} in part~(b) were named {\filenamefont pspx4},
but if the contents of both files remained unchanged, the command to
compute the centralizer in ${\rm PSp}_6(2)$ of $g$ might be \smallskip \hskip0.45truein{\tt cent\quad psp::psp62\quad pspx4::g\quad gCentr::C} \smallskip
where now the centralizer is saved in the file {\filenamefont gCentr}, but in a
Cayley library named {\tt C}. A path may also be specified, for example, \smallskip \hskip0.45in{\tt cent\quad ../groups/psp::psp62\quad ../groups/pspx4::g\quad gCentr::C} \smallskip
in Unix. (In MS~DOS on the IBM~PC, the forward slash must be replaced
by a backslash. Under CMS on the IBM~370, the file name and file type must
be separated by a period, rather than the blank normally used under CMS.)
If however, the file name and the library name for input files
differ only in that the file name contains path information, the
{\tt -p} option (discussed later) may be useful. % \medbreak
In the examples above, not only did the file name and the Cayley library
name match, but both matched the actual name for the object appearing in
the Cayley library. Actually, the name for the object need not be
related to the name of the Cayley library. For example, the following
is acceptable. \medbreak \vbox{{\elevenpoint\advance\leftskip by 0.45truein\obeywhitespace\tt\catcode`^=\other
LIBRARY psp62; " PSp(6,2) acting on nonzero vectors, degree 63."
G: permutation group(63);
G.forder: 2^9 * 3^4 * 5 * 7;
G.generators:
a = (1,2)(3,5)(4,7)(8,12)(11,16)(13,19)(17,18)(20,26)(21,28)(23,30)(24,32)
(25,34)(29,37)(31,40)(33,43)(36,46)(38,41)(39,49)(42,44)(45,52)(48,51)
(53,58)(57,62)(59,61),
b = (1,3,6,10,15,22)(2,4,8,13,20,27)(5,9,14,21,29,38)(7,11,17,23,31,41)
(12,18,24,33,44,34)(16,19,25)(26,35,45,53,32,42)(28,36,47)(30,39,50,
56,61,58)(37,48)(40,51,46,54,59,62)(49,55,60,63,52,57);
FINISH;\vskip0pt}} \medbreak
In this situation, the command line must still specify the Cayley library name
(and file name, if different), but informative messages printed as the
command executes use the object name ({\tt G}, in this case). For
objects created by commands, an object name different from the Cayley
library name may be specified by means of the {\tt -n} option, discussed
later. % % \section{III.\quad\kern-3pt FIELDS, MONOMIAL PERMUTATIONS, AND MATRICES\kern-2pt} %
This section treats several topics that arise primarily in connection
with computations involving combinatorial structures -- designs, matrices,
and codes. % \subsection{i)\enskip Finite fields:}Finite fields arise when computing with
codes, or with matrices whose entries belong to the field. At present, only
fields ${\rm GF}(q)$ whose order $q$ is either 4 or a prime integer are
supported; moreover, we must have $q\leq 255$. (For automorphism
group and isomorphism calculations, time and space considerations generally
dictate a practical limit on $q$ that is far lower.) Field elements are
numbered $0,1,\ldots,q-1$. When $q$ is prime, the field is taken as the
integers modulo $q$. When $q=4$, there is an essentially unique way to number the field elements. \smallbreak
We denote the set of nonzero elements of
${\rm GF}(q)$ by ${\rm GF}(q)^{\#}$. \bigbreak \subsection{ii)\enskip Monomial permutations:}Given a fixed field
${\rm GF}(q)$, a monomial permutation of monomial degree $n$ over
${\rm GF}(q)$ is essentially a permutation $s$ on
${\rm GF}(q)^{\#} \times\{1,\ldots,n\}$ which satisfies the following property,
henceforth referred to as the {\it monomial property:\/}
$$\displaylines{(\alpha,i)^s = (\beta,j)\quad {\rm implies}\quad
(\gamma\alpha,i)^s = (\gamma\beta,j)\kern40pt\cr\kern40pt
{\rm\hbox{for all}}\enskip \alpha,\beta,\gamma\in {\rm GF}(q)^{\#}\enskip {\rm and}\enskip
i,j\in\{1,\ldots,n\}.\cr}$$
Note that $s$ is determined completely by its action on the points $(1,i)$,
$1\leq i\leq n$; note also that the actual degree of $s$ is $(q-1)n$. \smallbreak
For purposes of actual computation, however, we want
a representation of $s$ as a
permutation on $\{1,\ldots,(q-1)n\}$; to obtain this,
we number the pair $(\alpha,i)$ by
$(q-1)(i-1)+\overline{\alpha}$, where $\overline{\alpha}$ denotes the integer
representing $\alpha$. Then the monomial property becomes
$$\displaylines{\bigl((q-1)(i-1)+\overline{\alpha}\bigr)^s =
(q-1)(j-1)+\overline{\beta}\quad{\rm implies}\kern40pt\cr \kern40pt\bigl((q-1)(i-1)+\overline{\gamma\alpha}\bigr)^s =
(q-1)(j-1)+\overline{\gamma\beta}.\cr}$$ \medbreak
For example, over the field ${\rm GF}(4)$, the monomial permutation $s$ on
${\rm GF}(4) \times\{1,2,3,4\}$ determined by
$$ (1,1)^s = (3,2),\quad (1,2)^s = (2,4),\quad (1,3)^s = (1,1),\quad
(1,4)^s = (2,3)$$
is represented as a permutation on $\{1,\ldots,12\}$ as follows:
$$(1,6,10,8,2,4,11,9,3,5,12,7).$$ % \bigbreak \subsection{iii)\enskip Permutations acting on matrices:}Let
$A = (a_{ij})$ be an $r \times c$ matrix with entries from an arbitrary set.
A permutation $s$ of degree $r+c$ which fixes $\{1,\ldots,r\}$ setwise
induces an action on $A$ as follows: Row $i$ of $A$ is moved to row position $i^s$\enskip
$(1\leq i\leq r)$ and column $j$ of $A$ is moved to column position
$(r+j)^s-r$\enskip $(1\leq j\leq c)$. Thus
$$A^s = (b_{ij}),\quad {\rm where}\quad
b_{ij} = a_{i^\prime j^\prime},\enskip {\rm with}\enskip
i^\prime = i^{s^{-1}}\enskip {\rm and}\enskip
j^\prime = (r+j)^{s^{-1}}-r.$$
If $A^s = B$, we say that $s$ is an {\it isomorphism\/} of $A$ to $B$. When
$A^s=A$,\enskip $s$ is called an {\it automorphism\/} of $A$. The group formed by
the automorphisms is called the {\it automorphism group\/} of $A$, and denoted
${\rm AUT}(A)$. \medbreak
For example, the action of a permutation $s$ of degree 7 on a $3\times 4$
matrix $A$ is illustrated by the following.
$$s = (1,3,2)(4,7,5),\qquad
A = \pmatrix{8&0&4&3\cr
2&9&3&0\cr
0&1&7&5\cr},\qquad
A^s = \pmatrix{9&0&3&2\cr
1&5&7&0\cr
0&3&4&8\cr}.$$ % \bigbreak \subsection{iv)\enskip Monomial permutations acting on matrices:}Now let
$A = (a_{ij})$ be an $r \times c$ matrix with entries from a field
${\rm GF}(q)$. A monomial permutation $s$ of monomial degree $r+c\kern3pt$
(actual degree $(q-1)(r+c)\kern2pt)$ which fixes $\{1,\ldots,(q-1)r\}$ setwise
induces an action on $A$. This action is most easily described if we think of $s$ as
a permutation on ${\rm GF}(q)^{\#} \times\{1,\ldots,n\}$, as in~(ii) above;
then $s$ fixes $\{(\alpha,i)\vert\alpha\in{\rm GF}(q)^{\#},1\leq i\leq r\}$
setwise. If $(1,i)^s = (\alpha,k)$ and $(1,r+j)^s = (\beta,r+m)$,
then row $i$ of $A$ is multiplied by $\alpha$ and moved to row position $k$,\enskip
and column $j$ of $A$ is multiplied by $\beta$ and moved to column position
$m$. Thus
$$ A^s = (b_{ij}),\quad {\rm where}\quad
b_{ij} = \lambda^{-1}\mu^{-1}a_{i^\prime j^\prime},$$
with $\lambda$, $\mu$, $i^\prime$, and $j^\prime$ determined by
$$ (\lambda,i^\prime) = (1,i)^{s^{-1}}\quad {\rm and}\quad
(\mu,r+j^\prime) = (1,r+j)^{s^{-1}}.$$
If $A^s = B$, we say that $s$ is an {\it monomial isomorphism\/} of $A$ to $B$. When
$A^s=A$,\enskip $s$ is called a {\it monomial automorphism\/} of $A$. The group
formed by the automorphisms is called the {\it monomial automorphism group\/} of $A$, and denoted
${\rm AUT}^*(A)$. \medbreak
For example, over the field ${\rm GF}(4)$, the action of a
monomial permutation $s$ of monomial degree 5 (actual degree 15)
on a $2\times 3$ matrix $A$ is illustrated by the following.
$$\displaylines{(1,1)^s = (3,2),\enskip\kern2pt (1,2)^s = (1,1),\enskip\kern2pt
(1,3)^s = (2,5),\enskip\kern2pt (1,4)^s = (3,3),\enskip\kern2pt (1,5)^s = (2,4),\cr
s = (1,6,3,5,2,4)(7,14,12,8,15,10,9,13,11),\quad\enskip
A = \pmatrix{2&0&3\cr
0&3&1\cr},\quad\enskip
A^s = \pmatrix{2&2&0\cr
0&3&2\cr}.\cr}$$ % % % % \section{IV.\quad PARTITION BACKTRACK COMMANDS} %
The commands employing the partition backtrack method that are currently
available are described below. Note material
in square brackets is optional. (The brackets themselves are not to be
typed.) Discussion of most of the available options will be
deferred to Section~V; only those unique to a specific command will be
mentioned here. \medskip
Options are never required, but they may prove
useful in controlling the format of the output or the procedures used in the
computation. For example, certain options allow for a time versus space
tradeoff. For some ``unusual'' groups (e.g., very dense imprimitive groups),
it may be necessary to specify nonstandard options in order to obtain
acceptable performance. \medskip
The partition backtrack programs described here represent full implementations
of the partition backtrack method, as set forth in (Leon, 1991), with
two exceptions.
{\smallskip\advance\leftskip by 0.45in\relax \item{i)}The criterion in Prop.~8(iii) is not checked. \smallskip \item{ii)}In coset--type computations, the refinement $\germR^+$ of Figure~8 is
always taken as $\germR$\footnote{${}^{\dag}$}{\elevenpoint In order to allow
this manual to be printed without special AMS~TeX fonts, underlined
letters (e.g., $\germR$) are used here as a substitute for
letters appearing in the Euler Fraktur (German) font in (Leon, 1991).} \smallskip} % % \subsection{Set stabilizers:}Set stabilizers may be computed
by the {\tt setstab} command. The format is \smallskip \hskip0.45truein{\tt setstab}\quad\options\quad {\it permGroup\quad pointSet\quad
stabilizerSubgroup} \smallskip
This command computes the set stabilizer in the permutation group {\it permGroup\/}
of the set {\it pointSet\/} and saves the result (in Cayley library format)
as the permutation group {\it stabilizerSubgroup}. \medbreak
At present, the set stabilizer program sometimes
run slowly in doubly transitive groups, and often runs very slowly in groups
that are triply transitive or ``almost'' triply transitive (e.g.,
${\rm SL}_n(2)$\kern2pt), especially when both the point set and its complement
are large and when the set stabilizer turns out to be small. Imprimitive
groups closely related to doubly transitive groups may also cause
difficulty. Modifications to alleviate this difficulty, at least in part,
will be added eventually. % % \subsection{Set images:}Given a permutation group $G$ on $\{1,\ldots,n\}$
and subsets $\Lambda$ and $\Phi$ of $\{1,\ldots,n\}$, the {\tt setimage}
command may be used to determine if there exists an element $g$ of $G$ such
that $\Lambda^g = \Phi$. The format is \smallskip \hskip0.45truein{\tt setimage}\quad\options\quad {\it permGroup\quad pointSet1\quad
pointSet2\quad groupElement} \smallskip
where {\it permGroup}, {\it pointSet1}, {\it pointSet2}, and {\it groupElement}
play the role of $G$, $\Lambda$, $\Phi$, and $g$, respectively. That is,
the command determines whether there exists an element of {\it permGroup\/}
mapping {\it pointSet1\/} to {\it pointSet2\/} and, if so, saves one such
element as the permutation {\it groupElement}.
Note that {\it groupElement\/} will not be created if $\Phi\notin\Lambda^G$.
(Unless the {\tt -q} option is specified, a message indicating whether
$\Phi\in\Lambda^G$ will be written to the standard output.)
The potential difficulties with doubly and triply transitive groups mentioned
for set stabilizer computations apply here also. % % \subsection{Ordered partition stabilizers:}Stabilizers of ordered partitions
may be computed by the {\tt parstab} command. The format is \smallskip \hskip0.45truein{\tt parstab}\quad\options\quad {\it permGroup\quad ordPartition\quad
stabilizerSubgroup} \smallskip
This command computes the stabilizer in the permutation group {\it permGroup\/}
of the ordered partition {\it ordPartition\/} and saves the result as the
permutation group {\it stabilizerSubgroup}. The remarks about performance
on doubly and triply transitive groups for set stabilizer computations
apply here also. % % \subsection{Ordered partition images:}Given a permutation group $G$ on
$\{1,\ldots,n\}$ and ordered partitions $\Pi$ and $\Sigma$ of $\{1,\ldots,n\}$,
the {\tt parimage} command may be used to determine if there exists an
element $g$ of $G$ such that $\Pi^g = \Sigma$. The format is \smallskip \hskip0.45truein{\tt parimage}\quad\options\quad {\it permGroup\quad ordPartition1\quad
ordPartition2\quad groupElement} \smallskip
where {\it permGroup}, {\it ordPartition1}, {\it ordPartition2}, and {\it groupElement}
play the role of $G$, $\Pi$, $\Sigma$, and $g$, respectively.
That is,
the command determines whether there exists an element of {\it permGroup\/}
mapping {\it ordPartition1\/} to {\it ordPartition2\/} and, if so, saves one
such element as the permutation {\it groupElement}.
The permutation {\it groupElement\/} is created only if $\Sigma\in\Pi^G$.
The remarks about performance on doubly and triply
transitive groups given above for
set stabilizer computations apply here also. % % \subsection{Group intersections:}Given permutation groups $G$ and $H$ on
$\{1,\ldots,n\}$, the {\tt inter} command may be used compute the
intersection $G\cap H$. The format is \smallskip \hskip0.45truein{\tt inter}\quad\options\quad {\it permGroup1\quad permGroup2\quad
interGroup} \smallskip
This command computes the intersection of groups {\it permGroup1\/} and {\it permGroup2\/}
and saves the result as the group {\it interGroup\/}. The potential
difficulty with doubly and triply transitive groups discussed above for set
stabilizer computations applies here also when both groups are doubly
or triply transitive. % % \subsection{Centralizers of elements:}Given a permutation group $G$ and
a permutation $x$ (not necessarily contained in $G$), the
{\tt cent} command may be used compute $C_G(x)$, the centralizer in $G$ of $x$.
The format is \smallskip \hskip0.45truein{\tt cent}\quad\options\quad {\it permGroup\quad permutation\quad
centralizerSubgroup} \smallskip
Here {\it permGroup}, {\it permutation}, and {\it centralizerSubgroup\/}
play the role of $G$, $x$, and $C_G(x)$ above. That is, the command computes
the centralizer in the group {\it permGroup\/} of
the permutation {\it permutation\/}
and saves the result as the group {\it centralizerSubgroup}. \medbreak
For this command, it is permissible to specify
{\it permGroup\/} as {\tt\#}{\it n}, where {\it n\/}
is an integer at least 2, in which case {\it permGroup\/} is taken as the symmetric
group of degree {\it n}; in this situation, the normal restrictions on
base size (discussed later) do not apply to {\it permGroup}, although they do apply to
{\it centralizerSubgroup}. \medbreak
The {\tt cent} command accepts an option {\tt -np} which can have an effect
(often small) on performance. If this option is specified, a refinement
process based on the cycle structure of $x$ will not be used. The effect is
to reduce memory requirements a bit. In many cases, the running time does
not change significantly, but in some cases it does increase a great deal. \medbreak
It should be noted that in many cases, perhaps most
cases arising in practice, centralizer computations are fairly easy
even for conventional algorithms, and the partition backtrack
program may perform no better than, and perhaps not even as well as,
programs based on conventional techniques, such as those in
Cayley. (Note, however, that, unlike Cayley, the program here does not require
that the permutation to be centralized lie in the group.) % % \subsection{Conjugacy of elements:}Given a permutation group $G$ and
permutations $x$ and $y$ (not necessarily contained in $G$), the
{\tt conj} command may be used to determine if $x$ and $y$ are conjugate
under $G$ and, if so, to find $g$ in $G$ with $x^g = y$. The format is \smallskip \hskip0.45truein{\tt conj}\quad\options\quad {\it permGroup\quad permutation1\quad
permutation2\quad conjugatingElement} \smallskip
Here {\it permGroup}, {\it permutation1}, {\it permutation2}, and
{\it conjugatingElement\/} play the role of $G$, $x$, $y$, and $g$ above.
That is, the command determines if there exists an element of
{\it permGroup\/} conjugating
{\it permutation1\/} to {\it permutation2\/} and, if so, it saves one such
element as the permutation {\it conjugatingElement}. If the two permutations
are not conjugate in {\it permGroup}, then {\it conjugatingElement} is not
created. In any case, a message indicating the result is written to the
standard output (unless the {\tt -q} option is specified). \medbreak
As with the {\tt cent} command, {\it permGroup\/} may be specified
as {\tt\#}{\it n}, in which case conjugacy in the symmetric group of
degree {\it n} is checked. (In this case, the program merely checks that
the two permutations have the same cycle structure.) Also, the {\tt -np}
option is accepted, and it works as described above for the {\tt cent}
command. \medbreak
As with centralizer computations, conjugacy calculations are usually
easy with conventional algorithms, and the partition backtrack method
may not yield an improvement. % % \subsection{Centralizers of groups:}Given a permutation groups $G$ and
a second permutation group $E$ (not necessarily contained in $G$), the
{\tt gcent} command may be used compute $C_G(E)$, the centralizer in
$G$ of $E$. The format is \smallskip \hskip0.45truein{\tt gcent}\quad\options\quad {\it permGroup1\quad permGroup2\quad
centralizerSubgroup} \smallskip
Here {\it permGroup1}, {\it permGroup2}, and {\it centralizerSubgroup\/}
play the role of $G$, $E$, and $C_G(E)$ above. That is, the command computes
the centralizer in the group {\it permGroup1\/} of
the group {\it permGroup2\/}
and saves the result as the group {\it centralizerSubgroup}. \medbreak
As with the element centralizer command ({\tt cent}),
it is permissible to specify {\it permGroup1\/} as {\tt\#}{\it n},
indicating the symmetric group of degree {\it n}. \medbreak
To an even greater extent than element centralizer
calculations, group centralizer calculations tend to
be easy ones for conventional algorithms; the full power of the
partition method is not needed, and perhaps not even desirable. For this
reason, little effort has gone into development of the {\tt gcent} command;
its implementation is fairly crude, and it is included primarily
for completeness. There are two options, {\tt -cg:}{\it m} and
{\tt -cp:}{\it p}, which affect its performance; for some groups $G$,
it may be necessary to assign them values different from the defaults
(current 3 and 10, respectively). A full description of the significance
of {\it m\/} and {\it p\/} will not be given here; however, we note that
higher values (especially for {\it m}) increase
memory requirements, and often increase execution time as well, but may be
needed if the group $E$ fails to have a small generating set (e.g., if E is
a large elementary abelian group). \medbreak
By specifying {\it permGroup1\/} and {\it permGroup2\/} as the same group,
the {\tt gcent} command may be used to compute the center of a group; note,
however, that it represents an exceptionally inefficient algorithm for
this purpose. % % % \subsection{Automorphism groups of designs:}The
{\tt desauto} command may be used to compute the
automorphism group of a design. Here a {\it design\/} means any set
of points (numbered $1,\ldots,n$ for some $n$) and any collection of subsets
of the point set. The format of the design automorphism group command is: \smallskip \hskip0.45truein{\tt desauto}\quad\options\quad {\it design\quad autoGroup} \smallskip
and the command sets {\it autoGroup} to the automorphism group of the
design {\it design\/}. \medbreak
The interpretation of the group {\it autoGroup\/} that is created depends
on whether the {\tt -pb} (points and blocks) option is specified.
Let $p$ and $b$ denote the number of points and blocks, respectively, of
the design. \smallskip
{\advance\leftskip by0.70truein \noindent\llap{i)\enspace}If the option {\tt -pb} is specified, then {\it autoGroup} is constructed as
a group of degree $p+b$, in which the action on $1,\ldots,p$ is the action
on points and in which the action on $p+1,\ldots,p+b$ is the
action on blocks, the $j$\kern1ptth block being
represented by $p+j$. \smallskip\vskip2pt \noindent\llap{ii)\enspace}If the {\tt -pb} option is omitted, then
{\it autoGroup} is constructed as a group of degree $p$, representing the
action on points only.
In this case, if there are repeated blocks, the group acting on
points only has lower
order than the group acting on points and blocks).
When this situation arises, the group saved as {\it autoGroup} represents
the group on points
only, but the information written to the standard output during the computation
refers to the group acting on points and blocks. (This occurs because the
computation is carried out on points and blocks; restriction to points
is performed only at the end; note also, for this reason, restriction to
points only does not save time or memory.)\vskip0pt} \medbreak % % % \subsection{Isomorphism of designs:}The
{\tt desiso} command may be used to check
isomorphism of designs. The format is \smallskip \hskip0.45truein{\tt desiso}\quad\options\quad {\it design1\quad
design2\quad isoPerm} \smallskip
and the command sets {\it isoPerm} to an isomorphism from
design {\it design1\/} to design {\it design2}, provided the designs
are isomorphic. (If not, the permutation {\it isoPerm\/} is
not created. In any case, a message indicating the result is written to
the standard output, unless the {\tt -q} option is specified.) \medbreak
As in the case of the {\tt desauto} command, described
above, the presence or absence of the {\tt -pb} option determines whether
{\it isoPerm\/} is constructed as a permutation on points and blocks,
or on points only (the default). When the action on blocks is included,
the $j$\kern1ptth block is represented by $p+j$. % % % % \subsection{Automorphism groups and monomial groups of matrices:}The
{\tt matauto} command may be used to compute the
automorphism group of a matrix. If the matrix elements are taken from a
small finite field ${\rm GF}(q)$, then optionally the monomial automorphism group may
be computed. (See Section~III for definitions.)
The command format is: \smallskip \hskip0.45truein{\tt matauto}\quad\options\quad {\it matrix\quad autoGroup} \smallskip
and the command sets {\it autoGroup} to the automorphism group of the
matrix {\it matrix\/} or, if the {\tt -mm} option is specified, to the
monomial automorphism group of {\it matrix\/}. \medbreak
If the {\tt -tr} option is specified, the matrix is transposed after it is
read in, and all computations apply to the transposed matrix. \medbreak
Let $r$ and $c$ denote the number of rows and columns, respectively, of
the matrix $A = (a_{ij})$ whose group is to be constructed. Normally
the automorphism group has degree $r+c$ and the monomial automorphism group
has degree $(q-1)(r+c)$; the interpretation of these groups is described
in Section~III. However, if the {\tt -ro} (rows only) option is specified,
the degree will be $r$ or $(q-1)r$, and the group will represent the action
on rows only. Note that restriction to rows only may reduce the order of
the group, just as in the case of designs restriction to points only may
reduce the order of the group. When this occurs, the remarks above for
design groups apply here also. \medbreak
At present, the program for computing monomial groups of matrices is a very
crude one. As a result, although it works reasonably for many matrices of
fairly large size, it can fail to run in acceptable time even for very small
matrices, e.g., matrices of all 0s. Sometimes use of the {\tt -tr} option
can get around this difficulty (which will be fixed eventually). % % % \subsection{Isomorphism and monomial isomorphism of matrices:}The
{\tt matiso} command may be used to check
if two matrices are isomorphic or, if the matrix elements are from a
finite field ${\rm GF}(q)$, monomially isomorphic. (See Section~III for
definitions.) The command format is \smallskip \hskip0.45truein{\tt matiso}\quad\options\quad {\it matrix1\quad
matrix2\quad isoPerm} \smallskip
In the absence of the {\tt -mm} option, the command sets {\it isoPerm} to an
isomorphism from matrix {\it matrix1\/} to matrix {\it matrix2}, provided the matrices
are isomorphic. (If not, the permutation {\it isoPerm\/} is
not created). If the {\tt -mm} option is specified, the command sets
{\it isoPerm} to a monomial isomorphism from matrix {\it matrix1\/} to matrix {\it matrix2},
provided the matrices are monomially isomorphic. (In this case, the matrix
entries should be field elements.) The effect of the {\tt -ro} option is as
described above for matrix automorphism group calculations. \medbreak
Currently the monomial isomorphism program suffers from the same limitations
as the monomial automorphism group program, as mentioned above. \medbreak % % \subsection{Automorphism groups of linear codes:}The
{\tt codeauto} command may be used to compute the
automorphism group of a linear code over a small field ${\rm GF}(q)$.
However, before the automorphism group of a code $C$ may be computed,
it is necessary to have a set $V$ of vectors (not necessarily codewords)
such that the following conditions hold. In these conditions, $V^*$
denotes the set of all nonzero scalar multiples of vectors in $V$. \smallbreak
{\advance\leftskip by1em\parindent=1em\relax \item{i)} No vector in $V$ is a scalar multiple of any other vector in $V$.
(In particular, $\vert V^*\vert = (q-1)\vert V\vert$.) \smallbreak \item{ii)} $V$ is ``reasonably small''. (With a very large memory,
``reasonably small'' might mean 100,000 or more.) \smallbreak \item{iii)} $V^*$ is invariant under ${\rm AUT}(C)$\enskip (the automorphism
group of $C$), \smallbreak \item{iv)} $\bigl\vert{\rm AUT}(V^*):{\rm AUT}(C)\bigr\vert$ is very small.
(The running time rises very rapidly as a function of this
index. Note that, if $V$ spans $C$, the index is 1.) \smallbreak}
Often the set of minimal weight vectors of the code (scalar multiples
removed if $q > 2$) make a suitable choice for $V$; minimum weight vectors
of the dual code may also be used. This choice for $V$ certainly
satisfies~(i) and~(iii),
may well satisfy~(ii), and in many cases satisfies~(iv). The author has available
programs for computing the set of minimum weight vectors (or vectors of
any specified weight.) \medbreak
The format of the code automorphism group command is \smallskip \hskip0.45truein{\tt codeauto}\quad\options\quad {\it code\quad
invarVectors\quad autoGroup} \smallskip
where {\it invarVectors\/} is the set $V$ of vectors described above
(in the format of a matrix, whose rows are the vectors). The command
sets {\it autoGroup} to the automorphism group of the
code {\it code}. \medbreak
The {\tt -cv} (coordinates and vectors) option for codes
has essentially the same effect as the
{\tt -pb} option for designs. With this option, the automorphism
group is saved in {\it autoGroup\/} as a permutation group
of degree $\bigl(q-1)(n+\vert V\vert\bigr)$\enskip ($n =$ length of code),
representing the action on (monomial) coordinates
and invariant vectors; without the {\tt -cv} option, it is saved as a permutation group
acting of degree $(q-1)n$, representing the action on (monomial)
coordinates only. (However, restriction to coordinates only can never lead to a reduction
in the group order, as occurred with restriction to points or rows for
designs or matrices.) For an explanation of the format of monomial
permutations, see Section~III. \medbreak
At present, the program for computing groups of non--binary codes is a very
crude one; sometimes it can fail to run in reasonable time even on small
codes. Eventually this program will be improved. \medbreak % % % \subsection{Isomorphism of linear codes:}The
{\tt codeiso} command may be used to check isomorphism
of linear codes. However, before isomorphism of two codes
$C_1$ and $C_2$ may be checked, it is necessary to have a sets $V_1$
and $V_2$ of vectors (not necessarily codewords of the two codes)
such that $V_1$ and $V_2$ satisfy conditions~(i), (ii), (iii), and~(iv) above
relative to $C_1$ and $C_2$, respectively, and in addition such that
any isomorphism of $C_1$ to $C_2$ must map $V_1^*$ to $V_2^*$. (As with
code automorphism groups, $V_1^*$ and $V_2^*$ denote the sets of nonzero scalar
multiples of vectors in $V_1$ and $V_2$, respectively.
Often suitable choices for $V_1$ and $V_2$ are the minimal weight vectors
of $C_1$ and $C_2$, respectively (scalar multiples removed.); minimal weight vectors of the duals
of the two codes also could be used. \medbreak
The format of the code isomorphism command is \smallskip \hskip0.45truein{\tt codeiso}\quad\options\quad {\it code1\quad
code2\quad invarVectors1\quad invarVectors2\quad
isoPerm} \smallskip
where {\it invarVectors1\/} and {\it invarVectors2\/}
are the sets $V_1$ and $V_2$, respectively, of vectors described above
(each in the format of a matrix, whose rows are the vectors). The command
sets {\it isoPerm} to an isomorphism from {\it code1\/} to {\it code2},
if the codes are isomorphic; if not, {\it isoPerm\/} is not created. \medbreak
As in the case of the {\tt codeauto} command, described
above, the presence or absence of the {\tt -cv} option determines whether
{\it isoPerm\/} is a permutation on (monomial) coordinates and invariant vectors,
or on (monomial) coordinates only. The interpretation of monomial permutations
is described in Section~III.. % % \vskip10pt \bigbigbreak
Note that a number of the commands above are implemented as shell
files (under Unix), batch files (under MS~DOS), or exec files
(under CMS). The commands that are implemented in this manner, and the contents of the Unix shell files, are as follows. (The list includes a few
commands to be discussed in Section~IX.) \bigskip \long\def\shellfile#1#2{\noindent\hskip0.45truein\hbox to1.0truein{#1\hfil}\relax \hbox to4.0truein{#2\hfil}\vskip2.0pt}\relax \vbox{{\it \shellfile{command}{contents of shell file} \vskip6pt \elevenpoint\tt \shellfile{setimage}{setstab -image \$*} \shellfile{parstab} {setstab -partn \$*} \shellfile{parimage}{setstab -image -partn \$*} \shellfile{conj} {cent -conj \$*} \shellfile{gcent} {cent -group \$*} \shellfile{desiso} {desauto -iso \$*} \shellfile{matauto} {desauto -matrix \$*} \shellfile{matiso} {desauto -iso -matrix \$*} \shellfile{codeauto}{desauto -code \$*} \shellfile{codeiso} {desauto -iso -code \$*} \shellfile{cjper} {cjrndper -perm \$*} \shellfile{ncl} {commut -ncl \$*} \shellfile{compper} {compgrp -perm:\$1 \$2 \$3} \shellfile{compset} {compgrp -set:\$1 \$2 \$3} \shellfile{chbase} {orblist -chbase \$*} \shellfile{ptstab} {orblist -ptstab \$*} \vskip0pt}} % % % \section{V.\quad OPTIONS} %
A partial description of the options that are currently available
follows. Most of the options are available with all of
the commands described in Section~IV. A few options apply only to
subgroup computations, or only to coset--representative computations;
these restrictions are noted below. Options applicable only to a single command
are discussed with that command in Section~IV. \medbreak
In general, options may be specified in any order. However, if
conflicting options are specified, the one specified last is
the one that is used. (In some cases, conflicting options are treated
as an error. Also, the {\tt -l} and {\tt -v} options, discussed later,
are an exception to the general rule that options may be specified in
any order; these options, if present, must come first, and the remainder
of the command line is ignored.) \medbreak
Entering any command with no options or arguments causes a brief
summary of the command format to be displayed. \bigbreak \subsection{Options affecting file handling:} \nobreak\medskip\nobreak % \defoption{-a}{Normally, if a file name is specified for an object
to be constructed, and if a file by that name already
exists, the programs overwrite the existing file. With
the {\tt -a} option, they append to the existing file,
rather than overwriting it.} \medbreak \defoption{-p:{\it path}}{Here {\it path\/} is a string.
The string {\it path\/} is concatenated to
the file name of every input file. This option can be useful
if all the input files are in another directory.
For example, \smallskip \hskip0.15truein{\tt setstab\quad\kern-1pt ../groups/psp62::psp62\quad\kern-1pt
../groups/lambda::lambda\quad\kern-2pt S} \smallskip
may be written more compactly as \smallskip \hskip0.15truein{\tt setstab\quad -p:../groups/\quad
psp62\quad lambda\quad S} \smallskip
(Note the final slash following {\tt groups} is required.).
The {\tt -p} option has no effect on output files.} % \bigbreak \subsection{Options affecting output format:} \nobreak\medskip\nobreak % \medbreak \defoption{-i}{This option applies to commands that construct and write out
either a permutation or a permutation group. It causes
permutations to be written in image format, rather
than in cycle format (the default).} % \medbreak \defoption{-n:{\it name}}{Here {\it name\/} is a string. The object created
by the command will be named {\it name}. By
default, the name assigned to the object will be
the name of the Cayley library containing its
definition. Note this option affects only the
name of the object, not that of the file or the
Cayley library.} % \medbreak \defoption{-q}{Suppresses informative messages on the state of the
computation, normally written to the standard output during
the computation.} % \medbreak \defoption{-s}{Causes statistics on the pruning of the backtrack
search tree to be written out to the standard output.
These statistics relate to the backtrack search tree
defined in the author's paper (Leon, 1991), and are
likely to be meaningful only to users familiar with that
paper.} % \medbreak \defoption{-w:{\it n}}{Here {\it n\/} should be a nonnegative integer.
This option applies only to coset representative
computations. If the degree is less
than or equal to {\it n}, and if a coset representative
is found, it will be included in the informative
messages written to the standard output. (In any case,
the coset representative will be written to a file in
Cayley library format.) The default value of {\it n}
is currently 300.} \bigbreak % \subsection{Options affecting performance of the algorithm:} \nobreak\medskip\nobreak \defoption{-b:{\it k}}{Here {\it k\/} is a nonnegative integer which
determines the extent to which base changes are performed
in an attempt to
improve pruning of the backtrack search tree using
tests on double--coset minimality (Leon, 1991, Prop~8).
When {\it k}~=~0,
base change is never performed (except during $\bfgermR$--base
construction, when it is used for a different purpose).
As {\it k\/} increases, the number of base change operations
performed increases; however,
increasing {\it k\/} beyond the base size produces no
further increase in the number of base change operations.
Designating {\it k}~=~0 reduces memory requirements and often
produces the best running times as well. On the other
hand, some high--density groups seem to require a higher
value of {\it k\/} in order to obtain acceptable performance.
By default, the program chooses a value of {\it k\/} based
on the density and degree of transitivity of the group;
quite often, this default value is 0. \smallskip
{\it Note:}\enskip For coset representative computations,
this option has no effect unless known subgroups of the two
associated groups are specified; see discussion of the
{\tt -kL} and {\tt -kR} options below.} % \medbreak \defoption{-g:$m$}{Here $m$ should be a nonnegative integer.
This is one of several parameters providing a
time vs.\ space tradeoff.
Small values of $m$, say 10 or less, minimize memory
requirements, while large values of $m$, say 100 or
greater, reduce the running time moderately for most
difficult groups. Use of a high value is recommended
for multiply transitive groups. \smallskip
After $\bfgermR$--base construction, the program attempts to
reduce the height of the Schreier trees for the
containing group by adding new strong generators. However,
it will never add generators for this purpose if doing
so would cause the total number of strong generators to
exceed $m$. (It will also stop adding generators if the height
falls below certain goals currently fixed in the program.)} % \medbreak \defoption{-k:$H$}{Here $H$ specifies a permutation group (in the format
{\it cayleyLibraryName\/} or
{\it fileName}\kern1pt::\kern1pt{\it cayleyLibraryName}).
This option applies only to subgroup
calculations. The group $H$ must
be a known subgroup of the group being computed. In
principle, this option allows one to take advantage
of any subgroup of the group being computed that happens
--> --------------------
--> maximum size reached
--> --------------------
Messung V0.5
¤ Dauer der Verarbeitung: 0.18 Sekunden
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
